Lukas' Notes

Path Coverage

2 min read

software-engineering testing

Definition

Path Coverage

Path coverage is a structural testing metric that measures the percentage of all possible execution paths through a program that have been executed.

Concept

A “path” is a unique sequence of nodes and edges from the entry block to the exit block of the Control Flow Graph.

  • Strength: It is the strongest standard coverage criterion. 100% path coverage implies 100% statement, branch, and basic block coverage.
  • Limitation (Feasibility): For programs with loops, the number of paths can be infinite (unbounded loops) or exponentially large (2^n paths for n sequential decisions). In practice, this makes full path coverage impossible for non-trivial software.

Example: The “Interaction” Bug

The lecture uses a specific example to show why Branch Coverage is insufficient compared to Path Coverage.

Scenario: Two independent if statements where one sets a variable to 0, and the other divides by it.

graph TD
    Entry --> A{A is True?}
    A -- Yes --> SetX["x = 0"]
    A -- No --> SetY["y = 0"]
    SetX --> B{B is True?}
    SetY --> B
    B -- Yes --> DivX["Return 5 / x"]
    B -- No --> DivY["Return 5 / y"]

Branch Coverage Failure:
We can achieve 100% Branch Coverage with just 2 tests:

  1. (Safe)
  2. (Safe)

Path Coverage Success:
Path Coverage requires 4 tests, forcing the combination A=True, B=True:

  • Path:
  • Result: Division by Zero Exception.

Lecture Insight

Path coverage detects bugs hidden in the interaction between code blocks that Branch Coverage might treat as independent.

Input-Dependent Loops

Loops create a new path for every possible iteration count, making full path coverage practically impossible.

while (n > 0) { ... } // Path count depends on value of n

Implication: Since the number of paths is potentially infinite (unbounded loops), testing is typically restricted to a limited number of iterations (e.g., 0, 1, >1), effectively reducing it to Loop Coverage.

Graph View

Backlinks