Constraint handling in combinatorial test generation using forbidden tuples

Abstract

Constraint handling is a challenging problem in combinatorial test generation. In general, there are two ways to handle constraints, i.e., constraint solving and forbidden tuples. In our earlier work, we proposed a constraint handling approach based on forbidden tuples for software product line systems consisting of only Boolean parameters. In this paper, we generalize this approach for general software systems that may consist of other types of parameter. The key idea of our approach is using the notion of minimum forbidden tuples to perform validity checks on both complete and partial tests. Furthermore, we propose an on-demand strategy that only generates minimum forbidden tuples for validity checks as they are encountered, instead of generating all of them up front. We implemented our generalized approach with and without the on-demand strategy in our combinatorial testing tool called ACTS. We performed experiments on 35 systems using ACTS and PICT. The results show that for these 35 systems, our generalized approach performed faster than PICT and the constraint solving-based approach in ACTS. For some large systems, the improvement on test generation time is up to two orders of magnitude.