Transcript Data flow coverage criteria

Systems V & V, Quality
and Standards
Dr Sita Ramakrishnan
School CSSE
Monash University
1
Test Coverage Criteria
based on Data Flow Mechanisms
Topics
 Program Structure
 Categories of Data Flow Coverage Criteria
 Data Flow Testing
References:
 Peters J F and Pedrycz W,Software Engineering, An Engineering Approach, McGraW
Hill, 2000, (Ch.12, Software Testing, pp.437-500)
 Horgan J.R., London S., Lyu M.R. Achieving software quality with testing coverage
measures. IEEE Computer, Sep. 1994: 60-69
 Other references (books included in the slides, conference & journal papers) given in
the handout for the unit
© S Ramakrishnan
2
Program Structure
 Program consists of blocks
 Block consists of a sequence of statements
 When a first statement is executed, the following
statements are executed in the given order
 Can be represented by a flow graph
© S Ramakrishnan
3
Testing Coverage
 Have looked at testing techniques such as:
Black-box testing which includes categories such as:
• Syntax-driven driven testing – where specification is described
by a certain grammar. -> Generate test cases such that each
production rule is applied/tested at least once
• Decision-table based testing – may suit if requirements have
been written as if-then rules
• Cause-effect graphs in functional testing – addresses
limitations of decision table where all inputs are treated
separately although real world problem demand another
approach. Boundary-value analysis & equivalence class
partition also assume the independence of input
Structural testing – includes basic categories such as
statement, branch & path coverage tests
© S Ramakrishnan
4
Testing Coverage
More on Black-box Testing with Cause-Effect Graphs:
 Cause-effect graphs capture relationships
between specific combination of inputs (causes)
and outputs (effects).
• Helps avoid combinatorial explosion associated
with decision table approach
 Causes and Effects represented as nodes of a
cause-effect graph – includes intermediate
nodes to link cause & effects in forming logical
expressions
© S Ramakrishnan
5
Testing Coverage –
Cause-Effect Graphs
Eg. of an ATM transaction system. Causes and Effected listed as:
 Causes: C1 : Command is credit, C2: Command is Debit
C3: Account No. is valid, C4: Trans. Amount is valid
 Effects: E1: Print “invalid command”, E2: “invalid acct no”
E3: “debit no. not valid”, E4 & E5: debit & credit a/c respectively
or
C1
C2
C3
C4
and
E1
and
E2
and
and
E3
Cause-effect graph
© S Ramakrishnan
E4
E5
6
Testing Coverage –
Cause-Effect Graphs
 4 input (Cause) nodes & 5 output (Effect) nodes
 the node in between input (C ) & output (E ) realise
“and” or “or” operators
 Processing node used in cause-effect graph – and,
or, negation, and with processing node,
“and” - effect occurs if all inputs are true
“or” - effect occurs if at least one input is true
 “negation” – effect occurs if inputs are false
 Cause-Effect graph helps determine the
corresponding test cases
© S Ramakrishnan
7
Testing Coverage –
Cause-Effect Graphs
 Eg. To determine test cases from C-E Graph
Want to find out the causes for E3 say given:
C2
C3
C4
and
C1 C2 C3 C4
E3
X
1
1 0
X= (don’t care condition)
1 = true, 0 = false
E3 does not depend on
Cause (C1)
© S Ramakrishnan
8
Test coverage based on
Data Flow Coverage Criteria
 Why data flow orientation in testing?
 Data structures and their usage are essential elements of
any code and hence need to be taken into account when
looking at software testing
Main categories of data flow coverage criteria





basic block
all-use
c-use
d-use
du-path
© S Ramakrishnan
9
Test coverage based on
Data Flow Coverage Criteria
In a piece of Java code:
sum = 0;
prod = 0;
i = 1;
while (i <= n)
{ sum+ = i;
prod* = i;
i++
}
if (k == 0) print_results1;
Eg
Definitions shown in blue
->
->
basic block shown in purple
prod* = i an eg of “use”
i++ also an eg of “use”
if “use” appears in a computational
expression, the pair is c-use,
if in predicate, resulting pair is p-use
if (k == 1) compute;
© S Ramakrishnan
10
Test coverage based on
Data Flow Coverage Criteria

