Software implementation errors are one of the most significant contributors to information system security vulnerabilities, making software testing an essential part of system assurance. In 2003 NIST published a widely cited report which estimated that inadequate software testing costs the US economy $59.5 billion per year, even though 50% to 80% of development budgets go toward testing. Exhaustive testing – testing all possible combinations of inputs and execution paths – is impossible for real-world software, so high assurance software is tested using methods that require extensive staff time and thus have enormous cost. For less critical software, budget constraints often limit the amount of testing that can be accomplished, increasing the risk of residual errors that lead to system failures and security weaknesses.
Combinatorial testing is a method that can reduce cost and increase the effectiveness of software testing for many applications. The key insight underlying this form of testing is that not every parameter contributes to every failure and most failures are caused by interactions between relatively few parameters. Empirical data gathered by NIST and others suggest that software failures are triggered by only a few variables interacting (6 or fewer). This finding has important implications for testing because it suggests that testing combinations of parameters can provide highly effective fault detection. Pairwise (2-way combinations) testing is sometimes used to obtain reasonably good results at low cost, but pairwise testing may miss 10% to 40% or more of system bugs, and is thus not sufficient for mission-critical software. Combinatorial testing beyond 2-way has been limited, primarily due to a lack of good algorithms for higher interaction levels such as 4-way to 6-way testing. New algorithms, however, have made combinatorial testing beyond pairwise practical for industrial use.