Generating Method for Combinatorial Testing Data Using Propositional Normal Form Conversion

In an embedded system which operates multiple devices, combinatorial testing of multiple events is needed to verify proper behavior of the system. However, the number of test cases becomes huge, especially for the order in which events happen in parallel, and it is difficult to carry out all cases.  So many methods to generate minimum test data set have been already proposed, but their reduction is not enough or their usage is less flexible.  This paper describes a simple and flexible algorithm of generating combinatorial test data efficiently.  This method represents combination conditions with propositional logic formula in the conjunctive normal form (CNF) and converts it into the disjunctive normal form (DNF).  Each term of the DNF becomes a set of test data to cover all combinations.  This method is available to use for any type of combinatorial testing data generation, not only for an event order, and is able to impose additional conditions.  However, since this method is applicable only to the problem of small size, improvement of the algorithm is required.


The relation of CNF and DNF used here is explained using a simple example.  Assume that there are 6 kinds of food, p1...p6, and there are 5 kinds of vitamins, c1...c5, which are contained in those foods. Table 1 shows the vitamins contained in foods.  This table is called an AND-OR table, because an OR combination is used for column elements and an AND combination is used for raw elements.

The purpose here is searching for combinations of foods p1-p5 which can take in all vitamins.  In order to take in c1, p1 or p3 or p6 are required.  This is expressed as c1 = p1∨p3∨p6.  About each vitamin the conditions for required foods are as follows.

The condition which takes in all vitamins is (2).  This is the CNF which is the total condition.

This condition is converted into DNF as follows:

Each clause of DNF becomes the combination of the food which satisfies the expression (2).  For example p1 and p2 is one of the minimum set.  The foods and the vitamins in this example correspond to the test cases and the conditions to be satisfied respectively.