# On the Interaction between Test-Suite Reduction and Regression-Test
Selection Strategies

Sebastian Ruland  Technical University Darmstadt, Darmstadt, Germany  Malte
Lochau  University of Siegen, Siegen, Germany

###### Abstract

Unit testing is one of the most established quality-assurance techniques for
software development. One major advantage of unit testing is the adjustable
trade-off between efficiency (i.e., testing effort) and effectiveness (i.e.,
fault-detection probability). To this end, various strategies have been
proposed to exploit this trade-off. In particular, test-suite reduction (TSR)
reduces the number of (presumably redundant) test cases while testing a single
program version. Regression-test selection (RTS) selects test cases for
testing consecutive program revisions. However, both TSR and RTS may
influence—or even obstruct— each others’ performance when used in combination.
For instance, test cases discarded during TSR for a particular program version
may become relevant again for RTS. However, finding a combination of both
strategies leading to a reasonable trade-off throughout the version history of
a program is an open question. The goal of this paper is to gain a better
understanding of the interactions between TSR and RTS with respect to
efficiency and effectiveness. To this end, we present a configurable framework
called RegreTS for automated unit-testing of C programs. The framework
comprises different strategies for TSR and RTS and possible combinations
thereof. We apply this framework to a collection of subject systems,
delivering several crucial insights. First, TSR has almost always a negative
impact on the effectiveness of RTS, yet a positive impact on efficiency.
Second, test cases revealing to testers the effect of program modifications
between consecutive program versions are far more effective than test cases
simply covering modified code parts, yet causing much more testing effort.

##  1 Introduction

##### Background and Motivation.

Software testing is concerned with revealing as many bugs as possible in a
program within a—usually strictly limited—amount of time [1]. In particular,
_unit testing_ is one of the most important innovations in the recent past for
pro-actively ensuring software quality in an effective, yet tractable and
agile manner. Bugs revealed by unit tests include program crashes caused by
programming errors as well as faulty input-output value pairs contradicting a
given specification of the expected behavior (e.g., functionally incorrect
program logics or ambiguous requirements). To this end, _test cases_ are
defined in terms of exemplary input values and expected output values for
experimentally executing the program unit under test in a systematic manner.

One advantage of software testing as compared to other quality-assurance
techniques is the—more or less—freely adjustable trade-off between two
(generally conflicting) optimization goals, namely _effectiveness_ (i.e.,
maximizing fault-detection probability) and _efficiency_ (minimizing testing
effort) [2, 3, 4]. In an idealistic setting, a perfect trade-off between both
goals would be a test suite that finds _all_ bugs with _minimum_ effort (e.g.,
requiring a minimum number of test cases). In reality, however, the number and
exact location of bugs are, unfortunately, a-priori unknown; and even if all
bugs would be known in advance (which would make testing obsolete), then
finding a minimum set of test cases for revealing them is NP-hard [5]. Various
_heuristics_ have been proposed to control the selection of sufficiently
effective, yet efficient sets of test cases for a program unit under test.
Heuristics for measuring effectiveness often rely on structural _code-coverage
metrics_ (e.g., branch coverage) to be optimized by a selected test suite [6],
whereas heuristics for efficiency apply test-suite reduction (TSR) techniques
to decrease the number of _redundant_ test cases, again, with respect to that
given code-coverage criterion [2].

Moreover, modern software development is faced with the challenge of ever-
shortened release cycles leading to increasing frequencies of consecutive
program revisions. The goal of _regression testing_ is to reveal emerging bugs
introduced by erroneous program modifications between subsequent program
versions [2]. RTS strategies define criteria for updating an existing test
suite of a previous program version, by removing outdated test cases, by
keeping still relevant test cases, and by adding further test cases for newly
added functionality. Many RTS and regression-test generation strategies are
further concerned with prioritizing test cases to apply the presumably more
effective test cases first. The aforementioned trade-off between efficiency
and effectiveness is therefore also the primary goal of regression testing,
but now starting from an existing test suite inherited from previous program
revisions.

##### Problem Statement and Research Challenges.

Both _TSR strategies_ for testing a single program version as well as
_regression-testing strategies_ for testing consecutive program revisions are
concerned with the same problem:

> _How to achieve a reasonable trade-off between efficiency and
> effectiveness?_

Nevertheless, both kinds of strategies may potentially influence—or even
obstruct— each other in various ways. For instance, a test case being
considered redundant for one program version (thus being removed during TSR)
may become relevant, again, for later program revisions. As a result,
expensive re-selections of eventually “lost” test cases may become necessary
during regression testing. Hence, excessive TSR, although potentially
improving testing efficiency for one program version, may, eventually, have a
negative impact on regression testing. On the other hand, too reluctant TSR
may lead to an ever-growing test suite thus also increasing test-selection
effort during regression testing. Those subtle interactions between TSR and
regression testing are neither obvious nor fully predictable in advance.
Finding a feasible combination of both strategies yielding a suitable
efficiency/effectiveness trade-off throughout the entire version history of a
program is an open challenge involving further fine-grained details to be
taken into account (e.g., code-coverage criteria, TSR heuristics, RTS criteria
etc.).

##### Contributions.

We present a conceptual framework for an in-depth investigation of
interactions between strategies for TSR and RTS and the resulting impact on
(mutually contradicting) efficiency and effectiveness measures. We focus on
unit testing of C programs and use practically established control-flow
coverage criteria as effectiveness measure for RTS and TSR [4]. As
effectiveness heuristics for RTS, we consider modification-traversing as well
as modification-revealing test cases [2].

In our experimental comparison of the different strategies, we additionally
consider fault-detection rate as a-posteriori effectiveness measure.
Concerning testing efficiency, we measure sizes of test suites (i.e., number
of test cases) as well as the computational effort (i.e., CPU-time) for
(regression) test-case generation and/or selection as well as TSR.

To summarize, we make the following contributions.

  * •

Configurable framework for unit-test generation and selection, integrating
recent TSR strategies, as well as existing and novel RTS strategies.

  * •

Tool support for automatically applying different strategies to a version
history of C program units.

  * •

Experimental evaluation results gained from applying our tool to a collection
of C program units with available version history. The evaluation results show
that:

(1) TSR based on a coverage-based notion of test-case redundancy almost always
decreases effectiveness of RTS, yet obviously having a positive impact on
testing efficiency,

(2) modification-revealing test cases are far more effective than
modification-traversing test cases for RTS, yet modification-revealing test-
case generation requires much more computational effort and

(3) the number of test cases and the number of previous program versions
considered for RTS only has a low impact on the effectiveness of regression
testing.

##### Outline.

The remainder of this paper is structured as follows.

Section 2 contains an overview on the necessary background and terminology
used in the remainder of the paper. We first introduce an illustrative example
to introduce essential notions and concepts and also use this example to
derive the motivation for the methodology proposed in the main part of the
paper.

Section 3 contains a conceptual description of the proposed evaluation
framework for investigating the interaction between TSR and RTS strategies.
After a general overview, the different possible strategies are then described
in more detail using the illustrative example.

Section 4 provides a detailed description of our tool support for the
envisioned methodology together with experimental evaluation results gained
from applying the tool to a collection of subject systems.

Section 5 provides an overview about related work from the fields of
regression testing strategies, automated test-case generation, as well as
related approaches for regression verification.

Section 6 concludes the paper and provides a brief outlook on possible future
work.

##### Verifiability.

To make our results reproducible, we provide the tool implementation and all
experimental results as well as raw data on a supplementary web
page111https://www.es.tu-darmstadt.de/regrets.

##  2 Background and Motivation

We first describe the necessary background for the rest of this paper. We
introduce an illustrative running example by means of a small, evolving C
program unit with corresponding unit test cases. Based on this example, we
describe basic notions of unit testing, test-suite reduction and regression
testing. We conclude by summarizing the research challenges addressed in the
remainder of this paper.

##### Program Units.

Let us consider the sample C program unit in Fig. 1a. This source code 222We
will use the terms program, source code and program unit interchangeably for
convenience constitutes the initial version $P_{0}$ of an evolving program
developed and (re-)tested in an incremental manner. Function find_last
receives as inputs an integer-array x[] and an integer value y and is supposed
to return the index of the _last occurrence_ of the value of y in x[]. The
first element of the array is supposed to carry as meta-information the
_length_ (i.e., the number of elements) of the array. For this reason, the
first element should be ignored during the search for the value of y. The
search itself is supposed to be performed by iterating over the array and by
keeping track of the latest occurrence of y 333Of course, a more reasonable
implementation may perform a reversed iterative search and return the first
occurrence. The purpose of the example is to demonstrate essential testing
concepts in a condensed way thus requiring some simplifications which do,
however, not threaten the validity of the overall approach.. Additionally, the
function should return predefined error codes:

  * •

If the size of the array (i.e., the value of the first element) is less or
equal to zero, the returned error-code is -1.

  * •

If the value of y does not occur in the array, the returned error-code is -2.

⬇ 1 int find_last (int x[], int y) { 2 if(x[0] <= 0) 3 return -1; 4 int last =
-2; 5 for (int i=0; i <= x[0]-2; i++) 6 if (x[i] <= y) 7 last = i; 8 return
last; 9 }

(a) Initial Version $P_{0}$ of a Program Unit

