SOFTWARE TESTING

MODULE 3
Graph coverage

• Directed graphs form the foundation for many coverage criteria.

• They come from many sources and types of software artifacts, including control flow graphs
from source, design structures, finite state machines, state charts, and use cases, among others.

• We use the term artifact in the most general way, to be anything associated with the software,
including the requirements, design documents, implementation, tests, user manuals, and many
others.

• Graph criteria usually require the tester to “cover” the graph in some way, usually by traversing
specific portions of the graph.
Graph coverage
• Given an artifact under test, the idea is to extract a graph from that artifact.

• For example, the most common graph abstraction for source code maps executable statements and
branches to a control flow graph.

• It is important to recognize that the graph is not the same as the artifact, and usually omits certain
details.

• It is also possible for the same artifact to have several useful, but different, graph abstractions.

• The same abstraction that produces the graph from the artifact also maps test cases for the artifact to
paths in the graph.

• Accordingly, a graph-based coverage criterion evaluates a test set for an artifact in terms of how the
paths corresponding to the test cases “cover” the artifact’s graph abstraction.
Graph coverage

• A graph G formally is:

❖ a set N of nodes

❖ a set N0 of initial nodes, where N0 ⊆ N

❖ a set Nf of final nodes, where Nf ⊆ N

❖ a set E of edges, where E is a subset of N × N

Graph coverage

• Graphs are often drawn with bubbles and arrows.

• The nodes with incoming edges but no predecessor nodes are the initial nodes. The nodes with heavy
borders are final nodes.
Graph coverage

• A path is a sequence [n1, n2, ..., nM] of nodes, where each pair of adjacent nodes, (ni, ni+1), 1 ≤ i < M, is
in the set E of edges.

• The length of a path is defined as the number of edges it contains.

• Following the notation for edges, we say a path is from the first node in the path and to the last node in
the path.

• It is also useful to be able to say that a path is from (or to) an edge e, which simply means that e is the
first (or last) edge in the path.

• A cycle is a path that begins and ends at the same node.

Graph coverage

• Many test criteria require inputs that start at one node and end at another.

• This is only possible if those nodes are connected by a path.

• When we apply these criteria on specific graphs, we sometimes find that we have asked for a path that
for some reason cannot be executed.

• For example, a path may demand that a loop be executed zero times in a situation where the program
always executes the loop at least once.

• This kind of problem is based on the semantics of the software artifact that the graph represents.

• We emphasize that we are looking only at the syntax of the graph.

Graph coverage

• A node n (or an edge e) is syntactically reachable from node ni if there exists a path from node ni to n
(or edge e).

• A node n (or edge e) is also semantically reachable if it is possible to execute at least one of the paths
with some input.

• We can define the function reachG(x) as the portion of a graph that is syntactically reachable from

• the parameter x.

• The parameter for reachG() can be a node, an edge, or a set of nodes or edges.
Graph coverage

• From 1, it is possible to reach all nodes except 3 and 7.

• From the entire set of initial nodes {1, 2, 3}, it is possible to reach all nodes.

• If we start at 5, it is possible to reach all nodes except 1, 3, 4, and 7.

• If we start at edge (7, 10), it is possible to reach only 7, 10 and edge (7, 10).
Graph coverage

• Test path: A path p, possibly of length zero, that starts at some node in N0 and ends at some node in Nf

• A test path represents the execution of a set of test cases.

• The reason test paths must start in N0 is that test cases always begin from an initial node.

• It is important to note that a single test path may correspond to a very large number of test cases on the
software.

• It is also possible that a test path may correspond to zero test cases if the test path is infeasible.
Graph coverage

• For some graphs, all test paths start at one node and end at a single node.

• We call these single entry/single exit or SESE graphs.

• For SESE graphs, the set N0 has exactly one node, called n0, and the set Nf also has exactly one node,
called nf , which may be the same as n0.

• We require that nf be syntactically reachable from every node in N, and that no node in N (except nf )
be syntactically reachable from nf (unless n0 and nf are the same node).

• In other words, no edges start at nf , except when n0 and nf happen to be the same node.
Graph coverage

• Figure below is an example of a SESE graph.

• This particular structure is sometimes called a “double-diamond” graph, and corresponds to the control
flow graph for a sequence of two if-then-else statements.

• The initial node, 1, is designated with an incoming arrow (remember we only have one initial node),
and the final node, 7, is designated with a thick circle.

• Exactly four test paths exist in the double-diamond graph: [1, 2, 4, 5, 7], [1, 2, 4, 6, 7], [1, 3, 4, 5, 7],
and [1, 3, 4, 6, 7].
Graph coverage

