Narasimha Rao.

P
Compiled with reference from:
Software Testing Techniques: Boris Beizer
Craft of Software Testing: Brain Marrick
Unit 2
ref boris beizer 2




Control Flow Graphs and Path Testing
We will see in Unit 2:

Concepts of path testing

Predicates

Path predicates and Achievable paths

Path Sensitizing

Path Instrumentation

Applications of path testing


In addition we have also,

Control flow graphs, flowcharts

Testing when program contains iterative loop statements.

U2
ref boris beizer 3




Control Flow Graphs and Path Testing
Path Testing Definition

A family of structural test techniques based on judiciously selecting a set of test paths
through the programs.


Goal: Pick enough paths to assure that every source statement is executed at least once.

It is a measure of thoroughness of code coverage.

It is used most for unit testing on new software.

Its effectiveness reduces as the software size increases.

We use Path testing techniques indirectly.

Path testing concepts are used in and along with other testing techniques



Code Coverage: During unit testing: # stmts executed at least once / total # stmts
U2
ref boris beizer 4




Control Flow Graphs and Path Testing
Path Testing contd..


Assumptions:

Software takes a different path than intended due to some error.

Specifications are correct and achievable.

Processing bugs are only in control flow statements

Data definition & access are correct


Observations

Structured programming languages need less of path testing.

Assembly language, Cobol, Fortran, Basic & similar languages make path testing necessary.

U2
ref boris beizer 5




Control Flow Graphs and Path Testing
Control Flow Graph

A simplified, abstract, and graphical representation of a programs control structure
using process blocks, decisions and junctions.

U2
Do Process A
Process Block
Decisions
Junctions
Case Statement
IF
A = B ?
NO: ELSE DO
YES: THEN DO
1 2
1
CASE-OF
2
N
CASE 1
CASE 2
CASE N
Control Flow Graph Elements
ref boris beizer 6




Control Flow Graphs and Path Testing
Control Flow Graph Elements:

Process Block:

A sequence of program statements uninterrupted by decisions or junctions with a single
entry and single exit.

Junction:

A point in the program where control flow can merge (into a node of the graph)
Examples: target of GOTO, Jump, Continue

Decisions:

A program point at which the control flow can diverge (based on evaluation of a condition).
Examples: IF stmt. Conditional branch and Jump instruction.

Case Statements:

A Multi-way branch or decision.
Examples: In assembly language: jump addresses table, Multiple GOTOs, Case/Switch

For test design, Case statement and decision are similar.
U2
ref boris beizer 7
Control Flow Graphs and Path Testing




Control Flow Graph Vs Flow Charts
U2
Control Flow Graph Flow Chart
Compact representation of the program Usually a multi-page description
Focuses on Inputs, Outputs, and the control
flow into and out of the block.
Focuses on the process steps inside
Inside details of a process block are not
shown
Every part of the process block are drawn
ref boris beizer 8




Control Flow Graphs and Path Testing
U2
Creation of Control Flow Graph from a program

One statement to one element translation to get a Classical Flow chart
Add additional labels as needed
Merge process steps
A process box is implied on every junction and decision
Remove External Labels
Represent the contents of elements by numbers.
We have now Nodes and Links


INPUT X, Y
Z := X + Y
V := X - Y
IF Z >= 0 GOTO SAM
JOE: Z := Z + V
SAM: Z := Z - V
FOR N = 0 TO V
Z := Z - 1
NEXT N
END
INPUT X, Y
Z >= 0 ?
Z := X + Y V := X - Y
Z := Z - V
Z := Z + V
SAM
JOE
NO
N := 0 Z := Z - 1
LOOP
N = V ?
NO
YES
END One to One Flow Chart
N := N+1
ref boris beizer 9




Control Flow Graphs and Path Testing
U2
Creation of Control Flow Graph from a program

One statement to one element translation to get a Classical Flow chart
Add additional labels as needed
Merge process steps
A process box is implied on every junction and decision
Remove External Labels
Represent the contents of elements by numbers.
We have now Nodes and Links


INPUT X, Y
Z := X + Y
V := X - Y
IF Z >= 0 GOTO SAM
JOE: Z := Z + V
SAM: Z := Z - V
FOR N = 0 TO V
Z := Z - 1
NEXT N
END
Simplified Flow Graph
Z >= 0 ?
P1
P3
P2
SAM
JOE
NO
P4
LOOP
N = V ?
NO
YES
END
P5
ref boris beizer 10




Control Flow Graphs and Path Testing
U2
Creation of Control Flow Graph from a program

One statement to one element translation to get a Classical Flow chart
Add additional labels as needed
Merge process steps
A process box is implied on every junction and decision
Remove External Labels
Represent the contents of elements by numbers.
We have now Nodes and Links


