Other Related Topics - Automatic Generation of Combinatorial Test Data - page 84

software debugging has two steps: the first step is to find the location of the cause of
the bug, which is called fault localization , and the second step is to modify the code
to eliminate the bug, which is called bug fixing . Fault localization often costs much
time during debugging.
Unlike traditional fault localization, which targets at locating failure causes in
the source code, fault localization based on combinatorial testing aims at locating
failure-causing parameter combinations (also called faulty combinations ). Since CT
is a black-box testing technique, we usually have the SUT model only, without the
source code. But finding the faulty combinations can still provide useful information
for locating the root cause inside the SUT.
Colbourn and McClary, as well as Martínez et al. proposed to construct special-
purpose covering arrays (such as error locating arrays [ 11 , 12 ], locating and detect-
ing arrays [ 13 ]) to identify the faulty combinations according to the test execution
results. These covering arrays have fault localization abilities themselves, so that we
can deduce the possible faulty combinations from the execution results. However,
such arrays are often quite large.
An effective class of methods for fault localization uses adaptive testing, which
generates and executes a set of additional test cases to provide more information
for locating the fault, where the generation of additional test cases is based on the
execution results of the previous test cases. Some algorithms start by analyzing
the execution results of the test suite, and maintain a set of suspicious parameter
combinations [ 14 - 16 ]. Then, they iteratively generate and execute several sets of
additional test cases to narrow down the set of suspicious parameter combinations,
until the faulty combinations are finally located. Some other algorithms start from a
single failing test case, and then generate and execute some additional test cases to
locate the faulty combinations in the failing test case [ 17 - 20 ]. The key observation
of these algorithms is that if test case T 1 fails and T 2 passes, the non-overlapping
part of T 1 and T 2 must contain some parameters of some faulty combination; and
if both T 1 and T 2 fail, the overlapping part of T 1 and T 2 must contain a faulty
combination.
Another category of CT-based fault localization methods is to analyze the exe-
cution results of the covering array. Intuitively, if most of the test cases containing
a certain combination fail, this combination will be very likely to cause the failure.
Classification tree [ 21 ] or SAT solving/optimization techniques [ 22 ] can be applied
to find these combinations, given a set of execution results. Experimental results
show that, when the size of the test suite is small, many possible faulty combinations
will be found, and it is difficult to pinpoint the cause of the defects. The smallest
test suite is not always the best for locating faults. Thus, it is necessary “to make a
balance between reducing the size of the test suite and increasing the ability of fault
localization” [ 22 ].