Chapter 27 of 32

White-Box Testing & Cyclomatic Complexity

In Black-Box Testing we designed tests from the specification without looking at the code. That approach has a blind spot: a test suite can pass every specified scenario and still leave whole branches of the program unexecuted. A bug hiding in a branch that no test ever runs will go straight to production.

White-box testing closes that gap. We open the box, look at the code's structure, and ask: "Which statements, branches and paths have my tests actually exercised?" This chapter covers the coverage criteria, the control flow graph, McCabe's cyclomatic complexity (a GATE and university favourite), basis path testing, loop testing, data flow testing and mutation testing, with real tool output.

White-box testing (also called structural, glass-box, clear-box or structure-based testing) designs test cases from the internal structure of the software (its code or detailed design) with the aim of exercising that structure to a chosen level of coverage.


Why Look Inside?

Consider a specification that says: "Customers with more than ₹1 lakh sales get a 10% bonus, more than ₹50,000 get 5%, and anyone with 5 or more years of service gets an extra 2%." A black-box tester might write tests for the obvious cases. But what if the developer added an undocumented branch, a special case for one region, or a shortcut that skips validation? Only by examining the code can we know that every piece has been run at least once.

White-box testing is mostly done by developers at the unit and integration levels (see Levels of Testing). It answers questions black-box testing cannot:

  • Is there code that no test executes (possibly dead code, possibly untested logic)?

  • Has every decision been taken both ways (true and false)?

  • Does every loop work for zero, one and many iterations?

  • Is every variable defined before it is used?

It also has limits: it cannot find missing features. If the specification requires a 15% bonus for ₹5 lakh sales and the developer never wrote that code, 100% coverage of the existing code will not reveal it. That is why the two approaches are complementary.


The Control Flow Graph (CFG)

A control flow graph is a directed graph in which each node represents a statement or a basic block (a sequence of statements with one entry and one exit and no branches in between), and each edge represents a possible transfer of control between them. A node with two or more outgoing edges is a decision (or predicate) node.

Basic shapes

  Sequence      if-then-else       if-then

    (1)             (1)              (1)
     │             ╱   ╲            ╱   │
     ▼            ▼     ▼          ▼    │
    (2)         (2)     (3)      (2)    │
     │            ╲     ╱          ╲    │
     ▼             ▼   ▼            ▼   ▼
    (3)             (4)              (3)


  while loop                         (1) = loop condition
                                     (2) = loop body
     ┌──► (1) ───F───► (3)           (3) = statement after the loop
     │     │T
     │     ▼
     └─── (2)

Worked example 1: the bonus function

Here is the bonus rule in Python, saved as bonus.py. The comments label each CFG node:

def bonus(sales, years):
    rate = 0                      # node 1
    if sales > 100000:            # node 2 (decision)
        rate = 10                 # node 3
    elif sales > 50000:           # node 4 (decision)
        rate = 5                  # node 5
    if years >= 5:                # node 6 (decision)
        rate += 2                 # node 7
    return sales * rate // 100    # node 8
               (1)
                │
               (2)  sales > 100000 ?
              T╱ ╲F
             (3)  (4)  sales > 50000 ?
              │  T╱ ╲F
              │ (5)  │
               ╲ │  ╱
                (6)  years >= 5 ?
               T╱ ╲F
              (7)  │
                ╲  │
                 (8)

Edges: 1→2, 2→3, 2→4, 3→6, 4→5, 4→6, 5→6, 6→7, 6→8, 7→8
N = 8 nodes, E = 10 edges, decision nodes: 2, 4, 6

Coverage Criteria

A coverage criterion states which structural elements the tests must exercise. Coverage is measured as a percentage:

Coverage = (number of elements exercised by the tests ÷ total number of elements) × 100%

1. Statement coverage

Every statement is executed at least once. For the bonus function, we need nodes 3 and 5 both executed, which requires two different sales values. Two tests suffice: (200000, 6) runs 1-2-3-6-7-8 and (60000, 1) runs 1-2-4-5-6-8. All 8 nodes are covered.

But notice: no test takes the false side of sales > 50000 going straight to node 6. Statement coverage is the weakest criterion.

2. Branch (decision) coverage

Every decision takes both its true and its false outcome at least once, i.e. every edge leaving a decision node is traversed. Here there are 3 decisions × 2 outcomes = 6 branches. The minimum is three tests, for example (200000, 6), (60000, 1) and (30000, 3): the second and third tests are both needed because node 4 must go true once and false once, and both of those require sales ≤ 100000, while the first test covers the true side of node 2.

