The IPO Family - Automatic Generation of Combinatorial Test Data - page 46

test case with don't-care values, and the solver produces a feasible solution, which
could be translated back into a full test case. The resulting test suite is:
⎛
⎝

⎞
⎠

1111
1222
2121
2221
1212
2122

.

And one more step, we reorder the columns back to the original order of parame-
ters, and the resulting test suite is:

⎛ ⎞

1111
1222
2211
2212
1122
2221

⎝ ⎠

.

4.4 IPO Variants

IPO is a very general framework. Since the original algorithm was proposed, there
have been a number of extensions to the basic framework.

• Covering strength . The original IPO algorithm was used for pairwise test gener-

ation [ 3 , 7 ]. It was extended to support t -way test generation by initializing the
starting test suite as the set of all the combinations of the first t parameters [ 4 ].
Nie et al. [ 6 ] and Wang et al. [ 8 , 9 ] also provided modifications for support of
variable-strength covering arrays.

• Initial parameter order . The IPOG algorithm [ 4 ] suggests putting parameters into

an arbitrary order, and some research papers [ 5 , 10 ] suggest sorting the parameters
in nonincreasing order of their domain sizes.

• Horizontal growth . In the original IPOalgorithm, two horizontal growth algorithms

were proposed: (1) By enumerating all possible permutations of parameter values
for the new column, and selecting the permutation covering the greatest number
of uncovered target combinations. However this strategy is extremely expensive;
(2) By assigning each value of parameter p i once for the first s i rows, and for the
remaining rows, selecting values greedily just as the IPOG algorithm. The special
treatment for the first s i rows is actually unnecessary, and was not used in later IPO-
based algorithms. Forbes et al. [ 2 ] proposed that if for a certain row, all values for
parameter p i cover no uncovered target combinations, a don't-care value is added