Why Complexity Matters to Testing: Basis Path Testing

The baseline method

A basis can be found by trial and error, but NIST 500-235 gives a method. "The first step is to pick a functional 'baseline' path through the program that represents a legitimate function and not just an error exit", in the tester's judgement "the most important path to test". Then, one decision at a time, flip a decision's outcome on a path already chosen and follow the program on to its exit, until every decision outcome has been taken. Each new path adds exactly one edge the earlier paths had not taken, which is why the paths come out independent, and why there are exactly V(G) of them.

Worked example: two defects that cancel

Here is a version of ExamReg's fee rule for forms up to 7 days late: the form fee of Rs 800, waived by a concession, plus a Rs 100 late fee for any form after the last date. The version under test has two defects: its concession removes Rs 700 instead of Rs 800, and its late fee adds nothing instead of Rs 100. When a student has a concession and is late, the two mistakes cancel: 800 - 700 + 0 = 100, which happens to be right.

The function has two decisions, so V(G) = 3, and four paths through it, named by the outcomes of its two decisions: TT, TF, FT and FF. The program writes each path as a vector over the graph's seven edges, measures independence by the rank of those vectors, and compares a branch coverage test set with a basis.

from fractions import Fraction
from itertools import combinations

def total_fee(days_late, concession):                 # the version under test (days_late 0 to 7)
    fee = 800
    if concession:                                    # decision d1
        fee = fee - 700
    if days_late > 0:                                 # decision d2
        fee = fee + 0
    return fee

def specified(days_late, concession):                 # the fee rule for 0 to 7 days late
    return (0 if concession else 800) + (100 if days_late > 0 else 0)

# the control flow graph's edges, and the edges each path through it takes
EDGES = ["entry-d1", "d1 true", "after d1", "d1 false", "d2 true", "after d2", "d2 false"]
PATHS = {"TT": ["entry-d1", "d1 true", "after d1", "d2 true", "after d2"],
         "TF": ["entry-d1", "d1 true", "after d1", "d2 false"],
         "FT": ["entry-d1", "d1 false", "d2 true", "after d2"],
         "FF": ["entry-d1", "d1 false", "d2 false"]}
INPUT = {"TT": (3, True), "TF": (0, True), "FT": (3, False), "FF": (0, False)}

def vector(path):
    return [Fraction(int(e in PATHS[path])) for e in EDGES]

def rank(rows):
    """Gaussian elimination: the number of linearly independent rows."""
    rows, r = [row[:] for row in rows], 0
    for col in range(len(EDGES)):
        pivot = next((i for i in range(r, len(rows)) if rows[i][col] != 0), None)
        if pivot is None:
            continue
        rows[r], rows[pivot] = rows[pivot], rows[r]
        for i in range(len(rows)):
            if i != r and rows[i][col] != 0:
                factor = rows[i][col] / rows[r][col]
                rows[i] = [a - factor * b for a, b in zip(rows[i], rows[r])]
        r += 1
    return r

def run(name, paths):
    print(f"{name}: paths {' '.join(paths)}, rank {rank([vector(p) for p in paths])}")
    for p in paths:
        args = INPUT[p]
        got, want = total_fee(*args), specified(*args)
        print(f"   {p} {str(args):<11} expected {want:>3}, got {got:>3}  {'pass' if got == want else 'FAIL'}")

print(f"V(G) = {len(EDGES)} edges - 6 nodes + 2 = {len(EDGES) - 6 + 2}")
run("branch coverage, two tests", ["TT", "FF"])
run("basis from the baseline FT", ["FT", "TT", "FF"])
combo = [a + b - c for a, b, c in zip(vector("TT"), vector("FF"), vector("FT"))]
print("TT + FF - FT equals TF:", combo == vector("TF"))

bases = [c for c in combinations(PATHS, 3) if rank([vector(p) for p in c]) == 3]
finding = [c for c in bases if any(total_fee(*INPUT[p]) != specified(*INPUT[p]) for p in c)]
print(f"every basis of 3 paths: {len(bases)}; bases that find the defect: {len(finding)}")

V(G) = 7 edges - 6 nodes + 2 = 3
branch coverage, two tests: paths TT FF, rank 2
   TT (3, True)   expected 100, got 100  pass
   FF (0, False)  expected 800, got 800  pass
basis from the baseline FT: paths FT TT FF, rank 3
   FT (3, False)  expected 900, got 800  FAIL
   TT (3, True)   expected 100, got 100  pass
   FF (0, False)  expected 800, got 800  pass
TT + FF - FT equals TF: True
every basis of 3 paths: 4; bases that find the defect: 4

Branch coverage passes. Two tests, a late student with a concession (TT) and an on-time student without one (FF), make each decision go both ways: 4 of 4 branch outcomes, 100 per cent branch coverage. Both pass, because in TT the two defects cancel and in FF neither is reached. The rank line says why this is not enough: the two paths have rank 2, one short of V(G).

