A survey of combinatorial testing <s> INTRODUCTION <s> 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. <s> BIB001 </s> A survey of combinatorial testing <s> INTRODUCTION <s> 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. <s> BIB002 </s> A survey of combinatorial testing <s> INTRODUCTION <s> 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. <s> BIB003 </s> A survey of combinatorial testing <s> INTRODUCTION <s> 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). <s> BIB004 </s> A survey of combinatorial testing <s> INTRODUCTION <s> 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. <s> BIB005 </s> A survey of combinatorial testing <s> INTRODUCTION <s> 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. <s> BIB006
The use of computers is entering into every corner of social life and is becoming the important engine of economical and social progress. As the kernel of information technology, software has become a key issue affecting social and economic development. To improve software quality, many software testing methods have been proposed and studied. Different testing methods target different types of fault, and can be effective This work was supported by the National Natural Science Foundation of China (60773104, 60721002, 90818027) , 863 high technical plan of China (2008AA01Z143, 2009AA01Z147) . This article was partially written during C. Nie's sabbatical, sponsored by the Chinese Scholarship Council in CREST (Center for Research in Evolution, Search, and Testing), King's College London. Authors' addresses: C. Nie, State Key Laboratory for Novel Software Technology and Department of Computer Science and Technology, Nanjing University, Nanjing, Jiangsu, P. R. China 210093; email: changhainie@nju.edu.cn; H. Leung, Department of Computing, the Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong; email: cshleung@inet.polyu.edu.hk. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested fromfor certain testing scenarios. For example, mutation testing, which involves modifying the source-code in a small way, can help the tester develop effective tests, identify weaknesses in the test suite, or locate sections of the code that are seldom or never accessed during execution BIB001 ]; metamorphic testing can solve the oracle problem in testing based on the property of Software Under Test (SUT) BIB006 ; structural testing aims to find faults related to the internal structure of SUT BIB003 . In this article we focus on Combinatorial Testing (CT), also called Combinatorial Interaction Testing (CIT). CT tests SUT with a covering array test suite which tests all the required parameter value combinations. The advantage of CT is that it can detect failures triggered by the interactions among parameters in SUT. Suppose we want to test a network game software running in the Internet environment. The operation of this game may be influenced by many parameters, such as browser, operating system, the type of network access, graphics, audio, the number of players, and so on. Each of these parameters may take on many possible values. The interactions of these parameters may cause some failures. Due to the large combination space, exhaustive testing by testing all the parameter value combinations is generally impractical. Even if we have the resources to try all value combinations, this is not effective because most of the value combinations do not cause any failure. CT provides a practical way to detect failures caused by parameter interactions with a good tradeoff between cost and efficiency. It samples the large combination space using a smaller test suite to cover certain key parameter value combinations. As the software functions become more complex, and the running environments become distributed, networked, and more complicated, modern software systems need to be designed to be highly configurable so that they can run on and be optimized for a wide variety of platforms and support various usage scenarios. With the adoption of new software development technology, such as component-based software and the serviceoriented software, more and more software systems tend to have many parameters. Interactions of these parameters may cause failures. As a result, software testing often faces the problem of a large test combination space. These trends create a heavy demand for more intelligent test data sampling mechanisms to detect interaction triggered failures. CT offers such an effective testing technique which has been well studied and widely used in the last 20 years. Actually no single software testing technique can provide complete testing. Each type of testing technique selects test cases using its own unique sampling approach, relying on some knowledge of the system to select a subset of tests to execute BIB004 . For example, structural testing selects test cases guided by some structural coverage of source-code. CT selects test cases with a sampling mechanism to systematically cover parameter value combinations using a small test set which is relatively easy to manage and execute. It can avoid the combination explosion problem of exhaustive testing. CT has the following characteristics: (1) CT creates test cases by selecting values for parameters and by combining these values to form a covering array. The covering array specifies test data where each row of the array can be regarded as a set of parameter values for a specific test. The collection of tests (represented by the rows of the array) covers all τ -way combinations of parameter values, where τ specifies the number of parameters in combination. An example is given in Figure 3 , which shows a 2-way covering array for 4 parameters with three values each. The interesting property of this array is that any two columns contain all nine possible value combinations for two specific parameters corresponding to the columns. For example, taking columns c 1 and c 2 , we can see that all nine possible 2-way combinations occur somewhere in the rows of the two columns. In fact, this is true for any two columns. Collectively, this set of tests will exercise all 2-way combinations of input values in only 9 tests, as compared with 81 for exhaustive coverage. (2) CT uses a covering array as the test suite. The covering array aims to test as many parameter value combinations as possible in order to detect failures triggered by parameter interactions. (3) Not every parameter of SUT can trigger a fault, and some faults can be exposed by testing interactions among a small number of parameters. Kuhn et al. studied the faults in several software projects, and found that all the known faults are caused by interactions among 6 or fewer parameters BIB002 BIB005 . Based on this result, CT can be very effective for certain types of applications, with performance approaching that of exhaustive testing while using fewer test cases. (4) Being a specification-based testing technique, CT requires no knowledge about the implementation of SUT. Also, the specification required by CT is "lightweight," since we only need to know the basic system configuration to identify the input parameters and their possible values. (5) Test generation for CT can be automated, which is a key to gaining a wide industrial acceptance. In software testing, there is no guideline that dictates the best course of testing, and there are no "best practices" that can always guarantee success  . Although CT is useful in detecting certain faults, it can create a false confidence because: (1) CT may be viewed as providing a kind of shortcut of software testing. It has its own pitfalls, such as not testing all possible parameter combinations. (2) If the parameters and their values are not selected properly, this will lower the defect detection capability of CT. (3) If we fail to identify all the interactions between parameters in SUT, CT will not test those "missed" interactions. (4) If we do not have a "good enough" oracle, the verification of testing results will be difficult. To ensure successful testing, we should apply CT wisely. This requires professional skill and good judgement in its application. The full strengths and weaknesses of CT need to be better understood. In this article, we survey the state of the research of CT. In our study, we have collected over 90 key papers related to CT. We classify these papers into eight categories. Note that most of categories are nonexclusive; that is, a paper may focus on modeling of CT and also on evaluation. We assign each paper to one category based on the main objective of the paper. Thus, our classification is subjective and some papers may be classified into another category by other researchers. Nevertheless, we believe that on the whole, the distribution shown in Figure 1 represents a fairly good picture of the current state of research in CT. The remaining part of this article is organized as follows: Section 2 presents the commonly used terms of CT. Section 3 discusses the eight categories of research, and reviews the contributions from various research groups and the growing trend of CT. In the last section, we make recommendations on the future direction of research in CT. 