50.003 - Code-based Testing : Path testing

Learning Outcomes

Construct a control flow graph from a structured program
Explain different types of test coverage metrics based on program graph
Apply path testing techniques to generate test case to attain path coverage and MCDC coverage.

Recall

Specification based testing
- Test cases are derived from the specification
- The goal is to ____
Code-based testing
- Test cases are defined by making use of the knowledge of the internal structure and algorithm used in the test subject.
- The goal is to ____

Code-based Testing

If there exists some bug in the program, it must be triggered by some sequence of statements from the program.

In order to find faults, the tests must cover all possible sequences of statements.

Programs as Graphs

As a convention, we write $\overline{S}$ to denote a sequence of statement $S_1;...;S_n$, $e$ to denote an expression, i.e. $x > 1$, $isTrue$, etc.

Let $P$ be a program, and $G$ to be the control flow graph of $P$, then

Each statement $S$ in $P$ denotes a vertex $V$ in $G$, written, $S \in P \vdash V \in G$, sometimes we omit the $P$ and $G$ for simplicity.
An edge $(V_1,V_2)$ exists in $G$ iff $S_1;S_2$ are two statements in sequence in $P$ such that $S_1 \vdash V_1$ and $S_2 \vdash V_2$.
Let ${\tt if}\ e\ \{\overline{S_1}\} {\tt else} \{\overline{S_2}\} \vdash V$ then edges $(V,V_1)$ and $(V, V_2)$ exist in $G$ iff
- $S_1$ is the first statement in $\overline{S_1}$ and $S_1 \vdash V_1$ and
- $S_2$ is the first statement in $\overline{S_2}$ and $S_2 \vdash V_2$.
Let ${\tt if}\ e\ \{\overline{S_1}\} {\tt else} \{\overline{S_2}\}; S'$ in $P$ and $S' \vdash V'$ then edges $(V_1',V')$ and $(V_2',V')$ exist in $G$ iff
- $S_1'$ is the last statement in $\overline{S_1}$ and $S_1' \vdash V_1'$ and
- $S_2'$ is the last statement in $\overline{S_2}$ and $S_2' \vdash V_2'$.
Let ${\tt while}\ e\ \{\overline{S_1}\} \vdash V$. Then edges $(V, V_1)$ exist in $G$ iff
- $S_1$ is the first stataement in $\overline{S_1}$ and $S_1 \vdash V_1$.
Let ${\tt while}\ e\ \{\overline{S_1}\} \vdash V$. Then edges $(V_1', V)$ exist in $G$ iff
- $V_1'$ is the last stataement in $\overline{S_1}$.

We can compile for loops to while loops before generating the control flow graph.

For example, consider the following program

// example A
function sum_all(arr) {
  let sum = 0;
  for (let i in arr) {
    sum = arr[i] + sum;
  }
  return sum;
}

will be compiled into

// example A
function sum_all(arr) {
  let sum = 0;
  let i = 0;
  while (i < arr.length) {
    sum = arr[i] + sum;
    i++;
  }
  return sum;
}

We can generate a control flow graph from sum_all

graph
  1-->2
  2-->3
  3-->4
  4-->5
  5-->3
  3-->7

where the vertex IDs are the line number of the statement.

Path

Given a graph $G$, a path $p$ is a sequence of vertices, $V_1,...,V_n$ in $G$ such that for all $i \in [1,n-1]$, $(V_i, V_{i+1})$ is an edge in $G$.

For example, in the above control flow graph, we have the following paths

$1$
$1,2,3$
$1,2,3,7$
$1,2,3,4,5,7$
$2,3$
...

Test Coverage Metrics

Program Graph-based coverage

There are following different levels of test coverage metrics for program testing

A set of tests constitute

node coverage if all nodes in the control flow graph are visited when the tests are executed.
edge coverage if all the edges in the control flow graph are viisted when the tests are executed.
condition coverage if all conditional predicates are evaluated to both true and false.
path coverage if all the paths in the control flow graph are visited when the tests are executed.

Note that condition coverage often works better than edge coverage as it forces the tests to exercise every single atomic predicates, i.e those are not formed by conjunction, disjunction and negation operator. Consider the following example

// example B
function div_by_zero(x,y) {
  if ((x==0) || (y>0)) {
    y = y/x;
  } else {
    x = y++;
  }
  return x + y;
}

Given the test cases

x = 5, y = -5
x = 7, y = 5

covers all the edges, however it does not discover the division by zero bug.

To trigger the bug, we would need to include the following test case

x = 0, y = 1

Which gives us condition coverage.

Note that path coverage is impossible the achieved without approximation in the presence of loops. In practice we are required to traverse each loop with a fixed number of times, often 1. Then we apply graph condensation, in which the cycles in the control flow graph is replaced by a single node.

For instance, in our running example, the result of the condensation processing is

graph
  1-->2
  2-->3'
  3'-->7

in which the loop 3-4-5 is merged into a single node 3' by assuming the loop terminates after $X$ of iterations.

Condition coverage vs path coverage

Note that neither path coverage entails condition coverage nor vice versa.

For example,

// example C
if ((x>0) || (x <-1)) {
  res = 1;
} else {
  res = 0;
}

To obtain path coverage, we could have two tests, i.e. x=1 and x = 0, which voilates condition coverage.

On the other hand,

// example D
if (x && y) {
  res = 1;
} else {
  res = 0;
}

Having {(x = true, y = false), (x = false, y = true)} we achieve condition coverage, but not path coverage nor edge coverage.

Note that condition coverage and edge coverage do not imply path coverage, either.

// example E
function f(x) {
  if (x > 1) {
    y = 1;
  } else {
    y = 0;
  }
  if (x > 0) {
    z = 1;
  } else {
    z = 0;
  }
  return y * z;
}

The test cases {(x = 2), (x = -1)} give us condition coverage and edge coverage. But we have not attained path coverage. e.g. we have not visited the path of taking the then-branch of the first if-statement followed by the else-branch of the second if-statement.

MCDC coverage

MCDC stands for Modified Condition Decision Coverage.

MCDC requires

Each statement must be executed at least once.
Every program entry point and exit point must be invoked at least once.
All possible outcomes of every control statement are taken at least once.
Every nonconstant Boolean expression has been evaluated to both true and false outcomes. A boolean expression is constant iff it is a tautology, e.g. a==a, a!=a and p && !p
Every nonconstant condition in a Boolean expression has been evaluated to both true and false outcomes.
Every nonconstant condition in a Boolean expression has been shown to independently affect the outcomes (of the expression).

Points 1 and 2 entail node coverage, 3 and 4 imply edge coverage. 5 implies condition coverage. 6 requires more explaination.

In the example D, to achieve MCDC coverage, we generate a decision table

cond	1	2	3	4
x	T	T	F	F
y	T	F	T	F
x && y	T	F	F	F
actions
res = 0	X
res = 1		X	X	X

In the above table, we conclude that if we fix x with one value, and toggle y's value we are able to obtain both actions. Similar observation applies when we fix y and toggle x. So we argue that we achieve MCDC coverage if we pick either

{ (x = true, y = true), (x = false, y = true), (x = true, y = false) } or
{ (x = true, y = true), (x = false, y = true), (x = false, y = false) }

While for example C

cond	1	2	3
x>0	T	F	F
x<-1	F	T	F
x >0 \|\| x<-1	T	T	F
actions
res = 1	X	X
res = 0			X

In the above table we realize that the two sub condition expresssions x>0 and x<-1 are dependent mutually, i.e. we can't hold x>0 to be true and toggle x<-1. In this example, we can still attain MCDC coverage by considering {x=1, x =-2, x=0}. If we adjust the example by replacing x >0 || x<-1 with x >0 && x < -1, there is no way we can attain MCDC coverage, because it is impossoble to find such a value of x to satisfy the condition.

Coverage Report in Jest

In Jest, we can enable to coverage report by adding the following to the package.json, assuming Jest has been enabled and installed.

  "jest": {
    "collectCoverage": true
    ,"coverageReporters": ["text", "html"]
  },

Assuming we have the sum_all.js file with code describe in the example A and the corresponding test code as follows,

// test/sum_all.test.js
const sum_all = require('../src/sum_all');
describe("test suite for sum_all", () => {
    test ("test 1 for sum_all", () => {
        const expected = 55;
        expect(sum_all([1,2,3,4,5,6,7,8,9,10])).toBe(expected);
    })
})

when we run npm run test sum_all.test.js, we see the following additional output

 PASS  test/sum_all.test.js
  test suite for sum_all
    ✓ test 1 for sum_all (3 ms)

------------|---------|----------|---------|---------|-------------------
File        | % Stmts | % Branch | % Funcs | % Lines | Uncovered Line #s 
------------|---------|----------|---------|---------|-------------------
All files   |     100 |      100 |     100 |     100 |                   
 sum_all.js |     100 |      100 |     100 |     100 |                   
------------|---------|----------|---------|---------|-------------------

We may also refer to the .html report generated in the coverage folder.

Unfortunately, we don't get condition coverage from jest builtin coverage analyzer. Consider the div_by_zero test. Given the div_by_zero function in example B and the test code as follows

// test/div_by_zero.test.js
const f = require('../src/div_by_zero');

describe("test suite for div_by_zero", () => {
    test ("test 1 for f", () => {
        const expected = -9;
        expect(f(5,-5)).toBe(expected);
    })
    test ("test 2 for f", () => {
        const expected = 7.714285714285714;
        expect(f(7,5)).toBeCloseTo(expected,5);
    })
})

running npm run test div_by_zero.test.js we find

----------------|---------|----------|---------|---------|-------------------
File            | % Stmts | % Branch | % Funcs | % Lines | Uncovered Line #s 
----------------|---------|----------|---------|---------|-------------------
All files       |     100 |      100 |     100 |     100 |                   
 div_by_zero.js |     100 |      100 |     100 |     100 |                   
----------------|---------|----------|---------|---------|-------------------

Path Testing

To conduct path testing, a general approach is

to generate enough test cases cover all paths with condensation (if possible).
in case of complex condition expression (esp with dependent condition expressions), we should construct a decision table to check impossibilities and generate additional test cases to ensure condition coverage.

In regard to the path generation, we first need to find out how many unique paths exist. Recall notion of cyclomatic complexity from graph theory class, that defines the number of linearly independent paths from the entry to the exit node.

$$ V(G) = e - n + 2p $$ where $e$ is the number of edges in $G$ and $n$ is the number of nodes in $G$ and $p$ denotes the number of connected components. Since we are dealing with one program at a time, the number of connected compoment is 1. (Note $p$ is not strongly connected component.)

By applying the above formula to the control flow graph from the max_all function, we find that in total there are 6 - 6 + 2 * 1 = 2 linearly unique paths from the entry to the exit, namely

$1,2,3,7$
$1,2,3,4,5,7$

We generate the test cases as follows,

id	arr	expected output
1	[]	0
2	[1,2,3,4,5,6,7,8,9,10]	55

Note that Cyclomatic Complexity only measures the number of uniquely linearly paths, which serves as the lower-bound of the path coverage. For instance, recall example E, the cyclomatic complexity of function f is 8-7+2*1 = 3. But there exist 4 executable paths. This is because when counting linearly paths, the first if-else gives us two paths, by including a second if-else adds an extra 1 uniquely linearly path (as alternative). To find all executale paths (with max 1-loop-unrolling), we need to rely on the condition coverage.

Now we have to verify whether we have attained MCDC for max_all. Since there is only one predicate i < arr.length we have already covered both possible outcome of the predicate, namely, we executed the body the loop as well as exit from the loop. Hence we argue that the above test cases is providing path and MCDC coverage.

Cohort Exercise (Graded)

Let's consider another example

function gcd(x,y) {
  let r = null;
  if ((x < 1) || (y < 1)) {
    r = null;
  } else {
    while (x != y) {
      if (x > y) {
        let t = x - y;
        x = y;
        y = t
      } else {
        let t = y - x;
        y = x;
        x = t;
      }
    }
    r = x;
  }
  return r;
}

construct CFG of the above program.
find the cyclomatic complexity of the CFG.
generate the test cases to cover all paths.
generate extra test cases (if needed) to attain MCDC coverage.
verify your test cases's coverage using jest (though it is only up to edge coverage)