Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

An Efficient Algorithm for Constraint Handling in Combinatorial Test Generation

Published

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

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 July 24, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created March 18, 2013, Updated February 19, 2017