• A test path p is said to visit node n if n is in p.

• Test path p is said to visit edge e if e is in p.

• The term visit applies well to single nodes and edges, but sometimes we want to consider subpaths.

• For subpaths, we use the term tour.

• Test path p is said to tour subpath q if q is a subpath of p.

• The first path of Figure, [1, 2, 4, 5, 7], visits nodes 1 and 2, visits edges (1, 2) and (4, 5), and tours the
subpath [2, 4, 5]
Graph coverage

• We define a mapping path G for tests, so for a test case t,

path G(t) is the test path in graph G that is executed by t.

• Figure illustrates a set of test cases and corresponding

test paths on a SESE graph with the final node nf = 3.

• Some edges are annotated with predicates that describe

the conditions under which that edge is traversed.

• So, in the example, if a is less than b, the only path is

from 1 to 2 and then on to 4 and 3.
Structural Coverage Criteria

• We define graph coverage criteria by specifying a set of test requirements, T R.

• We will start by defining criteria to visit every node and then every edge in a graph.

• The first criterion is probably familiar and is based on the old notion of executing every statement in a
program.

• This concept has variously been called “statement coverage,” “block coverage,” “state coverage,” and
“node coverage.” We use the general graph term Node Coverage.

• The requirements produced by a graph criterion are technically predicates that can have either the value
true (the requirement has been met) or false (the requirement has not been met).
Structural Coverage Criteria

• For the double-diamond graph in Figure, the test requirements for Node Coverage are: T R = {visit 1,
visit 2, visit 3, visit 4, visit 5, visit 6, visit 7}.

• That is, we must satisfy a predicate for each node, where the predicate asks whether the node has been
visited or not.
Node Coverage
• Node Coverage (Formal Definition): For each node n ∈ reachG(N0), T R contains the predicate “visit
n.”

• Node Coverage (NC): T R contains each reachable node in G.

• Node Coverage (NC) (Standard Definition): Test set T satisfies node coverage on graph G if and
only if for every syntactically reachable node n in N, there is some path p in path(T) such that p visits n.

• Eg: T R = {1, 2, 3, 4, 5, 6, 7}. Test path p1 = [1, 2, 4, 5, 7] meets the first, second, fourth, fifth, and
seventh test requirements, and test path p2 = [1, 3, 4, 6, 7] meets the first, third, fourth, sixth, and
seventh. Therefore, if a test set T contains {t1, t2}, where path(t1) = p1 and path(t2) = p2, then T
satisfies Node Coverage on G.
Edge Coverage
• Edge Coverage (EC): T R contains each reachable path of length up to 1, inclusive, in G.

Note: Consider a graph with a node that has no edges. Without the “up to” clause in the definition, Edge
Coverage would not cover that node. Intuitively, we would like edge testing to be at least as demanding
as node testing.
Edge Pair Coverage

• Edge-Pair Coverage (EPC): T R contains each reachable path of length up to 2, inclusive, in G.

Simple Path:

• A path from ni to nj is simple if no node appears more than once in the path, with the exception that the
first and last nodes may be identical.

• That is, simple paths have no internal loops, although the entire path itself may wind up being a loop.

• One useful aspect of simple paths is that any path can be created by composing simple paths.
Prime Path and Prime Path Coverage
• Prime Path: A path from ni to nj is a prime path if it is a simple path and it does not appear as a proper
subpath of any other simple path.

• Prime Path Coverage (PPC): T R contains each prime path in G.

Simple and Complete Round Trip Coverage

• A round trip path is a prime path of nonzero length that starts and ends at the same node.

• One type of round trip test coverage requires at least one round trip path to be taken for each node, and
another requires all possible round trip paths.

• Simple Round Trip Coverage (SRTC): T R contains at least one round-trip path for each reachable
node in G that begins and ends a round-trip path.

• Complete Round Trip Coverage (CRTC): T R contains all round-trip paths for each reachable node
in G.
Complete Path Coverage & Specified Path Coverage

• Complete Path Coverage (CPC): T R contains all paths in G.

• Complete Path Coverage is useless if a graph has a cycle, since this results in an infinite number of
paths, and hence an infinite number of test requirements.

• A variant of this criterion is, however, useful. Suppose that instead of requiring all paths, we consider a
specified set of paths.

• For example, these paths might be given by a customer in the form of usage scenarios.

• Specified Path Coverage (SPC): T R contains a set S of test paths, where S is supplied as a parameter.
Structural Coverage Criteria
Data Flow Criteria
• The next few testing criteria are based on the assumption that to test a program adequately, we should
focus on the flows of data values.

• Specifically, we should try to ensure that the values created at one point in the program are created and
used correctly.

• This is done by focusing on definitions and uses of values. A definition (def ) is a location where a
value for a variable is stored into memory (assignment, input, etc.).

• A use is a location where a variable’s value is accessed. Data flow testing criteria use the fact that
values are carried from defs to uses.

• We call these du-pairs (they are also known as definition-use, def-use, and du associations in the testing
literature).
Data Flow Criteria

• All variables involved in a decision are assumed to be used on the associated edges, so a and b are in
the use set of all three edges (1, 2), (1, 3), and (1, 4).
Data Flow Criteria
• An important concept when discussing data flow criteria is that a def of a variable may or may not
reach a particular use.

• The most obvious reason that a def of a variable v at location li (a location could be a node or an edge)
will not reach a use at location lj is because no path goes from li to lj .

• A more subtle reason is that the variable’s value may be changed by another def before it reaches the
use.

• Thus, a path from li to lj is def-clear with respect to variable v if for every node nk and every edge ek on
the path, k != i and k != j, v is not in def(nk) or in def(ek). That is, no location between li and lj changes
the value.

• If a def-clear path goes from li to lj with respect to v, we say that the def of v at li reaches the use at lj
Data Flow Criteria

• Du-path: A du-path with respect to a variable v is a simple

path that is def-clear with respect to v from a node ni for which
v is in def(ni) to a node nj for which v is in use(nj ).

• Figure gives an example of a graph annotated with defs and

uses.

• Rather than displaying the actual sets, we show the full

program statements that are associated with the nodes and
edges.

• This is common and often more informative to a human, but

the actual sets are simpler for automated tools to process
Data Flow Criteria
• Note that the parameters (subject and pattern) are considered to be explicitly defined by the first node
in the graph.

• That is, the def set of node 1 is def(1) = {subject, pattern}.

• Also note that decisions in the program (for example, if subject[iSub] == pattern[0]) result in uses of
the associated variables for both edges in the decision.

• That is, use(4, 10) ≡ use(4, 5) ≡ {subject, iSub, pattern}.

Data Flow Criteria

• Figure shows the same graph, but this time with the
def and use sets explicitly marked on the graph.

• Note that node 9 both defines and uses the variable

iPat.

• This is because of the statement iPat + +, which is

equivalent to iP at = iP at + 1.

• In this case, the use occurs before the def

Data Flow Criteria
• The test criteria for data flow will be defined as sets of du-paths.

• This makes the criteria quite simple, but first we need to categorize the du-paths into several groups.
The first grouping of du-paths is according to definitions.

• Specifically, consider all of the du-paths with respect to a given variable defined in a given node.

• Let the def-path set du(ni , v) be the set of du-paths with respect to variable v that start at node ni .

• The second, and more important, grouping of du-paths is according to pairs of definitions and uses.

• We call this the def-pair set. After all, the heart of data flow testing is allowing definitions to flow to
uses.
Data Flow Criteria
• To illustrate the notions of def-path sets and def-pair sets,
consider du-paths with respect to the variable iSub, which
has one of its definitions in node 10 in Figure.

• There are du-paths with respect to iSub from node 10 to

nodes 5 and 10, and to edges (3,4), (3,11), (4,5), (4, 10),
(7, 8), and (7,9).

• The def-path set for the use of iSub at node 10 is: du(10,
iSub) = {[10, 3, 4], [10, 3, 4, 5], [10, 3, 4, 5, 6, 7, 8], [10,
3, 4, 5, 6, 7, 9], [10, 3, 4, 5, 6, 10], [10, 3, 4, 5, 6, 7, 8, 10],
[10, 3, 4, 10], [10, 3, 11]}
Data Flow Criteria
• This def-path set can be broken up into the following def-pair
sets:

• du(10, 4, iSub) = {[10, 3, 4]}

• du(10, 5, iSub) = {[10, 3, 4, 5]}

• du(10, 8, iSub) = {[10, 3, 4, 5, 6, 7, 8]}

• du(10, 9, iSub) = {[10, 3, 4, 5, 6, 7, 9]}

• du(10, 10, iSub) = {[10, 3, 4, 5, 6, 10], [10, 3, 4, 5, 6, 7, 8, 10],

[10, 3, 4, 10]}

• du(10, 11, iSub) = {[10, 3, 11]}

Examples of Control Flow Criteria
Examples of Control Flow Criteria
CFG for Code
CFG for if statement
CFG for if statement with return
CFG for Switch-Case
CFG for Loops
CFG for Exceptions
Graph Coverage for Design Elements

● Use of data abstraction and object-oriented software has led to an increased

emphasis on modularity and reuse.
● This means that testing of software based on various parts of the design (design
elements) is becoming more important than in the past.
● These activities are usually associated with integration testing.
● One benefit of modularity is that the software components can be tested
independently, which is usually done by programmers during unit and module
testing.
Structural Graph Coverage for Design Elements

● Graph coverage for design elements usually starts by creating graphs that are based
on couplings between software components.
● Coupling measures the dependency relations between two units by reflecting their
interconnections; faults in one unit may affect the coupled unit.
● Coupling provides summary information about the design and the structure of the
software.
Structural Graph Coverage for Design Elements

● The most common graph used for structural design coverage is the call graph.
● In a call graph, the nodes represent methods (or units) and the edges represent
method calls.
● Figure represents a small program that contains six methods. Method A calls B, C,
and D, C calls E and F, and D also calls F.
Structural Graph Coverage for Design Elements
Structural Graph Coverage for Design Elements

● Node Coverage requires that each method be called at least once and is also
called Method Coverage.
● Edge Coverage requires that each call be executed at least once and is also called
Call Coverage.
● Node Coverage requires that each method be called at least once, whereas Edge
Coverage requires that F be called at least twice, once from C and once from D
Structural Graph Coverage for Design Elements

Inheritance and Polymorphism

● The object-oriented language features of inheritance and polymorphism introduce

new abilities for designers and programmers, but also new problems for testers.
● In OO programming, classes are not directly tested because they are not
executable.
● In fact, the edges in the inheritance hierarchy do not represent execution flow at all,
but rather inheritance dependencies. To apply any type of coverage, we first need a
model for what coverage means.
Structural Graph Coverage for Design Elements
Inheritance and Polymorphism

● The first step is to require that objects be instantiated for some or all of the classes.
Figure shows the inheritance hierarchy with one object instantiated for each class.
Structural Graph Coverage for Design Elements

Inheritance and Polymorphism

● The most obvious interpretation of Node Coverage for this graph is to require that at
least one object be created for each class.
● However, this seems weak because it says nothing about execution.
● The logical extension is to require that for each object of each class, the call graph
must be covered according to the Call Coverage criterion and is called OO Call
Coverage criterion
● An extension of this is the All Object Call criterion, which requires that Call Coverage
is satisfied for every object that is instantiated for every class.
Data Flow Graph Coverage for Design Elements

● Control connections among design elements are simple and straightforward and
tests based on them are probably not very effective at finding faults. On the other
hand, data flow connections are often very complex and difficult to analyze.
● The primary issue is where the defs and uses occur.
● When testing program units, the defs and uses are in the same unit. During integration
testing, defs and uses are in different units.
Data Flow Graph Coverage for Design Elements

● A caller is a unit that invokes another unit, the callee.

● The statement that makes the call is the call site.
● An actual parameter is in the caller; its value is assigned to a formal parameter in the
callee.
● The call interface between two units is the mapping of actual to formal parameters.
Data Flow Graph Coverage for Design Elements

● The underlying premise of the data flow testing criteria for design elements is that to
achieve confidence in the interfaces between integrated program units, it must be
ensured that variables defined in caller units be appropriately used in callee units.
● This technique can be limited to the unit interfaces, allowing us to restrict our
attention to the last definitions of variables just before calls to and returns from the
called units, and the first uses of variables just after calls to and returns from the called
unit.
Data Flow Graph Coverage for Design Elements
Data Flow Graph Coverage for Design Elements

● Three types of data flow couplings have been identified. The most obvious is
parameter coupling, where parameters are passed in calls.
● Shared data coupling occurs when two units access the same data object as a
global or other non-local variable, and external device coupling occurs when two
units access the same external medium such as a file.
● We use the general term coupling variable for variables that are defined in one unit
and used in another
Data Flow Graph Coverage for Design Elements

● This form of data flow is concerned only with last-defs before calls and returns and
first uses after calls and returns.
● That is, it is concerned only with defs and uses immediately surrounding the calls
between methods.
● The last-defs before a call are locations with defs that reach uses at call sites and the
last-defs before a return are locations with defs that reach a return statement.
● Last-def: The set of nodes that define a variable x for which there is a def-clear path
from the node through the call site to a use in the other unit
Data Flow Graph Coverage for Design Elements

● A path from ni to nj is use-clear with respect to variable v if for every node nk on the
path, k != i and k = j, v is not in use(nk).
● First-use: The set of nodes that have uses of a variable y and for which there exists a
path that is def-clear and use-clear from the entry point (if the use is in the callee) or
the call site (if the use is in the caller) to the nodes.
Data Flow Graph Coverage for Design Elements

Coupling du-pairs Last-defs and First-use