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

necessary to obtain the first set of results. This makes concrete the concepts of
representation, fitness function and search based algorithm (and their operators)
introduced in the previous sections. First, let us clarify what we mean by TCP.
Regression testing is a testing activity that is performed to gain confidence
that the recent modifications to the System Under Test (SUT), e.g. bug patches
or new features, did not interfere with existing functionalities [108]. The simplest
way to ensure this is to execute all available tests; this is often called retest-all
method. However, as the software evolves, the test suite grows too, eventually
making it prohibitively expensive to adopt the retest-all approach. Many tech-
niques have been developed to deal with the cost of regression testing.
Test Case Prioritisation represents a group of techniques that particularly deal
with the permutations of tests in regression test suites [28, 108]. The assumption
behind these techniques is that, because of the limited resources, it may not be
possible to execute the entire regression test suite. The intuition behind Test
Case Prioritisation techniques is that more important tests should be executed
earlier. In the context of regression testing, the 'important' tests are the ones
that detect regression faults. That is, the aim of Test Case Prioritisation is to
maximise earlier fault detection rate . More formally, it is defined as follows:

Test Case Prioritisation Problem

Definition 1.

Given: Atestsuite, T , the set of permutations of T , PT ,andafunctionfrom

PT to real numbers, f : PT → R .

To find T ∈ T )( T ∈ PT )( T = T )[ f ( T )

Problem: PT such that ( ∀ ≥

f ( T )] .

Ideally, the function f should be a mapping from tests to their fault detection
capability. However, whether a test detects some faults or not is only known after
its execution. In practice, a function f that is a surrogate to the fault detection
capability of tests is used. Structural coverage is one of the most popular choices:
the permutation of tests that achieves structural coverage as early as possible is
thought to maximise the chance of early fault detection.

5.1 Representation
At its core, TCP as a search problem is an optimisation in a permutation space
similar to the Travelling Salesman Problem (TSP), for which many advanced
representation schemes have been developed. Here we will focus on the most
basic form of representation. The set of all possible candidate solutions is the set
of all possible permutations of tests in the regression test suite. If the regression
test suite contains n tests, the representation takes the form of a vector with n
elements. For example, Figure 9 shows one possible candidate solution for TCP
with size n , i.e. with a regression test suite that contains 6 tests,

.
Depending on the choice of the search algorithm, the next step is either to
define the neighbouring solutions of a given solution (local search) or to define
the genetic operators (genetic algorithm).

{ t 0 ,...,t 5 }