The key insight underlying combinatorial testing’s effectiveness resulted from a series of studies by NIST from 1999 to 2004. NIST research showed 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. A method called "pairwise testing" has been popular for decades as a way of detecting such interactions.
But it is not enough to test all pairs of values, because many failures are only revealed when more than two conditions are true. Surprisingly, no one had investigated the distribution of interactions involving more than two factors prior to the 1999 research. Looking at many other applications in different domains revealed similar patterns of failure-triggering interactions:
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
As noted, empirical data show that only a small number of factors are involved in software failures. We can't do exhaustive testing, but the interaction rule says we don't have to; we can still provide very strong assurance by testing all 4-way to 6-way combinations. Obviously we don't know which combinations trigger faults, but we can include all t-way combinations in a mathematical structure called a covering array, which is just a matrix that includes all t-way combinations of factor values. There is still of course no guarantee of finding all defects, but multiple studies have found 4-way to 6-way combination coverage was able to detect all faults found with exhaustive testing (see Case Studies section). Thus we can refer to this type of testing as "effectively exhaustive" (within reason!).
Security and Privacy: assurance, modeling, testing & validation
Technologies: semiconductors, software & firmware