Data Flow Testing

Data - Flow Testing - Basics

• Concepts of Data flows

• Data-flow testing strategies

 Data - Flow Testing - Basics

o Data Flow Testing is a structural testing method that examines how variables are
defined and used throughout a program.
o It uses control flow graphs to identify paths where variables are defined and then
utilized, aiming to uncover anomalies such as unused variables or incorrect
definitions.
o By focusing on the flow of data, it helps ensure that variables are properly handled
and used in the code.

3
 Data - Flow Testing - Basics

A control-flow graph (CFG) and data-flow graph (DFG) are both used in data flow
testing to analyze a program's code and identify potential issues:

Data-flow graph (DFG)

oData-flow graphs are more concerned with the correct propagation and
transformation of data, making them essential for testing data-related aspects.

Control-flow graph (CFG)

oControl flow graphs are used to understand the execution paths through the
program, which indirectly affects data flow by ensuring that all potential paths are
tested.

4
 DATA FLOW MACHINES
There are two types of data flow machines with different architectures.
Von Neumann Machine Architecture:
This architecture features interchangeable storage of instructions and data
in the same memory units.
It executes one instruction at a time in the following, micro instruction sequence:
• Fetch instruction from memory
• Interpret instruction
• Fetch operands
• Process or Execute
• Store result
• Increment program counter
• GOTO 1
Multi-instruction, Multi-data machines (MIMD) Architecture:
These machines can fetch several instructions and objects in parallel.
They can also do arithmetic and logical operations simultaneously on different data objects.
The decision of how to sequence them depends on the compiler.
5
 Data - Flow Testing - Basics - Motivation
Program Control flow with Von Neumann’s paradigm
BEGIN
Given m, n, p, q, find e. PAR DO Parallel Do

READ m, n, n,
a = n+m
e = (m+n+p+q) * (m+n-p-q) p, q
END PAR
b=p+q PAR DO
a := m+n
a := m + n
c=a+b b := p+q
b := p + q END PAR
c := a + b PAR DO
d := a - b c := a+b
d=a-b
d := a-b
e := c * d END PAR
e=c*d PAR DO
e := c * d
END PAR
6 Multiple representations of control flow graphs possible. END
 Data - Flow Testing - Basics - Motivation
Program Flow using Data Flow Machines paradigm
n m p q
BEGIN
PAR DO
READ m, n, n, p, q
END PAR a := m+n b := p+q
PAR DO
a := m+n
b := p+q c := a+b d := a-b
END PAR
PAR DO
c := a+b
d := a-b
e := c * d
END PAR
PAR DO
e := c * d
END PAR The interrelations among the data items remain same.
7
END
Data - Flow Testing - Basics

Assumptions
• Problems in a control flow
• Problems with data objects

Assumption of Correct Control Flow:

oData-flow testing strategies assume that the control flow of the software is generally
correct.
o The primary focus is not on control flow errors but on issues related to data objects.
Focus on Data Objects:
oThe main concern is with data objects: ensuring they are available when needed and
that operations on them are correct.

8
 Data - Flow Testing - Basics

Data Flow Graphs (DFG)

• It is a graph with nodes & directed links
• Test the Von Neumann way -

oConvert to a CFG
oAnnotate : program actions (weights)

Annotating control flow graphs with information about data objects helps in
understanding and analyzing how data flows through the program and how it
interacts with different control paths.

9
 Data - Flow Testing - Basics

Data Object State & Usage

Program Actions (d, k, u):

Defined (created) - explicitly or implicitly (d)

Killed (released) - directly or indirectly (k)

Used - (u)

• In a calculation - (c)

• In a predicate - directly or indirectly (p)

10
 Data - Flow Testing - Basics

Data Flow Anomalies

A Two letter sequence of Actions (d, k, u)
A
dd : harmless, suspicious
dk : probably a bug. Action
du : normal
kd : normal
kk : harmless, but probably a bug
ku : a bug
ud : normal. Redefinition.
uk : normal
uu : normal

11
 Data - Flow Testing - Basics – Data Flow Anomalies

Data Flow Graphs

12
 Data - Flow Testing - Basics – Data Flow Anomalies
An anomaly is the one denoted by a two-character sequence of action

