White-box testing, basis path testing, and cyclomatic complexity

Testing from the inside

White-box testing (also called glass-box or structural testing) derives its test cases from the internal structure of a component rather than from its specification. The motivation is a fact about where defects live: logic that is only reached under an unusual combination of conditions is exactly the logic that was reasoned about least carefully, and typos cluster in the branches nobody exercises by hand. Exhaustive path testing is out of the question for anything real — a modest routine with a loop has effectively unbounded path count — so white-box testing needs a principled way to choose a small set of paths that still guarantees something. That is what basis path testing supplies.

The flow graph

First, turn the routine into a structure you can count. In a flow graph each node is a sequence of statements with no branching (a whole straight-line block collapses into one node), and each edge is a possible transfer of control. A node that makes a decision is a predicate node and has two edges leaving it. A region is an area of the plane enclosed by edges, and the area outside the graph counts as a region too. One rule matters when you draw one: a compound condition such as if (a && b) must be split into two predicate nodes, because the code really does make two decisions and a single node would undercount them.

Cyclomatic complexity, three ways

Cyclomatic complexity is a quantitative measure of the logical complexity of a program, computed on its flow graph. Three computations give the same number, and being able to do all three is what an exam question rewards:

• V(G) = E − N + 2, where E is the number of edges and N the number of nodes;
• V(G) = (number of predicate nodes) + 1;
• V(G) = (number of enclosed regions), counting the outer region.

What the number buys you is precise: V(G) is an upper bound on the number of linearly independent paths through the component, and therefore the size of the basis set — the set of paths you must execute to guarantee that every statement has run at least once and every branch has been taken in both directions. Compute V(G), derive that many independent paths, write one test case per path, and you have a coverage guarantee rather than a hope. The same number does a second job as a product metric: modules whose V(G) climbs much above ten are consistently harder to test and more defect-prone, so the metric is used to flag candidates for restructuring long before anyone writes the tests.

Control-structure testing

Basis path testing is necessary but not sufficient, so three more families sit alongside it. Condition testing attacks the logical conditions themselves — each simple condition true and false, each compound condition exercised so a wrong Boolean operator shows up. Data-flow testing selects paths by where a variable is defined and where it is used, which finds the classic defined but never used on this path and used before defined faults. Loop testing works the loop construct directly: for a simple loop, skip it, run one pass, run two, run a typical number, and run at its maximum and one beyond; nested loops are tested from the innermost outward, holding the others at typical values, and concatenated loops are treated independently unless one's counter feeds the next.

Worked example — the BorrowBox late-fee routine

computeLateFee decides what a member owes. Its logic is: if the tool was returned by the due time, no fee; if it was returned inside the grace period, no fee; otherwise the fee is the overdue days times the daily rate; and if that exceeds the cap, it becomes the cap. Drawn as a flow graph that is six nodes and eight edges, with three predicate nodes (overdue?, past grace?, over cap?). All three computations agree: E − N + 2 = 8 − 6 + 2 = 4; predicates plus one is 3 + 1 = 4; and the drawing encloses four regions. So the basis set has four paths, and four test cases cover them: return the tool early (no fee); return it inside the grace window (no fee); return it two days late for a fee under the cap; return it thirty days late so the cap binds. Add a fourth predicate — say a check for member credit — and V(G) becomes five, which is the increment rule in miniature: every decision you add costs one more test, forever.