Efficient algorithms and tools for practical combinatorial testing

Abstract

Combinatorial Testing (CT) is an effective testing strategy which has seen increased adoption in the field of software testing. As a black-box testing technique it concerns itself with generating input test cases able to provide mathematical input-space coverage guarantees while keeping the number of test cases low. Generating optimal combinatorial test sets is believed to be a hard optimization problem which has spurred the development of several greedy algorithms which trade-off optimality for speed. One of the most popular representatives is the In-Parameter-Order family of algorithms. This class of algorithms has seen a wide adoption in including software, hardware and security testing as they are able to construct test sets for most instances occurring in practice. In this thesis, an efficient design of the In-Parameter-Order algorithms is presented which drastically reduces the time and required memory to compute combinatorial test sets. The improved theoretical design is implemented in a prototype and benchmarked against the state of the art implementation. Furthermore, the algorithms are made available in a general purpose test generation tool developed for this thesis which is open and free to use by anyone. The thesis also studies the impact of tie-breaking, parameter ordering and tuple enumeration order on the resulting test sets. An extensive experimental study shows that different tie-breakers have no significant impact on average and that ordering parameters in order of descending domain size can lead to drastically smaller test sets.