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

Chapter 4
The IPO Family

Abstract Aside from the one-test-at-a-time strategy, the in-parameter-order (IPO)
is another greedy strategy for generating covering arrays. As the name says, the
IPO strategy extends the covering array in parameter order. In each iteration, the
algorithm extends a smaller covering array into a larger covering array with one
more parameter. The extension process has two stages, which extends the covering
array horizontally and vertically, respectively.

4.1 In-Parameter-Order

The in-parameter-order (IPO) strategywas first introduced by Lei and Tai [ 3 ], andwas
later modified and generalized as the in-parameter-order-general (IPOG) test genera-
tion framework [ 4 ]. Different from the one-test-at-a-time strategy, which extends the
covering array row by row, the IPO strategy extends the covering array in parameter
order: it starts from a small covering array of a subset of parameters, and gradually
extends the small covering array into larger covering arrays. Suppose at a certain
moment, the current covering array is a set of the first i parameters, the IPO strategy
first extends the covering array by adding an additional column so that the resulting
array with i 1 columns covers as many target combinations as possible, and then

it extends the array vertically by adding new rows to cover the remaining uncov-
ered target combinations of the first i

+

1 parameters. And finally, when the array is
extended to k columns, it becomes a complete covering array for the k parameters.
The execution of the IPO algorithms can be illustrated as Fig. 4.1 .
The original IPOG algorithm is shown in Algorithm 3, which is intended to be
used to generate covering arrays for some fixed covering strength t .
The algorithm first initializes the test suite as all combinations of the first t para-
meters in line 2. Then, it enters a for-loop in line 3. In the i th iteration of the for-loop,
the algorithm starts from a covering array of the first i

+

1 parameters, and extends
the covering array to a larger covering array of the first i parameters. The exten-
sion process has two stages: a horizontal extension and a vertical extension. The
horizontal extension stage adds one column for the i th parameter, covering as many
new target combinations as possible. After horizontal extension, the array may still

−