The testing of a computer programs is an inductive process whereby the execution of a program on a large number of different inputs causes our belief in its correctness to be increased. Unfortunately we know that sheer numbers of test inputs are not enough, and we need a method that differentiates important test cases from the vast majority of totally uninteresting ones. This thesis analyzes one such method, called mutation analysis.

Mutation analysis asserts that those test cases are important which differentiate, in the sense of being correctly processed by one and incorrectly processed by the other, the original program from programs very similar in structure and meaning. These alternative programs are called mutants of the original. The power of this method is further increased by two observations: the coupling effect, which asserts that complex errors can often be detected by the analysis of a small set of simple alternatives; and the competent programmer hypothesis, which asserts that most programs are, when they reach the stage of development considered here, a close approximation to being correct.

In this thesis the mutation analysis method is first described in very general terms. The thesis then pursues two very different directions: The first is to give formal meanings to the terms “mutants”, “errors”, “coupling effect”, and “competent programmer” and prove in a restricted programming domain a theorem concerning the coupling of simple and complex errors. Several results of this nature are proved for decision tables and for a set of linear recursive LISP programs. The second direction is to study a realistic programming language and to ask whether in a statistical sense the coupling effect occurs. A system to implement mutation analysis for FORTRAN programs is described and compared to other testing methods. Several further studies using this system are described, including analyses of the system’s error-detection capabilities, the machine and human resources it requires, and difficulties involved in using it. The last includes the problem of deciding whether a program and its mutant are computationally equivalent.

The thesis concludes with a summary and a discussion of 5 possible areas for future research.

…Credit must be given to my advisor, Richard Lipton, who originated the concept of mutation analysis and encouraged me to pursue it. The second greatest influence over this work came from Frederick Sayward, who for the 4 years I have known him has been a great friend as well as colleague. The third member of my committee is Alan Perlis, who I want to thank for his prompt reading and careful comments, as well as for many lively and enjoyable discussions during my 4 years at Yale.

See Also: