Path Testing- paths, nodes and links
• Path: 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 may go through several junctions, processes, or
decisions, one or more times.
• Paths consists of segments.
• The segment is a link – a single process that lies between
two nodes.
• Link is a single process (block) in between two nodes.
• Node is a junction or decision.
Path Testing- paths, nodes and links (Conti…)
• A path segment is succession of consecutive links that
belongs to some path.
• The length of path is measured by number of links in the
path or number of nodes traversed
• The name of a path is the name of the nodes along the
path.
• Path-Testing Path is an “entry to exit” path through a
processing block.
Fundamental Path Selection Criteria
• There are many paths between the entry and exit of a typical routine.
• Every decision doubles the number of potential paths. And every loop
multiplies the number of potential paths by the number of different
iteration values possible for the loop.
• Defining complete testing:
– Exercise every path from entry to exit
– Exercise every statement or instruction at least once
– Exercise every branch and case statement, in each direction at least
once
If prescription 1 is followed then 2 and 3 are automatically followed. But it
is impractical for most routines. It can be done for the routines that have
no loops, in which it is equivalent to 2 and 3 prescriptions.
Path selection criteria - example
PRESCRIPTION 1:
If ( X, LT,0) GOTO 200
X=X+A
200 X=X+A
300 CONTINUE
Path selection criteria - example (Conti..)
PRESCRIPTION 1:
Yes
If ( X, LT,0) GOTO 200
X=X+A 200
X=X+A ? no
300 CONTINUE
For X negative, the output is X + A, while for X greater than or equal
to zero, the output is X + 2A. Following prescription 2 and executing
every statement, but not every branch, would not reveal the bug in
the following incorrect version:
Path selection criteria - example (Conti..)
yes
PRESCRIPTION 1:
If ( X, LT,0) GOTO 200
X=X+A 200
? No
X=X+A
300 CONTINUE
A negative value produces the correct answer. Every statement
can be executed, but if the test cases do not force each branch to
be taken, the bug can remain hidden. The next example uses a
test based on executing each branch but does not force the
execution of all statements:
Path selection criteria - example (Conti..)
If (X) 200,150,150
100 X=X+A
GOTO 100
150 X=X+A
200 X=X+A
300 CONTINUE
The hidden loop around label 100 is not revealed by tests based
on prescription 3 alone because no test forces the execution of
statement 100 and the following GOTO statement.
Path Testing Criteria
• Any testing strategy based on paths must at least both
exercise every instruction and take branches in all
directions.
• A set of tests that does this is not complete in an
absolute sense, but it is complete in the sense that
anything less must leave something untested.
• So we have explored three different testing criteria or
strategies out of a potentially infinite family of strategies.
1. Path testing
2. Statement testing
3. Branch testing
Path Testing(P∞)
Execute all possible control flow paths through the
program: typically, this is restricted to all possible
entry/exit paths through the program.
If we achieve this prescription, we are said to have
achieved 100% path coverage. This is the strongest
criterion in the path testing strategy family: it is
generally impossible to achieve.
Statement Testing (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.
An alternate equivalent characterization is to say that we
have achieved 100% node coverage. We denote this by
C1.
This is the weakest criterion in the family: testing less
than this for new software is unconscionable and should
be criminalized.
Branch Testing ( P2)
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.
An alternative characterization is to say that we have
achieved 100% link coverage.
For structured software, branch testing and therefore
branch coverage strictly includes statement coverage.
We denote branch coverage by C2.
Common sense and strategies
• Branch and statement coverage are accepted today as
the minimum mandatory testing requirement.
• The question “ why not use a judicious sampling of
paths?”, what’s wrong with leaving some code,
untested?” is ineffectual in the view of common sense
and experience since:
– 1. not testing a piece of a code leaves a residue of bugs in
the program in proportion to the size of the untested code
and the probability of bugs.
– 2. the high probability paths are always thoroughly tested
if only to demonstrate that the system works properly.
Which paths to be tested?
You must pick enough paths to achieve C1+C2.
The question of what is the fewest number of such paths
is interesting to the designer of test tools that help
automate the path testing, but it is not crucial to the
pragmatic design of tests
Path Selection – Example
An example of path selection
• Draw the control flow graph on a single sheet of paper.
• Make several copies – as many as you will need for
coverage (C1+C2) and several more.
• Use a yellow highlighting marker to trace paths. Copy the
paths onto a master sheets.
• Continue tracing paths until all lines on the master sheet
are covered, indicating that you appear to have achieved
C1+C2.
• As you trace the paths, create a table that shows the
paths, the coverage status of each process, and each
decision.
Tracing table for Path Selection
An example of path selection (Conti..)
After you have traced a covering path set on the master
sheet and filled in the table for every path. Check the
following:
– Does every decision have a YES and NO in its column? (C2)
– Has every case of all case statements been marked? (C2)
– Is every three way branch covered? (C2)
– Is every link covered at least once? (C1)
Revised path selection rules
Pick the simplest, functionally sensible entry/exit path.
Pick additional paths as small variation from previous
paths. Pick paths that do not have loops rather than
paths that do. Favor short paths that make sense over
paths that don’t.
Pick additional paths that have no obvious functional
meaning only if it’s necessary to provide coverage.
Be comfortable with your chosen paths as long as you
achieve C1+C2.
Don’t follow rules slavishly-except for coverage.
