A survey of combinatorial testing <s> Model of SUT <s> Distributed systems consist of a number of network elements that interact with each other. As the number of network elements and interchangeable components for each network element increases, the trade-off that the system tester faces is the thoroughness of test configuration coverage vs. limited resources of time and expense that are available. An approach to resolving this trade-off is to determine a set of test configurations that test each pair-wise combination of network components. This goal gives a well-defined level of test coverage, with a reduced number of system configurations. To select such a set of test configurations, we show how to apply the method of orthogonal Latin squares, from the design of balanced statistical experiments. Since the theoretical treatment assumes constraints that may not be satisfied in practice, we then show how to adapt this approach to realistic application constraints. <s> BIB001 </s> A survey of combinatorial testing <s> Model of SUT <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> BIB002 </s> A survey of combinatorial testing <s> Model of SUT <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> BIB003 </s> A survey of combinatorial testing <s> Model of SUT <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> BIB004 </s> A survey of combinatorial testing <s> Model of SUT <s> Systems constructed from components, including distributed systems, consist of a number of elements that interact with each other. As the number of network elements or interchangeable components for each network element increases, the trade off that the system tester faces is the thoroughness of test configuration coverage, versus availability of limited resources (time and budget). An approach to resolving this trade off is to determine a minimal set of test configurations that test each pair-wise combination of components. This goal gives a well-defined, cost-effective level of test coverage, with a reduced number of system configurations. To select such a set of test configurations, we show how to apply the method of covering arrays, and improve on previous results. <s> BIB005 </s> A survey of combinatorial testing <s> Model of SUT <s> Test reduction is an important issue in black-box testing. The number of possible black-box tests for any non-trivial software application is extremely large. For the class of programs with multiple inputs and outputs, the number of possible tests grows very rapidly as combinations of input test data are considered. In this paper, we introduce an approach to test reduction that uses automated input-output analysis to identify relationships between program inputs and outputs. Our initial experience with the approach has shown that it can significantly reduce the number of black-box tests. <s> BIB006 </s> A survey of combinatorial testing <s> Model of SUT <s> For ensuring the displaying effects of Web applications, it is important to perform compatibility testing for browsers under the different configurations and it is a hard task to test all. So this paper focused on the improvements for browser compatibility testing. Firstly, we introduced the related work. Then we analysed the functional speciality of the current popular browsers, and provided the preconditions to simplify problems. Next we gave an instance and brought forward the single factor covering method and the pair-wise covering design to gain testing suits. Finally, we introduced the assistant tools we have developed and the future work. <s> BIB007 </s> A survey of combinatorial testing <s> Model of SUT <s> In this paper, we consider a problem that arises in black box testing: generating small test suites (i.e., sets of test cases) where the combinations that have to be covered are specified by input-output parameter relationships of a software system. That is, we only consider combinations of input parameters that affect an output parameter. We also do not assume that the input parameters have the same number of values. To solve this problem, we revisit the greedy algorithm for test generation and show that the size of the test suite it generates is within a logarithmic factor of the optimal. Unfortunately, the algorithm's main weaknesses are its time and space requirements for construction. To address this issue, we present a problem reduction technique that makes the greedy algorithm or any other test suite generation method more efficient if the reduction in size is significant. <s> BIB008 </s> A survey of combinatorial testing <s> Model of SUT <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> BIB009 </s> A survey of combinatorial testing <s> Model of SUT <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> BIB010 </s> A survey of combinatorial testing <s> Model of SUT <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> Model of SUT <s> Combinatorial testing methods address generation of test cases for problems involving multiple parameters and combinations. The Orthogonal Array Based Testing Strategy (OATS) is one such combinatorial testing method, a systematic, statistical way of testing pair-wise interactions. It provides representative (uniformly distributed) coverage of all variable pair combinations. This makes the technique particularly useful for testing of software, wherever there is combinatorial explosion: a. In system testing for handling feature interactions b. In integration testing components c. It is also quite useful for testing products with a large number of configuration possibilities. One of the fundamental assumptions behind OATS approach is that a subset covering all pair-wise combinations will be more effective than a randomly selected subset. OATS provides a means to select a minimal test set that guarantees testing the pair-wise combinations of all the selected variables. Covering pair-wise combinations has been reported to be very effective in the literature. Successful use of this technique, with 50% effort saving and improved testing with a factor of 2.6 is reported in the literature. In this paper, we report on the in-house web-based application that we designed and implemented to support customized version of OATS and our experience in piloting and getting this method used in projects. In the in-house tool we have introduced a number of additional features, that help in generation and post processing of test-cases. We have also designed a supporting process for using this method, and we discuss the steps in this process in the paper. We share details on application in feature testing of a mobile phone application. This method has also been successfully used in designing feature interaction test cases and for augmenting the regression suite to increase coverage. <s> BIB012 </s> A survey of combinatorial testing <s> Model of SUT <s> Combination strategies are test methods that generate test cases based on input parameter models. This paper suggests a structured modeling method used to translate requirements expressed in a general format into an input parameter model suitable for combination strategies. ::: ::: This paper also describes results from two initial experiments exploring the efficiency and effectiveness of the modeling method. These results indicate that the resulting models may contain enough information to detect the vast majority of faults in the system under test. Further, results indicate that the modeling method is simple enough to use in practical testing. <s> BIB013
Modeling of SUT is a very fundamental and important activity for CT, since the effectiveness and efficiency of CT depend on the model used. It is the starting point of CT. Different testers may come up with different models of SUT based on their own skill and experience. A key issue in modeling is to build a precise model at the "right" level of abstraction. We first give the definition of model of SUT, then review some approaches for modeling a SUT. Definition 3.1.1 (SUT Model). For CT, a model of SUT includes four elements: parameters that may affect the SUT; values that should be selected for each parameter; interaction relations that exist between parameters, and constraints that exist between values of the different parameters, which can be used to exclude combinations that are not meaningful from the domain semantics. A model for the SUT can be denoted as a 4-tuple: Model SU T (P, V, R, C). By Definition 3.1.1, four key issues need to be resolved in modeling of SUT: (1) how to identify parameters that may affect the SUT; (2) Only when these issues are settled can CT be effectively brought into play. The first issue is to identify parameters for CT. Parameters in the SUT may represent configuration parameters, like those of the NGS in Figure 2 , and similar cases found in BIB002 , BIB005 , and BIB007 . They may also represent user input parameters BIB006 ], features of the SUT BIB009 ], interfaces or GUI BIB001  ], and components or objectives  . By reviewing various system documents and conducting some case studies BIB010 , we can select an initial set of parameters for the SUT and then refine this set by adding or deleting parameters during the modeling procedure. The second issue is to determine the applicable values for each parameter. This step is critical to the modeling of SUT, since the behavior of the SUT is governed by the specific combination of parameter values. Note that some parameters may have many values. For example, the parameter "Audio" in the NGS, a configure parameter, can have many possible values, as there are hundreds of audio products in the market. When the parameter is an input of continuous values, it can have an infinite number of values. In this case, we must select some typical values. Equivalence partitioning, boundary value analysis, and primary element selection are the usual methods to be used here. Through selection of typical representative values from the equivalent class, completing with some boundary values, and assigning some important or relevant values for each parameter, we can keep the size of each V i (1 ≤ i ≤ n) in the SUT small (with just a few representative values). The third issue is to identify the actual interactions between parameters. We can study the system documents to identify: (1) parameters which will not interact with any other parameters; (2) parameters which may have strong interactions with each other; and (3) interactions which exist between a small number of parameters. The fourth issue is to identify the constraints that exist between certain parameters. A common case occurs when some specific values of one parameter conflict with some values of another parameter. For example, the Browser parameter of the NGS cannot take on "Firefox" value when the Access parameter has 'ISDL" value. This represents a kind of mutual exclusion constraint between parameters. The opposite case may also occur when some specific value of one parameter must be combined with some value of another parameters. For example, the Browser parameter of the NGS must take on "IE" value when the Access parameter has "ISDL" value or when the Audio parameter has "Maya" value. To obtain the information on the interactions and constraints between parameters, we can study the requirement document, design document, codes, and other related documents. We can also interview designers and programmers to extract the relevant information. Static analysis, such as program slicing, can also be used to identify the interactions between parameters BIB006 Korel 2000a, 2000b; BIB006 BIB008 . With the information of interaction and constraints between parameters, we can make CT more pertinent and effective. The output of modeling of SUT is (P, V, R, C): where each V i is the value set for parameter c i (i = 1, 2, . . . , n); a set R of the interaction relations between parameters, and a set C of constraints which specifies the requirements on what should or should not be covered. Modeling of SUT provides the foundation for the following steps of CT. There have been many studies on modeling of SUT which helped to advance this field. For example, BIB003 BIB004 learned that iteration and expert knowledge is required to build a proper model. BIB011 gave the samples of modeling system which can serve as a tutorial for applying CT. There have been some good guidelines for modeling of SUT. Many applicable scenarios have been given in  , and the procedure for determining the parameters and their values, and generating test suite is given in BIB012 . BIB013 presented a basic eightstep process for input parameter modeling and gave some initial experience of using this process.  gave some practical ways of modeling that make the pure pairwise testing approach more applicable. Despite these prior works, there are still several open questions left in this area: (1) how to effectively and efficiently model SUT for CT? (2) how to validate the model? (3) how to evaluate the effectiveness of the different approaches of modeling?