INPUT X, Y
Z := X + Y
V := X - Y
IF Z >= 0 GOTO SAM
JOE: Z := Z + V
SAM: Z := Z - V
FOR N = 0 TO V
Z := Z - 1
NEXT N
END
Simplified Flow Graph
1 2 3 4 5
6 7
ref boris beizer 11
Linked List Notation of a Control Flow Graph





Node Processing, label, Decision Next-Node

1 (BEGIN; INPUT X, Y; Z := X+Y ; V := X-Y) : 2
2 ( Z >= 0 ? ) : 4 (TRUE)
: 3 (FALSE)
3 (JOE: Z := Z + V) : 4
4 (SAM: Z := Z V; N := 0) : 5
5 (LOOP; Z := Z -1) : 6
6 (N = V ?) : 7 (FALSE)
: END (TRUE)
7 (N := N + 1) : 5
Control Flow Graphs and Path Testing
U2
1 2 3 4 5
6 7
ref boris beizer 12




Control Flow Graphs and Path Testing
Path Testing Concepts

1. Path is a sequence of statements starting at an entry, junction or decision and ending at
another, or possibly the same junction or decision or an exit point.

Link is a single process (block) in between two nodes.

Node is a junction or decision.

Segment is a sequence of links. A path consists of many segments.

Path segment is a succession of consecutive links that belongs to the same path. (3,4,5)

Length of a path is measured by # of links in the path or # of nodes traversed.

Name of a path is the set of the names of the nodes along the path. (1,2,3 4,5, 6)
(1,2,3,4, 5,6,7, 5,6,7, 5,6)

Path-Testing Path is an entry to exit path through a processing block.




U2
ref boris beizer 13




Control Flow Graphs and Path Testing
Path Testing Concepts..

2. Entry / Exit for a routines, process blocks and nodes.


Single entry and single exit routines are preferable.

Called well-formed routines.

Formal basis for testing exists.

Tools could generate test cases.

U2
ref boris beizer 14




Control Flow Graphs and Path Testing
Path Testing Concepts..

Multi-entry / Multi-exit routines: (ill-formed)

A Weak approach: Hence, convert it to single-entry / single-exit routine.

Integration issues:

Large # of inter-process interfaces. Creates problem in Integration.
More # test cases and also a formal treatment is more difficult.










Theoretical and tools based issues

A good formal basis does not exist.
Tools may fail to generate important test cases.
U2
Multi-
entry
routine
Multi-
Exit
Routine
Valid only for x
Valid for x or y
Valid only for Y
Called by x, y
Valid for caller A, B
Valid for caller A
Valid for caller B, C
ref boris beizer 15




Control Flow Graphs and Path Testing
Path Testing Concepts contd..

Convert a multi-entry / exit routine to a single entry / exit routine:
Use an entry parameter and a case statement at the entry => single-entry










Merge all exits to Single-exit point after setting one exit parameter to a value.





U2
Begin N
Begin
Begin 1
1
2
N
Begin 2
Case
Exit N
Exit 1
Exit 2
1
2
N
SET E = 1
SET E = 1
SET E = 1
ref boris beizer 16




Control Flow Graphs and Path Testing
Path Testing Concepts contd..

Test Strategy for Multi-entry / exit routines

1. Get rid of them.
2. Control those you cannot get rid of.

3. Convert to single entry / exit routines.
4. Do unit testing by treating each entry/exit combination as if it were a completely different
routine.

5. Recognize that integration testing is heavier
6. Understand the strategies & assumptions in the automatic test generators and confirm that
they do (or do not) work for multi-entry/multi exit routines.

U2
ref boris beizer 17




Control Flow Graphs and Path Testing
Path Testing Concepts

3. Fundamental Path Selection Criteria

A minimal set of paths to be able to do complete testing.

Each pass through a routine from entry to exit, as one traces through it, is a potential path.

The above includes the tracing of 1..n times tracing of an interactive block each separately.

Note: A bug could make a mandatory path not executable or could create new paths not
related to processing.
U2
Complete Path Testing prescriptions:

1. Exercise every path from entry to exit.
2. Exercise every statement or instruction at least once.
3. Exercise every branch and case statement in each direction, at least once.

Point 1 => point 2 and 3. Point 2 & 3 are not the same
Point 1 is impractical. For a structured language, Point 3 => Point 2

ref boris beizer 18




Control Flow Graphs and Path Testing
Path Testing Concepts

Path Testing Criteria :

1. Path Testing (P

):

Execute all possible control flow paths thru the program; but typically restricted to
entry-exit paths.

