Statement Coverage

• Choose a test set T such

that by executing program bool isEqual(int x, int y)
P for each test case in T, {
if (x = y)
each basic statement of P
z := false;
is executed at least once else
• Executing a statement once z := false;
and observing that it return z;
behaves correctly is not a }
guarantee for correctness,
int max(int x, int y)
but it is an heuristic
{
– this goes for all testing if (x > y)
efforts since in general return x;
checking correctness is else
undecidable return x;
}
 Statement Coverage

areTheyPositive(int x, int y) Following test set will give us statement

{ coverage:
if (x >= 0) T1 = {(x=12,y=5), (x= 1,y=35),
print(“x is positive”); (x=115,y=13),(x=91,y= 2)}
else
print(“x is negative”); There are smaller test cases which will
if (y >= 0) give us statement coverage too:
print(“y is positive”); T2 = {(x=12,y=  5), (x= 1,y=35)}
else
print(“y is negative”); There is a difference between these two
} test sets though
 Statement vs. Branch Coverage

assignAbsolute(int x)
{ Consider this program segment, the test set
if (x < 0) T = {x=1} will give statement coverage,
x := -x; however not branch coverage
z := x;
}
B0
Control Flow Graph: (x < 0)

true false
B1 Test set {x=1} does not
x := -x execute this edge, hence, it
does not give branch coverage

B2
z := x
 Control Flow Graphs (CFGs)
• Nodes in the control flow graph are basic blocks
– A basic block is a sequence of statements always entered at the
beginning of the block and exited at the end
• Edges in the control flow graph represent the control flow

if (x < y) { B0 (x < y)
x = 5 * y; Y N
x = x + 3;
} x = 5 * y B1 B2 y = 5
else x = x + 3
y = 5;
x = x+y;

x = x+y B3

• Each block has a sequence of statements

• No jump from or to the middle of the block
• Once a block starts executing, it will execute till the end
 Branch Coverage
• Construct the control flow graph

• Select a test set T such that by executing program P for each test
case d in T, each edge of P’s control flow graph is traversed at least
once

B0
(x < 0)

true false
B1 Test set {x=1} does not
x := -x execute this edge, hence, it
does not give branch coverage

Test set {x= 1, x=2}gives

B2 both statement and branch
z := x coverage
 Path Coverage
• Select a test set T such that by executing program P for each test
case d in T, all paths leading from the initial to the final node of P’s
control flow graph are traversed
 Path Coverage
B0
areTheyPositive(int x, int y)
(x >= 0)
{
if (x >= 0) true false
print(“x is positive”); B1 B2
else print(“x is p”) print(“x is n”)
print(“x is negative”);
if (y >= 0)
print(“y is positive”); B3
else (y >= 0)
print(“y is negative”); true false
} B4 B5
Test set: print(“y is p”) print(“y is n”)
T2 = {(x=12,y=  5), (x= 1,y=35)}
gives both branch and statement B6
coverage but it does not give path coverage
return
Set of all execution paths: {(B0,B1,B3,B4,B6), (B0,B1,B3,B5,B6), (B0,B2,B3,B4,B6),
(B0,B2,B3,B5,B6)}
Test set T2 executes only paths: (B0,B1,B3,B5,B6) and (B0,B2,B3,B4,B6)
 Path Coverage
B0
areTheyPositive(int x, int y)
(x >= 0)
{
if (x >= 0) true false
print(“x is positive”); B1 B2
else print(“x is p”) print(“x is n”)
print(“x is negative”);
if (y >= 0)
B3
print(“y is positive”);
else (y >= 0)
print(“y is negative”); true false
} B4 B5
print(“y is p”) print(“y is n”)
Test set:
T1 = {(x=12,y=5), (x= 1,y=35),
(x=115,y=13),(x=91,y= 2)} B6
gives both branch, statement and path return
coverage
 Path Coverage
• Number of paths is exponential in the number of conditional
branches
– testing cost may be expensive

• Note that every path in the control flow graphs may not be executable
– It is possible that there are paths which will never be executed
due to dependencies between branch conditions

• In the presence of cycles in the control flow graph (for example loops)
we need to clarify what we mean by path coverage
– Given a cycle in the control flow graph we can go over the cycle
arbitrary number of times, which will create an infinite set of paths
– Redefine path coverage as: each cycle must be executed 0, 1, ...,
k times where k is a constant (k could be 1 or 2)
 Condition Coverage
• In the branch coverage we make sure that we execute every branch at
least once
– For conditional branches, this means that, we execute the TRUE
branch at least once and the FALSE branch at least once
• Conditions for conditional branches can be compound boolean
expressions
– A compound boolean expression consists of a combination of
boolean terms combined with logical connectives AND, OR, and
NOT
• Condition coverage:
– Select a test set T such that by executing program P for each test
case d in T, (1) each edge of P’s control flow graph is traversed at
least once and (2) each boolean term that appears in a branch
condition takes the value TRUE at least once and the value FALSE
at least once
• Condition coverage is a refinement of branch coverage (part (1) is
same as the branch coverage)
 Condition Coverage
T = {(x=1, y=1), (x=1, y=1)} will achieve
statement, branch and path coverage, however
something(int x) T will not achieve condition coverage
{ because the boolean term (y < x) never
if (x < 0 || y < x) evaluates to true. This test set satisfies part (1)
{ but does not satisfy part (2).
y := -y;
x := -x; B0 T = {(x=1, y=1), (x=1, y=0)}
} (x < 0 || y < x) will not achieve condition coverage
z := x; either. This test set satisfies part (2)
} true false but does not satisfy part (1). It does
B1 not achieve branch coverage since
y := -y; both test cases take the true branch,
x := -x; and, hence, it does not achieve
condition coverage by definition.
Control Flow Graph B2
T = {(x=1, y=2), {(x=1, y=1)}
z := x
achieves condition coverage.
Multiple Condition Coverage
• Multiple Condition Coverage requires that all possible combination of truth
assignments for the boolean terms in each branch condition should
happen at least once
• For example for the previous example we had:
x < 0 && y < x

term1 term2
• Test set {(x=1, y=2), (x=1, y=1)}, achieves condition coverage:
– test case (x=1, y=2) makes term1=true, term2=true, and the whole
expression evaluates to true (i.e., we take the true branch)
– test case (x=1, y=1) makes term1=false, term2=false, and the whole
expression evaluates to false (i.e., we take the false branch)
• However, test set {(x=1, y= 2), (x=1, y=1)} does not achieve multiple
condition coverage since we did not observe the following truth
assignments
– term1=true, term2=false
– term1=false, term2=true