UNIT-II
FLOW GRAPHS AND PATH TESTING
1.Path Testing Basics:
1.Motivation and Assumption
o Path Testing is the name given to a family of test techniques based on
judiciously selecting a set of test paths through the program.
o If the set of paths are properly chosen then we have achieved some measure
of test thoroughness. For example, pick enough paths to assure that every
source statement has been executed at least once.
o Path testing techniques are the oldest of all structural test techniques.
o Path testing is most applicable to new software for unit testing. It is a
structural technique.
o It requires complete knowledge of the program's structure.
o It is most often used by programmers to unit test their own code.
o The effectiveness of path testing rapidly deteriorates as the size of the
software aggregate under test increases.
The Bug Assumption:
o The bug assumption for the path testing strategies is that something has
gone wrong with the software that makes it take a different path than
intended.
o As an example "GOTO X" where "GOTO Y" had been intended.
o Structured programming languages prevent many of the bugs targeted
by path testing: as a consequence the effectiveness for path testing for these
languages is reduced and for old code in COBOL, ALP, FORTRAN and Basic, the
path testing is indispensable.
2.Control Flow Graphs:
o The control flow graph is a graphical representation of a program's control
structure. It uses the elements named process blocks, decisions, and junctions.
o The flow graph is similar to the earlier flowchart, with which it is not to be
confused.
Flow Graph Elements:
A flow graph contains four different types of elements. (1) Process Block (2)
Decisions (3) Case Statements (4) Junctions
1. Process Block:
o A process block is a sequence of program statements uninterrupted by
either decisions or junctions.
o It is a sequence of statements such that if any one of statement of the
block is executed, then all statement thereof are executed.
o Formally, a process block is a piece of straight line code of one
statement or hundreds of statements.
o A process has one entry and one exit. It can consists of a single
statement or instruction, a sequence of statements or instructions, a
single entry/exit subroutine, a macro or function call, or a sequence of
these.
2. Decisions:
o A decision is a program point at which the control flow can diverge.
o Machine language conditional branch and conditional skip instructions
are examples of decisions.
o Most of the decisions are two-way but some are three way branches in
control flow.
3. Case Statements:
o A case statement is a multi-way branch or decisions.
o Examples of case statement are a jump table in assembly language, and
the PASCAL case statement.
o From the point of view of test design, there are no differences between
Decisions and Case Statements
4. Junctions:
o A junction is a point in the program where the control flow can merge.
o Examples of junctions are: the target of a jump or skip instruction in ALP,
a label that is a target of GOTO.
Control Flow Graphs Vs Flowcharts:
o A program's flow chart resembles a control flow graph.
o In flow graphs, we don't show the details of what is in a process block.
o In flow charts every part of the process block is drawn.
o The flowchart focuses on process steps, where as the flow graph focuses on
control flow of the program.
o The act of drawing a control flow graph is a useful tool that can help us
clarify the control flow and data flow issues.
A control flowgraph is a simplified representation of a program’s structure. We
will take the example of a program to understand the same.
INPUT A, B
X=A+B
Y=A-B
IF X > 0 GOTO LABEL1
LABEL2: X = X – 1
LABEL1:X = X + Y END
BEGIN X>0 LABEL2 LABEL1 END
4 5
1 2 3
3. Path Testing :
A.Paths, Nodes and Links:
A path is a sequence of instructions or statements that start at an entry,
junction or decision and at another or same entry, junction or decision,
or exit, through a program.
Path consists of segments.
The smallest segment is a link i.e. a single process that lies between two
nodes.
The length of a path is measured by the number of links in it or
alternatively, by the number of nodes traversed.
If a program is assumed to have a single entry and exit node, then the
number of links is just one less than the number of nodes traversed.
Because links are named by the pair of nodes joined by them, the name
of a path is the name of nodes along that path.
B.Multi-Entry/Multi-Exit Routines: if a routine can have several different kinds
of outcomes, then an exit parameter should be used. An alternative could be
to encapsulate the common parts into subroutines. Instead of using direct
linkages between multiple exits and entries, we handle the control flow by
examining the values of the exit parameter that can serve as an entry
parameter for the next routine or a return parameter for the calling routine.
The trouble with multi-entry and multi-exit routine is that it can be very
difficult to determine what the inter-process control flow is, and consequently
it is easy to miss important test cases. Further the use of such routines
increases the number of entries and exits and thus, the number of interfaces,
which means more test-cases than otherwise required.
C.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.
4.Path Testing Criteria:
1. Path testing : Execute all possible control flow paths through the program;
typically all possible entry/exit paths through the program. If we can achieve
this, we are said to have completed 100% path coverage.
2. Statement Testing : 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 or alternatively, 100% node coverage
3. Branch Testing : Execute enough tests to assure that every branch
alternative has been exercised at least once under some test. If we do enough
tests to achieve this prescription then we have achieved 100% branch coverage
or alternatively 100% link coverage.
PREDICATES, PATH PREDICATES AND ACHIEVABLE PATHS :
1.Predicates :
The value of the decision variable decides the direction taken at the decision.
For binary decisions, decision is taken in the form of a Boolean expression
whose outcome is either true or false. The logical function evaluated at a
decision is called a predicate. Every path corresponds to a succession of
TRUE/FALSE values for the predicates traversed on that path. A predicate
associated with a path is called a path predicate.
a.Multiway Branches :
The path taken through a multiway branch such as GOTO, case statements, or
jump statements (in assembly language) cannot be directly expressed in the
terms of TRUE/FALSE. Although such alternatives can be described in the terms
of multivalued logic, an easier expedient is to express multiway branches as an
equivalent set of IF..THEN..ELSE statements. This translation may not be
unique as there are several ways create a tree of IF..THEN..ELSE.
b.Inputs:
In testing, input does not only refer to the direct inputs in the form of
variables in a subroutine call, but includes all data objects referenced by the
routine whose values are fixed prior to entering it, e.g. inputs in a calling
sequence, objects in a data structure, values left in a register. Inputs can be
treated as numbers irrespective if they are numbers, Boolean, integers, etc.
Because an array can be mapped onto a onedimensional array, we can treat
the set of inputs to the routine as if it is a onedimensional array, which we call
input vector.
2. Predicate Expressions :
Predicate Interpretation:
The act of symbolic substitution of operations along the path in order to
express the predicate solely in terms of the input vector is called predicate
expression. The interpretation may depend upon the path. For example,
3.Independence and Correlation of Variables and Predicates:
The path predicates take on truth values (TRUE or FALSE) based on the values
of input variables, either directly or indirectly. A variable is independent of
processing if its value does not change as a result of processing. Conversely,
the variable is said to be process dependent if its value changes as a result of
processing. Similarly, a predicate whose truth value changes as a result of
processing is said to be process dependent and whose value does not change
as result of the processing is process independent.
Variables, whether process dependent or independent, may be correlated to
one another. Two variables are correlated if every combination of their values
cannot be independently specified. Variables whose values can be specified
independently without restriction are uncorrelated. By analogy, a pair of
predicates whose outcome depend on one or more variables in common
(whether or not those variables are correlated) are said to be correlated
predicates.
4.Predicate Coverage :
Compound predicates are those of the form A .OR. B or A .AND. B and more
complicate Boolean expressions. The branch taken at such decisions is
determined by the truth value of the entire Boolean expression. Predicate
coverage is said to have been achieved if all the possible combinations of truth
values corresponding to the selected path have been explored under some
test. It is stronger than branch coverage. If all the possible combinations of all
predicates are covered under all interpretations then it is equivalent to total
path testing.
5. Testing Blindness:
Testing blindness is a pathological situation in which the desired path is
achieved for wrong reason. It can occur because of the interaction of two or
more statements that make the buggy predicate work in spite of its bug and
because of an unfortunate selection of input values that does not reveal the
situation. We will be discussing three kinds of testing blindness:
Assignment blindness
Equality blindness and
Self blindness.
Assignment Blindness: Assignment blindness occurs when the erroneous
predicate appears to work correctly because the chosen value works with both
correct and incorrect predicate assignment statement .
If a test applies Y := 1, the desired path is taken in either case, but there still
exists a bug if a different value is assigned to X. In this case, the wrong path
would be taken because of the error in the predicate.
Equality Blindness:
Equality blindness occurs when the path selected by a prior predicate results
in a value that works both for correct and erroneous predicate. For example
The first predicate 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
erroneous versions.
Self-blindness:
Self-blindness occurs when the erroneous predicate is a multiple of the correct
predicate and as a result is indistinguishable along that path. For example
The assignment X = A, makes the two predicates multiples of each other, i.e. A
– 1 > 0 and 2A – 2 > 0, so the direction taken is the same for the correct and
incorrect version. A path with another assignment could behave differently
and would expose the bug.
PATH INSTRUMENTATION
1.Problem :
The outcome of a test is what we expect to happen as a result of testing. This
includes the outputs as well. Just like inputs, the test outcomes include
computer memory, mass storage, I/O, registers that should or should not have
changed as a result of tests conducted. When a test is run, we compare the
actual outcome with the expected outcome. If these match, we can say that
some of the conditions for passing have been satisfied but these are not
sufficient as the desired outcome could have been achieved for the wrong
reason. This situation is called coincidental correctness. Similarly, let us assume
that we ran a covering of tests and achieved the desired outcomes for each
case. Again, we cannot say that we have covered because the desired outcome
could have been achieved from the wrong path. Path instrumentation is what
is required to be done to confirm that the outcome was achieved by the
intended path. All instrumentation methods are the variations of an
interpretive trace. An interpretive trace program is the one that executes every
statement in order and records the intermediate values of all calculations, the
statements labels traversed, etc. The problem with these traces is that they
give us far more information than what is needed. Looking at the limitations of
the trace packages or symbolic debuggers, a variety of instrumentation
methods have emerged which are more suitable for testing.
2. Link Markers:
A simple and effective instrumentation is called a traversal marker or link
marker. Every link is named by a letter. Instrument the links so that its name is
recorded when it is executed. The series of letters produced while going from
the routine’s entry to its exit should exactly correspond to the path name if
there are no bugs. Also, a single link marker may not be sufficient because links
can be affected due to bugs.
3. Link Counters:
The method based on counters is less disruptive. Instead of pushing unique link
names while traversing the link, we simply increment the counter. The same
problem, as with single link markers, exists with single link counters. This leads
to double link counters. With these, we expect an even count which is double
the expected path length.
4.Implementation
For the source languages that support test tool, path instrumentation and
verification can be provided using this tool for unit testing. But for the
languages that do not support these tools, it has to be done the hard way.
Instrumentation is more important when the path testing is used at higher
levels of program structure e.g. in transaction flows rather than in unit level.
Also, the discrepancy between actual and intended structure becomes greater
at the higher level of structure.
