Software Testing Methodologies Student Notes

Unit 2
STM
Software Testing Methodologies

Unit2:Flow graphs and Path testing

 Basics concepts of path testing

 Predicates
 Path predicates and achievable paths
 Path sensitizing
 Path instrumentation
 Applications of path testing

What is Path Testing ?

 Path testing is the name given to a family of test techniques based on selecting a set of
test paths through the program

 Differences between Control Flow graphs Versus Flowcharts ?

In control flow graphs, we don’t show the details of what is in a process block; In flowcharts, every
part of the process block is drawn: if a process block consists of 100 steps, the flowchart may
have 100 boxes. The flowchart focuses on process steps, whereas the control flowgraph ignores
them. The flowchart forces an expansion of representation which confuse the control flow, but the
flow graph compacts the representation and makes it easier to follow.

Control flow graph

 Control Flow graphs

 A process block* is a sequence of program statements uninterrupted by either decisions

or junctions. Formally, it is a sequence of statements such that if any one statement of the block
is executed, then all statements thereof are executed
 A decision is a program point at which the control flow can diverge.
 A junction is a point in the program where the control flow can merge.
 A case statement is a multiway branch or decision.

Sri Sivani college of Engineering 1

Software Testing Methodologies Student Notes

Unit 2

Control flow graph elements

Fundamentals of path testing

 Paths, Nodes, and Links

 A path through a program is a sequence of instructions or statements that starts at an
entry, junction, or decision and ends at another, or possibly the same, junction, decision, or exit
 A path segment is a succession of consecutive links that belongs to some path.
 The length of a path is measured by the number of links

Fundamental Path Selection Criteria

 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.

Sri Sivani college of Engineering 2

Software Testing Methodologies Student Notes

Unit 2

Explain about Path testing criteria ?

Path–Testing Criteria

 Path Testing (P)—Execute

(P)—Execute all possible control flow paths through the This is the
strongest criterion in the path–testing strategy family: it is generally impossible to achieve.

Statement Testing (P1)—Execute

(P1)—Execute all statements in the program at least once under some
test. If we do enough tests to achieve this, we are said to have achieved 100% statement
coverage.* (100% node coverage )We denote this by C1.

 Branch Testing (P2)—Execute enough tests to assure that every branch alternative has
been exercised at least once under some test. we have achieved 100% branch coverage ( 100%
link coverage). We denote branch coverage by C2.

Explain about The Kinds of Loops ?

 1) Simple loop 2) nested loop, 3) concatenated4) horrible.

Simple loop: Testing strategy

 Case 1—Single Loop, Zero Minimum, N Maximum, No Excluded Values
 Case 2—Single Loop, Nonzero Minimum, No Excluded Values

Sri Sivani college of Engineering 3

Software Testing Methodologies Student Notes

Unit 2
 Case 3—Single Loops with Excluded Values
 Nested Loops
– 1. Start at the innermost loop. Set all the outer loops to their minimum values.
– 2. Test the minimum, minimum + 1, typical, maximum – 1, and maximum for the innermost
loop, while holding the outer loops at their minimum–iteration–parameter values. Expand
the tests as required for out–of–range and excluded values.
– 3. If you’ve done the outermost loop, GOTO step 5, ELSE move out one loop and set it up
as in step 2—with all other loops set to typical values.
– 4. Continue outward in this manner until all loops have been covered.
– 5. Do the five cases for all loops in the nest simultaneously.

 Concatenated loops:
loops: Concatenated loops fall between single and nested loops with
respect to test cases. Two loops are concatenated if it’s possible to reach one after exiting the
other while still on a path from entrance to exit

Conversion of Multi–Exit or Multi–Entry Routines

Sri Sivani college of Engineering 4

Software Testing Methodologies Student Notes

Unit 2
An Example for satisfying C1 +C2 strategy

PATHS DECISIONS PROCESS—LINK

