A survey of combinatorial testing <s> Failure Diagnosis <s> Approaches to software testing based on methods from the field of design of experiments have been advocated as a means of providing high coverage at relatively low cost. Tools to generate all pairs, or higher n-degree combinations, of input values have been developed and demonstrated in a few applications, but little empirical evidence is available to aid developers in evaluating the effectiveness of these tools for particular problems. We investigate error reports from two large open-source software projects, a browser and Web server, to provide preliminary answers to three questions: Is there a point of diminishing returns at which generating all n-degree combinations is nearly as effective as all n+1-degree combinations? What is the appropriate value of n for particular classes of software? Does this value differ for different types of software, and by how much? Our findings suggest that more than 95% of errors in the software studied would be detected by test cases that cover all 4-way combinations of values, and that the browser and server software were similar in the percentage of errors detectable by combinations of degree 2 through 6. <s> BIB001 </s> A survey of combinatorial testing <s> Failure Diagnosis <s> Exhaustive testing of computer software is intractable, but empirical studies of software failures suggest that testing can in some cases be effectively exhaustive. We show that software failures in a variety of domains were caused by combinations of relatively few conditions. These results have important implications for testing. If all faults in a system can be triggered by a combination of n or fewer parameters, then testing all n-tuples of parameters is effectively equivalent to exhaustive testing, if software behavior is not dependent on complex event sequences and variables have a small set of discrete values. <s> BIB002 </s> A survey of combinatorial testing <s> Failure Diagnosis <s> Pairwise testing is one of very practical and effective testing methods for various types of software systems. This paper proposes a novel debugging method based on pairwise testing. By analyzing the test cases and retesting with some complementary test cases, the method can narrow the factors that cause the errors in a very small range. So it can provide a very efficient and valuable guidance for the software testing and debugging. <s> BIB003 </s> A survey of combinatorial testing <s> Failure Diagnosis <s> Many modern software systems are designed to be highly configurable so they can run on and be optimized for a wide variety of platforms and usage scenarios. Testing such systems is difficult because, in effect, you are testing a multitude of systems, not just one. Moreover, bugs can and do appear in some configurations, but not in others. Our research focuses on a subset of these bugs that are "option-related"-those that manifest with high probability only when specific configuration options take on specific settings. Our goal is not only to detect these bugs, but also to automatically characterize the configuration subspaces (i.e., the options and their settings) in which they manifest. To improve efficiency, our process tests only a sample of the configuration space, which we obtain from mathematical objects called covering arrays. This paper compares two different kinds of covering arrays for this purpose and assesses the effect of sampling strategy on fault characterization accuracy. Our results strongly suggest that sampling via covering arrays allows us to characterize option-related failures nearly as well as if we had tested exhaustively, but at a much lower cost. We also provide guidelines for using our approach in practice. <s> BIB004 </s> A survey of combinatorial testing <s> Failure Diagnosis <s> The identification of interaction faults in component-based systems has focused on indicating the presence of faults, rather than their location and magnitude. While this is a valuable step in screening a system for interaction faults prior to its release, it provides little information to assist in the correction of such faults. Consequently tests to reveal the location of interaction faults are of interest. The problem of nonadaptive location of interaction faults is formalized under the hypothesis that the system contains (at most) some number d of faults, each involving (at most) some number t of interacting factors. Restrictions on the number and size of the putative faults lead to numerous variants of the basic problem. The relationships between this class of problems and interaction testing using covering arrays to indicate the presence of faults, designed experiments to measure and model faults, and combinatorial group testing to locate faults in a more general testing scenario, are all examined. While each has some definite similarities with the fault location problems for component-based systems, each has some striking differences as well. In this paper, we formulate the combinatorial problems for locating and detecting arrays to undertake interaction fault location. Necessary conditions for existence are established, and using a close connection to covering arrays, asymptotic bounds on the size of minimal locating and detecting arrays are established. ::: ::: A final version of this paper appears in J Comb Optim (2008) 15: 17-48. <s> BIB005
After detecting a failure, we need to investigate the failure to locate and then remove the fault. BIB001 and BIB002 suggested that software faults are often triggered by only a few interacting variables. Their results have important implications for CT. If all faults in SUT are triggered by a combination of no more than n parameters, then testing all n-way combinations of parameters can provide a high confidence that nearly all faults have been discovered. So CT is an effective approach for detecting failures triggered by the combination of parameter values. When a defect is exposed in CT, we should determine which specific combination of parameter values causes the failure, or which value schema of SUT triggers the failure. Failure diagnosis by finding failure-triggering schema is also called fault characterization. Fault characterization in CT can help developers quickly pinpoint the causes of failures, hopefully leading to a quicker turn-around time for bug fixes. Automated techniques, which can effectively, efficiently, and accurately perform fault characterization, can save a great deal of time and money. This is especially beneficial when system configuration spaces are large, the software changes frequently, and resources are limited. BIB004 applied CT and fed the testing results to a classification tree algorithm to localize the observed faults. Their results suggested that sampling via covering arrays can characterize option-related failures nearly as well as if we had tested exhaustively, but at a much lower cost. BIB003 presented a further testing strategy for fault revealing and failure diagnosis, which first tests SUT with a covering array, then reduces the value schemas contained in the failed test case by eliminating those appearing in the passed test cases. If the failure-causing schema is found in the reduced schema set, failure diagnosis is completed with the identification of the specific input values which caused the failure; otherwise, a further test suite based on SOFOT is developed for each failed test cases, testing is repeated, and the schema set is then further reduced, until no more failure is found or the fault has been located. For example, when we test NGS (Figure 2 ) with the test suite in Figure 3 , if t 1 = (Netscape, Windows, ISDL, Creative) failed, and other test cases passed, we can generate M = M t 1 − t is passed M t , M has many schemas. If we cannot find the failurecausing schema, we then design a further test suite T t 1 for t 1 with SOFOT, T t 1 = {(I E, Windows, ISDL, Creative) (Netscape, Linux, ISDL, Creative) (Netscape, Windows, V P N, Creative) (Netscape, Windows, ISDL, Maya)}. After we execute T t 1 again, if only the second test failed, we compute M = M t 1 − t is passed M t again. Since M may be greatly reduced, we can find the failure-causing schema in M more easily. More detail can be found in BIB003 . Colbourn [2006] and BIB005 extended the notion of a covering array to detecting and locating arrays, which forms fault interaction test suites that permit the location of a specified number of faults of specified strength. Additional work is needed to develop better methods for failure diagnosis. There is also a lack of empirical results on the various failure diagnosis methods. Another fruitful area of study is to make use of the results from CT to localize the fault and fix it, as valuable information about the fault can be gained from the failed test cases.