Differential Testing and Shrinking

The problem

A model wrote a fast candidate for a function you already have a slow but trusted reference of. Instead of writing tests by hand, compare the two on random inputs (the idea of property-based testing). When they disagree, you have found a bug, and the tricky part is to show it in the simplest possible form: a long random failing input is hard to read, so you shrink it to a minimal one.

Inputs here are lists of integers.

Random inputs

random_list(rng, max_len=8, lo=-5, hi=5): a list whose length is rng.integers(0, max_len + 1) and whose values are drawn with rng.integers(lo, hi + 1, size=length), in that order (the length first, then one call for all the values), as a Python list of ints.

Finding a counterexample

find_counterexample(candidate, reference, rng, n_trials=200): draw up to n_trials lists with random_list and return the first one where candidate(xs) != reference(xs), or where candidate raises an exception (while reference does not). Return None if none is found. Call both functions on copies, so that a function that changes its input cannot affect the comparison.

Example. The reference is sorted(xs); the candidate is sorted(set(xs)), an "optimization" that drops duplicates. Random lists without repeated values pass. The first trial with seed 0 already gives [2, 0, -3, -2, -5, -5, -5], where the two disagree: the candidate drops two of the three $-5$ .

Shrinking

shrink(xs, fails): fails(xs) returns True when xs still makes the candidate fail. Repeat:

try removing one element, from the first position to the last, and keep the first shorter list that still fails;
when no single removal works, try replacing each nonzero element by 0, in order, and keep the first that still fails;
stop when nothing changes, and return the list.

Example. fails(xs) = "the list has a repeated value". Shrinking [3, -1, 4, 0, 5, 3]: removing 3 (first) leaves [-1, 4, 0, 5, 3], no repeat: no longer fails. Removing $-1$ leaves [3, 4, 0, 5, 3]: still fails, keep it. Continue: the final result is [3, 3]. Replacing a 3 by 0 would make the list [0, 3]: no repeat, so it is not kept. The bug is now obvious: two equal values.

A minimal counterexample is what makes a bug obvious. If the failure does not depend on the values, the shrunk list ends up as zeros: [3, -1, 4, 0, 5] may shrink to [0].

What to implement

random_list(rng, max_len=8, lo=-5, hi=5), find_counterexample(candidate, reference, rng, n_trials=200) and shrink(xs, fails) as described.

Requirements

A candidate that raises an exception where the reference does not counts as a failure.