A survey of combinatorial testing
---
paper_title: A practical system for mutation testing: help for the common programmer

paper_content:

Mutation testing is a technique for unit testing software that, although powerful, is computationally expensive. Recent engineering advances have given us techniques and algorithms for significantly reducing the cost of mutation testing. These techniques include a new algorithmic execution technique called schema-based mutation, an approximation technique called weak mutation, a reduction technique called selective mutation, and algorithms for automatic test data generation. This paper outlines a design for a system that will approximate mutation, but in a way that will be accessible to everyday programmers. We envisage a system to which a programmer can submit a program unit, and get back a set of input/output pairs that are guaranteed to form an effective test of the unit by being close to mutation adequate.
---
paper_title: An investigation of the applicability of design of experiments to software testing

paper_content:

Approaches to software testing based on methods from the field of design of experiments have been advocated as a means of providing high coverage at relatively low cost. Tools to generate all pairs, or higher n-degree combinations, of input values have been developed and demonstrated in a few applications, but little empirical evidence is available to aid developers in evaluating the effectiveness of these tools for particular problems. We investigate error reports from two large open-source software projects, a browser and Web server, to provide preliminary answers to three questions: Is there a point of diminishing returns at which generating all n-degree combinations is nearly as effective as all n+1-degree combinations? What is the appropriate value of n for particular classes of software? Does this value differ for different types of software, and by how much? Our findings suggest that more than 95% of errors in the software studied would be detected by test cases that cover all 4-way combinations of values, and that the browser and server software were similar in the percentage of errors detectable by combinations of degree 2 through 6.
---
paper_title: An Effective Iterative Metamorphic Testing Algorithm Based on Program Path Analysis

paper_content:

Metamorphic testing (MT) is very practical and effective for programs with oracle problems, and many researches have been done in this field. In this article, we present a new iterative MT algorithm, APCEMSI, to avoid the blindness of existing MT methods. The test suites generated by APCEMSI satisfy a criterion which is defined upon program path analysis technique. Experiment result shows that APCEMSI could find errors effectively with much fewer test cases.
---
paper_title: Using spanning sets for coverage testing

paper_content:

A test coverage criterion defines a set E/sub r/ of entities of the program flowgraph and requires that every entity in this set is covered under some test Case. Coverage criteria are also used to measure the adequacy of the executed test cases. In this paper, we introduce the notion of spanning sets of entities for coverage testing. A spanning set is a minimum subset of E/sub r/, such that a test suite covering the entities in this subset is guaranteed to cover every entity in E/sub r/. When the coverage of an entity always guarantees the coverage of another entity, the former is said to subsume the latter. Based on the subsumption relation between entities, we provide a generic algorithm to find spanning sets for control flow and data flow-based test coverage criteria. We suggest several useful applications of spanning sets: They help reduce and estimate the number of test cases needed to satisfy coverage criteria. We also empirically investigate how the use of spanning sets affects the fault detection effectiveness.
---
paper_title: Software fault interactions and implications for software testing

paper_content:

Exhaustive testing of computer software is intractable, but empirical studies of software failures suggest that testing can in some cases be effectively exhaustive. We show that software failures in a variety of domains were caused by combinations of relatively few conditions. These results have important implications for testing. If all faults in a system can be triggered by a combination of n or fewer parameters, then testing all n-tuples of parameters is effectively equivalent to exhaustive testing, if software behavior is not dependent on complex event sequences and variables have a small set of discrete values.
---
paper_title: Prediction of software failures through logistic regression

paper_content:

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).
---
paper_title: Generating combinatorial test suite for interaction relationship

paper_content:

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.
---
paper_title: Designing test suites for software interaction testing

paper_content:

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
---
paper_title: Prediction of software failures through logistic regression

paper_content:

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).
---
paper_title: A variable strength interaction testing of components

paper_content:

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.
---
paper_title: Robust testing of AT&T PMX/StarMAIL using OATS

paper_content:

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.
---
paper_title: Orthogonal Latin squares: an application of experiment design to compiler testing

paper_content:

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.
---
paper_title: Input parameter modeling for combination strategies

paper_content:

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.
---
paper_title: A Browser Compatibility Testing Method Based on Combinatorial Testing

paper_content:

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.
---
paper_title: Combinatorial testing: learnings from our experience

paper_content:

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.
---
paper_title: Model-based testing of a highly programmable system

paper_content:

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.
---
paper_title: Generating small combinatorial test suites to cover input-output relationships

paper_content:

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.
---
paper_title: Model-based testing in practice

paper_content:

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.
---
paper_title: Designing test suites for software interaction testing

paper_content:

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
---
paper_title: The AETG system: An approach to testing based on combinatorial design

paper_content:

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.
---
paper_title: A practical strategy for testing pair-wise coverage of network interfaces

paper_content:

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.
---
paper_title: 4 DETERMINATION OF TEST CONFIGURATIONS FOR PAIR-WISE INTERACTION COVERAGE

paper_content:

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.
---
paper_title: Combination testing strategies: A survey

