Using projections to debug large combinatorial models

Abstract

Combinatorial test design (CTD) is an effective test planning technique that reveals faults resulting from parameters interactions in a system. The test space is manually modeled by a set of parameters, their respective values, and restrictions on the value combinations - referred to as a CTD model. Each possible combination of values in the cross product of the parameters, that is not excluded by restrictions, represents a valid test. 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 usually a user input. In many real-life testing problems, the relationships between the different test parameters are complex. Thus, precisely capturing them by restrictions in the CTD model might be a very challenging and time consuming task. Since the test space is of exponential size in the number of parameters, it is impossible to exhaustively review all potential tests. In this paper, we present technology that supports the modeling process by enabling repeated reviews of projections of the test space on a subset of the parameters, while indicating how the value combinations under review are affected by the restrictions. In addition, we generate explanations as to why the restrictions exclude specific value combinations of the subsets of parameters under review. These explanations can be used to identify modeling mistakes, as well as to increase the understanding of the test space. Furthermore, we identify specific excluded combinations that may require special attention, and list them for review together with their corresponding exclusion explanation. To enable the review of subsets of the exponential test space, indicate their status, and identify excluded combinations for review, we use a compact representation of the test space that is based on Binary Decision Diagrams. For the generation of explanations we use satisfiability solvers. We evaluate the proposed technology on real-life CTD models and demonstrate its effectiveness. © 2013 IEEE.