A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <s> This paper describes how both the quality and efficiency of protocol testing were improved by using a new Bellcore tool called the Automatic Efficient Test Generator (AETG). The AETG tool is based on ideas from experimental design and it creates a test set that contains all possible pairs of involved factors. Two examples are given to illustrate this technique and compare it with traditional approaches. The improved quality of testing leads to a faster detection of nonconformances and a higher quality of products in a shorter development interval. Although the application discussed in this paper covers protocol conformance testing, the techniques for improving the quality of testing can be applied to other types of testing such as feature testing and testing between two different network elements. > <s> BIB001 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <s> The combinatorial design method substantially reduces testing costs. The authors describe an application in which the method reduced test plan development from one month to less than a week. In several experiments, the method demonstrated good code coverage and fault detection ability. <s> BIB002 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <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> BIB003 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <s> Testing is a critical component of modern software development. The problem of designing a suite of test cases is superficially similar to that of designing an experiment to estimate main effects and interactions, but there are crucial differences. Additive models are unhelpful, and classical design criteria are also. We propose a new class of models and new measures of effectiveness. We compare several designs. <s> BIB004 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <s> The paradigm of model based testing shifts the focus of testing from writing individual test cases to developing a model from which a test suite can be generated automatically. We report on our experience with model based testing of a highly programmable system that implements intelligent telephony services in the US telephone network. Our approach used automatic test case generation technology to develop sets of self checking test cases based on a machine readable specification of the messages in the protocol under test. The AETG/sup TM/ software system selected a minimal number of test data tuples that covered pairwise combinations of tuple elements. We found the combinatorial approach of covering pairwise interactions between input fields to be highly effective. Our tests revealed failures that would have been difficult to detect using traditional test designs. However, transferring this technology to the testing organization was difficult. Automatic generation of cases represents a significant departure from conventional testing practice due to the large number of tests and the amount of software development involved. <s> BIB005 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <s> AETG/sup SM/ Web is a Web based service developed by Bellcore researchers for enabling model based testing. In model based testing, the functional test requirements of the system are first modeled and then test cases based on this model are created or generated. AETG/sup SM/ Web employs a Web based user interface to model the functional requirements of the system under test, and automatically generates test cases for the system using the AETG/sup SM/ test case generation technology. A brief review of modeling using AETG/sup SM/ Web and the AETG/sup SM/ test generation paradigm is explained. <s> BIB006 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <s> Model-based testing is a new and evolving technique for generating a suite of test cases from requirements. Testers using this approach concentrate on a data model and generation infrastructure instead of hand-crafting individual tests. Several relatively small studies have demonstrated how combinatorial test generation techniques allow testers to achieve broad coverage of the input domain with a small number of tests. We have conducted several relatively large projects in which we applied these techniques to systems with millions of lines of code. Given the complexity of testing, the model-based testing approach was used in conjunction with test automation harnesses. Since no large empirical study has been conducted to measure efficacy of this new approach, we report on our experience with developing tools and methods in support of model-based testing. The four case studies presented here offer details and results of applying combinatorial test-generation techniques on a large scale to diverse applications. Based on the four projects, we offer our insights into what works in practice and our thoughts about obstacles to transferring this technology into testing organizations. <s> BIB007 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <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> BIB008 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <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> BIB009 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <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> BIB010 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <s> The combinatorial approach to software testing uses models to generate a minimal number of test inputs so that selected combinations of input values are covered. The most common coverage criteria is two-way, or pairwise coverage of value combinations, though for higher confidence three-way or higher coverage may be required. This paper presents example system requirements and corresponding models for applying the combinatorial approach to those requirements. These examples are intended to serve as a tutorial for applying the combinatorial approach to software testing. Although this paper focuses on pairwise coverage, the discussion is equally valid when higher coverage criteria such as three-way (triples) are used. We use terminology and modeling notation from the AETG1 system to provide concrete examples. <s> BIB011 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <s> Many modern software systems are designed to be highly configurable so they can run on and be optimized for a wide variety of platforms and usage scenarios. Testing such systems is difficult because, in effect, you are testing a multitude of systems, not just one. Moreover, bugs can and do appear in some configurations, but not in others. Our research focuses on a subset of these bugs that are "option-related"-those that manifest with high probability only when specific configuration options take on specific settings. Our goal is not only to detect these bugs, but also to automatically characterize the configuration subspaces (i.e., the options and their settings) in which they manifest. To improve efficiency, our process tests only a sample of the configuration space, which we obtain from mathematical objects called covering arrays. This paper compares two different kinds of covering arrays for this purpose and assesses the effect of sampling strategy on fault characterization accuracy. Our results strongly suggest that sampling via covering arrays allows us to characterize option-related failures nearly as well as if we had tested exhaustively, but at a much lower cost. We also provide guidelines for using our approach in practice. <s> BIB012 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <s> Regression testing is an expensive part of the software maintenance process. Effective regression testing techniques select and order (or prioritize) test cases between successive releases of a program. However, selection and prioritization are dependent on the quality of the initial test suite. An effective and cost efficient test generation technique is combinatorial interaction testing, CIT, which systematically samples all t-way combinations of input parameters. Research on CIT, to date, has focused on single version software systems. There has been little work that empirically assesses the use of CIT test generation as the basis for selection or prioritization. In this paper we examine the effectiveness of CIT across multiple versions of two software subjects. Our results show that CIT performs well in finding seeded faults when compared with an exhaustive test set. We examine several CIT prioritization techniques and compare them with a re-generation/prioritization technique. We find that prioritized and re-generated/prioritized CIT test suites may find faults earlier than unordered CIT test suites, although the re-generated/prioritized test suites sometimes exhibit decreased fault detection. <s> BIB013 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <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> BIB014 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <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> BIB015 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <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> BIB016 </s> A survey of combinatorial testing <s> A.2. Cohen D. M., Dalal et al. and AETG from Bellcore <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> BIB017
The group from Bellcore has worked in modeling, test generation, and the application of CT. They presented the first use of test generation system called AETG to generate a test suite of CT for various application scenarios in 1990's  BIB002 BIB003  ] and concluded that AETG was an effective and efficient way to create test case BIB001 . Cohen et al. showed that the number of tests required to cover n-way parameter combinations grows logarithmically with the number of parameters, and showed that AETG was able to reduce the number of test cases compared to OA. They used AETG to generate both a high-level test plan and detailed test cases by incorporating some constraints and seeds. Other studies also found that the AETG pairwise test sets gave good coverage in a variety of settings  ]. Dalal et al. later presented the method of factor covering design for testing, and offered some testing guidelines based on their experience. They also proposed some models and some measures of effectiveness BIB004 ], and reported four case studies in which their model-based test architecture has been used. The main lessons learned were that the model of the test data was fundamentally important, and considerable domain expertise and iteration were often required to find a suitable model BIB005 BIB007 . After providing a publicly available Web interface to AETG BIB006 , to serve as a tutorial for CT, they recently presented example system requirements and the corresponding methods for applying the combinatorial approach to those requirements BIB011 . Cohen et al. worked on many areas of CT, including test generation, application, test prioritization, failure diagnosis, constraints, and evaluation. They first examined the need of variable strength covering array and proposed this new subject of research, then they presented some computational methods, such as simulated annealing, to find variable strength array BIB008 . They also explored a method for building covering array of strength three that combined 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 BIB009 BIB010 . They later tried to quantify the effects of different configurations on a test suite's operation and effectiveness . They used covering array to detect option-related defects and gave fault characterization in complex configuration spaces using the classification tree analysis BIB012 . They also examined the effectiveness of CT on regression testing in evolving programs with multiple versions as well as studied several prioritization techniques BIB013 , presented a general constraint representation and a technique based on the existing constraint handling techniques BIB014 BIB015 BIB017 . Recently they presented an incremental and adaptive approach to building covering array schedules BIB016 .