paper_content:

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.
---
paper_title: Black-box test reduction using input-output analysis

paper_content:

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.
---
paper_title: Modeling requirements for combinatorial software testing

paper_content:

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.
---
paper_title: Handling Constraints in the Input Space when Using Combination Strategies for Software Testing

paper_content:

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 ...
---
paper_title: Interaction testing of highly-configurable systems in the presence of constraints

paper_content:

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.
---
paper_title: Constructing Interaction Test Suites for Highly-Configurable Systems in the Presence of Constraints: A Greedy Approach

paper_content:

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.
---
paper_title: Constraint Models for the Covering Test Problem

paper_content:

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.
---
paper_title: Exploiting Constraint Solving History to Construct Interaction Test Suites

paper_content:

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.
---
paper_title: Towards incremental adaptive covering arrays

paper_content:

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.
---
paper_title: The AETG system: An approach to testing based on combinatorial design

paper_content:

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.
---
paper_title: Combination testing strategies: A survey

paper_content:

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.
---
paper_title: Automating test case generation for the new generation mission software system

paper_content:

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.
---
paper_title: Test prioritization for pairwise interaction coverage

paper_content:

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.
---
paper_title: The AETG system: An approach to testing based on combinatorial design

paper_content:

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.
---
paper_title: In-parameter-order: a test generation strategy for pairwise testing

paper_content:

Pairwise testing (or 2-way testing) is a specification-based testing criterion, which requires that for each pair of input parameters of a system, every combination of valid values of these two parameters be covered by at least one test case. Empirical results show that pairwise testing is practical and effective for various types of software systems. We show that the problem of generating a minimum test set for pairwise testing is NP-complete. We propose a test generation strategy, called in-parameter-order (or IPO), for pairwise testing. For a system with two or more input parameters, the IPO strategy generates a pairwise test set for the first two parameters, extends the test set to generate a pairwise test set for the first three parameters, and continues to do so for each additional parameter. The IPO strategy allows the use of local optimization techniques for test generation and the reuse of existing tests when a system is extended with new parameters or new values of existing parameters. We present practical, IPO-based test generation algorithms. We describe the implementation of an IPO-based test generation tool and show some empirical results.
---
paper_title: IPOG: A General Strategy for T-Way Software Testing

paper_content:

Most existing work on t-way testing has focused on 2-way (or pairwise) testing, which aims to detect faults caused by interactions between any two parameters. However, faults can also be caused by interactions involving more than two parameters. In this paper, we generalize an existing strategy, called in-parameter-order (IPO), from pairwise testing to t-way testing. A major challenge of our generalization effort is dealing with the combinatorial growth in the number of combinations of parameter values. We describe a t-way testing tool, called FireEye, and discuss design decisions that are made to enable an efficient implementation of the generalized IPO strategy. We also report several experiments that are designed to evaluate the effectiveness of FireEye
---
paper_title: Generating Optimal Test Set for Neighbor Factors Combinatorial Testing

paper_content:

Combinatorial testing is a specification-based testing method, which can detect the faults triggered by interaction of factors. For one kind of software in which the interactions only exist between neighbor factors, this paper proposes the concept of neighbor factors combinatorial testing, presents the covering array generation algorithms for neighbor factors pair-wise (N=2) coverage, neighbor factors N-way (N\geqslant2) coverage and variable strength neighbor factors coverage, and proves that the covering arrays generated by these three algorithms are optimal. Finally we analyze an application scenario, which shows that this approach is very practical.
---
paper_title: IPOG-IPOG-D: efficient test generation for multi-way combinatorial testing

paper_content:

This paper presents two strategies for multi-way testing (i.e. t-way testing with t>2). The first strategy generalizes an existing strategy, called in-parameter-order, from pairwise testing to multi-way testing. This strategy requires all multi-way combinations to be explicitly enumerated. When the number of multi-way combinations is large, however, explicit enumeration can be prohibitive in terms of both the space for storing these combinations and the time needed to enumerate them. To alleviate this problem, the second strategy combines the first strategy with a recursive construction procedure to reduce the number of multi-way combinations that have to be enumerated. Both strategies are deterministic, i.e. they always produce the same test set for the same system configuration. This paper reports a multi-way testing tool called FireEye, and provides an analytic and experimental evaluation of the two strategies. Copyright © 2007 John Wiley & Sons, Ltd.
---
paper_title: Greedy Heuristic Algorithms to Generate Variable Strength Combinatorial Test Suite

paper_content:

Combinatorial testing is a practical software testing approach that has been widely used in practice. Most research and applications of such approach focus on N-way combinatorial testing that provides a minimum coverage of all N-way interactions among factor. However, the strengths of different interactions may not be a fixed integer N, but a variable. Therefore, variable strength combinatorial testing approach is necessary in applications. Existing variable strength combinatorial testing, which allows some interactions have a higher strength than others, has a limitation that such higher-strength interactions must be disjoint. To avoid such a limitation, an improved variable strength combinatorial testing approach, which makes a more sufficient consideration on actual interaction relationship, is proposed in this article. Furthermore, two greedy heuristic algorithms are also proposed to generate combinatorial test suite. Compared to some existing algorithms and tools, the proposed algorithms have advantages on both the execution effectiveness and the optimality of generated test suite. Experimental results can prove such advantages.
---
paper_title: One-test-at-a-time heuristic search for interaction test suites