Implies 100% path coverage. Impossible to achieve.

2. Statement Testing ( P
1
) :

Execute all statements in the program at least once under the some test.
100% statement coverage => 100% node coverage.
Denoted by C1
C1 is a minimum testing requirement in the IEEE unit test standard: ANSI 87B.

3. Branch Testing (P
2
) :

Execute enough tests to assure that every branch alternative has been exercised
at least once under some test.
Denoted by C2
Objective: 100% branch coverage and 100% Link coverage.

For well structured software, branch testing & coverage include statement coverage
U2
ref boris beizer 19
Control Flow Graphs and Path Testing




Picking enough (the fewest) paths for achieving C1+C2


U2
Z >= 0 ?
P1
SAM
NO
LOOP
N = V ?
NO
YES
END
2
b
a
1
c
e
f
g d
5
4 3
6
Paths Decisions Process-link
2 5 a b c d e f g
abdeg Y Y Y Y Y Y Y
acdeg No Y Y Y Y Y Y
abdefeg Y N Y Y Y Y Y Y
acdefeg No Y Y Y Y Y Y Y
1.
Does every decision have Y & N (C2)?
2.
Are call cases of case statement marked (C2)?
3.
Is every three way branch covered (C2)?
4.
Is every link covered at least once (C1)?



Make small changes in the path changing only 1
link or node at a time.


ref boris beizer 20




Control Flow Graphs and Path Testing
Revised path selection Rules

1. Pick the simplest and functionally sensible entry/exit path

2. Pick additional paths as small variations from previous paths. (pick those with no loops,
shorter paths, simple and meaningful)

3. Pick additional paths but without an obvious functional meaning (only to achieve C1+C2
coverage).

4. Be comfortable with the chosen paths. play hunches, use intuition to achieve C1+C2

5. Dont follow rules slavishly except for coverage




U2
ref boris beizer 21




Control Flow Graphs and Path Testing
4. Testing of Paths involving loops

Bugs in iterative statements apparently are not discovered by C1+C2.
But by testing at the boundaries of loop variable.

Types of Iterative statements

1. Single loop statement.

2. Nested loops.

3. Concatenated Loops.

4. Horrible Loops

Let us denote the Minimum # of iterations by nmin
the Maximum # of iterations by nmax
the value of loop control variable by V
the #of test cases by T
the # of iterations carried out by n

Later, we analyze the Loop-Testing times
U2
ref boris beizer 22




Control Flow Graphs and Path Testing
Testing of path involving loops

1. Testing a Single Loop Statement (three cases)

Case 1. nmin = 0, nmax = N, no excluded values

1. Bypass the loop.
If you cant, there is a bug, nmin 0 or a wrong case.
2. Could the value of loop (control) variable V be negative?
could it appear to specify a ve n ?
3. Try one pass through the loop statement: n = 1
4. Try two passes through the loop statement: n = 2
To detect initialization data flow anomalies:
Variable defined & not used in the loop, or
Initialized in the loop & used outside the loop.
5. Try n = typical number of iterations : nmin < n < nmax
6. Try n = nmax -1

7. Try n = nmax
8. Try n = nmax + 1.
What prevents V (& n) from having this value?
What happens if it is forced?

U2
2
1
ref boris beizer 23




Control Flow Graphs and Path Testing
Testing of path involving loops

Case 2. nmin = +ve, nmax = N, no excluded values


1. Try nmin - 1
Could the value of loop (control) variable V be < nmin?
What prevents that ?
2. Try nmin
3. Try nmin + 1

4. Once, unless covered by a previous test.
5. Twice, unless covered by a previous test.

4. Try n = typical number of iterations : nmin < n < nmax
5. Try n = nmax -1

6. Try n = nmax
7. Try n = nmax + 1.
What prevents V (& n) from having this value?
What happens if it is forced?

Note: only a case of no iterations, n = 0 is not there.
U2
2
1
ref boris beizer 24




Control Flow Graphs and Path Testing
Path Testing Concepts

Case 3. Single loop with excluded values

1. Treat this as single loops with excluded values as two sets.

2. Example:

V = 1 to 20 excluding 7,8,9 and10

Test cases to attempt are for:
V = 0,1,2,4,6,7 and V = 10,11,15,19,20,21
(underlined cased are not supposed to work)









U2
2
1
ref boris beizer 25




Control Flow Graphs and Path Testing
Testing of path involving loops

2. Testing a Nested Loop Statement






Multiplying # of tests for each nested loop => very large # of tests

A test selection technique:

