Branch Testing and Branch Coverage

Why branch coverage is stronger: the empty side of an if

The syllabus states the relation: "When 100% branch coverage is achieved, all branches in the code, unconditional and conditional, are exercised by test cases", and "Branch coverage subsumes statement coverage." The reason is simple. Every statement lies on some branch, so taking every branch runs every statement. The converse fails because a branch can contain no statement at all. An if without an else has a False branch that goes straight to the next statement; statement coverage never needs it, and branch coverage always does.

Chapter Fifty-Nine ended on exactly that branch. Its one test of late_fee executed all 5 statements and took only 2 of the 4 branches, and the two it never took were both False.

The tracer and the functions, as the earlier chapters wrote them:

"""A small coverage tracer: which statements and which branches of one function ran.

It watches one function with sys.settrace, which calls back on every new line executed.
A decision is an if, elif, while or for; its True branch is taken when the next line
executed is inside its body, its False branch when it is anywhere else (or the function
returns). Limits: one statement per line, and no recursion; that is all it was built for.
"""
import ast
import inspect
import sys

def structure(func):
    """Statements {line: text} and decisions {line: (first, last line of the body)}."""
    first = func.__code__.co_firstlineno
    source = inspect.getsource(func).splitlines()
    tree = ast.parse("\n".join(source)).body[0]
    statements, decisions = {}, {}
    for node in ast.walk(tree):
        docstring = isinstance(node, ast.Expr) and isinstance(node.value, ast.Constant)
        if isinstance(node, ast.stmt) and node is not tree and not docstring:
            statements[node.lineno + first - 1] = source[node.lineno - 1].strip()
        if isinstance(node, (ast.If, ast.While, ast.For)):
            decisions[node.lineno + first - 1] = (node.body[0].lineno + first - 1,
                                                  node.body[-1].end_lineno + first - 1)
    return statements, decisions

def trace(func, args):
    """Call func(*args); return the line numbers it executed, in order."""
    lines = []
    def on_line(frame, event, arg):
        if event == "line":
            lines.append(frame.f_lineno)
        return on_line
    sys.settrace(lambda frame, event, arg: on_line if frame.f_code is func.__code__ else None)
    try:
        func(*args)
    except Exception:
        pass                                   # a test's verdict is not the tracer's business
    finally:
        sys.settrace(None)
    return lines

def measure(func, tests):
    """Statement and branch coverage of func over tests (a list of argument tuples)."""
    statements, decisions = structure(func)
    ran, taken = set(), set()
    for args in tests:
        lines = trace(func, args)
        ran.update(lines)
        for i, line in enumerate(lines):
            if line in decisions:
                low, high = decisions[line]
                after = lines[i + 1] if i + 1 < len(lines) else None
                taken.add((line, after is not None and low <= after <= high))
    branches = {(d, outcome) for d in decisions for outcome in (True, False)}
    return {"statements": (len(ran & statements.keys()), len(statements)),
            "branches": (len(taken), len(branches)),
            "statements missed": [statements[n] for n in sorted(statements.keys() - ran)],
            "branches missed": [f"{statements[d]} -> {outcome}"
                                for d, outcome in sorted(branches - taken)]}

def late_fee(days_late):
    """The late fee, in rupees, for a form days_late days after the last date (0 to 15)."""
    if days_late > 0:
        fee = 100
    if days_late > 7:
        fee = 500
    return fee

def result_summary(passed, appeared):
    """A paper's pass percentage, and whether it goes to the exam cell for review."""
    percent = passed / appeared * 100
    review = False
    if percent < 40:
        review = True
    return round(percent, 1), review

Worked example 1: from 2 of 4 branches to 4 of 4

Branch testing reads the missing outcomes and designs a test for them. Both False outcomes happen together when the student is not late at all, so the second test is a form on the last date, expected Rs 0. A third test, 3 days late, is the kind a tester adds for the Rs 100 band; the program shows what it adds to coverage.

from coverage_tracer import measure
from examreg_checks import late_fee

def run(days):
    try:
        return late_fee(days)
    except Exception as problem:
        return f"crash: {type(problem).__name__}"