Branch coverage implies statement coverage (in a graph where every node is reachable), but not the other way round.

3. Condition coverage

When a decision is a compound expression such as if a > 0 and b > 0, each atomic condition (a > 0, b > 0) must take both true and false values. Surprisingly, this does not imply branch coverage:

Testa > 0b > 0Decision (and)
T1: a = 5, b = −1TFF
T2: a = −1, b = 5FTF

Each condition was both true and false, yet the decision was never true, so the "then" branch never ran.

4. Condition/decision coverage

Both conditions and decisions must take every outcome. Adding T3: a = 5, b = 5 (decision true) achieves it.

5. Modified condition/decision coverage (MC/DC)

Every condition must be shown to independently affect the decision outcome: there must be a pair of tests where only that condition changes and the decision changes with it. For a > 0 and b > 0:

Testa > 0b > 0DecisionShows independence of
T3TTT(pairs with both below)
T2FTFa > 0 (T3 vs T2)
T1TFFb > 0 (T3 vs T1)

MC/DC typically needs about N + 1 tests for N conditions, instead of 2N. It is required for the most critical airborne software under the aviation standard DO-178C (Level A), and is highly recommended for the highest integrity level (ASIL D) of the automotive standard ISO 26262.

6. Multiple condition coverage

All 2N combinations of condition values in each decision are tested (here 4: TT, TF, FT, FF). Thorough, but grows exponentially.

7. Path coverage

Every complete path from entry to exit is executed. For the bonus function, the first if/elif has 3 outcomes and the second if has 2, so there are 3 × 2 = 6 paths. A program with a loop can have an unbounded number of paths, so full path coverage is usually impossible; that is why we use basis paths (below).

The subsumption hierarchy

            Path coverage              Multiple condition coverage
                  │                                │
                  │                              MC/DC
                  │                                │
                  │                  Condition/decision coverage
                  │                       ╱                ╲
                  └──────►  Branch (decision) coverage     Condition coverage
                                          │                 (does NOT imply
                                 Statement coverage          branch coverage)

"A → B" read downwards: achieving the upper criterion guarantees the lower one.

A short-circuit note: languages like C, Java and Python evaluate a and b lazily, so when a is false, b is never evaluated. Coverage tools work with what actually ran, which is why compound conditions are often analysed condition by condition.


Measuring Coverage with a Real Tool

Let us measure the bonus function with coverage.py, the standard Python coverage tool. First, a suite with just one test:

# test_bonus.py
import unittest
from bonus import bonus

class TestBonus(unittest.TestCase):
    def test_big_sales_senior(self):
        self.assertEqual(bonus(200000, 6), 24000)

if __name__ == "__main__":
    unittest.main()
$ coverage run --branch test_bonus.py
$ coverage report -m --include=bonus.py

(--include limits the report to the code under test; without it the test file itself is listed too.)

Output (coverage.py 7.17):

Name       Stmts   Miss Branch BrPart  Cover   Missing
------------------------------------------------------
bonus.py       9      2      6      2    60%   5-6, 7->9
------------------------------------------------------
TOTAL          9      2      6      2    60%

Reading the report (the numbers are file line numbers, where line 1 is the def line):

  • Stmts 9, Miss 2: lines 5–6 (the elif and rate = 5) never ran.

  • Branch 6, BrPart 2: 6 possible branch outcomes; 2 decisions were only partially taken. 7->9 means the jump from line 7 (if years >= 5) straight to line 9 (the return), i.e. the false outcome, never happened.

  • Cover 60%: coverage.py combines both: (7 statements + 2 branches executed) ÷ (9 + 6) = 9 ÷ 15 = 60%.

Now we add tests chosen from the CFG (one per basis path; see the next section):

class TestBonus(unittest.TestCase):
    def test_big_sales_senior(self):      # path 1-2-3-6-7-8
        self.assertEqual(bonus(200000, 6), 24000)
    def test_big_sales_junior(self):      # path 1-2-3-6-8
        self.assertEqual(bonus(200000, 2), 20000)
    def test_medium_sales(self):          # path 1-2-4-5-6-8
        self.assertEqual(bonus(60000, 1), 3000)
    def test_low_sales(self):             # path 1-2-4-6-8
        self.assertEqual(bonus(30000, 3), 0)

