Property-based, mutation & fuzzing

1 · Property-based testing

Start with the bug you've shipped. You wrote a function, added three tests — the empty case, a normal case, a big number — watched them go green, and moved on. Weeks later it falls over on an input you never imagined: a string with a lone %, a list that was already sorted, a number at exactly the integer boundary. The tests didn't lie; they only ever checked the handful of cases you could think of. And that's the ceiling of example-based testing: it can only find bugs in the examples you were already smart (or paranoid) enough to write down.

Here's the reframe that breaks that ceiling. Instead of asking "what should f(3) return?" — a question you have to answer once per example — ask "what should be true of the answer no matter what I feed in?" That second question is a property: a statement that must hold for every valid input, not one input. "Decoding an encoded string gives the original back" is a property. "Sorting a list twice is the same as sorting it once" is a property. You state the rule once, and a generator then hammers it with hundreds of random inputs trying to prove you wrong.

Think of it as the difference between spot-checking a bridge by driving your own car over it a few times, versus rolling every conceivable weight across it and asserting "it never collapses." You've stopped enumerating cases and started asserting a law. When the generator does find an input that breaks the law, a good tool does one more crucial thing: it shrinks the counterexample — it whittles the messy random failing input down to the smallest one that still breaks, so instead of debugging 'x9#%, qz%a' you debug '%'. That minimal case is usually a one-line diagnosis.

The common mistake is writing a property that's really just the implementation restated — asserting sorted(xs) == my_own_sort(xs) tests nothing if both share the same bug. Good properties come from a few reliable families (round-trip, idempotence, invariants, a trusted oracle) that hold for reasons independent of how you coded the function — that independence is what makes them catch real bugs. The lab below is a from-scratch for_all loop so the whole mechanism runs on the stdlib; the callout after it names the real tool, Hypothesis.

Example-based tests check specific input→output pairs you thought of. Property-based testing flips this: you state a property — an invariant that must hold for every input — and a generator produces hundreds of random inputs to try to falsify it. When it finds a counterexample, a good tool shrinks it to the minimal failing case. The lab is a from-scratch for_all so it runs on the stdlib.

property_based.pyimport random

# Property-based testing: instead of hand-picking examples, state a *property*
# (an invariant that must hold for ALL inputs) and check it on many random ones.
# A from-scratch mini property-tester, so this runs on the stdlib alone.
def for_all(gen, prop, trials=1000, seed=0):
    rng = random.Random(seed)
    for i in range(trials):
        x = gen(rng)
        if not prop(x):
            return ("FAIL", x)         # a counterexample
    return ("OK", trials)

# System under test: an encode/decode round-trip.
def encode(s): return s.replace("%", "%25").replace(",", "%2C")
def decode(s): return s.replace("%2C", ",").replace("%25", "%")

# Property 1 (round-trip / inverse): decode(encode(s)) == s for ALL strings.
rand_str = lambda rng: "".join(rng.choice("a,%z ") for _ in range(rng.randint(0, 8)))
print("round-trip :", for_all(rand_str, lambda s: decode(encode(s)) == s, seed=1))

# Property 2 (idempotence of sorting): sorting twice == sorting once.
rand_list = lambda rng: [rng.randint(-5, 5) for _ in range(rng.randint(0, 6))]
print("sort idempot:", for_all(rand_list, lambda xs: sorted(sorted(xs)) == sorted(xs), seed=2))

# Property 3 catches a bug: a broken decode that forgets to unescape "%25".
def decode_buggy(s): return s.replace("%2C", ",")
print("buggy decode:", for_all(rand_str, lambda s: decode_buggy(encode(s)) == s, seed=1))

round-trip : ('OK', 1000)
sort idempot: ('OK', 1000)
buggy decode: ('FAIL', '%, a%aa')

The round-trip and idempotence properties hold across 1000 random inputs; the buggy decoder is falsified with a counterexample containing a bare % (here '%, a%aa') — exactly the escaping case a hand-written example set tends to miss. Our mini-tester reports the first failing input; a real tool like Hypothesis would shrink it down to the minimal '%'. Common property families to memorize:

2 · Metamorphic testing — when you have no oracle

