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.

PUBLICATIONS

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
Pub Type
Conferences

Download Paper

https://doi.org/10.1109/ICSTW.2015.7107441
Local Download

Keywords

Combinatorial Testing, Constraints, Forbidden Tuples
Numerical methods and software and Mathematics and statistics

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 April 19, 2024)

Created April 12, 2015, Updated September 21, 2020