![](https://csdnimg.cn/release/download_crawler_static/11286886/bgb.jpg)
5 Getting The First Result: A Simple Example for Regression Testing
This section presents an application of a search-based approach to the Test Case Prioritisation
(TCP) in regression testing, illustrating the steps that are 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 techniques have
been developed to deal with the cost of regression testing.
Test Case Prioritisation represents a group of techniques that particularly deal with the permu-
tations 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:
Definition 1 Test Case Prioritisation Problem
Given: a test suite, T , the set of permutations of T , P T , and a function from P T to real numbers,
f : P T → R.
Problem: to find T
0
∈ P T such that (∀T
00
)(T
00
∈ P T )(T
00
6= T
0
)[f(T
0
) ≥ f(T
00
)].
Ideally, the function f should be a mapping from tests to their fault detection capability. How-
ever, 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, {t
0
, . . . , t
5
}.
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).