tests = []
for days, expected in [(10, 500), (0, 0), (3, 100)]:
    tests.append((days,))
    c = measure(late_fee, tests)
    got = run(days)
    print(f"add late_fee({days}): expected {expected}, got {got}"
          f" {'pass' if got == expected else 'FAIL'}; now statements"
          f" {c['statements'][0]} of {c['statements'][1]}, branches {c['branches'][0]} of {c['branches'][1]}")

add late_fee(10): expected 500, got 500 pass; now statements 5 of 5, branches 2 of 4
add late_fee(0): expected 0, got crash: UnboundLocalError FAIL; now statements 5 of 5, branches 4 of 4
add late_fee(3): expected 100, got 100 pass; now statements 5 of 5, branches 4 of 4

The test that branch coverage asked for is the test that fails. At 0 days neither assignment runs, and the function crashes instead of returning Rs 0. Two tests reach 100 per cent branch coverage (the combination not late but more than 7 days is impossible, so two tests take all four outcomes), and the third adds nothing to the count, though it is still a good test of the Rs 100 band. The fix the failure points to is an else, or an initial fee = 0, on the path that had no statement.

What branch coverage misses

The ISTQB syllabus names the first limit: "exercising a branch with a test case will not detect defects in all cases. For example, it may not detect defects requiring the execution of a specific path in a code." Taking every branch at least once is not taking every combination of branches, and a defect that shows only when a particular True here follows a particular False there can survive 100 per cent.

The second limit is inside the decisions. A decision may combine several conditions, each a "Boolean expression containing no Boolean operators" (ISO/IEC/IEEE 29119-4), with and and or. Branch coverage asks only that the whole decision be true once and false once. It does not ask why it was false.

Worked example 2: a defect inside a condition

Here is ExamReg's fee rule for one student, without the backlog papers: the form fee of Rs 800, waived by a concession, plus the late fee, which applies to everyone. The code has the defect Chapter Fifty-Six's decision table caught, written this time as part of a condition.

def total_fee(days_late, concession):
    """Form fee Rs 800, waived with a concession, plus the late fee (days_late 0 to 15)."""
    fee = 800
    if concession:
        fee = 0
    if days_late >= 8:
        fee = fee + 500
    elif days_late >= 1 and not concession:
        fee = fee + 100
    return fee

The elif is one decision with two conditions: c1, days_late >= 1, and c2, not concession. The program measures the branch coverage of a test set designed to take all six branch outcomes, and prints, for every test that reaches the elif, the value of each condition.

from coverage_tracer import measure
from fee_rule import total_fee

def specified(days_late, concession):                    # the fee rule: the late fee applies to all
    late = 0 if days_late == 0 else 100 if days_late <= 7 else 500
    return (0 if concession else 800) + late

def show(name, tests):
    b = measure(total_fee, tests)["branches"]
    print(f"{name}: branches {b[0]} of {b[1]}")
    for days, concession in tests:
        c1, c2 = days >= 1, not concession               # the elif's two conditions
        reaches = days < 8                               # the elif is only evaluated below 8 days
        conds = f"c1={'T' if c1 else 'F'} c2={'T' if c2 else 'F'}" if reaches else "elif not reached"
        got, want = total_fee(days, concession), specified(days, concession)
        print(f"   ({days:>2}, {str(concession):<5}) {conds:<16} expected {want:>4},"
              f" got {got:>4} {'pass' if got == want else 'FAIL'}")

show("branch coverage", [(10, True), (4, False), (0, False)])
show("adding the test c2=F asks for", [(10, True), (4, False), (0, False), (4, True)])

branch coverage: branches 6 of 6
   (10, True ) elif not reached expected  500, got  500 pass
   ( 4, False) c1=T c2=T        expected  900, got  900 pass
   ( 0, False) c1=F c2=T        expected  800, got  800 pass
adding the test c2=F asks for: branches 6 of 6
   (10, True ) elif not reached expected  500, got  500 pass
   ( 4, False) c1=T c2=T        expected  900, got  900 pass
   ( 0, False) c1=F c2=T        expected  800, got  800 pass
   ( 4, True ) c1=T c2=F        expected  100, got    0 FAIL

The first three tests take all 6 branch outcomes, 100 per cent branch coverage, and every one passes. Look at the condition columns: the elif was true once (c1 and c2 both true) and false once, but it was false because c1 was false, the student was on time. c2 was never false: no test reached the elif with a concession. So the part of the decision that is wrong, and not concession, never had a chance to make a difference.

