Session 3.8 - Path Testing, Cyclomatic Complexity & White-box Summary

Concept Overview

Path testing is the most comprehensive white-box technique: it requires every unique execution path from entry to exit to be exercised. While theoretically complete, loops make exhaustive path coverage infeasible. Cyclomatic complexity (CC) provides a practical, measurable upper bound on the number of independent paths and serves as a code complexity metric. McCabe's Basis Path Testing combines both into an actionable test design method.

Path Testing
Every distinct route through the CFG from entry to exit is executed at least once. Theoretically the strongest coverage criterion.

Cyclomatic Complexity
A quantitative measure of code complexity based on the number of linearly independent paths. Also the minimum number of tests needed for basis path coverage.

Basis Path Testing
McCabe's method of selecting a minimum set of linearly independent paths whose combinations generate all other paths. Achieves full branch coverage.

Path Testing

Path coverage requires that every unique execution path from the entry node to an exit node in the CFG is exercised by at least one test case. It is the strongest structural coverage criterion.

Definition: execution path

An execution path is a sequence of nodes and edges in the CFG starting at the entry node and ending at an exit node, following directed edges. Two paths are distinct if they traverse a different sequence of nodes or edges.

Feasible vs Infeasible Paths

Feasible path: A path that can actually be executed by some input combination. All nodes and edges along the path are reachable simultaneously.
Infeasible path: A path that exists in the CFG but cannot be exercised by any input because the conditions along the path contradict each other. Example: a path that requires x > 5 and x < 3 simultaneously.

The loop problem

For a loop that executes up to k times, the number of paths multiplies by (k+1) for each additional loop iteration. A simple for i in range(100) creates 101 loop exit paths. Nested loops create combinatorial explosion.

This is why exhaustive path coverage is considered theoretically complete but practically infeasible for most real-world code. Cyclomatic complexity and basis path testing provide a workable solution.

Path Testing Worked Example

Consider the following insurance premium calculator:

def calculate_premium(age, smoker, pre_existing):
    base = 1000                          # N1
    if age > 50:                           # N2 decision
        base += 500                       # N3
    if smoker:                              # N4 decision
        base += 800                       # N5
    if pre_existing:                        # N6 decision
        base *= 2                          # N7
    return base                            # N8

All distinct paths (3 independent decisions, no loops)

Path	Nodes	Conditions	Premium
P1	N1→N2(T)→N3→N4(T)→N5→N6(T)→N7→N8	age>50, smoker, pre_existing	(1000+500+800)×2 = 4600
P2	N1→N2(T)→N3→N4(T)→N5→N6(F)→N8	age>50, smoker, no pre_existing	2300
P3	N1→N2(T)→N3→N4(F)→N6(T)→N7→N8	age>50, non-smoker, pre_existing	(1500)×2 = 3000
P4	N1→N2(T)→N3→N4(F)→N6(F)→N8	age>50, non-smoker, no pre_existing	1500
P5	N1→N2(F)→N4(T)→N5→N6(T)→N7→N8	age≤50, smoker, pre_existing	(1000+800)×2 = 3600
P6	N1→N2(F)→N4(T)→N5→N6(F)→N8	age≤50, smoker, no pre_existing	1800
P7	N1→N2(F)→N4(F)→N6(T)→N7→N8	age≤50, non-smoker, pre_existing	2000
P8	N1→N2(F)→N4(F)→N6(F)→N8	age≤50, non-smoker, no pre_existing	1000

Full path coverage requires all 8 tests (2³ for 3 independent binary decisions). Note: this equals the MCC count for these conditions — because each decision here has only one condition.

Loop Coverage Strategies

Loops create theoretically infinite paths. Beizer's loop testing strategy provides a practical set of test cases that cover the most defect-prone loop behaviours without exhaustive iteration testing.

Beizer's Simple Loop Test Cases