Property-based testing has a hidden assumption: that you can check the answer. To assert decode(encode(s)) == s, you need to know what the right answer is. But a huge slice of the software you'll actually test in AI work has no knowable right answer. What exact relevance score should a search ranker give document #47 for the query "budget travel"? What's the correct summary of a support ticket? What should a physics simulation output on step 900,000? You cannot compute these by hand, so you have nothing to compare against. This is the famous oracle problem — an "oracle" being any source of the known-correct answer, and for these systems there simply isn't one.

The clever escape is to stop asking "is this output correct?" and start asking "are these two related outputs consistent with each other?" You don't need to know the answer to trig to be certain that sin(x) and sin(π − x) must come out equal — that relationship holds by definition, whatever the actual values are. Testing a relationship between the outputs of deliberately-related inputs, rather than one output against a fixed answer, is metamorphic testing. The relationship you assert is called a metamorphic relation.

These relations are usually easier to state than to notice, because they're the "obvious" things a correct system can never violate. Make a document longer by adding a word the query is searching for — its relevance must not drop. Feed a classifier the same image rotated slightly — the label shouldn't flip. Multiply every price in a shopping cart by two — the total must double. In each case you never say what the number is, only how it must move when you nudge the input in a known direction. Any run that breaks the relation is a genuine bug, caught with zero oracle.

The trap to avoid is asserting a relation that isn't actually guaranteed — "adding any word raises the score" is false (add an irrelevant word and a good ranker leaves the score flat), so a test built on it would fire false alarms and get deleted. The art is picking transforms whose effect is genuinely certain (add a matching word → score can't decrease). As you'll see in TQ8 and ch05-evaluation, this is the backbone technique for testing LLMs and ML models, precisely because their outputs are non-deterministic and have no ground-truth oracle.

Sometimes you cannot compute the exact expected output — a search ranker, an ML model, a physics simulation. The oracle problem. Metamorphic testing sidesteps it: instead of checking one output against a known answer, you check a relation between the outputs of related inputs. If sin(x) is hard to verify, you can still assert sin(x) == sin(π − x).

metamorphic.pyimport random

# Metamorphic testing: when you have NO oracle (you can't compute the exact
# expected output), test a RELATION between outputs of related inputs instead.
# Example: a search-relevance score you can't hand-compute, but you know adding
# a matching word must not DECREASE the score (a metamorphic relation).
def score(query, doc):
    q = set(query.split()); d = doc.split()
    return sum(d.count(w) for w in q)      # count of query-word hits

rng = random.Random(0)
words = ["alpha", "beta", "gamma", "delta"]
violations = 0
for _ in range(1000):
    query = " ".join(rng.sample(words, 2))
    doc = " ".join(rng.choice(words) for _ in range(rng.randint(1, 6)))
    base = score(query, doc)
    # Metamorphic transform: append a word that IS in the query.
    q_word = query.split()[0]
    followup = score(query, doc + " " + q_word)
    if followup < base:                    # relation: must not decrease
        violations += 1
print("metamorphic relation held:", violations == 0, "| violations:", violations)

metamorphic relation held: True | violations: 0

We cannot say what the relevance score should be, but we know a valid metamorphic relation: adding a query word to a document must not decrease its score. Checking that over 1000 random query/doc pairs finds no violation — and would immediately flag a ranker that regressed. This is the workhorse technique for testing the non-deterministic and LLM systems in TQ8 and ch05-evaluation.

3 · Mutation testing — do your assertions actually bite?

Here is a green build that means nothing. A teammate proudly reports 95% test coverage. Every function runs under test, the dashboard is a wall of green, everyone feels safe. Then a one-character bug — < where they meant <= — ships to production and corrupts data for a week. How? Because coverage answers a much weaker question than everyone assumes. Coverage tells you a line was executed during the tests. It says nothing about whether any test would have complained if that line were wrong. A test can call a function, exercise every branch, and assert absolutely nothing — 100% covered, 0% checked.

So how do you test whether your tests are any good? You can't just read them — a weak assertion looks identical to a strong one at a glance. The trick is delightfully sneaky: deliberately break the code and see if the tests notice. That is mutation testing. A mutation tool makes a tiny, plausible edit to your source — flips a + to a -, a < to a <=, an and to an or, a True to a False — producing a deliberately buggy copy called a mutant. Then it runs your test suite against that mutant.