1. Start at the inner-most loop. Set all outer-loops to Min iteration parameter values: V
min
.
2. Test the V
min,
V
min
+ 1, typical V, V
max
- 1, V
max
for the inner-most loop. Hold the outer-
loops to V
min.
Expand tests are required for out-of-range & excluded values.

3. If you have done with outer most loop, Go To step 5. Else, move out one loop and do
step 2 with all other loops set to typical values.
4. Do the five cases for all loops in the nest simultaneously.


Assignment: check # test cases = 12 for nesting = 2, 16 for 3, 19 for 4.
U2
3
2
4
1
ref boris beizer 26




Control Flow Graphs and Path Testing
Testing of path involving loops








Compromise on # test cases for processing time.

Expand tests for solving potential problems associated with initialization of variables and
with excluded combinations and ranges.

Apply Huangs twice thorough theorem to catch data initialization problems.
U2
3
2
4
1
ref boris beizer 27




Control Flow Graphs and Path Testing
Testing of path involving loops

3. Testing Concatenated Loop Statements







Two loops are concatenated if its possible to reach one after exiting the other while still on
the path from entrance to exit.

If these are independent of each other, treat them as independent loops.

If their iteration values are inter-dependent & these are same path, treat these like a nested
loop.

Processing times are additive.
U2
4
3
2
1
ref boris beizer 28




Control Flow Graphs and Path Testing
Testing of path involving loops

4.Testing Horrible Loops







Avoid these.

Even after applying some techniques of paths, resulting test cases not definitive.

Too many test cases.

Thinking required to check end points etc. is unique for each program.

Jumps in & out of loops and intersecting loops etc, makes test case selection an ugly task.

etc. etc.
U2
5
4
3
2 1
6
ref boris beizer 29




Control Flow Graphs and Path Testing
Testing of path involving loops

Loop Testing Times

Longer testing time for all loops if all the extreme cases are to be tested.

Unreasonably long test execution times indicate bugs in the s/w or specs.

Case: Testing nested loops with combination of extreme values leads to long test times.

Show that its due to incorrect specs and fix the specs.
Prove that combined extreme cases cannot occur in the real world. Cut-off those tests.

Put in limits and checks to prevent the combined extreme cases.
Test with the extreme-value combinations, but use different numbers.

The test time problem is solved by rescaling the test limit values.

Can be achieved through a separate compile, by patching, by setting parameter values
etc..


U2
ref boris beizer 30




Control Flow Graphs and Path Testing
Effectiveness of Path Testing


Path testing (with mainly P1 & P2) catches ~65% of Unit Test Bugs ie., ~35% of all bugs.

More effective for unstructured than structured software.


Limitations

Path testing may not do expected coverage if bugs occur.

Path testing may not reveal totally wrong or missing functions.

Unit-level path testing may not catch interface errors among routines.

Data base and data flow errors may not be caught.

Unit-level path testing cannot reveal bugs in a routine due to another.

Not all initialization errors are caught by path testing.

Specification errors cannot be caught.
U2
ref boris beizer 31




Control Flow Graphs and Path Testing
Effectiveness of Path Testing


A lot of work

Creating flow graph, selecting paths for coverage, finding input data values to force
these paths, setting up loop cases & combinations.

Careful, systematic, test design will catch as many bugs as the act of testing.
Test design process at all levels at least as effective at catching bugs as is running the test
designed by that process.



More complicated path testing techniques than P1 & P2

Between P2 & P
Complicated & impractical

Weaker than P1 or P2.
For regression (incremental) testing, its cost-effective
U2
ref boris beizer 32




Control Flow Graphs and Path Testing
Predicates, Predicate Expressions

Path

A sequence of process links (& nodes)

Predicate

The logical function evaluated at a decision : True or False. (Binary , boolean)

Compound Predicate
Two or more predicates combined with AND, OR etc.

Path Predicate

Every path corresponds to a succession of True/False values for the predicates traversed
on that path.

A predicate associated with a path.
X > 0 is True AND W is either negative or equal to 122 is True

Multi-valued Logic / Multi-way branching
U2
ref boris beizer 33




Control Flow Graphs and Path Testing
Predicates, Predicate Expressions

Predicate Interpretation

The symbolic substitution of operations along the path in order to express the predicate
solely in terms of the input vector is called predicate interpretation.

An input vector is a set of inputs to a routine arranged as a one dimensional array.

Example:
INPUT X, Y INPUT X
ON X GOTO A, B, C IF X < 0 THEN Y:= 2
A: Z := 7 @ GOTO H ELSE Y := 1
B: Z := -7 @ GOTO H IF X + Y*Y > 0 THEN
C: Z := 0 @ GOTO H

H: DO SOMETHING

K: IF X + Z > 0 GOTO GOOD ELSE GOTO BETTER

