Control Flow Testing

From Code to Graphs #

Control flow testing uses the structure of code — its branches, loops, and sequences — as the basis for test design. The primary tool is the control flow graph (CFG), which provides a visual representation of all possible execution paths.

Unlike black-box techniques that ignore implementation, control flow testing is a white-box technique that requires access to source code. It ensures that tests exercise the structural elements of the code.

Building a Control Flow Graph #

Basic Elements #

Every CFG consists of:

• Start node: Entry point of the function
• End node: Exit point(s) of the function
• Process nodes: Sequential statements (rectangles or circles)
• Decision nodes: Branching points — if, switch, ternary (diamonds)
• Junction nodes: Points where branches merge
• Edges: Directed arrows showing flow between nodes

Sequential Statements #

Sequential statements that always execute together collapse into a single node:

a = 1
b = 2
c = a + b

This is one node — no branching occurs.

If-Else Structures #

if condition:       # Decision node
    do_something()  # True branch node
else:
    do_other()      # False branch node
result = finish()   # Junction node

CFG: Decision → (True edge → do_something → Junction) and (False edge → do_other → Junction) → finish

Loops #

while condition:     # Decision node (also loop header)
    process()        # Loop body node
                     # Back edge returns to condition
post_loop()          # Exit from loop

The back edge from the loop body to the condition node is what creates a cycle in the graph.

Switch/Case Statements #

match status:
    case "active":    action_a()
    case "pending":   action_b()
    case "inactive":  action_c()
    case _:           default_action()

A switch creates a decision node with multiple outgoing edges — one per case.

Loop Testing Strategies #

Loops are the most error-prone control flow structures. A systematic approach tests loops at their boundaries:

Simple Loop Testing (Beizer’s Loop Testing) #

For a loop that can iterate 0 to N times:

Nested Loop Testing #

Testing all combinations of nested loops is exponential. The practical approach:

1. Start with the innermost loop. Set all outer loops to their minimum values. Test the inner loop using simple loop testing.
2. Move outward one level at a time. For each outer loop, fix inner loops at typical values and test the outer loop.
3. Test interactions by running the outer loop with the inner loop at boundary values.

Concatenated Loops #

Two loops in sequence: test each independently unless the second loop uses data produced by the first. If they share data, test them together.

Dominators and Post-Dominators #

Dominator: Node A dominates node B if every path from entry to B passes through A. The entry node dominates all nodes.

Post-dominator: Node A post-dominates B if every path from B to exit passes through A. The exit node post-dominates all nodes.

These concepts help identify:

• Loop headers — nodes that dominate the back edge source
• Natural loops — a back edge from node B to its dominator A defines a natural loop
• Critical edges — edges whose removal disconnects parts of the graph

Practical CFG Construction #

For real code, follow this process:

1. Number each statement or group sequential statements into blocks
2. Mark decision points (if, while, for, switch, ternary, try/catch)
3. Draw edges from each block to its successors
4. Mark back edges for loops
5. Verify: Entry should reach every node; every node should reach exit

Example: Order Processing #

def process_order(order):                    # Node 1: Entry
    if not order.items:                      # Node 2: Decision
        return {"error": "Empty order"}      # Node 3

    total = 0                                # Node 4
    for item in order.items:                 # Node 5: Loop decision
        if item.quantity <= 0:               # Node 6: Decision
            continue                         # Node 7
        total += item.price * item.quantity  # Node 8
                                             # Back edge to Node 5

    if total > 0:                            # Node 9: Decision
        tax = total * 0.1                    # Node 10
        return {"total": total + tax}        # Node 11
    else:
        return {"error": "Invalid total"}    # Node 12

Edges: 1→2, 2→3(T), 2→4(F), 4→5, 5→6(body), 5→9(exit loop), 6→7(T), 6→8(F), 7→5, 8→5, 9→10(T), 9→12(F), 10→11

From this CFG, cyclomatic complexity = 4 (edges - nodes + 2 = 12 - 10 + 2).

Exercise: Build and Test CFGs #

Problem 1 #

Draw the CFG and derive test cases for this function:

def authenticate(username, password, two_factor_code):
    user = find_user(username)

    if user is None:
        return "USER_NOT_FOUND"

    if not verify_password(user, password):
        user.failed_attempts += 1
        if user.failed_attempts >= 3:
            lock_account(user)
            return "ACCOUNT_LOCKED"
        return "WRONG_PASSWORD"

    if user.requires_2fa:
        if not verify_2fa(user, two_factor_code):
            return "INVALID_2FA"

    create_session(user)
    return "SUCCESS"

Problem 2 #

Apply loop testing to this function:

def find_duplicates(items, max_scan=100):
    seen = set()
    duplicates = []

    for i, item in enumerate(items):
        if i >= max_scan:
            break
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)

    return duplicates

CFG Analysis in Practice #

In real projects, you rarely draw CFGs by hand for every function. Instead:

1. Use tools. Many IDEs can visualize control flow. SonarQube reports complexity. Python’s dis module shows bytecode flow.
2. Focus on complex functions. Functions with V(G) > 10 benefit most from CFG analysis.
3. Look for structural patterns — deeply nested if-else, loops with multiple exits, exception handling paths.
4. Simplify first. If a CFG is too complex to draw, the function should probably be refactored.

Key Takeaways #

• Control flow graphs represent all possible execution paths through code
• Nodes are statement blocks; edges are flow between them; back edges create loops
• Loop testing follows Beizer’s strategy: 0, 1, 2, N-1, N, N+1 iterations
• Nested loops: test inner loops first, then work outward
• Dominators identify loop headers and critical structural relationships
• Cyclomatic complexity from the CFG gives the minimum number of basis path tests
• Use CFG analysis primarily for complex functions (V(G) > 10) where intuitive test design is insufficient