A survey of combinatorial testing <s> CONCLUSION AND FUTURE WORK <s> Combination strategies are test-case selection methods where test cases are identifled by combining values of the difierent test object input parameters based on some combinatorial strategy. This survey presents 15 difierent combination strategies, and covers more than 30 papers that focus on one or several combination strategies. We believe this collection represents most of the existing work performed on combination strategies. This survey describes the basic algorithms used by the combination strategies. Some properties of combination strategies, including coverage criteria and theoretical bounds on the size of test suites, are also included in this description. This survey paper also includes a subsumption hierarchy that attempts to relate the various coverage criteria associated with the identifled combination strategies. Finally, this survey contains short summaries of all the papers that cover combination strategies. <s> BIB001 </s> A survey of combinatorial testing <s> CONCLUSION AND FUTURE WORK <s> Interaction testing is widely used in screening for faults. In software testing, it provides a natural mechanism for testing systems to be deployed on a variety of hardware and software configurations. Several algorithms published in the literature are used as tools to automatically generate these test suites; AETG is a well known example of a family of greedy algorithms that generate one test at a time. In many applications where interaction testing is needed, the entire test suite is not run as a result of time or cost constraints. In these situations, it is essential to prioritize the tests. Here we adapt a "one-test-at-a-time" greedy method to take importance of pairs into account. The method can be used to generate a set of tests in order, so that when run to completion all pairwise interactions are tested, but when terminated after any intermediate number of tests, those deemed most important are tested. Computational results on the method are reported. <s> BIB002 </s> A survey of combinatorial testing <s> CONCLUSION AND FUTURE WORK <s> A covering arrayCA(N;t,k,v) is an N × k array such that every N × t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t-sets of component interactions. We introduce a combinatorial technique for their construction, focussing on covering arrays of strength 3 and 4. With a computer search, covering arrays with improved parameters have been found. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 202–213, 2006 <s> BIB003 </s> A survey of combinatorial testing <s> CONCLUSION AND FUTURE WORK <s> Combinatorial testing could detect the faults triggered by the interactions among factors in software. But in many cases, the pair-wise, N-way and even the variable strength combinatorial testing may lead test suite redundancy and fault detect ability decreasing, because these methods do not make sufficient consideration on the actual factors interaction. In this paper, a new interaction relationship based combinatorial testing model was proposed to cover the actual factor interactions in software by extending the conventional combinatorial testing model and IO relationship testing model. The new method may be more effectively than existed combinatorial testing methods without decrease of the fault detect ability. Furthermore, two test suite generation algorithms for interaction relationship based combinatorial testing were also presented. Finally, we compared our algorithms with some similar test generation algorithms in IO relationship testing model, and the experience result showed the advantage of our algorithms. <s> BIB004 </s> A survey of combinatorial testing <s> CONCLUSION AND FUTURE WORK <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
In the last 20 years, combinatorial testing has been widely studied and applied. Now, it has become a well-accepted testing method, given its proven ability of detecting interaction failures. Many topics have been studied over the years, such as modeling of SUT, test suite generation, the application of CT, test prioritization, failure diagnosis, metric, and evaluation. In this article, we make four major contributions: (1) To our best knowledge, this is the first complete and systematic survey for CT, as an independent software testing technique, although BIB001 have given a survey on combinatorial testing strategy, focusing mainly on test cases generation. We have made an careful survey on over 90 key papers. (2) We classified all the work of CT into eight categories according to the testing procedure. For each category, we surveyed the motivation, key issues, solutions, and the current state of research. (3) We reviewed the contributions of the different research groups, and presented the growing trend of CT research. (4) Based on our study and other knowledge, we recommend the following areas of focus in CT research in the future. (1) A good model of the test parameters is critical to CT. We need effective ways to identify the parameters of SUT, determine the values of each parameter, and explore the interactions and constraints existing among the parameters. To be effective in detecting defects, not only do we need a good understanding of the limitations and strengths of CT, but also a good model of SUT that includes all relevant parameters, their values, interactions, and constraints. (2) Although many methods have been proposed to generate test suite for CT, as the problem of test suite generation is NP-hard, there is room for further improvement of these test generation methods. In particular, a good method should support the use of seeding and make full use of constraints in generating a set of feasible test cases. Various mathematical methods, computational methods, and their crossover combinations can play an important role in improving test generation. (3) As there exist failures which are caused by the interaction of more than 2 factors in SUT, and for certain critical SUT, we may want to test more combinations to ensure its quality. Thus there is a need for the test suite generation algorithms for τ -way(τ > 2). Although the IPOG, density algorithm, simulated annealing, and some mathematical techniques have been used to generate τ -way covering array(usually τ = 3), there has been relative little work on τ -way compared to 2-way, and more work is needed in this area. (4) To realize the full potential of CT, better strategies and methods need to be developed to make use of the testing result from CT to support further testing, failure diagnosis, and evaluation. (5) As CT generally requires a large number of tests, it is impractical to conduct manual testing and results analysis. Tools are needed to support the many testing steps. More work is needed in integrating the test generation tools with other tools to automate the entire testing process of CT. (6) Another fruitful area of research in CT is to expand it to different levels of testing. For example, we can explore the application of CT in unit testing, integration testing, and system testing. We can also investigate how to apply CT to different types of software, such as object-oriented software, service-oriented software, etc. (7) There is a lack of empirical results in CT. We need to conduct more studies and collect more evidence to fully understand the limitations and strengths of CT. For example, there is still no empirical study on the effect of the prioritization by interaction coverage. (8) One approach to overcome the weakness of CT is to combine this technique with other testing techniques. We can try to incorporate the concept of CT into other testing techniques or to expand CT by including other testing techniques. For example, we may combine CT with test case prioritization to ensure the most important test cases are executed early; we can also combine CT with metamorphic testing to solve the oracle problem of CT by automating the process to determine whether a test passes or fails. Bryce et al. made many contributions on test generation, failure diagnosis, and prioritization. Sherwood first introduced the CATS tool, which implemented a heuristic algorithm for pairwise coverage  ]. This group discussed two algebraic approaches to generate covering array, which could be used to build mixed covering array of strength 2 and covering array of higher strength BIB003 , and introduced several greedy algorithms to construct covering arrays, mixed-level covering arrays, and -biased covering arrays BIB004 ]. Colbourn later proposed the failure locate and detect array  BIB005 . Bryce and Colbourn proposed a deterministic density algorithm to generate a test set for pairwise testing and a higher strength covering array BIB002 Colbourn 2007a, 2008] . They then defined the problem of test suite prioritization, proposed solutions both generating prioritized test suites from scratch and prioritizing existing test suites by combinatorial coverage for GUI and Web applications, and conducted an empirical study on prioritized CT with seeding and constraints BIB002  .