Output (same commands as before):

Name       Stmts   Miss Branch BrPart  Cover   Missing
------------------------------------------------------
bonus.py       9      0      6      0   100%
------------------------------------------------------
TOTAL          9      0      6      0   100%

100% statement and branch coverage. Keep that result in mind: we will see in the mutation testing section that 100% coverage still does not mean the tests are strong.


Cyclomatic Complexity

In 1976 Thomas McCabe proposed a single number that measures the decision structure of a program. It has two uses: it indicates how complex (and error-prone) a module is, and it gives the number of test cases needed for basis path testing.

The cyclomatic complexity V(G) of a control flow graph G is the number of linearly independent paths through it. It can be computed in three equivalent ways:

1. V(G) = E − N + 2P, where E = edges, N = nodes, P = number of connected components (P = 1 for a single program or function).

2. V(G) = π + 1, where π = number of binary decision (predicate) nodes.

3. V(G) = number of regions of the planar flow graph, counting the outside region as one.

Applying all three to the bonus function

  1. E − N + 2P = 10 − 8 + 2 × 1 = 4.

  2. Predicate nodes are 2, 4 and 6: π + 1 = 3 + 1 = 4.

  3. Regions: the graph encloses three bounded areas (between 2-3-6 and 2-4-6, between 4-5-6 and 4-6, between 6-7-8 and 6-8) plus the outer region = 4.

All three agree, as they must. This is a good self-check in exams.

Worked example 2: a loop

def count_even(nums):
    count = 0; i = 0                 # node 1
    while i < len(nums):             # node 2 (decision)
        if nums[i] % 2 == 0:         # node 3 (decision)
            count += 1               # node 4
        i += 1                       # node 5
    return count                     # node 6
        (1)
         │
         ▼
        (2) ◄────────────┐      while i < len(nums) ?
       T│  ╲F            │
        ▼   ╲            │
        (3)  ╲           │      nums[i] even ?
       T│ ╲F  ╲          │
        ▼  │   ▼         │
       (4) │   (6)       │      (6) = return count
        │  │             │
        ▼  ▼             │
         (5) ────────────┘      i += 1, back to the condition

Edges: 1→2, 2→3, 2→6, 3→4, 3→5, 4→5, 5→2      E = 7, N = 6
V(G) = 7 − 6 + 2 = 3        π + 1 = 2 + 1 = 3

Three independent paths: 1-2-6 (empty list), 1-2-3-5-2-6 (one odd number), 1-2-3-4-5-2-6 (one even number). Note that the loop back edge 5→2 makes the number of complete paths unbounded, but the number of basis paths is still just 3.

Compound conditions and switch statements

  • A compound condition such as if a > 0 and b > 0 really contains two decisions (because of short-circuit evaluation). When the CFG is drawn with one node per simple condition, each and/or adds 1 to V(G). Most tools (for example radon for Python, or the complexity checks in many linters) count it this way. If a question draws the compound condition as a single node, follow the graph as given.

  • A switch with k outcomes (including default) is a k-way decision and contributes k − 1 to V(G), since it is equivalent to k − 1 binary decisions.

Several components

If a program consists of P separate functions, each drawn as its own graph, the formula uses the total edges and nodes: V = E − N + 2P. Equivalently, V(total) = sum of the individual V values. Example: three functions with V = 4, 3 and 2 give V = 9 in total.

What the number means

V(G)Typical interpretation
1–10Simple, well-structured, low risk. McCabe suggested 10 as an upper limit per module.
11–20Moderately complex; harder to test thoroughly.
21–50Complex, high risk; consider refactoring.
> 50Practically untestable; very high risk.

The bands above are a widely used rule of thumb, not a formal standard. A high V(G) is a reason to look closer, split the function, or test more, connecting to the low-coupling, high-cohesion advice in Modularity, Coupling & Cohesion.


Basis Path Testing

Basis path testing (McCabe, popularised by Pressman) turns cyclomatic complexity into a test design method.

  1. Draw the CFG from the code or design.

  2. Compute V(G). This is the number of test cases needed for the basis set, and an upper bound on the number of tests needed for branch coverage.

  3. Find a basis set of V(G) linearly independent paths. Each new path must include at least one edge not used by the previous paths.

  4. Prepare a test case (inputs and expected output) that forces each path.

For the bonus function (V = 4):

