Search Based Software Engineering: Techniques, Taxonomy, Tutorial - Empirical Software Engineering and Verification - page 23

8.1 Case Study: Multi-objective Test Suite Minimisation

Let us consider another class of regression testing techniques that is different
from Test Case Prioritisation studied in Section 5: test suite minimisation. Pri-
oritisation techniques aim to generate an ideal test execution order; minimisation
techniques aim to reduce the size of the regression test suite when the regression
test suite of an existing software system grows to such an extent that it may no
longer be feasible to execute the entire test suite [80]. In order to reduce the size
of the test suite, any redundant test cases in the test suite need to be identified
and removed.
Regression Testing requires optimisation because of the problem posed by
large data sets. That is, organisations with good testing policies quickly accrue
large pools of test data. For example, one of the regression test suites studied
in this paper is also used for a smoke-test by IBM for one of its middleware
products and takes over 4 hours if executed in its entirety. However, a typical
smoke-test can be allocated only 1 hour maximum, forcing the engineer either
to select a set of test cases from the available pool or to prioritise the order in
which the test cases are considered.
The cost of this selection or prioritisation may not be amortised if the engineer
wants to apply the process with every iteration in order to reflect the most
recent test history or to use the whole test suite more evenly. However, without
optimisation, the engineer will simply run out of time to complete the task. As a
result, the engineer may have failed to execute the most optimal set of test cases
when time runs out, reducing fault detection capabilities and thereby harming
the effectiveness of the smoke test.
One widely accepted criterion for redundancy is defined in relation to the
coverage achieved by test cases [16, 20, 53, 74, 81]. If the test coverage achieved
by test case t 1 is a subset of the test coverage achieved by test case t 2 ,itcan
be said that the execution of t 1 is redundant as long as t 2 is also executed. The
aim of test suite minimisation is to obtain the smallest subset of test cases that
are not redundant with respect to a set of test requirements. More formally, test
suite minimisation problem can be defined as follows [108]:

Test Suite Minimisation Problem

Definition 2.

Given:

Atestsuiteof n tests, T ,asetof m test goals

{ r 1 ,...,r m }

, that must
be satisfied to provide the desired 'adequate' testing of the program, and subsets
of T , T i s, one associated with each of the r i s such that any one of the test cases
t j belonging to T i can be used to achieve requirement r i .

Find a representative set, T , of test cases from T that satisfies

Problem:

all r i s.

The testing criterion is satisfied when every test-case requirement in r 1 ,...,r m }

is satisfied. A test-case requirement, r i , is satisfied by any test case, t j ,that
belongs to T i , a subset of T . Therefore, the representative set of test cases is the

{