Combinatorial Testing

Combinatorial testing is the technique that uses the algorithm to generate different permutations of variables as test cases for finding the software defect that is caused by the interaction of certain varialbes.

Obviously the more permutations are generated to test the software, the more likely the software defect will be found. For situation that there are only a handful of variables each of which has very few set of values, the brute force approach to generate all possible permutations among all variables is feasible. However in most situations the brute force approach is not practical due to the amount of permutations to be generated. Also more test cases means increased cost in implementing the test cases and execute them.

The empirical evidence published showed that most of the software defects are caused by one or two variables. Therefore, pairwise algorithm is most commonly used combinatorial testing algorithm for generating test cases. Iin most cases it provides sufficient test coverage required with the least number of permutations (rows) compared with other algorithms.

For example on Google's Advanced Search web page there are 10 different search fields you can specify. Some fields are the values you can enter while some are dropdown list you can select a value from. To thoroughly test this page it will require over several million test cases even we only test couple of values for the fields the user has to enter. To demonstrate the differences between these algorihtms we used a very small number of values (2 values with blank as one of the value) for each of the user entered fields and cut down the language dropdown list from 40 options to 10 options. Below is the comparison on number of test cases each algorihtm generates:

  • Pairwise: 110
  • 3-Way: 550
  • 4-way: 1783
  • Full: 105,600