The basis fails. The tester takes as the baseline an ordinary late form: FT, 3 days late, no concession. Flipping the first decision gives TT; flipping the second gives FF. Three paths, rank 3: a basis. And the baseline itself fails: the student should pay 800 + 100 = 900 rupees and is charged 800, because the late fee adds nothing.

Why the basis could not miss it. The line TT + FF - FT equals TF shows the fourth path is a combination of the three tested ones, which is what makes them a basis. The last line checks every possible set of three paths: all 4 are bases, and all 4 find the defect. The reason is the one NIST 500-235 gives for its own example: testing the two decisions independently requires at least one path on which they go different ways, TF or FT, and on those paths the two defects no longer cancel. In NIST 500-235's words, structured testing "does not allow interactions between decision outcomes during testing to hide errors". Branch coverage does allow it: its two tests varied both decisions together.

The steps, for a module of any size

1. Draw the control flow graph and compute V(G), by any of the three methods of Chapter Seventy, on cyclomatic complexity.
2. Choose a baseline path: a typical, important function of the module, not an error exit.
3. Flip one decision at a time: for each decision on a chosen path whose other outcome has not yet been taken, take that outcome and follow the program to the exit, keeping the other decisions as typical as possible.
4. Stop at V(G) paths, when every outcome of every decision has been taken.
5. Find inputs that drive each path, write expected results from the specification, and run.

Some paths cannot be driven by any input, for instance when a module makes the same decision twice; NIST 500-235 treats that case separately, by changing the code to remove the dependency or by settling for the largest number of independent paths that can be exercised.

Where the effort goes

Complexity turns into a test budget. Chapter Seventy's measurements of ExamReg put late_band at 3, check_form at 5 and hall_ticket_status at 15: a basis for the last needs fifteen tests, five times as many as the first. That is not a penalty on the complex module; it is the honest cost of its logic, and a reason, before testing starts, to split it, since three modules of complexity 5 are easier to test well than one of 15.

What it does not mean

A basis is not all paths. It is V(G) paths from which every other path can be built; with loops, all paths are infinitely many.

Basis path testing does not choose expected results. The 900 rupees that exposed the defect came from the fee rule.

It is not the same as weak structured testing. Running V(G) different paths that happen to cover all branches is not enough; NIST 500-235 calls that weak structured testing, and it does not guarantee independence.

Any basis is not equally good. Every basis catches defects like the one above; the baseline method adds the tester's judgement by starting from the most important path.

Quick revision

• Structured (basis path) testing (NIST 500-235): "Test a basis set of paths through the control flow graph of each module".
• A basis has V(G) linearly independent paths; every other path is a linear combination of them.
• Baseline method: start from the most important functional path; flip exactly one decision outcome at a time until every outcome has been taken.
• Significance in testing: V(G) is the minimum number of tests; test effort should follow complexity; decisions are tested independently, so interactions cannot hide defects.
• Worked example: two cancelling defects; branch coverage (TT, FF, rank 2) passed; the basis (FT, TT, FF, rank 3) failed at FT, 800 charged for 900; all 4 possible bases find the defect.
• Structured testing subsumes branch and statement coverage.

Test yourself

1. State the structured testing criterion. What is a basis set of paths? Test a basis set of paths through each module's control flow graph. A basis set is a set of linearly independent paths from which every path through the graph can be formed as a linear combination; it always has V(G) paths.

2. Describe the baseline method for generating basis paths. Choose a baseline path that represents a typical, important function of the module. Then repeatedly take a path already chosen, flip the outcome of one decision whose other outcome has not yet been exercised, and follow the program to its exit. Each new path adds one new decision outcome, and after V(G) paths every outcome has been taken and the paths form a basis.

3. Why does a module with V(G) = 5 need at least five tests under basis path testing, when branch coverage might need two? Because five linearly independent paths are needed to form a basis, and each test follows one path. Branch coverage only requires each decision outcome to be taken once, which a few long paths can do together without the decisions ever being varied independently.

4. In the worked example, why did branch coverage miss the defects while every basis found them? Branch coverage used two tests in which both decisions went the same way, and on those paths the two defects cancelled out or were not reached. Any basis of three paths must include a path on which the decisions go different ways, and on such a path the defects do not cancel, so the wrong fee appears.

5. Derive the basis paths for check_form, whose complexity is 5. Baseline: a valid form with one correctly coded paper, on time (papers present, loop entered once, code valid, loop exits, not late). Flip the empty-form decision: no papers (the loop is then not entered). Flip the code-length decision: one badly coded paper. Flip the loop decision: two papers, so the loop repeats. Flip the lateness decision: the baseline form more than 15 days late. Five paths, with expected results from the specification.

6. What is the significance of cyclomatic complexity in testing? It gives the minimum number of tests for basis path testing; it points testing effort at the most complex, most error-prone modules; and testing a basis set guarantees each decision is tested independently, so defects that depend on how decisions combine cannot hide as they can under branch coverage.