Information Technology Reference
In-Depth Information
hitting set of T i s. Furthermore, in order to maximise the effect of minimisation,
T should be the minimal hitting set of T i s. The minimal hitting-set problem
is an NP-complete problem as is the dual problem of the minimal set cover
problem [34].
The NP-hardness of the problem encouraged the use of heuristics and
meta-heuristics. The greedy approach [74] as well as other heuristics for min-
imal hitting set and set cover problem [20, 53] have been applied to test suite
minimisation but these approaches were not cost-cognisant and only dealt with a
single objective (test coverage). With the single-objective problem formulation,
the solution to the test suite minimisation problem is one subset of test cases
that maximises the test coverage with minimum redundancy.
Later, the problem was reformulated as a multi-objective optimisation prob-
lem [106]. Since the greedy algorithm does not cope with multiple objectives very
well, Multi-Objective Evolutionary Algorithms (MOEAs) have been applied to
the multi-objective formulation of the test suite minimisation [63, 106]. The
case study presents the multi-objective formulation of test suite minimisation
introduced by Yoo and Harman [106].
Representation. Test suite minimisation is at its core a set-cover problem; the
main decision is whether to include a specific test into the minimised subset or
not. Therefore, we use the binary string representation. For a test suite with n
tests,
, the representation is a binary string of length n :the i -th digit
is 1 if t i is to be included in the subset and 0 otherwise. Binary tournament
selection, single-point crossover and single bit-flip mutation genetic operators
were used for MOEAs.
{
t 1 ,...,t n }
Fitness Function. Three different objectives were considered: structural cov-
erage, fault history coverage and execution cost. Structural coverage of a given
candidate solution is simply the structural coverage achieved collectively by all
the tests that are selected by the candidate solution (i.e. their corresponding bits
are set to 1). This information is often available from the previous iteration of
regression testing. This objective is to be maximised.
Fault history coverage is included to compliment structural coverage metric
because achieving coverage may not always increase fault detection capability.
We collect all known previous faults and calculate fault coverage for each can-
didate solution by counting how many of the previous faults could have been
detected by the candidate solution. The underlying assumption is that a test
that has detected faults in the past may have a higher chance of detecting faults
in the new version. This objective is to be maximised.
The final objective is execution cost. Without considering the cost, the sim-
plest way to maximise the other two objectives is to select the entire test suite.
By trying to optimise for the cost, it is possible to obtain the trade-off between
structural/fault history coverage and the cost of achieving them. The execution
cost of each test is measured using a widely-used profiling tool called valgrind .
 
Search WWH ::




Custom Search