News for hackers. Stuff that matters.
Re:Chasing a Bug in a SAT Solver by rgovostes on Friday June 21, 2024 @03:27AM (#40747059)
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

Re:Chasing a Bug in a SAT Solver by wyldfire on Friday June 21, 2024 @03:43AM (#40747127)
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).
Re:Chasing a Bug in a SAT Solver by kragen on Friday June 21, 2024 @03:31AM (#40747072)
thanks, this is fantastic!
Re:Chasing a Bug in a SAT Solver by andrewchambers on Friday June 21, 2024 @04:38AM (#40747468)
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.

Re:Chasing a Bug in a SAT Solver by nextaccountic on Friday June 21, 2024 @06:17AM (#40748015)
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...

Re:Chasing a Bug in a SAT Solver by gergo_barany on Friday June 21, 2024 @07:59AM (#40748657)
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

Re:Chasing a Bug in a SAT Solver by ajb on Friday June 21, 2024 @09:49AM (#40749617)
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)

Re:Chasing a Bug in a SAT Solver by pfdietz on Friday June 21, 2024 @09:55AM (#40749681)
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.

Re:Chasing a Bug in a SAT Solver by kragen on Saturday June 22, 2024 @11:14PM (#40764470)
i think hypothesis uses a string of random numbers rather than a tree?
Re:Chasing a Bug in a SAT Solver by pfdietz on Saturday June 22, 2024 @11:57PM (#40764666)
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.
Re:Chasing a Bug in a SAT Solver by PhilipRoman on Friday June 21, 2024 @10:14AM (#40749841)
AFL provides a nice standalone tool "afl-minimize", I've used it on several occasions and it works great for certain types of inputs.