One of the key concepts in testing is that of adequate test sets. A test selection criterion decides which test sets are adequate. In this paper, a language schema for specifying a large class of test selection criteria is developed; the schema is based on two operations for building complex criteria from simple ones. Basic algebraic properties of the two operations are derived. In the second part of the paper, a simple language-an instance of the general schema-is studied in detail, with the goal of generating small adequate test sets automatically. It is shown that one version of the problem is intractable, while another is solvable by an efficient algorithm. An implementation of the algorithm is described.
@cite_11: Testing has long been in need of mathematical underpinnings to explain its value as well as its limitations. This paper develops and applies a mathematical framework that 1) unifies previous work on the subject, 2) provides a mechanism for comparing the power of methods of testing programs based on the degree to which the methods approximate program verification, and 3) provides a reasonable and useful interpretation of the notion that successful tests increase one's confidence in the program's correctness.
Gourlay @cite_11 presents a precise framework for the discussion of issues in testing. In his terminology, our test selection criteria are a special form of the test methods for the set-choice construction testing system. Gourlay reinterprets previously published discussions about the suitability of various test selection criteria. In our approach, we do not attempt to decide a priori which criteria are sufficient --- we leave that decision to the test designer. That is why we emphasize the importance of a language in which criteria are specified.