paper_content:

Algorithms for the construction of software interaction test suites have focussed on the special case of pairwise coverage; less is known about efficiently constructing test suites for higher strength coverage. The combinatorial growth of t-tuples associated with higher strength hinders the efficacy of interaction testing. Test suites are inherently large, so testers may not run entire test suites. To address these problems, we combine a simple greedy algorithmallwith heuristic search to construct and dispense one test at a time. Our algorithm attempts to maximize the number of t-tuples covered by the earliest tests so that if a tester only runs a partial test suite, they test as many t-tuples as possible.allHeuristic search is shown to provide effective methods for achieving such coverage.
---
paper_title: A test generation strategy for pairwise testing

paper_content:

Pairwise testing is a specification-based testing criterion which requires that for each pair of input parameters of a system, every combination of valid values of these two parameters be covered by at least one test case. The authors propose a novel test generation strategy for pairwise testing.
---
paper_title: Augmenting simulated annealing to build interaction test suites

paper_content:

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.
---
paper_title: A variable strength interaction testing of components

paper_content:

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.
---
paper_title: Pair-wise test coverage using genetic algorithms

paper_content:

There has been an emerging trend to develop software using different components. In this way the cost of the software reduces and the developer is able to complete the system efficiently. The components' code may or may not be visible to the developer. Testing, in this case, requires the development of a set of test configurations that can be applied on the software. However, for software that comprises a large number of components, it is infeasible to test each and every test configuration within the limited testing budget and time. In this paper we propose a GA-based technique that identifies a set of test configurations that are expected to maximize pair-wise coverage, with the constraint that the number of test configurations is predefined. Although the paper primarily focuses on the interaction between software components, the idea can be applied to single code component testing. We performed some experiments using our proposed approach. The results were promising.
---
paper_title: Constructing test suites for interaction testing

paper_content:

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.
---
paper_title: Using artificial life techniques to generate test cases for combinatorial testing

paper_content:

Combinatorial testing is a specification-based testing criterion, which requires that for each t-way combination of input parameters of a system, every combination of valid values of these t parameters be covered by at least one test case. This approach is motivated by the observation that in many applications a significant number of faults are caused by interactions of a smaller number of parameters. In this paper, we propose new test generation algorithms for combinatorial testing based on two artificial life techniques: a genetic algorithm (GA) and an ant colony algorithm (ACA). The usefulness of these algorithms is demonstrated through experiments. In the case t = 3 in particular, our algorithms exhibited impressive results
---
paper_title: In-parameter-order: a test generation strategy for pairwise testing

paper_content:

Pairwise testing (or 2-way testing) is a specification-based testing criterion, which requires that for each pair of input parameters of a system, every combination of valid values of these two parameters be covered by at least one test case. Empirical results show that pairwise testing is practical and effective for various types of software systems. We show that the problem of generating a minimum test set for pairwise testing is NP-complete. We propose a test generation strategy, called in-parameter-order (or IPO), for pairwise testing. For a system with two or more input parameters, the IPO strategy generates a pairwise test set for the first two parameters, extends the test set to generate a pairwise test set for the first three parameters, and continues to do so for each additional parameter. The IPO strategy allows the use of local optimization techniques for test generation and the reuse of existing tests when a system is extended with new parameters or new values of existing parameters. We present practical, IPO-based test generation algorithms. We describe the implementation of an IPO-based test generation tool and show some empirical results.
---
paper_title: Covering arrays of higher strength from permutation vectors

paper_content:

A covering arrayCA(N;t,k,v) is an N × k array such that every N × t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t-sets of component interactions. We introduce a combinatorial technique for their construction, focussing on covering arrays of strength 3 and 4. With a computer search, covering arrays with improved parameters have been found. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 202–213, 2006
---
paper_title: Augmenting simulated annealing to build interaction test suites

paper_content:

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.
---
paper_title: Towards incremental adaptive covering arrays

paper_content:

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.
---
paper_title: The AETG system: An approach to testing based on combinatorial design

paper_content:

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.
---
paper_title: 4 DETERMINATION OF TEST CONFIGURATIONS FOR PAIR-WISE INTERACTION COVERAGE

paper_content:

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.
---
paper_title: Robust testing of AT&T PMX/StarMAIL using OATS

paper_content:

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.
---
paper_title: Test suite prioritization by interaction coverage

paper_content:

Event-driven software (EDS) is a widely used class of software that takes sequences of events as input, changes state, and outputs new event sequences. Managing the size of tests suites for EDS is difficult as the number of event combinations and sequences grow exponentially with the number of events. We propose a new testing technique that extends software interaction testing. Traditional software interaction testing systematically examines all t-way interactions of parameters for a program. This paper extends the notion to t-way interactions over sequences of events. The technique applies to many classes of software; we focus on that of EDS. As a proof-of-concept, we prioritize existing test suites for four GUI-based programs by t-way interaction coverage. We compare the rate of fault detection with that of several other prioritization criteria. Results show that prioritization by interaction coverage has the fastest rate of fault detection in half of our experiments, making the most impact when tests have high interaction coverage.
---
paper_title: Prioritizing User-Session-Based Test Cases for Web Applications Testing

paper_content:

Web applications have rapidly become a critical part of business for many organizations. However, increased usage of Web applications has not been reciprocated with corresponding increases in reliability. Unique characteristics, such as quick turnaround time, coupled with growing popularity motivate the need for efficient and effective Web application testing strategies. In this paper, we propose several new test suite prioritization strategies for Web applications and examine whether these strategies can improve the rate of fault detection for three Web applications and their preexisting test suites. We prioritize test suites by test lengths, frequency of appearance of request sequences, and systematic coverage of parameter-values and their interactions. Experimental results show that the proposed prioritization criteria often improve the rate of fault detection of the test suites when compared to random ordering of test cases. In general, the best prioritization metrics either (1) consider frequency of appearance of sequences of requests or (2) systematically cover combinations of parameter-values as early as possible.
---
paper_title: Combinatorial Interaction Regression Testing: A Study of Test Case Generation and Prioritization

paper_content:

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.
---
paper_title: Search Algorithms for Regression Test Case Prioritization

paper_content:

Regression testing is an expensive, but important, process. Unfortunately, there may be insufficient resources to allow for the reexecution of all test cases during regression testing. In this situation, test case prioritization techniques aim to improve the effectiveness of regression testing by ordering the test cases so that the most beneficial are executed first. Previous work on regression test case prioritization has focused on greedy algorithms. However, it is known that these algorithms may produce suboptimal results because they may construct results that denote only local minima within the search space. By contrast, metaheuristic and evolutionary search algorithms aim to avoid such problems. This paper presents results from an empirical study of the application of several greedy, metaheuristic, and evolutionary search algorithms to six programs, ranging from 374 to 11,148 lines of code for three choices of fitness metric. The paper addresses the problems of choice of fitness metric, characterization of landscape modality, and determination of the most suitable search technique to apply. The empirical results replicate previous results concerning greedy algorithms. They shed light on the nature of the regression testing search space, indicating that it is multimodal. The results also show that genetic algorithms perform well, although greedy approaches are surprisingly effective, given the multimodal nature of the landscape
---
paper_title: Covering arrays for efficient fault characterization in complex configuration spaces

paper_content:

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.
---
paper_title: An investigation of the applicability of design of experiments to software testing

paper_content:

Approaches to software testing based on methods from the field of design of experiments have been advocated as a means of providing high coverage at relatively low cost. Tools to generate all pairs, or higher n-degree combinations, of input values have been developed and demonstrated in a few applications, but little empirical evidence is available to aid developers in evaluating the effectiveness of these tools for particular problems. We investigate error reports from two large open-source software projects, a browser and Web server, to provide preliminary answers to three questions: Is there a point of diminishing returns at which generating all n-degree combinations is nearly as effective as all n+1-degree combinations? What is the appropriate value of n for particular classes of software? Does this value differ for different types of software, and by how much? Our findings suggest that more than 95% of errors in the software studied would be detected by test cases that cover all 4-way combinations of values, and that the browser and server software were similar in the percentage of errors detectable by combinations of degree 2 through 6.
---
paper_title: Software fault interactions and implications for software testing

paper_content:

Exhaustive testing of computer software is intractable, but empirical studies of software failures suggest that testing can in some cases be effectively exhaustive. We show that software failures in a variety of domains were caused by combinations of relatively few conditions. These results have important implications for testing. If all faults in a system can be triggered by a combination of n or fewer parameters, then testing all n-tuples of parameters is effectively equivalent to exhaustive testing, if software behavior is not dependent on complex event sequences and variables have a small set of discrete values.
---
paper_title: Locating and Detecting Arrays for Interaction Faults

paper_content:

The identification of interaction faults in component-based systems has focused on indicating the presence of faults, rather than their location and magnitude. While this is a valuable step in screening a system for interaction faults prior to its release, it provides little information to assist in the correction of such faults. Consequently tests to reveal the location of interaction faults are of interest. The problem of nonadaptive location of interaction faults is formalized under the hypothesis that the system contains (at most) some number d of faults, each involving (at most) some number t of interacting factors. Restrictions on the number and size of the putative faults lead to numerous variants of the basic problem. The relationships between this class of problems and interaction testing using covering arrays to indicate the presence of faults, designed experiments to measure and model faults, and combinatorial group testing to locate faults in a more general testing scenario, are all examined. While each has some definite similarities with the fault location problems for component-based systems, each has some striking differences as well. In this paper, we formulate the combinatorial problems for locating and detecting arrays to undertake interaction fault location. Necessary conditions for existence are established, and using a close connection to covering arrays, asymptotic bounds on the size of minimal locating and detecting arrays are established. ::: ::: A final version of this paper appears in J Comb Optim (2008) 15: 17-48.
---
paper_title: A software debugging method based on pairwise testing

