Code-Based Test Coverage

Code-based test coverage of a software system refers to how thoroughly the various logical elements within the software source code are exercised by the test suite. If some logical elements are not exercised during testing, then could very likely be sources of latent defect remaining in the system after testing.

Whereas techniques that address test data adequacy without examining the source code are sometimes called black box techniques, the term white box adequacy is used for those techniques that do examine source code.

Control Flow Graphs

Control-flow graphs are diagrammatic representations of the structure of computational units, with nodes representing code segments and edges representing control flow. More precisely, a control-flow graph is a directed graph having the following specific node types.

*Pure decision nodes always have one incoming edge, while pure junction nodes always have one outgoing edge. To simplify diagrams and descriptions, junction nodes are often coalesced with a following processing or decision node.

For example, draw a control-flow graph for the integer division program.

q = 0;
r = x;
while (r >= y) {
  r = r - y;
  q = q + 1;
}

Control Flow Graph Primitives

For each type of structured statement or control feature in a language, a primitive control flow graph can be defined to show the canonical structure.

C-Style For Loops

for (i = 0; i < n; i++) {
   P(i);
}

What does the canonical primitive look like?

Switch Statements

switch  (x) {
   case a: P(x); break;
   case b: Q(x); break;
   case c: R(x); break;
}

Note that the default case (x is not a, b, or c) must be included as a path.

Short-Circuit Conditionals

The && and || operators introduce extra branching in the control flow graphs. Note that all branches must be taken for full branch coverage.

if (x == 0 || y/x > 1) {
    T(x, y);
}

Basic Structural Coverage: Statements and Branches

The two most elementary coverage techniques are related to the two fundamental structures of control-flow graphs.

Which is better: statement coverage or branch coverage?

• 100% statement coverage does not imply 100% branch coverage.
• 100% branch coverage does imply 100% statement coverage.
• Branch coverage therefore subsumes statement coverage and is generally considered the better criterion.

Condition-Based Coverage

When control-flow predicates are based on boolean combinations, it is possible that some combinations are not tested, even if all branches are taken.

if (x > 0 | y > 0) {
    T(x, y);
}

Here, there are four possible combinations of the two boolean conditions, but only two of them need be executed for full branch coverage.

The all-conditions coverage criterion requires that all combinations of basic predicates be executed. The all-conditions criterion subsumes branch coverage, which in turn subsumes statement coverage.

Path-Based Coverage

Control flow paths are sequences of nodes encountered during program execution. Even if statement or branch coverage is complete, there are often many path combinations that are not explicitly examined. Various kinds of path coverage attempt to address such deficiencies in test adequacy.

Consider branch coverage of the following example.

if (x > 0) {
    y = T(x);
}
else {
    y = U(x);
}
if (x%2 == 0) {
    z = V(y);
}
else {
    z = W(y);
}

Here, branch coverage would be complete by executing the program for two values: x=-1 and x=2. But there are four possible computations:

• z=(V(T(x))
• z=(V(U(x))
• z=(W(T(x))
• z=(W(U(x))

The all paths adequacy criterion would ensure that all combinations are tested by requiring that all entry-exit paths through the flow-graph are exercised.

In programs with loops, however, the paths that may be considered effectively become infinite, so it is impossible to apply this criterion.

Many alternative path-based criteria have been developed in the research literature. Most of them are computationally complex to apply. The most promising approaches focus on cycle-free definition-use paths.

• A definition point is a point at which a variable is assigned a value.
• A use point is a point at which the variable value is accessed.
• A definition-use path is a control flow path between a definition and a use of a given variable, with no intervening redefinition of the variable.
• The cycle-free all definition-use paths criteria ensures that every such definition-use path is covered.

Graph Coverage for Source Code

Read Chapter 2, Sections 2-1-2.3 of Paul Ammann and Jeff Offutt, Introduction to Software Testing. Cambridge University Press, 2008. SFU Library: in print or online. Quiz Thursday September 22 2016, 15:30, based on section 2.3 only.