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. 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> 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. While (US = ∅) <s> Pairwise 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. The authors propose a novel test generation strategy for pairwise testing. <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. While (US = ∅) <s> There has been an emerging trend to develop software using different components. In this way the cost of the software reduces and the developer is able to complete the system efficiently. The components' code may or may not be visible to the developer. Testing, in this case, requires the development of a set of test configurations that can be applied on the software. However, for software that comprises a large number of components, it is infeasible to test each and every test configuration within the limited testing budget and time. In this paper we propose a GA-based technique that identifies a set of test configurations that are expected to maximize pair-wise coverage, with the constraint that the number of test configurations is predefined. Although the paper primarily focuses on the interaction between software components, the idea can be applied to single code component testing. We performed some experiments using our proposed approach. The results were promising. <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. While (US = ∅) <s> Complete interaction testing of components is too costly in all but the smallest systems. Yet component interactions are likely to cause unexpected faults. Recently, design of experiment techniques have been applied to software testing to guarantee a minimum coverage of all t-way interactions across components. However, t is always fixed. This paper examines the need to vary the size of t in an individual test suite and defines a new object, the variable strength covering array that has this property. We present some computational methods to find variable strength arrays and provide initial bounds for a group of these objects. <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. 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. While (US = ∅) <s> Software system faults are often caused by unexpected interactions among components. Yet the size of a test suite required to test all possible combinations of interactions can be prohibitive in even a moderately sized project. Instead, we may use pairwise or t-way testing to provide a guarantee that all pairs or t-way combinations of components are tested together This concept draws on methods used in statistical testing for manufacturing and has been extended to software system testing. A covering array, CA(N; t, k, v), is an N/spl times/k array on v symbols such that every N x t sub-array contains all ordered subsets from v symbols of size t at least once. The properties of these objects, however do not necessarily satisfy real software testing needs. Instead we examine a less studied object, the mixed level covering array and propose a new object, the variable strength covering array, which provides a more robust environment for software interaction testing. Initial results are presented suggesting that heuristic search techniques are more effective than some of the known greedy methods for finding smaller sized test suites. We present a discussion of an integrated approach for finding covering arrays and discuss how application of these techniques can be used to construct variable strength arrays. <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. While (US = ∅) <s> Combinatorial testing is a specification-based testing criterion, which requires that for each t-way combination of input parameters of a system, every combination of valid values of these t parameters be covered by at least one test case. This approach is motivated by the observation that in many applications a significant number of faults are caused by interactions of a smaller number of parameters. In this paper, we propose new test generation algorithms for combinatorial testing based on two artificial life techniques: a genetic algorithm (GA) and an ant colony algorithm (ACA). The usefulness of these algorithms is demonstrated through experiments. In the case t = 3 in particular, our algorithms exhibited impressive results <s> BIB007 </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. While (US = ∅) <s> Combinatorial testing is a specification-based testing method, which can detect the faults triggered by interaction of factors. For one kind of software in which the interactions only exist between neighbor factors, this paper proposes the concept of neighbor factors combinatorial testing, presents the covering array generation algorithms for neighbor factors pair-wise (N=2) coverage, neighbor factors N-way (N\geqslant2) coverage and variable strength neighbor factors coverage, and proves that the covering arrays generated by these three algorithms are optimal. Finally we analyze an application scenario, which shows that this approach is very practical. <s> BIB008 </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. While (US = ∅) <s> Most existing work on t-way testing has focused on 2-way (or pairwise) testing, which aims to detect faults caused by interactions between any two parameters. However, faults can also be caused by interactions involving more than two parameters. In this paper, we generalize an existing strategy, called in-parameter-order (IPO), from pairwise testing to t-way testing. A major challenge of our generalization effort is dealing with the combinatorial growth in the number of combinations of parameter values. We describe a t-way testing tool, called FireEye, and discuss design decisions that are made to enable an efficient implementation of the generalized IPO strategy. We also report several experiments that are designed to evaluate the effectiveness of FireEye <s> BIB009 </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. While (US = ∅) <s> Algorithms for the construction of software interaction test suites have focussed on the special case of pairwise coverage; less is known about efficiently constructing test suites for higher strength coverage. The combinatorial growth of t-tuples associated with higher strength hinders the efficacy of interaction testing. Test suites are inherently large, so testers may not run entire test suites. To address these problems, we combine a simple greedy algorithmallwith heuristic search to construct and dispense one test at a time. Our algorithm attempts to maximize the number of t-tuples covered by the earliest tests so that if a tester only runs a partial test suite, they test as many t-tuples as possible.allHeuristic search is shown to provide effective methods for achieving such coverage. <s> BIB010 </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. While (US = ∅) <s> This paper presents two strategies for multi-way testing (i.e. t-way testing with t>2). The first strategy generalizes an existing strategy, called in-parameter-order, from pairwise testing to multi-way testing. This strategy requires all multi-way combinations to be explicitly enumerated. When the number of multi-way combinations is large, however, explicit enumeration can be prohibitive in terms of both the space for storing these combinations and the time needed to enumerate them. To alleviate this problem, the second strategy combines the first strategy with a recursive construction procedure to reduce the number of multi-way combinations that have to be enumerated. Both strategies are deterministic, i.e. they always produce the same test set for the same system configuration. This paper reports a multi-way testing tool called FireEye, and provides an analytic and experimental evaluation of the two strategies. Copyright © 2007 John Wiley & Sons, Ltd. <s> BIB011 </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. While (US = ∅) <s> Combinatorial testing is a practical software testing approach that has been widely used in practice. Most research and applications of such approach focus on N-way combinatorial testing that provides a minimum coverage of all N-way interactions among factor. However, the strengths of different interactions may not be a fixed integer N, but a variable. Therefore, variable strength combinatorial testing approach is necessary in applications. Existing variable strength combinatorial testing, which allows some interactions have a higher strength than others, has a limitation that such higher-strength interactions must be disjoint. To avoid such a limitation, an improved variable strength combinatorial testing approach, which makes a more sufficient consideration on actual interaction relationship, is proposed in this article. Furthermore, two greedy heuristic algorithms are also proposed to generate combinatorial test suite. Compared to some existing algorithms and tools, the proposed algorithms have advantages on both the execution effectiveness and the optimality of generated test suite. Experimental results can prove such advantages. <s> BIB012
Generate a test case t to cover the most uncovered τ -way combinations. Check the constraints and ensure it is valid. Remove all the the τ -way combinations covered by the test cases t from US. End while. The second class of greedy algorithm is the In Parameter Order (IPO) algorithm. This class of algorithm begins by generating all τ -sets for the first τ factors and then incrementally expands the solution, both horizontally and vertically using heuristics until the array is complete. BIB001 , BIB002 , and BIB009 BIB011 described an algorithm for generating 2-way and τ -way covering array. We gave a greedy algorithm based on solution space tree to generate 2-way array  and extended the existing greedy algorithms for VCA BIB008 BIB012 . Heuristic search techniques such as hill climbing, great flood, tabu search, and simulated annealing have been applied to τ -way covering array and VCA generation. Also some AI-based search techniques such as Genetic Algorithm (GA) and Ant Colony Algorithm(ACA) have also been used. Heuristic search techniques start from a preexisting test set and then apply a series of transformations to the test set until it covers all the combinations. BIB003 used a GA-based technique that identifies a set of test configurations that are expected to maximize pairwise coverage with a predefined number of test cases. BIB010 augmented the one-test-at-a-time greedy algorithm with a heuristic search, which can generate tests that have a high rate of τ -tuple coverage. This approach combines the speed of greedy methods with the slower but more accurate heuristic search techniques. The hybrid approach seems to achieve a more rapid convergence of τ -tuple coverage than either greedy or heuristic search alone. They compared four heuristic search techniques and found that hill climbing is effective only when time is severely constrained, but tabu search, simulated annealing, and the great flood perform better over a longer time. BIB004 BIB005 BIB006 reported using the computational method of simulated annealing to generate 3-way covering array and variable strength array. BIB007 also used the genetic algorithm and ant colony algorithm to generate the 3-way covering array. Heuristic search techniques can often produce a smaller test set than those from the greedy algorithm, but typically require a longer computation. In the following we give a generic search algorithm for covering array generation.