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

when all target combinations are covered. The main difference between algorithms
based on this strategy resides in their different strategies to generate new test cases.
Here, we call a combination

σ ={ ( p i 1 , v i 1 ), ( p i 2 , v i 2 ),...,( p i l , v i l ) } to be cov-

v 1 , v 2 ,..., v k ) v i j , i.e.,

ered by test case θ = ( if and only if for 1 ≤ j ≤ l , v i j =

the value of each parameter in σ is consistent with the corresponding value in θ .A

combination is said to be covered by a test suite if and only if the test suite has at

least one test case covering

σ

σ . If there is no test case in a test suite, which covers σ ,

σ

the combination is said to be uncovered .

Note that with the presence of constraints, some target combinations may be in-
valid , i.e., no test case satisfying all the constraints can cover these combinations.
As a consequence, the algorithm needs to give special consideration to the target
combinations, since we need to know which target combinations are valid so that
we can decide whether the current test suite meets the coverage requirement. Some
algorithms check the validity of target combinations one by one during the initial-
ization of the set of target combinations. But this may cost a lot of time when the
number of target combinations is large.

3.2 Automatic Efficient Test Generator (AETG)

3.2.1 The AETG Algorithm

The one-test-at-a-time strategy was first used in AETG (Automatic Efficient Test
Generator) [ 6 ]. The AETG algorithm is described as follows (suppose we are gen-
erating a covering array of strength t ):
To generate each new test case, the algorithm first generates M candidate test
cases (in the original AETG algorithm, M

50), and selects the one covering the
greatest number of uncovered target combinations as the new test case. For generating
each candidate test case, AETG chooses the first parameter-value pair that appears
the most frequently in the remaining target combinations (line 7 and 8). Then, it
permutes the remaining parameters in random order (line 9), and greedily assigns
values to them (line 10-13). For assigning each parameter, AETG chooses the value
that makes the resulting partial test case cover the great number of uncovered target
combinations.
To deal with constraints, as described in their patent [ 5 ], the original algorithm
checks whether each candidate test case satisfies all the constraints after it is gener-
ated. If the new candidate test case does not satisfy all the constraints, it permutes
the field labels to see whether the constraints are satisfied. If not, the algorithm aban-
dons the candidate test case. If all the candidate test cases violate the constraints, the
algorithm uses exhaustive search to find a valid test case.
We can see the constraint handling of the original AETG algorithm is inefficient,
since when the number of constraints is large, most of the possible test cases will be
invalid, so the candidate test cases generated by AETG are very likely to be invalid,

=