Property-Based Testing and How Shrinking Finds the Minimal Case

A table of examples tests the cases its author thought of. Property-based testing tests cases generated from a description of the input domain, and it reports failures as a minimized counter- example rather than as “input 47 failed”. The two halves of that sentence are separate mechanisms, and the second is the one that decides whether the technique is usable. Generating random inputs is trivial; reducing a failure to something a person can read is the engineering.

The framing that makes the technique coherent: a property is a statement that must hold for all inputs of a shape, checked against many inputs of that shape. The generator defines the shape, the property defines the claim, and the shrinker turns a violation into evidence.

From example to property

An example test asserts that sort([3,1,2]) equals [1,2,3]. A property asserts that for every list xs, sort(xs) is a permutation of xs and sort(xs) is non-decreasing. The property is checked against a hundred generated lists and, if it holds, says considerably more than the example did.

Not every specification decomposes into properties this cleanly, and the ones that do tend to share a shape: an invariant that must survive a transformation, an algebraic law relating two operations, a round-trip between a parser and a printer, a comparison against a slow but obviously correct implementation. The oracle problem does not disappear; it moves. A property is an oracle that applies to a whole class of inputs, which is a better oracle than a single expected value but still an oracle someone had to invent. The classes of oracle available are surveyed in test oracles and expected outputs.

The practical gain is in the tails. Hand-written cases cluster around values the author considered plausible: small integers, ASCII strings, short lists. Random generation produces the empty string, the string of 300 identical characters, the list containing the same object twice, the integer at the type boundary. Those are where the defects live, and they are exactly the cases intuition skips.

Generators as composable descriptions

A generator produces values of a type. The primitive generators cover integers within a range, floating point values including special ones, byte strings, and characters drawn from a specified alphabet. Composition is what makes the approach scale: a list generator takes an element generator, a record generator takes a generator per field, and a recursive generator describes trees by referring to itself with a size bound.

Two design decisions inside a generator matter more than the surface API.

Distribution. A uniform integer generator over a 64-bit range almost never produces a value below 100, and values below 100 are where the interesting behaviour usually is. Practical libraries bias toward small magnitudes and toward boundaries, mixing a uniform draw with a geometric one so that small values are common and large values are still reachable. Without that bias, a property about a counter will be tested a hundred times with numbers in the trillions and never with 0, 1, or the maximum.

Size as a parameter. A generator takes a size parameter that bounds the magnitude of what it produces: the length of a list, the depth of a tree, the absolute value of an integer. Libraries start small and increase size across the run, so early cases are cheap and later cases are large. Size is also the lever the shrinker uses, which is why it must be part of the generator’s interface rather than an afterthought.

from hypothesis import given, strategies as st

# Composed: a list of distinct integers, plus a target drawn from the same range.
@given(st.lists(st.integers(), unique=True), st.integers())
def test_binary_search_finds_every_member(xs, target):
    xs = sorted(xs)
    idx = binary_search(xs, target)
    if target in xs:
        assert idx >= 0 and xs[idx] == target
    else:
        assert idx == -1

The generator describes the shape; the property covers both branches with one statement about target in xs. The library runs the body many times, then reports the smallest failure it can find.

A generator that is too permissive produces failures that are not about the code. A property about a date parser fed arbitrary byte strings will fail on inputs that are not dates, and the counterexample will be noise. Constraining the generator — characters from the date grammar’s alphabet, then a format check — moves the failure rate from mostly-invalid to mostly-valid, which is what makes a run informative. The measure to watch is not the pass rate but whether failures, when they occur, are about the property.

The shrinker as a search over failure

When a generated input fails, the library has a failing input of whatever size the run happened to reach: a list of 137 elements, a string of 96 characters, a nested structure eight levels deep. The shrinker searches for a smaller input that still fails, and the search is what makes the output readable.

