A survey of combinatorial testing <s> Definitions of Test Suite for CT <s> Orthogonal Latin squares—a new method for testing compilers—yields the informational equivalent of exhaustive testing at a fraction of the cost. The method has been used successfully in designing some of the tests in the Ada Compiler Validation Capability (ACVC) test suite. <s> BIB001 </s> A survey of combinatorial testing <s> Definitions of Test Suite for CT <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> BIB002 </s> A survey of combinatorial testing <s> Definitions of Test Suite for CT <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> BIB003 </s> A survey of combinatorial testing <s> Definitions of Test Suite for CT <s> Abstract : Testing is an expensive but essential part of any software project. Having the right methods to detect faults is a primary factor for success in the software industry. Component based systems are problematic because they are prone to unexpected interaction faults, yet these may be left undetected by traditional testing techniques. In all but the smallest of systems, it is not possible to test every component interaction. One can use a reduced test suite that guarantees to include a defined subset of interactions instead. A well studied combinatorial object, the covering array, can be used to achieve this goal. Constructing covering arrays for a specific software system is not always simple and the resulting object may not closely mirror the real test environment. Not only are new methods for building covering arrays needed, but new tools to support these are required as well. Our aim is to develop methods for building smaller test suites that provide stronger interaction coverage, while retaining the flexibility required in a practical test suite. We combine ideas from combinatorial design theory, computational search, statistical design of experiments and software engineering. We begin with a description of a framework for greedy algorithms that has formed the basis for several published methods and a widely used commercial tool. We compare this with a meta-heuristic search algorithm, simulated annealing. The results suggest that simulated annealing is more effective at finding smaller test suites, and in some cases improves on combinatorial methods as well. We then develop a mathematical model for variable strength interaction testing. This allows us to balance the cost and the time of testing by targeting individual subsets of components. We present construction techniques using meta-heuristic search and provide the first known bounds for objects of this type. We end by presenting some new cut-and-paste techniques that merge recursive combinatorial constructions <s> BIB004 </s> A survey of combinatorial testing <s> Definitions of Test Suite for CT <s> Abstract The quality of software has been a main concern since the inception of computer software. To be able to produce high quality software, software developers and software testers alike need continuous improvements in their developing and testing methodologies. These improvements should result in better coverage of the input domain, efficient test cases, and in spending fewer testing resources. In this paper we focus on an approach for generating efficient test cases based on the special properties of Design of Experiments and developing a logistic regression model of predicting test case outcomes. Design of Experiments will be utilized to efficiently minimize the number of test cases and the logistic regression model will be used to predict software failures. This approach, in turn, would provide the software tester with a model that reduces the number of test cases, predicts test case outcomes, reduces cost, and allows better forecast of release readiness. We demonstrate our approach using two case studies (TI Interactive software and Microsoft's Pocket PC operating system). <s> BIB005 </s> A survey of combinatorial testing <s> Definitions of Test Suite for CT <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> BIB006
Next we give the definitions of orthogonal array, covering array, and variable strength covering array, and also present the evolution of test suites for CT at the same time. Definition 2.2.1 (Orthogonal Array). For SUT, a strength τ Orthogonal Array(OA) (or a Mixed strength τ Orthogonal Array (MOA)), denoted as OA (N; τ, n, (a 1 , a 2 , . . . , a n )) is an N × n array with the following properties. (1) Each column i(1 ≤ i ≤ n) contains only elements from the set V i with a i = |V i |. The Orthogonal Array Number, OAN(N; τ, n, (a 1 , a 2 , . . . , a n )), is the minimum N required to satisfy the parameter τ, n, (a 1 , a 2 , . . . , a n ). When a 1 = a 2 = · · · = a n = v, the orthogonal array is written as OA (N; τ, n, v) , and its orthogonal array number as OAN (N; τ, n, v)  ]. The orthogonal array requires each combination to be covered the same number of times BIB001 BIB002 . The most widely used orthogonal array is the one with strength τ = 2. The earliest proposed CT method was OATS (Orthogonal Array Testing System) which used an orthogonal array of strength 2 as the test suite. In general, the orthogonal array was difficult to generate and its test suite was often quite large. But OA has its advantages, such as making it relatively easy to identify the particular combination that caused a failure. Soon τ -way testing became more popular, which uses a τ − way covering array as the test suite. We next define the τ − way covering array. it is called a τ − way covering array (or a Mixed strength τ Covering Array (MCA)), denoted as CA (N; τ, n, (a 1 , a 2 , . . . , a n )). The covering array number, CAN (N; τ, n, (a 1 , a 2 , . . . , a n )), is the minimum N required to satisfy the parameter τ , n, and (a 1 , a 2 , . . . , a n ). When a 1 = a 2 = . . . = a n = v, the covering array is written as CA (N; τ, n, v) , and its covering array number as CAN (N; τ, n, v) BIB003 . Testing with a test suite of τ −way covering array is called τ −way testing. τ -way testing is a kind of CT which requires that every combination of any τ parameter values in the software must be tested at least once. When τ = 1, it is called the Each Choice (EC) combination strategy. It becomes Pairwise Testing (PW) when τ = 2. When τ = n, it is called the All Combination (AC) strategy. From Definitions 2.2.1 and 2.2.2, we can see that an orthogonal array with strength τ is a τ -way covering array, but the reverse is not necessarily true. Figure 3 can also be viewed as a 2-way covering array for the NGS, and Figure 2 can be viewed as an 1-way covering array for the NGS. A more practical and in some cases more flexible approach to examining interaction coverage than τ -way testing is the variable strength interaction testing BIB004 . Its test suite is called a variable strength covering array. This method uses a covering array that offers different covering strengths to different parameter groups and aims to cover only combinations of parameters having mutual interactions. This is important because interactions do not often exist uniformly between parameters. Some parameters will have strong interactions with each other while others may have few or no interactions. For this reason, we may from time to time wish to focus testing on a specific set of parameters and apply a higher strength testing on them without ignoring the rest. In this case, the variable strength covering testing may be more effective and efficient. Definition 2.2.3 (Variable Strength Covering Array). Let R denote the set of the interaction relation set. R is the covering requirements for the SUT. Let C A be an m × n matrix, with the elements of column i of C Afrom V i , which is the value set of parameter c i . If C A covers all the combinations required by R, we call C A a covering array for the SUT. Every row of C A is a test case. When R has elements of different sizes, that is, τ is fixed} and |R| = C τ n , the covering array C A for the SUT is a τ -way covering array as defined earlier. Testing with a variable strength covering array is called variable strength interaction testing. τ -way testing can be viewed as a special case of variable strength interaction testing, and both of them as special cases of CT. Actually CT can be expanded to include other important factors, such as constraints, and assigned test suite (seeds). CT can be viewed as a kind of Design Of Experiment (DOE), which is a structured method that is used to determine the relationship between the different factors affecting a process and the output of that process BIB005 . The relationships between various forms of CT are illustrated in Figure 4 . For prioritized combinatorial testing, BIB006 ] defines a new type of covering array, called -biased covering array. An -biased covering array is a covering array CA (N; 2, k, v) in which the first rows form tests whose total benefit is as large as possible. That is, no CA (N ; 2, k, v) has rows that provide a larger total benefit. For instance, certain factors or levels for an input may have an associated benefit or priority that indicates a higher preference that the interaction be covered earlier in testing.