Unit testing based on graphs: Summary
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.
Structural coverage criteria.
Data flow coverage criteria.
Coverage criteria over call graphs.
Focus of this lecture: Summarize structural and data flow
coverage over graphs.
Software artifact under test
Unit testing of code i.e., one particular method or procedure
or function.
Abstraction considered: Graphs.
Control flow graphs
Data flow graphs: CFG + data definitions and uses.
Example Re-visited
Statics Example.
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++
Structural coverage criteria
CFG can be thought of as a coarse abstraction of the underlying
code. We retain only the control flow information in this graph.
Node coverage: Corresponds to executing every (basic block)
of statement.
Edge coverage: Corresponds to executing all the
decisions/transfer of control.
Prime path coverage: Corresponds to executing loops
(structurally).
Data flow graphs
Data-Flow Graphs are CFG augmented with definitions and uses of
data.
Provide useful information about the values of variables as a
program executes.
Example Re-visited
Pattern Matching Example.
1
NOTFOUND=−1;iSub=0;rtnIndex=NOTFOUND;
2 isPat=false;subjectLen=[Link];
patternLen=[Link]
3
iSub+patternLen−1<subjectLen && isPat==false
4
subject[iSub]==pattern[0]
5 rtnIndex=iSub;
isPat=true;iPat=1
6
11
iPat<patternLen
return(rtnIndex)
7
subject[iSub+iPat]==
pattern[iPat]
break iPat++
iSub++ 10 8 9
rtnIndex=NOTFOUND;
Pattern Matching: Defs and uses
1 def(1) = {subject,pattern}
def(2)={NOTFOUND,iSub,rtnIndex,isPat,subjectLen,patternLen}
2
use(2)={subject,pattern}
3
use(3,11)=use(3,4)={iSub,patternLen,subjectLen,isPat}
4
use(4,10)=use(4,5)={subject,iSub,pattern}
5 def(5)={rtnIndex,isPat,iPat}
use(5)={iSub}
6
11
use(6,10)=use(6,7)={iPat,patternLen}
use(11)={rtnIndex}
7
use(7,8)=use(7,9)={subject,pattern,iSub,iPat}
def(10)= 10 8 9
use(10)={iSub} def(9)=use(9)={iPat}
def(8)={rtnIndex,isPat}
use(8)={NOTFOUND}
Data-flow coverage criteria
All defs coverage: Every definition reaches at least one use.
All uses coverage: Every definition reaches all possible uses.
All du-paths coverage: All possible paths connecting
definitions to uses.
Graph coverage criteria: Subsumption
Complete Path Coverage
Prime Path Coverage
All du−Paths Coverage
All Uses Coverage Edge Pair Coverage Complete Round Trip Coverage
All Defs Coverage Edge Coverage Simple Round Trip Coverage
Node Coverage