One reference, many inputs

Differential testing keeps a trusted reference and compares the generated function against it input by input. The reference is small and already trusted; the generated code is the part under test.

Coverage comes from input count, not from cleverness. Hundreds or thousands of driven inputs beat a handful of hand-picked cases.

A runnable comparison

The program below uses fake scripted functions in place of a model. It compares an accepted candidate and a planted-bug variant against the reference over all 256 byte values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

def ref_parity(byte_val):
    p = 0
    v = byte_val
    while v:
        p ^= v & 1
        v >>= 1
    return p

def gen_parity(byte_val):
    # FAKE stand-in for an assistant-generated function, written for this course
    p = 0
    for b in range(8):
        p ^= (byte_val >> b) & 1
    return p

def plant_parity(byte_val):
    # FAKE faulty variant that drops the top bit, written for this course
    p = 0
    for b in range(7):
        p ^= (byte_val >> b) & 1
    return p

def count_diffs(fn, inputs):
    n = 0
    for x in inputs:
        if fn(x) != ref_parity(x):
            n += 1
    return n

inputs = list(range(256))
good = count_diffs(gen_parity, inputs)
planted = count_diffs(plant_parity, inputs)
if good == 0 and planted == 128:
    print("PASS: 256 inputs, candidate agrees on all, planted-bug variant differs on 128")
else:
    print("FAIL: good=%d planted=%d" % (good, planted))
    raise SystemExit(1)

Read the difference count

The harness reports two counts: 0 differences for the accepted candidate and 128 for the planted-bug variant. The 128 follows from the code: the variant drops bit 7, so it differs exactly when bit 7 is set, which is half of 256 inputs.

The planted-bug count is the point of the exercise. A harness that reports zero on a known-bad variant proves nothing; one that reports 128 proves it can catch a one-bit-class mistake.

Common mistakes

Regenerating with different sampling varies the output, so a passing candidate is evidence about that candidate only. Temperature 0 is approximately greedy, not a guarantee of identical output across runs; sampling behavior varies by model, so measure it.

Related topics

• Property-based checks

• The verify-first checklist