Graph coverage criteria: Applied to test code
Meenakshi D’Souza
International Institute of Information Technology
Bangalore.
Graph coverage criteria: Overview
Model software artifacts as graphs and look at coverage
criteria over graphs.
Three kinds of criteria:
Structural coverage criteria.
Data flow coverage criteria.
Coverage criteria over call graphs.
Focus of this lecture: Using structural graph coverage criteria
to test source code.
Structural graph coverage criteria: Code
Steps to be followed:
1 Modelling control flow in code as graphs.
Understand the notion of basic blocks.
Modelling branching, looping etc. in code as graphs.
2 Using structural coverage criteria to test control flow in code.
Typically used to test a particular function or procedure or a
method.
Control flow graphs for code
A Control Flow Graph (CFG) models all executions of a
method by describing control structures.
Nodes: Statements or sequences of statements (basic blocks).
Basic Block: A sequence of statements such that if the first
statement is executed, all statements will be (no branches).
Edges: Transfer of control from one statement to the next.
CFGs are often annotated with extra information to model
data:
Branch predicates.
Defs and/or uses.
CFG: If statement
if (x<y)
{
y:=0; x<y x>=y
x:=x+1;
} y:=0
x:=x+1 x:=y+1
else
{
x:=y+1;
} z:=x+1
z:=x+1;
CFG: If statement
if (x<y)
{ x<y
y:=0;
x:=x+1; y:=0
x>=y
} x:=x+1
z:=x+1;
z:=x+1
CFG: If statement with return
if (x<y)
{
return x<y
}
print(x); x>=y
return
return; print(x);
return;
Note: There are two nodes corresponding to the two return
statements.
CFG: Switch-case
read(c); read(c);
switch(c)
’N’ default
{
’Y’
case ’N’:z=25; z=25;
case ’Y’:{x=50;
break;}
default:{x=0; x=50; x=0;
break;
break;} break;
}
print(x);
print(x);
Note: case ‘N’ without a break statement leads to case ‘Y’. It
is not so for the other two cases.
CFG: Loops
There could be various kinds of loops: while, for, do-while etc.
To accurately represent the possible branches out of a loop,
the CFG for loops need extra nodes to be added.
CFG: While loop
1 x=0;
x=0;
while(x<y)
{
y=f(x,y); 2
x=x+1; x<y x>=y
}
3 4
y=f(x,y);
x=x+1;
Note: Node 2 in the graph above is a dummy node.
CFG: For loop
1 x=0
for(x=0;x<y;x++)
{
y=f(x,y); 2
} x<y x>=y
3 5
y=f(x,y)
4 x=x+1
Note: Node 1 implicitly initializes the loop, and node 4 implicitly
increments the loop.
CFG: Do while loop
x=0;
x=0;
do x<y
{
y=f(x,y); y=f(x,y);
x=x+1; x=x+1;
}while(x<y);
print(y);
x>=y
CFG: While loop with break and continue
x=0; x=0;
1
while(x<y)
{
y=f(x,y);
if(y==0) 2
{ y=f(x,y);
break; 3
}else if(y<0) y==0
{
y=y*2;
4 break;
continue;
}
x=x+1;
} 5
print(y); y<0
y=y*2;
6 continue;
7 x=x+1;
print(y); 8
CFG: Exceptions (try-catch)
try s=[Link]();
{ IOException
s=[Link]();
if([Link]()>96)
throw new Exception length<=96
("too long"); length>96
if([Link]()==0) [Link]();
throw new Exception throw
length!=0
("too short");
}(catch IOException e){ length==0
[Link]();
}(catch Exception e){
throw
[Link]();
}
return(s);
[Link]();
return(s);
Example program: Statistics
public static void computeStats (int [] numbers)
{ int length = [Link];
double med, var, sd, mean, sum, varsum;
sum = 0.0;
for(int i=0; i<length; i++)
{ sum += numbers[i]; }
med = numbers[length/2];
mean = sum/(double)length;
varsum = 0.0;
for(int i=0; i<length; i++)
{ varsum = varsum+((numbers[i]-mean)*(numbers[i]-mean)); }
var = varsum/(length-1);
sd = [Link](var);
[Link] ("mean:" + mean);
[Link] ("median:" + med);
[Link] ("variance:" + var);
[Link] ("standard deviation:" + sd);
}
CFG for Statistics program
2 i=0
3
i>=length
i<length
i++ 4 5
i=0
6
i<length
i>=length
7 8
i++
Edge coverage for Statistics program
TR:
3
{[1,2],[2,3],[3,4],[4,3],[3,5],[5,6],[6,7],[7,6],
[7,8]}.
4 5
Test path: [1,2,3,4,3,5,6,7,6,8]
7 8
Edge pair coverage for Statistics program
1 TR:
A. [1,2,3]
2 B. [2,3,4], C. [2,3,5]
D. [3,4,3], E. [3,5,6]
3 F. [4,3,5], G. [4,3,4]
H. [5,6,7], I. [5,6,8]
4 5 J. [6,7,6]
K. [7,6,8], L. [7,6,7].
6 Test paths: [1,2,3,4,3,5,6,7,6,8]
ii. [1,2,3,5,6,8]
iii. [1,2,3,4,3,4,3,5,6,7,6,7,6,8]
7 8
Prime path coverage for Statistics program
1
TR:
A. [3,4,3]
2 B. [4,3,4]
Test paths:
C. [7,6,7]
i. [1,2,3,4,3,5,6,7,6,8]
3 D. [7,6,8]
ii. [1,2,3,4,3,4,3,5,6,7,6,7,6,8]
E. [6,7,6]
iii. [1,2,3,4,3,5,6,8]
F. [1,2,3,4]
4 5 iv. [1,2,3,5,6,7,6,8]
G. [4,3,5,6,7]
v. [1,2,3,5,6,8]
H. [4,3,5,6,8]
6 I. [1,2,3,5,6,7]
J. [1,2,3,5,6,8]
7 8
Credits
Part of the material used in these slides are derived from the
presentations of the book Introduction to Software Testing, by
Paul Ammann and Jeff Offutt.