dd (Defined-Defined):Probably harmless but suspicious. Why do we need to define an object

twice without using it in between?
Dk (Defined-Killed): Probably a bug. Why to define an object without using it?
du (Defined-Used):Normal case. The object is used after defining it.
kd (Killed-Defined):Normal case. An object is killed and then redefined.
kk (Killed-Killed):Harmless but probably buggy. Did you want to be sure it was really killed?
ku (Killed-Used): A Bug. The object does not exist in the sense that its value is undefined or
indeterminate.
ud (Used-Defined):Usually not a bug because the language permits reassignment at almost
any time.
uk (Used-Killed):Normal situation.
uu (Used-Used):Normal situation. The object is used multiple times, which is standard in most
applications.
13
 Data - Flow Testing - Basics – Data Flow Anomalies
In addition to the two-letter combinations, there are six single-letter situations that involve
either a leading or trailing dash. These dashes help interpret the action more precisely:
Leading dash (-): Indicates that nothing relevant happens to the variable from the start of the
program up to the current action.
Trailing dash (-): Indicates that nothing relevant happens to the variable after the current
action until the program’s exit.

-k: Possibly anomalous. The variable is being killed (marked as unavailable), but it has not
been defined prior to this point. This could be a problem unless the variable was created in a
called routine or is a global variable.
-d: Normal case. This is the first time the variable is defined along this path, so it's okay.
-u: Possibly anomalous. The variable is being used without being explicitly defined earlier
on this path. This is fine if the variable is global and was previously defined, but otherwise, it
could indicate a problem

14
 Data - Flow Testing - Basics – Data Flow Anomalies

k-:Normal case. The last action on this path was killing the variable. Nothing anomalous
here.
d-: Possibly anomalous. The variable was defined but not used before the program exits.
This could be okay if it's part of a global definition or if the variable was defined for use in
other routines.
u-: Normal case, but possibly a bug. The variable was used but not killed. This could
indicate a common bug, where dynamically allocated memory or an object was not returned
or freed after being used.

15
 Data - Flow Testing - Basics – Data Flow Anomalies

DATA FLOW ANOMALY STATE GRAPH:

Data flow anomaly model prescribes that an object can be in one of four distinct states:
K :- undefined, previously killed, does not exist
D :- defined but not yet used for anything
U :- has been used for computation or in predicate
A :- anomalous

These capital letters (K,D,U,A) denote the state of the variable and should not be confused with the
program action, denoted by lower case letters.

Unforgiving Data - Flow Anomaly Flow Graph: Unforgiving model, in which once a variable
becomes anomalous it can never return to a state of grace.

16
Data - Flow Testing - Basics
Data Flow Anomaly State graph u: The variable is used.
k: The variable is killed or deallocated.
Unforgiving Data flow state graph
d: The variable is defined or assigned a value.

States
Undefined K (Killed):
K
D (Defined but not used):
U (Used):
k, u A (Anomalous):

u
d, k
U D A Anomalous
u
d
Defined d, k, u
17 Used ref boris beizer
Data - Flow Testing - Basics
Data Flow Anomaly State graph
Forgiving Data flow state graph u A  DD, DK, KU
k u
KU
K k
k u

d DK

k
d
u k
U D d
u
d
DD
u
18 d
 Data - Flow Testing - Basics

Data Flow State Graphs

• Differ in processing of anomalies

• Choice depends on Application, language, context

19
 Data - Flow Testing - Basics

Static vs Dynamic Anomaly Detection

Static Analysis:
oConducted without executing the program.
• Static analysis of data flows oDetects issues like syntax errors.
oUseful for identifying data-flow anomalies but
• Dynamic analysis cannot detect all runtime issues.

Intermediate data values

20
 Data - Flow Testing - Basics

Static vs Dynamic Anomaly Detection

Dynamic Analysis:
• Static analysis of data flows oPerformed during the execution of a
program.
oIdentifies issues based on intermediate
• Dynamic analysis values, such as division by zero.
Intermediate data oEssential for detecting runtime anomalies
values that static analysis may miss.

21
 Data - Flow Testing - Basics

Insufficiency of Static Analysis (for Data flow) - Limitations

