3 ms·

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

• kragen 2y ago
  thanks, this is fantastic!
• wyldfire 2y ago
  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).
• andrewchambers 2y ago
  I wrote a single file python3 implementation with no other dependencies here: https://github.com/andrewchambers/ddmin-python https://github.com/andrewchambers/ddmin-python It can be used as a cli program or a python library.
• nextaccountic 2y ago
  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-shrink-with-regard-to-haskells-quickcheck https://stackoverflow.com/questions/16968549/what-is-a-shrin...
  • gergo_barany 2y ago
    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 https://blog.regehr.org/archives/1284
• ajb 2y ago
  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/aws-policy-minimize 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)
• pfdietz 2y ago
  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.
  • kragen 2y ago
    i think hypothesis uses a string of random numbers rather than a tree?
    • pfdietz 2y ago
      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.
• PhilipRoman 2y ago
  AFL provides a nice standalone tool "afl-minimize", I've used it on several occasions and it works great for certain types of inputs.