Hacker News Reader

Comment by rgovostes | Hacker News Reader

If you have a large input that triggers a bug and you want to reduce it, it might be worth looking into the Delta Debugging[0] algorithm used by C-Reduce[1] to make minimal test cases for C-like languages. C-Reduce "happens to do a pretty good job reducing the size of programs in languages other than C/C++, such as JavaScript and Rust" so it might work out of the box for you. (Aside: there's also ddSMT for SMT solvers that take SMT-LIB2 input.)

0: https://www.st.cs.uni-saarland.de/dd/

1: https://github.com/csmith-project/creduce

View on HN

A problem with test case reduction occurs when your test generator also ensures the test input satisfies some properties. This means naive reduction can produce invalid inputs for which "failure" doesn't represent a bug. An example is in testing C compilers where the C code must not exhibit any of the many undefined behaviors described in the C standard. Creduce goes to some lengths to work around this problem.

A solution to this is doing the reduction on a tree of random numbers provided to the test generator, so the output is always a legitimate test input. The Hypothesis testing system takes this approach.

i think hypothesis uses a string of random numbers rather than a tree?

It partitions the string into an implicit tree and uses that structure to reduce the string, if I understand correctly. The partitioning is obtained from the stack's structure during generation.

The Delta Debugging algorithm is an underused tool, which is not only applicable to debugging, but any task where you need to find a minimal satisfying subset. For example, it can also be used to automatically find an (approximately) minimal set of cloud permissions needed for some purpose: https://github.com/KanoComputing/aws-tools/blob/master/bin/a... This is otherwise quite a tedious exercise.

(It's approximate because theoretically you can find a local minimum - but for permissions, there's probably only one minimum)

I wrote a single file python3 implementation with no other dependencies here:

https://github.com/andrewchambers/ddmin-python

It can be used as a cli program or a python library.

Not sure if this makes sense but is that similar to fuzzing? Or can it be used alongside fuzzing

What I am familiar is with property testing libraries that automatically shrink failing cases, like quickcheck for Haskell, quickcheck for Rust and Hypothesis for Python. I suppose that if we modelled C code as an AST one could use quickcheck to shrink a test case. Is creduce like this, but operating on strings rather than trees?

https://stackoverflow.com/questions/16968549/what-is-a-shrin...

Yes, the kind of test case reduction that C-Reduce does is analogous to QuickCheck's shrinking. Some of C-Reduce's transformations are purely "on strings", e.g., "delete a physical line from the file", others are a bit more syntax-aware, e.g., "delete N tokens", and some actually build an AST using Clang and do some semantic transformations like "replace function parameter by global variable".

And yes, this is used alongside fuzzing, once a fuzzer (like Csmith from the same group as C-Reduce) has found a file that provokes a bug.

A reducer is not a fuzzer itself, although with some ingenuity it can be made to behave like a fuzzer in certain contexts: https://blog.regehr.org/archives/1284

AFL provides a nice standalone tool "afl-minimize", I've used it on several occasions and it works great for certain types of inputs.

I've used creduce (and cvise) to reduce test cases for all kinds of inputs, even ones that aren't C-like. If it has newline-delimited text, it'll work well (though you should adjust the knobs accordingly in order to converge faster).

thanks, this is fantastic!

Reply on news.ycombinator.com