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.

Constraint Handling In Combinatorial Test Generation Using Forbidden Tuples

Published

Author(s)

Raghu N. Kacker, David R. Kuhn, Yu Lei

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 early 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 parameters. The key idea of our approach is use a notion called minimum forbidden tuples to perform validity checks on both complete and partial tests. Furthermore, we propose an on-demand strategy that generates minimal forbidden tuples needed to perform 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 the constraint solving-based approach in PICT. For some large systems, the improvement on test generation time is up to two orders of magnitude.
Proceedings Title
Proceedings of
Seventh IEEE International Conference on Software Testing, Verification and Validation
ICST 2015
Conference Dates
April 13-17, 2015
Conference Location
Graz
Conference Title
Seventh IEEE International Conference on Software Testing, Verification and Validation
ICST 2015
ICST 2015

Keywords

Combinatorial Testing, Constraints, Forbidden Tuples

Citation

Kacker, R. , Kuhn, D. and Lei, Y. (2015), Constraint Handling In Combinatorial Test Generation Using Forbidden Tuples, Proceedings of Seventh IEEE International Conference on Software Testing, Verification and Validation ICST 2015, Graz, -1, [online], https://doi.org/10.1109/ICSTW.2015.7107441 (Accessed February 22, 2024)
Created April 12, 2015, Updated September 21, 2020