Predicate interpretation may or may not depend on the path. IF -7 > 3 ..

Path predicates are the specific form of the predicates of the decisions along the selected
path after interpretation.
U2
ref boris beizer 34




Control Flow Graphs and Path Testing
Predicates, Predicate Expressions

Process Dependency

An input variable is independent of the processing if its value does not change as a result of
processing.

An input variable is process dependent if its value changes as a result of processing.

A predicate is process dependent if its truth value can change as a result of processing.

A predicate is process independent if its truth value does not change as a result of
processing.

Process dependence of a predicate doesnt follow from process dependence of variables

Examples: X + Y = 10 Increment X & Decrement Y.
X is odd Add an even # to X

If all the input variables (on which a predicate is based) are process independent, then
predicate is process independent.

U2
ref boris beizer 35




Control Flow Graphs and Path Testing
Predicates, Predicate Expressions

Correlation

Two input variables are correlated if every combination of their values cannot be specified
independently.

Variables whose values can be specified independently without restriction are uncorrelated.

A pair of predicates whose outcomes depend on one or more variables in common are
correlated predicates.


Every path through a routine is achievable only if all predicates in that routine are
uncorrelated.

If a routine has a loop, then at least one decisions predicate must be process dependent.
Otherwise, there is an input value which the routine loops indefinitely.
U2
ref boris beizer 36




Control Flow Graphs and Path Testing
Predicates, Predicate Expressions

Path Predicate Expression

Every selected path leads to an associated boolean expression, called the path predicate
expression, which characterizes the input values (if any) that will cause that path to be
traversed.

Select an entry/exit path. Write down un-interpreted predicates for the decisions along the
path. If there are iterations, note also the value of loop-control variable for that pass.
Converting these into predicates that contain only input variables, we get a set of boolean
expressions called path predicate expression.

Example (inputs being numerical values):

If X
5
> 0 .OR. X
6
< 0 then

X1 + 3X2 + 17 >= 0
X3 = 17
X4 X1 >= 14 X2



U2
ref boris beizer 37




Control Flow Graphs and Path Testing
Predicates, Predicate Expressions


A: X
5
> 0 E: X
6
< 0
B: X1 + 3X2 + 17 >= 0 F: X1 + 3X2 + 17 >= 0
C: X3 = 17 G: X3 = 17
D: X4 X1 >= 14 X2 H: X4 X1 >= 14 X2

Converting into the predicate expression form:

A B C D + E B C D ( A + E ) B C D


If we take the alternative path for the expression: D then

(A + E ) B C D


U2
ref boris beizer 38




Control Flow Graphs and Path Testing
Predicates, Predicate Expressions

Predicate Coverage:

Look at examples & possibility of bugs: A B C D A + B + C + D

Due to semantics of the evaluation of logic expressions in the languages, the entire
expression may not be always evaluated.

A bug may not be detected.
A wrong path may be taken if there is a bug.

Realize that on our achieving C2, the program could still hide some control flow bugs.

Predicate coverage:

If all possible combinations of truth values corresponding to selected path have been
explored under some test, we say predicate coverage has been achieved.

Stronger than branch coverage.

If all possible combinations of all predicates under all interpretations are covered, we
have the equivalent of total path testing.
U2
ref boris beizer 39




Control Flow Graphs and Path Testing
Testing blindness


coming to the right path even thru a wrong decision (at a predicate). Due to the

interaction of some statements makes a buggy predicate work, and

the bug is not detected by the selected input values.


calculating wrong number of tests at a predicate

by ignoring the # of paths to arrive at it.



Cannot be detected by path testing and need other strategies
U2
ref boris beizer 40




Control Flow Graphs and Path Testing
Testing blindness

Assignment blinding: A buggy Predicate seems to work correctly as the specific value
chosen in an assignment statement works with both the correct & buggy predicate.

Correct Buggy
X := 7 X := 7
IF Y > 0 THEN IF X + Y > 0 THEN (check for Y=1)

Equality blinding:

When the path selected by a prior predicate results in a value that works both for the
correct & buggy predicate.
Correct Buggy
IF Y = 2 THEN IF Y = 2 THEN ..
IF X + Y > 3 THEN IF X > 1 THEN (check for any X>1)

Self-blinding
When a buggy predicate is a multiple of the correct one and the result is
indistinguishable along that path.
Correct Buggy
X := A X := A
IF X - 1 > 0 THEN IF X + A -2 > 0 THEN (check for any X,A)
U2
ref boris beizer 41




Control Flow Graphs and Path Testing
Achievable Paths

1. Objective is to select & test just enough paths to achieve a satisfactory notion of
test completeness such as C1 + C2.

