Test data generation is one of the most critical phases of software testing in the sense that it has the greatest impact on the success or failure of the test to achieve its purpose. The problem of test data selection can be formulated simply as follows: Given an input space S (which is assumed to be so large that it is impractical to test the program on all elements of S), choose a small subset T of S such that we can achieve the goal of the test by executing the candidate program on T rather than on S. Clearly, the requirement that T must satisfy depends on the goal of the test. We consider two possible requirements:

1. A Logical Requirement. Any program that runs successfully for all elements of T runs successfully for all elements of S. Note that this is equivalent to the following property: If a candidate program P fails on some element s of S, then there exists an element t of T such that execution of P on the element t fails.
2. A Stochastic Requirement. The reliability observed on the execution of a candidate program P on T is lower than, or the same as (an approximation of), the reliability observed on the execution of a candidate program P on S. So that any reliability claim made on the basis of observations made during the testing phase, when input data is limited to T, will be borne out during the operation phase, when the input ranges over all of S.

It is important to note that these two requirements are dependent on the oracle used in the test; it is conceivable that for each requirement, the stronger the oracle (corresponding to a more-refined specification), the larger is set T; this will be discussed in Chapter 11.