This is a potential security issue, you are being redirected to https://csrc.nist.gov.
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
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:
The number of tests produced by ACTS or other covering array generators is proportional to vt 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 Mt is the proportion of input combinations covered, and Bt is the minimum proportion of input combinations triggering a code branch, then 100% branch coverage will be achieved if
Mt + Bt > 1 (1)
The reason this condition is important in combinatorial testing is that we will normally be using covering arrays, which by definition have Mt = 100%, for a t-way covering array. The term Bt 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, Mt = .25, because line1 is executed only for one of the possible four settings of A&&B. Clearly, it is always true that Bt > 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 vt 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 vt * 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 22 * C(5,2) = 40.
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 - firstname.lastname@example.org 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.