Reducing combinatorial testing requirements based on equivalences with respect to the code under test

Combinatorial testing, where different combinations of parameter values are used to create test inputs, is a well-known approach for black-box testing of software systems. Researchers have defined several coverage criteria for combinatorial testing. Among them, the most comprehensive criterion is all combinations coverage. While using this criterion gives the most assurance in the correctness of the code under test, this criterion can have too many test requirements, which can make it impractical to apply. This paper introduces a new, simple approach that provides the same assurance as all combinations coverage but typically with fewer test inputs, thereby reducing the overall cost of combinatorial testing. Our key insight is that one test input execution can cover several test requirements for combinatorial coverage criteria. Our approach builds on the Korat test-generation technique to explore which combinations of parameter values are equivalent with respect to the code under test. An illustration on a pedagogical example shows how this approach can lead to substantial reduction in the number of tests.