An Efficient Algorithm for Constraint Handling in Combinatorial Test Generation

Published

March 18, 2013

Author(s)

Raghu N. Kacker

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.

Proceedings Title

Proceedings of
Sixth IEEE International Conference on Software Testing, Verification and Validation
ICST 2013

Conference Dates

March 17-22, 2013

Conference Location

Luxembourg

Conference Title

Sixth IEEE International Conference on Software Testing, Verification and Validation ICST 2013

Pub Type

Conferences

Download Paper

Local Download

Keywords

Combinatorial Testing, Constraint Handling, Test Gen

Citation

Kacker, R. (2013), An Efficient Algorithm for Constraint Handling in Combinatorial Test Generation, Proceedings of Sixth IEEE International Conference on Software Testing, Verification and Validation ICST 2013, Luxembourg, -1, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=913191 (Accessed April 24, 2026)

Additional citation formats