One Test at a Time - Automatic Generation of Combinatorial Test Data - page 34

•

Layer one—Repetitions. We may generate covering arrays a number of times,
keeping the smallest one. This layer is meaningful only when some decision in
the algorithm is made randomly.

• Layer two—Candidate rows. An algorithm may generate a number of candidate

rows, choosing the best one to add to the covering array.

• Layer three—Factor ordering. Factors may be ordered either randomly, or by the

number of levels associated with a factor, or by the number of uncovered pairs
involving this factor and the fixed factors, etc.

• Layer four—Level selection. For a given factor f , we can select some level (value)

for it using some level selection criterion. For example, the candidates can be
ranked by the number of uncovered pairs involving this level (value) of the current
factor and the fixed factors.

As we mentioned earlier, AETG-SAT [ 7 , 9 ] is based on the AETG algorithm,
and uses a SAT solver to check the validity of the resulting partial test case before
any assignments are made. The algorithm handles constraints better than the original
AETG algorithm.
Jacek Czerwonka's tool PICT [ 10 ] uses a similar strategy to greedily assign values
to parameters. Like AETG-SAT, it checks constraint satisfiability when attempting
to assign a value to an unassigned parameter. PICT translates the constraints into
forbidden combinations, and computes other combinations that are forbidden as
implied by the constraints. The satisfiability check is done by checking whether the
partial test case contains any explicit or implicit forbidden combinations. It can also
guarantee the assigned partial test case is always a part of a valid test case.
The TCG algorithm [ 11 ] uses a similar strategy with AETG, but the parameter
assignment process is deterministic: (1) for adding each row, it generates only one test
case instead of multiple candidates; (2) when assigning parameter values, it selects
the least used value; (3) parameters are assigned in nonincreasing order of their
domain sizes. The DDA algorithm [ 1 , 2 ] uses a density-based approach to decide
which parameter and value to choose. It is also deterministic.
The algorithm proposed by Calvagna and Gargantini [ 4 ] generates each test case
by greedily selecting a set of consistent uncovered target combinations, and then using
a model checker to assign the remaining parameter values. Constraint satisfiability is
checked when attempting to add a new uncovered target combination to the selected
set of target combinations. For each row, the algorithm also generates only one test
case instead of multiple candidates.

3.4 Test Generation Using Constrained Optimization

What the AETG-like algorithms we described in the last section have in common
is that when generating each test case, they all proceed in a greedy manner, which
assign parameters in a certain order, and choose values for the parameters using some
strategy to maximize the number of newly-covered target combinations.