arthrop0d

Brief articles on varied topics.

Property-Based Testing Shrinkers

testingalgorithms

Property-based testing shrinkers reduce a failing generated input to a smaller input that still demonstrates the bug. Instead of showing you a large random case, the shrinker searches for a simpler counterexample that preserves the test failure.

The problem: useful failures are often buried

A property-based test checks a general rule against many automatically generated inputs. For example, a test might generate lists of integers and assert that a function correctly detects whether a list contains duplicates.

The first failing list might contain dozens of values. It may have been assembled from nested structures, optional fields, strings, and unusual numbers. That input proves something is wrong, but it is a poor debugging artifact: most of its data is probably irrelevant.

Without shrinking, you typically get one of three outcomes:

A shrinker automates the second job while preserving the important part of the first: the failure must remain observable.

A failing example

Suppose the implementation only checks for adjacent duplicates:

def has_duplicate(values):
    for index in range(len(values) - 1):
        if values[index] == values[index + 1]:
            return True
    return False

The intended property is that the function agrees with the general definition of a duplicate:

def expected(values):
    return len(values) != len(set(values))

A generated input such as this exposes the bug:

values = [12, -400, 7, 12, 91, 3]

The value 12 occurs twice, so expected(values) is True, but the two occurrences are not adjacent and has_duplicate(values) returns False. The test fails.

The shrinker may eventually report:

values = [0, 1, 0]

This is much easier to read. It retains the essential structure: two equal values separated by a different value.

What the shrinker actually does

Shrinking starts with the concrete failing input. It does not generate a new random example and hope that it fails. Instead, it proposes simpler versions of the known failing value and runs the test again on each proposal.

Conceptually, the loop looks like this:

candidate = failing_input

for simpler in possible_simplifications(candidate):
    if test_still_fails(simpler):
        candidate = simpler
        restart_search_from(candidate)

test_still_fails means more than checking for one expected return value. It normally reruns the property and treats the same kind of assertion failure, exception, or other configured failure as a failure. A candidate that passes is rejected because it no longer demonstrates the problem.

The process repeats until the shrinker cannot find an acceptable simplification. The result is a minimal or small counterexample according to the framework's rules—not necessarily the mathematically smallest value in every possible sense.

The usual reduction steps

Shrinkers use knowledge of the generated value's structure. For a list, useful candidates commonly include:

  1. Removing the whole list or large slices.
  2. Removing smaller slices or individual elements.
  3. Shrinking each remaining element.
  4. Trying simpler combinations of nested values.

Applied to [12, -400, 7, 12, 91, 3], deletion might first remove the tail, then the middle, and so on. Removing too much causes the test to pass—for example, removing one of the 12 values eliminates the duplicate—so that candidate is discarded. The shrinker keeps reductions that still fail.

Once the list has the necessary shape, the element shrinker can simplify numbers. Many systems move integers toward zero, shorten strings, remove dictionary entries, or replace complex values with simpler members of the same generated domain. That can turn [12, -400, 12] into [0, 1, 0], provided the intermediate candidates continue to fail.

The order matters for efficiency, but not for correctness. A shrinker usually uses a deliberately chosen sequence of transformations rather than trying every possible input. It may remove chunks before individual elements, or simplify outer structures before inner ones. Different paths can produce different small counterexamples.

Preserving validity as well as failure

Generated inputs often obey constraints. A test might generate a non-empty list, a valid JSON document, or a request whose fields satisfy a schema. A shrinker must respect those constraints, or it could produce an input that the property was never intended to accept.

There are two common ways to handle this. A structured generator can provide shrink operations that naturally produce valid values. Alternatively, the test can reject invalid candidates before deciding whether they preserve the original failure. Either way, the goal is not merely “make the input smaller”; it is “make a valid input smaller while keeping the relevant failure.”

For compound data, the shrinker may also need to preserve relationships. If a generated object contains an identifier and a reference to that identifier, changing one without the other could create an unrelated failure. Good generators and shrinkers encode enough structure to avoid losing that meaning.

Why the reported example may change

The first failure is not always the final failure shown in the test output. After shrinking, the framework reruns the reduced input—sometimes several times—to confirm that it still fails. This is why logs often contain phrases such as “falsifying example” or “minimal failing case.” They describe the result of a search, not the original random input.

Shrinking also exposes flaky tests. If a candidate sometimes fails and sometimes passes, the shrinker cannot reliably decide whether a reduction preserves the failure. Nondeterministic dependencies, time, concurrency, and external services can therefore produce unstable or unhelpful counterexamples. A deterministic property and a reproducible environment make shrinking much more effective.

The practical value is straightforward: property-based testing explores a broad input space, while shrinking turns one discovered failure into a focused example. The shrinker repeatedly asks, “Can I remove or simplify this part and still reproduce the bug?” What remains is usually the shortest explanation of the defect that the test framework can find.

← All articles