PathNew edge(s) introducedInput (sales, years)Expected bonus
P1: 1-2-3-6-7-8(baseline)(200000, 6)200000 × 12% = 24000
P2: 1-2-3-6-86→8(200000, 2)20000
P3: 1-2-4-5-6-82→4, 4→5, 5→6(60000, 1)3000
P4: 1-2-4-6-84→6(30000, 3)0

Compare the counts for this one small function: statement coverage needs 2 tests, branch coverage 3, basis paths 4 and all paths 6. In general: statement ≤ branch ≤ V(G) ≤ total paths.

Some paths in a basis set can be infeasible: no input can make the program follow them (for example, when two decisions test the same variable in contradictory ways). Such a path is replaced by another independent path.


Loop Testing

Loops are a rich source of off-by-one errors. Beizer's classic guidelines for a simple loop allowed at most n iterations:

  • Skip the loop entirely (0 iterations).

  • Exactly 1 pass, and exactly 2 passes.

  • m passes, where m is a typical value (m < n).

  • n − 1, n and n + 1 passes (the last one should be impossible or rejected).

This is boundary value analysis applied to the iteration count. For nested loops, start with the innermost loop (outer loops at their minimum), test it fully, then work outwards. Concatenated loops are tested as simple loops if they are independent, otherwise as nested. Unstructured loops (jumps into the middle) should be redesigned.


Data Flow Testing

Control-flow criteria look at which statements and branches run. Data flow testing looks at what happens to variables along those paths.

  • A definition (def) of a variable is a statement that assigns it a value: rate = 0.

  • A use reads its value: a c-use (computation use) as in sales * rate, or a p-use (predicate use) as in if years >= 5.

  • A def-use (du) pair is a definition and a use that it can reach along some path with no redefinition in between (a def-clear path).

In the bonus function, rate is defined at nodes 1, 3, 5 and 7 and used at node 7 (rate += 2 reads and redefines it) and node 8. The du pair (1, 8) is exercised by path P4, where rate stays 0. Common criteria are all-defs (each definition reaches at least one use), all-uses (each definition reaches every use it can reach) and all-du-paths. Data flow analysis also catches anomalies such as a variable used before being defined, or defined twice with no use in between.


Mutation Testing: Testing the Tests

Our four tests achieved 100% statement and branch coverage. Are they good tests? Mutation testing answers this by deliberately inserting small faults (mutants) into the code and checking whether the tests notice.

A mutant is killed if at least one test fails on it, and survives otherwise. Mutation score = killed mutants ÷ (total mutants − equivalent mutants) × 100%. An equivalent mutant behaves exactly like the original for every input, so no test can ever kill it.

A small hand-made mutation runner for our bonus function:

# mutate.py: run the test suite against four mutants of bonus.py
import io, unittest, test_bonus

SOURCE = open("bonus.py").read()
MUTANTS = {
    "M1: sales > 100000  ->  sales >= 100000": ("sales > 100000", "sales >= 100000"),
    "M2: rate = 5  ->  rate = 6":             ("rate = 5", "rate = 6"),
    "M3: years >= 5  ->  years > 5":          ("years >= 5", "years > 5"),
    "M4: rate += 2  ->  rate -= 2":           ("rate += 2", "rate -= 2"),
}

killed = 0
for name, (old, new) in MUTANTS.items():
    namespace = {}
    exec(SOURCE.replace(old, new, 1), namespace)
    test_bonus.bonus = namespace["bonus"]          # plug the mutant in
    suite = unittest.defaultTestLoader.loadTestsFromModule(test_bonus)
    result = unittest.TextTestRunner(stream=io.StringIO()).run(suite)
    status = "killed" if result.failures or result.errors else "SURVIVED"
    killed += status == "killed"
    print(f"{name:42} {status}")
print(f"Mutation score = {killed}/{len(MUTANTS)} = {killed / len(MUTANTS):.0%}")

Output with our four basis-path tests:

M1: sales > 100000  ->  sales >= 100000    SURVIVED
M2: rate = 5  ->  rate = 6                 killed
M3: years >= 5  ->  years > 5              SURVIVED
M4: rate += 2  ->  rate -= 2               killed
Mutation score = 2/4 = 50%

100% coverage, but only 50% mutation score: no test uses sales exactly 100000 or years exactly 5, so the boundary mutants survive. We add two boundary tests (here white-box and black-box thinking meet):

    def test_boundary_sales(self):        # exactly 100000 is NOT "> 100000"
        self.assertEqual(bonus(100000, 0), 5000)
    def test_boundary_years(self):        # exactly 5 years gets the extra 2%
        self.assertEqual(bonus(60000, 5), 4200)
