Combinatorial Testing for Cybersecurity and Reliability
Richard Kühn, Raghu N. Kacker, Larry Feldman, Gregory A. Witte · 2016
Combinatorial testing (CT) is a proven method for more effective software testing at lower cost. 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. This finding, referred to as the interaction rule, has important implications for software testing because it means that testing parameter combinations can provide more efficient fault detection than conventional methods. New algorithms compressing combinations into a small number of tests have made CT practical for industrial use, making it possible to do better testing at lower cost. Background Software developers often notice an interesting – though not surprising – phenomenon: when the number of system users increases significantly, components that had previously operated correctly will suddenly fail or display errors. For example, if there are many new transactions or accounts, some are likely to contain combinations of values that have not been seen before. Some of these rare combinations trigger faults that escaped previous testing and extensive use. Combinatorial testing can help detect problems early in the testing life cycle. [1] Because system failures often result from the interaction of conditions that might be innocuous individually, testing combinations of parameter values can be nearly as effective as testing all possible combinations for many types of applications. Implementing this form of testing requires a covering array, a matrix that includes all t-way combinations of values for some specified interaction level, t. As noted, most failures are caused by one or two parameters; empirical data show that the number of failures triggered by three or more parameters is small, and no failures discovered by NIST or other researchers have involved more than six parameters. As a result of this phenomenon, covering arrays that include all 3-way to 6-way combinations can provide strong testing.