2. Extract the programs control flow graph & select a set of tentative covering paths.

3. For a path in that set, interpret the predicates.

4. Trace the path through, multiplying the individual compound predicates to achieve a
boolean expression. Example: (A + BC) ( D + E)

5. Multiply & obtain sum-of-products form of the path predicate expression:
AD + AE + BCD + BCE

6. Each product term denotes a set of inequalities that, if solved, will yield an input
vector that will drive the routine along the selected path.

7. A set of input values for that path is found when any of the inequality sets is solved.

A solution found => path is achievable. Otherwise the path is unachievable.
U2
ref boris beizer 42




Control Flow Graphs and Path Testing
Path Sensitization
U2
Heuristic procedures:
Choose an easily sensitizable path set, & pick hard-to-sensitize paths to achieve more coverage.
Identify all the variables that affect the decisions. For process dependent variables,
express the nature of the process dependency as an equation, function, or whatever is
convenient and clear. For correlated variables, express the logical, arithmetic, or
functional relation defining the correlation.
1. Identify correlated predicates and document the nature of the correlation as for variables.
If the same predicate appears at more than one decision, the decisions are obviously
correlated.
2. Start path selection with uncorrelated & independent predicates. If coverage is achieved,
but the path had dependent predicates, something is wrong.
Its the act of finding a set of solutions to the path predicate expression.
In practice, for a selected path finding the required input vector is not difficult. If there is difficulty, it
may be due to some bugs.
ref boris beizer 43




Control Flow Graphs and Path Testing
Path Sensitization Heuristic procedures: contd..

4. If the coverage is not achieved yet with independent uncorrelated predicates, extend the
path set by using correlated predicates; preferably process independent (not needing
interpretation)

U2
5. If the coverage is not achieved, extend the path set by using dependent predicates
(typically required to cover loops), preferably uncorrelated.
6. Last, use correlated and dependent predicates.
7. For each of the path selected above, list the corresponding input variables. If the variable
is independent, list its value. For dependent variables, interpret the predicate ie., list the
relation. For correlated variables, state the nature of the correlation to other variables.
Determine the mechanism (relation) to express the forbidden combinations of variable
values, if any.
8. Each selected path yields a set of inequalities, which must be simultaneously satisfied to
force the path.
ref boris beizer 44




Control Flow Graphs and Path Testing
Examples for Path Sensitization


1. Simple Independent Uncorrelated Predicates

U2
2. Independent Correlated Predicates

3. Dependent Predicates

4. Generic
ref boris beizer 45




Control Flow Graphs and Path Testing
Examples for Path Sensitization..
1. Simple Independent Uncorrelated Predicates
U2
1 4 2 7 6
A

C

B

D
9
3 5
10
8
a b e c d
f
h
l
i
j k
m
B
_
B
A
_
A
_
C
_
D
D
C
Path Predicate Values Path Predicate Values

abcdef A C abcdef A C
aghcimkf A B C D abcimjef A C D
aglmjef A B D abcimkf A C D
aghcdef A B C
aglmkf A B D
4 predicates => 16 combinations
Set of possible paths = 8
A Simple case of solving inequalities. (obtained by the procedure for finding a covering set of paths)
ref boris beizer 46




Control Flow Graphs and Path Testing
Examples for Path Sensitization

2. Correlated Independent Predicates
U2
1 4 2 6
Y

Y
3 5
a
c
g d
b
f
_
Y
Y
Y
_
Y
Correlated paths => some paths are unachievable
ie., redundant paths.
ie., n decisions but # paths are < 2
n


Due to practice of saving code which makes
the code very difficult to maintain.


Eliminate the correlated decisions.
Reproduce common code.

1
4
2 6
Y
3
a
c
g
f b
e
_
Y
Y
5
4 5
d
d
Correlated decision removed & CFG simplified
If a chosen sensible path is not achievable,
- theres a bug.
- design can be simplified.
- get better understanding of correlated decisions
ref boris beizer 47




Control Flow Graphs and Path Testing






U2
Examples for Path Sensitization

3. Dependent Predicates


Usually most of the processing does not affect the control flow.

Use computer simulation for sensitization in a simplified way.



Dependent predicates contain iterative loop statements usually.


For Loop statements:

Determine the value of loop control variable for a certain # of iterations, and then
work backward to determine the value of input variables (input vector).
ref boris beizer 48




Control Flow Graphs and Path Testing






U2
Examples for Path Sensitization
4. The General Case

