Control Flow Testing: CFGs, Cyclomatic Complexity, and Basis Path Analysis

Control flow testing treats code as a graph. Nodes are basic blocks (sequences of statements with no branches); edges are the control flow between them. Testing strategies based on this graph — basis path testing, loop testing, cyclomatic complexity — are the foundation of systematic white-box testing.

What is a Control Flow Graph (CFG)?

A control flow graph models program execution as a directed graph:

• Nodes: basic blocks — maximal sequences of statements that always execute together
• Edges: possible control flow transitions between basic blocks
• Entry node: the start of the function
• Exit node: the return point(s)

For a simple function:

def calculate_grade(score):          # Node 1 (entry)
    if score >= 90:                  # Node 1 → decision
        grade = 'A'                  # Node 2 (true branch)
    elif score >= 80:                # Node 3 (decision)
        grade = 'B'                  # Node 4 (true branch)
    else:                            # 
        grade = 'C or below'         # Node 5 (false branch)
    return grade                     # Node 6 (exit)

CFG edges:

• Node 1 → Node 2 (score >= 90)
• Node 1 → Node 3 (score < 90)
• Node 2 → Node 6
• Node 3 → Node 4 (score >= 80)
• Node 3 → Node 5 (score < 80)
• Node 4 → Node 6
• Node 5 → Node 6

The graph makes explicit which paths through the code exist.

Cyclomatic Complexity

McCabe's cyclomatic complexity (V(G)) measures the number of linearly independent paths through a CFG:

Formula 1: V(G) = E - N + 2

• E = number of edges
• N = number of nodes
• (For a connected graph with one entry and exit)

Formula 2: V(G) = number of decision points + 1

Formula 3: V(G) = number of regions in the planar graph + 1

For the grade example:

• Decisions: 2 (if score >= 90 and elif score >= 80)
• V(G) = 2 + 1 = 3

Cyclomatic complexity tells you:

• The minimum number of test cases needed for branch coverage (V(G) test cases)
• A measure of code complexity and testability
• An indicator of maintenance risk

Complexity thresholds

When a function exceeds V(G) = 10, consider refactoring. High cyclomatic complexity correlates with higher defect rates, not just testing difficulty.

Building a CFG

Basic blocks

A basic block is a maximal sequence of consecutive statements with no branches in or out (except at entry and exit).

x = 10           # \ 
y = x + 5        #  > One basic block (no branches)
z = y * 2        # /

if x > 0:        # Decision — ends the basic block, creates two edges
    x = x - 1   # True branch basic block
else:
    x = 0       # False branch basic block

return x         # Another basic block

Control structures and their CFG shapes

If-else:

Entry → [Decision] → [True branch] → [Merge]
                  → [False branch] → [Merge]

If without else:

Entry → [Decision] → [True branch] → [Merge]
                  ─────────────────→ [Merge]

While loop:

Entry → [Loop condition] → [Loop body] → (back to Loop condition)
                        → [Post-loop code]

For loop (equivalent structure to while with initialization)

Switch/match: Multiple edges from decision, one per case, all converge at the end.

CFG for loops

Loops require special attention. A while loop has:

• The condition check node (decision)
• The loop body node
• A back edge from body to condition

The CFG itself doesn't tell you how many times the loop executes. That's a path constraint, not a structural constraint. Testing loop iteration counts is separate from CFG-based testing.

Basis Path Testing

Basis path testing derives a set of paths that together provide branch coverage with the minimum number of test cases equal to V(G).

Derivation procedure

Step 1: Build the CFG and calculate V(G).

Step 2: Identify the baseline path — the simplest path from entry to exit (typically the main happy path).

Step 3: For each edge not yet covered, create a new path by starting from the baseline and taking the alternative edge at one decision point.

For the grade example (V(G) = 3):

Baseline path: 1 → 2 → 6 (score ≥ 90 → 'A')

Path 2: Cover the second branch at Node 1. Take the false branch: 1 → 3 → 4 → 6 (80 ≤ score < 90 → 'B')

Path 3: Cover the false branch at Node 3: 1 → 3 → 5 → 6 (score < 80 → 'C or below')

