A survey of combinatorial testing <s> Test Case Generation Technique. <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> BIB001 </s> A survey of combinatorial testing <s> Test Case Generation Technique. <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> Test Case Generation Technique. <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> BIB003
Test case generation is the most active area of CT research. In our survey, we have identified 50 related papers on test generation. We also included a few studies on covering array published in mathematical journals. As the problem of covering array generation is NP-hard, researchers have tried various methods to solve it. To date, four main groups of methods have been proposed: greedy algorithm, heuristic search algorithm, mathematic method, and random method. The first two groups are computational approaches. Greedy algorithms have been the most widely used method for test suite generation for CT. They construct a set of tests such that each test covers as many uncovered combinations as possible. There are two classes of greedy algorithms. The first class is the one-row-at-a-time variation based on the automatic test case generator AETG BIB001 . presented a generic framework for this class of algorithms. A single row of the array is constructed at each step until all τ -sets have been covered. Algorithms that fit into this class include: the heuristic algorithm used to generate pairwise test suite of the CATS tool  ], the density-based greedy algorithm for generating a 2-way and higher strength covering array BIB003 Colbourn 2007a, 2008] , and the greedy algorithm with different heuristics used in PICT  ]. BIB002 also gave a greedy algorithm for a parametric test case generation tool that applies a combinatorial design approach to the selection of candidate test cases. A typical greedy algorithm works as follows.