Test Case	Iterations	Purpose
Skip the loop entirely	0	Tests the loop-false branch. Verifies behaviour when the loop body is never executed.
One pass through loop	1	Tests minimal loop execution. Catches off-by-one errors at the start.
Two passes through loop	2	Tests multi-iteration behaviour. Catches errors in iteration logic (accumulator reset, counter increment).
Typical number of passes	m (middle)	Tests normal operational behaviour for a representative iteration count.
One below maximum	max - 1	Tests near-boundary behaviour.
Maximum iterations	max	Tests boundary at upper limit. Catches buffer overflow, off-by-one at termination.
One above maximum	max + 1	Tests over-boundary rejection. Verifies loop guard correctly prevents excess iterations.

Nested loop strategy

For nested loops, test from innermost to outermost:

Fix outer loop at minimum, exercise inner loop through all Beizer cases.
Fix inner loop at typical, exercise outer loop through all Beizer cases.
Test both at minimum, both at maximum, and one at minimum with the other at maximum.

Cyclomatic Complexity

Cyclomatic complexity (CC), introduced by Thomas McCabe in 1976, is a quantitative measure of the number of linearly independent paths through a program. It acts as both a testing metric (minimum tests needed) and a code quality/maintainability indicator.

Three equivalent computation methods

Method	Formula	Where
Method 1: Graph	`CC = E − N + 2P`	E = edges, N = nodes, P = connected components (usually 1 for a single function)
Method 2: Decision	`CC = D + 1`	D = number of decision points (binary predicates: if, while, for, case, &&, \|\|, ?:)
Method 3: Region	`CC = R`	R = number of closed regions in the planar CFG (including the outer region)

Important note on boolean operators

Short-circuit boolean operators && (AND) and || (OR) each add 1 to the decision count. For example, if (A && B) has 2 binary predicates, so it contributes 2 to D, giving CC contribution of 2 from this one if statement.

Cyclomatic Complexity — Worked Example

Consider the insurance premium function from earlier, extended with a loyalty discount loop:

def calculate_premium_v2(age, smoker, pre_existing, years):
    base = 1000                             # N1
    if age > 50:                              # N2 – D1
        base += 500                          # N3
    if smoker:                                 # N4 – D2
        base += 800                          # N5
    if pre_existing:                           # N6 – D3
        base *= 2                             # N7
    discount = 0
    i = 0                                     # N8
    while i < years:                          # N9 – D4
        discount += 50                       # N10
        i += 1
    base -= discount                           # N11
    return base                               # N12

Method 1: Graph formula (E − N + 2P)

Nodes: N1 through N12 = 12 nodes. Edges: N1→N2, N2→N3(T), N2→N4(F), N3→N4, N4→N5(T), N4→N6(F), N5→N6, N6→N7(T), N6→N8(F), N7→N8, N8→N9, N9→N10(T), N9→N11(F), N10→N9 (back-edge), N11→N12 = 15 edges.

CC = E − N + 2P = 15 − 12 + 2(1) = 5

Method 2: Decision count (D + 1)

Decision points: D1 (age > 50), D2 (smoker), D3 (pre_existing), D4 (i < years) = 4 decisions.

CC = D + 1 = 4 + 1 = 5

Method 3: Region count

Count closed regions in the planar CFG: Region 1 (D1 branch), Region 2 (D2 branch), Region 3 (D3 branch), Region 4 (D4 loop body). Plus the outer (unbounded) region = 5 regions.

CC = R = 5

All three methods agree: CC = 5

This means the minimum number of linearly independent paths (basis paths) = 5. A basis path test set of 5 test cases achieves 100% branch coverage.

Interpreting Cyclomatic Complexity

McCabe's complexity thresholds

CC Value	Risk Level	Interpretation	Action
1 – 10	Simple	Code is straightforward. Easy to test and maintain.	Normal testing; no refactoring needed.
11 – 20	Moderate	Code is moderately complex. Some risk of defects.	Thorough testing; consider refactoring large functions.
21 – 50	High	Complex code with significant defect risk.	Mandatory refactoring before release. Prioritise testing.
> 50	Untestable	Code is too complex to test reliably. High maintenance cost.	Restructure completely. Do not ship without major rework.