The logic is beautifully simple. If the mutant is buggy and a good suite should catch it, then some test ought to fail. A test that fails on the mutant has done its job — the mutant is killed. But if every test still passes on the broken code, the mutant is a survivor, and that survival is hard proof that your tests never actually checked the behaviour that line controls. The mutation score — killed ÷ total mutants — is therefore a direct, honest measure of how much your assertions bite, which is exactly the thing coverage pretends to measure but can't. Think of it as hiring a saboteur to plant faults in your product just to check that your quality inspectors are awake.

The catch that keeps the score below 100%: some mutants change the code without changing its behaviour at all — mutating x * 1 into x + 1 would be caught, but x * 1 into x ** 1 computes the same thing, so no test could ever kill it. These equivalent mutants are undetectable in general, which is why serious teams chase a high mutation score on their riskiest modules rather than a perfect one. The lab builds a miniature mutation tester and pits a strong suite (which pins the value) against a weak one (which only runs the code) so you can watch the score collapse.

Coverage (TQ6) tells you a line ran; it cannot tell you the assertion checked the right thing. Mutation testing answers that: it deliberately introduces small bugs (mutants) into your code — flip + to -, < to <=, and to or — then runs your suite. A mutant your suite fails on is killed; one it passes is a survivor — proof of a weak or missing assertion.

The mutation score is killed / total mutants. The lab builds a tiny mutation tester and contrasts a strong suite (asserts the value) with a weak one (only runs the code):

mutation.pyimport copy

# Mutation testing: judge a TEST SUITE by seeding bugs (mutants) into the code
# and checking the suite catches them. A suite that passes on buggy code is weak.
# From-scratch mutation tester: swap an operator in the source, re-exec, run tests.
SOURCE = "def add(a, b):\n    return a + b\n"

def make_tests(strong):
    # strong=True asserts a value (kills the mutant); weak just checks it runs.
    def tests(ns):
        add = ns["add"]
        if strong:
            assert add(2, 3) == 5          # pins the value -> kills '+'->'-'
        else:
            add(2, 3)                      # no assertion -> mutant survives
    return tests

MUTATIONS = [("+", "-"), ("+", "*")]       # operator-swap mutants

def mutation_score(source, tests):
    killed = 0
    for old, new in MUTATIONS:
        mutant = source.replace(old, new, 1)
        ns = {}
        exec(mutant, ns)
        try:
            tests(ns)                      # suite runs against the mutant
        except AssertionError:
            killed += 1                    # caught the bug -> mutant killed
    return killed, len(MUTATIONS)

k1, n = mutation_score(SOURCE, make_tests(strong=True))
print(f"strong suite: killed {k1}/{n}  score={100*k1//n}%")
k2, _ = mutation_score(SOURCE, make_tests(strong=False))
print(f"weak   suite: killed {k2}/{n}  score={100*k2//n}%  <- passes on buggy code!")

strong suite: killed 2/2  score=100%
weak   suite: killed 0/2  score=0%  <- passes on buggy code!

The strong suite kills 100% of mutants because assert add(2,3) == 5 fails when + becomes - or *. The weak suite calls add but asserts nothing, so every mutant survives — a 0% mutation score. That is the whole lesson: a green, high-coverage suite can still be worthless if it never asserts. Real tools do this at scale:

4 · Fuzzing — hunt for crashes

Every technique so far tested inputs a human could imagine. Property tests, metamorphic relations, mutants — they all reason about meaningful inputs and whether the answer is right. But some of the nastiest production incidents don't come from a wrong answer; they come from an input so weird that the code never had a chance to give any answer at all. The parser that got a truncated file and threw IndexError. The decoder handed "-3/0" and died on ZeroDivisionError. The endpoint that received 40,000 bytes of emoji and hung. Nobody wrote a test for these because nobody thinks like that — but an attacker, or a flaky upstream system, absolutely will.

Fuzzing is the technique that thinks like that for you. Instead of a few careful cases, it fires an enormous, cheap stream of generated — often malformed, garbage, adversarial — inputs at your code and watches for one specific failure mode: not "wrong output" but a crash. An unhandled exception, an infinite hang, a memory fault. The bar is deliberately low, and that's the point: "never crash on any input" is a promise you can check millions of times per second without ever knowing what the correct output would have been. It's the ultimate no-oracle test — you're only asserting that the code stays on its feet.