Definition – value stored in a memory location




Defined (d) – data structure is defined, created or initialized
when it is given a valid state
Use – value fetched from a memory location
C-use – used in computation or output statement &
- associated with each node
P-use – used in a predicate& associated with each edge
All-uses
C-uses
P-uses
Decision
Basic Block
Hierarchy of different dataflow
coverage criteria
© S Ramakrishnan
11
Test coverage based on
Data Flow Coverage Criteria
 Def-use Graph
 Obtained from the flow graph
 Associate with each node the sets
• C-use (i) - variables which have global c-uses in block i
• Def (i) - variables with global definitions in block i
 Associate with each edge (i,j)
•
P-use (i,j) – variables which have p-uses on edge (i,j)
 Define sets of nodes
•
•
dpu(x,i) - edges (j,k) such that x Є p-use(j,k) and there is a
def-clear path w.r.t. x from i to (j,k)
dcu(x,i) - nodes j such that x Є c-use(j) and there is a defclear path w.r.t. x from i to j
© S Ramakrishnan
12
Test coverage based on
Data Flow Coverage Criteria



Def-use Graph Paths – Definitions
Complete path – path from entry node to exit node
Def-clear path w.r.t. x from node i to node j and
from node i to edge nm , j
a path (i, n1,n2, …nm , j) containing no definitions or
undefinitions of x in nodes n1, n2, ….n m
© S Ramakrishnan
13
Test coverage based on
Data Flow Coverage Criteria
 Data flow coverage criteria –

The family of data flow testing criteria is based on requiring
that –
 The test data execute definition-clear paths from each node
containing a global definition of a variable to specified nodes
containing global c-uses and edge containing p-uses of that
variable

For each variable definition, data flow testing criteria require
that
 All/some definition-clear paths w.r.t. that variable from the node
containing the definition to all/some of that uses/c-uses/p-uses
reachable by some such paths be executed
© S Ramakrishnan
14
Test coverage based on
Data Flow Coverage Criteria
 All-def criterion
 If variable x has a global definition in node i, the all-defs
criterion requires the test data to exercise some path which
goes from i to some node or edge at which the value
assigned to x in node i is used
 All-uses criterion
 If variable x has a global definition in node i, the all-uses
criterion requires the test data to exercise at least one path
which goes from i to each node or edge at which the value
assigned to x in node i is used
© S Ramakrishnan
15
Test coverage based on
Data Flow Coverage Criteria
 All-DU-paths criterion
 If variable x has a global definition in node i, the all-DUpaths criterion requires the test data to exercise all paths
which go from i to each node and edge at which the value
assigned to x in node i is used
 Other DF testing criteria




All-p-uses
All-c-uses
All-p-uses/some-c-uses
All-c-uses/some-p-uses
© S Ramakrishnan
16
Test coverage based on
Data Flow Coverage Criteria
Hierarchy of data flow coverage criteria
all-paths
all-du-paths
all-uses
all-c-uses-some-p-uses
all-c-uses
all-defs
all-p-uses-some-c-uses
all-p-uses
all-edges
all-nodes
© S Ramakrishnan
17
Test coverage based on
Data Flow Coverage Criteria
 Interprocedural Data Flow Testing
•
•
•
Most df testing methods deal with dependencies
that exist within a procedure – intra procedural aspect
Data dependencies may also exist between procedures
Requires analysis of flow of data across these
procedure/module boundaries
© S Ramakrishnan
18
Test coverage based on
Data Flow Coverage Criteria
 Homework: Closer look at Table 12.6 Coverage
Criteria on P.479 in Peters & Pedrycz text (see
slide 1 for Reference details)
© S Ramakrishnan
19