CC as test count guide
CC = minimum number of test cases needed for basis path (100% branch) coverage. CC = 5 means at minimum 5 tests are required to exercise all independent paths.

CC as maintainability metric
High CC correlates with higher defect density, longer debugging time, and greater resistance to change. Many teams enforce CC ≤ 10 per function via linting rules.

Tools
lizard (Python/multi-language), PMD (Java), ESLint complexity rule (JS), Radon (Python), SonarQube (multi-language). Most CI pipelines can enforce CC thresholds automatically.

Basis Path Testing (McCabe's Method)

Basis path testing is McCabe's structured method for selecting a minimum set of linearly independent test paths that guarantee 100% branch coverage. The number of basis paths equals the cyclomatic complexity.

Steps for basis path testing

Draw the CFG from the source code.
Compute the cyclomatic complexity (CC). This is the number of basis paths.
Select a base path: any complete path from entry to exit (usually the happy-path or most common execution).
Derive additional independent paths: each new path must differ from all previous paths by flipping at least one new branch that was not flipped before. Re-use as many edges as possible from existing paths.
Stop when you have CC paths. This set is the basis path set.
Design one test case per basis path that forces execution of exactly that path.

Basis path test set for calculate_premium_v2 (CC = 5)

Path	Route	Test Inputs	Purpose
BP-1 (base)	N1→N2(F)→N4(F)→N6(F)→N8→N9(F)→N11→N12	age=30, smoker=F, pre=F, years=0	All false branches; no loop. Base = 1000.
BP-2	Flip D1: N2(T)→N3, rest same as BP-1	age=60, smoker=F, pre=F, years=0	Covers age > 50 branch. Base = 1500.
BP-3	Flip D2: N4(T)→N5, rest same as BP-1	age=30, smoker=T, pre=F, years=0	Covers smoker branch. Base = 1800.
BP-4	Flip D3: N6(T)→N7, rest same as BP-1	age=30, smoker=F, pre=T, years=0	Covers pre-existing branch. Base = 2000.
BP-5	Flip D4: N9(T)→N10→N9(F)→N11, rest same as BP-1	age=30, smoker=F, pre=F, years=3	Covers while loop. Base = 1000 − 150 = 850.

Verification: all 8 branches covered by the 5 basis paths

D1=T: BP-2. D1=F: BP-1, BP-3, BP-4, BP-5.
D2=T: BP-3. D2=F: BP-1, BP-2, BP-4, BP-5.
D3=T: BP-4. D3=F: BP-1, BP-2, BP-3, BP-5.
D4=T: BP-5. D4=F: BP-1, BP-2, BP-3, BP-4.
All 8 branches (4 × 2) covered. BC = 100%.

White-box Testing Module Summary

Complete coverage criteria hierarchy — Sessions 3.5 to 3.8

Session	Criterion	Element Covered	Min Tests (n vars/conditions)	Subsumes
3.5	CFG construction	Foundation for all white-box techniques	—	—
3.6	Statement Coverage (SC)	Every executable statement	1 (ideal)	—
3.6	Branch Coverage (BC)	Every branch T and F of every decision	2–n	SC
3.7	Condition Coverage (CC)	Each atomic condition T and F	2–n	Not BC
3.7	B/CC	BC + CC simultaneously	2–n	SC, BC, CC
3.7	MC/DC	Each condition independently affects decision	n+1 per decision	SC, BC, CC
3.7	Multiple Condition (MCC)	All 2ⁿ condition combinations	2ⁿ	All
3.8	Path Coverage (PC)	Every entry-to-exit path	Exponential / CC	All
3.8	Basis Path Testing	CC linearly independent paths	= CC	SC, BC

Choosing the Right Criterion

Decision guide: which criterion to apply?

Scenario	Recommended Criterion	Reason
Simple CRUD function, low risk	Statement Coverage (80%+)	Minimum cost, catches obvious untested code.
Standard enterprise module	Branch Coverage (80–100%)	Catches false-branch defects. Good ROI.
Module with compound conditions (AND/OR)	Branch/Condition Coverage or MC/DC	Ensures individual conditions are properly tested.
Safety-critical software (aviation, medical, automotive)	MC/DC	Required by DO-178C, ISO 26262, IEC 62304.
Complex function with many paths	Basis Path Testing (CC-driven)	Structured, measurable, guarantees BC with minimum tests.
Function with unbounded loops	Branch Coverage + Beizer loop cases	Path coverage is infeasible; loop boundary tests cover risk.

Practical workflow recommendation

Compute cyclomatic complexity of each function. Flag anything above 10 for refactoring.
Run coverage tool after unit tests and review the report.
Target 100% branch coverage for all functions with CC ≤ 10.
For functions with compound conditions, add MC/DC test cases.
For high-CC functions (>10), apply basis path testing to systematically derive the test set.
Document any intentionally uncovered branches (e.g., dead-code defensive checks) in the test plan.

Common Mistakes

Treating infeasible paths as gaps
Infeasible paths cannot be exercised by any input. Attempting to cover them wastes effort. Document and exclude them from coverage targets with justification.

Miscounting decisions for CC
Forgetting that && and || each add 1 to the decision count. A single if (A && B && C) contributes 3 to D, not 1.

Selecting non-independent basis paths
Basis paths must be linearly independent (each introduces at least one new edge not in any previous path). Selecting similar paths duplicates effort without improving coverage.

Ignoring loop boundary tests
Testing a loop only with a typical iteration count misses defects at zero iterations, one iteration, and maximum iterations.

Class Activity

You are given the following order processing function:

def process_order(items, coupon, member):
    total = 0
    for item in items:                      # Loop — D1
        total += item["price"]
    if member and total > 1000:            # D2, D3 (two conditions)
        total *= 0.9
    if coupon == "FLAT100":                 # D4
        total -= 100
    if total < 0:                            # D5
        total = 0
    return total

Draw the CFG and label all nodes and edges (including the loop back-edge).
Compute cyclomatic complexity using all three methods and verify they agree.
Identify all basis paths (number = CC value).
Design one concrete test case per basis path (specify the items list, coupon string, and member boolean).
List the Beizer loop test cases for the for loop (what items lists would you use?).

Evaluation rubric (10 marks)

2 marks: Correct CFG with all nodes, edges, and back-edge.
2 marks: CC computed correctly by all three methods.
2 marks: Correct number of linearly independent basis paths identified.
2 marks: Valid concrete test inputs per basis path with expected output.
2 marks: Correct Beizer loop test cases (0, 1, 2, typical, max iterations).

Exit Ticket

A function has 18 edges, 14 nodes, and 1 connected component. What is its cyclomatic complexity? How many basis path tests are needed?
A while loop can execute 0 to 50 times. List the iteration counts you would test using Beizer's strategy.
Name one advantage of basis path testing over exhaustive path coverage, and one limitation compared to MC/DC for compound conditions.

Summary & Assignment

Path coverage is the theoretically strongest structural criterion but is infeasible for loops. Cyclomatic complexity provides a practical bound on independent paths and serves as both a test count guide and a code quality metric. McCabe's basis path testing method produces a minimum test set of CC paths that guarantees 100% branch coverage. Combined with Beizer's loop coverage strategy, basis path testing makes white-box testing tractable for real-world code.

This session completes the white-box testing module. The full coverage hierarchy — from Statement Coverage through Branch, Condition, MC/DC, MCC, and Path Coverage — provides a comprehensive framework for selecting the right testing rigour for any software risk context.

Final Module Assignment: Select two functions from your mini-project. For each function: (1) draw the CFG, (2) compute cyclomatic complexity, (3) derive the basis path test set, (4) implement and run those tests, and (5) record actual vs expected output. Additionally, for any function containing compound boolean conditions, derive and run the MC/DC test set. Submit CFGs, CC computations, basis path tables, test code, and coverage tool output screenshots showing your final branch coverage percentage.

Session 3.8 — Path Testing, Cyclomatic Complexity & White-box Summary

Learning Objectives