Test-case Reducers Are Underappreciated Debugging Tools

Test-case reducers are less well known than they should be, and those who are aware of them don’t always realise the variety of ways we can use – perhaps even abuse! – them. In this post, I’m going to explore some of the things I’ve learnt while using these wonderful tools. I’ll start at the basics, because the idea is so simple that it can be hard to believe it works. I’ll then work my way up to a deeper surprise. Test-case reducers try to reduce the length of an input, but we can force them to take into account additional factors such as how often an error occurs, or the number of instructions executed. Depending on the problem you’re trying to debug, this can make a huge difference to the real-world effectiveness of test-case reducers. I don’t expect that anything in this post will surprise experts, but since I learnt this stuff the hard way, perhaps others will benefit from having some of it in one place. Test-case reduction Imagine we have written a program that crashes on a large input, and we don’t know what part of the input causes the crash: what can we do? Most of us will probably start with debugging our program using classic techniques, gradually moving from the quick and dirty (printf) to the more principled (debuggers) to – if we’re desperate and experienced – “exotic” tools (sanitisers, valgrind, etc). Every programmer ends up with a set of debugging tools and techniques they reach for, some more effective1 than others. One technique that is used less often than it probably should be is reducing the size of the input. In nearly all cases, the smaller an input is, the easier it is for us to work out why it’s leading to problems. Reduction can be manual. We can load an input into a text editor, remove a portion of it, and then see if the new, smaller, input still causes a crash. Unsurprisingly, as easily-bored humans with limited vision, we tend to miss many opportunities for reduction when we do so manually. It’s also often the case that deleting part of an input stops the program crashing in the way we were investigating: the reduced program might run to completion, or throw a different, correct and expected, error on the new input.

Even worse, at some point one realises that deleting portion A of the input doesn’t achieve the effect we want, but deleting disjoint portions A and B does: how big is the search space of deletions?! A Sisyphean future beckons. Test-case reducers Fortunately, there are tools that automate the process of reducing test cases: test-case reducers2. These take a program, an input, and an interestingness test. The test-case reducer tries ever shorter versions of the input, and the interestingness test tells the reducer whether those shorter versions still trigger the problem you care about. Test-case reducers can be astonishingly effective – 95-99% reductions are common – and often make debugging vastly easier. Test-case reducers can sound like they’re magic: how can a tool know what parts of the input to remove? To make things even worse, the community that has most thoroughly embraced them are compiler authors, who many programmers think of as being an impossibly skilled elite3. It seems to me that the combination of these two things has put many people off from trying such tools. The good news is that test-case reducers are not magic. The easiest way to see that is by writing one. Let’s imagine that I’ve written this program which reads words in from a file: import sys for l in open(sys.argv[1]): if len(l) > 25: print("Word too long\n")

When I run this on my machine with /usr/share/dict/words it prints a warning: $ python3 t.py /usr/share/dict/words Word too long

For the sake of the example, let’s pretend that seeing that warning is an “error” and we haven’t been able to work out why it crashes using traditional debugging techniques. Can a test-case reducer help us? The first thing we need to do is define our interestingness test. I’ll deliberately follow the conventions of the test-case reducers I’m familiar with and say that an interestingness test is a program which:

Returns 0 if the input is “interesting” – that is, the input manifests the error we are interested in – and we should use this reduced input going forward.

Returns non-0 if the input is “uninteresting” and we need to try a different reduction.

I’m going to write a simple4 shell script that takes a filename in as the first argument, runs my program above, and checks if it produces “Word too long” as its output. If it does, my interestingness test will return 0; if not it will return 1. #! /bin/sh if python3 t.py "$1" | grep "Word too long" > /dev/null; then exit 0 else exit 1 fi

Now we need to do the hard part: the reducer! Fortunately it’s not too difficult: #! /usr/bin/env python3 import subprocess, sys, tempfile cur = [x.rstrip() for x in list(open(sys.argv[2]))] i = 0 while i < len(cur): with tempfile.NamedTemporaryFile(mode="w") as p: cnd = cur[:] del cnd[i] p.write("\n".join(cnd)) p.flush() if subprocess.run([sys.argv[1], p.name]).returncode == 0: cur = cnd else: i += 1 print("\n".join(cur))

In essence, this first loads in the text input and splits it into lines (cur). Then it loops over the input. Each iteration creates a candidate input (cnd), with one line of input removed (del cnd[i]) relative to the previous starting point. We create a temporary file, write the candidate input to it, and run our interestingness test. If it returns 0, we keep the candidate as our new starting point (cur=cnd) or try the next line (i+=1) otherwise. When no more reductions are possible, the reduced input is printed to stdout. To say this implementation is slow is an understatement, but if I run it, it eventually5 prints out: $ python3 reducer.py ./interestingness.sh /usr/share/dict/words antidisestablishmentarianism

When I first came across the idea of test-case reducers, I was briefly sceptical: how can something so simple do anything useful?