paper_content:

Pairwise testing is one of very practical and effective testing methods for various types of software systems. This paper proposes a novel debugging method based on pairwise testing. By analyzing the test cases and retesting with some complementary test cases, the method can narrow the factors that cause the errors in a very small range. So it can provide a very efficient and valuable guidance for the software testing and debugging.
---
paper_title: A measure for component interaction test coverage

paper_content:

A trend in software development is to assemble a system from a number of components. These may be either available commercially off-the-shelf, or by the use of network-based resources. In many cases, the system is expected to function for multiple configurations of interchangeable components. The trade off that a system tester faces is the thoroughness of test component configuration coverage, versus limited resources of time and expense. This paper presents a metric that can be used to measure component interaction coverage of a set of system test configurations. It also provides a formal definition of the system test interaction problem.
---
paper_title: Comparing the fault detection effectiveness of n-way and random test suites

paper_content:

Software testing plays a critical role in the timely delivery of high-quality software systems. Despite the important role that testing plays, little is known about the fault detection effectiveness of many testing techniques. We investigate "n-way" test suites created using a common greedy algorithm for use in combinatorial testing. A controlled study is designed and executed to compare the fault detection effectiveness of n-way and random test suites. Combinatorial testing is conducted on target systems that have been injected with software faults. The results are that there is no significant difference in the fault detection effectiveness of n-way and random test suites for the applications studied. Analysis of the random test suite finds that they are very similar to n-way test suites from the perspective of the number of test data combinations covered. This result concurs with other hypothetical results that indicate little difference between n-way and random test suites. While we do not expect this result to apply in all combinatorial testing situations, we believe the result will lead to the design of better combinatorial test suites.
---
paper_title: Prediction of software failures through logistic regression

paper_content:

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).
---
paper_title: Efficient evaluation of multifactor dependent system performance using fractional factorial design

paper_content:

Performance of computer-based systems may depend on many different factors, internal and external. In order to design a system to have the desired performance or to validate that the system has the required performance, the effect of the influencing factors must be known. Common methods give no or little guidance on how to vary the factors during prototyping or validation. Varying the factors in all possible combinations would be too expensive and too time-consuming. This paper introduces a systematic approach to the prototyping and the validation of a system's performance, by treating the prototyping or validation as an experiment, in which the fractional factorial design methodology is commonly used. To show that this is possible, a case study evaluating the influencing factors of the false and real target rate of a radar system is described. Our findings show that prototyping and validation of system performance become structured and effective when using the fractional factorial design. The methodology enables planning, performance, structured analysis, and gives guidance for appropriate test cases. The methodology yields not only main factors, but also interacting factors. The effort is minimized for finding the results, due to the methodology. The case study shows that after 112 test cases, of 1024 possible, the knowledge gained was enough to draw conclusions on the effects and interactions of 10 factors. This is a reduction with a factor 5-9 compared to alternative methods.
---
paper_title: A Browser Compatibility Testing Method Based on Combinatorial Testing

paper_content:

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.
---
paper_title: Combinatorial testing: learnings from our experience

paper_content:

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.
---
paper_title: Generating test cases for GUI responsibilities using complete interaction sequences

paper_content:

Testing graphical user interfaces (GUI) is a difficult problem due to the fact that the GUI possesses a large number of states to be tested, the input space is extremely large due to different permutations of inputs and events which affect the GUI, and complex GUI dependencies which may exist. There has been little systematic study of this problem yielding a resulting strategy which is effective and scalable. The proposed method concentrates upon user sequences of GUI objects and selections which collaborate, called complete interaction sequences (CIS), that produce a desired response for the user. A systematic method to test these CIS utilizes a finite-state model to generate tests. The required tests can be substantially reduced by identifying components of the CIS that can be tested separately. Since consideration is given to defects totally within each CIS, and the components reduce required testing further, this approach is scalable. An empirical investigation of this method shows that substantial reduction in tests can still detect the defects in the GUI. Future research will prioritize testing related to the CIS testing for maximum benefit if testing time is limited.
---
paper_title: Improved quality of protocol testing through techniques of experimental design

paper_content:

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. >
---
paper_title: Reducing time to market with combinatorial design method testing

paper_content:

Testers face the challenge of doing as much testing as possible within the available, and usually constrained, schedule. In the hypercompetitive commercial marketplace, it is not practical to exhaustively test all combinations of system test cases. This paper discusses the author’s experience with a method that generates a small subset of test cases which provides good coverage of the test domain—the Combinatorial Design Method. It has proven to be flexible for system level testing of small, commercial satellite ground systems. Cost savings of 67% and schedule savings of 68% are shown for an example.
---
paper_title: A practical strategy for testing pair-wise coverage of network interfaces

