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

4.2 IPOG-C for Handling Constraints

Yu et al. [ 10 ] proposed the IPOG-C algorithm to add constraint handling support to
the IPOG framework. Several modifications are made:
•

During the initialization stage in line 2, the covering array is initialized as all valid
combinations of the first t parameters.

• When initializing the set of target combinations in line 4, the validity of each

target combination should be checked. Only valid target combinations are stored
in the set.

τ
be valid and make it cover the greatest number of uncovered target combinations.

• In the horizontal extension stage, the chosen value for parameter p i should make

• In the vertical extension stage, when modifying a test case to cover a target com-

bination, the resulting test case must still be valid.
When checking the validity of a target combination or a partial test case, IPOG-C
translates the problem into a constraint satisfaction problem (CSP), 1 and a constraint
solver is used to check whether a feasible solution exists. The target combination or
the partial test case is valid if and only if the resulting CSP has a solution.
The IPOG-Calgorithmprovides several optimizations to enhance the performance
of constraint handling, including the following:
•

The validity of target combinations can be postponed to the moment between
horizontal extension and vertical extension. This is because every newly-covered
target combinations in horizontal extension must be valid. So checking the validity
of target combinations after horizontal extension can greatly reduce the number
of target combinations that need to be checked, and the number of solver calls can
also be reduced.

• When checking the satisfiability of a target combination, or checking the satisfia-

bility of a partial test case after replacing don't-care values with concrete values, a
constraint relation graph is built to find all relevant constraints that may be violated
when some parameter values change. As a result, the number of constraints need
to be checked in CSP could be reduced, and the solving time could be reduced too.

• During the test generation process, IPOG-C will call the constraint solver many

times, and there is a great chance that some solver calls are identical. Recording the
solving history and reusing the results can help reduce the number of solver calls.

4.3 IPOG-C Example

We again use the example SUT used in the AETG example to illustrate how IPOG-C
works.
Suppose we are testing a web-based application on different client platforms to
see whether it can work normally on different system configurations. Possible factors

1 For a brief introduction to CSP and constraint solving, see Sect. 6.1 .