arthrop0d

Brief articles on varied topics.

Property-Based Testing and Shrinking Counterexamples

testingalgorithms

Property-based testing checks a rule against many generated inputs, then shrinks any failing input into a smaller counterexample that still exposes the bug. Instead of writing every example by hand, you describe the behavior that must always hold and let the testing tool search for violations.

The problem with example-based tests

A conventional unit test gives a function a few chosen inputs and checks their expected outputs. Those examples are valuable, but they cover only the cases someone thought to write down. Bugs often hide in combinations of values: an empty list followed by a duplicate, a boundary number, an unusual string, or a particular ordering of records.

Writing more examples helps, but the number of possible inputs grows quickly. Property-based testing addresses this by generating many inputs automatically. It also reports an input that violates the rule, rather than merely saying that one of a large collection of random cases failed.

The rule being tested is called a property: a statement that should remain true across a whole class of inputs. For example, removing duplicates should not leave two copies of the same value, regardless of the input list.

A property is an invariant

An invariant is a condition that must hold before or after an operation. Consider this deliberately incorrect implementation, which only compares each value with the item most recently added:

def unique(values):
    result = []
    for value in values:
        if not result or value != result[-1]:
            result.append(value)
    return result

It removes adjacent duplicates, but it does not remove a value that appeared earlier. The input [1, 2, 1] produces [1, 2, 1].

A property-based test can state the intended behavior:

from hypothesis import given, strategies as st

@given(st.lists(st.integers()))
def test_unique_has_no_duplicates(values):
    result = unique(values)
    assert len(result) == len(set(result))

st.integers() describes the input domain, and st.lists(...) describes lists made from that domain. The @given decorator runs the test with many lists rather than with one list written into the test itself.

The test is not checking that unique matches one expected output. It checks a general condition about every result: its length must equal the number of distinct values in it. When the implementation is wrong, the test framework records a list that makes the assertion false.

Generation is guided, not just random

A generator, also called a strategy, knows how to produce values of a particular shape: integers, text, lists, dictionaries, or structured combinations of those things. It can favor useful boundary cases such as zero, negative numbers, empty collections, and very small or very large values.

This is different from throwing arbitrary bytes at a program. The strategy generates inputs that are valid for the test and can be reproduced and reduced. You can also compose strategies: a request strategy might generate a method, URL, headers, and body while preserving relationships between them.

The framework repeatedly evaluates the property with generated values. A passing input is discarded. A failing input is a counterexample—a concrete value that disproves the claimed property.

The important output is not “test failed after 347 random attempts.” It is “this specific input violates the rule.”

Shrinking turns a failure into an explanation

A first failing input may be noisy. It could contain a long list, large integers, or irrelevant fields. Shrinking is the process of searching for a smaller failing input.

After finding a failure, the framework applies reductions appropriate to the input’s structure, such as:

After each reduction, it runs the property again. If the reduced candidate still fails, the candidate becomes the new failure. If it passes, that reduction is rejected and another is tried. The process continues until the framework cannot find a simpler candidate under its shrink rules.

For the broken unique function, a generated failure might contain dozens of integers. Shrinking can remove unrelated elements and reduce the remaining values. A result such as [0, 1, 0] is enough to preserve the bug: the first and last values are duplicates, but they are not adjacent. The smaller example exposes the missing behavior much more clearly than the original list.

Shrinking is not simply “sort the input” or “keep the first few items.” It must preserve the condition that causes the failure. For structured inputs, that may require coordinated changes. If a test generates a start and end date with the requirement that the end follows the start, a shrinker should reduce both while maintaining that relationship.

What “smallest” means

A shrunk example is usually minimal according to the framework’s reduction order, not necessarily the mathematically smallest possible value. There may be several equally small counterexamples, and a framework may stop when its known reductions no longer improve the case.

That is still a major advantage. The goal is an understandable, reproducible failure—not a proof that no smaller input exists. The final counterexample often reveals an overlooked boundary or a missing case immediately.

Reproducing and fixing the failure

Property-based tools normally retain enough information to replay a failure, often through a seed or an encoded example shown in the failure report. The exact mechanism varies, but the workflow is consistent: run the same property, inspect the minimal input, then turn that input into a regression test if it represents an important permanent case.

The shrinking report also changes how you debug. Instead of examining a large randomly generated request, you investigate the small input that still fails. Once the implementation is fixed, the property continues testing the whole generated domain, protecting against nearby cases that a single regression example might miss.

Generation finds breadth; shrinking supplies clarity. Together, they let you state behavior at the level of an invariant while receiving a concrete, usually small explanation when the software violates it.

← All articles