paper_content:

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.
---
paper_title: The Arrangement of Field Experiments

paper_content:

The present position of the art of field experimentation is one of rather special interest. For more than fifteen years the attention of agriculturalists has been turned to the errors of field experiments. During this period, experiments of the uniformity trial type have demonstrated the magnitude and ubiquity of that class of error which cannot be ascribed to carelessness in measuring the land or weighing the produce, and which is consequently described as due to “soil heterogeneity”; much ingenuity has been expended in devising plans for the proper arrangement of the plots; and not without result, for there can be little doubt that the standard of accuracy has been materially, though very irregularly, raised. What makes the present position interesting is that it is now possible to demonstrate (a) that the actual position of the problem is very much more intricate than was till recently imagined, but that realising this (b) the problem itself becomes much more definite and (c) its solution correspondingly more rigorous.
---
paper_title: Robust testing of AT&T PMX/StarMAIL using OATS

paper_content:

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.
---
paper_title: Orthogonal Latin squares: an application of experiment design to compiler testing

paper_content:

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.
---
paper_title: Robust testing of AT&T PMX/StarMAIL using OATS

paper_content:

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.
---
paper_title: Orthogonal Latin squares: an application of experiment design to compiler testing

paper_content:

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.
---
paper_title: Generating combinatorial test suite for interaction relationship

paper_content:

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.
---
paper_title: Test prioritization for pairwise interaction coverage

paper_content:

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.
---
paper_title: Covering arrays of higher strength from permutation vectors

paper_content:

A covering arrayCA(N;t,k,v) is an N × k array such that every N × t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t-sets of component interactions. We introduce a combinatorial technique for their construction, focussing on covering arrays of strength 3 and 4. With a computer search, covering arrays with improved parameters have been found. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 202–213, 2006
---
paper_title: Combination testing strategies: A survey

paper_content:

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.
---
paper_title: Locating and Detecting Arrays for Interaction Faults

paper_content:

The identification of interaction faults in component-based systems has focused on indicating the presence of faults, rather than their location and magnitude. While this is a valuable step in screening a system for interaction faults prior to its release, it provides little information to assist in the correction of such faults. Consequently tests to reveal the location of interaction faults are of interest. The problem of nonadaptive location of interaction faults is formalized under the hypothesis that the system contains (at most) some number d of faults, each involving (at most) some number t of interacting factors. Restrictions on the number and size of the putative faults lead to numerous variants of the basic problem. The relationships between this class of problems and interaction testing using covering arrays to indicate the presence of faults, designed experiments to measure and model faults, and combinatorial group testing to locate faults in a more general testing scenario, are all examined. While each has some definite similarities with the fault location problems for component-based systems, each has some striking differences as well. In this paper, we formulate the combinatorial problems for locating and detecting arrays to undertake interaction fault location. Necessary conditions for existence are established, and using a close connection to covering arrays, asymptotic bounds on the size of minimal locating and detecting arrays are established. ::: ::: A final version of this paper appears in J Comb Optim (2008) 15: 17-48.
---
paper_title: The combinatorial design approach to automatic test generation

paper_content:

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.
---
paper_title: Covering arrays for efficient fault characterization in complex configuration spaces

paper_content:

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.
---
paper_title: Model-based testing of a highly programmable system

paper_content:

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.
---
paper_title: AETG/sup SM/ Web: a Web based service for automatic efficient test generation from functional requirements

paper_content:

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.
---
paper_title: Interaction testing of highly-configurable systems in the presence of constraints

paper_content:

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.
---
paper_title: Constructing Interaction Test Suites for Highly-Configurable Systems in the Presence of Constraints: A Greedy Approach

paper_content:

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.
---
paper_title: Exploiting Constraint Solving History to Construct Interaction Test Suites

paper_content:

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.
---
paper_title: Model-based testing in practice

paper_content:

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.
---
paper_title: Augmenting simulated annealing to build interaction test suites

paper_content:

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.
---
paper_title: Towards incremental adaptive covering arrays

paper_content:

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.
---
paper_title: Designing test suites for software interaction testing

paper_content:

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
---
paper_title: Improved quality of protocol testing through techniques of experimental design

paper_content:

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. >
---
paper_title: The AETG system: An approach to testing based on combinatorial design

paper_content:

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.
---
paper_title: Combinatorial Interaction Regression Testing: A Study of Test Case Generation and Prioritization

paper_content:

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.
---
paper_title: Factor-covering designs for testing software

paper_content:

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.
---
paper_title: Modeling requirements for combinatorial software testing

paper_content:

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.
---
paper_title: Constructing test suites for interaction testing

paper_content:

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.
---
paper_title: Input parameter modeling for combination strategies

paper_content:

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.
---
paper_title: Handling Constraints in the Input Space when Using Combination Strategies for Software Testing

paper_content:

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 ...
---
paper_title: Combination testing strategies: A survey

paper_content:

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.
---
paper_title: Using artificial life techniques to generate test cases for combinatorial testing

