Overview Graph Coverage Criteria
O
v
e
r
v
i
e
w
G
r
a
p
h
C
o
v
e
r
a
g
e
C
r
i
t
e
r
i
a
(
I
n
t
r
o
d
u
c
t
i
o
n
t
o
S
o
f
t
w
a
r
e
T
e
s
t
i
n
g
C
h
a
p
t
e
r
2
.
1
,
2
.
2
)
Paul Ammann & Jeff Offutt
Paul Ammann & Jeff Offutt
Hierarchy of S
tructural/graph
SW Coverages
2
/60
Complete Value
Coverage
CVC
(SW) Model checking
Concolic testing
C
o
v
e
r
i
n
g
G
r
a
p
h
s
(
2
.
1
)
Graphs are the most
Graphs are the most
commonly
commonly
used structure for testing
used structure for testing
Graphs can come from
Graphs can come from
many sources
many sources
Control flow graphs
Control flow graphs
Design structure
Design structure
FSMs and statecharts
FSMs and statecharts
Use cases
Use cases
Tests usually are intended to “
Tests usually are intended to “
cover
cover
” the graph in some way
” the graph in some way
3
D
e
f
i
n
i
t
i
o
n
o
f
a
G
r
a
p
h
A set
A set
N
N
of
of
nodes
nodes
,
,
N
N
is not empty
is not empty
A set
A set
N
N
0
0
of
of
initial nodes
initial nodes
,
,
N
N
0
0
is not empty
is not empty
A set
A set
N
N
f
f
of
of
final nodes
final nodes
,
,
N
N
f
f
is not empty
is not empty
A set
A set
E
E
of
of
edges
edges
, each edge from one node to another
, each edge from one node to another
(
(
n
n
i
i
,
,
n
n
j
j
),
),
i
i
is
is
predecessor
predecessor
,
,
j
j
is
is
successor
successor
4
T
h
r
e
e
E
x
a
m
p
l
e
G
r
a
p
h
s
5
N
0
= { 0 }N
f
= { 3 }N
0
= { }N
f
= { 3 }N
0
= { 0, 1, 2 }N
f
= { 7, 8, 9 }Not a
Not a
valid
valid
graph
graph
P
a
t
h
s
i
n
G
r
a
p
h
s
Path
Path
: A sequence of nodes – [n
: A sequence of nodes – [n
1
1
, n
, n
2
2
, …, n
, …, n
M
M
]
]
Each pair of nodes is an edge
Each pair of nodes is an edge
Length
Length
:
:
The number of edges
The number of edges
A single node is a path of length 0
A single node is a path of length 0
Subpath
Subpath
:
:
A subsequence of nodes in
A subsequence of nodes in
p
p
is a subpath of
is a subpath of
p
p
Reach
Reach
(
(
n
n
) : Subgraph that can be reached from
) : Subgraph that can be reached from
n
n
6
Paths
[ 0, 3, 7 ]
[ 1, 4, 8, 5, 1 ]
[ 2, 6, 9 ]
Reach (0) = { 0, 3, 4,7, 8, 5, 1, 9 }
Reach ({0, 2}) = GReach([2,6]) = {2, 6,9}
T
e
s
t
P
a
t
h
s
a
n
d
S
E
S
E
s
Test Path
Test Path
: A path that starts at an initial node and ends at a
: A path that starts at an initial node and ends at a
final node
final node
Test paths represent execution of test cases
Test paths represent execution of test cases
Some test paths can be executed by many tests
Some test paths can be executed by many tests
Some test paths cannot be executed by
Some test paths cannot be executed by
any
any
tests
tests
SESE graphs
SESE graphs
: All test paths start at a single node and end
: All test paths start at a single node and end
at another node
at another node
Single-entry, single-exit
Single-entry, single-exit
N0 and Nf have exactly one node
N0 and Nf have exactly one node
7
Double-diamond graph
Four test paths
[ 0, 1, 3, 4, 6 ]
[ 0, 1, 3, 5, 6 ]
[ 0, 2, 3, 4, 6 ]
[ 0, 2, 3, 5, 6 ]
V
i
s
i
t
i
n
g
a
n
d
T
o
u
r
i
n
g
Visit
Visit
:
:
A test path
A test path
p
p
visits
visits
node
node
n
n
if
if
n
n
is in
is in
p
p
A test path
A test path
p
p
visits
visits
edge
edge
e
e
if
if
e
e
is in
is in
p
p
Tour
Tour
: A test path
: A test path
p
p
tours
tours
subpath
subpath
q
q
if
if
q
q
is a subpath of
is a subpath of
p
p
8
Path [ 0, 1, 3, 4, 6 ]
Visits nodes 0, 1, 3, 4, 6
Visits edges (0, 1), (1, 3), (3, 4), (4, 6)
Tours subpaths (0, 1, 3), (1, 3, 4), (3, 4, 6), (0, 1, 3, 4), (1, 3, 4, 6)
T
e
s
t
s
a
n
d
T
e
s
t
P
a
t
h
s
path
path
(
(
t
t
)
)
: The test path executed by test
: The test path executed by test
t
t
path
path
(
(
T
T
)
)
: The set of test paths executed by the set of tests
: The set of test paths executed by the set of tests
T
T
Each test executes
Each test executes
one and only one
one and only one
test path
test path
A location in a graph (node or edge) can be
A location in a graph (node or edge) can be
reached
reached
from
from
another location if there is a sequence of edges from the first
another location if there is a sequence of edges from the first
location to the second
location to the second
Syntactic
Syntactic
reach
reach
: A subpath exists in the graph
: A subpath exists in the graph
Semantic
Semantic
reach
reach
: A test exists that can execute that subpath
: A test exists that can execute that subpath
9
T
e
s
t
s
a
n
d
T
e
s
t
P
a
t
h
s
10
test 1
test 2
test 3
T
e
s
t
i
n
g
a
n
d
C
o
v
e
r
i
n
g
G
r
a
p
h
s
(
2
.
2
)
We use graphs in testing as follows :
We use graphs in testing as follows :
Developing a model of the software as a graph
Developing a model of the software as a graph
Requiring tests to visit or tour specific sets of nodes, edges or subpaths
Requiring tests to visit or tour specific sets of nodes, edges or subpaths
11
•
T
e
s
t
R
e
q
u
i
r
e
m
e
n
t
s
(
T
R
)
:
D
e
s
c
r
i
b
e
p
r
o
p
e
r
t
i
e
s
o
f
t
e
s
t
p
a
t
h
s
•
T
e
s
t
C
r
i
t
e
r
i
o
n
:
R
u
l
e
s
t
h
a
t
d
e
f
i
n
e
t
e
s
t
r
e
q
u
i
r
e
m
e
n
t
s
•
S
a
t
i
s
f
a
c
t
i
o
n
:
G
i
v
e
n
a
s
e
t
T
R
o
f
t
e
s
t
r
e
q
u
i
r
e
m
e
n
t
s
f
o
r
a
c
r
i
t
e
r
i
o
n
C
,
a
s
e
t
o
f
t
e
s
t
s
T
s
a
t
i
s
f
i
e
s
C
o
n
a
g
r
a
p
h
i
f
a
n
d
o
n
l
y
i
f
f
o
r
e
v
e
r
y
t
e
s
t
r
e
q
u
i
r
e
m
e
n
t
i
n
T
R
,
t
h
e
r
e
i
s
a
t
e
s
t
p
a
t
h
i
n
p
a
t
h
(
T
)
t
h
a
t
m
e
e
t
s
t
h
e
t
e
s
t
r
e
q
u
i
r
e
m
e
n
t
t
r
•
S
t
r
u
c
t
u
r
a
l
C
o
v
e
r
a
g
e
C
r
i
t
e
r
i
a
:
D
e
f
i
n
e
d
o
n
a
g
r
a
p
h
j
u
s
t
i
n
t
e
r
m
s
o
f
n
o
d
e
s
a
n
d
e
d
g
e
s
•
D
a
t
a
F
l
o
w
C
o
v
e
r
a
g
e
C
r
i
t
e
r
i
a
:
R
e
q
u
i
r
e
s
a
g
r
a
p
h
t
o
b
e
a
n
n
o
t
a
t
e
d
w
i
t
h
r
e
f
e
r
e
n
c
e
s
t
o
v
a
r
i
a
b
l
e
s
N
o
d
e
a
n
d
E
d
g
e
C
o
v
e
r
a
g
e
Edge coverage is slightly stronger than node coverage
Edge coverage is slightly stronger than node coverage
12
•
T
h
e
“
l
e
n
g
t
h
u
p
t
o
1
”
a
l
l
o
w
s
f
o
r
g
r
a
p
h
s
w
i
t
h
o
n
e
n
o
d
e
a
n
d
n
o
e
d
g
e
s
•
N
C
a
n
d
E
C
a
r
e
o
n
l
y
d
i
f
f
e
r
e
n
t
w
h
e
n
t
h
e
r
e
i
s
a
n
e
d
g
e
a
n
d
a
n
o
t
h
e
r
s
u
b
p
a
t
h
b
e
t
w
e
e
n
a
p
a
i
r
o
f
n
o
d
e
s
(
a
s
i
n
a
n
“
i
f
-
e
l
s
e
”
s
t
a
t
e
m
e
n
t
)
Node Coverage
: TR = { 0, 1, 2 }Test Path = [ 0, 1, 2 ]
Edge Coverage
: TR = { (0,1), (0, 2), (1, 2) }Test Paths = [ 0, 1, 2 ]
[ 0, 2 ]
P
a
t
h
s
o
f
L
e
n
g
t
h
1
a
n
d
0
A graph with
A graph with
only one node
only one node
will not have any edges
will not have any edges
13
•
I
t
m
a
y
b
e
b
o
r
i
n
g
,
b
u
t
f
o
r
m
a
l
l
y
,
E
d
g
e
C
o
v
e
r
a
g
e
n
e
e
d
s
t
o
r
e
q
u
i
r
e
N
o
d
e
C
o
v
e
r
a
g
e
o
n
t
h
i
s
g
r
a
p
h
•
O
t
h
e
r
w
i
s
e
,
E
d
g
e
C
o
v
e
r
a
g
e
w
i
l
l
n
o
t
s
u
b
s
u
m
e
N
o
d
e
C
o
v
e
r
a
g
e
–
S
o
w
e
d
e
f
i
n
e
“
l
e
n
g
t
h
u
p
t
o
1
”
i
n
s
t
e
a
d
o
f
s
i
m
p
l
y
“
l
e
n
g
t
h
1
”
•
W
e
h
a
v
e
t
h
e
s
a
m
e
i
s
s
u
e
w
i
t
h
g
r
a
p
h
s
t
h
a
t
o
n
l
y
h
a
v
e
o
n
e
e
d
g
e
–
f
o
r
E
d
g
e
P
a
i
r
C
o
v
e
r
a
g
e
…
C
o
v
e
r
i
n
g
M
u
l
t
i
p
l
e
E
d
g
e
s
Edge-pair coverage requires
Edge-pair coverage requires
pairs of edges
pairs of edges
, or subpaths of
, or subpaths of
length 2
length 2
14
•
T
h
e
“
l
e
n
g
t
h
u
p
t
o
2
”
i
s
u
s
e
d
t
o
i
n
c
l
u
d
e
g
r
a
p
h
s
t
h
a
t
h
a
v
e
l
e
s
s
t
h
a
n
2
e
d
g
e
s
•
T
h
e
l
o
g
i
c
a
l
e
x
t
e
n
s
i
o
n
i
s
t
o
r
e
q
u
i
r
e
a
l
l
p
a
t
h
s
…
•
U
n
f
o
r
t
u
n
a
t
e
l
y
,
t
h
i
s
i
s
i
m
p
o
s
s
i
b
l
e
i
f
t
h
e
g
r
a
p
h
h
a
s
a
l
o
o
p
,
s
o
a
w
e
a
k
c
o
m
p
r
o
m
i
s
e
i
s
t
o
m
a
k
e
t
h
e
t
e
s
t
e
r
d
e
c
i
d
e
w
h
i
c
h
p
a
t
h
s
:
S
t
r
u
c
t
u
r
a
l
C
o
v
e
r
a
g
e
E
x
a
m
p
l
e
15
Node Coverage
TR
NC
= { 0, 1, 2, 3, 4, 5, 6 }Test Paths: [ 0, 1, 2, 3, 6 ] [ 0, 1, 2, 4, 5, 4, 6 ]
Edge Coverage
TR
EC
={(0,1),(0,2),(1,2), (2,3), (2,4), (3,6), (4,5),(4,6), (5,4)}Test Paths: [ 0, 1, 2, 3, 6 ] [ 0, 2, 4, 5, 4, 6 ]
Edge-Pair Coverage
TR
EPC
= { [0,1,2], [0,2,3], [0,2,4], [1,2,3], [1,2,4], [2,3,6],[2,4,5], [2,4,6], [4,5,4], [5,4,5], [5,4,6] }
Test Paths: [ 0, 1, 2, 3, 6 ] [ 0, 1, 2, 4, 6 ] [ 0, 2, 3, 6 ]
[ 0, 2, 4, 5, 4, 5, 4, 6 ]
Complete Path Coverage
Test Paths: [ 0, 1, 2, 3, 6 ] [ 0, 1, 2, 4, 6 ] [ 0, 1, 2, 4, 5, 4, 6 ]
[ 0, 1, 2, 4, 5, 4, 5, 4, 6 ] [ 0, 1, 2,
4, 5, 4, 5, 4, 5
, 4, 6 ] …
L
o
o
p
s
i
n
G
r
a
p
h
s
If a graph contains a loop, it has an
If a graph contains a loop, it has an
infinite
infinite
number of
number of
paths
paths
Thus, CPC is
Thus, CPC is
not feasible
not feasible
SPC is not satisfactory because the results are
SPC is not satisfactory because the results are
subjective
subjective
and vary with the tester
and vary with the tester
Attempts to “deal with”
Attempts to “deal with”
loops:
loops:
1980s
1980s
: Execute each loop, exactly once ([4, 5, 4] in previous example)
: Execute each loop, exactly once ([4, 5, 4] in previous example)
1990s
1990s
: Execute loops 0 times, once, more than once
: Execute loops 0 times, once, more than once
2000s
2000s
: Prime paths
: Prime paths
16
S
i
m
p
l
e
P
a
t
h
s
a
n
d
P
r
i
m
e
P
a
t
h
s
Simple Path
Simple Path
:
:
A path from node n
A path from node n
i
i
to n
to n
j
j
is simple, if no node
is simple, if no node
appears more than once, except possibly the first and last
appears more than once, except possibly the first and last
nodes are the same
nodes are the same
No internal loops
No internal loops
Includes all other subpaths
Includes all other subpaths
A loop is a simple path
A loop is a simple path
Prime Path
Prime Path
:
:
A simple path that does
A simple path that does
not
not
appear as a proper
appear as a proper
subpath of any other simple path
subpath of any other simple path
17
Simple Paths
: [ 0, 1, 3, 0 ], [ 0, 2, 3, 0], [ 1, 3, 0, 1 ],
[ 2, 3, 0, 2 ], [ 3, 0, 1, 3 ], [ 3, 0, 2, 3 ], [ 1, 3, 0, 2 ],
[ 2, 3, 0, 1 ], [ 0, 1, 3 ], [ 0, 2, 3 ], [ 1, 3, 0 ], [ 2, 3, 0 ],
[ 3, 0, 1 ], [3, 0, 2 ], [ 0, 1], [ 0, 2 ], [ 1, 3 ], [ 2, 3 ], [ 3, 0 ],
[0], [1], [2], [3]
Prime Paths
: [ 0, 1, 3, 0 ], [ 0, 2, 3, 0], [ 1, 3, 0, 1 ],
[ 2, 3, 0, 2 ], [ 3, 0, 1, 3 ], [ 3, 0, 2, 3 ], [ 1, 3, 0, 2 ],
[ 2, 3, 0, 1 ]
P
r
i
m
e
P
a
t
h
C
o
v
e
r
a
g
e
A simple, elegant and finite criterion that requires
A simple, elegant and finite criterion that requires
loops
loops
to be
to be
executed as well as skipped
executed as well as skipped
18
•
W
i
l
l
t
o
u
r
a
l
l
p
a
t
h
s
o
f
l
e
n
g
t
h
0
,
1
,
…
•
T
h
a
t
i
s
,
i
t
s
u
b
s
u
m
e
s
n
o
d
e
,
e
d
g
e
,
a
n
d
e
d
g
e
-
p
a
i
r
c
o
v
e
r
a
g
e
P
r
i
m
e
P
a
t
h
E
x
a
m
p
l
e
The previous example has 38
The previous example has 38
simple
simple
paths
paths
Only
Only
nine
nine
prime paths
prime paths
19
Prime Paths
[ 0, 1, 2, 3, 6 ]
[ 0, 1, 2, 4, 5 ]
[ 0, 1, 2, 4, 6 ]
[ 0, 2, 3, 6 ]
[ 0, 2, 4, 5]
[ 0, 2, 4, 6 ]
[ 5, 4, 6 ]
[ 4, 5, 4 ]
[ 5, 4, 5 ]
Execute
loop once
Execute loop
more than once
Execute
loop 0 times
‘!’ means path
terminates
Len 2
[0, 1, 2]
[0, 2, 3]
[0, 2, 4]
[1, 2, 3]
[1, 2, 4]
[2, 3, 6] !
[2, 4, 6] !
[2, 4, 5] !
[4, 5, 4] *
[5, 4, 6] !
[5, 4, 5] *
S
i
m
p
l
e
&
P
r
i
m
e
P
a
t
h
E
x
a
m
p
l
e
20
Len 0
[0]
[1]
[2]
[3]
[4]
[5]
[6] !
Len 1
[0, 1]
[0, 2]
[1, 2]
[2, 3]
[2, 4]
[3, 6] !
[4, 6] !
[4, 5]
[5, 4]
‘*’ means path
cycles
Len 3
[0, 1, 2, 3]
[0, 1, 2, 4]
[0, 2, 3, 6] !
[0, 2, 4, 6] !
[0, 2, 4, 5] !
[1, 2, 3, 6] !
[1, 2, 4, 5] !
[1, 2, 4, 6] !
Len 4
[0, 1, 2, 3, 6] !
[0, 1, 2, 4, 6] !
[0, 1, 2, 4, 5] !
Simple
paths
Note that paths w/o ! or * cannot be prime paths
R
o
u
n
d
T
r
i
p
s
Round-Trip Path
Round-Trip Path
:
:
A prime path that starts and ends at the
A prime path that starts and ends at the
same node
same node
21
•
T
h
e
s
e
c
r
i
t
e
r
i
a
o
m
i
t
n
o
d
e
s
a
n
d
e
d
g
e
s
t
h
a
t
a
r
e
n
o
t
i
n
r
o
u
n
d
t
r
i
p
s
•
T
h
a
t
i
s
,
t
h
e
y
d
o
n
o
t
s
u
b
s
u
m
e
e
d
g
e
-
p
a
i
r
,
e
d
g
e
,
o
r
n
o
d
e
c
o
v
e
r
a
g
e
I
n
f
e
a
s
i
b
l
e
T
e
s
t
R
e
q
u
i
r
e
m
e
n
t
s
An
An
infeasible
infeasible
test requirement
test requirement
cannot be satisfied
cannot be satisfied
Unreachable statement (dead code)
Unreachable statement (dead code)
A subpath that can only be executed if a contradiction occurs (
A subpath that can only be executed if a contradiction occurs (
X > 0
X > 0
and
and
X < 0
X < 0
)
)
22
P
r
a
c
t
i
c
a
l
r
e
c
o
m
m
e
n
d
a
t
i
o
n
–
B
e
s
t
E
f
f
o
r
t
T
o
u
r
i
n
g
–
S
a
t
i
s
f
y
a
s
m
a
n
y
t
e
s
t
r
e
q
u
i
r
e
m
e
n
t
s
a
s
p
o
s
s
i
b
l
e
w
i
t
h
o
u
t
s
i
d
e
t
r
i
p
s
–
A
l
l
o
w
s
i
d
e
t
r
i
p
s
t
o
t
r
y
t
o
s
a
t
i
s
f
y
u
n
s
a
t
i
s
f
i
e
d
t
e
s
t
r
e
q
u
i
r
e
m
e
n
t
s
•
M
o
s
t
t
e
s
t
c
r
i
t
e
r
i
a
h
a
v
e
s
o
m
e
i
n
f
e
a
s
i
b
l
e
t
e
s
t
r
e
q
u
i
r
e
m
e
n
t
s
•
I
t
i
s
u
s
u
a
l
l
y
u
n
d
e
c
i
d
a
b
l
e
w
h
e
t
h
e
r
a
l
l
t
e
s
t
r
e
q
u
i
r
e
m
e
n
t
s
a
r
e
f
e
a
s
i
b
l
e
•
W
h
e
n
s
i
d
e
t
r
i
p
s
a
r
e
n
o
t
a
l
l
o
w
e
d
,
m
a
n
y
s
t
r
u
c
t
u
r
a
l
c
r
i
t
e
r
i
a
h
a
v
e
m
o
r
e
i
n
f
e
a
s
i
b
l
e
t
e
s
t
r
e
q
u
i
r
e
m
e
n
t
s
•
H
o
w
e
v
e
r
,
a
l
w
a
y
s
a
l
l
o
w
i
n
g
s
i
d
e
t
r
i
p
s
w
e
a
k
e
n
s
t
h
e
t
e
s
t
c
r
i
t
e
r
i
a
T
o
u
r
i
n
g
,
S
i
d
e
t
r
i
p
s
a
n
d
D
e
t
o
u
r
s
Prime paths do not have
Prime paths do not have
internal loops
internal loops
… test paths
… test paths
might
might
23
•
T
o
u
r
:
A
t
e
s
t
p
a
t
h
p
t
o
u
r
s
s
u
b
p
a
t
h
q
i
f
q
i
s
a
s
u
b
p
a
t
h
o
f
p
•
T
o
u
r
W
i
t
h
S
i
d
e
t
r
i
p
s
:
A
t
e
s
t
p
a
t
h
p
t
o
u
r
s
s
u
b
p
a
t
h
q
w
i
t
h
s
i
d
e
t
r
i
p
s
i
f
f
e
v
e
r
y
e
d
g
e
i
n
q
i
s
a
l
s
o
i
n
p
i
n
t
h
e
s
a
m
e
o
r
d
e
r
•
T
h
e
t
o
u
r
c
a
n
i
n
c
l
u
d
e
a
s
i
d
e
t
r
i
p
,
a
s
l
o
n
g
a
s
i
t
c
o
m
e
s
b
a
c
k
t
o
t
h
e
s
a
m
e
n
o
d
e
•
T
o
u
r
W
i
t
h
D
e
t
o
u
r
s
:
A
t
e
s
t
p
a
t
h
p
t
o
u
r
s
s
u
b
p
a
t
h
q
w
i
t
h
d
e
t
o
u
r
s
i
f
f
e
v
e
r
y
n
o
d
e
i
n
q
i
s
a
l
s
o
i
n
p
i
n
t
h
e
s
a
m
e
o
r
d
e
r
S
i
d
e
t
r
i
p
s
a
n
d
D
e
t
o
u
r
s
E
x
a
m
p
l
e
24
Touring without
sidetrips or
detours
25
W
W
e
e
a
a
k
k
n
n
e
e
s
s
s
s
e
e
s
s
o
o
f
f
t
t
h
h
e
e
P
P
u
u
r
r
e
e
l
l
y
y
S
S
t
t
r
r
u
u
c
c
t
t
u
u
r
r
a
a
l
l
C
C
o
o
v
v
e
e
r
r
a
a
g
g
e
e
/* TC1: x= 1, y= 1;
TC2: x=-1, y=-1;*/
void foo(int x, int y) {if ( x > 0)
x++;
else
x--;
if(y >0)
y++;
else
y--;
assert (x * y >= 0);
}
x>0
x++
x--
yes
no
y>0
y++
y--
assert(x*y>=0)
Purely structural coverage (e.g., branch coverage) alone
cannot
improve the quality of target software sufficiently
->
Advanced semantic testing
should be accompanied
F
i
n
a
l
R
e
m
a
r
k
s
26
1. Why are coverage criteria important for testing?
2. Why is branch coverage popular in industry?
3. Why is prime path coverage not use in practice?
4. Why is it difficult to reach 100% branch coverage of
real-world programs?
Data Flow Coverage
27
D
a
t
a
F
l
o
w
C
r
i
t
e
r
i
a
Definition
Definition
: A location where a value for a variable is stored into me
: A location where a value for a variable is stored into me
mory
mory
Use
Use
: A location where a variable’s value is accessed
: A location where a variable’s value is accessed
def (n) or def (e)
def (n) or def (e)
: The set of variables that are defined by node n
: The set of variables that are defined by node n
or edge e
or edge e
use (n) or use (e)
use (n) or use (e)
: The set of variables that are used by node n or
: The set of variables that are used by node n or
edge e
edge e
28
G
o
a
l
:
T
r
y
t
o
e
n
s
u
r
e
t
h
a
t
v
a
l
u
e
s
a
r
e
c
o
m
p
u
t
e
d
a
n
d
u
s
e
d
c
o
r
r
e
c
t
l
y
Defs
: def (0) = {X} def (4) = {Z} def (5) = {Z}Uses
: use (4) = {X} use (5) = {X}D
U
P
a
i
r
s
a
n
d
D
U
P
a
t
h
s
DU pair
DU pair
: A pair of locations (
: A pair of locations (
l
l
i
i
,
,
l
l
j
j
) such that a variable
) such that a variable
v
v
is defined at
is defined at
l
l
i
i
and used at
and used at
l
l
j
j
Def-clear
Def-clear
: A path from
: A path from
l
l
i
i
to
to
l
l
j
j
is
is
def-clear
def-clear
with respect to
with respect to
variable
variable
v,
v,
if
if
v
v
is not given another value on any of the n
is not given another value on any of the n
odes or edges in the path
odes or edges in the path
Reach
Reach
: If there is a def-clear path from
: If there is a def-clear path from
l
l
i
i
to
to
l
l
j
j
with respect to
with respect to
v
v
,
,
the def of
the def of
v
v
at
at
l
l
i
i
reaches
reaches
the use at
the use at
l
l
j
j
du-path
du-path
: A
: A
simple
simple
subpath that is def-clear with respect
subpath that is def-clear with respect
to
to
v
v
from a def of
from a def of
v
v
to a use of
to a use of
v
v
du
du
(
(
n
n
i
i
,
,
n
n
j
j
,
,
v
v
)
)
– the set of du-paths from
– the set of du-paths from
n
n
i
i
to
to
n
n
j
j
du
du
(
(
n
n
i
i
,
,
v
v
)
)
– the set of du-paths that start at
– the set of du-paths that start at
n
n
i
i
29
T
o
u
r
i
n
g
D
U
-
P
a
t
h
s
A test path
A test path
p
p
du-tours
du-tours
subpath
subpath
d
d
with respect to
with respect to
v
v
if
if
p
p
tours
tours
d
d
and the subpath taken is def-clear with respect to
and the subpath taken is def-clear with respect to
v
v
Sidetrips
Sidetrips
can be used, just as with previous touring
can be used, just as with previous touring
Three criteria
Three criteria
Use every def
Use every def
Get to every use
Get to every use
Follow all du-paths
Follow all du-paths
30
D
a
t
a
F
l
o
w
T
e
s
t
C
r
i
t
e
r
i
a
31
•
T
h
e
n
w
e
m
a
k
e
s
u
r
e
t
h
a
t
e
v
e
r
y
d
e
f
r
e
a
c
h
e
s
a
l
l
p
o
s
s
i
b
l
e
u
s
e
s
•
F
i
n
a
l
l
y
,
w
e
c
o
v
e
r
a
l
l
t
h
e
p
a
t
h
s
b
e
t
w
e
e
n
d
e
f
s
a
n
d
u
s
e
s
•
F
i
r
s
t
,
w
e
m
a
k
e
s
u
r
e
e
v
e
r
y
d
e
f
r
e
a
c
h
e
s
a
u
s
e
D
a
t
a
F
l
o
w
T
e
s
t
i
n
g
E
x
a
m
p
l
e
32
G
r
a
p
h
C
o
v
e
r
a
g
e
C
r
i
t
e
r
i
a
S
u
b
s
u
m
p
t
i
o
n
33
A
s
s
u
m
p
t
i
o
n
s
f
o
r
D
a
t
a
F
l
o
w
C
o
v
e
r
a
g
e
1.
E
v
e
r
y
u
s
e
i
s
p
r
e
c
e
d
e
d
b
y
a
d
e
f
2.
E
v
e
r
y
d
e
f
r
e
a
c
h
e
s
a
t
l
e
a
s
t
o
n
e
u
s
e
3.
F
o
r
e
v
e
r
y
n
o
d
e
w
i
t
h
m
u
l
t
i
p
l
e
o
u
t
g
o
i
n
g
e
d
g
e
s
,
a
t
l
e
a
s
t
o
n
e
v
a
r
i
a
b
l
e
i
s
u
s
e
d
o
n
e
a
c
h
o
u
t
e
d
g
e
,
a
n
d
t
h
e
s
a
m
e
v
a
r
i
a
b
l
e
s
a
r
e
u
s
e
d
o
n
e
a
c
h
o
u
t
e
d
g
e
.
Software testing involves various techniques such as graph coverage criteria and test paths. This overview delves into the hierarchy of structural graph coverages, covering graphs, the definition of a graph, example graphs, paths in graphs, and test paths in SESE graphs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Overview Graph Coverage Criteria ( Introduction to Software Testing Chapter 2.1, 2.2) Paul Ammann & Jeff Offutt
Hierarchy of Structural/graph SW Coverages Complete Value Coverage CVC (SW) Model checking Complete Path Coverage CPC Concolic testing Prime Path Coverage PPC All-DU-Paths Coverage ADUP Edge-Pair Coverage EPC All-uses Coverage AUC Complete Round Trip Coverage CRTC Edge Coverage EC All-defs Coverage ADC Simple Round Trip Coverage SRTC Node Coverage NC 2/60
Covering Graphs (2.1) Graphs are the most commonly used structure for testing Graphs can come from many sources Control flow graphs Design structure FSMs and statecharts Use cases Tests usually are intended to cover the graph in some way 3
Definition of a Graph A set N of nodes, N is not empty A set N0 of initial nodes, N0 is not empty A set Nf of final nodes, Nf is not empty A set E of edges, each edge from one node to another ( ni , nj ), i is predecessor, j is successor 4
Three Example Graphs 0 1 0 2 0 Not a valid graph 3 4 5 1 2 6 1 2 7 8 3 9 3 N0 = { 0 } Nf = { 3 } N0 = { 0, 1, 2 } Nf = { 7, 8, 9 } N0 = { } Nf = { 3 } 5
Paths in Graphs Path : A sequence of nodes [n1, n2, , nM] Each pair of nodes is an edge Length : The number of edges A single node is a path of length 0 Subpath : A subsequence of nodes in p is a subpath of p Reach (n) : Subgraph that can be reached from n 0 1 2 Reach (0) = { 0, 3, 4, 7, 8, 5, 1, 9 } Paths [ 0, 3, 7 ] Reach ({0, 2}) = G 3 4 5 6 [ 1, 4, 8, 5, 1 ] Reach([2,6]) = {2, 6, 9} [ 2, 6, 9 ] 7 8 9 6
Test Paths and SESEs Test Path : A path that starts at an initial node and ends at a final node Test paths represent execution of test cases Some test paths can be executed by many tests Some test paths cannot be executed by any tests SESE graphs : All test paths start at a single node and end at another node Single-entry, single-exit N0 and Nf have exactly one node Double-diamond graph Four test paths [ 0, 1, 3, 4, 6 ] [ 0, 1, 3, 5, 6 ] [ 0, 2, 3, 4, 6 ] [ 0, 2, 3, 5, 6 ] 1 4 0 3 6 2 5 7
Visiting and Touring Visit : A test path pvisits node n if n is in p A test path pvisits edge e if e is in p Tour : A test path ptours subpath q if q is a subpath of p Path [ 0, 1, 3, 4, 6 ] Visits nodes 0, 1, 3, 4, 6 Visits edges (0, 1), (1, 3), (3, 4), (4, 6) Tours subpaths (0, 1, 3), (1, 3, 4), (3, 4, 6), (0, 1, 3, 4), (1, 3, 4, 6) 8
Tests and Test Paths path (t) : The test path executed by test t path (T) : The set of test paths executed by the set of tests T Each test executes one and only one test path A location in a graph (node or edge) can be reached from another location if there is a sequence of edges from the first location to the second Syntactic reach : A subpath exists in the graph Semantic reach : A test exists that can execute that subpath 9
Tests and Test Paths test 1 many-to-one Test Path test 2 test 3 Deterministic software a test always executes the same test path many-to-many Test Path 1 test 1 test 2 Test Path 2 test 3 Test Path 3 Non-deterministic software a test can execute different test paths 10
Testing and Covering Graphs (2.2) We use graphs in testing as follows : Developing a model of the software as a graph Requiring tests to visit or tour specific sets of nodes, edges or subpaths Test Requirements (TR) : Describe properties of test paths Test Criterion : Rules that define test requirements Satisfaction : Given a set TR of test requirements for a criterion C, a set of tests T satisfies C on a graph if and only if for every test requirement in TR, there is a test path in path(T) that meets the test requirement tr Structural Coverage Criteria : Defined on a graph just in terms of nodes and edges Data Flow Coverage Criteria : Requires a graph to be annotated with references to variables 11
Node and Edge Coverage Edge coverage is slightly stronger than node coverage The length up to 1 allows for graphs with one node and no edges NC and EC are only different when there is an edge and another subpath between a pair of nodes (as in an if- else statement) Node Coverage : TR = { 0, 1, 2 } Test Path = [ 0, 1, 2 ] 0 1 Edge Coverage : TR = { (0,1), (0, 2), (1, 2) } Test Paths = [ 0, 1, 2 ] [ 0, 2 ] 2 12
Paths of Length 1 and 0 A graph with only one node will not have any edges 0 It may be boring, but formally, Edge Coverage needs to require Node Coverage on this graph Otherwise, Edge Coverage will not subsume Node Coverage So we define length up to 1 instead of simply length 1 We have the same issue with graphs that only have one edge for Edge Pair Coverage 0 1 13
Covering Multiple Edges Edge-pair coverage requires pairs of edges, or subpaths of length 2 The length up to 2 is used to include graphs that have less than 2 edges The logical extension is to require all paths Unfortunately, this is impossible if the graph has a loop, so a weak compromise is to make the tester decide which paths: 14
Structural Coverage Example Node Coverage TRNC = { 0, 1, 2, 3, 4, 5, 6 } Test Paths: [ 0, 1, 2, 3, 6 ] [ 0, 1, 2, 4, 5, 4, 6 ] 0 Edge Coverage TREC ={(0,1),(0,2),(1,2), (2,3), (2,4), (3,6), (4,5),(4,6), (5,4)} Test Paths: [ 0, 1, 2, 3, 6 ] [ 0, 2, 4, 5, 4, 6 ] 1 Edge-Pair Coverage 2 TREPC = { [0,1,2], [0,2,3], [0,2,4], [1,2,3], [1,2,4], [2,3,6], [2,4,5], [2,4,6], [4,5,4], [5,4,5], [5,4,6] } Test Paths: [ 0, 1, 2, 3, 6 ] [ 0, 1, 2, 4, 6 ] [ 0, 2, 3, 6 ] [ 0, 2, 4, 5, 4, 5, 4, 6 ] 3 4 5 Complete Path Coverage 6 Test Paths: [ 0, 1, 2, 3, 6 ] [ 0, 1, 2, 4, 6 ] [ 0, 1, 2, 4, 5, 4, 6 ] [ 0, 1, 2, 4, 5, 4, 5, 4, 6 ] [ 0, 1, 2, 4, 5, 4, 5, 4, 5, 4, 6 ] 15
Loops in Graphs If a graph contains a loop, it has an infinite number of paths Thus, CPC is not feasible SPC is not satisfactory because the results are subjective and vary with the tester Attempts to deal with loops: 1980s : Execute each loop, exactly once ([4, 5, 4] in previous example) 1990s : Execute loops 0 times, once, more than once 2000s : Prime paths 16
Simple Paths and Prime Paths Simple Path : A path from node ni to nj is simple, if no node appears more than once, except possibly the first and last nodes are the same No internal loops Includes all other subpaths A loop is a simple path Prime Path : A simple path that does not appear as a proper subpath of any other simple path Simple Paths : [ 0, 1, 3, 0 ], [ 0, 2, 3, 0], [ 1, 3, 0, 1 ], [ 2, 3, 0, 2 ], [ 3, 0, 1, 3 ], [ 3, 0, 2, 3 ], [ 1, 3, 0, 2 ], [ 2, 3, 0, 1 ], [ 0, 1, 3 ], [ 0, 2, 3 ], [ 1, 3, 0 ], [ 2, 3, 0 ], [ 3, 0, 1 ], [3, 0, 2 ], [ 0, 1], [ 0, 2 ], [ 1, 3 ], [ 2, 3 ], [ 3, 0 ], [0], [1], [2], [3] 3 0 1 2 Prime Paths : [ 0, 1, 3, 0 ], [ 0, 2, 3, 0], [ 1, 3, 0, 1 ], [ 2, 3, 0, 2 ], [ 3, 0, 1, 3 ], [ 3, 0, 2, 3 ], [ 1, 3, 0, 2 ], [ 2, 3, 0, 1 ] 17
Prime Path Coverage A simple, elegant and finite criterion that requires loops to be executed as well as skipped Will tour all paths of length 0, 1, That is, it subsumes node, edge, and edge-pair coverage 18
Prime Path Example The previous example has 38 simple paths Only nine prime paths 0 Prime Paths [ 0, 1, 2, 3, 6 ] [ 0, 1, 2, 4, 5 ] [ 0, 1, 2, 4, 6 ] [ 0, 2, 3, 6 ] [ 0, 2, 4, 5] [ 0, 2, 4, 6 ] [ 5, 4, 6 ] [ 4, 5, 4 ] [ 5, 4, 5 ] 1 Execute loop 0 times 2 Execute loop once 3 4 Execute loop more than once 5 6 19
Simple & Prime Path Example ! means path terminates [0, 1, 2] [0, 2, 3] [0, 2, 4] [1, 2, 3] [1, 2, 4] [2, 3, 6] ! [2, 4, 6] ! [2, 4, 5] ! [4, 5, 4] * [5, 4, 6] ! [5, 4, 5] * Simple paths Len 0 [0] [1] [2] [3] [4] [5] [6] ! Len 1 [0, 1] [0, 2] [1, 2] [2, 3] [2, 4] [3, 6] ! [4, 6] ! [4, 5] [5, 4] Len 2 Len 3 [0, 1, 2, 3] [0, 1, 2, 4] * means path cycles [0, 2, 3, 6] ! [0, 2, 4, 6] ! [0, 2, 4, 5] ! [1, 2, 3, 6] ! [1, 2, 4, 5] ! [1, 2, 4, 6] ! 0 1 2 3 4 5 Len 4 [0, 1, 2, 3, 6] ! [0, 1, 2, 4, 6] ! [0, 1, 2, 4, 5] ! 6 Prime Paths Note that paths w/o ! or * cannot be prime paths 20
Round Trips Round-Trip Path : A prime path that starts and ends at the same node These criteria omit nodes and edges that are not in round trips That is, they do not subsume edge-pair, edge, or node coverage 21
Infeasible Test Requirements An infeasible test requirement cannot be satisfied Unreachable statement (dead code) A subpath that can only be executed if a contradiction occurs (X > 0 and X < 0) Most test criteria have some infeasible test requirements It is usually undecidable whether all test requirements are feasible When sidetrips are not allowed, many structural criteria have more infeasible test requirements However, always allowing sidetrips weakens the test criteria Practical recommendation Best Effort Touring Satisfy as many test requirements as possible without sidetrips Allow sidetrips to try to satisfy unsatisfied test requirements 22
Touring, Sidetrips and Detours Prime paths do not have internal loops test paths might Tour : A test path p tours subpath q if q is a subpath of p Tour With Sidetrips : A test path p tours subpath q with sidetrips iff every edge in q is also in p in the same order The tour can include a sidetrip, as long as it comes back to the same node Tour With Detours : A test path p tours subpath q with detours iff every node in q is also in p in the same order 23
Sidetrips and Detours Example a b c d 2 5 0 1 4 Touring without sidetrips or detours 3 1 2 5 6 2 5 0 1 4 3 4 Touring with a sidetrip 3 1 2 5 2 5 0 1 4 3 4 Touring with a detour 3 24
Weaknesses of the Purely Structural Coverage /* TC1: x= 1, y= 1; TC2: x=-1, y=-1;*/ void foo(int x, int y) { if ( x > 0) x++; else x--; if(y >0) y++; else y--; assert (x * y >= 0); } yes no x>0 x++ x-- y>0 y++ y-- assert(x*y>=0) Purely structural coverage (e.g., branch coverage) alone cannot improve the quality of target software sufficiently -> Advanced semantic testing should be accompanied 25
Final Remarks 1. Why are coverage criteria important for testing? 2. Why is branch coverage popular in industry? 3. Why is prime path coverage not use in practice? 4. Why is it difficult to reach 100% branch coverage of real-world programs? 26
Data Flow Criteria Goal: Try to ensure that values are computed and used correctly Definition : A location where a value for a variable is stored into me mory Use : A location where a variable s value is accessed def (n) or def (e) : The set of variables that are defined by node n or edge e use (n) or use (e) : The set of variables that are used by node n or edge e Z = X*2 Defs: def (0) = {X} 1 4 def (4) = {Z} X = 42 def (5) = {Z} 0 3 6 Uses: use (4) = {X} 2 5 Z = X-8 use (5) = {X} 28
DU Pairs and DU Paths DU pair : A pair of locations (li, lj) such that a variable v is defined at li and used at lj Def-clear : A path from li to lj is def-clear with respect to variable v, if v is not given another value on any of the n odes or edges in the path Reach : If there is a def-clear path from li to lj with respect to v, the def of v at li reaches the use at lj du-path : A simple subpath that is def-clear with respect to v from a def of v to a use of v du (ni, nj, v) the set of du-paths from ni to nj du (ni, v) the set of du-paths that start at ni 29
Touring DU-Paths A test path p du-tours subpath d with respect to v if p tours d and the subpath taken is def-clear with respect to v Sidetrips can be used, just as with previous touring Three criteria Use every def Get to every use Follow all du-paths 30
Data Flow Test Criteria First, we make sure every def reaches a use Then we make sure that every def reaches all possible uses Finally, we cover all the paths between defs and uses 31
Data Flow Testing Example Z = X*2 1 4 X = 42 0 3 6 2 5 Z = X-8 All-defs for X All-uses for X All-du-paths for X [ 0, 1, 3, 4 ] [ 0, 1, 3, 4 ] [ 0, 1, 3, 4 ] [ 0, 1, 3, 5 ] [ 0, 2, 3, 4 ] [ 0, 1, 3, 5 ] [ 0, 2, 3, 5 ] 32
Graph Coverage Criteria Subsumption Complete Path Coverage CPC Assumptions for Data Flow Coverage 1.Every use is preceded by a def 2.Every def reaches at least one use 3.For every node with multiple outgoing edges, at least one variable is used on each out edge, and the same variables are used on each out edge. Prime Path Coverage PPC All-DU-Paths Coverage ADUP Edge-Pair Coverage EPC All-uses Coverage AUC Complete Round Trip Coverage CRTC Edge Coverage EC All-defs Coverage ADC Simple Round Trip Coverage SRTC Node Coverage NC 33
