GoKawiilTest-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 effective 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
... continue reading