Theory of Testing Computer Programs.

Abstract

The theoretical works on program testing by Goodenough and Gerhart, Howden, and Geller are unified and generalized by a new theoretical framework for testing presented in this thesis. The framework provides a mechanism for comparing the power of methods of testing programs based on the degree to which the methods approximate program verification. The framework also provides a reasonable and useful interpretation of the notion that successful tests increase one's confidence in the program's correctness. Applications of the framework include confirmation of a number of common assumptions about practical testing methods. Among the assumptions confirmed is the need for generating tests from specifications as well as programs. On the other h and , a careful formal analysis of assumptions surrounding mutation analysis shows that the "competent programmer hypothesis" does not suffice to ensure the claimed high reliability of mutation testing. Responding to the confirmed need for testing based on specifications as well as programs, the thesis describes a new method for generating test data from specifications expressed in predicate calculus. The new method has the advantages that, beside filling the gap just mentioned, it is very general, working on any order of logic, it is easy enough to be of practical use, it can be automated to a great extent, and it produces test data methodically and consistently that are of obvious utility for the problems studied.