o The
Pointer
Static
Similar to values
correctness
analysis
arrays, for
might
these arrays
ofdead
detect
complex are
dynamically dynamically
anomalies
data constructed
on
structures calculated,
SA can What
sometimes constitutes
detect an anomaly may
variables, varysolving
but based on
1. Validation of Dead Variables making
require static
unachievable
function names
runtime
the validation
paths,
in
execution
program’s leading
calls impossible
to the
cannot
to and
context validate be forstate.
specific array
falsedeveloper's
positives.
validated
their
this problem in general is unsolvable.
Path validation requires execution.
elements.
2. Validation of pointers in Arrays statically.
expectations. Static analysis might not align with
3. o
Validation of pointers for Records & pointers Uninitialized array elements can lead to errors that only
the program’s specific requirements.
4. Dynamic addresses for dynamic subroutine calls dynamic analysis can detect.
5. Identifying False anomaly on an unachievable path
6. Recoverable anomalies & Alternate state graph
7. Concurrency, Interrupts, System Issues o In concurrent or multi-tasking environments,
static analysis becomes inadequate due to the
complexity of managing multiple data flows
across various execution paths and priority
levels.
o Interrupts and true concurrency complicate
anomaly detection further, requiring dynamic
testing to identify issues accurately.

22
 Data Flow Model

o The data flow model is based on the program's control flow graph
o Here we annotate each link with symbols (for example, d, k, u, c, p) or
sequences of symbols (for example, dd, du, ddd) that denote the
sequence of data operations on that link with respect to the variable of
interest. Such annotations are called link weights.
o The control flow graph structure is same for every variable: it is the
weights that change.

23
 Data - Flow Testing - Basics : Data Flow Model

Procedure to Build:
1. Entry & Exit nodes
2. Unique node identification
3. Weights on out link
4. Predicated nodes
5. Sequence of links
1. Join
2. Concatenate weights
3. The converse

24
 Procedure to Build:
Node Creation and Naming:
Each statement in the program is represented by a unique node. Every node, except for entry and exit nodes, must have
at least one incoming and outgoing link.
Entry and Exit Nodes:
Entry nodes are dummy nodes added at the start of the program, for example, for statements like BEGIN.
Exit nodes are dummy nodes at the program’s conclusion, such as for statements (like END or RETURN) These
complete the graph by marking the start and end of the process.
Linking and Weighting:
Outlinks from simple statements are weighted by the sequence of data-flow actions that correspond to the code
execution order. This weight sequence may consist of multiple letters representing actions, such as cd or ckd for variable
assignments.
For languages that support complex structures like multiple assignments, the weight represents the order of object code
execution for each variable.
Predicate Nodes:
Predicate nodes (e.g., IF-THEN-ELSE, DO WHILE, CASE) are weighted based on the p-use (predicate use) on every
outlink, specific to that outlink’s data-flow.
Node Simplification:
A sequence of simple statements (nodes with one inlink and one outlink) can be condensed into a pair of nodes. The
weight between them becomes the concatenation of the link weights from the original sequence of nodes.

25
 Data - Flow Testing - Basics : Data Flow Model

o If there are several data-flow actions on a given link for a given variable, then the
weight of the link is denoted by the sequence of actions on that link for that
variable.
o Conversely, a link with several data-flow actions on it can be replaced by a
succession of equivalent links, each of which has at most one data-flow action for
any variable.

26
 Data Flow Model
Example: a –1
n

Z = b + ---------
START a - 1
INPUT a, b, n #INPUT (a, b, n):
Z := 0 #Variable Z is set to 0. This Z serves as the result accumulator
IF a = 1 THEN Z := 1
GOTO DONE1
r := 1 c := 1
POWER:
c := c * a
r := r + 1
IF r <= n THEN GO TO POWER
Z := (c – 1) / (a – 1)
DONE1:
Z := b + Z
END
27
Data - Flow Testing - Basics – Data Flow model

Read a,b,n
Z := 0 Y Z := 1 Z := b + Z

1 2 5 6
P1 a = 1?

