Generating small combinatorial test suites to cover input-output relationships
- 1 January 2003
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In this paper, we consider a problem that arises in black box testing: generating small test suites (i.e., sets of test cases) where the combinations that have to be covered are specified by input-output parameter relationships of a software system. That is, we only consider combinations of input parameters that affect an output parameter. We also do not assume that the input parameters have the same number of values. To solve this problem, we revisit the greedy algorithm for test generation and show that the size of the test suite it generates is within a logarithmic factor of the optimal. Unfortunately, the algorithm's main weaknesses are its time and space requirements for construction. To address this issue, we present a problem reduction technique that makes the greedy algorithm or any other test suite generation method more efficient if the reduction in size is significant.Keywords
This publication has 9 references indexed in Scilit:
- Generating expected results for automated black-box testingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Small Maximal Independent Sets and Faster Exact Graph ColoringLecture Notes in Computer Science, 2001
- Model-based testing in practicePublished by Association for Computing Machinery (ACM) ,1999
- Factor-Covering Designs for Testing SoftwareTechnometrics, 1998
- The AETG system: an approach to testing based on combinatorial designIEEE Transactions on Software Engineering, 1997
- Applying design of experiments to software testingPublished by Association for Computing Machinery (ACM) ,1997
- Covering arrays and intersecting codesJournal of Combinatorial Designs, 1993
- Vector sets for exhaustive testing of logic circuitsIEEE Transactions on Information Theory, 1988
- The program dependence graph in static program testingInformation Processing Letters, 1987