paper_content:

Combinatorial testing is a specification-based testing criterion, which requires that for each t-way combination of input parameters of a system, every combination of valid values of these t parameters be covered by at least one test case. This approach is motivated by the observation that in many applications a significant number of faults are caused by interactions of a smaller number of parameters. In this paper, we propose new test generation algorithms for combinatorial testing based on two artificial life techniques: a genetic algorithm (GA) and an ant colony algorithm (ACA). The usefulness of these algorithms is demonstrated through experiments. In the case t = 3 in particular, our algorithms exhibited impressive results
---
paper_title: Vector sets for exhaustive testing of logic circuits

paper_content:

(L, d)-universal sets are useful for exhaustively testing logic circuits with a large number of functional components, designed so that every functional component depends on at most d inputs. Randomized and deterministic constructions of (L, d)-universal test sets are presented, and lower and upper bounds on the optimal sizes of such sets are proven. It is also proven that the design of an optimal exhaustive test set for an arbitrary logic circuit is an NP-complete problem. >
---
paper_title: Backtracking Algorithms and Search Heuristics to Generate Test Suites for Combinatorial Testing

paper_content:

Combinatorial covering arrays have been used in several testing approaches. This paper first discusses some existing methods for finding such arrays. Then a SAT-based approach and a backtracking search algorithm are presented to solve the problem. A novel pruning strategy called SCEH is proposed to increase the efficiency of the methods. Several existing search heuristics and symmetry breaking techniques are also used in the backtracking search algorithm. Lastly, this paper introduces a tool called EXACT (EXhaustive seArch of Combinatorial Test suites) which implements all the above techniques to construct the covering arrays automatically. The experimental results show that our backtracking search method outperforms other methods in many small size cases.
---
paper_title: Automating test case generation for the new generation mission software system

paper_content:

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.
---
paper_title: An investigation of the applicability of design of experiments to software testing

paper_content:

Approaches to software testing based on methods from the field of design of experiments have been advocated as a means of providing high coverage at relatively low cost. Tools to generate all pairs, or higher n-degree combinations, of input values have been developed and demonstrated in a few applications, but little empirical evidence is available to aid developers in evaluating the effectiveness of these tools for particular problems. We investigate error reports from two large open-source software projects, a browser and Web server, to provide preliminary answers to three questions: Is there a point of diminishing returns at which generating all n-degree combinations is nearly as effective as all n+1-degree combinations? What is the appropriate value of n for particular classes of software? Does this value differ for different types of software, and by how much? Our findings suggest that more than 95% of errors in the software studied would be detected by test cases that cover all 4-way combinations of values, and that the browser and server software were similar in the percentage of errors detectable by combinations of degree 2 through 6.
---
paper_title: Combinatorial group testing methods for the BIST diagnosis problem

paper_content:

We examine an abstract formulation of BIST diagnosis in digital logic systems. The BIST diagnosis problem has applications that include identification of erroneous test vectors, faulty scan cells, faulty modules, and faulty logic blocks in FPGAs. We develop an abstract model of this problem and show a fundamental correspondence to the well-established subject of combinatorial group testing (CGT) [Ding-Zhu Du et al., (1994)]. Armed with this new perspective, we show how to improve on a number of existing techniques in the VLSI diagnosis literature. In addition, we adapt and apply a number of CGT algorithms that are well-suited to the diagnosis problem in the digital realm. We also propose completely new methods and empirically evaluate the different algorithms. Our experiments show that results of the proposed algorithms outperform recent diagnosis techniques [J. Ghosh-Dastidar et al. (1999), (2000), J. Rajski et al. (1997)]. Finally, we point out future directions that can lead to new solutions for the BIST diagnosis problem.
---
paper_title: Constraint Models for the Covering Test Problem

paper_content:

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.
---
paper_title: Case studies and new results in combinatorial enumeration

paper_content:

A 1976 block design enumeration algorithm has been reimplemented with a number of enhancements. Its use is demonstrated with a number of case studies involving different kinds of incidence structures. New results include the enumeration of weakly union-free twofold triple systems of orders 12 and 13, Mendelsohn triple systems of orders 10 and 12, 2-(8, 4, 9), 2-(10, 4, 4), 2-(16, 4, 2), 3-(11, 5, 4) and 4-(12, 6, 4) block designs, and 2-(7, 3, λ) designs for 14 ≤ λ ≤ 16. Some of these results correct enumerations previously published in the literature. Additional results confirm independently produced results, some of which have been published quite recently. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 239–260, 2000
---
paper_title: Software fault interactions and implications for software testing

paper_content:

Exhaustive testing of computer software is intractable, but empirical studies of software failures suggest that testing can in some cases be effectively exhaustive. We show that software failures in a variety of domains were caused by combinations of relatively few conditions. These results have important implications for testing. If all faults in a system can be triggered by a combination of n or fewer parameters, then testing all n-tuples of parameters is effectively equivalent to exhaustive testing, if software behavior is not dependent on complex event sequences and variables have a small set of discrete values.
---
paper_title: Upper bounds for covering arrays by tabu search

