A survey of combinatorial testing <s> Let US be the set of all the τ -way combinations that should be covered according to the model of SUT (P,V,R,C). Let Seeds be the set of test cases assigned by testers. Remove all the τ -way combinations covered by the test cases in Seeds from US. For each test case t, fitness(t)=the number of τ -way combinations in US covered by t, but uncovered by the generated test cases and Seeds While (US = ∅) <s> Robust Testing is a systematic test method that uses the OATS (Orthogonal Array Testing System) tool to convert information from product requirements or specifications into a concise set of tests. We found Robust Testing more than twice as productive as conventional testing practices for testing PMX/StarMAIL Release 2.2, a complex private mail exchange (PMX) local area network (LAN)-based electronic mail product that works with several types and versions of LAN software, operating systems, and personal computers (PCs). Robust Testing required less time, enabling us to complete testing on schedule. It found more potentially user-affecting faults, and inspired greater confidence in the quality of the delivered product. <s> BIB001 </s> A survey of combinatorial testing <s> Let US be the set of all the τ -way combinations that should be covered according to the model of SUT (P,V,R,C). Let Seeds be the set of test cases assigned by testers. Remove all the τ -way combinations covered by the test cases in Seeds from US. For each test case t, fitness(t)=the number of τ -way combinations in US covered by t, but uncovered by the generated test cases and Seeds While (US = ∅) <s> This paper describes a new approach to testing that uses combinatorial designs to generate tests that cover the pairwise, triple, or n-way combinations of a system's test parameters. These are the parameters that determine the system's test scenarios. Examples are system configuration parameters, user inputs and other external events. We implemented this new method in the AETG system. The AETG system uses new combinatorial algorithms to generate test sets that cover all valid n-way parameter combinations. The size of an AETG test set grows logarithmically in the number of test parameters. This allows testers to define test models with dozens of parameters. The AETG system is used in a variety of applications for unit, system, and interoperability testing. It has generated both high-level test plans and detailed test cases. In several applications, it greatly reduced the cost of test plan development. <s> BIB002 </s> A survey of combinatorial testing <s> Let US be the set of all the τ -way combinations that should be covered according to the model of SUT (P,V,R,C). Let Seeds be the set of test cases assigned by testers. Remove all the τ -way combinations covered by the test cases in Seeds from US. For each test case t, fitness(t)=the number of τ -way combinations in US covered by t, but uncovered by the generated test cases and Seeds While (US = ∅) <s> Pairwise testing (or 2-way testing) is a specification-based testing criterion, which requires that for each pair of input parameters of a system, every combination of valid values of these two parameters be covered by at least one test case. Empirical results show that pairwise testing is practical and effective for various types of software systems. We show that the problem of generating a minimum test set for pairwise testing is NP-complete. We propose a test generation strategy, called in-parameter-order (or IPO), for pairwise testing. For a system with two or more input parameters, the IPO strategy generates a pairwise test set for the first two parameters, extends the test set to generate a pairwise test set for the first three parameters, and continues to do so for each additional parameter. The IPO strategy allows the use of local optimization techniques for test generation and the reuse of existing tests when a system is extended with new parameters or new values of existing parameters. We present practical, IPO-based test generation algorithms. We describe the implementation of an IPO-based test generation tool and show some empirical results. <s> BIB003 </s> A survey of combinatorial testing <s> Let US be the set of all the τ -way combinations that should be covered according to the model of SUT (P,V,R,C). Let Seeds be the set of test cases assigned by testers. Remove all the τ -way combinations covered by the test cases in Seeds from US. For each test case t, fitness(t)=the number of τ -way combinations in US covered by t, but uncovered by the generated test cases and Seeds While (US = ∅) <s> Systems constructed from components, including distributed systems, consist of a number of elements that interact with each other. As the number of network elements or interchangeable components for each network element increases, the trade off that the system tester faces is the thoroughness of test configuration coverage, versus availability of limited resources (time and budget). An approach to resolving this trade off is to determine a minimal set of test configurations that test each pair-wise combination of components. This goal gives a well-defined, cost-effective level of test coverage, with a reduced number of system configurations. To select such a set of test configurations, we show how to apply the method of covering arrays, and improve on previous results. <s> BIB004 </s> A survey of combinatorial testing <s> Let US be the set of all the τ -way combinations that should be covered according to the model of SUT (P,V,R,C). Let Seeds be the set of test cases assigned by testers. Remove all the τ -way combinations covered by the test cases in Seeds from US. For each test case t, fitness(t)=the number of τ -way combinations in US covered by t, but uncovered by the generated test cases and Seeds While (US = ∅) <s> Component based software development is prone to unexpected interaction faults. The goal is to test as many-potential interactions as is feasible within time and budget constraints. Two combinatorial objects, the orthogonal array and the covering array, can be used to generate test suites that provide a guarantee for coverage of all t-sets of component interactions in the case when the testing of all interactions is not possible. Methods for construction of these types of test suites have focused on two main areas. The first is finding new algebraic constructions that produce smaller test suites. The second is refining computational search algorithms to find smaller test suites more quickly. In this paper we explore one method for constructing covering arrays of strength three that combines algebraic constructions with computational search. This method leverages the computational efficiency and optimality of size obtained through algebraic constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide some new bounds for some strength three covering arrays. <s> BIB005 </s> A survey of combinatorial testing <s> Let US be the set of all the τ -way combinations that should be covered according to the model of SUT (P,V,R,C). Let Seeds be the set of test cases assigned by testers. Remove all the τ -way combinations covered by the test cases in Seeds from US. For each test case t, fitness(t)=the number of τ -way combinations in US covered by t, but uncovered by the generated test cases and Seeds While (US = ∅) <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> BIB006 </s> A survey of combinatorial testing <s> Let US be the set of all the τ -way combinations that should be covered according to the model of SUT (P,V,R,C). Let Seeds be the set of test cases assigned by testers. Remove all the τ -way combinations covered by the test cases in Seeds from US. For each test case t, fitness(t)=the number of τ -way combinations in US covered by t, but uncovered by the generated test cases and Seeds While (US = ∅) <s> The increasing complexity of configurable software systems creates a need for more intelligent sampling mechanisms to detect and locate failure-inducing dependencies between configurations. Prior work shows that test schedules basedon a mathematical object, called a covering array, can beused to detect and locate failures in combination with a classification tree analysis. This paper addresses limitations ofthe earlier approach. First, the previous work requires developers to choose the covering array's strength, even thought here is no scientific or historical basis for doing so. Second, if a single covering array is insufficient to classify specificfailures, the entire process must be rerun from scratch. To address these issues, our new approach incrementally and adaptively builds covering array schedules. It begins witha low strength, and continually increases this as resources allow, or poor classification results require. At each stage, previous tests are reused. This allows failures due to only one or two configurations settings to be found and classified as early as possible, and also limits duplication of work when multiple covering arrays must be used. <s> BIB007
Generate a set of test cases randomly; Evolve the test set with a metaheuristic search method, such as simulated annealing, hill climbing, great flood, tabu search, particle swarm optimization, ant colony optimization, and genetic algorithm. Output the valid t (satisfying the constraints) with the highest fitness score. Remove all the τ -way combinations covered by the test cases t from US. End while. Mathematical methods for computing the covering array have been widely studied in the mathematic community and they are often published in mathematical journals. The study of covering array is an example of the interplay between pure mathematics and the applied problems generated by computer science  ]. Some mathematical methods compute test sets directly based on a mathematical function. These approaches are generally extensions of the mathematical methods for constructing orthogonal arrays. Some methods are based on recursive construction, which builds larger test sets from smaller ones BIB004  . For example, in Figure 9 (a), C A(m; 2, n, v) is an m× n matrix, representing a 2-way covering array. We can construct a larger C A(2m; 2, n 2 , v) by first concatenating n copies of CA horizontally, then below each ith copy of CA, generate a new array formed by repeating the i column in CA n times. A concrete example is shown in Figure 9 (b), where we use C A(4; 2, 3, 2) to construct a larger C A(8; 2, 9, 2). More detail can be found in BIB004 . But mathematical techniques (both direct and recursive) are not general. For example, we cannot use mathematical techniques to built a good covering array for a system with 10 parameters, each having six different values. Several test tools, such as TConfig  ], Combinatorial Test Services (CTS)  , and TestCover  ] all use mathematical constructions to generate covering arrays. Mathematical methods have two key advantages: (1) The computations involved are typically "lightweight," and they are immune to any combinatorial effect. (2) They can be extremely fast and can produce optimal test sets in some special cases. But they also have some disadvantages: (1) They often impose restrictions on the system configurations to which they can be applied. For example, many approaches require that the domain size be a prime number or power of a prime number. This significantly limits their applicability. (2) They currently do not effectively deal with test prioritization and constraint. Compared to the mathematical methods, computational approaches offer the following advantages: (1) They can be applied to an arbitrary system configuration, since there is no restriction on the number of parameters and the number of values each parameter can take. (2) They can be easily adapted for test prioritization and constraint handling. However, the computational approaches also have their own disadvantages: (1) They involve explicitly enumerating all possible combinations to be covered. When the number of combinations is large, explicit enumeration can be prohibitive in terms of both the space for storing these combinations and the time needed to enumerate them. (2) They are typically greedy, in the sense that they construct tests in a locally optimized manner which does not necessarily lead to a globally optimized test set. Thus, the generated test sets from computational approaches are often not minimal. The fourth group of test generation method is the random method, an ad hoc approach that randomly selects test cases from the complete set of test cases based on some input distribution. It is often compared with the other methods to study the effectiveness of test suite generation algorithm and the failure detection ability of the proposed methods . For some special cases, random search and search-based methods can do better than other methods. Techniques from the field of search-based software engineering proposed by Harman can be applied to improve the test suite for CT  ]. Test suite generated by search techniques is often smaller in size and better in constraint handling, as it integrates randomness and combination coverage. Researchers have begun to combine different methods to efficiently generate a small test suite. For example, BIB005 combine the recursive combinatorial constructions of mathematic methods with the simulated annealing of computational search methods. Their method leverages the computational efficiency and optimality of size obtained through combinatorial constructions while benefiting from the generality of a heuristic search. In theory, we can explore different combinations of the four main classes of test generation methods. For example, we can combine mathematical method with search method to generate a test suite, or combine heuristic greedy, random method and mathematical method together. There are C 2 4 + C 3 4 + C 4 4 = 11 combinations that we can study. There is still a lot of room to develop better methods for test generation for CT, and especially if we can explore some special ways to resolve some specific testing scenarios. Also, it is worthwhile to conduct a thorough study of various test generation methods to fully understand their limitations and strengths under various testing scenarios. 3.2.5. Test Case Generation Tools. More than 20 software tools have been developed for test case generation, for example, CATS (Constrained Array Test System) developed by BIB006 , OATS (Orthogonal Array Test System) developed by Phadke et al. BIB001 , AETG developed by BIB002 , IPO developed by BIB003 , Tconfig developed by  , CTS (Combinatorial Test Service) developed by IBM, and PICT developed by Microsoft  ]. We have also developed the SST tool for test generation  . Some new tools are still continually appearing. Many of these tools are freeware. As each tool has its own characteristics and advantages, none is the best for all settings. If possible we may use them together, and then choose the best result. Some integrated tools have been developed to generate a minimal test suite T c . Test generation involves mainly four factors and each factor has many cases, as shown in Figure 8 . For example, for covering array, we can use EC, BC, OA, PW, τ -way covering array, or the combination of these test suites, and even the increment adaptive covering array BIB007 ]. The test generation method can be greedy, heuristic search, mathematic, random, or some combination of these methods. In the process of test generation we may or may not need to deal with constraints, and we may or may not need to assign some seeds. From Figure 8 , we can see that there are at least 5 × 2 × 2 × 5 = 100 scenarios. Therefore it is a big challenge to totally resolve the many issues of test generation. All existing tools have their own advantages and disadvantages. There is a need to develop some more effective and more convenient tools for test generation. For example, we can build a platform that integrates several tools together. Then, the best test set can be selected depending on the specific testing requirements.