No simple procedure to solve for values of input vector for a selected path.
1. Select cases to provide coverage on the basis of functionally sensible paths.
Well structured routines allow easy sensitization.
Intractable paths may have a bug.
If the solution is not found, path is not achievable, it could be a bug.
5. Continue until the entrance & therefore have established a set of input conditions for the path.
4. Continue tracing along the path. Pick the broadest range of values for variables affected
and consistent with values that were so far determined.
3. Start at the end of the path and list the predicates while tracing the path in reverse.
Each predicate imposes restrictions on the subsequent (in reverse order) predicate.
2. Tackle the path with the fewest decisions first. Select paths with least # of loops.
ref boris beizer 49




Control Flow Graphs and Path Testing






U2
Examples for Path Sensitization
4. The General Case contd..

Alternately:

1. In the forward direction, list the decisions to be traversed.
For each decision list the broadest range of input values.
Advantages & Disadvantages of the two approaches:
The forward method is usually less work.
you do not know where you are going as you are tracing the graph.
3. Continue. Some decisions may be dependent on and/or correlated with earlier ones.
2. Pick a path & adjust all input values. These restricted values are used for next decision.
4. The path is unachievable if the input values become contradictory, or, impossible.
If the path is achieved, try a new path for additional coverage.
ref boris beizer 50




Control Flow Graphs and Path Testing
PATH INSTRUMENTATION

Output of a test:

Results observed. But, there may not be any expected output for a test.
U2-1
Expected Outcome:
Any expected change or the lack of change at the output (predicted as part of
design).
Actual Outcome:
Observed outcome

Outcome:
Any change or the lack of change at the output.
ref boris beizer 51




Control Flow Graphs and Path Testing
PATH INSTRUMENTATION

Coincidental Correctness:

When expected & actual outcomes match,
Necessary conditions for test to pass are met.
Conditions met are probably not sufficient.
(the expected outcome may be achieved due to a wrong reason)

U2-1
X = 16 CASE SELECT Y := X - 14
Here
Y is 2
Y := 2
Y := X mod 14
Path Instrumentation is what we have to do confirm that the outcome was
achieved by the intended path.
ref boris beizer 52




Control Flow Graphs and Path Testing Questions from previous exams





U2
1. General strategy:

1. Based on Interpretive tracing & use interpreting trace program.

2. A trace confirms the expected outcome is or isnt obtained along the intended path.

3. Computer trace may be too massive. Hand tracing may be simpler.

2. Traversal or Link Makers:

Simple and effective

1. Name every link.

2. Instrument the links so that the link is recorded when it is executed (during the test)

3. The succession of letters from a routines entry to exit corresponds to the pathname.


PATH INSTRUMENTATION METHODS
ref boris beizer 53




Control Flow Graphs and Path Testing
Single Link Marker Instrumentation: An example
U2
Input
A,B,C
A = 7? j i
B$ =
a ?
k
No
No
o
C =
0 ?
l
n
m
No
B$ =
d ?
p
No
C
0 ?
q
s
r
No
Sample path: i j n
ref boris beizer 54




Control Flow Graphs and Path Testing
Single Link Marker Instrumentation: Not good enough
U2
Problem:
Processing in the links may be chewed open by bugs. Possibly due to GOTO
statements, control takes a different path, yet resulting in the intended path again.
m
A = 7? j i
No
k
?
n
No
Process C
Process A Process B
Process D
ref boris beizer 55




Control Flow Graphs and Path Testing
Double Link Marker Instrumentation:
U2
The problem is solved.

Two link markers specify the path name and both the beginning & end of the link.
m
A = 7? j i
o ? q Process C
Process A Process B
Process D
r
n
l
p
ref boris beizer 56




Control Flow Graphs and Path Testing
PATH INTRUMENTATION techniques
3. Link Counters Technique:

U2
Less disruptive and less informative.
Increment a link counter each time a link is traversed. Path length could confirm
the intended path.
For avoiding the same problem as with markers, use double link counters.
Expect an even count = double the length.
Now, put a link counter on every link. (earlier it was only between decisions)
If there are no loops, the link counts are = 1.
Sum the link counts over a series of tests, say, a covering set. Confirm the total link
counts with the expected.
Using double link counters avoids the same & earlier mentioned problem.
ref boris beizer 57




Control Flow Graphs and Path Testing
PATH INTRUMENTATION techniques
3. Link Counters Technique: contd..


Check list for the procedure:
U2
Do begin-link counter values equal the end-link counter values?
Does the input-link count of every decision equal to the sum of the link counts of the
output links from that decision?
Do the sum of the input-link counts for a junction equal the output-link count for that
junction?
Do the total counts match the values you predicted when you designed the covering
test set?
This procedure and the checklist could solve the problem of Instrumentation.
ref boris beizer 58




Control Flow Graphs and Path Testing
PATH INTRUMENTATION techniques