START
Z := (c-1)/(a-1)
INPUT a, b, n
Z := 0
r := 1 c:=1 IF a = 1 THEN Z := 1
P2 GOTO DONE1
3 4 r<n? r := 1 c := 1
r := r+1, c:= c*a POWER:
c := c * a
Y r := r + 1
IF r <= n THEN GO TO POWER
Z := (c – 1) / (a – 1)
DONE1:
CFG for the Example Z := b + Z
END
 d or kd cd or ckd
d
1 2 5 6
a = 1?
P1
Y

d or kd

P2 START
3 4 r < n ? INPUT a, b, n
Z := 0
Y IF a = 1 THEN Z := 1
GOTO DONE1
r := 1 c := 1
POWER:
c := c * a
r := r + 1
IF r <= n THEN GO TO POWER
Z := (c – 1) / (a – 1)
DONE1:
Z := b + Z
END

CFG annotated – Data Flow Model for Z

1 2 5 6
a = 1?
P1
Y

-d c-

ckd or kd P2
3 4 r<n?
START
INPUT a, b, n
Y Z := 0
IF a = 1 THEN Z := 1
GOTO DONE1
r := 1 c := 1
POWER:
c := c * a
r := r + 1
IF r <= n THEN GO TO POWER
Z := (c – 1) / (a – 1)
DONE1:
Z := b + Z
END

CFG annotated – Data Flow Model for c

 1 2 5 6
a = 1?
P1
Y

-d p-

ckd or kd P2
3 4 r<n?
START
INPUT a, b, n
Y Z := 0
IF a = 1 THEN Z := 1
GOTO DONE1
r := 1 c := 1
POWER:
c := c * a
r := r + 1
IF r <= n THEN GO TO POWER
Z := (c – 1) / (a – 1)
DONE1:
Z := b + Z
END

31 CFG annotated – Data Flow Model for r

 d c
1 2 5 6
a = 1?
P1
Y

P2
3 4 r<n?
START
Y INPUT a, b, n
Z := 0
IF a = 1 THEN Z := 1
GOTO DONE1
r := 1 c := 1
POWER:
c := c * a
r := r + 1
IF r <= n THEN GO TO POWER
Z := (c – 1) / (a – 1)
DONE1:
Z := b + Z
END

CFG annotated – Data Flow Model for b

 d
1 2 5 6
a = 1?
P1
Y
p-

P2
3 4 r<n?
START
INPUT a, b, n
Y Z := 0
IF a = 1 THEN Z := 1
GOTO DONE1
r := 1 c := 1
POWER:
c := c * a
r := r + 1
IF r <= n THEN GO TO POWER
Z := (c – 1) / (a – 1)
DONE1:
Z := b + Z
END

CFG annotated – Data Flow Model for n

 d
1 2 5 6
a = 1?
P1
p
c-

c P2
3 4 r<n?
START
INPUT a, b, n
Y Z := 0
IF a = 1 THEN Z := 1
GOTO DONE1
r := 1 c := 1
POWER:
c := c * a
r := r + 1
IF r <= n THEN GO TO POWER
Z := (c – 1) / (a – 1)
DONE1:
Z := b + Z
END

34 CFG annotated – Data Flow Model for a

 Data - Flow Testing - Basics – Data Flow model

A DFM for each variable

Single DFM for multiple variables

Use weights subscripted with variables

35
 Data - Flow Testing – Data Flow Testing Strategies

• A structural testing strategy (path testing)

• Add, data flow strategies with link weights

• Test path segments to have a ‘d’ (or u, k, du, dk)

36
 Data - Flow Testing – Data Flow Testing Strategies

Definition-Clear Path Segment (no k, kd), kd) with respect to variable X, is a

connected sequence of links such that X is (possibly) defined on the first link
and not redefined or killed on any subsequent link of that path segment.
Loop-Free Path Segment is a path segment for which every node in it is
visited atmost once.
Simple path segment is a path segment in which at most one node is visited
twice.
A du path from node i to k is a path segment such that if the last link has a
computational use of X, then the path is simple and definition-clear;
if the penultimate (last but one) node is j - that is, the path is (i,p,q,...,r,s,t,j,k)
and link (j,k) has a predicate use - then the path from i to j is both loop-free
and definition-clear.
37
 Data - Flow Testing – Data Flow Testing Strategies
DFT Strategies
1. All-du paths (ADUP)
2. All uses (AU) strategy

