Using binary decision diagrams for combinatorial test design

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. © 2011 ACM.