On the limit of control flow analysis for regression test selection.
Automated analyses for regression test selection (RTS) attempt to determine if a modified program, when run on a test t, will have the same behavior as an old version of the program run on t, but without running the new program on t. RTS analyses must confront a price/performance tradeoff: a more precise analysis might be able to eliminate more tests, but could take much longer to run.We focus on the application of control flow analysis and control flow coverage, relatively inexpensive analyses, to the RTS problem, considering how the precision of RTS algorithms can be affected by the type of coverage information collected. We define a strong optimality condition (edge-optimality) for RTS algorithms based on edge coverage that precisely captures when such an algorithm will report that re-testing is needed, when, in actuality, it is not. We reformulate Rothermel and Harrold's RTS algorithm and present three new algorithms that improve on it, culminating in an edge-optimal algorithm. Finally, we consider how path coverage can be used to improve the precision of RTS algorithms.
Introduction
The goal of regression test selection (RTS) analysis is to answer the
following question as inexpensively as possible:
Given test input t and programs old and new, does new(t)
have the same observable behavior as old(t)?
To appear, 1998 ACM/SIGSOFT International Symposium on
Software Testing and Analysis
Of course, it is desired to answer this question without running program
new on test t. RTS analysis uses static analysis of programs
old and new in combination with dynamic information (such as coverage
collected about the execution old(t) in order to
make this determination. An RTS algorithm either selects a test for
re-testing or eliminates the test.
Static analyses for RTS come in many varieties: some examine the
syntactic structure of a program [6]; others use control flow or control
dependence information [11, 12]; more ambitious analyses examine
the def-use chains or flow dependences of a program [9, 5].
Typically, each of these analyses is more precise than the previous,
but at a greater cost.
A safe (conservative) RTS analysis never eliminates a test t if new(t)
has different behavior than old(t). A safe algorithm may select
some test when it could have been eliminated.
We focus on the application of control flow analysis to safe regression
testing (from now on we will use CRTS to refer to "Control-
flow-based RTS"). Previous work has improved the precision of
CRTS analysis but left open the question of what the limit of such
analyses are. CRTS can be improved in two ways: by increasing the
precision of the analysis applied to the control flow graph representations
of programs old and new, or by increasing the precision of
the dynamic information recorded about the execution old(t). We
will address both issues and the interactions between them.
Our results are threefold:
ffl (Section 3) Building on recent work in CRTS by Rothermel
and Harrold [12], we show a strong relationship between
CRTS, deterministic finite state automata, and the intersection
of regular languages. We define the intersection graph
of two control flow graphs, which precisely captures the goal
of CRTS and forms the basis for a family of CRTS algorithms,
parameterized by what dynamic information is collected about
old(t).
ffl (Section 4) We consider the power of CRTS when the dynamic
information recorded about old(t) is edge coverage (i.e.,
whether or not each edge of old's control flow graph was
executed). We define a strong optimality condition (edge-
optimality) for CRTS algorithms based on edge coverage. We
then reformulate Rothermel and Harrold's CRTS algorithm
in terms of the intersection graph and present three new algorithms
that improve on it, culminating in an edge-optimal
algorithm. The first algorithm eliminates a test whenever
the Rothermel/Harrold algorithm does, and safely eliminates
more tests in general, at the same cost. The next two algorithms
are even more precise, but at greater computational
cost.
ffl (Section 5) By recording path coverage information about
rather than edge coverage, we can improve upon edge-
optimal algorithms. However, if path profiling is limited to
tracking paths of a bounded length (which is motivated by concerns
of efficiency), then an adversary will always be able to
choose a program new that will cause any CRTS algorithm
based on path coverage to fail.
Section 6 reviews related work and Section 7 summarizes the paper.
Background
We assume a standard imperative language such as C, C++, or Java
in which the control flow graph of a procedure P is completely determined
at compile time. In P's control flow graph G, each vertex
represents a basic block of instructions and each edge represents
a control transition between blocks. The translation of an abstract
syntax tree representation of a procedure into its control flow graph
representation is well known [1]. Since G is an executable representation
of P, we will talk about executing both P and G on a test
t.
We now define some graph terminology that will be useful in the
sequel.
s; x) be a directed control flow graph with vertices
a unique entry vertex s, from which all vertices
are reachable, and exit vertex x, which has no successors and is
reachable from all vertices. A vertex v is labelled with BB(v), the
code of the basic block it contains. Two different vertices may have
identical labels. It is often convenient to refer to a vertex by its label
and we will often do so, distinguishing vertices with identical labels
when necessary.
An edge source vertex v to target vertex w
via a directed edge labelled l. The outgoing edges of each vertex
are uniquely labeled. Labels are values (typically, true or false for
boolean predicates) that determine where control will transfer next
after execution of BB(v). 2 If a vertex v has only one outgoing edge,
its label is e, which is not shown in the figures.
Since the outgoing edges of a vertex are uniquely labelled, an edge
may also be represented by a pair (v; l), which we call a
control transition or transition, for short. The vertex succ(v; l) denotes
the vertex that is the l-successor of vertex v (if
A path in G is a sequence of edges
where the target vertex of e i is the source vertex of e i+1 for 1 -
path may be represented equivalently by an alternating
sequence of vertices and edge labels
is the source vertex of edge e i (for 1 - i - n), v n+1 is the
target vertex of e n , and l i is the label of edge e
Given a path p of n edges (and n [i] be the i th
vertex [i] be the i th edge label (1 - i - n).
2 The number of outgoing edges of vertex v and the labels on
these edges are uniquely defined by BB(v). Thus, different vertices
that have identical basic blocks will have the same number of out-going
edges with identical labels.
Paths beginning at a designated vertex (for our purposes, the entry
vertex s) are equivalently represented by a sequence of basic blocks
and labels (rather than a sequence of edges or vertices and labels):
A complete path is a path from s to x.

Figure

1 shows two programs P and P 0 and their corresponding
control flow graphs G and G 0 . For both G and G 0 , the entry vertex
is and the exit vertex is . The label of a vertex v denotes
its basic block BB(v). Graph G has one occurrence of basic block
C while graph G 0 has two occurrences of C. The graph G 00 is the
intersection graph of G and G 0 and is discussed next.
3 CRTS and the Intersection Graph
In control flow analysis, the graphical structure of a program is an-
alyzed, but the semantics of the statements in a program are not,
except to say whether or not two statements are textually identical.
This implies that CRTS algorithms must assume that every complete
path through a graph is potentially executable (even though
there may be unexecutable paths). Unexecutable paths cannot affect
the safety of CRTS algorithms, but may decrease their preci-
sion, just as they do in compiler optimization.
CRTS algorithms must be able to determine if two basic blocks
are semantically equivalent. Of course, this is undecidable in gen-
eral. Following Rothermel and Harrold, we use textual equivalence
of the code as a conservative approximation to semantic equiva-
lence, which is captured in the definition of equivalent vertices:
Two vertices v and w (from potentially different graphs) are equivalent
if the code of BB(v) is lexicographically identical to BB(w).
Let Equiv(v;w) be true iff v is equivalent to w. 3
Once we have equivalent vertices, we can extend equivalence to
paths, as follows: paths p and q are identical if p and q are the
same length, Equiv(p v [i]; q v [i]) is true for all i, and p l
all i. That is, p and q are identical words (over an alphabet of basic
blocks and labels).
The following simple definition (a restatement of that found in [11])
precisely captures the power of CRTS:
If graph G run on input t (denoted by G(t)) traverses complete
path p and graph G 0 contains complete path p 0 identical
to p, then G 0
(t) will traverse path p 0 and have the
same observable behavior as G(t).
The above definition translates trivially into the most precise and
computationally expensive CRTS algorithm: record the complete
execution path of G(t) (via code instrumentation that traces the
path [4]) and compare it to the control flow graph of G 0 to determine
if the path exists there. We will see later in Section 5 that any
algorithm that does not record the complete execution path of G(t)
can be forced, by an adversary choosing an appropriate graph G 0 ,
to select a test that could have been eliminated.
We observe that a control flow graph G may be viewed as a deterministic
finite automaton (DFA) with start state s and final state x
that accepts the language L(G), the set of all complete paths in G.
More precisely, a control flow graph G has a straightforward interpretation
as a DFA in which each vertex v in V corresponds to two
3 The exit vertex x can only be equivalent to other exit vertices
(i.e., vertices with no successors).
U,U
f
f
f
G" A,A
reject
accept
if A {
{ U }
if C { Y } else { Z }
} else {
if C { W }
U
f
f
Y Z
G' A
if A {
{ U }
if C { W }
U
f
f
f
G A

Figure

1: Example programs P and P 0 , their corresponding control flow graphs G and G 0 , and the intersection graph G 00 of G and G 0 .
states, v 1 and v 2 . These states are connected by a state transition
labelled by BB(v). Edges in E are also interpreted as
state transitions: an edge v ! l w is interpreted as a state transition
. The alphabet of the DFA is the union of all basic blocks
and all edge labels, s 1 is the start state, and x 2 is the final state. The
recognizes precisely the complete paths of G. Rather than
represent the control flow graph in this more verbose fashion, we
choose to present it in its traditional form but keep its DFA interpretation
in mind.
Given this insight, the CRTS question reduces to:
Is a complete path p from L(G) also in L(G 0 )?
), the paths for which re-testing is not
needed, and let D(G;G 0
), the paths for which re-testing
is needed.
A CRTS algorithm is optimal if, given any path p in I(G;G 0 ), the
algorithm reports that p is in I(G;G 0 ). A CRTS algorithm is safe
if, given any path p in D(G;G 0 ), the algorithm reports that p is in
To help reason about I(G;G 0 ) and D(G;G 0 ), we define a new graph
the intersection graph of
which also has a straightforward interpretation as a
DFA. 4 This graph can be efficiently constructed from G and G 0 .
The vertex set V 00 of G 00 is simply the cross product of V and V 0 ,
with two additional vertices:
We use the following relation to help define
is essentially an optimized version of a product automaton
of G and G 0 [7].
The edge set E 00 is defined in terms of ,! l and the Equiv relation.
not
) is the entry vertex of G 00 . We will restrict the vertex
and edge sets of G 00 to be the vertices and edges reachable from
). If no vertices (other than (s; s 0
or edges are reachable from
are not equivalent. A pair (v; v 0
) is reachable
from (s; s 0
there is a path p in G from s to v that is a prefix of a
path in I(G;G 0
reject represents the reject state, which corresponds
to paths in D(G;G 0
represents the accept
state, which corresponds to paths in I(G;G 0 ).

Figure

1 shows the intersection graph G 00 of the graphs G and G 0 in
the figure. We can see that there are two paths in I(G;G 0 ), corresponding
to the paths:
and
in G 00 . The corresponding paths in G are: [A; f ;C; f
Graph G 00 also shows that any path that begins
with the transition (A;t) is in D(G;G 0
Two straightforward results about the intersection graph G 00 will inform
the rest of the paper: A path p is in I(G;G 0 ) iff it is represented
by a path from (s; s 0 ) to accept in G 00 ; a path p is in D(G;G 0 ) iff it
is represented by a path from (s; s 0 ) to reject in G 00 . Of course, every
complete path p in G is either in I(G;G 0 ) or D(G;G 0 ). More
Theorem 1 Let G 00 be the intersection graph of graphs G and G 0 .
Path
from G is in I(G;G 0 ) iff
is in G 00 .
Theorem 2 Let G 00 be the intersection graph of graphs G and G 0 .
Path
from G is in D(G;G 0 ) iff there exists n) such that
is in G 00 .

Figure

shows how the intersection graph of graphs G and G 0 is
computed via a synchronous depth-first search of both graphs. The
procedure DFS is always called with equivalent vertices v and v 0 .
If (v; v 0 ) is already in V 00 , this pair has been visited before and the
procedure returns. Otherwise, (v; v 0 ) is inserted into V 00 and each
its corresponding edge is considered in
turn. 5 Edges are appropriately inserted into E 00 to reflect whether
or not vertices w and w 0 are equivalent, and whether or not w is the
exit vertex of G. The algorithm recurses only when w and w 0 are
equivalent and w is not the exit vertex of G. The algorithm also
computes the set of vertices V 00
accept from which accept is reachable
in G 00 , which will be used later.
The worst-case time complexity of the algorithm is O(jEj \Delta jE 0 j).
Note that it is not necessary to store the relation E 00 explicitly, since
it can be derived on demand from V 00 , E and E 0 . Thus, the space
complexity for storing the intersection graph (as well as V 00
accept ) is
in the worst case.
4 CRTS Using Edge Coverage
What is the limit of CRTS given that the dynamic information collected
about G(t) is edge coverage? Consider a complete path p
representing the execution path of G(t) and the set of edges E p of
G that it covers. There may be another complete path q in G, distinct
from p, such that E represent the set of paths
(including p) whose edge sets are identical to E p .
To determine whether or not G 0 needs retesting, a CRTS algorithm
using edge coverage must consider (at least implicitly) all the paths
in P p . If all of these paths are members of I(G;G 0 ) then the CRTS
algorithm can and should eliminate the test that generated path p.
However, if even one of the paths in P p is in D(G;G 0 ) then the
algorithm must select the test in order to be safe.
Given this insight, we can now define what it means for a CRTS
algorithm to be edge-optimal:
A CRTS algorithm is edge-optimal if for any path p
such that P p ' I(G;G 0
), the algorithm reports that p is
in I(G;G 0
5 Note that if v and v 0 are equivalent then w must
be defined since BB(v 0 ) is identical to BB(v).
6 Note that no such paths can exist if G is acyclic. In this case,
each complete path has a different set of edges than all other complete
paths.
accept := facceptg
procedure
begin
for each edge do
else
else
accept then
accept [f(v;v 0 )g
ni
od

Figure

2: Constructing the intersection graph of G and G 0 via
a synchronous depth-first search of the two graphs. The algorithm
also determines the set of vertices V 00
accept from which
accept is reachable.
accept
reject
accept
reject
accept
reject
Rothermel/Harrold algorithm Partial-reachability algorithm Full-reachability algorithm
accept
reject
Valid-reachability algorithm

Figure

3: The four edge-based CRTS algorithms, summarized pictorially with the intersection graph. The dotted outline represents V 00
accept , the
vertices of G 00 from which accept is reachable.
Algorithm Time Space Precision Edge-optimal?
Rothermel/Harrold O(jEj \Delta (jE
Partial-reachability O(jEj \Delta (jE
Full-reachability O(jEj \Delta jE

Table

1: Comparison of four edge-based CRTS algorithms.
We first present the Rothermel/Harrold (RH) algorithm, restated in
terms of the intersection graph. We then present three new algo-
rithms, culminating in an edge-optimal algorithm. Figure 3 illustrates
what the RH algorithm and each of the four algorithms does,
using the intersection graph. 7 Each picture shows the start vertex
states reject and accept. The dotted outline represents
accept , the vertices of G 00 from which accept is reachable.
ffl The RH algorithm detects whether or not E p covers an edge incident
to reject. If it does not, then path p must be in I(G;G 0
ffl The partial-reachability algorithm detects whether or not E p
covers a path in the intersection graph from an edge leaving
accept to the reject vertex. Again, if no such path exists then
p is in I(G;G 0 ). A surprising result is that partial-reachability
of reject can be determined with time and space complexity
equivalent to the RH algorithm. This algorithm is more precise
than the RH algorithm since it may be the case that E p contains
an edge incident to reject but does not cover a partial path from
a vertex in V 00
accept to reject.
ffl The full-reachability algorithm determines whether or not E p
covers a path from (s; s 0 ) to reject. If not, then p is in I(G;G 0 ).
This algorithm is more precise than the partial-reachability al-
gorithm, but at a greater cost. However, it is still not edge-
optimal.
ffl The valid-reachability algorithm makes use of a partial order
v on edges in G to rule out certain "invalid" paths. We show
that if P cannot cover a valid reaching
path to reject from (s; s ), yielding an edge-optimal algorithm.

Table

1 summarizes the time and space complexity for the four al-
gorithms. T represents the set of tests on which G has been run.
All edge-based CRTS algorithms incur a storage cost of O(jEj \Delta jT
for the edge coverage information stored for each test in T , which
we factor out when discussing the space complexity of these algorithms

7 If s is not equivalent to s 0 , then I(G;G 0 ) is empty. We assume
that all four algorithms initially check this simple condition before
proceeding.
4.1 The Rothermel-Harrold Algorithm
We now present the RH algorithm in terms of the intersection graph
The RH algorithm first computes the set D of control
transitions incident to reject (using a synchronous depth-first
search of graphs G and G 0 similar to that in Figure 2):
Given D and an edge set E p , the RH algorithm then operates as
must be in I(G;G 0
since it contains
no transition from D, which is required for p to be in D(G;G 0
Otherwise, conservatively assume that p is in D(G;G 0
Consider the intersection graph of Figure 1. For this graph,
)g. Since every path from A to X in graph G contains
one of these transitions, the RH algorithm will require all tests to be
rerun on G 0 . However, in this example, for any path p in I(G;G 0 ),
so the RH algorithm is not edge-optimal. Consider
such a path
The transitions of G 00 covered by E p are shown as bold edges in

Figure

1. There is no complete path other than p that covers exactly
the transitions (A; f ), (C;t) and (W;e).
The time and space complexity to compute D is clearly the same as
that for the depth-first search algorithm of Figure 2. To compute, for
all tests t in a set of tests T , whether or not the set of edges covered
by G(t) contains a transition from D, takes O(jEj \Delta jT time. Thus,
the RH algorithm has an overall running time of O(jEj \Delta (jE
and space complexity of O(jV j \Delta jV 0 j).
Rothermel and Harrold show that if G and G 0 do not have a
"multiply-visited vertex" then their algorithm will never report that
p is in D(G;G 0
actually is in I(G;G 0
). This means that
their algorithm is optimal (and thus edge-optimal) for this class of
graphs. Stated in terms of the intersection graph G 00 , a vertex v in G
is a "multiply-visited vertex" if:
So in

Figure

vertex C of graph G is a multiply-visited vertex.
Rothermel and Harrold ran their algorithm on a set of seven small
A,A
U,U
f
f
f
f
G"
reject
accept
A
U
f
f
Y
G'
U
f
f
f
G A
if A {
{ U }
if C { Y }
} else {
if C { W }
if A {
{ U }
if C { W }

Figure

4: An example that shows that the partial-reachability algorithm is not edge-optimal.
programs (141-512 lines of code, 132 modified versions) and one
larger program (49,000 lines of code, 5 modified versions), and
found that the multiply-visited vertex condition did not occur for
these programs and their versions [12]. Further experimentation is
clearly needed on larger and more diverse sets of programs to see
how often this condition arises.
4.2 The Partial-reachability Algorithm
Let us reconsider the example of Figure 1. The dotted outline in
graph G 00 shows the set V 00
accept . The only transition leaving this set
is (A;t). Any path leading to reject must include this transition.
Thus, if this transition is not in E p then p must be in I(G;G 0 ), as is
the case with path
which has E (C;t);(W;e)g.
Consider the projection of E p onto the edge set of G
and the graph G 00
results (the edges of E 00
are shown
in bold in Figure 1). It is straightforward to see that, in general, for
any edge v 00 ! w 00 in G 00
reject must be reachable
from w 00 in G 00
. Therefore, for an edge
in V 00
accept and w 00 is not in V 00
accept it must be the case that reject is
reachable from w 00 .
This observation leads to the partial-reachability algorithm which
has time and space complexity identical to that of the RH algorithm,
yet is more precise. This algorithm does not require construction
of G 00
p , but is able to determine whether or not reject is partially-
reachable from an edge leaving V 00
accept .
Similar to the RH algorithm, this algorithm first computes a set
D reject of transitions in G using the intersection
accept g
The set D reject contains transitions in G that transfer control out of
accept . The algorithm then operates as follows: If /then p is in I(G;G 0 ), since p must contain a transition from D reject
in order to be in D(G;G 0 ). Otherwise, conservatively assume that p
is in D(G;G 0
It is easy to see that the partial-reachability algorithm subsumes the
RH algorithm, since whenever reject is not empty,
will not be empty. Stated another way, whenever the RH algorithm
reports that p is in I(G;G 0 ), the partial-reachability algorithm will
report the same.
As shown in Figure 2, the set V 00
accept can be determined during
construction of the intersection graph, in O(jEj \Delta jE 0
space. To compute D reject takes O(jEj
simply requires visiting every edge e 00 in E 00 to determine if e 00
leaves
accept . If so, then the transition e in G corresponding to
e 00 is added to D reject . Once D reject has been computed, the rest of
the algorithm is identical to the RH algorithm: for each test in T ,
check whether or not the set of edges covered by the test has an edge
in D reject . Thus, the time and space complexity of this algorithm is
identical to the RH algorithm.
4.3 The Full-reachability Algorithm

Figure

4 shows that the partial-reachability algorithm is not edge-
optimal. In this example, the intersection graph G 00 has
Thus, for the path which is in I(G;G 0
and for which P p ' I(G;G 0
both the RH algorithm and partial-
reachability algorithm will fail to report that p is in I(G;G 0
since
transition (C;t) is covered by path p. Note, however, that in G 00
p the
reject vertex is not reachable from (s; s 0 ).
In general, either reject or accept must be reachable from (s; s 0 )
in G 00
. The full-reachability algorithm is simple: If reject is not
reachable in G 00
then p is in I(G;G 0
Otherwise, conservatively
assume that p is in D(G;G 0
Consider graph G in Figure 4. Any complete path in G containing
U
while A { }
G
A
f
U U
if A {
if A {
while A { }
} else { Y }
f
f
U,U
f
f
f
A 3
G'
Y
U
reject
accept

Figure

5: An example that shows that the full-reachability algorithm is not edge-optimal.
the transition additionally, does not contain
the transition (A;t). Therefore, for any such path p, vertex reject is
not reachable from vertex (A;A) in G 00
.
The DFS algorithm in Figure 2 can be easily modified to compute
the reachability of reject in G 00
p , but must be run for each test in T ,
resulting in an overall running time of O(jEj \Delta jE j). The space
complexity remains the same as before.
4.4 The Valid-reachability Algorithm: An
Edge-optimal Algorithm
As shown in Figure 5, the full-reachability algorithm is not edge-
optimal. Consider the path
in graph G, which is in I(G;G 0
) and has coverage
)g. Every path in G that covers exactly these
transitions is in I(G;G 0
). Nonetheless, the projection of E p onto G 00
yields a graph in which reject is reachable from (U;U) via the path
However, notice that for any path in graph G that includes both the
transitions (A;t) and (A; f ), the first occurrence of the transition
(A;t) in the path must occur before the first occurrence of (A; f ).
Therefore, all paths in P p must have this property, since by definition
they cover (A;t), (A; f ), and (U;e). While the set of transitions
in the path by which reject is reachable in G 00
includes (U;e) and
does not include (A;t) before (A; f ). So, this path cannot
be in P p and should be ignored.
The problem then is that the full-reachability algorithm considers
paths that are not in P p but reach reject in G 00
. By refining the
notion of reachability, we arrive at an edge-optimal algorithm. We
define a partial order on the edges of graph G as follows:
containing both edges
e and f , the first instance of e in p precedes the first instance
of f in p.
We leave it to the reader to prove that v is indeed a partial order
(it is anti-symmetric, transitive, and reflexive). An equivalent but
constructive definition of v follows:
dominates f 8 or ( f is reachable from e, and e
is not reachable from f ).
The v relation for graph G in Figure 5 is (U;e) v (A;t) v (A; f ).
The valid-reachability algorithm is based on the following observa-
tion: If a path q contains a transition f 2 E p but does not contain
a transition e 2 E p such that e v f in G, then any path with q as a
prefix cannot be a member of P p . We say that such a path does not
respect v.
The valid-reachability algorithm first checks if reject is reachable
from (s; s 0 ) in G 00
. If not, then p is in I(G;G 0 ), as before. If (s; s 0 ) is
reachable, the algorithm computes R 00 , the set of transitions in G 00
that are reachable from (s; s 0
) and from which reject is reachable. It
also computes the projection R of these transitions onto G. That is,
R is a subset of E p . If E p contains edges e and f such that
e 62 R, f 2 R and e v f , then the algorithm outputs that p is in
). Otherwise, the algorithm conservatively assumes that p is
in D(G;G 0
It is straightforward to show that the valid-reachability algorithm is
safe. The following theorem shows that it is also edge-optimal:
Theorem 3 Given graphs G and G 0 and their intersection graph
G 00 . If P p ' I(G;G 0 ) for any complete path p in G, then either
ffl reject is not reachable from (s; s 0
p , or
Proof: If reject is not reachable in G 00
then we are done. Instead,
suppose that reject is reachable from (s; s 0 ) in G 00
. Furthermore,
assume that for all f 2 R and e Given
these assumptions, we will show that there is a complete path q in
) such that E contradicting our initial assumption
that all paths with edge coverage equal to E p are in I(G;G 0
There are two parts to the proof: 1. show that there is a path q 1 in G
from entry to v that covers only transitions from R, respects v and
8 An edge e dominates edge f in graph G if every path from s to
f in G contains e.
U
while A { }
G
A
f
U
f
f
f
G"
U,U
f
f
f
A 3
U
U
if A {
if A {
while A { }
V2reject
accept

Figure

An example for which any CRTS algorithm based on edge coverage cannot distinguish a path in I(G;G 0
) from a path in D(G;G ).
induces a path in G 00 from (s; s ) to reject; 2. show that there is a
path q 2 from v to x in G that covers the transitions in
does not cover a transition outside E p . The concatenation of paths
yields a path q in D(G;G 0 ) such that E
The existence of path q 1 follows from the closure property of R
with respect to v (if f 2 R, e 2 E p and e v f then e 2 R), and the
fact that R is the projection of R 00 , the transitions by which reject is
reachable from (s; s 0 ) in G 00
.
We now show the existence of path q 2 . Let e be the last edge in
path q 1 . Since E p is the edge coverage of a complete path p, it
follows that for all edges e and f in E p , either f is reachable from e
in G via transitions in E p or e is reachable from f via transitions in
. Since the path q 1 respects v, it also follows that for all edges
f in cannot be related by v. In
the former case, f is reachable from e via transitions in E p . In the
latter case, edges e and f are not related by v, so it follows that e
and f must both be reachable from the other via transitions in E p ,
completing our proof.
The time complexity of the valid-reachability algorithm is O(jEj \Delta
j). The algorithm requires, for each test in T , the construction
of G 00
p and the set R, which takes time O(jEj \Delta jE 0 j), dominating
all other steps in the algorithm. Using an extended version of the
Lengauer/Tarjan immediate dominator algorithm [8], the immediate
v relation for G can be computed in near-linear time and space
in the size of G. To determine whether or not the set of edges R
is closed with respect to E p and v requires the following steps: 1.
projecting to create v p , an O(E) operation; 2. visiting
each immediate relation e v p f to check if e 62 R and f 2 R. As two
constant-time set membership operations are performed for each
immediate v p relation, of which there are O(E), this step takes
O(E) time. The space complexity of the valid-reachability algorithm
remains at O(jV j \Delta jV 0 j).
5 CRTS Using Path Coverage

Figure

6 shows that any CRTS algorithm based on edge coverage
can be forced to make an incorrect (but safe) decision. It presents
two programs, their graphs G and G 0 , and their intersection graph
is in I(G;G 0 ). The path p has )g. This is
exactly the same set of edges covered by any path in D(G;G 0 ), such
as:
Thus, it is impossible to determine whether a path in I(G;G ) or in
produced the edge set E p .
We consider how the path profiling technique of Am-
mons/Ball/Larus (ABL) [2] applied to the graphs in Figure 6
can separate the paths p and q. The ABL algorithm decomposes
a control flow graph into acyclic paths based on the backedges
identified by a depth-first search from s. Suppose that v ! w is a
backedge. The ABL decomposition yields four classes of paths:
(1) A path from s to x.
(2) A path from s to v, ending with backedge v ! w.
(3) A path from w to v (after execution of backedge v !w) ending
with execution of backedge v ! w.
After execution of backedge v ! w, a path from w to x.
Graph G has backedge A ! t A. Applying the ABL decomposition
to graph G in Figure 6 yields a total of four paths (corresponding to
the four types listed above):
The ABL algorithm inserts instrumentation into program P to track
whether or not each of these four paths is covered in an execution.
Recall the paths p and q that got edge-based CRTS into trouble.
Path p is composed of the paths p 2 followed by p 4 , so ABL will
record that only these two paths are covered when p executes. On
the other hand, the path q is composed of p 2 , followed by p 3 , followed
by p 4 . Thus, for this example where edge coverage could not
distinguish the two paths, the ABL path coverage does.
As mentioned in the introduction, an adversary can create a graph
G 0 such that any control-flow-based RTS algorithm that records less
than the complete path executed through G will be unable to distinguish
a path in I(G;G 0
) from a path in D(G;G 0
). This is only true
if G contains cycles, as it does in our example
In the example from Figure 6, we can defeat the ABL path coverage
by adding another if-then conditional (with basic block
the outermost conditional in program P 0 . Now, the path
is in I(G;G 0 ) and the path in which (A;t) occurs one more time,
is in D(G;G 0 ). However, both these paths cover exactly the set of
they will not be distinguished unless
longer paths are tracked. For any cutoff chosen, we can add another
level of nesting and achieve the same effect.
6 Related Work
Rothermel and Harrold define a framework for comparing different
regression test selection methods [11], based on four characteristics

ffl Inclusiveness, the ability to choose modification revealing
tests (paths in D(G;G 0
ffl Precision, the ability to eliminate or exclude tests that will not
reveal behavioral differences (paths in I(G;G 0
ffl Efficiency, the space and time requirements of the method, and
ffl Generality, the applicability of the method to different classes
of languages, modifications, etc.
Our approach shares many similarities with the RH algorithm. The
three reachability algorithms are based on control flow analysis and
edge coverage. The partial-reachability algorithm is just as inclusive
as the RH algorithm but is more precise with equivalent effi-
ciency. The full-reachability and valid-reachability algorithms are
even more precise, but at a greater cost. We have not yet considered
how to generalize our algorithms to handle interprocedural control
flow, as they have done.
Rothermel shows that the problem of determining whether or not
a new program is "modification-traversing" with respect to an old
program and a test t is PSPACE-hard [10]. Intuitively, this is because
the problem involves tracing the paths that the programs execute
and the paths can have size exponential in the input program
size (or worse). Of course, given a complete path through an old
program and a new program, it is a linear-time decision procedure
to determine if the new program contains the path. However, this
defines away the real problem: that the size of the path can be un-
bounded. We have considered the best a CRTS algorithm can do
when the amount of information recorded about a program's execution
is O(E) (edge coverage) or exponential in the number of edges
(ABL path coverage).

Summary

We have formalized control-flow-based regression test selection using
finite automata theory and the intersection graph. The partial-
reachability algorithm has time and space complexity equivalent to
the best previously known algorithm, but is more precise. In ad-
dition, we defined a strong optimality condition for edge-based regression
test selection algorithms and demonstrated an algorithm
(valid-reachability) that is edge-optimal. Finally, we considered
how path coverage can be used to further improve regression test
selection.
A crucial question on which the practical relevance of our work
hinges is whether or not the "multiply-visited" vertex condition defined
by Rothermel and Harrold occurs in practice. For versions of
programs that do not have this condition, the RH algorithm is op-
timal. When this condition does occur, as we have shown, the RH
algorithm is not even edge-optimal. We plan to analyze the extensive
version control repositories of systems in Lucent [3] to address
this question.

Acknowledgements

Thanks to Mooly Sagiv and Patrice Godefroid for their suggestions
pertaining to finite state theory. Thanks also to Glenn Bruns, Mary
Jean Harrold, Gregg Rothermel, Mike Siff, Mark Staskauskas and
Peter Mataga for their comments.



--R


Exploiting hardware performance counters with flow and context sensitive profiling.
If your version control system could talk.
Optimally profiling and tracing pro- grams
Incremental program testing using program dependence graphs.
A system for selective regression testing.
Introduction to Automata The- ory
A fast algorithm for finding dominators in a flow graph.
Using data flow analysis for regression testing.
Efficient, Effective Regression Testing Using Safe Test Selection Techniques.
Analyzing regression test selection techniques.

--TR
Compilers: principles, techniques, and tools
Incremental program testing using program dependence graphs
Optimally profiling and tracing programs
Analyzing Regression Test Selection Techniques
A safe, efficient regression test selection technique
TestTube
Exploiting hardware performance counters with flow and context sensitive profiling
A fast algorithm for finding dominators in a flowgraph
Introduction To Automata Theory, Languages, And Computation
Efficient, effective regression testing using safe test selection techniques

--CTR
Amitabh Srivastava , Jay Thiagarajan, Effectively prioritizing tests in development environment, ACM SIGSOFT Software Engineering Notes, v.27 n.4, July 2002
Guoqing Xu, A regression tests selection technique for aspect-oriented programs, Proceedings of the 2nd workshop on Testing aspect-oriented programs, p.15-20, July 20-20, 2006, Portland, Maine
Mary Jean Harrold , Gregg Rothermel , Rui Wu , Liu Yi, An empirical investigation of program spectra, ACM SIGPLAN Notices, v.33 n.7, p.83-90, July 1998
Alessandro Orso , Nanjuan Shi , Mary Jean Harrold, Scaling regression testing to large software systems, ACM SIGSOFT Software Engineering Notes, v.29 n.6, November 2004
Gregg Rothermel , Roland J. Untch , Chengyun Chu, Prioritizing Test Cases For Regression Testing, IEEE Transactions on Software Engineering, v.27 n.10, p.929-948, October 2001
Mary Jean Harrold , James A. Jones , Tongyu Li , Donglin Liang , Alessandro Orso , Maikel Pennings , Saurabh Sinha , S. Alexander Spoon , Ashish Gujarathi, Regression test selection for Java software, ACM SIGPLAN Notices, v.36 n.11, p.312-326, 11/01/2001
Gregg Rothermel , Mary Jean Harrold, Empirical Studies of a Safe Regression Test Selection Technique, IEEE Transactions on Software Engineering, v.24 n.6, p.401-419, June 1998
John Bible , Gregg Rothermel , David S. Rosenblum, A comparative study of coarse- and fine-grained safe regression test-selection techniques, ACM Transactions on Software Engineering and Methodology (TOSEM), v.10 n.2, p.149-183, April 2001
Mary Jean Harrold , David Rosenblum , Gregg Rothermel , Elaine Weyuker, Empirical Studies of a Prediction Model for Regression Test Selection, IEEE Transactions on Software Engineering, v.27 n.3, p.248-263, March 2001
Jianjun Zhao , Tao Xie , Nan Li, Towards regression test selection for AspectJ programs, Proceedings of the 2nd workshop on Testing aspect-oriented programs, p.21-26, July 20-20, 2006, Portland, Maine
Guoqing Xu , Atanas Rountev, Regression Test Selection for AspectJ Software, Proceedings of the 29th International Conference on Software Engineering, p.65-74, May 20-26, 2007
Nancy J. Wahl, An overview of regression testing, ACM SIGSOFT Software Engineering Notes, v.24 n.1, p.69-73, Jan. 1999
profiling;coverage;control flow analysis;regression testing