paper_content:

A t-covering array is a collection of k vectors in a discrete space with the property that, in any t coordinate positions, all combinations of the coordinate values occur at least once. Such arrays have applications, for example, in software testing and data compression. Covering arrays are sometimes also called t-surjective arrays or qualitatively t-independent families; when t=2 covering arrays are also called group covering designs or transversal covers. In an optimal covering array the number of vectors is minimized. Constructions for optimal covering arrays are known when t=2 and the vectors are binary vectors, but in the other cases only upper and lower bounds are known. In this work a tabu search heuristic is used to construct covering arrays that improve on the previously known upper bounds on the sizes of optimal covering arrays.
---
paper_title: Improved test generation algorithms for pair-wise testing

paper_content:

Software testing is expensive and time consuming. Given the different input parameters with multiple possible values for each parameter, performing exhaustive testing which tests all possible combinations is practically impossible. Generating an optimal test set which will effectively test the software system is therefore desired. Pair-wise testing is known for its effectiveness in different types of software testing. Pair-wise testing requires that for a given numbers of input parameters to the system, each possible combination of values for any pair of parameters be covered by at least one test case. Pair-wise testing is known for its effectiveness in different types of software testing. The problem of generating a minimum size test set for pair-wise testing is NP-complete. This paper presents new techniques for reducing the number of test cases for pair-wise testing. The paper shows an algorithm to generate test cases for 2-valued parameters and how orthogonal arrays and ordered designs may be used for deriving test cases for parameters with more than two values. Moreover, using mixed-level or asymmetric orthogonal array as tool, we present test set generation strategy for parameters with different number of values. A comparison of empirical results with previous test generation strategies "AETG" and "IPO" shows that the number of test cases generated with the proposed methodology is never higher and in some cases significantly lower than using AETG or IPO
---
paper_title: Reducing time to market with combinatorial design method testing

paper_content:

Testers face the challenge of doing as much testing as possible within the available, and usually constrained, schedule. In the hypercompetitive commercial marketplace, it is not practical to exhaustively test all combinations of system test cases. This paper discusses the author’s experience with a method that generates a small subset of test cases which provides good coverage of the test domain—the Combinatorial Design Method. It has proven to be flexible for system level testing of small, commercial satellite ground systems. Cost savings of 67% and schedule savings of 68% are shown for an example.
---
paper_title: 172 Constraint-Based Approaches to the Covering Test Problem ⋆

paper_content:

Covering arrays have been studied for their applications to drug screening and software and hardware testing. In this paper, we model the problem as a constraint program. Our proposed models exploit non-binary (global) constraints, redundant modelling, channelling constraints, and symmetry breaking constraints. Our initial experiments show that with our best integrated model, we are able to either prove optimality of existing bounds or find new optimal values for arrays of moderate size. Local search on a SAT-encoding of the model is able to find improved bounds on larger problems.
---

Title: A Survey of Combinatorial Testing

Section 1: Introduction
Description 1: Introduce the relevance and benefits of combinatorial testing in improving software quality by detecting failures caused by parameter interactions.

Section 2: Background
Description 2: Provide an overview of combinatorial testing, including formal notations, definitions, and the evolution of test suites for CT.

Section 3: Definitions of Test Suite for CT
Description 3: Define orthogonal arrays, covering arrays, and variable strength covering arrays and discuss their significance in combinatorial testing.

Section 4: Test Case Generation Methods
Description 4: Discuss different methods for generating test suites in combinatorial testing, such as greedy algorithms, heuristic search techniques, mathematical methods, and random methods.

Section 5: The State of CT Research
Description 5: Survey the various research topics within combinatorial testing, including modeling of SUT, test suite generation, prioritization, failure diagnosis, and metrics.

Section 6: Model of SUT
Description 6: Review the importance and methods for modeling the system under test (SUT) and the key issues in identifying parameters, values, interactions, and constraints.

Section 7: Combination Strategies and Tools for Test Suite Generation
Description 7: Introduce combination strategies, covering arrays, seeding, constraints handling, and the tools available for generating test suites.

Section 8: Test Case Prioritization
Description 8: Explain the criteria and methods for test case prioritization, and the impact of prioritization on the effectiveness of combinatorial testing.

Section 9: Failure Diagnosis
Description 9: Describe methods to diagnose failures and localize faults by identifying failure-triggering schemas using combinatorial testing results.

Section 10: Metric and Evaluation
Description 10: Discuss the metrics used to evaluate combinatorial testing itself and methods to assess the quality of the SUT after CT.

Section 11: The Application of CT and Testing Procedure
Description 11: Discuss the application of combinatorial testing in different contexts and the refinement of testing procedures to enhance effectiveness.

Section 12: Summary
Description 12: Summarize the contributions to combinatorial testing from various research groups and the evolution of the field.

Section 13: Conclusion and Future Work
Description 13: Conclude the survey by discussing the current state of combinatorial testing, its proven capabilities, and areas for future research.