3. All p-uses/some c-uses(APU+C) and

4. All c-uses/some p-uses(ACU+P)

5. All Definitions Strategy

6. All p-uses(APU)

7. All c-uses Strategy(ACU)

Purpose:

Test Design, Develop Test Cases

38
 Data - Flow Testing – Data Flow Testing Strategies

1. All-du paths (ADUP)

It requires that every du path from every definition of every variable to every use
of that definition be exercised under some test.
o The All-du-paths (ADUP) strategy is the strongest data-flow testing strategy.
It ensures that:
o Every definition of every variable is tested.
o For each definition of a variable, every path from that definition to each of its uses
(whether computational or predicate use) is exercised under some test.

39
 Data - Flow Testing – Data Flow Testing Strategies

2. All uses (AU) strategy

o At least one definition clear path segment from every definition of every
variable to every use of that definition be exercised under some test.

40
 Data - Flow Testing – Data Flow Testing Strategies

3. All p-uses/some c-uses

o The All P-uses / Some C-uses (APU + c) strategy focuses on:
o Testing all predicate uses of a variable (points where the variable is used in a
condition, like "if" statements).
o Testing some computational uses of the variable (where the variable is used in a
computation, like assignments or calculations).
o This strategy is stronger than branch coverage, as it ensures thorough testing of
decision points.

41
 Data - Flow Testing – Data Flow Testing Strategies

4. All c-uses/some p-uses

o The All C-uses / Some P-uses (ACU + p) strategy ensures:
o Testing all computational uses of a variable.
o Testing some predicate uses of the variable.
o This strategy is weaker than branch coverage, meaning it provides less coverage of
decision points but focuses more on computations involving the variable.

42
 Data - Flow Testing – Data Flow Testing Strategies

4. All Definitions Strategy (AD)

The All Definitions (AD) strategy is a basic form of data-flow testing.
It requires:
oAt least one path from every definition of a variable to one of its uses, whether it is a
computational use or a predicate use.
oThis strategy is weaker than ACU + p and APU + c, as it only guarantees that the
variable's definition is tested at least once, without needing to test every possible use.

43
 Data - Flow Testing – Data Flow Testing Strategies

5. All-Predicate Uses, All-Computational Uses Strategy

The All Predicate Uses (APU) strategy requires:

For every definition of a variable, at least one definition-free path from the definition to
every predicate use of the variable (i.e., every decision-making point where the variable
is used).

The All Computational Uses (ACU) strategy requires:

For every definition of a variable, at least one definition-free path from the definition to
every computational use of the variable (i.e., every calculation or assignment involving
the variable).

44
 Ordering the strategies Data Flow Testing Strategies

All Paths (P∞)

All du Paths

All-uses Paths (AU)

All-c / some-p (ACU+p) All-p / some-c APU+c

All Defs AD
All c uses (ACU) All P-uses APU

All Branches P2

45 ref boris
All Stmts P1 beizer
 Data - Flow Testing – Data Flow Testing Strategies

Testing, Maintenance & Debugging in the Data Flow context

Slicing:
• A static program slice is a part of a program defined wrt a
variable ‘v’ and a statement ‘s’; It is the set of all
statements that could affect the value of ‘ v’ at stmt ‘s’.

Stmt1 var v
stmt2
Stmt3 var v
Stmt4 var v

Stmt s var v
46
 Data - Flow Testing – Data Flow Testing Strategies

Testing, Maintenance & Debugging in the Data Flow context

Dicing:

• A program dice is a part of slice in which all stmts. which

are known to be correct have been removed.

• Obtained from ‘slice’ by incorporating correctness

information from testing / debugging.

47
 Data - Flow Testing – Data Flow Testing Strategies

Testing, Maintenance & Debugging in the Data Flow context

Debugging:

• Select a slice.

• Narrow it to a dice.

• Refine the dice till it’s one faulty stmt.

48
 Data - Flow Testing – Data Flow Testing Strategies

Testing, Maintenance & Debugging in the Data Flow context

Dynamic Slicing:

• Refinement of static slicing

• Only achievable paths to the stmt ‘s’ in question are

included.

Slicing methods bring together testing, maintenance &

debugging.
49