The mechanism is a greedy descent over a lazily generated structure. The original input is not stored as a finished value; it is a tree of choices made by the generators — “this list has 137 elements”, “element 12 is the integer 4001”, “this optional field is present”. Shrinking walks that tree and tries replacing a choice with a smaller one: fewer elements, a smaller integer, an absent optional field, a shallower recursion. Each candidate is re-run through the property. If it still fails, the candidate replaces the current best and the descent continues from there.

Two properties of that loop explain the results. It is greedy, so it finds a local minimum rather than a global one; the reported counterexample is minimal with respect to the shrink candidates tried, not minimal in any absolute sense. And it is structure-preserving: the shrink candidates are produced by the same generators, so the result is always a valid input of the described shape. A shrinker that produced invalid inputs would report counterexamples the code rejects for the wrong reason.

The cost is that each shrink step is another execution of the property, and the descent runs until no candidate improves. For a property that takes a millisecond, shrinking a deep structure can take hundreds of executions, which is why libraries cap the number of shrink steps and why a slow property produces a large reported counterexample: the budget ran out before the descent finished.

The payoff is diagnostic. “Sorted insert fails for [0, 1] inserting 1” names the bug; “fails for a list of 137 elements” does not. Reduction turns a random failure into a hand-written example, which then belongs in the suite as a regression test with no generator involved.

Determinism, seeds, and reproduction

A randomized test that cannot be reproduced is a defect report with no content. Every library therefore supports a fixed seed: the run that failed records the seed, and re-running with that seed regenerates the same inputs in the same order, including the same shrinking path.

The subtlety is that reproduction depends on more than the seed. Changing the generator, the size schedule, or the number of cases changes the sequence, so a stored seed is only meaningful against a frozen version of the test. Libraries handle this by recording both the seed and the shrink path — the sequence of choices that produced the minimal counterexample — so a later run can jump directly to the failing case even if the surrounding sequence changed.

In CI, the usual arrangement is a random seed per run plus a persistent record of failures. The random seed explores; the recorded failures guarantee that a known bug stays fixed. Without the second half, a property suite is a random walk that rediscovers the same three bugs forever.

Where the technique is weak

Random generation is a sampling method, and sampling has blind spots that are structural rather than a matter of running more cases.

Rare preconditions. A property that only applies when a generated input satisfies a rare predicate will almost never apply. Filtering generated values until the predicate holds is the wrong fix, because the filter’s acceptance rate determines the run time: a predicate true for one input in a thousand needs a thousand generations per useful case. The right fix is to generate values that satisfy the predicate by construction.

Long dependency chains. A generator that produces a valid configuration of twenty interacting fields will produce almost exclusively invalid ones, because validity is a conjunction. The generator must encode the conjunction — produce the fields in an order that makes each subsequent choice valid — which is real work and is where most of the effort in a mature property suite goes.

Numeric properties over wide domains. A property about a hash function’s distribution, or about a floating-point routine’s precision, is checked against samples that cover a vanishing fraction of the domain. A hundred cases say nothing about a distribution; the property either holds by construction or the technique cannot establish it.

Stateful systems. Properties over sequences of operations need a model of the system’s expected state and a generator of valid operation sequences. This is model-based testing, it is considerably more work than a pure-function property, and it is where the technique’s leverage on real systems lives. The construction of such models is the subject of stateful and model-based testing.

The economics of a property suite

A property costs more to write than an example and less to maintain. The writing cost is the generator plus the property plus, usually, one round of debugging the generator itself, which fails on inputs the property never intended to see. The maintenance cost is low because the property does not name specific values: a refactoring that changes the internal representation leaves the property untouched, whereas a table of examples may need every row rewritten.

The signal per case is lower, since most generated cases pass trivially, and the signal per failure is much higher, since the shrinker supplies a minimal input. The combination argues for using properties where the input space is large and the invariant is statable, and examples where the specification is a table of specific outcomes. Both belong in the same suite, and neither replaces the other.