Naive fuzzing throws purely random bytes, which is like trying to open a combination lock by mashing digits — you'll almost never stumble onto the deep code paths where the interesting bugs hide. So modern fuzzers are coverage-guided, and this is the idea that made fuzzing legendary (AFL, libFuzzer). The fuzzer instruments your program to see which lines each input reaches. When an input triggers a branch it has never reached before, that input is a lead worth following — the fuzzer saves it and mutates it further, evolving a corpus of inputs that burrow deeper and deeper into the code. Random discovers the shallow bugs; coverage-guidance grows toward the buried ones.

The mindset shift worth internalizing: a passing fuzz run never proves your code is correct — it only proves nobody found a crash this time. Fuzzing is a hunt, not a proof, which is why it targets parsers, decoders, deserializers, and anything eating untrusted input, and why it's usually run continuously rather than once. The lab strips this to its skeleton — a loop that feeds biased random inputs to a buggy fraction parser and reports the first crash — so the crash-finding core is visible before you meet the real tools (Atheris, AFL++, libFuzzer) in the callout.

Fuzzing throws large volumes of generated (often malformed) input at a target and watches for a crash — an unhandled exception, hang, or memory fault — rather than a wrong value. Modern fuzzers are coverage-guided: they instrument the target and keep inputs that reach new code paths, evolving toward deep bugs (the AFL/libFuzzer idea). The lab is a minimal crash-finder that shows the core loop.

fuzz.pyimport random

# Fuzzing: feed many generated inputs and watch for a CRASH (an unhandled
# exception), not a wrong value. Real fuzzers are coverage-guided: they keep
# inputs that reach NEW code paths. This mini loop shows the crash-finding core.
def parse_fraction(s):
    # Buggy parser: crashes on a zero denominator (unhandled ZeroDivisionError).
    num, den = s.split("/")
    return int(num) / int(den)

def fuzz(target, gen, trials=5000, seed=0):
    rng = random.Random(seed)
    seen_paths = set()
    for i in range(trials):
        x = gen(rng)
        try:
            target(x)
            seen_paths.add("ok")
        except ZeroDivisionError:
            return ("CRASH", x, i)          # found the crashing input
        except (ValueError, IndexError):
            seen_paths.add("handled")       # expected bad-input rejections
    return ("no crash", trials)

# Generator biased toward interesting inputs (small ints, includes 0 denominator).
def gen(rng):
    n = rng.randint(-3, 3); d = rng.randint(-2, 2)
    return f"{n}/{d}"

print("fuzz result:", fuzz(parse_fraction, gen, seed=7))

fuzz result: ('CRASH', '-3/0', 3)

The generator is biased toward interesting values (small ints, including a zero denominator), so within a few iterations it produces an input like '-3/0' and the parser's unhandled ZeroDivisionError surfaces. A coverage-guided fuzzer would additionally retain inputs that unlock new branches, finding far deeper bugs than this uniform sampler.

5 · Which technique, and when

Four techniques in one chapter invites a natural mistake: treating them as competitors and picking a favourite. They're not rivals — they answer four genuinely different questions, and reaching for the wrong one wastes effort while leaving the real risk untested. The way to keep them straight is to hold onto the question each one uniquely answers, because that question is what tells you when to reach for it.

Line them up by the question: Property-based asks "does an invariant hold for all inputs?" — reach for it on pure logic, parsers, and data transforms where you can check the answer and want confidence far beyond a few examples. Metamorphic asks "does a relation hold when I have no way to check the answer?" — reach for it on ML models, rankers, simulations, and LLM output, exactly where the oracle is missing. Mutation asks "do my tests actually catch bugs?" — it isn't a test of your code at all, it's a test of your test suite, so reach for it when you need to trust a suite that guards something important. Fuzzing asks "does any input crash me?" — reach for it wherever untrusted or malformed data enters: parsers, decoders, deserializers.

Notice they operate at different layers, which is why mature teams run all four rather than choosing. Property and metamorphic tests define what correct means; mutation testing then audits whether those tests are strong enough to defend the definition; fuzzing hunts the pathological inputs none of the others thought to write down. A useful way to picture it: property/metamorphic tests are the rules of the game, mutation testing is the referee checking the rules are enforced, and fuzzing is the stress-tester trying to break the stadium. The table below is your at-a-glance decision guide; the callout after it drives home that they compose into layers, not a single choice.

Knowledge check

import random

