NIST logo

Publication Citation: An Efficient Algorithm for Constraint Handling in Combinatorial Test Generation

NIST Authors in Bold

Author(s): Raghu N. Kacker;
Title: An Efficient Algorithm for Constraint Handling in Combinatorial Test Generation
Published: March 18, 2013
Abstract: Combinatorial testing has been shown to be a very effective testing strategy. An important problem in combinatorial testing is dealing with constraints, i.e., restrictions that must be satisfied in order for a test to be valid. In this paper, we present an efficient algorithm, called IPOG-C, for constraint handling in combinatorial testing. Algorithm IPOG-C modifies an existing combinatorial test generation algorithm called IPOG to support constraints. The major contribution of algorithm IPOG-C is that it includes three optimizations to improve the performance of constraint handling. These optimizations can be generalized to other combinatorial test generation algorithms. We implemented algorithm IPOG-C in a combinatorial test generation tool called ACTS. We report experimental results that demonstrate the effectiveness of algorithm IPOG-C. The three optimizations increased the performance by one or two orders of magnitude for most subject systems in our experiments. Furthermore, a comparison of ACTS to three other tools suggests that ACTS can perform significantly better for systems with more complex constraints.
Conference: Sixth IEEE International Conference on Software Testing, Verification and Validation ICST 2013
Proceedings: Proceedings of Sixth IEEE International Conference on Software Testing, Verification and Validation ICST 2013
Location: Luxembourg, -1
Dates: March 17-22, 2013
Keywords: Combinatorial Testing; Constraint Handling; Test Gen
Research Areas: Software, Math
PDF version: PDF Document Click here to retrieve PDF version of paper (344KB)