The fourth test is the one the conditions ask for: a student with a concession, 4 days late, so that c2 is false while c1 is true. The fee rule says Rs 100, the late fee alone. The code says Rs 0, because its condition quietly excuses a concession student from the late fee as well.

Beyond branch coverage, in outline

ISO/IEC/IEEE 29119-4 defines three criteria that look inside decisions. For the elif above:

Branch condition combination testing doubles its tests with each condition added to a decision; MC/DC asks only for pairs that show each condition's effect, which here took three tests instead of four. The ISTQB syllabus leaves such criteria out of the Foundation level, noting that "There are more rigorous white-box test techniques that are used in some safety-critical, mission-critical, or high-integrity environments to achieve more thorough code coverage". For MU's examination, knowing what each asks, and why branch coverage stops short, is enough.

Branch coverage in numbers

• Compute the coverage. Branch coverage = branch outcomes taken ÷ total branch outcomes × 100. Two decisions give four outcomes; tests taking three of them give 75 per cent.
• Find the fewest tests for 100 per cent. Each decision needs a test that makes it true and one that makes it false; tests can share decisions. late_fee needs two, since one input can make both decisions false and another both true.
• Compare with statement coverage. A test set at 100 per cent branch coverage is always at 100 per cent statement coverage; the reverse fails whenever an if has no else.

What it does not mean

100 per cent branch coverage does not mean every path was taken. It means each outcome of each decision was taken at least once, not every combination of outcomes.

It does not mean every condition was tested. A decision can go both ways while one of its conditions never changes, as c2 did.

Branch coverage and decision coverage are not different ideas. They count the same outcomes (decision coverage) or all edges including straight-line ones (branch coverage in ISTQB's sense), and they agree at 100 per cent.

Branch testing does not choose expected results. The Rs 0 for a form on time came from the fee rule, and so did the Rs 100 that exposed the concession defect.

Quick revision

• Branch (ISO/IEC/IEEE 24765): alternative sets of statements selected for execution; branch testing: "each outcome of each decision point".
• ISTQB: a branch is a transfer of control between two nodes of the control flow graph, unconditional or conditional; coverage = branches exercised ÷ total branches.
• Branch coverage subsumes statement coverage, not vice versa: the False side of an if without else has no statement.
• Worked example 1: late_fee at 2 of 4 branches passed; the test for the missing False outcomes (0 days) crashed; 2 tests give 4 of 4.
• Limits: defects needing a specific path, and defects inside compound conditions.
• Worked example 2: 3 tests gave 6 of 6 branches and passed; the condition not concession was never false; the test that made it false (4 days late, concession) found Rs 0 charged where Rs 100 was due.
• Beyond: branch condition, branch condition combination and MC/DC testing (ISO/IEC/IEEE 29119-4).

Test yourself

1. Define branch testing and branch coverage. Branch testing is a white-box technique that designs tests to exercise each outcome of each decision in the code, the branches of its control flow. Branch coverage is the number of branches exercised by the tests divided by the total number of branches, expressed as a percentage.

2. Why does branch coverage subsume statement coverage, but not the reverse? Every statement lies on some branch, so exercising every branch executes every statement. But a branch may contain no statement, such as the false side of an if without an else, so a test set can execute every statement without taking every branch.

3. Give a function and a test set with 100 per cent statement coverage but not 100 per cent branch coverage, and show the defect branch testing finds. late_fee assigns the fee only inside two ifs. The single test of 10 days late executes all five statements but takes only the true outcomes. Branch testing adds a test making both decisions false, 0 days late, and the function crashes because no fee was assigned.

4. What kinds of defect can 100 per cent branch coverage miss? Defects that need a particular combination of branches along a path, since each branch need be taken only once; defects inside a compound condition, since the decision can go both ways without each condition taking both values; and data-dependent defects, such as a division by zero.

5. Distinguish branch condition testing, branch condition combination testing and MC/DC. Branch condition testing requires each condition within a decision to take both values and the decision to take both outcomes. Branch condition combination testing requires every combination of condition values within a decision. MC/DC requires showing that each condition can independently change the decision's outcome, by pairs of tests differing only in that condition.

6. For the decision days_late >= 1 and not concession, give tests that satisfy MC/DC. Three tests: 4 days late without a concession (true), 0 days without a concession (false: only the first condition changed) and 4 days with a concession (false: only the second condition changed).