def for_all(gen, prop, trials=1000, seed=0):
    rng = random.Random(seed)
    for _ in range(trials):
        x = gen(rng)
        if not prop(x): return ("FAIL", x)
    return ("OK", trials)

print(for_all(lambda r: r.randint(-10**9, 10**9),
              lambda n: int(str(n)) == n, seed=1))
# ('OK', 1000)

import random
from collections import Counter

def for_all(gen, prop, trials=1000, seed=0):
    rng = random.Random(seed)
    for _ in range(trials):
        x = gen(rng)
        if not prop(x): return ("FAIL", x)
    return ("OK", trials)

rand_list = lambda r: [r.randint(-9, 9) for _ in range(r.randint(0, 8))]
is_ordered = lambda xs: all(a <= b for a, b in zip(sorted(xs), sorted(xs)[1:]))
print("idempotent:", for_all(rand_list, lambda xs: sorted(sorted(xs)) == sorted(xs), seed=3))
print("invariant :", for_all(rand_list,
      lambda xs: is_ordered(xs) and Counter(sorted(xs)) == Counter(xs), seed=4))
# idempotent: ('OK', 1000)
# invariant : ('OK', 1000)

import random

def score(query, doc):
    q = set(query.split()); d = doc.split()
    return sum(d.count(w) for w in q)

rng = random.Random(0); words = ["a", "b", "c", "d"]; bad = 0
for _ in range(2000):
    query = " ".join(rng.sample(words, 2))
    doc = " ".join(rng.choice(words) for _ in range(rng.randint(1, 5)))
    if score(query, doc + " " + query.split()[0]) < score(query, doc):
        bad += 1
print("violations:", bad)   # 0

SRC = ("def clamp(x, lo, hi):\n"
       "    if x < lo: return lo\n"
       "    if x > hi: return hi\n"
       "    return x\n")
MUT = [("< lo", "<= lo"), ("> hi", ">= hi")]

def mscore(src, tests):
    killed = 0
    for old, new in MUT:
        ns = {}; exec(src.replace(old, new, 1), ns)
        try: tests(ns); 
        except AssertionError: killed += 1
    return killed, len(MUT)

def strong(ns):
    c = ns["clamp"]
    assert c(0, 0, 10) == 0 and c(10, 0, 10) == 10   # probes both boundaries
def weak(ns):
    assert ns["clamp"](5, 0, 10) == 5               # middle only

print("strong:", mscore(SRC, strong))   # (2, 2)
print("weak  :", mscore(SRC, weak))     # (0, 2)

import random

def target(s):                       # returns reached branches; may crash
    reached = {"enter"}
    parts = s.split("/")
    if len(parts) == 2:
        reached.add("two")
        return int(parts[0]) / int(parts[1]), reached   # ZeroDivision on /0
    reached.add("one"); return None, reached

def fuzz(seed=0, trials=3000):
    rng = random.Random(seed); corpus = ["1/1"]; seen = set()
    for _ in range(trials):
        base = rng.choice(corpus)
        s = "".join(c for c in base if rng.random() > 0.3) + rng.choice("0/12")
        try:
            _, reached = target(s)
            if reached - seen: seen |= reached; corpus.append(s)   # new coverage
        except ZeroDivisionError:
            return ("CRASH", s)
        except (ValueError, IndexError):
            pass
    return ("no crash", len(corpus))

print(fuzz(seed=1))   # ('CRASH', ...) with a zero denominator

POLICY = {
    "critical": {"cov": 90, "mut": 80},
    "core":     {"cov": 80, "mut": 60},
    "peripheral":{"cov": 60, "mut": 0},   # coverage only
}

def gate(modules):
    fails = []
    for m in modules:
        pol = POLICY[m["tier"]]
        if m["cov"] < pol["cov"]:
            fails.append((m["name"], "coverage", pol["cov"] - m["cov"]))
        if m["mut"] < pol["mut"]:
            fails.append((m["name"], "mutation", pol["mut"] - m["mut"]))
    return fails

mods = [
    {"name": "payments", "tier": "critical",  "cov": 92, "mut": 71},
    {"name": "search",   "tier": "core",      "cov": 83, "mut": 64},
    {"name": "banner",   "tier": "peripheral","cov": 55, "mut": 0},
]
for f in gate(mods): print(f)
# ('payments', 'mutation', 9)
# ('banner', 'coverage', 5)