U2
Limitations
Instrumentation probe (marker, counter) may disturb the timing relations & hide
racing condition bugs.
Instrumentation probe (marker, counter) may not detect location dependent
bugs.

If the presence or absence of probes modifies things (for example in the data base)
in a faulty way, then the probes hide the bug in the program.
ref boris beizer 59




Control Flow Graphs and Path Testing





U2
PATH INTRUMENTATION - IMPLEMENTATION


For Unit testing : Implementation may be provided by a comprehensive test tool.
For higher level testing or for testing an unsupported language:

Introduction of probes could introduce bugs.
Instrumentation is more important for higher level of program structure like transaction flow
At higher levels, the discrepancies in the structure are more possible & overhead of
instrumentation may be less.
For Languages supporting conditional assembly or compilation:

Probes are written in the source code & tagged into categories.
Counters & traversal markers can be implemented.
Can selectively activate the desired probes.
For language not supporting conditional assembly / compilation:

Use macros or function calls for each category of probes. This may have less bugs.
A general purpose routine may be written.
In general:
Plan instrumentation with probes in levels of increasing detail.
ref boris beizer 60




Control Flow Graphs and Path Testing U2
Implementation & Application of Path Testing

1. Integration, Coverage, and Paths in Called Components
Mainly used in Unit testing, especially new software.

In an Idealistic bottom-up integration test process integrating one component at a time.
Use stubs for lower level component (sub-routines), test interfaces and then replace stubs by
real subroutines.
In reality, integration proceeds in associated blocks of components. Stubs may be avoided.
Need to think about paths inside the subroutine.

To achieve C1 or C2 coverage:
Predicate interpretation may require us to treat a subroutine as an in-line-code.
Sensitization becomes more difficult.
Selected path may be unachievable as the called components processing may block it.
Weaknesses of Path testing:

It assumes that effective testing can be done one level at a time without bothering what
happens at lower levels.
predicate coverage problems & blinding.
ref boris beizer 61




Control Flow Graphs and Path Testing





U2
Implementation & Application of Path Testing

2. Application of path testing to New Code
Do Path Tests for C1 + C2 coverage

Use the procedure similar to the idealistic bottom-up integration testing, using a
mechanized test suite.

A path blocked or not achievable could mean a bug.

When a bug occurs the path may be blocked.
ref boris beizer 62




Control Flow Graphs and Path Testing





U2
Implementation & Application of Path Testing

3. Application of path testing to Maintenance
Path testing is applied first to the modified component.

Use the procedure similar to the idealistic bottom-up integration testing, but without using
stubs.

Select paths to achieve C2 over the changed code.

Newer and more effective strategies could emerge to provide coverage in maintenance
phase.
ref boris beizer 63




Control Flow Graphs and Path Testing





U2
Implementation & Application of Path Testing


4. Application of path testing to Rehosting

Path testing with C1 + C2 coverage is a powerful tool for rehosting old software.

Software is rehosted as its no more cost effective to support the application
environment.

Use path testing in conjunction with automatic or semiautomatic structural test
generators.

ref boris beizer 64




Control Flow Graphs and Path Testing





U2
Process of path testing during rehosting

A translator from the old to the new environment is created & tested. Rehosting
process is to catch bugs in the translator software.
Implementation & Application of Path Testing
Application of path testing to Rehosting..

A complete C1 + C2 coverage path test suite is created for the old software. Tests
are run in the old environment. The outcomes become the specifications for the
rehosted software.
Another translator may be needed to adapt the tests & outcomes to the new
environment.
The cost of the process is high, but it avoids risks associated with rewriting the code.
Once it runs on new environment, it can be optimized or enhanced for new
functionalities (which were not possible in the old environment.)
ref boris beizer 65




Control Flow Graphs and Path Testing Questions from previous exams
For reference just to see that we have covered these:

Q. Define Path Testing. Explain three path testing criteria.

Q. Illustrate with an example, how statement and branch coverage can be achieved during path selection. Write
all steps involved in it.

Q. Write the effectiveness and limitations of path testing.

Q. Define Path Sensitization. Explain heuristic procedure for sensitizing paths with the help of an example.

Q. How can a program control structure be represented graphically? Explain with the help of required diagrams.

Q. How is a flowchart differed from a control flow chart?

Q. Explain about Multi entry and Multi exit routines & fundamental path selection criteria

Q. Explain about path instrumentation. How are link counters useful in Path Instrumentation method?

Q. Write about implementation of path testing. What are the various applications of path testing?

Q. Categorize different kinds of loops and explain.

U2
ref boris beizer 66




Software Testing Methodology








To Unit 3 Transaction flow testing

U2