A survey of combinatorial testing <s> A.7. Kuhn et al. <s> (L, d)-universal sets are useful for exhaustively testing logic circuits with a large number of functional components, designed so that every functional component depends on at most d inputs. Randomized and deterministic constructions of (L, d)-universal test sets are presented, and lower and upper bounds on the optimal sizes of such sets are proven. It is also proven that the design of an optimal exhaustive test set for an arbitrary logic circuit is an NP-complete problem. > <s> BIB001 </s> A survey of combinatorial testing <s> A.7. Kuhn et al. <s> The significant expansion of autonomous control and information processing capabilities in the coming generation of mission software systems results in a qualitatively larger space of behaviors that needs to be "covered" during testing, not only at the system level but also at subsystem and unit levels. A major challenge in this area is to automatically generate a relatively small set of test cases that, collectively, guarantees a selected degree of coverage of the behavior space. This paper describes an algorithm for a parametric test case generation tool that applies a combinatorial design approach to the selection of candidate test cases. Evaluation of this algorithm on test parameters from the Deep Space One mission reveals a valuable reduction in the number of test cases, when compared to an earlier home-brewed generator. <s> BIB002 </s> A survey of combinatorial testing <s> A.7. Kuhn et al. <s> A 1976 block design enumeration algorithm has been reimplemented with a number of enhancements. Its use is demonstrated with a number of case studies involving different kinds of incidence structures. New results include the enumeration of weakly union-free twofold triple systems of orders 12 and 13, Mendelsohn triple systems of orders 10 and 12, 2-(8, 4, 9), 2-(10, 4, 4), 2-(16, 4, 2), 3-(11, 5, 4) and 4-(12, 6, 4) block designs, and 2-(7, 3, λ) designs for 14 ≤ λ ≤ 16. Some of these results correct enumerations previously published in the literature. Additional results confirm independently produced results, some of which have been published quite recently. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 239–260, 2000 <s> BIB003 </s> A survey of combinatorial testing <s> A.7. Kuhn et al. <s> Testers face the challenge of doing as much testing as possible within the available, and usually constrained, schedule. In the hypercompetitive commercial marketplace, it is not practical to exhaustively test all combinations of system test cases. This paper discusses the author’s experience with a method that generates a small subset of test cases which provides good coverage of the test domain—the Combinatorial Design Method. It has proven to be flexible for system level testing of small, commercial satellite ground systems. Cost savings of 67% and schedule savings of 68% are shown for an example. <s> BIB004 </s> A survey of combinatorial testing <s> A.7. Kuhn et al. <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> BIB005 </s> A survey of combinatorial testing <s> A.7. Kuhn et al. <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> BIB006 </s> A survey of combinatorial testing <s> A.7. Kuhn et al. <s> A t-covering array is a collection of k vectors in a discrete space with the property that, in any t coordinate positions, all combinations of the coordinate values occur at least once. Such arrays have applications, for example, in software testing and data compression. Covering arrays are sometimes also called t-surjective arrays or qualitatively t-independent families; when t=2 covering arrays are also called group covering designs or transversal covers. In an optimal covering array the number of vectors is minimized. Constructions for optimal covering arrays are known when t=2 and the vectors are binary vectors, but in the other cases only upper and lower bounds are known. In this work a tabu search heuristic is used to construct covering arrays that improve on the previously known upper bounds on the sizes of optimal covering arrays. <s> BIB007 </s> A survey of combinatorial testing <s> A.7. Kuhn et al. <s> We examine an abstract formulation of BIST diagnosis in digital logic systems. The BIST diagnosis problem has applications that include identification of erroneous test vectors, faulty scan cells, faulty modules, and faulty logic blocks in FPGAs. We develop an abstract model of this problem and show a fundamental correspondence to the well-established subject of combinatorial group testing (CGT) [Ding-Zhu Du et al., (1994)]. Armed with this new perspective, we show how to improve on a number of existing techniques in the VLSI diagnosis literature. In addition, we adapt and apply a number of CGT algorithms that are well-suited to the diagnosis problem in the digital realm. We also propose completely new methods and empirically evaluate the different algorithms. Our experiments show that results of the proposed algorithms outperform recent diagnosis techniques [J. Ghosh-Dastidar et al. (1999), (2000), J. Rajski et al. (1997)]. Finally, we point out future directions that can lead to new solutions for the BIST diagnosis problem. <s> BIB008 </s> A survey of combinatorial testing <s> A.7. Kuhn et al. <s> Covering arrays have been studied for their applications to drug screening and software and hardware testing. In this paper, we model the problem as a constraint program. Our proposed models exploit non-binary (global) constraints, redundant modelling, channelling constraints, and symmetry breaking constraints. Our initial experiments show that with our best integrated model, we are able to either prove optimality of existing bounds or find new optimal values for arrays of moderate size. Local search on a SAT-encoding of the model is able to find improved bounds on larger problems. <s> BIB009 </s> A survey of combinatorial testing <s> A.7. Kuhn et al. <s> Software testing is expensive and time consuming. Given the different input parameters with multiple possible values for each parameter, performing exhaustive testing which tests all possible combinations is practically impossible. Generating an optimal test set which will effectively test the software system is therefore desired. Pair-wise testing is known for its effectiveness in different types of software testing. Pair-wise testing requires that for a given numbers of input parameters to the system, each possible combination of values for any pair of parameters be covered by at least one test case. Pair-wise testing is known for its effectiveness in different types of software testing. The problem of generating a minimum size test set for pair-wise testing is NP-complete. This paper presents new techniques for reducing the number of test cases for pair-wise testing. The paper shows an algorithm to generate test cases for 2-valued parameters and how orthogonal arrays and ordered designs may be used for deriving test cases for parameters with more than two values. Moreover, using mixed-level or asymmetric orthogonal array as tool, we present test set generation strategy for parameters with different number of values. A comparison of empirical results with previous test generation strategies "AETG" and "IPO" shows that the number of test cases generated with the proposed methodology is never higher and in some cases significantly lower than using AETG or IPO <s> BIB010 </s> A survey of combinatorial testing <s> A.7. Kuhn et al. <s> Combinatorial covering arrays have been used in several testing approaches. This paper first discusses some existing methods for finding such arrays. Then a SAT-based approach and a backtracking search algorithm are presented to solve the problem. A novel pruning strategy called SCEH is proposed to increase the efficiency of the methods. Several existing search heuristics and symmetry breaking techniques are also used in the backtracking search algorithm. Lastly, this paper introduces a tool called EXACT (EXhaustive seArch of Combinatorial Test suites) which implements all the above techniques to construct the covering arrays automatically. The experimental results show that our backtracking search method outperforms other methods in many small size cases. <s> BIB011 </s> A survey of combinatorial testing <s> A.7. Kuhn et al. <s> Covering arrays can be applied to the testing of software, hardware and advanced materials, and to the effects of hormone interaction on gene expression. In this paper we develop constraint programming models of the problem of finding an optimal covering array. Our models exploit global constraints, multiple viewpoints and symmetry-breaking constraints. We show that compound variables, representing tuples of variables in our original model, allow the constraints of this problem to be represented more easily and hence propagate better. With our best integrated model, we are able to either prove the optimality of existing bounds or find new optimal solutions, for arrays of moderate size. Local search on a SAT-encoding of the model is able to find improved solutions and bounds for larger problems. <s> BIB012
Kuhn et al. studied the effectiveness of CT in a variety of application domains. Their research showed that about 20%-70% of software faults were triggered by single parameters, about 50%-95% of faults were triggered by two or fewer parameters, and about 15% were triggered by three or more parameters. Thus, CT, especially pairwise testing, is very effective in practice. Later they studied the fault interactions of large distributed systems, and discovered that the failure-triggering interactions of this kind of systems are mostly 4 to 6 BIB005 BIB006 . Their work shows that CT can be as effective as exhaustive testing in some cases, if all failures can be triggered by an interaction of 6 or fewer parameter values. to generate test suite for pairwise testing. BIB010 presented a pairwise test set generation strategy for parameters with different number of values. BIB002 proposed an algorithm to generate test suite using the combinatorial design approach.  described an efficient algorithm for generating tests that cover a prescribed set of combinations of parameters based on repeatedly coloring the vertices of a graph. BIB003 reimplemented the block design enumeration algorithm with a number of enhancements and demonstrated its use with several case studies involving different kinds of incidence structures. BIB007 used a tabu search heuristic to construct covering arrays and improved on the previously known upper bounds of the sizes of optimal covering arrays. Recently BIB011 presented a SAT-based approach and a backtracking search algorithm to generate a covering array. Other researchers also reported their experience in the application of CT. For example,  discussed the pairwise testing and its application.  focused on ways to make the pure pairwise testing approach more practical and on features of tools that support pairwise testing in practise. BIB008 adapted and applied a number of CT algorithms to resolve the diagnosis problem. BIB001 gave methods to generate the τ -way covering array for logic circuits where each parameter has two values, and proved that the design of an optimal test suite for an arbitrary circuit is an NP-complete problem. BIB009 BIB012 developed constraint programming models of the problem of finding an optimal covering array and exploited global constraints, multiple viewpoints, and symmetry-breaking constraints. BIB004 also presented his experience with applying CT. White and Almezen [2000] generated a complete interaction sequence for GUI testing.