Practical Combinational Tutorial

What follows is from the executive summary of the publication:

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 American economy $59.5 billion a year, even though 50 percent to 80 percent 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 (six or fewer). This finding has important implications for testing because it suggests that testing combinations of parameters can provide highly effective fault detection. Pairwise (two-way combinations) testing is sometimes used to obtain reasonably good results at low cost, but pairwise testing may miss 10 percent to 40 percent or more of system bugs, and is thus not sufficient for mission-critical software. Combinatorial testing beyond two-way has been limited, primarily due to a lack of good algorithms for higher interaction levels such as four-way to six-way testing. New algorithms, however, have made combinatorial testing beyond pairwise practical for industrial use.

This publication provides a self-contained tutorial on using combinatorial testing for real-world software. It introduces the key concepts and methods, explains use of software tools for generating combinatorial tests - freely available on the NIST website -- and discusses advanced topics such as the use of formal models of software to determine the expected results for each set of test inputs.

With each topic, a section on costs and practical considerations explains tradeoffs and limitations that may impact resources or funding. The material is accessible to an undergraduate student of computer science or engineering, and includes an extensive set of references to papers that provide more depth on each topic.