A survey of combinatorial testing <s> Combination Strategies and Tools for Test Suite Generation <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> Combination Strategies and Tools for Test Suite Generation <s> Combination strategies are test-case selection methods where test cases are identifled by combining values of the difierent test object input parameters based on some combinatorial strategy. This survey presents 15 difierent combination strategies, and covers more than 30 papers that focus on one or several combination strategies. We believe this collection represents most of the existing work performed on combination strategies. This survey describes the basic algorithms used by the combination strategies. Some properties of combination strategies, including coverage criteria and theoretical bounds on the size of test suites, are also included in this description. This survey paper also includes a subsumption hierarchy that attempts to relate the various coverage criteria associated with the identifled combination strategies. Finally, this survey contains short summaries of all the papers that cover combination strategies. <s> BIB002 </s> A survey of combinatorial testing <s> Combination Strategies and Tools for Test Suite Generation <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> BIB003 </s> A survey of combinatorial testing <s> Combination Strategies and Tools for Test Suite Generation <s> This study compares seven different methods for handling constraints in input parameter models when using combination strategies to select test cases. Combination strategies are used to select test ... <s> BIB004 </s> A survey of combinatorial testing <s> Combination Strategies and Tools for Test Suite Generation <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> BIB005 </s> A survey of combinatorial testing <s> Combination Strategies and Tools for Test Suite Generation <s> Combinatorial interaction testing (CIT) is a method to sample configurations of a software system systematically for testing. Many algorithms have been developed that create CIT samples, however few have considered the practical concerns that arise when adding constraints between combinations of options. In this paper, we survey constraint handling techniques in existing algorithms and discuss the challenges that they present. We examine two highly-configurable software systems to quantify the nature of constraints in real systems. We then present a general constraint representation and solving technique that can be integrated with existing CIT algorithms and compare two constraint-enhanced algorithm implementations with existing CIT tools to demonstrate feasibility. <s> BIB006 </s> A survey of combinatorial testing <s> Combination Strategies and Tools for Test Suite Generation <s> Researchers have explored the application of combinatorial interaction testing (CIT) methods to construct samples to drive systematic testing of software system configurations. Applying CIT to highly-configurable software systems is complicated by the fact that, in many such systems, there are constraints between specific configuration parameters that render certain combinations invalid. In recent work, automated constraint solving methods have been combined with search-based CIT methods to address this problem with promising results. In this paper, we observe that the pattern of computation in greedy CIT algorithms leads to sequences of constraint solving problems that are closely related to one another. We propose two techniques for exploiting the history of constraint solving: (1) using incremental algorithms that are present within available constraint solvers and (2) mining constraint solver data structures to extract information that can be used to reduce the CIT search space. We evaluate the cost-effectiveness of these reductions on four real-world highly-configurable software systems and on a population of synthetic examples that share the characteristics of those four systems. In combination our techniques reduce the cost of CIT in the presence of constraints to that of traditional unconstrained CIT methods without sacrificing the quality of solutions. <s> BIB007 </s> A survey of combinatorial testing <s> Combination Strategies and Tools for Test Suite Generation <s> Researchers have explored the application of combinatorial interaction testing (CIT) methods to construct samples to drive systematic testing of software system configurations. Applying CIT to highly-configurable software systems is complicated by the fact that, in many such systems, there are constraints between specific configuration parameters that render certain combinations invalid. Many CIT algorithms lack a mechanism to avoid these. In recent work, automated constraint solving methods have been combined with search-based CIT construction methods to address the constraint problem with promising results. However, these techniques can incur a non-trivial overhead. In this paper, we build upon our previous work to develop a family of greedy CIT sample generation algorithms that exploit calculations made by modern Boolean satisfiability (SAT) solvers to prune the search space of the CIT problem. We perform a comparative evaluation of the cost-effectiveness of these algorithms on four real-world highly-configurable software systems and on a population of synthetic examples that share the characteristics of those systems. In combination our techniques reduce the cost of CIT in the presence of constraints to 30 percent of the cost of widely-used unconstrained CIT methods without sacrificing the quality of the solutions. <s> BIB008
A combination strategy selects test cases by combining values of the different test object parameters based on some combinatorial strategy BIB002 . It involves four elements: (1) covering array specifying the specific kind of test suite to be used; (2) seeding to assign some specific test cases in advance; (3) constraints to be considered in the test generation; and (4) method to be used to generate test cases. Next we introduce these aspects. 3.2.1. Covering Array. There are many kinds of covering array we can select for CT. Figure 6 shows that different covering arrays have different sizes and offer different coverage. Based on the observation in testing that a larger test suite typically requires more testing cost and a higher coverage typically increases the chance of detecting failures, these covering arrays have different failure detection abilities and involve different testing costs. In practice, some of them can be combined together; for example, BC can be combined with OA or with PW by taking the union of the respective test suites. Several studies investigated the effectiveness of these covering arrays. For example,  evaluated five combination strategies: AC, EC, BC, OA, and PW. These strategies were evaluated with respect to the number of test cases, the number of faults found, the failure size, and the number of decisions covered. Their results indicated that the Each Choice strategy required the least number of tests and found the smallest number of faults. This research provides some suggestion on selecting an appropriate covering array. 3.2.2. Seeding. Seeding means to assign some specific test cases or some specific schema in testing. BIB001 first used the term seeds to guarantee inclusion of their favorite test cases by specifying them as seed tests or partial seed tests. The seed tests are included in the generated test set without modification. The partial seed tests are seed tests that have some input fields which have unassigned values. The Automatic Efficient Test Generator (AETG) can complete the partial test cases by filling in values for the missing fields. Seeding has two practical applications  ]: (1) It allows explicit specification of important combinations. For example, if a tester is aware of combinations that are likely to be used in the field, he can specify a test suite to contain these combinations. All τ -way combinations in these seeds will be considered covered and only incremental test cases which contain the uncovered τ -wise combinations will be generated and added. (2) It can be used to minimize change in the test suite when the test domain description is modified and a new test suite regenerated. For example, a small modification of the test domain description, like adding parameters or parameter values, might cause big changes in the resulting test suite. Containing these changes can save testing cost. Recently, BIB005 presented a new use of the seeding mechanism: increment adaptive covering array, by building a series of covering arrays incrementally and adaptively. Their approach begins with a seed of a low strength covering array, and continually increases this as resources allow, and based on the revealed faults and results of failure diagnosis. At each stage, the test cases from the previous stage are reused as seeds. This allows failures owing to only one or two configuration settings to be found and fixed as early as possible, and also reduces duplication of testing when multiple covering arrays must be used. For example, we can first test SUT with EC, then generate a PW test suite using the test suite from EC as seeds, and if it is necessary, we can repeat the test generation using this PW test suite as seeds to form a new higher strength covering array. Many test generation tools of CT also support a seeding mechanism, such as AETG BIB001 , PICT  ], and SST developed by us  . These tools can first accept a predefined test suite, then generate additional test cases to achieve the required coverage while minimizing redundant coverage of interactions. 3.2.3. Constraints. Constraints occur naturally in most systems. The typical situation is that some combinations of parameter values are invalid. Existence of constraints increase the difficulty in applying CT: (1) Most existing test generation methods cannot deal with constraints, and ignore them. Ignoring constraints may lead to the generation of test configurations that are invalid. This can lead to ineffective test planning and wasted testing effort. (2) It is difficult to design a general algorithm for test generation with due consideration of constraints. (3) Even a small number of constraints may give rise to an enormous number of invalid configurations. When the generated test suite contains many invalid test cases, this will cause a loss of combination coverage. (4) Complicated constraints may exist in SUT, and multiple constraints can interact to produce additional implicit constraints. It is both time consuming and highly error prone to deal with constraints manually in test suite generation. Thus, proper handling of constraints is a key issue we must address in test suite generation. Since Bryce and Colbourn first addressed "soft constraints" by weighting factors and levels  , there has been some work done by Hnich et al. to address "hard constraints," although they only provided examples of small inputs and did not demonstrate that their method would scale BIB003 . Although handling constraints is still an open problem, there have been several good attempts in dealing with constraints. For example, BIB006 BIB007 BIB008 studied the magnitude and subtlety of constraints found in configurable systems and presented techniques for handling them. They described the variety and type of constraints that can arise in highly configurable systems and reported on the constraints found in two nontrivial software systems. They presented a technique for compiling constraints into a boolean satisfiability (SAT) problem and integrating constraint checking with both greedy and simulated annealing algorithms for interaction test generation. BIB004 investigated four different constraint handling methods: the abstract parameter method and the submodels method that can result in conflict-free parameter models, the avoid method which ensures that only conflict-free test cases are selected during the test case selection process, and the replace method which removes conflicts from already selected test cases. They also provided a good guideline on when to use these four constraint handling methods.