4 6 7 9 a b c d e f g h i j k l m
abcde YES YES ü ü ü ü ü
abhkgde NO YES NO ü ü ü ü ü ü ü
abhlibcde NO,YES YES YES ü ü ü ü ü ü ü ü
abcdfjgde YES NO,YES YES ü ü ü ü ü ü ü ü
abcdfmibcde YES NO,YES NO ü ü ü ü ü ü ü ü

 Explain about PREDICATES, PATH PREDICATES, AND

ACHIEVABLE PATHS ?

 Predicate: The logical function evaluated at a decision is called a predicate
Some examples: “A is greater than zero,”
“the fifth character has a numerical value of 31,”
“X is either negative or equal to 10,”
“X + Y = 3Z2 – 44,”
“Flag 21 is set.”

 Every path corresponds to a succession of TRUE/FALSE values for the predicates

traversed on that path.
As an example:
– “ ‘X is greater than zero’ is TRUE.”
– AND “ ‘X + Y = 3Z2 – 44’ is FALSE.”

Sri Sivani college of Engineering 5

Software Testing Methodologies Student Notes

Unit 2
AND “ ‘W is either negative or equal to 10’ is TRUE.” is a sequence of predicates whose
truth values will cause the routine to take a specific path.
 A predicate associated with a path is called a path predicate.

Predicate Expressions

 A set of Boolean expressions, all of which must be satisfied to achieve the selected path.
This set is called the path predicate expression. Assuming (for the sake of our example) that
the input variables are numerical, the expression is equivalent to a set of inequalities such as
– X1 + 3X2 + 17 >= 0
– X3 = 17
– X4 – X1 >= 14X2

 Any set of input values that satisfy all of the conditions of the path predicate expression
will force the routine to the path. If there is no such set of inputs, the path is not achievable. The
situation can be more complicated because a predicate could have an .OR. in it. For example:
– IF X5 > 0 .OR. X6 > 0 THEN . . .

 A single .OR., such as the above, gives us two sets of expressions, either of which, if
solved, forces the path. If we added the above expression to the original three we would have the
following two sets of inequalities:
 A: X5 > 0 E: X6 < 0
 B: X1 + 3X2 + 17 >= 0 B: X1 + 3X2 + 17 >= 0
 C: X3 = 17 C: X3 = 17
 D: X4 – X1 >= 14X2 D: X4 – X1 >= 14X2

 We can simplify our notation by using an uppercase letter to denote each predicate’s
truth value and then use boolean algebra notation to denote the predicate expression:
concatenation means “AND”, a plus sign means “OR”, and negation is denoted by an overscore.
The above example, using the boolean variable names shown above then becomes
– ABCD + EBCD = (A+E)BCD

 If we had taken the opposite branch at the fourth predicate, the inequality would be X4 –
X1 < 14X2 and the resulting predicate expression for that path would be (A+E)BCD

Explain about Testing blindness ?

 Testing blindness is a pathological situation in which the desired path is achieved

for the wrong reason. It can occur because of the interaction of two or more statements
that makes the buggy predicate “work” despite its bug and because of an unfortunate
selection of input values that does not reveal the situation.
 Assignment Blindness
 Assignment blindness occurs when the buggy predicate appears to work correctly
because the specific value chosen for an assignment statement works with both the correct and
incorrect predicate. Here’s an example:

Correct Buggy

Sri Sivani college of Engineering 6

Software Testing Methodologies Student Notes

Unit 2
X := 7 X := 7
.. …. ………

IF Y > 0 THEN IF X + Y > 0 THEN

 If the test case sets Y := 1 the desired path is taken in either case, but there is still a bug.
Some other path that leads to the same predicate could have a different assignment value for X,
so the wrong path would be taken because of the error in the predicate.
Testing blindness
 Equality blindness occurs when the path selected by a prior predicate results in a value
that works both for the correct and buggy predicate. For example,

Correct Buggy

IF Y = 2 THEN IF Y = 2 THEN
... .....
IF X + Y > 3 THEN. . . IF X > 1 THEN. . .

 The first predicate (IF Y = 2) forces the rest of the path, so that for any positive value of
X, the path taken at the second predicate will be the same for the correct and buggy versions.