Indeed, the example above might make the whole idea seem trivial: the “error” in my original program was so blindingly obvious that I surely didn’t need any of this additional machinery! In my opinion, thinking in that way can blind one to the key idea of test-case reduction: my reducer has no understanding of my interestingness test or, by extension, the underlying program the interestingness test is running. In other words, test-case reduction has done something useful despite having almost no understanding of why what it’s doing is useful. This lack of understanding is the key to the success of test-case reducers. I can run my test-case reducer on any text file, and it will work6. As a quick proof, I asked my favourite LLM to generate me a reasonably sized C program that might be amenable to test-case reduction, taking the very first thing it gave me. The problem in this case is a classic example: a program which unexpectedly produces two outputs in two different configurations (FAST=0 and FAST=1). The C file is 78 lines long and I defined the following interestingness test: #! /bin/sh set -eu cp "$1" t.c cc -std=c99 -O2 -DFAST=0 t.c -o slow cc -std=c99 -O2 -DFAST=1 t.c -o fast slow_out="$(timeout 1s ./slow)" || exit 1 fast_out="$(timeout 1s ./fast)" || exit 1 test "$slow_out" = "0d754a56" || exit 1 test "$fast_out" != "0d754a56" || exit 1

I’ll come back to why that’s longer than our first interestingness test a little bit later. I then made one quick change to my reducer: c = subprocess.run([sys.argv[1], p.name], stdout=subprocess.

DEVNULL, stderr=subprocess.DEVNULL)

to avoid output from subcommands confusing me, and then ran the reducer: $ python3 reducer.py ./interestingness.sh t.c > t2.c $ wc -l t2.c 54

The reducer took under 10 seconds to run, and in that short amount of time reduced the size of the input by 30% (by lines-of-code)! And, yes, it really did preserve the error I cared about. The great thing about reducers is that if you’re willing to run them for longer, they can do even better. Let’s make one very simple change to our reducer: every time we find an interesting input, we take the new input, and start deleting lines from the start: in other words, we are now able to retry lines which we could not previously remove. All it needs us to add is i=0 at the appropriate point: if c.returncode == 0: cur = cnd i = 0

It now takes almost 10 times longer to run, but it shaves another 3 lines off the reduced output. As you can imagine, further enhancements of the reducer do better and better jobs. I’m not going to bore you, or me, with them, because we can use off-the-shelf reducers which do all the tricks one might think of — and more! I’m particularly fond of Shrink Ray, which as well as having a number of powerful and sensible reduction rules also runs test-case reduction in parallel: $ pipx install shrinkray $ shrinkray --no-clang-delta ./interesting.sh t.c

By adding --no-clang-delta I’m preventing Shrink Ray from using any special knowledge it has of C. In other words, I’m making it as ignorant of the semantics of what it’s reducing as the simple reducer I wrote7. Shrink Ray has a nice UI, which is good, because it chugs away on our example for a while:

As you would expect – and bearing in mind the logarithmic y-axis in the graph – it inevitably hits diminishing returns after a while, so although it’s done a lot of reduction in a small number of minutes, it takes some tens of minutes to fully exhaust its arsenal.

After about 15 minutes, it finishes, having managed to reduce the input by over 60% (in terms of bytes)! It’s worth restating how impressive this is: I gave it a random C program, a small shell script, and it reduced it enough to make debugging a lot easier. Shrink Ray has all sorts of clever tricks up its sleeve. Some are fairly obvious – it knows standard comment syntaxes, for example, and will try removing those early on – but some are surprising. My favourite is when it starts reducing integers to smaller values, which often makes debugging surprisingly easier. I highly recommend watching it run, because seeing the reductions it attempts is illuminating. What I find particularly satisfying is when Shrink Ray manages to find a small number of reductions that suddenly unlock many further reductions. Here’s a screenshot from a random recent reduction I ran: I had spent quite some time trying to debug that particular input, and managed to do nothing but drown myself in detail. After about 20 minutes, Shrink Ray found the magic key that allowed the input to be reduced in size by 90%, then kept on chipping away until it was reduced by 99%. Suddenly the bug popped out at me. This is a common experience in test-case reduction. Interestingness tests can be hard to write Let’s go back to the second interestingness test I defined: #! /bin/sh set -eu cp "$1" t.c cc -std=c99 -O2 -DFAST=0 t.c -o slow cc -std=c99 -O2 -DFAST=1 t.c -o fast slow_out="$(timeout 1s ./slow)" || exit 1 fast_out="$(timeout 1s ./fast)" || exit 1 test "$slow_out" = "0d754a56" || exit 1 test "$fast_out" != "0d754a56" || exit 1

That might look a bit more complex than you were expecting: the reason for that is that bitter experience has shown me how easy it is to write suboptimal, mostly flat-out wrong, interestingness tests. Even this short example embeds several important lessons.