M1: sales > 100000  ->  sales >= 100000    killed
M2: rate = 5  ->  rate = 6                 killed
M3: years >= 5  ->  years > 5              killed
M4: rate += 2  ->  rate -= 2               killed
Mutation score = 4/4 = 100%

Real projects use tools that generate hundreds of mutants automatically (for example PIT for Java, Stryker for JavaScript/C#, mutmut for Python). Mutation testing is expensive, but it is the most honest measure of how good a test suite is.


Black-Box vs White-Box at a Glance

AspectBlack-boxWhite-box
Test basisSpecificationCode / detailed design
Who usually does itTesters, usersDevelopers
MeasuresRequirements coverageStatement, branch, path coverage
Finds missing features?YesNo
Finds unexecuted / dead code?NoYes
Affected by code changes?Only if behaviour changesTests may need redesign when structure changes

Common Mistakes

  • Using E − N + 2 when the graph has several components. The general formula is E − N + 2P.

  • Counting nodes with multiple outgoing edges as one predicate each. π + 1 holds for binary decisions; a k-way switch counts as k − 1.

  • Forgetting the outer region when counting regions.

  • Believing condition coverage implies branch coverage. The (T, F), (F, T) example shows it does not.

  • Treating 100% coverage as "fully tested". Coverage shows what was executed, not whether the results were checked or whether boundaries were probed; mutation testing exposed this.

  • Confusing V(G) with the total number of paths. V(G) is the size of a basis set; the total number of paths can be much larger or even infinite with loops.


Interview and Exam Questions

Q1. A control flow graph has 17 edges and 13 nodes. What is its cyclomatic complexity?

V(G) = E − N + 2 = 17 − 13 + 2 = 6 (one connected component).

Q2. A function has 4 if statements (no else-if), one while loop and one for loop, all with simple conditions. What is V(G)?

Each is one binary decision: π = 6, so V(G) = π + 1 = 7.

Q3. A function contains if (x > 0 && y > 0 || z == 1) and nothing else. What is its cyclomatic complexity when counting atomic conditions?

Three atomic conditions, each a binary decision under short-circuit evaluation: V(G) = 3 + 1 = 4. If the whole expression is drawn as a single decision node, V(G) = 2.

Q4. Give tests that achieve 100% condition coverage but not 100% decision coverage for if (a || b).

(a = T, b = F) and (a = F, b = T). Each condition is both true and false, but the decision is true in both tests, so the false branch is never taken.

Q5. What is the relationship between V(G) and the number of test cases for branch coverage?

V(G) is an upper bound on the number of tests needed for branch coverage and is the exact number of tests in a basis path set. Branch coverage often needs fewer (3 vs 4 in the bonus example).

Q6. A program has three modules with cyclomatic complexities 5, 3 and 7. What is the complexity of the whole program?

For separate components, V = E − N + 2P, which equals the sum of the individual complexities: 5 + 3 + 7 = 15.

Q7. What is an equivalent mutant and why is it a problem?

A mutant that behaves identically to the original program for every input, e.g. changing i < n to i != n in a loop where i increases by exactly 1 from 0 and n ≥ 0. No test can kill it, so it must be excluded from the mutation score, and finding equivalent mutants generally needs human judgement.


Summary

  • White-box testing designs tests from the code's structure and measures coverage. It finds unexecuted code and logic errors but not missing features.

  • Coverage criteria from weak to strong: statement → branch → condition/decision → MC/DC → multiple condition; path coverage is the strongest control-flow criterion. Condition coverage alone does not imply branch coverage.

  • Cyclomatic complexity V(G) = E − N + 2P = π + 1 = number of regions. The bonus example gave 4 by all three methods. McCabe's suggested limit is 10 per module.

  • Basis path testing: V(G) independent paths, one test each. Counts for one function: statement 2 ≤ branch 3 ≤ basis 4 ≤ all paths 6.

  • Loop testing applies BVA to the number of iterations; data flow testing follows def-use pairs of variables.

  • Mutation testing checks test quality: 100% coverage gave only a 50% mutation score until boundary tests were added.

  • Next, Levels of Testing shows where these techniques are applied: unit, integration, system and acceptance testing.