Testing blindness
 Self–blindness occurs when the buggy predicate is a multiple of the correct predicate
and as a result is indistinguishable along that path. For example,

Correct Buggy
X := A X := A
.... ……
IF X – 1 > 0 THEN... IF X + A – 2 > 0 THEN

 The assignment (X := A) makes the predicates multiples of each other (for example, A –
1 > 0 and 2A – 2 > 0), so the direction taken is the same for the correct and buggy version. A path
with another assignment could behave differently and would reveal the bug.

:
 Achievable and Unachievable Paths and path sensitization:

– 1. select and test enough paths to achieve a C1 and/or C2. 2. Extract the program’s
control flow graph and select a set of covering paths.
– 3. For any path in that set, interpret the predicates along the path as needed to express
them in terms of the input vector.
– 4. Trace the path through, multiplying (Boolean) the individual compound predicates to
achieve a Boolean expression such as (A + BC)(D + E)(FGH)(IJ)(K)(L), where the terms in
the parentheses are the compound predicates met at each decision along the path and
each letter (A, B, . . .) stands for simple predicates.
– 5. Multiply out the expression to achieve a sum–of–products form:
ADFGHIJKL + AEFGHIJKL + BCDFGHIJKL + BCEFGHIJKL
– 6. Each product term denotes a set of inequalities that, if solved, will yield an input vector
that will drive the routine along the designated path
– 7. Solve any one of the inequality sets for the chosen path and you have found a set of
input values for the path.

Sri Sivani college of Engineering 7

Software Testing Methodologies Student Notes

Unit 2
 If you can find a solution, then the path is achievable. If you can’t find a solution to any of
the sets of inequalities, the path is unachievable. The act of finding a set of solutions to the path
predicate expression is called path sensitization.

Heuristic Procedures for Sensitizing Paths

 . Identify all variables that affect the decisions. Classify them as to whether they are process
dependent or independent.
 Classify the predicates as dependent or independent. A predicate based only on independent
input variables must be independent.
 Start path selection with uncorrelated, independent predicates.
 If coverage hasn’t been achieved using independent uncorrelated predicates, extend the path
set by using correlated predicates;
 If coverage hasn’t been achieved, extend the cases to those that involve dependent
predicates (typically required to cover loops),
 Last, use correlated, dependent predicates.
 For each path selected above, list the input variables corresponding to the predicates
required to force the path.
 8. Each path will yield a set of inequalities, which must be simultaneously satisfied to force
the path

PATH INSTRUMENTATION

 Path instrumentation is what we have to do to confirm that the outcome was achieved
by the intended path.

 Strategies: 1) link markers instrumentation

a) single link marker Instrumentation
b) Double linker marker Instrumentation

 2) link counters

link markers instrumentation: link markers is also called as traversed marker which
use small case letters for naming link. whenever a link is traversed the link name is recorded in
the marker. the concatenation of the names of all the links starting from an entry to an exit
gives the path name

Sri Sivani college of Engineering 8

Software Testing Methodologies Student Notes

Unit 2
Single linker instrumentation

in the above diagram the preferred route is JKL. If any routine is executed in that path J, K, L
markers would be recorded. so t we can check that whether it has been followed the correct path
or not.

Why single linker markers are not enough

In the above diagram, the desired path has to traverse is IKM. Single linker only record start of
the link . in the above diagram after visiting marker M, it has to follow the straight path, but it
jumps into some other process. but it will record IKM .we think that we had traversed IKM. but
actually after M marker it has taken some other path. so that why we will use Double linker
marker to represent every link.

Link Counters Instead of a unique link name to be pushed into a string when the link is
traversed, we simply increment a link counter. We now confirm that the path length is as
expected

APPLICATION OF PATH TESTING

 Path–testing methods are mainly used in
 unit testing, especially for new software
 integration coverage and paths in called components
 maintenance
 rehosting

Sri Sivani college of Engineering 9

Software Testing Methodologies Student Notes

Unit 2
_

Sri Sivani college of Engineering 10

Software Testing Methodologies Student Notes

Unit 2

Sri Sivani college of Engineering 11