⬇ 5--:for (int i=0; i <= x[0]-2; i++ 5++:for (int i=1; i <= x[0]-2; i++

(b) First Bug Fix

⬇ 1 int find_last (int x[], int y) { 2 if(x[0] <= 0) 3 return -1; 4 int last =
-2; 5 for (int i=1; i <= x[0]-2; i++) 6 if (x[i] <= y) 7 last = i; 8 return
last; 9 }

(c) New Program Version $P_{1}$ After Applying the First Bug Fix

⬇ 5--:for (int i=1; i <= x[0]-2; i++ 5++:for (int i=1; i <= x[0]-1; i++

(d) Second Bug Fix

⬇ 1 int find_last (int x[], int y) { 2 if(x[0] <= 0) 3 return -1; 4 int last =
-2; 5 for (int i=1; i <= x[0]-1; i++) 6 if (x[i] <= y) 7 last = i; 8 return
last; 9 }

(e) New Program Version $P_{2}$ After Applying the Second Bug Fix

⬇ 6--:if (x[i] <= y) 6++:if (x[i] == y)

(f) Third Bug Fix

⬇ 1 int find_last (int x[], int y) { 2 if(x[0] <= 0) 3 return -1; 4 int last =
-2; 5 for (int i=1; i <= x[0]-1; i++) 6 if (x[i] == y) 7 last = i; 8 return
last; 9 }

(g) New Program Version $P_{3}$ After Applying the Third Bug Fix

Figure 1: Program Versions $P_{0}$, $P_{1}$, $P_{2}$ and $P_{3}$ with their
corresponding Bug Fixes

##### Program Bugs.

The initial program version $P_{0}$ in Fig. 1a does, however, not satisfy the
specified functionality as it contains the following three _bugs_.

  1. 1.

_Bug 1_ : The search index starts at $0$, thus incorrectly including the value
of the meta-information into the search (see line 5).

  2. 2.

_Bug 2_ : The search index stops at $x[0]-2$ thus incorrectly excluding the
last element from the search (see line 5).

  3. 3.

_Bug 3_ : The search incorrectly matches all values smaller than, or equal to,
y instead of solely considering values equal to y (see line 6).

To fix those bugs, assume the developer to consecutively creates _program
revisions_ by correcting erroneous code parts.

##### Program Revisions.

Let us assume that three consecutive _revisions_ , $P_{1}$, $P_{2}$ and
$P_{3}$, of the initial program version $P_{0}$ have been created, where
$P_{3}$ finally has all three bugs fixed as described above. A _program
revision_ denotes a _new program version_ as a result of _modifications_ made
to some parts of the previous program version. We represent program revisions
using the established diff-syntax frequently used in patch files. Line numbers
marked with post-fix -- refer to the respective lines in the previous program
version being removed in the new version, and those with post-fix ++ refer to
lines in the new version being added to the previous version:

  * •

_Patch 1_ in Fig. 1b provides a fix for Bug 1.

  * •

_Patch 2_ in Fig. 1d provides a fix for Bug 2.

  * •

_Patch 3_ in Fig. 1f provides a fix for Bug 3.

After the first bug fix, we obtain the improved (yet still faulty) program
version $P_{1}$ (cf. Fig. 1c). The second bug fix to $P_{1}$ (yielding program
version $P_{2}$, cf. Fig. 1e) and the third bug fix to $P_{2}$ finally yield
the bug-free version $P_{3}$ (cf. Fig. 1g). Such an incremental process is
often interleaved by consecutive _unit-testing steps_ to assure correctness of
new versions and/or to reveal further bugs potentially emerging during
revisions.

##### Unit Testing.

Test cases for unit testing by means of program inputs are usually selected
with respect to (structural) _code coverage criteria_. For instance, we
require at least two _different_ test cases for _branch coverage_ of program
version $P_{0}$. First, we require a test case for covering (reaching) the
true-branch of the if-statement in line 2 (i.e., the input-array is empty).
Additionally, we require at least one further test case for covering the
remaining branches as follows.

  * •

The false-branch of the if-statement in line 2 (i.e., requiring the input-
array to have at least one element).

  * •

The true-branch of the for-loop in line 5 (i.e., requiring the input-array to
have at least two elements).

  * •

The false-branch of the for-loop in line 5 (i.e., requiring the input-array to
have at least one element).

  * •

The true-branch of the if-statement in line 6 (i.e., requiring the input-array
to have at least one element being less or equal to y).

  * •

The false-branch of the if-statement in line 6 (i.e., requiring the input-
array to have at least one element not being less or equal to y).

To satisfy branch coverage on $P_{0}$, a developer/tester may select a _test
suite_ consisting of the following two _test cases_ 444More precisely, this
test suite is only able to reach Line 8 due to Bug 3:

  * •

$t_{1}$= (x=[0], y=0),

  * •

$t_{2}$= (x=[3,5,5,3], y=4).

We denote test cases $t$ as collections of input-value assignments (i.e., an
array x and a value for y). Test-case specifications are often further
equipped with the expected output values (i.e., last=-1 for $t_{1}$ and
last=-2 for $t_{2}$). If applied to $P_{0}$, $t_{1}$ would _pass_ , whereas
$t_{2}$ would indeed _fail_ as it produces the erroneous return value 0
instead of the expected value -2. Hence, this test suite, although satisfying
branch coverage, only reveals Bug 1 and Bug 3, but not Bug 2. In contrast, a
test suite containing as test cases:

  * •

$t_{1}$= (x=[0], y=0),

  * •

$t_{3}$= (x=[1,1,1], y=2),

  * •

$t_{4}$= (x=[1,2,2], y=0).

also satisfies branch coverage and reveals Bug 1 and Bug 2, but not Bug 3.
Hence, this test suite is similarly _effective_ as the first (revealing two
out of three bugs), yet being less _efficient_ as it causes more testing
effort due to the additional test-case execution. The test suite:

  * •

$t_{1}$= (x=[0], y=0),

  * •

$t_{2}$= (x=[3,5,5,3], y=4),

  * •

$t_{3}$= (x=[1,1,1], y=2).

satisfies branch coverage and reveals all three bugs, since $t_{2}$ detects
Bug 1 and Bug 3, and $t_{3}$ detects Bug 1 and Bug 2. In contrast, the test
suite

  * •

$t_{1}$= (x=[0], y=0),

  * •

$t_{5}$= (x=[3,1,1,2], y=1).

also satisfies branch coverage, but reveals none of the three bugs, since
$t_{1}$ is unable to reach any bug and the execution of $t_{5}$ (accidentally)
produces a correct output for all versions. These examples illustrate the
well-known dilemma of unit-test selection that (1) adherence to (purely
syntactic) code-coverage criteria does not guarantee effective test-suite
selections [7, 8], and (2) using more test cases does not necessary increase
effectiveness, yet obviously decreases testing efficiency. Concerning (2),
_TSR_ aims at removing redundant test cases from a test suite without
decreasing code coverage [4].

##### Test-Suite Reduction.

Let us now assume that a developer/tester first selects the test cases $t_{1}$
and $t_{2}$ for testing program version $P_{0}$, where $t_{2}$ fails due to
Bugs 1 and 3. After applying the first bug fix to remove Bug 1, the initial
test suite consisting of $t_{1}$ and $t_{2}$ does no more satisfy branch
coverage. This is due to the fact, that after the first bug fix is applied,
the first element (i.e., the meta-information) of the input array is no more
included into the search. As the last element is also not included (due to Bug
2), execution of $t_{2}$ will not enter the true-branch of the if-statement in
line 6, and is, therefore, unable to reach 100% branch coverage. Hence, the
developer/tester has to select a further test case, for instance:

  * •

$t_{6}$= (x=[3,0,1,0], y=0)

to cover the missing branch. Thus, the existing test case $t_{2}$ becomes
_redundant_ and might be removed from the test suite as $t_{1}$ and $t_{6}$
are sufficient for 100% branch coverage.

More generally, _TSR_ is concerned with selecting from an existing set of test
cases a sufficient, yet preferably small number of test cases for a program
under test. Corresponding strategies for TSR have to address several
challenges:

  * •

Finding a _minimal_ set of test cases from an existing test suite satisfying a
given coverage criterion is NP-hard, being reducible to the minimum set-cover
problem [5].

  * •

As illustrated by the running example, defining redundancy of test cases only
with respect to a code-coverage criterion might be misleading thus obstructing
testing effectiveness [7, 8].

A further challenge arises in the context of evolving programs. Let us next
assume that bug fix 2 is applied to remove Bug 2. After that, the new test
case $t_{6}$ is no more able to reveal the remaining Bug 3, as the last
element of the array is equal to $y$ and, therefore, the test output
(accidentally) satisfies the specification. In contrast, the previously
removed test case $t_{2}$ would have revealed Bug 3, since the last element is
smaller than $y$, thus leading to the output of $3$ instead of $-2$. This
example shows that TSR solely based on structural coverage criteria defined on
a current program version might be problematic in case of evolving programs.
Test cases being redundant for a current program version might become relevant
again after a program revision. In particular, _regression testing_ 555The
term regression testing often summarizes a wide range of different disciplines
of testing evolving programs not only including RTS, but also test-case
prioritization, test-history analysis, test-artifact storage etc. We will
focus on to the core problem of selecting test cases for regression testing.
is concerned with selecting a suitable set of test cases after program
revisions [2, 9].

##### Regression Testing.

As illustrated by the previous example, after revealing a bug due to a failed
test-case execution, a developer/tester consecutively creates program
revisions to fix the bugs 666For the sake of clarity, we assume in the
following that the granularity of each individual modification made during a
revision is limited to one particular line of code. However, this assumption
does not possess any threat to the validity of our approach.. After creating a
program revision, the current test suite is re-executed to assure
modifications made during the revision (1) successfully fix a discovered bug
(i.e., test cases previously failing now pass) and (2) do not introduce new
bugs (i.e., test cases previously passing still pass). Those test cases from
the existing test suite should be re-executed investigating program parts
affected by modifications made during the revision. New test cases might be
required to investigate existing and/or newly introduced program parts not yet
and/or no more covered by existing test cases. In both cases, one
distinguishes between _modification-traversing_ test cases and _modification-
revealing_ test cases [2]. Executions of modification-traversing test cases at
least _reach_ a program modification, but may, however, not reveal the
modification to a tester (i.e., the program versions before and after the
revision may produce the same output values for the same test inputs). In
contrast, executions of modification-revealing test cases not only reach a
program modification, but also yield different output values when applied
before and after the revision.

For instance, recall the case in which the initial test suite consisting of
$t_{1}$ and $t_{2}$ is applied to $P_{0}$. As $t_{2}$ fails on $P_{0}$, a
developer might perform the first bug fix, leading to $P_{1}$. Next assume
that $t_{1}$ and $t_{2}$ are simply reused for testing $P_{1}$. Both test
cases would pass now although the second and third bug are still present in
$P_{1}$. This is because $t_{1}$ is unable to reach the bug and $t_{2}$ is
unable to detect the bug as the last element which would reveal Bug 3 is not
included in the search due to Bug 2. The output yielded by $t_{2}$, therefore,
also conforms to the specification. In contrast, selecting $t_{3}$ in addition
to, or instead of, $t_{2}$ would also reveal the second bug on $P_{1}$, thus
enabling the developer to perform a further bug fix leading to $P_{2}$.
However, after this bug fix, $t_{3}$ becomes unable to detect the last bug as
there are no values contained in $x$ having a smaller value than $y$. In
contrast, $t_{2}$ is now able to detect the last bug.

The previous example shows that effectiveness of a test suite not only depends
on the particular test cases, but also on the current program version under
test. Hence, fault-detection probability of test cases may both decay as well
as improve over time.

To generalize, _RTS_ is concerned with selecting a sufficient, yet preferably
small number of existing/new test cases to be (re-)executed on a revised
program. Strategies for RTS have to address several challenges:

  * •

Finding a _minimal_ modification-traversing set of test cases from an existing
test suite is NP-hard and does, by definition, not guarantee effective
assurance of program revisions.

  * •

Finding _any_ modification-revealing test case for a program modification
corresponds to the program-equivalence problem which is undecidable.

  * •

In a practical setting, the aforementioned idealized assumptions on program
revisions do usually not hold: units may contain several bugs which influence
or even obfuscate each other and not all modifications applied during a
program revision are actually bug fixes.

##### Test-Suite Reduction vs. Regression-Test Selection

Both techniques aim at _improving testing efficiency_ by reducing the number
of test cases to be executed without presumably harming effectiveness:

  * •

TSR strategies aim at selecting from an existing test suite of one program
version a presumably small subset being sufficient to satisfy the given code-
coverage criterion.

  * •

RTS strategies aim at selecting from an existing test suite of previous
program versions and/or new test cases a presumably small subset being
sufficient to traverse/reveal critical program modifications in the current
program revision.

The previous examples illustrate the subtle interplay between both strategies
affecting efficiency and effectiveness in non-obvious ways:

  * •

Removing too few test cases during TSR might obstruct the gain in efficiency
of subsequent RTS as well as TSR steps due to critically increasing overhead
required for those strategies in case of ever-growing test suites.

  * •

Removing too many test cases during TSR might obstruct effectiveness of
subsequent RTS as well as TSR steps as currently redundant test cases might
become relevant again.

We next present a novel evaluation framework to systematically investigate
these interactions.

##  3 Evaluation Methodology

We present a configurable framework for systematically addressing the
challenges described in the previous section. The methodology allows us to
evaluate interactions between different strategies for TSR and RTS with
respect to practical efficiency and effectiveness measures. We first present a
conceptual overview and then describe the provided parameters for adjusting
the strategies.

###  3.1 Overview

Figure 2 provides an overview of our methodology using the running example
introduced in the previous section.

Figure 2: Overview of the Evaluation Methodology

Starting from the initial program version $P_{0}$, the subsequent program
versions, $P_{1},P_{2},\allowbreak P_{3},\ldots$, result from applying
consecutive revisions, given as patches $\textit{Patch}_{1}$,
$\textit{Patch}_{2}$, $\textit{Patch}_{3}$. For each program version $P_{i}$,
we consider a corresponding test suite $T_{i}$ containing the test cases
selected for this particular program version. Based on the initial test suite
$T_{0}$ created for $P_{0}$ (e.g., using either a coverage criterion like
branch coverage, or randomly generated test cases, or other criteria), the
regression test suites $T_{i}$ for testing subsequent program versions
$P_{i}$, $i>0$, result from applying a RTS strategy. As a complementing step,
a TSR strategy may be applied to test suites $T_{i}$ of program versions
$P_{i}$ to remove redundant test cases.

Our methodology comprises strategies for both _TSR_ as well as _RTS_. The
parameters for fine-tuning the strategies are denoted as circled numbers in
Fig. 2. We briefly describe these parameters which will be explained in more
detail below.

  1. \raisebox{-.5pt} {\small\arabicenumi}⃝

Reduction Strategy (RS): Technique used for TSR. Possible strategies: None,
ILP, FAST++, and DIFF.

  2. \raisebox{-.5pt} {\small\arabicenumi}⃝

Regression Test-Case Selection Criterion (RTC): New regression test cases for
a program version $P_{i}$ may be added to test suite $T_{i}$ either by means
of modification-traversing test cases (i.e., at least reaching the lines of
code modified from $P_{i-1}$ to $P_{i}$) or by modification-revealing test
cases (i.e., yielding different outputs if applied to $P_{i}$ and $P_{i-1}$).

  3. \raisebox{-.5pt} {\small\arabicenumi}⃝

Number of Regression Test Cases (NRT): The number of _different_ regression
test cases added into $T_{i}$ satisfying RTC for _each_ previous program
version $T_{j}$, $0\leq j<i$.

  4. \raisebox{-.5pt} {\small\arabicenumi}⃝

Number of Previous Program Revisions (NPR): The (maximum) number of previous
program versions $P_{j}$ ($i-\textbf{NPR}\leq j<i$) for all of which NRT
different test cases satisfying RTC are added to $T_{i}$.

  5. \raisebox{-.5pt} {\small\arabicenumi}⃝

Continuous Reduction (CR): Controls whether the non-reduced test suite
$T_{i-1}$ (No-CR) or the reduced test suite $T_{i-1}^{\prime}$ (CR) of the
previous program $P_{i-1}$ version is (re-)used for the next program version
$P_{i}$ or if the previous test cases are ignored (None). This test suite is
extended by new test cases according to the previously described parameters.

Note that parameter CR can be applied for all test suites of all versions.
However, for clarity and space reasons, it is only depicted from program
version $P_{2}$ on in Fig. 2.

###  3.2 Test-Suite Reduction Strategies

We now describe the different TSR strategies supported by our framework. We,
again, use an illustrative example to explain the impact of the strategies on
the trade-off between precision and computational effort. We first give a
general characterization of the _test-suite minimization problem_ for one
single program $P$, a given test suite $T$ and a code-coverage criterion on
$P$ [4].

Input: Program $P$, Test Suite $T$, where

  * •

$P$ contains of a set of test goals $G=\\{g_{1},g_{2},\ldots,g_{n}\\}$
according to the given code-coverage criterion and

  * •

test suite $T={t_{1},t_{2},\ldots,t_{n}}$ consists of a set of test cases,
where each $t_{j}\in T$ covers a subset $G_{j}\subseteq G$ of test goals on
$P$ such that for each $g_{i}\in G$ there exists at least one test case
$t_{j}\in T$ with $g_{i}\in G_{j}$ 777Set $G$ actually contains the subsets of
test goals covered by at least one test case in $T$..

Output: Minimal Test Suite $T^{\prime}\subseteq T$, where

  * •

for each $g_{i}\in G$ there exists at least one test case $t_{j}\in
T^{\prime}$ with $g_{i}\in G_{j}$ and

  * •

for each $T^{\prime\prime}\subseteq T$ also satisfying the first property, it
holds that $|T^{\prime}|\leq|T^{\prime\prime}|$.

The test-suite minimization problem is NP-hard being reducible to the minimum
set cover problem [4] such that finding exact minimal solutions is
computational infeasible for realistic programs. Various _TSR_ heuristics have
been proposed for approximating minimal test suites constituting different
trade-offs between precision (deviation from exact solutions) and
computational effort for performing the reduction.

To illustrate the different approaches in our framework, $P_{1}$ from our
running example together with $\textit{T}_{3}$ containing four test cases
selected for branch coverage:

  * •

$t_{1}$= (x=[0], y=0),

  * •

$t_{2}$= (x=[3,5,5,3], y=4),

  * •

$t_{3}$= (x=[1,1,1], y=2), and

  * •

$t_{4}$= (x=[1,2,2], y=0).

Figure 3 (on the left) illustrates the test-suite minimization problem.

Figure 3: Comparision of Test-Suite Reduction Strategies

Program version $P_{1}$ contains three conditional branches (i.e., if-
statement in line 2, loop-head in line 6 and if-statement in line 7), leading
to six goals $G=\\{g_{1},g_{2},\ldots,g_{6}\\}$. A line between test case
$t_{i}$ and test goal $g_{j}$ indicates that $g_{j}\in G_{i}$ (i.e., $t_{i}$
satisfies $g_{j}$). Test suite $T_{3}$ indeed satisfies branch coverage on
$P_{1}$ as for each $g\in G$, there is at least one test case in $T_{3}$.
However, $T_{3}$ is not _minimal_ as, for instance, $t_{2}$ and $t_{4}$ cover
exactly the same test goals, $g_{2},g_{3},g_{4}$ and $g_{6}$, and this set is
further subsumed by the test goals satisfied by $t_{3}$. In fact, $t_{3}$ is
the only test case covering $g_{5}$ and $t_{1}$ is also indispensable as it is
the only test case satisfying $g_{1}$. Hence, $T_{3}=\\{t_{1},t_{3}\\}$ is the
(unique) _minimal_ test suite as shown on the left.

Computing the minimal test suite requires, in the worst case, to enumerate all
$2^{|T|}$ subsets of $T$ which is infeasible in case of realistic programs.
Practical approaches usually compute _reduced_ test suites approximating the
minimal solution. We now describe the strategies considered in our framework.

##### ILP Strategy.

The test-suite minimization problem can be encoded as Integer linear
optimization problem which can be precisely solved using Integer Linear
Programming (ILP) solvers [5]. Our ILP encoding uses for each test case
$t_{i}\in T$ a decision variable $x_{i}$ either having value $1$ if $t_{i}$ is
selected, or value $0$ if $t_{i}$ is not selected. The ILP formula contains
for each test goal $g_{j}\in G$ a clause building the sum of the decision
variables $x_{i}$ of all test cases $t_{i}\in T$ for which $g_{j}\in G_{i}$
holds. By requiring the value of each such sum to be greater than $0$, we
ensure each test goal to be covered by the minimal test suite. To enforce
minimality, the overall optimization objective is to minimize the sum over all
values of decision variables $x_{i}$.

Applied to our example, this encoding introduces the variables
$x_{1},x_{2},x_{3},x_{3}$ for the test cases in $T$ and adds the following
clauses for the test goals:

$\displaystyle x_{1}$ $\displaystyle>=1$ (1) $\displaystyle x_{2}+x_{3}+x_{4}$
$\displaystyle>=1$ (2) $\displaystyle x_{2}+x_{3}+x_{4}$ $\displaystyle>=1$
(3) $\displaystyle x_{2}+x_{3}+x_{4}$ $\displaystyle>=1$ (4) $\displaystyle
x_{3}$ $\displaystyle>=1$ (5) $\displaystyle x_{2}+x_{3}+x_{4}$
$\displaystyle>=1$ (6)

The optimization objectives is defined as:

$\textit{min}(x_{1}+x_{2}+x_{3}+x_{4})\text{.}$

As illustrated in Fig.3, recent ILP solvers are able to deliver an exact
minimal solution. However, large amount of test cases naturally lead to high
computational effort. We discuss two TSR heuristics to avoid intractable
computational effort in case of larger-scaled problems, yet providing an
acceptable approximation of the exact (minimal) solution.

##### FAST++ Strategy.

The FAST++ approach encodes the selection of test cases into a (reduced) test
suite using the Euclidean distance of a reduced vector-space model computed by
random projection [10]. We also illustrate this approach using our example.
Test cases are encoded as vectors, where the number of elements corresponds to
the number of different input values of all test cases. The first element of
each vector denotes the number of occurrences of the lowest input value (e.g.,
for our running example the number ’0’). The next element of each vector is
the next lowest input value (e.g., for our running example the number ’1’).
The encoding of all test cases is shown in Tab. 1 and the result of reducing
the dimensions of the vector-space model by random projection is shown in Tab.
2.

Table 1: Vector Encoding of Test Cases Test Case \ Value | 0 | 1 | 2 | 3 | 5 | 6
---|---|---|---|---|---|---
($t_{1}$) | 2 | 0 | 0 | 0 | 0 | 0
($t_{2}$) | 0 | 0 | 0 | 2 | 1 | 2
($t_{3}$) | 0 | 3 | 1 | 0 | 0 | 0
($t_{4}$) | 1 | 1 | 2 | 0 | 0 | 0
Table 2: Vector Encoding of Test Cases after Random Projection Test Case \ Value | x | y | z
---|---|---|---
($t_{1}$) | 0 | 0 | 0
($t_{2}$) | 0 | 0 | 5
($t_{3}$) | 0 | 3 | 2
($t_{4}$) | 0 | 2 | 0

Based on this encoding, TSR works as follows. First, a random test case (e.g.,
$t_{2}$) is selected into the (initially empty) reduced test suite. For the
selected test case, the Euclidean distances to all other remaining test cases
is computed based on the reduced vector-space model. The probability of
selecting a particular remaining test case next into the reduced test suite
increases with the distance value (thus preferring test cases covering test
goals being dissimilar to those covered by previously selected ones). In our
example, this would be, for instance, test case $t_{1}$. This iterative step
is repeated until all test goals are covered. For instance, the next test case
might be $t_{3}$ which suffices to achieve full branch coverage thus leading
to termination. This technique is, on average, more efficient than ILP, yet
potentially leading to less precise results as demonstrated by the example.
There is not even a guarantee to find local optima as random projection may
obfuscate necessary information. Additionally, the ordering of input values is
ignored.

##### DIFF Strategy.

This strategy also incrementally selects test cases until all test goals are
covered [11]. In contrast to FAST++, DIFF is a purely greedy-based approach
which always selects as next test case one that covers a maximum number of
uncovered test goals. Applied to our example, DIFF would, for instance,
perform the following selections:

  1. 1.

$t_{3}$ (covering 5 uncovered test goals),

  2. 2.

$t_{1}$ (covering 1 uncovered test goal).

This technique is, in general, similarly efficient and (im-)precise as FAST++,
where this particular example is well-suited for DIFF as the local optimum is
the same as the global one. However, if local and global optima differ, there
is no guarantee about the optimality of the result.

The different TSR technique might lead to different results in terms of the
number of test cases of the reduced test suite. Although, this clearly leads
to different results in terms of efficiency (in terms of test-suite size) it
also might affect effectiveness. For example, test case $t_{2}$ does not cover
additional test goals and also does not detect any bugs in program version
$P_{1}$. However, in program version $P_{2}$ it will again detect Bug 3. We
chose those three TSR strategies as they provide different trade-offs between
the effectiveness of reduction (i.e., how small the resulting test-suite will
be) and efficiency in terms of CPU time needed for reduction. [10, 12] Since
ILP provides an optimal solution, the resulting test-suite will be minimal,
however, leading to much more computational effort. The greedy approach (DIFF)
is more efficient, however, the resulting test-suite might be larger compared
to ILP. FAST++ is even more efficient compared to the greedy approach,
however, leading to to even larger test-suites.

###  3.3 Regression-Test Selection Strategies

The TSR strategies considered so far are concerned with selecting from an
_existing test suite of one single program version_ a reduced subset
preserving test coverage on that program version. In contrast, RTS strategies
are concerned with selecting from an _existing test suite of a previous
program version_ a sufficient set of test cases to investigate modifications
applied to that program version leading to a subsequent version. If no such
test case(s) can be found among the existing ones, new test cases must be
created and added to the test suite of the subsequent program version. We next
describe different RTS strategies supported by our framework. We use an
illustrative example to explain the impact of the strategies on the trade-offs
between precision and computational effort. We start with a general
characterization of the _regression-test selection problem_ , consisting of a
program version $P$ with existing test suite $T$ and subsequent version
$P^{\prime}$ for which a regression test suite $T^{\prime}$ is created [2].

Input: Program version $P_{i-1}$ with Test Suite $T_{i-1}$ and subsequent
program version $P_{i}$.

Output: Regression Test Suite $T_{i}=T_{i-1}^{\prime}\cup T_{i}^{\prime}$,
where $T_{i-1}^{\prime}\subseteq T_{i-1}$ are existing test cases selected for
reuse from $T_{i-1}$ and $T_{i}^{\prime}$ are newly added test cases.

Consider $P_{3}$ from our running example together with test suite
$\textit{T}_{3}$. Figure 4 provides an illustration of the RTS problem.

Figure 4: Comparison of Regression-Test Selection Strategies

For $P_{3}$, the selected test suite contains three modification-traversing
test cases (i.e., $t_{2}$, $t_{3}$ and $t_{4}$) being able to at least
_traverse_ the modified line of code. However, only $t_{2}$ is _modification
revealing_ as it not only reaches the modification, but also disposes a
difference in the output behavior of $P_{3}$ as compared to $P_{2}$. Hence,
depending on the RTS strategy, also new test cases have to be generated for
$T_{i}^{\prime}$.

##### Regression-Test-Case Generation.

We now describe how we automatically generate regression test cases utilizing
off-the-shelf test-generation tools originally designed for covering test
goals encoded as reachability properties. We utilize a software model-checker
for C programs to automatically derive test cases from counterexamples for
(non-) reachability queries of test goals [13]. We encode the problem of
generating regression test cases for different versions of a program in a
generic comparator-function. The shape of the comparator-function $P_{i,j}$
for the program versions $P_{i}$ and $P_{j}$ depends on parameter RTC. We
illustrate this using the comparator-function $P_{2,3}$ for our running
example.

⬇ 1 int find_last_p2_3(int x[], int y) { 2 if(x[0] <= 0) 3 return -1; 4 5 int
last = -2; 6 for (int i=1; i <= x[0]-1; i++) { 7 test_goal: 8 if (x[i] == y) 9
last = i; 10 } 11 return last; 12 }

(a) Modification-Traversing Comparator-Function for $P_{2}$ and $P_{3}$

⬇ void find_last_p2_3(int x[], int y){ if(find_last_p2(x,y) !=
find_last_p3(x,y) test_goal:printf("differencing␣test␣case␣found"); }

(b) Modification-Revealing Comparator-Function for $P_{2}$ and $P_{3}$

Figure 5: Comparator-Functions

  * •

$\textbf{RTC}=\textbf{MT}$: The comparator-function $P_{2,3}$ for generating
_modification-traversing_ test cases between $P_{2}$ and $P_{3}$ is shown in
Figure 5a. The program location affected by the program modification leading
from $P_{2}$ to $P_{3}$ is marked by a special program label test_goal. A
test-case generator can be used to generate a program input reaching this
program label (and therefore at least _traversing_ this modification).

  * •

$\textbf{RTC}=\textbf{MR}$: The comparator-program $P_{2,3}$ for generating
_modification-revealing_ test cases between $P_{2}$ and $P_{3}$ is shown in
Fig. 5b. Here, the program input is delegated to $P_{2}$ and $P_{3}$ and the
output is compared by an equals-function (or != in case of basic types) based
on the return-type. Hence, the special program label test_goal in line 3 is
only reachable by a test case if the test input generated by a test-case
generator yields different output values for $P_{2}$ and $P_{3}$ (thus not
only reaching, but also _revealing_ this modification).

##### Remarks.

The problem of generating modification-revealing test cases obviously subsumes
the generation of modification-traversing test cases and therefore,
presumably, causes (much) more computational effort. In fact, _both_ problems
are undecidable as reachability of program locations is reducible to the
halting problem. Hence, the test-generation approach described above is
inherently incomplete 888 This fact, however, is already true for the problem
of generating a test case simply reaching a test goal in one version of a
program in a non-regression scenario.. Our framework further comprises the
parameter NRT to control the number of _multiple different test cases_
distinguishing the output behavior of two consecutive program versions (which
may, however, fail due to the theoretical limitations described before).
Lastly, the technique based on the comparator-function suffers from some
technical limitations. For example, if the data type of the return value
changes the comparison of the return values is, in general, no more possible
(see Fig. 6, where the return types of function $find\\_last\\_p3$ and
$find\\_last\\_p4$ differ such that the comparator-program would not compile).
Additionally, as both program versions need to be compiled into one single
program, merging of those versions can become technical challenging (e.g., if
the data type of global variables or functions changes or the members of
structs are modified).

⬇ 1 int find_last_p3 (int x[], int y) {...} 2 struct intStruct find_last_p4
(int x[], int y) {...} 3 4 5 void find_last_p3_4(int x[], int y){ 6
if(find_last_p3(x,y) != find_last_p4(x,y) 7
test_goal:printf("differencing␣test␣case␣found"); 8 }

Figure 6: Invalid Comparator Program

##### Multiple Regression Test-Case Generation.

Most test-case generators transform the input program into an intermediate
representation like a control-flow automaton (CFA). To keep the following
examples graspable, we use the basic example shown in Figure 7a instead of our
running example.

(a) Original CFA

(b) Instrumented CFA

Figure 7: On-the-fly CFA Instrumentation

This CFA corresponds to a small program with input value x returning 0 if x is
smaller than zero and the value of x, otherwise. A CFA can be used to identify
all program paths leading to test goals (e.g., all CFA-edges in case of branch
coverage) and to control automated test-suite generation by performing
reachability queries for uncovered test goal [14]. To support parameter NRT,
we have to generate _multiple different_ test cases reaching the same test
goal (i.e., a modified program location). We start by generating the first
test case based on the original CFA. For instance, to generate a test case
reaching the return-edge in Fig. 7a, any input is feasible (e.g., input -5
would traverse the left path). For further test cases reaching the return-
edge, we modify the CFA as shown in Fig. 7b to exclude already covered paths.
For this, we add for each path for which we already created a test case a
fresh variable with initial value 0 (i.e., variable w1 introduced by the new
edge from node 2 to e1). We assign value 1 to this variable after traversing
the associated branch of the path (i.e., the new edge from node 4 to e2). By
further requiring the value of at least one of the fresh variables before
reaching the test goal must not be 1 (i.e., the new edge from node 6 to e3),
we exclude all previous test cases reaching that test goal. In the example,
assumption w1!=1 enforces a further test case to assign a positive value to x,
whereas a third run of the test-case generator will find no further path
reaching this goal.

For example, to generate two test cases reaching line 7 in program version
$P_{3}$, we first generate a test case as usual (e.g., $t_{7}$= (x=[1,0],
y=1)). For the second test case, we introduce a fresh variable into the CFA
which is incremented when traversing a branch of the path already taken by the
previous test case (i.e., the true-branch of the if-statement, the true-branch
of the for-loop, the false-branch of the for-loop and the false-branch of the
last if-statement). As there are four branches, the final check will ascertain
that the fresh variable is not equal to $4$. When iterating through the for-
loop more than once (as opposed to the first test case) or taking the true-
branch of the last if-statement, the value will differ from $4$ and,
therefore, the path can be taken for a further test case being different from
all previous ones (e.g., $t_{8}$= (x=[2,0,0], y=1)).

##### Remarks.

Again, this methodology is _inherently incomplete_ as it is unknown whether
further test cases exist if no more test cases are found by the test-case
generator (e.g., due to time-outs). In addition, each incrementally added
fresh variable presumably increases program complexity thus potentially
increasing the computational effort required for every further test case.

##### Regression Test-Suite Generation.

We conclude by summarizing the description of our framework. Algorithm 1
depicts a generic procedure for generating regression test suites $T_{i}$ for
program version $P_{i}$ meeting all possible instantiations of the parameters
RTC, NRT, NPR, RS and CR.

1:$\textbf{RTC}\in\\{\textit{MT},\textit{MR}\\}$,
$\textbf{NRT}\in\mathbb{N}^{+}$, $\textbf{NPR}\in\\{1,\ldots,i\\}$

2:$P_{i}$, $\textit{Patch}_{1},\ldots,\textit{Patch}_{i}$

3:$T_{i-1}$

4:$T_{i}$

5:procedureMain

6:$T_{i}\leftarrow T_{i-1}(\textbf{CR})$

7:$T_{i,j}\leftarrow\emptyset$

8:$P_{j}\leftarrow P_{i}$

9:for $k=0$ to $\textbf{NPR}-1$ do

10: $P_{j}\leftarrow\textsc{apply}~{}\textit{Patch}_{i-k}^{-1}$ to $P_{j}$

11: $P_{i,j}\leftarrow\textsc{Comparator}\langle
P_{i},P_{j}\rangle(\textbf{RTC})$

12: $l\leftarrow 0$

13: while $l<\textbf{NRT}$ do

14: $t\leftarrow\textsc{NewTestGen}(P_{i,j},T_{i,j})$

15: if $t=\textit{null}$ then

16: continue in line 9

17: end if

18: $T_{i,j}\leftarrow T_{i,j}\cup\\{t\\}$

19: $l\leftarrow l+1$

20: end while

21:end for

22:$T_{i}\leftarrow T_{i}\cup T_{i,j}$

23:$T_{i}\leftarrow\textsc{Reduction}\langle T_{i}\rangle(\textbf{RS})$

Algorithm 1 Regression Test-Suite Generation

Parameter RTC is either set to modification-traversing (MT) or modification-
revealing (MR), whereas NRT and NPR can be any number greater than zero (NPR
is naturally restricted to be at most $i$). Besides the current version
$P_{i}$, the algorithm receives as inputs the sequence of patches applied
since version $P_{0}$ as well as the test suite $T_{i-1}$ of the preceding
version $P_{i-1}$ based on parameter CR. Lastly, RS is set to ILP, DIFF,
FAST++ or None.

Test suite $T_{i}$ is initialized with the test cases from the existing test
suite $T_{i-1}$ (line 6), and $P_{j}$ (initialized in line 8 by $P_{i}$)
refers to the previous version for which differentiating test cases are
generated in the next iteration. The outer loop from line 9 to 19 performs a
descending traversal over NPR previous versions by reversely applying the
corresponding patches to $P_{j}$ (i.e., applying Patch${}_{j}^{-1}$ to $P_{j}$
yields version $P_{j-1}$). In line 11, the comparator-function template is
instantiated with $P_{i}$ and $P_{j}$ to synthesize a _comparator_ -function
$P_{i,j}$ as input for a coverage-based test-case generator in line 14 [13].
The inner loop (lines 13–19) repeatedly generates test cases for $P_{i,j}$
until at most NRT different test cases have been generated (cf. Sect. 3.3).
The test-case generator receives as additional input the set $T_{i,j}$ of
already generated test cases. If the test-case generator fails to find further
test cases (either due to a time-out or due to exhaustive search), the current
iteration of the inner loop is terminated and the next iteration of the outer
loop starts (lines 15–16). Otherwise, the new test case is added to $T_{i,j}$
(line 18) and finally to $T_{i}$ (line 22). Finally, the test-suite is reduced
depending on parameter RS in line 23.

##### Remarks.

For generating multiple _different_ test cases for the _same_ modification,
only the set $T_{i,j}$ of already generated differentiating test cases for the
current pair $P_{i}$, $P_{j}$ of program versions is taken into account.
However, the approach may be generalized by blocking the whole set $T_{i}$ of
already generated test cases in subsequent runs of the test-case generator.
This may, however, lead to drastically increased computational effort and is,
therefore, currently not supported.

###  3.4 Integration and Discussion of Strategies

The parameters RS, RTC, NRT, NPR and CR allow for adjustments of efficiency
and effectiveness achievable by a regression-testing strategy concerning the
detection of regression bugs.

##### Efficiency.

Efficiency of regression-testing strategies may be measured in terms of (1)
the computational effort (e.g., CPU time) for selecting/generating regression
test cases, together with (2) the number of regression test cases being
selected. Concerning (1), strategies with $\textbf{RTC}=\textbf{MT}$ are
presumably more efficient than those with $\textbf{RTC}=\textbf{MR}$ as
finding modification-revealing test cases is, on average, computationally more
complicated than only reaching a modified program location. Concerning (2),
the number of regression test cases to be selected for each new program
version is (at most) $\textbf{NRT}\cdot\textbf{NPR}$ thus presumably growing
with increasing values of NRT and NPR. Additionally, strategies with
$\textbf{RS}\neq\textbf{None}$ are presumably less efficient in terms of CPU
time, but presumably much more efficient in terms of the number of test cases.
Finally, CR also presumably decreases efficiency in terms of CPU time, however
presumably increases efficiency in terms of number of test cases.

##### Effectiveness.

Effectiveness of regression-testing strategies may be measured in terms of the
number of regression bugs detected by the selected regression test cases. Test
cases selected for $\textbf{RTC}=\textbf{MR}$ are presumably more effective
than those for $\textbf{RTC}=\textbf{MT}$. Similarly, fault-detection rates of
regression test suites presumably increase with higher values for NRT (i.e.,
leading to more different ways of testing modifications between program
versions) as well as NPR (i.e., taking more previous program versions into
account). For instance, concerning the revision from $P_{2}$ to $P_{3}$ in our
example, revealing bug 3 in $P_{2}$ requires a test case such as $t_{2}$. This
can be ensured by strategies with $\textbf{RTC}=\textbf{MR}$,
$\textbf{NRT}>0$, and $\textbf{NPR}>0$ which are, however, presumably less
efficient than strategies with $\textbf{RTC}=\textbf{MT}$. Finally, RS and CR
might decrease effectiveness as reducing the test suite might remove test
cases that would succeed in finding the bug (see Sect. 3.2).

In the next section, we empirically investigate these assumptions by
presenting the results of an experimental evaluation gained from applying a
tool for our methodology to a collection of subject systems.

##  4 Experimental Evaluation

The configurable framework presented in the previous section allows us to
investigate the impact of the parameters \raisebox{-.5pt}
{\small1}⃝–\raisebox{-.5pt} {\small5}⃝ (see Sect. 3) on efficiency and
effectiveness of regression testing. In our experimental evaluation, we
consider version histories of C program units (i.e., function level). We use
real-world systems obtained from GitHub and the change history provided by
git. To systematically compare effectiveness of different regression-testing
strategies, we further employ simulated bugs throughout program-version
histories and measure the corresponding fault-detection ratio of the selected
test suites. We do this by repeatedly applying standard mutation operators for
C programs. Correspondingly, we measure efficiency in terms of the
computational effort for generating regression test cases as well as in terms
of the number of test cases to be (re-)executed throughout the version
history.

###  4.1 Research Questions

We consider the following research questions.

  * (RQ1)

How does the regression-testing strategy impact testing effectiveness?

  * (RQ2)

How does the regression-testing strategy impact testing efficiency?

  * (RQ3)

Which regression-testing strategy constitutes the best trade-off between
effectiveness and efficiency?

###  4.2 Experimental Setup

We next describe the evaluation methods and experimental design used in our
experiments to address these research questions.

##### Methods and Experimental Design

To compare different strategies for regression-testing, we instantiate the
five parameters RTC, NRT, NPR, RS and CR of our methodology as described in
Sect. 3 as follows:

  * •

$\textbf{RTC}\in\\{\textbf{MT},\textbf{MR}\\}$ (RTS Generation Criterion).

  * •

$\textbf{NRT}\in\\{\textbf{1},\textbf{2},\textbf{3}\\}$ (Number of Regression
Test Cases per Revision).

  * •

$\textbf{NPR}\in\\{\textbf{1},\textbf{2},\textbf{3}\\}$ (Number of Previous
Program Revisions).

  * •

$\textbf{RS}\in\\{\textbf{None},\textbf{ILP},\textbf{FAST++},\textbf{DIFF}\\}$
(TSR Strategy).

  * •

$\textbf{CR}\in\\{\textbf{CR},\textbf{No-CR},\textbf{None}\\}$ (Continuous
Reduction).

To answer RQ1-RQ3, each instantiation of all five parameters, therefore,
corresponds to one particular _regression-testing strategy_ under
consideration, where we denote a strategy by
$[\textbf{RTC},\textbf{NRT},\textbf{NPR},\allowbreak\textbf{RS},\textbf{CR}]$
for short. We thus obtain 144 reasonable regression-testing strategies (since
the combination of $\textbf{RS}=\textbf{None}$ and $\textbf{CR}=\textbf{CR}$
is meaningless and we do not take into account strategies having
$\textbf{CR}=\textbf{None}$ and $\textbf{RS}!=\textbf{None}$ as reduction of
non-accumulated test-suites is also meaningless). Two of these strategies may
be considered as proper _baselines_ :

  * •

Baseline 1 (basic regression testing
strategy):$[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{No-CR}]$.

  * •

Baseline 2 (basic regression testing without initial test
suite):$[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{None}]$.

We limit our considerations to 3 as maximum value for NRT and NPR as the
increase of effectiveness diminishes for higher values of NRT and NPR.
Additionally, we do not consider $0$ as value for NRT and NPR, as this would
obviously result in an empty test-suite.

We further divide RQ2 into the following sub-questions.

  * •

(RQ2.1) How does the regression-testing strategy impact efficiency in terms of
CPU time?

  * •

(RQ2.2) How does the regression-testing strategy impact efficiency in terms of
number of test-cases?

Note that we consider test-case generation time for CPU time and not test-case
execution time. This is due to the fact, that test-case execution time was
negligible during our evaluation.

##### Subject Systems.

We consider program units as our subject systems in terms of _testable
functions_ extracted from real-world C programs for which we further require
available version history. We therefore focus on open-source projects from
GitHub. We selected program units in terms of preprocessed c-files consisting
of an entry-function (i.e., the function-under-test) as well as all functions
within the same compilation unit having (direct or indirect) callee-
dependencies to the function-under-test. To sum up, our subject systems have
to fulfill the following requirements to be useable for our evaluation
purposes.

  * •

The unit must be processable by the test-case generator used in our framework
(e.g., syntax must be ANSI C, no multi-threading, etc.).

  * •

The functions-under-test (as well as all callees) must have undergone a
version-history of at least 3 modifications.

  * •

The signature of the functions-under-test must provide input parameters for
which different values will yield different return values (or affect the
values of at least one global variable). However, this needs not to be known
in advance as the existence of such parameters is actually checked during test
generation (which may timeout if this requirement is not met).

  * •

Calling the function-under-test multiple times with the same parameter values
produces the same return value or global-variable values (i.e., no non-
deterministic behavior or external system-function calls are considered).

The resulting collection of subject systems comprises program units from open-
source projects published in GitHub:

  * •

betaflight999https://github.com/betaflight/betaflight contains six program
units from the flight controller software _betaflight_.

  * •

netdata101010https://github.com/netdata/netdata contains six program units
from the infrastructure monitoring and troubleshooting software _netdata_.

  * •

wrk111111https://github.com/wg/wrk contains one program unit from the HTTP
benchmarking tool _wrk_.

The size of subject systems ranges from 270 to 950 lines of code (after
removing unnecessary code). The number of changes (i.e., commits) for each
subject system is between 4 and 18 (only counting commits changing code inside
the unit).

##### Simulating Bugs.

Although software evolution and regression testing become more and more
important, properly documented and practically usable histories of program
versions combined with information about real bugs in software projects are
still barely available. Hence, for in-depth investigations of the interactions
between program revisions, program bugs and their detection by regression test
cases as required for answering our research questions, we have to rely on
synthetically generated bugs. Mutation testing is a well-established approach
for evaluating effectiveness of testing techniques by simulating common
program faults [15]. In particular, mutation-testing tools provide collections
of syntactic program-transformation operations such that the resulting
modified program potentially shows different (i.e., erroneous) output
behaviors.

Fortunately, it has been recently shown that mutations provide a reliable
substitute for realistic bugs in testing experiments [15]. We, therefore,
utilize concepts from mutation testing to simulate bugs in our subject
systems. Figure 8 provides an overview of our approach. For each program
version other than program version $P_{0}$, we create mutants containing
simulated bugs. The regression-test generation is then executed on this bugged
version and effectiveness of the resulting test suite is measured by executing
the generated/selected regression-test suite on both the bugged and the bug-
fixed (i.e., the original) version and by comparing the return values (see
Sect. 3). If the return values differ, the bug is successfully detected by the
test-suite. We used 62 mutation operators in total (the names of the mutation
operators are provided on our supplementary web page 121212https://www.es.tu-
darmstadt.de/regrets), which can be clustered into three different types. The
first group consists of mutation operators replacing constants and variables
(e.g., replace variable $a$ by variable $b$, replace constant $5$ by constant
$6$ etc.). The second group consists of mutation operators replacing operators
(e.g., replacing $+$ by $-$). The last group consists of mutation operators
replacing pointers and array references (e.g., replacing pointer $pt1$ by
pointer $pt2$).

Figure 8: Bug Simulation using Mutation Testing

##### Data Collection.

For comparing different regression-testing strategies, we first generate a
faulty revisions $B_{i}$ from all revisions $P_{i}$ of each subject system by
simulating bugs as described before. Next, we introduce program labels into
each faulty revision $B_{i}$ marking each line of code which has been modified
since the last version $P_{i-1}$. These labels are used as test goals to
generate modification-traversing test cases (similarly for $P_{i-2}$ and
$P_{i-3}$ depending on parameter NPR). In addition, we generate the
comparator-programs described in Sect. 3 for generating modification-revealing
test-cases. The comparator-program is further used for comparing test-case
executions on the faulty version $B_{i}$ and the previous versions $P_{i-1}$,
$P_{i-2}$ and $P_{i-3}$. If no comparator-program can be created (e.g., due to
the limitations explained in Sect. 3), no test suite will be generated for all
strategies targeting this specific comparator-program.

We applied Algorithm 1 to generate regression-test suites $T_{i}^{s}$ for
every bugged revision $B_{i}$ using all 144 strategies.

To answer RQ1, we measure effectiveness of the generated test suites such that
test suite $T_{i}^{s}$ detects the bug in $B_{i}$ if it contains at least one
test case $t$ whose execution yields different output values when executed on
$P_{i}$ and $B_{i}$ (denoted $P_{i}(tc)\neq B_{i}(tc)$). Hence, effectiveness
with respect to a test suite $T_{i}^{s}$ is calculated as

$\textit{effectiveness}(T_{i}^{s})=\textit{detects}(T_{i}^{s},i)$ (8)

where $\textit{detects}(T_{i}^{s},i)=1$ if $\exists t\in
T_{i}^{s}:P_{i}(t)\neq B_{i}(t)$, or 0 otherwise, and $B_{i}$ is the faulty
revisions generated for $P_{i}$. Effectiveness of a strategy s is calculated
as

$\textit{effectiveness}(s)=\frac{\sum_{i=0}^{n}\textit{effectiveness}(T_{i}^{s})}{n}$
(9)

where $n$ is the number of revisions.

To answer RQ2, we measure efficiency in two ways. First, efficiency of
regression test suites generated by strategy $s$ for program unit $P_{i}$ is
calculated as the average _size_ of test suites $T_{i}^{s}$ in terms of the
number of test cases

$\textit{efficiency}_{\textit{size}}(T_{i}^{s})=|T_{i}^{s}|$ (10)

such that the overall efficiency of strategy s is calculated as

$\textit{efficiency}_{\textit{size}}(s)=\frac{\sum_{i=0}^{n}\textit{efficiency}_{\textit{size}}(T_{i}^{s})}{n}.$
(11)

Second, efficiency of the regression test-suite generation is given as the
aggregated CPU time $\textit{efficiency}_{\textit{CPU}}$ consisting of the
initialization phase of the software model-checker, the reachability analysis,
and the test-case extraction. While the first phase is only executed once for
each program revision under test, the other phases are executed by the number
of test goals multiplied by parameter NRT. Additionally, for practical
reasons, the whole process is limited by a global time-out parameter after
which the process terminates without providing further test cases thus
potentially leading to less test cases than specified by parameter NRT. The
equation for calculating $\textit{efficiency}_{\textit{CPU}}$ of the different
strategies is

$\textit{efficiency}_{\textit{cpu}}(s)=\frac{\sum_{i=0}^{n}\textit{efficiency}_{\textit{cpu}}(T_{i}^{s})}{n}.$
(12)

Finally, to answer RQ3, we calculate the mean values of each strategy for each
program unit in our subject system for effectiveness and efficiency and,
thereupon, calculate the trade-off as

$\textit{trade-
off}(s)=\frac{\textit{effectiveness}(s)}{\textit{efficiency}_{\textit{size}}(s)}.$
(13)

##### Tool Support.

We implemented Algorithm 1 in a tool, called RegreTS (_Regression Testing
Strategies_). RegreTS extends the software model-checker CPAchecker for C
programs to generate regression test cases. This is achieved by performing
reachability-analysis runs for program locations marked as test goals (see
Sect. 3). Additionally, we use MUSIC [16], a mutation tool for C programs, to
generate synthetic bugs as described above. For measuring test coverage, we
utilize TestCov131313https://gitlab.com/sosy-lab/software/test-suite-
validator, a test-suite executor for C programs. TestCov further supports TSR
with a greedy algorithm, as explained in Sect. 3, called DIFF. Furthermore, we
extended TestCov to also support FAST++ and ILP. All tools are available on
our website141414https://www.es.tu-darmstadt.de/regrets.

##### Measurement Setup.

RegreTS as well as MUSIC and TestCov have been executed on an Ubuntu 18.04
machine, equipped with an Intel Core i7-7700k CPU and 64 GB of RAM. The CPU
time for test-suite generation is limited to 900 s per revision, and the CPU
time for the execution of the test cases to detect bugs is limited to 30 s per
test case. The TSR is not limited by CPU time as the CPU time needed for
reduction was negligible. We executed our evaluation with Java 1.8.0-171 and
limited the Java heap to 15 GB.

###  4.3 Results

The measurements for RQ1 are depicted in Fig. 9a for all strategies with
$\textbf{RTC}=\textbf{MR}$ and in Fig. 9b for all strategies with
$\textbf{RTC}=\textbf{MT}$. Results for RQ2 are shown in Figs. 10a and 11a for
all strategies with $\textbf{RTC}=\textbf{MR}$ and Figs. 10b and 11b for all
strategies with $\textbf{RTC}=\textbf{MT}$. The results for RQ3 are shown in
Fig. 12a for all strategies with $\textbf{RTC}=\textbf{MR}$ and Fig. 12b for
all strategies with $\textbf{RTC}=\textbf{MT}$. The box plots in Figs. 10a,
10b, 11a and 11b aggregate the results after applying the formulas 11 and 12
(see above) for all subject systems. The boxes depict the range of results
while the black dashes depict the mean values. The whiskers show the minimum
and maximum values (excluding outliers).

##### RQ1 (Effectiveness).

The best effectiveness for our subject systems is achieved by the strategies
$[\textbf{MR},\textbf{3},\textbf{3},\textbf{None},\allowbreak\textbf{No-CR}]$,
$[\textbf{MR},\textbf{2},\textbf{3},\textbf{None},\allowbreak\textbf{No-CR}]$,
$[\textbf{MR},\textbf{2},\textbf{3},\textbf{None},\\\ \textbf{No-CR}]$,
$[\textbf{MR},\textbf{3},\textbf{3},\textbf{FAST++},\allowbreak\textbf{CR}]$
and $[\textbf{MR},\textbf{3},\textbf{3},\textbf{FAST++},\textbf{No-CR}]$ with
an average bug detection rate of 0.3659. Compared to the baseline 1
$[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\allowbreak\textbf{No-CR}]$
with an average detection rate of 0.306 and baseline 2
$[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{None}]$ with an
average detection rate of 0.224. The worst performing strategy is
$[\textbf{MT},\textbf{3},\textbf{3},\textbf{FAST++},\textbf{CR}]$ with an
average detection rate of 0.119.

##### RQ2 (Efficiency).

The best efficiency measure concerning CPU time is obtained by strategy
$[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{No-CR}]$ and
$[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{None}]$ with an
average amount of 6.058s. The worst performing strategy,
$[\textbf{MR},\textbf{3},\textbf{3},\textbf{ILP},\textbf{No-CR}]$, requires
993.229s on average. Concerning test-suite sizes,
$[\textbf{MT},\textbf{1},\textbf{1},\textbf{ILP},\textbf{CR}]$,
$[\textbf{MT},\textbf{2},\textbf{1},\textbf{ILP},\textbf{CR}]$, and
$[\textbf{MT},\textbf{3},\textbf{1},\textbf{ILP},\textbf{CR}]$ perform best
with an average measure of 0.225 test cases, whereas strategy
$[\textbf{MT},\textbf{3},\textbf{3},\textbf{None},\allowbreak\textbf{No-CR}]$
leads to the largest test-suite sizes with an average measure of 115.44 test
cases.

##### RQ3 (Trade-Off).

The base trade-off between effectiveness and CPU time is obtained by strategy
$[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{No-CR}]$ with an
average of 0.0503 bugs found per second. The worst performing strategy is
$[\textbf{MT},\textbf{3},\textbf{3},\textbf{FAST++},\textbf{CR}]$ with an
average of 0.0015 bugs found per second.

(a) Strategies with $\textbf{RTC}=\textbf{MR}$

(b) Strategies with $\textbf{RTC}=\textbf{MT}$

Figure 9: Results Effectiveness

(a) Strategies with $\textbf{RTC}=\textbf{MR}$

(b) Strategies with $\textbf{RTC}=\textbf{MT}$

Figure 10: Results Generation Time

(a) Strategies with $\textbf{RTC}=\textbf{MR}$

(b) Strategies with $\textbf{RTC}=\textbf{MT}$

Figure 11: Results Test-Suite Size

(a) Strategies with $\textbf{RTC}=\textbf{MR}$

(b) Strategies with $\textbf{RTC}=\textbf{MT}$

Figure 12: Results Bugs per Second

###  4.4 Discussion and Summary

##### RQ1 (Effectiveness).

Setting parameter RTC to MR increases effectiveness for all strategies. In
fact, almost all strategies using MR are more effective than even the most
effective strategy using MT. Indeed, parameter RTC has the highest impact on
effectiveness. While the impact of other parameters is smaller, it is
nonetheless also observable. Choosing None for parameter RS increases
effectiveness, as the other parameter value reduces effectiveness by reducing
the number of test cases. Choosing CR or No-CR for parameter CR has nearly no
impact on effectiveness. Strategies with MR and ILP cause a significant loss
in effectiveness if CR is selected. Choosing None for parameter CR has a
negative impact on strategies with MR selected, however, only having a small
impact if MT is selected. Lastly, parameters NRT and NPR also increase
effectiveness with increasing values (even in case of small increases).

Answer RQ1
---
The best effectiveness measure is reached by strategy
$[\textbf{MR},\textbf{3},\textbf{3},\textbf{None},\textbf{No-CR}]$ (i.e.,
modification revealing test cases, three test cases per test goal, up to three
previous revisions and no test-suite reduction) which improves effectiveness
compared to the baseline
$[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{No-CR}]$ by 19% and
compared to the baseline
$[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{None}]$ by 61%. The
highest impact on effectiveness is caused by parameter RTC

##### RQ2.1 (CPU Time).

Parameter RTC has by far the highest impact on CPU time. When choosing MT, CPU
time increases nearly 20 fold. As expected, parameter NPR increases the CPU
time nearly linearly to its respective value. Unexpectedly, parameter NRT does
not affect CPU time by a large margin. This is most likely due to the fact,
that reachability information computed during the first run of the test
generator can be re-used for the next test cases. Parameters CR and RS are
negligible in terms of CPU time if MR is selected, since the number of test-
cases remains small. If MT is selected, both parameters impact CPU time,
however still only by a small margin.

Answer RQ2.1
---
The best efficiency measure in terms of CPU time is reached by the baseline
strategies $[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{No-CR}]$
and $[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{None}]$ (i.e.,
modification traversing test cases, one test case per test goal, one previous
revision and no test-suite reduction, either ignoring or using the previous
test-suite (as this makes no different in CPU time)). The highest impact on
CPU time is caused by parameter RTC.

##### RQ2.2 (Test-Suite Size).

The highest impact on efficiency in terms of test-suite size is caused by
parameter RS. If None is selected, no reduction is enabled, and therefore, the
test-suite grows with each version. However, the choice of the technique used
for test-suite reduction only has a small impact on the test-suite size.

Parameter RTC also has a high impact on the test-suite size. This is due to
the fact, that a patch might contain multiple modifications. Therefore, the
number of test cases is higher in case of MT (i.e., requiring one test-case
per modified line) as compared to MR, where only one test case is required.
Parameter CR also affects test-suite sizes, but only by a small amount.
Lastly, parameters NRT and NPR affect the test-suite size almost linearly to
their respective values.

Answer RQ2.2
---
The best efficiency measure in terms of test-suite size is reached by the
strategy $[\textbf{MR},\textbf{1},\textbf{1},\textbf{ILP},\textbf{CR}]$ (i.e.,
modification revealing test cases, one test case per test goal, one previous
revision, ILP as test-suite reduction strategy and using the reduced test-
suite of the previous revision) which improves effectiveness compared to the
baseline $[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{No-CR}]$ by
6200% and compared to the baseline
$[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{None}]$ by 970%. The
highest impact on the test-suite size is caused by parameter RS.

##### RQ3 (Trade-Off).

We observe that all parameters have a large impact on the trade-off between
effectiveness and CPU time. Therefore, the interactions between the different
parameters is the main driver affecting the trade-off.

Answer RQ3
---
The strategy yielding the best trade-off is
$[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{No-CR}]$ (i.e.,
modification traversing test cases, one test case per test goal, one previous
revisions, no test-suite reduction and using the test-suite of the previous
revision as well) for which the fault-detection capability is acceptable, but
the efficiency in terms of CPU time is very high. Compared to the second
baseline $[\textbf{MT},\textbf{1},\textbf{1},\textbf{None},\textbf{None}]$ the
trade-off is increased by 36%.

##### Remarks.

Strategy
$[\textbf{MT},\textbf{3},\textbf{3},\allowbreak\textbf{None},\allowbreak\textbf{No-
CR}]$ is less effective than strategy $[\textbf{MT},\textbf{3},\textbf{2},\\\
\textbf{None},\allowbreak\textbf{No-CR}]$ which, by definition, is counter-
intuitive. This is due to the fact, that some comparator-programs for
comparing a faulty version $B_{i}$ to a program revision $P_{i-2}$ are invalid
(e.g., due to different return types), whereas the comparator-program for
$B_{i}$ and program revisions $P_{i-3}$ are actually valid. However, no test
cases could be found by the test-case generator revealing the bug. Hence, the
number of test suites for
$[\textbf{MT},\textbf{3},\textbf{3},\textbf{None},\allowbreak\textbf{No-CR}]$
and $[\textbf{MT},\textbf{3},\textbf{2},\textbf{None},\textbf{No-CR}]$ differ
slightly, which is the reason for the discrepancy between the factual results
and the theoretical specification of the technique. In our subject systems,
the probability that no valid comparator-program can be generated is
approximately 8%. Therefore, while this technical limitation is present, it
should not affect the results by a large margin.

###  4.5 Threats to Validity

##### Internal Validity.

Our regression-testing methodology relies on the assumption that when
different program versions are tested with the same test case, all factors
(e.g., platform, environment) that might influence the output except for the
source code itself remain constant. This so-called _controlled-regression-
testing assumption_ is commonly used in regression-testing experiments and
does, therefore, not harm validity of the results [2].

Concerning the soundness of our methodology, we tested the test-generation
loop by manually checking results for selected subject systems. However, due
to undecidability of reachability of program locations, if no more test cases
can be found (e.g., due to time-outs or imprecise counter-examples), it is
unknown if further test cases exist. Nevertheless, we expect precision
improvements to not substantially obstruct the (relative) results of our
evaluation.

Another threat to validity might arise from our selection of mutation
operators and their applications to our subject systems. However, our
selection comprises those mutations leading to useful results w.r.t. our
experimental setting, namely affecting one line of code, performing no code
deletions and producing a compilable result.

Limiting our considerations to (functional) unit testing may also threaten
internal validity. As unit testing constitutes the most established and
relevant testing technique in practice, it is particularly interesting and
relevant to investigate our methodology at this level first. In addition, the
proposed concepts might be likewise applicable at integration- and system-
level.

Additionally, our methodology does not incorporate systematic reusability-
checks of existing test cases for revealing modifications also in later
revisions which may affect efficiency measures. We plan to extend our
approach, accordingly, in a future work but we expect similar results as in
our current setting.

Finally, we expect our current focus on C programs to also not seriously harm
validity as we expect similar results for other programming languages, at
least for those relying on an imperative core (e.g., most OO languages).

##### External Validity.

We are not aware of any competitive tools with similar functionality as
RegreTS, especially concerning the generation of a configurable number of
modification-revealing test cases. Surprisingly, it was not possible for us to
use other recent test-case generators for strategies with
$\textbf{RTC}=\textbf{MR}$, which, by design, should have been possible. This
might be due to the fact, that the subject systems are real-world programs,
which where explicitly selected to be processable by our test-case generator.
However, test-case generators are (usually) limited in supporting certain
constructs of the C language. We tried to use other test-case generators
(i.e., Klee, FuSEBMC, Symbiotic and PRTest) from the international testing
competition 2021 [17]. However, these test-case generators were barely able to
generate any test cases at all. In addition, successfully generated test cases
were actually unable to reveal modifications between different program version
and were thus immediately removed from the test-suites during TSR (leading to
empty test suites). Only PRTest was able to generate some meaningful test-
cases but was, however, also not able to generate any test case for more than
half of the subject systems thus being unusable for a proper comparison.
However, the main focus of this paper is to compare different regression-
testing strategies, and not to compare different test-case generators for
regression-test generation. We thus assume the results to be very similar for
other test-case generation techniques (even though effectiveness in terms of
CPU time might change, the ratio of the CPU time of different strategy
presumably stay similar).

Another threat might arise from the selection of subject systems and the usage
of simulated bugs. Unfortunately, real-world systems with sufficient
information about revisions and bugs as required for our experiments are
barely available. We evaluated three prominent candidates for potential
candidates. First, CoreBench only provides a very short version history (often
only 1–2 versions) and incorporates many bugs being undetectable at unit level
(e.g., involving files and global errors like overflows) [18]. Second, the
_regression-verification tasks_ from the SV-Benchmarks [19] also have a small
version history and the different tasks cannot be executed in a self-sustained
manner as needed to reveal those bugs. However, we spend a lot of time in
searching for other freely available community benchmarks including version
history and known bugs. However, suitable benchmarks are still very rare.
Amongst others, we had a look into further subject systems from the SIR
Repository including programs like gzip and make [20], but either our test-
case generator was not able to handle those programs for mostly technical
reasons, or the programs were not suitable for our purposes (see descriptions
above). As also already discussed above, mutation testing is a reliable fault-
injection technique for measuring effectiveness in testing experiments [15].

Finally, our tool relies on third-party software, namely CPAchecker, a
software model-checker, and the mutation tool MUSIC for C programs. However,
both tools are established and have been extensively used for other
experiments in the recent past, so we expect them to produce sound results.

##  5 Related Work

###  5.1 Regression-Testing

A comprehensive overview about regression testing is provided by [2],
describing three categories: (1) _minimization_ of test suites as well as (2)
_selection_ and (3) _prioritization_ of test cases for regression testing.

##### Test-suite minimization

is concerned with selecting from an existing test suite a subset of test cases
to reduce the number of _redundant_ test executions during regression testing.
Many works propose heuristics for approximating near-optimal solutions [21, 4,
22, 23] for this NP-complete optimization problem, requiring as inputs an
_existing_ test suite and _a-priori defined_ metrics for measuring
effectiveness of test cases. The approaches used in this paper for TSR have
been proposed before. The greedy algorithm as used by _DIFF_ has been
introduced in [11]. To use ILP solving for TSR was initially proposed by [5]
and FAST++ has been introduced by [10]. However, none of these works
investigate the interactions between RTS and TSR techniques as done in this
paper.

[24] evaluate existing test-suite-reduction techniques on real-word projects
based on their failed builds. [25] proposed a new technique to reduce test
suites based on assertions instead of structural code coverage to improve
effectiveness of the resulting test suite. In an earlier work, [26] compare
and combine TSR and test-case selection to further increase efficiency of
regression testing. Our methodology goes beyond their approach as we consider
further strategic parameters which turned out to be very relevant.

##### Regression-test selection

is concerned with selecting from an existing test suite of an evolving program
a subset of test cases to be (re-)executed on a new program version. A variety
of different techniques has been applied (e.g., control-flow analysis [27, 28,
29] and/or data-flow analysis [30, 31, 32, 33]). Other works take behavior-
preserving modifications (e.g., refactorings) into account [34], apply RTS to
highly-configurable software [35], and try to find pareto-optimal solutions
for multi-objective RTS [36]. However, none of these works aim at _generating
new modification-revealing test cases_ to enhance effectiveness of regression
testing as done in our work. In particular, most recent works only guarantee
test cases to be modification-traversing.

##### Test-case prioritization

is concerned with selecting from an existing test suite a (re-)test-execution
order such that effectiveness of testing increases as quickly as possible over
time (e.g., to find as many faults as fast as possible) [37]. The underlying
problem is very similar to minimization/selection problems. Most existing
approaches consider code coverage as effectiveness criterion to statically
compute an (a-priori) ordering among test cases [38, 39, 40, 41, 42, 43]. In a
recent work, Wang and Zeng propose a dynamic prioritization technique based on
fault-detection history and other properties [44]. In contrast, in our
methodology, prioritization is currently out of scope, but may be easily
incorporated during test-case generation using recent approaches.

###  5.2 Test-Case Generation

A wide range of technique exist for (automatically) generating test cases
which we will describe in the following grouped by the test-case generation
technique applied. However, we are not aware of related works in terms of the
multiple test-cases per test goal to increase effectiveness of the resulting
test suite.

####  5.2.1 Coverage-Based Test-Case Generation

##### Fuzzing.

Fuzzing is currently very popular both in research and practice. The idea is
to quickly generate a large number of test cases by generating (semi-)random
input values. In some approaches, the input values of existing test cases are
reused and modified to generate new test cases. [45] Recent fuzzing techniques
are based on evolutionary algorithms [46] or context-free grammars of the
input data [47]. In addition, grey-box fuzzing [48] and whitebox fuzzing [47,
49] have been proposed (i.e., fuzzers also considering the source code of the
program under test). However, the primary goal of fuzzing is not to generate
test cases for regression testing systematically traversing / revealing
particular program modifications through different possible paths and/or
program versions as done in our approach.

##### Plain Random.

A test-case generation technique that is similar to, yet simpler than, is
plain random test-case generation. [50]. Test cases are randomly generated,
and afterwards, the achieved coverage is measured. This approach is clearly
more efficient than test-goal guided techniques. On the other hand, more
complicated test goals are often not reached, as the chance to generate valid
input values reaching those goals is small (e.g., to generate a test case for
input value $x$ which evaluates true for $x==1$ is $\frac{1}{2^{32}}$ for a
32-bit system). Therefore, generating (multiple different) modification-
revealing test cases is usually extremely expensive and ineffective using
purely random approaches.

##### Symbolic Execution.

Symbolic execution employs a symbolic reachability graph cope with the
reachable state space of input programs during test-case generation. One
prominent example is Klee [51]. Based on symbolic execution, it might be also
possible to generate multiple test cases covering the same goal through
different paths as done in our work. However, we are not aware of any recent
work going into this direction.

##### Bounded Model Checking.

Another technique to scale test-case generation to larger programs is bounded
model checking [52]. A bounded model checkers also computes the reachable
state space of programs (either in an abstract or concrete representation),
where loops are only explored up to maximum number of iterations $k$ (bound).
This enables the model checker to prove program properties with certainty only
within that bound. Such a tool can be also used for test cases generation
similar to symbolic model checking (i.e., by encoding test goals as
reachbility problems, see below). Again, we are not aware of any works using
bounded model checking to generate multiple test cases for the same test goal
or program modification, respectively.

##### Symbolic Model Checking.

Another approach to handle larger input programs is symbolic model checking as
applied, for instance, by the CPAchecker framework, which is also used by our
approach [13]. CoVeriTest is another recent test-case generator based on the
CPAchecker framework [53]. Again, these and other tools do currently not
support generation of multiple test-cases per test goal or program
modification as required in our approach. However, encoding the underlying
problem as reachability query as done in our approach would also enable the
usage of these other tools for regression-test generation.

####  5.2.2 Regression-Test-Case Generation.

We next discuss related work on generating test cases for systematically
investigating semantic differences between similar programs. _Differential
testing_ [54] is concerned with the following problem: Given two comparable
programs and an set of differential test cases, the systems can be checked for
bugs by running the test cases. If the outputs differ or the test loops
indefinitely or crashes, the test case is a candidate for a bug-revealing
test. Thereupon, Evans and Savioa proposed an approach for detecting program
changes by comparing test-execution results of two different program versions
[55]. The tool CSmith combines differential testing with fuzzing (i.e., C
programs) to find bugs in C-compiler implementations [56]. The work being
presumably most closely related to our methodology is DiffGen [57] for
generating test cases comparing two versions of a Java program. This is
achieved by instrumenting programs with equality-assert-statements and
generating test suites for statement coverage on (failed) assertions. This
work differs from ours as it does not support multiple test cases finding
differences between program versions, and also does not take multiple prior
versions into account. Additionally, they do not take TSR into account to
increase efficiency of regression testing.

The goal of _mutation testing_ is to _measure_ effectiveness of test suites or
test-generation techniques, respectively, by deriving from an original program
a set of syntactically slightly changed _mutants_ (simulating faults) [58]. A
test case _detects_ a mutant if its test-execution results for the original
program differ from those for the mutant. Based on this principle, [59] pursue
mutation-driven _generation_ of test cases for Java programs by using genetic
algorithms to find test cases that detect mutants. In contrast, [60] use a
combination of symbolic execution and a search-based heuristic to identify
test cases that are likely to _reveal_ mutants. [61] also propose a heuristic
for generating strong mutation-detecting test cases using hill climbing. As
these works are mainly based on heuristics, the generated test cases do not
guarantee to traverse/reveal program modifications. Additionally, those
approaches do not allow to configure the number of test cases or the number of
different programs as our parameters NPR and NRT, nor do they consider TSR.

Automatically _generating_ test cases for differentiating two program versions
for regression testing has been initially proposed by [62]. Their white-box
testing tool automatically compares output values of two given program
versions to derive input values leading to different outputs. Their approach
is applicable to Pascal programs only and does not support multiple test cases
and/or program versions as in our work.

###  5.3 Regression Verification

The goal of regression verification is to analyze different versions of a
system or program to check whether the specification is still fulfilled after
modifications. To this end, intermediate verification results are re-used
between versions to increase efficiency [63, 64, 65]. For instance,
intermediate results (so-called _abstraction precisions_) of verification runs
enable reuse for later version [66], and regression verification may be
applied to restrict the set of program inputs manually [67] or by syntactic
checks [68]. Furthermore, there is work on lifting principles of regression
verification to multi-threaded programs [69] and re-checking evolving software
of automated production systems [70]. Moreover, efficiency of regression
verification may be improved, for instance, by applying state-space
partitioning-techniques [71] and by improved encodings of reuse-information
[72]. Other works in this area reuse final verification results in case of a
subsequent change in the program [14, 73, 74, 75, 76]. However, none of these
approaches further utilizes the information collected for regression analysis
to derive modification-revealing test cases.

Similarly, _conditional model checking_ aims at reusing results of
verification runs to perform collaborative verification [77, 78]. To this end,
there are exchange formats for verification witnesses for property violations
[79] as well as for correctness proofs [80]. Furthermore, there is work on
keeping track of unverified parts of a program to apply test-case generation
for these parts [81, 82] and reusing verification results for hybrid systems
[83]. However, none of these approaches aim at finding differences between
versions of the same program as done in our approach.

##  6 Conclusion and Future Work

We presented a configurable regression-testing methodology for automating the
selection of regression test-cases with a particular focus on revealing
regression bugs in evolving programs. RegreTS currently supports regression
testing of C programs at unit level. Our experimental results show that
effectiveness and the efficiency highly depend on the selected regression
test-case generation strategy, where the parameter RTC (i.e., either
generating modification-traversing or modification-revealing test cases) has
the strongest impact on the effectiveness and efficiency. To conclude, our
experimental results show that for obtaining the best efficiency in terms of
CPU time and the best trade-off modification traversing test cases should be
used without test-suite reduction. However, for the best effectiveness,
modification revealing test cases should be used with multiple test cases per
test goal and multiple previous revisions taken into account. Additionally,
test-suite reduction obstructs effectiveness, therefore, for optimal
effectiveness test-suite reduction should be disabled.

As a future work, we plan to extend our approach. First, we plan to further
improve our test-generation technique to support additional subject systems as
well as in utilizing alternative test-case generation techniques within our
methodology (e.g., symbolic execution) and to compare the outcome with our
current results. Furthermore, we plan to investigate other kinds of regression
errors and to identify suitable regression strategies for effectively
revealing those bugs. Finally, we plan to adapt RegreTS to other testing
scenarios including, for instance, other input languages besides C and other
testing levels beyond unit testing which enables us to conduct experiments on
a richer set of subject systems.

##### Acknowledgments

This work was funded by the Hessian LOEWE initiative within the Software-
Factory 4.0 project.

## References

  * [1] Paul Ammann and Jeff Offutt  “Introduction to Software Testing”  Cambridge University Press, 2016
  * [2] Shin Yoo and Mark Harman  “Regression Testing Minimization, Selection and Prioritization: A Survey”  In _Softw. Test. Verif. Reliab._ 22.2 John WileySons Ltd., 2012, pp. 67–120  DOI: 10.1002/stv.430
  * [3] Emelie Engström, Mats Skoglund and Per Runeson  “Empirical Evaluations of Regression Test Selection Techniques: A Systematic Review”  In _Proceedings of the Second ACM-IEEE International Symposium on Empirical Software Engineering and Measurement_ ACM, 2008, pp. 22–31  DOI: 10.1145/1414004.1414011
  * [4] Mary Jean Harrold, Rajiv Gupta and Mary Lou Soffa  “A Methodology for Controlling the Size of a Test Suite”  In _ACM Trans. Softw. Eng. Methodol._ 2.3 ACM, 1993, pp. 270–285  DOI: 10.1145/152388.152391
  * [5] Alireza Khalilian and Saeed Parsa  “Bi-criteria Test Suite Reduction by Cluster Analysis of Execution Profiles”  In _Advances in Software Engineering Techniques_ Springer Berlin Heidelberg, 2012, pp. 243–256
  * [6] Saswat Anand et al.  “An orchestrated survey of methodologies for automated software test case generation”  In _Journal of Systems and Software_ 86.8, 2013, pp. 1978–2001  DOI: https://doi.org/10.1016/j.jss.2013.02.061
  * [7] Fabiano Pecorelli, Fabio Palomba and Andrea De Lucia  “The Relation of Test-Related Factors to Software Quality: A Case Study on Apache Systems”  In _Empirical Software Engineering_ 26.2 Springer ScienceBusiness Media LLC, 2021  DOI: 10.1007/s10664-020-09891-y
  * [8] Laura Inozemtseva and Reid Holmes  “Coverage is Not Strongly Correlated with Test Suite Effectiveness”  In _Proceedings of the 36th International Conference on Software Engineering_ Association for Computing Machinery, 2014, pp. 435–445  DOI: 10.1145/2568225.2568271
  * [9] Jung-Min Kim and A. Porter  “A history-based test prioritization technique for regression testing in resource constrained environments”  In _Proceedings of the 24th International Conference on Software Engineering. ICSE 2002_ Association for Computing Machinery, 2002, pp. 119–129  DOI: 10.1109/ICSE.2002.1007961
  * [10] Emilio Cruciani, Breno Miranda, Roberto Verdecchia and Antonia Bertolino  “Scalable Approaches for Test Suite Reduction”  In _2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)_ IEEE Press, 2019, pp. 419–429  DOI: 10.1109/ICSE.2019.00055
  * [11] Dirk Beyer and Thomas Lemberger  “TestCov: Robust Test-Suite Execution and Coverage Measurement”  In _Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering_ IEEE Press, 2019, pp. 1074–1077  DOI: 10.1109/ASE.2019.00105
  * [12] Zhenyu Chen, Xiaofang Zhang and Baowen Xu  “A Degraded ILP Approach for Test Suite Reduction.”  In _20th International Conference on Software Engineering and Knowledge Engineering, SEKE 2008_ , 2008, pp. 494–499
  * [13] Dirk Beyer, Adam J. Chlipala, Thomas A. Henzinger, Ranjit Jhala and Rupak Majumdar  “Generating Tests from Counterexamples”  In _Proceedings of the 26th International Conference on Software Engineering_ IEEE Computer Society, 2004, pp. 326–335  DOI: 10.5555/998675.999437
  * [14] Dirk Beyer, Andreas Holzer, Michael Tautschnig and Helmut Veith  “Information Reuse for Multi-goal Reachability Analyses”  In _ESOP ’13_ 7792 Springer, 2013, pp. 472–491  DOI: 10.1007/978-3-642-37036-6˙26
  * [15] James H. Andrews, Lionel C. Briand and Yvan Labiche  “Is mutation an appropriate tool for testing experiments? [software testing]”  In _Proceedings. 27th International Conference on Software Engineering, 2005. ICSE 2005._ IEEE, 2005, pp. 402–411  DOI: 10.1109/ICSE.2005.1553583
  * [16] Duy Loc Phan, Yunho Kim and Moonzoo Kim  “MUSIC: Mutation Analysis Tool with High Configurability and Extensibility”  In _2018 IEEE International Conference on Software Testing, Verification and Validation Workshops_ IEEE, 2018, pp. 40–46  DOI: 10.1109/ICSTW.2018.00026
  * [17] Dirk Beyer  “Status Report on Software Testing: Test-Comp 2021”  In _Fundamental Approaches to Software Engineering_ Springer International Publishing, 2021, pp. 341–357  DOI: 10.1007/978-3-030-71500-7˙17
  * [18] Marcel Böhme and Abhik Roychoudhury  “CoREBench: Studying Complexity of Regression Errors”  In _Proceedings of the 23rd ACM/SIGSOFT International Symposium on Software Testing and Analysis_ ACM, 2014, pp. 105–115
  * [19] Dirk Beyer  “SV-Benchmarks: Benchmark Set of 8th Intl. Competition on Software Verification (SV-COMP 2019)”  Zenodo, 2019  DOI: 10.5281/zenodo.2598728
  * [20] Hyunsook Do, Sebastian G. Elbaum and Gregg Rothermel  “Supporting Controlled Experimentation with Testing Techniques”  In _Empirical Software Engineering: An International Journal_ 10.4, 2005, pp. 405–435
  * [21] Tsong Yueh Chen and Man Fai Lau  “Dividing Strategies for the Optimization of a Test Suite”  In _Inf. Process. Lett._ 60.3 Elsevier North-Holland, Inc., 1996, pp. 135–141  DOI: 10.1016/S0020-0190(96)00135-4
  * [22] Joseph R. Horgan and Saul London  “A data flow coverage testing tool for C”  In _[1992] Proceedings of the Second Symposium on Assessment of Quality Software Development Tools_ IEEE, 1992, pp. 2–10  DOI: 10.1109/AQSDT.1992.205829
  * [23] A. Jefferson Offutt, Jie Pan and Jeffrey M. Voas  “Procedures for reducing the size of coverage-based test sets”  In _Twelfth International Conference on Testing Computer Software_ , 1995, pp. 111–123
  * [24] August Shi, Alex Gyori, Suleman Mahmood, Peiyuan Zhao and Darko Marinov  “Evaluating Test-Suite Reduction in Real Software Evolution”  In _Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis_ Association for Computing Machinery, 2018, pp. 84–94  DOI: 10.1145/3213846.3213875
  * [25] Junjie Chen, Yanwei Bai, Dan Hao, Lingming Zhang, Lu Zhang and Bing Xie  “How Do Assertions Impact Coverage-Based Test-Suite Reduction?”  In _2017 IEEE International Conference on Software Testing, Verification and Validation (ICST)_ IEEE, 2017  DOI: 10.1109/icst.2017.45
  * [26] August Shi, Tifany Yung, Alex Gyori and Darko Marinov  “Comparing and Combining Test-Suite Reduction and Regression Test Selection”  In _Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering_ Association for Computing Machinery, 2015, pp. 237–247  DOI: 10.1145/2786805.2786878
  * [27] J. Hartmann and David J. Robson  “Revalidation during the software maintenance phase”  In _Proceedings. Conference on Software Maintenance - 1989_ IEEE, 1989, pp. 70–80  DOI: 10.1109/ICSM.1989.65195
  * [28] J. Hartmann and David J. Robson  “RETEST-development of a selective revalidation prototype environment for use in software maintenance”  In _Twenty-Third Annual Hawaii International Conference on System Sciences_ 2 IEEE, 1990, pp. 92–101 vol.2  DOI: 10.1109/HICSS.1990.205179
  * [29] J. Hartmann and David J. Robson  “Techniques for selective revalidation”  In _IEEE Software_ 7.1, 1990, pp. 31–36  DOI: 10.1109/52.43047
  * [30] Rajiv Gupta, Mary Jean Harrold and Mary Lou Soffa  “An approach to regression testing using slicing”  In _Proceedings Conference on Software Maintenance 1992_ IEEE Computer Society, 1992, pp. 299–308  DOI: 10.1109/ICSM.1992.242531
  * [31] Mary Jean Harrold and M. L. Souffa  “An incremental approach to unit testing during maintenance”  In _Proceedings. Conference on Software Maintenance, 1988._ IEEE, 1988, pp. 362–367  DOI: 10.1109/ICSM.1988.10188
  * [32] Mary Jean Harrold and Mary Lou Soffa  “Interprocedual Data Flow Testing”  In _Proceedings of the ACM SIGSOFT ’89 Third Symposium on Software Testing, Analysis, and Verification_ ACM, 1989, pp. 158–167  DOI: 10.1145/75308.75327
  * [33] Abu-Bakr Taha, Stephen M. Thebaut and Sying-Syang Liu  “An approach to software fault localization and revalidation based on incremental data flow analysis”  In _[1989] Proceedings of the Thirteenth Annual International Computer Software Applications Conference_ IEEE, 1989, pp. 527–534  DOI: 10.1109/CMPSAC.1989.65142
  * [34] Kaiyuan Wang, Chenguang Zhu, Ahmet Celik, Jongwook Kim, Don Batory and Milos Gligoric  “Towards Refactoring-aware Regression Test Selection”  In _Proceedings of the 40th International Conference on Software Engineering_ ACM, 2018, pp. 233–244  DOI: 10.1145/3180155.3180254
  * [35] Dusica Marijan and Marius Liaaen  “Practical Selective Regression Testing with Effective Redundancy in Interleaved Tests”  In _Proceedings of the 40th International Conference on Software Engineering: Software Engineering in Practice_ Association for Computing Machinery, 2018, pp. 153–162  DOI: 10.1145/3183519.3183532
  * [36] Ankur Choudhary, Arun Prakash Agrawal and Arvinder Kaur  “An Effective Approach for Regression Test Case Selection Using Pareto Based Multi-objective Harmony Search”  In _Proceedings of the 11th International Workshop on Search-Based Software Testing_ ACM, 2018, pp. 13–20  DOI: 10.1145/3194718.3194722
  * [37] Weichen E. Wong, Joseph R. Horgan, Saul London and Aditya P. Mathur  “Effect of Test Set Minimization on Fault Detection Effectiveness”  In _1995 17th International Conference on Software Engineering_ ACM, 1995, pp. 41–41  DOI: 10.1145/225014.225018
  * [38] Gregg Rothermel, Roland H. Untch, Chengyun Chu and Mary Jean Harrold  “Test case prioritization: an empirical study”  In _Proceedings IEEE International Conference on Software Maintenance - 1999 (ICSM’99). ’Software Maintenance for Business Change’ (Cat. No.99CB36360)_ IEEE, 1999, pp. 179–188  DOI: 10.1109/ICSM.1999.792604
  * [39] Gregg Rothermel, Roland H. Untch, Chengyun Chu and Mary J. Harrold  “Prioritizing test cases for regression testing”  In _IEEE Transactions on Software Engineering_ 27.10, 2001, pp. 929–948  DOI: 10.1109/32.962562
  * [40] Sebastian Elbaum, David Gable and Gregg Rothermel  “Understanding and measuring the sources of variation in the prioritization of regression test suites”  In _Proceedings Seventh International Software Metrics Symposium_ IEEE Computer Society, 2001, pp. 169–179  DOI: 10.1109/METRIC.2001.915525
  * [41] Sebastian Elbaum, Alexey Malishevsky and Gregg Rothermel  “Incorporating varying test costs and fault severities into test case prioritization”  In _Proceedings of the 23rd International Conference on Software Engineering. ICSE 2001_ IEEE Computer Society, 2001, pp. 329–338  DOI: 10.1109/ICSE.2001.919106
  * [42] Alexey Malishevsky, Gregg Rothermel and Sebastian Elbaum  “Modeling the cost-benefits tradeoffs for regression testing techniques”  In _International Conference on Software Maintenance, 2002. Proceedings._ IEEE, 2002, pp. 204–213  DOI: 10.1109/ICSM.2002.1167767
  * [43] Gregg Rothermel, Sebastian Elbaum, Alexey Malishevsky, Praveen Kallakuri and Brian Davia  “The impact of test suite granularity on the cost-effectiveness of regression testing”  In _Proceedings of the 24th International Conference on Software Engineering. ICSE 2002_ ACM, 2002, pp. 130–140  DOI: 10.1145/581356.581358
  * [44] Xiaolin Wang and Hongwei Zeng  “History-Based Dynamic Test Case Prioritization for Requirement Properties in Regression Testing”  In _2016 IEEE/ACM International Workshop on Continuous Software Evolution and Delivery (CSED)_ IEEE, 2016, pp. 41–47  DOI: 10.1109/CSED.2016.016
  * [45] Jun Li, Bodong Zhao and Chao Zhang  “Fuzzing: a survey”  In _Cybersecurity_ 1.1 Springer ScienceBusiness Media LLC, 2018  DOI: 10.1186/s42400-018-0002-y
  * [46] Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida and Herbert Bos  “VUzzer: Application-aware Evolutionary Fuzzing”  In _Proceedings 2017 Network and Distributed System Security Symposium_ Internet Society, 2017  DOI: 10.14722/ndss.2017.23404
  * [47] Patrice Godefroid, Adam Kiezun and Michael Y. Levin  “Grammar-Based Whitebox Fuzzing”  In _Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation_ Association for Computing Machinery, 2008, pp. 206–215  DOI: 10.1145/1375581.1375607
  * [48] Michał Zalewski  “Technical ”whitepaper” for afl-fuzz”, 2006  URL: https://lcamtuf.coredump.cx/afl/technical_details.txt
  * [49] Patrice Godefroid, Michael Y. Levin and David Molnar  “Automated Whitebox Fuzz Testing”  In _Network Distributed Security Symposium (NDSS)_ , 2008
  * [50] Thomas Lemberger  “Plain random test generation with PRTest”  In _International Journal on Software Tools for Technology Transfer_ Springer ScienceBusiness Media LLC, 2020  DOI: 10.1007/s10009-020-00568-x
  * [51] Cristian Cadar, Daniel Dunbar and Dawson Engler  “KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs”  In _8th USENIX Symposium on Operating Systems Design and Implementation (OSDI 08)_ 8 USENIX Association, 2008, pp. 209–224
  * [52] Mikhail R. Gadelha, Rafael Menezes, Felipe R. Monteiro, Lucas C. Cordeiro and Denis Nicole  “ESBMC: Scalable and Precise Test Generation based on the Floating-Point Theory”  In _Fundamental Approaches to Software Engineering_ Springer International Publishing, 2020, pp. 525–529  DOI: 10.1007/978-3-030-45234-6˙27
  * [53] Marie-Christine Jakobs  “CoVeriTest with Dynamic Partitioning of the Iteration Time Limit (Competition Contribution)”  In _Fundamental Approaches to Software Engineering_ 12076 Springer International Publishing, 2020, pp. 540–544  DOI: 10.1007/978-3-030-45234-6“˙30
  * [54] William M. McKeeman  “Differential Testing for Software”  In _Digital Technical Journal_ 10, 1998, pp. 100–107
  * [55] Robert B. Evans and Alberto Savoia  “Differential Testing: A New Approach to Change Detection”  In _The 6th Joint Meeting on European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering: Companion Papers_ ACM, 2007, pp. 549–552  DOI: 10.1145/1295014.1295038
  * [56] Xuejun Yang, Yang Chen, Eric Eide and John Regehr  “Finding and Understanding Bugs in C Compilers”  In _Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation_ ACM, 2011, pp. 283–294  DOI: 10.1145/1993498.1993532
  * [57] Kunal Taneja and Tao Xie  “DiffGen: Automated Regression Unit-Test Generation”  In _2008 23rd IEEE/ACM International Conference on Automated Software Engineering_ IEEE, 2008, pp. 407–410  DOI: 10.1109/ASE.2008.60
  * [58] Yue Jia and Mark Harman  “An Analysis and Survey of the Development of Mutation Testing”  In _IEEE Transactions on Software Engineering_ 37.5, 2011, pp. 649–678  DOI: 10.1109/TSE.2010.62
  * [59] Gordon Fraser and Andreas Zeller  “Mutation-driven Generation of Unit Tests and Oracles”  In _Proceedings of the 19th International Symposium on Software Testing and Analysis_ ACM, 2010, pp. 147–158  DOI: 10.1145/1831708.1831728
  * [60] Mark Harman, Yue Jia and William B. Langdon  “Strong Higher Order Mutation-based Test Data Generation”  In _Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering_ ACM, 2011, pp. 212–222  DOI: 10.1145/2025113.2025144
  * [61] Francisco Carlos M. Souza, Mike Papadakis, Yves Le Traon and Márcio E. Delamaro  “Strong Mutation-based Test Data Generation Using Hill Climbing”  In _Proceedings of the 9th International Workshop on Search-Based Software Testing_ ACM, 2016, pp. 45–54  DOI: 10.1145/2897010.2897012
  * [62] Bogdan Korel and Ali M. Al-Yami  “Automated Regression Test Generation”  In _Proceedings of the 1998 ACM SIGSOFT International Symposium on Software Testing and Analysis_ ACM, 1998, pp. 143–152  DOI: 10.1145/271771.271803
  * [63] R. H. Hardin, R. P. Kurshan, K. L. McMillan, J. A. Reeds and N. J. A. Sloane  “Efficient regression verification”  In _WODES ’96_ IEE, 1996, pp. 157–150
  * [64] Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar and Marco A. A. Sanvido  “Extreme Model Checking”  In _Verification: Theory and Practice_ 2772, LNCS  Springer, 2003, pp. 332–358  DOI: 10.1007/978-3-540-39910-0˙16
  * [65] Ofer Strichman and Benny Godlin  “Regression Verification - A Practical Way to Verify Programs”  In _VSTTE ’05_ 4171, LNCS  Springer, 2008, pp. 496–501  DOI: 10.1007/978-3-540-69149-5˙54
  * [66] Dirk Beyer, Stefan Löwe, Evgeny Novikov, Andreas Stahlbauer and Philipp Wendler  “Precision Reuse for Efficient Regression Verification”  In _ESEC/FSE ’13_ ACM, 2013, pp. 389–399  DOI: 10.1145/2491411.2491429
  * [67] Marcel Böhme, Bruno C. d. S. Oliveira and Abhik Roychoudhury  “Partition-based Regression Verification”  In _ICSE ’13_ IEEE Press, 2013, pp. 302–311  DOI: 10.5555/2486788.2486829
  * [68] Benny Godlin and Ofer Strichman  “Regression verification: proving the equivalence of similar programs”  In _Software Testing, Verification and Reliability_ 23.3, 2013, pp. 241–258  DOI: 10.1002/stvr.1472
  * [69] Sagar Chaki, Arie Gurfinkel and Ofer Strichman  “Regression Verification for Multi-threaded Programs”  In _VMCAI ’12_ 7148 Springer, 2012, pp. 119–135  DOI: 10.1007/978-3-642-27940-9˙9
  * [70] Bernhard Beckert, Mattias Ulbrich, Birgit Vogel-Heuser and Alexander Weigl  “Regression Verification for Programmable Logic Controller Software”  In _ICFEM ’15_ 9407 Springer International Publishing, 2015, pp. 234–251  DOI: 10.1007/978-3-319-25423-4˙15
  * [71] John Backes, Suzette Person, Neha Rungta and Oksana Tkachuk  “Regression Verification Using Impact Summaries”  In _SPIN ’13_ 7976 Springer, 2013, pp. 99–116  DOI: 10.1007/978-3-642-39176-7˙7
  * [72] Dennis Felsing, Sarah Grebing, Vladimir Klebanov, Philipp Rümmer and Mattias Ulbrich  “Automating Regression Verification”  In _ASE ’14_ ACM, 2014, pp. 349–360  DOI: 10.1145/2642937.2642987
  * [73] Willem Visser, Jaco Geldenhuys and Matthew B. Dwyer  “Green: Reducing, Reusing and Recycling Constraints in Program Analysis”  In _FSE ’12_ ACM, 2012, pp. 58:1–58:11  DOI: 10.1145/2393596.2393665
  * [74] Ondrej Sery, Grigory Fedyukovich and Natasha Sharygina  “Incremental Upgrade Checking by Means of Interpolation-based Function Summaries”  In _FMCAD ’12_ IEEE, 2012, pp. 114–121
  * [75] Guowei Yang, Matthew B. Dwyer and Gregg Rothermel  “Regression Model Checking”  In _ICSM ’19_ IEEE, 2009, pp. 115–124  DOI: 10.1109/ICSM.2009.5306334
  * [76] Steven Lauterburg, Ahmed Sobeih, Darko Marinov and Mahesh Viswanathan  “Incremental State-Space Exploration for Programs with Dynamically Allocated Data”  In _ICSE ’08_ ACM, 2008, pp. 291–300  DOI: 10.1145/1368088.1368128
  * [77] Dirk Beyer, Thomas A. Henzinger, M. Erkan Keremoglu and Philipp Wendler  “Conditional Model Checking: A Technique to Pass Information between Verifiers”  In _Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering_ Association for Computing Machinery, 2012  DOI: 10.1145/2393596.2393664
  * [78] Maria Christakis, Peter Müller and Valentin Wüstholz  “Collaborative Verification and Testing with Explicit Assumptions”  In _FM ’12_ 7436 Springer, 2012, pp. 132–146  DOI: 10.1007/978-3-642-32759-9˙13
  * [79] Dirk Beyer, Matthias Dangl, Daniel Dietsch, Matthias Heizmann and Andreas Stahlbauer  “Witness Validation and Stepwise Testification Across Software Verifiers”  In _ESEC/FSE ’15_ ACM, 2015, pp. 721–733  DOI: 10.1145/2786805.2786867
  * [80] Dirk Beyer, Matthias Dangl, Daniel Dietsch and Matthias Heizmann  “Correctness Witnesses: Exchanging Verification Results Between Verifiers”  In _FSE ’16_ ACM, 2016, pp. 326–337  DOI: 10.1145/2950290.2950351
  * [81] Mike Czech, Marie-Christine Jakobs and Heike Wehrheim  “Just Test What You Cannot Verify!”  In _FASE ’15_ 9033 Springer, 2015, pp. 100–114  DOI: 10.1007/978-3-662-46675-9˙7
  * [82] Maria Christakis, Peter Müller and Valentin Wüstholz  “Guiding Dynamic Symbolic Execution Toward Unverified Program Executions”  In _ICSE ’16_ ACM, 2016, pp. 144–155  DOI: 10.1145/2884781.2884843
  * [83] Stefan Mitsch, Grant Olney Passmore and André Platzer  “Collaborative Verification-Driven Engineering of Hybrid Systems”  In _Mathematics in Computer Science_ 8.1, 2014, pp. 71–97  DOI: 10.1007/s11786-014-0176-y