Using binary decision diagrams for combinatorial test design
Authors:
Open Access
- 17 July 2011
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 254-264
Abstract
Combinatorial test design (CTD) is an effective test planning technique that reveals faulty feature interaction in a given system. The test space is modeled by a set of parameters, their respective values, and restrictions on the value combinations. A subset of the test space is then automatically constructed so that it covers all valid value combinations of every t parameters, where t is a user input. Various combinatorial testing tools exist, implementing different approaches to finding a set of tests that satisfies t-wise coverage. However, little consideration has been given to the process of defining the test space for CTD, which is usually a manual, labor-intensive, and error-prone effort. Potential errors include missing parameters and their values, wrong identification of parameters and of valid value combinations, and errors in the definition of restrictions that cause them not to capture the intended combinations. From our experience, lack of support for the test space definition process is one of the main obstacles in applying CTD to a wide range of testing domains. In this work, we present a Cartesian product based methodology and technology that assist in defining a complete and consistent test space for CTD. We then show how using binary decision diagrams (BDDs) to represent and build the test space dramatically increases the scalability of our approach, making it applicable to large and complex real-life test design tasks, for which explicit representation of the test space is infeasible. Finally, we show how BDDs can be used also to solve the CTD problem itself. We present a new and highly effective BDD-based approach for solving CTD, which finds a set of tests that satisfies t-wise coverage by subset selection. Our approach supports also advanced requirements such as requirements on the distribution of values in the selected tests. We apply our algorithm to real-life testing problems of varying complexity, and show its superior performance.Keywords
This publication has 13 references indexed in Scilit:
- Practical Combinatorial Testing: Beyond PairwiseIT Professional, 2008
- Software fault interactions and implications for software testingIEEE Transactions on Software Engineering, 2004
- Upper bounds for covering arrays by tabu searchDiscrete Applied Mathematics, 2004
- Logic verification using binary decision diagrams in a logic synthesis environment2003
- A test generation strategy for pairwise testingIEEE Transactions on Software Engineering, 2002
- Determination of Test Configurations for Pair-Wise Interaction Coverage2000
- The AETG system: an approach to testing based on combinatorial designIEEE Transactions on Software Engineering, 1997
- Graph-Based Representations of Discrete Functions1996
- Improving the variable ordering of OBDDs is NP-completeIEEE Transactions on Computers, 1996
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986