The Problem – Combinatorial Explosion

Testers often notice an interesting—though not surprising—phenomenon: When usage of an application jumps dramatically, components that have operated without trouble suddenly develop previously undetected errors. For example, newly added customers may have account records with an oddball combination of values that have not been seen before. Some of these rare combinations trigger faults that have escaped previous testing and extensive use. Or the application may have been installed on a new combination of DBMS-OS-hardware-network than was previously tested.

Combinatorial Testing

Combinatorial testing can help detect problems like this early in the testing life cycle. The key insight underlying combinatorial testing is to test the interaction between the different parameters that effect the system, and that not every possible parameter is a contributor to every fault. Most faults are caused by interactions between a relatively small number of parameters.

Pairwise Testing

Suppose we want to demonstrate that a new software application works correctly on PCs that use the Windows or Linux operating systems, Intel or AMD processors, and the IPv4 or IPv6 protocols. This is a total of 2 × 2 × 2 = 8 possibilities but, as the chart shows, only four tests are required to test every component interacting with every other component at least once. In this most basic combinatorial method, known as pairwise testing, at least one of the four tests covers all possible pairs of values among the three parameters.

Even though pairwise testing is not exhaustive, it is useful because it can check for simple, potentially problematic interactions with relatively few tests. The reduction in test set size from eight to the four shown in the diagram is not that impressive, but consider a larger example: a manufacturing automation system that has 20 controls, each with 10 possible settings—a total of 10²⁰ (100,000,000,000,000,000,000) combinations, which is far more than a software tester would be able to test in a lifetime. Surprisingly, we can check all pairs of these values with only 180 tests if they are carefully constructed.

Learn More

You can read more about combinatorial and pairwise testing, including the results of a 10-project study that showed more than twice as many defects per tester hour, in “Combinatorial Software Testing” published by the IEEE.