Combinatorial Methods for Trust and Assurance

Combinatorial testing is the use of tests that cover t-way combinations of parameter values, up to some specified criterion of coverage.  For example, if we have three boolean parameters, P₁, P₂, and P₃, then 2-way coverage can be achieved if we cover all four combinations of values (00, 01, 10, 11) for every pair of these parameters.  There are three pairs in this example:  (P₁, P₂), (P₁, P₃), and (P₂, P₃).  A structure called a covering array can compress all t-way combinations of values into an amazingly small set of tests. For example, there are 1,329,336,000 3-way combinations of 1,000 boolean variables. The ACTS tool generates covering arrays, and produces a test set of 71 tests that cover all of these 1,329,336,000 combinations. 

The key insight underlying combinatorial testing’s effectiveness is that most software bugs and failures are caused by one or two parameters, with progressively fewer by three or more. That is, they were only revealed when multiple conditions were true.  For example, a 2-way interaction fault could be "altitude = 0 AND volume < 2.2". So testing all 2-way combinations of parameter values could detect this problem.  But it is not enough to test all pairs of values, because many failures are only revealed when more than two conditions are true.  The distribution of failures by number of interacting factors (X axis) is shown below for a range of applications. 

As can be seen in the graph, most failures were caused by one or two parameters, with progressively fewer by three or more. This finding, referred to as the interaction rule, has important implications for software testing because 

• it is nearly always impossible to do exhaustive testing, but
• we don't have to test all possible combinations of inputs;
• we only have to test all of the combinations that trigger faults  

We can't do exhaustive testing, but the interaction rule says we don't have to, within reason; we can still provide very strong assurance by testing all 4-way to 6-way combinations.  Multiple studies have found 4-way to 6-way combination coverage was able to detect all faults found with exhaustive testing. Thus we can refer to this type of testing as "effectively exhaustive" (within reason). 

Combinatorial methods can be applied to all types of software, but are especially effective where interactions between parameters are significant.  The primary industry applications for ACTS are in database and e-commerce, aerospace, finance, telecommunications, industrial controls, and video game software, but we have users in probably every industry.  A sample of case studies can be found here. 

This depends on the level of assurance required.  As can be seen in the graph above, most failures are triggered by a single factor or the interaction of two factors, with progressively fewer by three or more factors. We have not seen more than six factors involved in a failure, so 7-way or higher faults appear to be extremely rare.  Note also:

• Variability decreases rapidly with interaction strength, from more than 50 percentage points difference between high and low values for 1-way and 2-way faults, to less than 25 points for 4-way, to less than 5 points difference for 5-way faults.  In other words, testing effectiveness may be more predictable with higher strength tests (4-way or higher). 
• Easily found faults decline with use and testing. As might be expected, the more software is used and tested, the harder it becomes to find remaining errors.  We refer to the distribution of faults as the fault profile.  The best fault profiles in the graph below are for the Apache server and NeoKylin, a Linux variant, probably because these both have hundreds of millions of users.  The poorest fault profiles are the DBMS, which was from initial testing, and FDA medical device recalls, for devices that may have only a few thousand users.  We have developed a mathematical model that is closely consistent with the empirical data (see Kuhn, D.R., Kacker, R.N. and Lei, Y., 2017, March. A Model for T-Way Fault Profile Evolution during Testing. In 2017 IEEE International Conference on Software Testing, Verification and Validation Workshops). 

As with all test methods, it will not be possible to include billions of values in tests, so parameter values should be partitioned into subsets that are relevant to the system requirements.  In general, it is best to keep the partition of test parameters to no more than 10 or so values per parameter.  Standard practices for equivalence partitions and boundary value analysis should be applied for determining representative parameter values. 

The number of tests produced by ACTS or other covering array generators is proportional to v^t log n, for v values per parameter, with n parameters, for a t-way covering array.  Note that this is not the exact number of tests produced; the test set size is proportional to this value, i.e., the number of tests grows exponentially with the number of values, but only logarithmically with the number of parameters.  This size is a characteristic of covering arrays, and holds for all covering array generating tools, not just ACTS.  For the tester, this means that it is best to keep the number of values per parameter under about 10, but it is not a problem to have hundreds of parameters.  We have produced test sets for more than 2,000 parameters.  A database of the best known covering array sizes can be found here.  

Branch coverage should be measured.  If branch coverage is not close to 100%, then (1) input parameter values can be changed to improve the test set, or (2) a higher strength (higher value of t) covering array can be used.  The question below on combinatorial coverage explains why this heuristic is important. 

No, combinatorial coverage is a completely different concept.  It measures the degree to which combinations of input values have been covered in tests, which is a static property of the test set.  Measures such as statement or branch coverage are dynamic properties, as they measure the proportion of statements and branches covered when the program is running.

There is a relationship between combinatorial coverage and structural coverage, captured in the branch coverage condition theorem. Where M_t is the proportion of input combinations covered, and B_t is the minimum proportion of input combinations triggering a code branch, then 100% branch coverage will be achieved if 

                          M_t +  B_t > 1                                                                    (1)

The reason this condition is important in combinatorial testing is that we will normally be using covering arrays, which by definition have M_t = 100%, for a t-way covering array.  The term B_t refers to the minimum proportion of input combinations that trigger a branch. For example, in the statements if (A&&B) line1; if (C) line2;,  where A and B are Boolean variables, M_t = .25, because line1 is executed only for one of the possible four settings of A&&B.  Clearly, it is always true that B_t > 0, so how can relation (1) above ever be false if we use a covering array in testing? In fact it cannot, if the input space has been properly modeled, that is if variable value partitions have been properly defined.  So failure to achieve close to 100% branch coverage indicates that the input model should be revised. The branch coverage condition provides a theoretical justification for the heuristic of requiring structural coverage as a means of validating requirements-based tests. 

If we take parameters with v values each, and form t-way combinations, each combination can have v^t possible settings.  The number of these combinations taken from n parameters is C(n, t) = n!/t!(n-t)!, commonly called "n choose t".  So the total number of possible t-way combinations of n parameters with v values each is v^t * C(n,t).

Consider a small example, with five parameters - a, b, c, d, e - of two values each: 0 or 1. If we take any two, such as (b,e), the possible value settings are 00, 01, 10, 11. We can systematically list the 2-way combinations:  (a,b), (a,c), (a,d), (a,e), (b,c), (b,d), (b,e), (c,d), (c,e), (d,e).  The number of 2-way combinations is thus 2² * C(5,2) = 40. 

Hundreds of corporations and organizations use the ACTS combinatorial testing tools.  See our case studies for published examples from some of the world's largest organizations, including Adobe, Avaya, Daimler AG, IBM, Jaguar Land Rover, Lockheed Martin, Red Hat, Rockwell Collins, Siemens, the US Air Force, the US Marine Corps, and others. Many universities also use the tools in software testing courses. 

Software on this site is free of charge and will remain free in the future. It is public domain; no license is required and there are no restrictions on use. You are free to include it and redistribute it in commercial products if desired. NIST is an agency of the United States Government, conducting research in advanced measurement and test methods. 

To obtain the tools, please send a request to Rick Kuhn - kuhn@nist.gov  including your name and the name of your organization. No other information is required, but we like to have a list of organizations so that we can show our management where the software is being used. We will send you a download link.