These 3 paths cover all edges. 3 test cases = V(G).

Basis path independence

The basis paths are linearly independent — no basis path can be expressed as a combination of others. This independence property means:

• The set is minimal (no redundant paths)
• Every additional path after the basis is redundant for structural coverage
• The basis paths form a "basis" for all possible paths through the function

Translating paths to test cases

For each basis path, identify input values that force execution along that path:

Loop Testing

Loops are a special case for CFG testing. The loop body can be executed 0, 1, many, or maximum times — each is a distinct case.

Simple loop testing strategy

For a loop iterating 0 to N times:

Nested loop testing

For nested loops, test the inner loop exhaustively while holding the outer loop at its minimum iteration count, then vary the outer loop:

1. Start with the innermost loop. Set all outer loops to minimum iteration counts.
2. Test innermost loop: 0, 1, typical, max iterations.
3. Move outward: set inner loops to typical iterations. Test next outer loop.
4. Repeat until outermost loop is tested.

Full combination testing of nested loops is infeasible (exponential). This strategy achieves reasonable coverage at polynomial cost.

Data Flow Analysis

Data flow testing extends CFG testing by tracking variable definitions and uses:

• Definition (def): a statement that assigns a value to a variable
• Use: a statement that reads the value of a variable
  • C-use (computation use): used in an expression or assignment
  • P-use (predicate use): used in a boolean condition

A def-use pair is a definition d and use u where there exists a path from d to u without another definition of the same variable (clear path).

Why data flow analysis finds different bugs than CFG

CFG analysis doesn't track what values flow through the graph. Data flow analysis finds:

Undefined variable use: a variable is used before being defined. The CFG may show the code executes, but data flow analysis shows there's no reaching definition.

Dead definitions: a variable is defined but never used (defined, then overwritten, or defined in dead code). May indicate a bug.

Missing use: a variable is defined in a branch but used after a merge point — but only if the defining branch is taken. Test must cover the path where the definition doesn't happen.

Testing all-defs and all-uses

All-defs coverage: for every definition, at least one path to some use is tested.

All-uses coverage: for every def-use pair (d, u), at least one path from d to u without re-definition is tested.

All-uses coverage subsumes all-defs coverage and provides deeper testing of data flow.

def process(x, flag):
    result = 0           # def: result (D1)
    if flag:
        result = x * 2   # def: result (D2); use: x
    else:
        result = x + 1   # def: result (D3); use: x
    return result        # use: result (U1)

Def-use pairs for result:

• (D1, U1): path where flag is false AND D3 doesn't execute... wait, D3 always executes when flag is False. D1 is always overwritten before U1. This means D1 is a dead definition!

Data flow analysis reveals D1 (result = 0) is a dead definition — it's always overwritten before use. This isn't a bug here (D1 is the initial value for safety), but in complex code it often is.

Cyclomatic Complexity in Practice

Tool measurement

# Python: radon
pip install radon
radon cc mymodule.py -a  # complexity per function, average

# JavaScript: ESLint complexity rule
{
  "rules": {
    "complexity": ["error", 10]  // fail if V(G) > 10
  }
}

# Java: PMD
pmd check -d src/ -R rulesets/java/design.xml

# Go: gocyclo
gocyclo -over 10 .

Integrate cyclomatic complexity into CI. Flag functions with V(G) > 10 as tech debt. Require refactoring for V(G) > 15 before merge.

Using complexity to allocate test effort

Functions with high cyclomatic complexity need more tests. Use V(G) as an allocation guide:

High-complexity functions should be refactored and tested more deeply. Refactoring alone reduces the test burden; testing alone manages the risk while refactoring is scheduled.

Summary

Control flow testing gives white-box testing a structural foundation. The CFG makes code paths explicit. Cyclomatic complexity quantifies testing effort. Basis path testing derives minimum coverage test sets. Loop testing addresses the variable-iteration special case.

For practical application: measure cyclomatic complexity in CI, use it to allocate test effort, derive basis paths for your highest-complexity functions, and test loops at 0, 1, typical, and maximum iterations.

The payoff: systematically derived test cases cover decision paths that ad hoc testing misses, and complexity metrics identify where to invest the effort.