7 ms·

You can use C-Reduce for any language

472 points by Tomte 2y ago

jchw 2y ago
I did not know about C-Reduce until just now, and I'm already hooked. This is basically like discovering git bisect for the first time. I'll have to stuff that into the back of my mind until I run into something where it might fit.
- __MatrixMan__ 2y ago
  Same story, I can't wait to try this.
- geon 2y ago
  I ran into some issues with what might be compiler bugs in cc65, a C compiler for the 6502 processor (c64, NES, Apple 1). I might see if I can get this set up. Apparently VICE supports "printing" to a file on the host OS, so I could run my test on the emulator.
- brightball 2y ago
  ...so I just discovered git bisect for the first time and this is pretty cool.
  - crdrost 2y ago
    Yes! The actual commands that you have to search up to get it to run automatically without user input, take almost as long to put together as finding the bug that you're finding (in the 80% case, of course there are 20% cases that take forever) but there is something so satisfying about seeing the thing just humming along once you have it set, that just makes it so satisfying.
    - dataflow 2y ago
      > Yes! The actual commands that you have to search up to get it to run automatically without user input, take almost as long to put together as finding the bug that you're finding Funny, I just wrote the exact same thing only to scroll down and see you had the same opinion: https://news.ycombinator.com/item?id=42262579 https://news.ycombinator.com/item?id=42262579
      - crdrost 2y ago
        One nice thing is that, once it's in your shell history, doing it again is really easy. So on a big codebase I was working on, it really did help multiple times and saved more than the initial investment. The frustrating thing is, because it's in your shell history, you have to look it up again after you change jobs...
- com2kid 2y ago
  Doing this manually was part of my first job out of college on a C/C++ compiler team. Kind of amazing that there is automation that can accomplish the same thing!
- pfdietz 2y ago
  It's great when combined with random test input generators.
  - eru 2y ago
    Yes, most property based testing libraries do this.
    - pfdietz 2y ago
      Hypothesis in particular has a very clever way to do test reduction. The key problem is that if your test generator is enforcing some constraint on the input, it's not necessarily the case that naive pruning will preserve the constraint. Hypothesis has a fairly general way of enforcing that the generated test input continues to satisfy constraints.
      - eru 2y ago
        Yes, Hypothesis is great. And 'shrinkray' mentioned elsewhere in the comments here seems to be by the same author.
- dataflow 2y ago
  > I did not know about C-Reduce until just now, and I'm already hooked. This is basically like discovering git bisect for the first time. I've known about git bisect for maybe a decade, and used it maybe... twice so far? And I think at least one of those times it took me longer to understand the command line options than it took to just do it manually. YMMV, maybe it's more useful in a larger collaborative codebase, but to me it sounds life-changing in theory but I haven't found it that in practice.
  - jchw 2y ago
    It's pretty incredible if I'm trying to find a breakage in a repo I don't understand. Build's failing? Easy enough: git bisect start master v1.1 # Bisect from v1.1 to current master git bisect run cmake --build .build # Find the first commit where `cmake --build` returns non-zero. No need to bother trying to understand the error message, I can go make coffee instead and then just look at the commit that broke it. Also, this is really useful for and in conjunction with Nixpkgs. It's not as useful for personal projects because chances are it won't tell you anything you don't already know.
    - dataflow 2y ago
      > It's pretty incredible if I'm trying to find a breakage in a repo I don't understand. > Build's failing? Easy enough: > It's not as useful for personal projects How often do you run into this situation, though? For your scenario to arise, you need: (1) A repo you're unfamiliar with (which is already unusual for most people... most people spend most of their time working on repositories they've become familiar with) (2) The unfamiliar repo to use standard build commands you already know, which is basically never the case in my experience (even cmake-based projects almost always need variables defined with custom names I don't know beforehand, and the configuration process is so onerous I find the GUI easier) (3) An obscure enough breakage where the output is complete garbage (otherwise the compile error would just tell you the file and line, and git blame would tell you the commit directly) (4) Knowledge that this unfamiliar repo actually would have actually built on your machine at some point (which is often not the case because cmake isn't hermetic and breakages are often due to having the wrong toolchain installed) (5) For the problem to be a mere build error, as opposed to some running of the program that requires investing time to automate (6) For you to not have any sort of prior CI or other form of validation on your dependencies, because you apparently didn't catch even catch a build error when it was introduced (never mind automated testing) I could go on, but these set of circumstances are more or less indistinguishable from ~never to me.
furyofantares 2y ago
Without an explanation of why it works on languages other than C, that is a hard claim to believe! I mean, I don't think they're lying but (given it doesn't use an LLM) I am bewildered.
- johnisgood 2y ago
  Yeah, I would have liked to see more examples and an explanation.
  - evmar 2y ago
    I glanced at the code. It seems to have multiple possible "passes" which reduce the code in various ways, and the passes here not tagged with "C"=>1 are used in the not-c mode recommended in the post. https://github.com/csmith-project/creduce/blob/31e855e290970cba0286e5032971509c0e7c0a80/creduce/creduce.in#L769 https://github.com/csmith-project/creduce/blob/31e855e290970... You can see the pass implementation in files on the left.
    - wat10000 2y ago
      The key thing is that the transforms it makes aren’t required to always produce a program that can actually run, or even build. The user provides a script which determines if a program is “interesting.” A program with build-time errors should be considered “not interesting” in most cases. (And if you’re hunting an incorrectly reported error, you’ll want to make sure you only consider that error to be interesting.) Then it yoinks out parts of your program and checks if the result is still interesting. If it’s not, that attempt is discarded and it tries something else. If the reduced program is still interesting, it will try yoinking out more stuff. Repeat until you like the result. There doesn’t need to be any understanding of the program in order for this to work. You just need something where removing some bit of the program has a chance of producing a new program that’s still interesting. That works in most programming languages. This process can take a long time, and it’s slower when there’s a lower probability of a removal producing an interesting program. Thus heuristics are added: don’t remove random character ranges, but work at a token level. When removing a brace, find the matching brace and remove the insides. That sort of thing. Most modern languages are similar enough to C that many of these rules are helpful for them too. And even if they don’t help, this just slows the process down, but it still works.
graypegg 2y ago
Found this article with examples of before and after: https://pramodkumbhar.com/2024/01/c-reduce-systematically-tackling-not-only-compiler-bugs-in-hpc-too/ https://pramodkumbhar.com/2024/01/c-reduce-systematically-ta... But still having trouble understanding how it knows WHAT to remove when trying each iteration. There must be some tokenization going on, but then I don't know how that would work across programming languages
wood_spirit 2y ago
Creduce is awesome. I used a test script that spent hours using CSmith to generate random test programs when developing an esoteric llvm target. When they crashed it automatically Creduced and left them for inspection. Invaluable!
asmeurer 2y ago
A paper by the authors John Regehr et al. from 2012 explaining how it works https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-eide-ellison-yang-pldi-2012.pdf https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-ei....
- gnulinux 2y ago
  I read this paper and I still feel lost as to how can this even be possible. It seems to understand how to tokenize, merge lines, remove tokens etc for arbitrary programming languages. Is there another paper that explains this algorithm alone?
  - IshKebab 2y ago
    It basically runs transformation passes over the code until they stop changing the code or break its behaviour. It seems like a small number of the passes are not specific to C: https://github.com/csmith-project/creduce/blob/master/creduce/creduce.in#L767-L938 https://github.com/csmith-project/creduce/blob/master/creduc... `"C" => 1,` means it is only for C. I would guess `pass_lines` is the most important for non-C code; I'm guessing (it's written in unreadable Perl) that it removes lines. So while it can work for languages other than C, most of its features are C-specific so it's not going to work nearly as well. Still I'd never heard of C-Reduce; pretty cool tool! Someone make one based on Tree Sitter, quick!
    - the8472 2y ago
      どうぞ https://langston-barrett.github.io/treereduce/ https://langston-barrett.github.io/treereduce/
      - IshKebab 2y ago
        Ah very cool!
    - codesnik 2y ago
      unreadable perl?! I clicked on the link expecting something super-terse and unstructured, but it's anything but. What the hell is wrong with people casually dropping such remarks.
lambda 2y ago
Note that as recommended by John Regehr, author of C-Reduce, for this use case you might also want to try Shrinkray, a tool that was written to be format independent and works well for cases that C-Reduce dow not: https://mastodon.social/@regehr/113489759789563570 https://mastodon.social/@regehr/113489759789563570
- canu7 2y ago
  Looking forward to try it! A shout out to cvise (https://github.com/marxin/cvise https://github.com/marxin/cvise) as a python alternative that works well too for non c languages.
- droideqa 2y ago
  Is this[0] the official repo of Shrinkray? [0]: https://github.com/DRMacIver/shrinkray https://github.com/DRMacIver/shrinkray
  - eru 2y ago
    Interesting, isn't that also the author of Python's hypothesis?
    - lambda 2y ago
      Yes, hypothesis also does minimization of failed test cases, so it's kind of a similar problem, just a question if what format the data is in and how you invoke your test.
    - DRMacIver 2y ago
      Yes, that's me. I accidentally got obsessed with test-case reduction as a result of writing Hypothesis, and wrote shrinkray because I thought it was ridiculous that I hadn't put all of the things I'd learned about test-case reduction into some general purpose tool that other people could benefit from. Shrinkray is still a bit under-advertised and rough around the edges in places, but I think that basically there's no good reason to use C-reduce over shrinkray for things that aren't C or C++. Shrinkray has very good generic heuristics that should work in most languages (it even works pretty well on binary files apparently, although I've not tested this myself), a couple of language specific passes for other languages, and is much more fun to watch. It might even be the case that you should use shrinkray for C and C++ too (because I use C-Reduce's transformations for those languages), but I'm less confident that that's true. The best I'll confidently claim is "probably more competitive than you'd expect".
andrewchambers 2y ago
I wrote a general purpose delta debugger in python - https://github.com/andrewchambers/ddmin-python https://github.com/andrewchambers/ddmin-python. Can be used to do the same thing.
judofyr 2y ago
Well, aren't you going to share the reduced file? Okay fine, let's see for ourselves: # Setup git clone git@github.com:RustPython/RustPython.git && cd RustPython && cargo build --release git clone git@github.com:tekknolagi/scrapscript.git && cp scrapscript/scrapscript.py . # Download interesting.sh, replace the path to RustPython chmod +x interesting.sh # Command in article: nix run nixpkgs#creduce -- --not-c interesting.sh scrapscript.py Niiice: (93.2 %, 13717 bytes) (93.2 %, 13683 bytes) (93.3 %, 13614 bytes) (93.3 %, 13592 bytes) (93.3 %, 13571 bytes) (93.3 %, 13517 bytes) (93.3 %, 13449 bytes) (93.4 %, 13412 bytes) (93.4 %, 13365 bytes) (93.4 %, 13333 bytes) (93.4 %, 13313 bytes) It seems to have stopped at "(96.4 %, 7347 bytes)" with the following output: https://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0cd8d https://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0...
- tomberek 2y ago
  Random thought. Another commenter worried about the runtime of the program becoming mangled and performing destructive operations on your machine. What if you run the reducer as a source-to-source Nix derivation? Protects against dangerous things, and can be easily distributed to remote builders.
  - capitol_ 2y ago
    How does this protect against dangerous things? My understanding is that this would just cause the dangerous things to be repeatable.
    - dietr1ch 2y ago
      It must be that by running any program within the nix build sandbox you don't expose your files unless you discover a privilege escalation attack by chance during the reduction process.
  - judofyr 2y ago
    Oh, that’s a neat idea. To reply to the sibling comment: Nix runs commands under a sandbox. It’s not bullet proof, but useful enough that it will prevent obvious commands like deleting local files and accessing the network. It took some time to get RustPython to run, but it seems to work fine: https://gist.github.com/judofyr/82d2255c92ebb0c6b3a6882ac9fde327#file-flake-nix https://gist.github.com/judofyr/82d2255c92ebb0c6b3a6882ac9fd... Also, after running it for 5 minutes it was now able of reducing it to a much smaller case: class a: def b() : c def h(d) : while d: break else: return d.b() def j(e) : f = a() if f.h () : g i = "" j(i)
def- 2y ago
Works well for SQL too, I‘ve been using it at my day job, found out via https://github.com/sqlancer/sqlancer?tab=readme-ov-file#reducing-a-bug https://github.com/sqlancer/sqlancer?tab=readme-ov-file#redu...
gmueckl 2y ago
How does this compare to dustmite (https://dlang.org/blog/2020/04/13/dustmite-the-general-purpose-data-reduction-tool/ https://dlang.org/blog/2020/04/13/dustmite-the-general-purpo...)?
dswilkerson 2y ago
Delta debugging is not new: https://en.wikipedia.org/wiki/Delta_debugging https://en.wikipedia.org/wiki/Delta_debugging My implementation of delta debugging, "delta" is 19+ years old: https://github.com/dsw/delta https://github.com/dsw/delta I released it as Open Source because Microsoft Research sent someone to my office to ask me to, back when Microsoft was calling Open Source a "cancer". The LLVM introduction by Latner refers to the "standard delta debugging tool", so it is rather well-known: https://aosabook.org/en/v1/llvm.html https://aosabook.org/en/v1/llvm.html 'unlike the standard "delta" command line tool.'
- arxanas 2y ago
  For other readers' benefit: C-Reduce is a little more sophisticated than plain delta-debugging. From the abstract of Test-Case Reduction for C Compiler Bugs (2012): > [...] [C-Reduce] produces outputs that are, on average, more than 25 times smaller than those produced by our other reducers or by the existing reducer that is most commonly used by compiler developers. We conclude that effective program reduction requires more than straightforward delta debugging. (Of course, this means that C-Reduce is 12 years old now.) At the same time, C-Reduce seems to be more general than the LLVM tool you linked ("BugPoint", dating to 2002), since that one works with LLVM IR specifically. I think most developers are generally unfamiliar with automatic test case minimization tools and techniques, so the post may be helpful even if the ideas have been known in their respective circles for quite some time.
jheriko 2y ago
the seems somewhat interesting but the example given is incredibly stupid.
- tekknolagi 2y ago
  Thank you for your feedback. I'll take that into consideration for my next blog post and compiler.
wyldfire 2y ago
A good companion/ successor is cvise. I've used c-reduce/cvise to reduce assembly programs to the minimal set that evokes an assembler defect quite a few times. It's a real handy program. [1] https://github.com/marxin/cvise https://github.com/marxin/cvise
ndesaulniers 2y ago
True, I've used it for asm, though these days I prefer c-vise.
af3d 2y ago
The link to the documentation seems to be dead. Archived version: https://web.archive.org/web/20221203043431/https://embed.cs.utah.edu/creduce/using/ https://web.archive.org/web/20221203043431/https://embed.cs....
rurban 2y ago
Of course, because it's perl, the Swiss army knife. Reducing token sets, blocks, statements is pretty language agnostic. It would have been an overarchitectured multi-file mess in python
- edwcross 2y ago
  A "super-parallel Python port" of C-Reduce, cvise (https://github.com/marxin/cvise https://github.com/marxin/cvise), is actually written in Python.
  - rurban 2y ago
    See? What I said
ajb 2y ago
This kind of algorithm needs to be better known. For example, the original DD algorithm can be used to automatically minimise the set of cloud permissions for a service (from a given set) (A PoC is aws-policy-minimize here: https://github.com/kanocomputing/aws-tools/ https://github.com/kanocomputing/aws-tools/)
pyrolistical 2y ago
Makes me think about an alternative one that is language specific and uses genetic algorithm. You start with your large repo case 1. Use language specific mutations that both add/delete 2. Crossover 3. Test fitness to see if they retain the compiler bug and sort by code size 4. Keep top N 5. Repeat This allows the code temporarily get larger to get out of local minimums.
snthpy 2y ago
This project should be called: re{pro,ducer}
- snthpy 2y ago
  i.e. $ echo re{pro,ducer} repro reducer

472 points by Tomte 2y ago

jchw 2y ago

I did not know about C-Reduce until just now, and I'm already hooked. This is basically like discovering git bisect for the first time. I'll have to stuff that into the back of my mind until I run into something where it might fit.

__MatrixMan__ 2y ago
Same story, I can't wait to try this.
geon 2y ago
I ran into some issues with what might be compiler bugs in cc65, a C compiler for the 6502 processor (c64, NES, Apple 1). I might see if I can get this set up. Apparently VICE supports "printing" to a file on the host OS, so I could run my test on the emulator.
brightball 2y ago
...so I just discovered git bisect for the first time and this is pretty cool.
- crdrost 2y ago
  Yes! The actual commands that you have to search up to get it to run automatically without user input, take almost as long to put together as finding the bug that you're finding (in the 80% case, of course there are 20% cases that take forever) but there is something so satisfying about seeing the thing just humming along once you have it set, that just makes it so satisfying.
  - dataflow 2y ago
    > Yes! The actual commands that you have to search up to get it to run automatically without user input, take almost as long to put together as finding the bug that you're finding Funny, I just wrote the exact same thing only to scroll down and see you had the same opinion: https://news.ycombinator.com/item?id=42262579 https://news.ycombinator.com/item?id=42262579
    - crdrost 2y ago
      One nice thing is that, once it's in your shell history, doing it again is really easy. So on a big codebase I was working on, it really did help multiple times and saved more than the initial investment. The frustrating thing is, because it's in your shell history, you have to look it up again after you change jobs...
com2kid 2y ago
Doing this manually was part of my first job out of college on a C/C++ compiler team. Kind of amazing that there is automation that can accomplish the same thing!
pfdietz 2y ago
It's great when combined with random test input generators.
- eru 2y ago
  Yes, most property based testing libraries do this.
  - pfdietz 2y ago
    Hypothesis in particular has a very clever way to do test reduction. The key problem is that if your test generator is enforcing some constraint on the input, it's not necessarily the case that naive pruning will preserve the constraint. Hypothesis has a fairly general way of enforcing that the generated test input continues to satisfy constraints.
    - eru 2y ago
      Yes, Hypothesis is great. And 'shrinkray' mentioned elsewhere in the comments here seems to be by the same author.
dataflow 2y ago
> I did not know about C-Reduce until just now, and I'm already hooked. This is basically like discovering git bisect for the first time. I've known about git bisect for maybe a decade, and used it maybe... twice so far? And I think at least one of those times it took me longer to understand the command line options than it took to just do it manually. YMMV, maybe it's more useful in a larger collaborative codebase, but to me it sounds life-changing in theory but I haven't found it that in practice.
- jchw 2y ago
  It's pretty incredible if I'm trying to find a breakage in a repo I don't understand. Build's failing? Easy enough: git bisect start master v1.1 # Bisect from v1.1 to current master git bisect run cmake --build .build # Find the first commit where `cmake --build` returns non-zero. No need to bother trying to understand the error message, I can go make coffee instead and then just look at the commit that broke it. Also, this is really useful for and in conjunction with Nixpkgs. It's not as useful for personal projects because chances are it won't tell you anything you don't already know.
  - dataflow 2y ago
    > It's pretty incredible if I'm trying to find a breakage in a repo I don't understand. > Build's failing? Easy enough: > It's not as useful for personal projects How often do you run into this situation, though? For your scenario to arise, you need: (1) A repo you're unfamiliar with (which is already unusual for most people... most people spend most of their time working on repositories they've become familiar with) (2) The unfamiliar repo to use standard build commands you already know, which is basically never the case in my experience (even cmake-based projects almost always need variables defined with custom names I don't know beforehand, and the configuration process is so onerous I find the GUI easier) (3) An obscure enough breakage where the output is complete garbage (otherwise the compile error would just tell you the file and line, and git blame would tell you the commit directly) (4) Knowledge that this unfamiliar repo actually would have actually built on your machine at some point (which is often not the case because cmake isn't hermetic and breakages are often due to having the wrong toolchain installed) (5) For the problem to be a mere build error, as opposed to some running of the program that requires investing time to automate (6) For you to not have any sort of prior CI or other form of validation on your dependencies, because you apparently didn't catch even catch a build error when it was introduced (never mind automated testing) I could go on, but these set of circumstances are more or less indistinguishable from ~never to me.

furyofantares 2y ago

Without an explanation of why it works on languages other than C, that is a hard claim to believe! I mean, I don't think they're lying but (given it doesn't use an LLM) I am bewildered.

johnisgood 2y ago
Yeah, I would have liked to see more examples and an explanation.
- evmar 2y ago
  I glanced at the code. It seems to have multiple possible "passes" which reduce the code in various ways, and the passes here not tagged with "C"=>1 are used in the not-c mode recommended in the post. https://github.com/csmith-project/creduce/blob/31e855e290970cba0286e5032971509c0e7c0a80/creduce/creduce.in#L769 https://github.com/csmith-project/creduce/blob/31e855e290970... You can see the pass implementation in files on the left.
  - wat10000 2y ago
    The key thing is that the transforms it makes aren’t required to always produce a program that can actually run, or even build. The user provides a script which determines if a program is “interesting.” A program with build-time errors should be considered “not interesting” in most cases. (And if you’re hunting an incorrectly reported error, you’ll want to make sure you only consider that error to be interesting.) Then it yoinks out parts of your program and checks if the result is still interesting. If it’s not, that attempt is discarded and it tries something else. If the reduced program is still interesting, it will try yoinking out more stuff. Repeat until you like the result. There doesn’t need to be any understanding of the program in order for this to work. You just need something where removing some bit of the program has a chance of producing a new program that’s still interesting. That works in most programming languages. This process can take a long time, and it’s slower when there’s a lower probability of a removal producing an interesting program. Thus heuristics are added: don’t remove random character ranges, but work at a token level. When removing a brace, find the matching brace and remove the insides. That sort of thing. Most modern languages are similar enough to C that many of these rules are helpful for them too. And even if they don’t help, this just slows the process down, but it still works.

graypegg 2y ago

Found this article with examples of before and after: https://pramodkumbhar.com/2024/01/c-reduce-systematically-tackling-not-only-compiler-bugs-in-hpc-too/ https://pramodkumbhar.com/2024/01/c-reduce-systematically-ta... But still having trouble understanding how it knows WHAT to remove when trying each iteration. There must be some tokenization going on, but then I don't know how that would work across programming languages

wood_spirit 2y ago

Creduce is awesome. I used a test script that spent hours using CSmith to generate random test programs when developing an esoteric llvm target. When they crashed it automatically Creduced and left them for inspection. Invaluable!

asmeurer 2y ago

A paper by the authors John Regehr et al. from 2012 explaining how it works https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-eide-ellison-yang-pldi-2012.pdf https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-ei....

gnulinux 2y ago
I read this paper and I still feel lost as to how can this even be possible. It seems to understand how to tokenize, merge lines, remove tokens etc for arbitrary programming languages. Is there another paper that explains this algorithm alone?
- IshKebab 2y ago
  It basically runs transformation passes over the code until they stop changing the code or break its behaviour. It seems like a small number of the passes are not specific to C: https://github.com/csmith-project/creduce/blob/master/creduce/creduce.in#L767-L938 https://github.com/csmith-project/creduce/blob/master/creduc... `"C" => 1,` means it is only for C. I would guess `pass_lines` is the most important for non-C code; I'm guessing (it's written in unreadable Perl) that it removes lines. So while it can work for languages other than C, most of its features are C-specific so it's not going to work nearly as well. Still I'd never heard of C-Reduce; pretty cool tool! Someone make one based on Tree Sitter, quick!
  - the8472 2y ago
    どうぞ https://langston-barrett.github.io/treereduce/ https://langston-barrett.github.io/treereduce/
    - IshKebab 2y ago
      Ah very cool!
  - codesnik 2y ago
    unreadable perl?! I clicked on the link expecting something super-terse and unstructured, but it's anything but. What the hell is wrong with people casually dropping such remarks.

lambda 2y ago

Note that as recommended by John Regehr, author of C-Reduce, for this use case you might also want to try Shrinkray, a tool that was written to be format independent and works well for cases that C-Reduce dow not: https://mastodon.social/@regehr/113489759789563570 https://mastodon.social/@regehr/113489759789563570

canu7 2y ago
Looking forward to try it! A shout out to cvise (https://github.com/marxin/cvise https://github.com/marxin/cvise) as a python alternative that works well too for non c languages.
droideqa 2y ago
Is this[0] the official repo of Shrinkray? [0]: https://github.com/DRMacIver/shrinkray https://github.com/DRMacIver/shrinkray
- eru 2y ago
  Interesting, isn't that also the author of Python's hypothesis?
  - lambda 2y ago
    Yes, hypothesis also does minimization of failed test cases, so it's kind of a similar problem, just a question if what format the data is in and how you invoke your test.
  - DRMacIver 2y ago
    Yes, that's me. I accidentally got obsessed with test-case reduction as a result of writing Hypothesis, and wrote shrinkray because I thought it was ridiculous that I hadn't put all of the things I'd learned about test-case reduction into some general purpose tool that other people could benefit from. Shrinkray is still a bit under-advertised and rough around the edges in places, but I think that basically there's no good reason to use C-reduce over shrinkray for things that aren't C or C++. Shrinkray has very good generic heuristics that should work in most languages (it even works pretty well on binary files apparently, although I've not tested this myself), a couple of language specific passes for other languages, and is much more fun to watch. It might even be the case that you should use shrinkray for C and C++ too (because I use C-Reduce's transformations for those languages), but I'm less confident that that's true. The best I'll confidently claim is "probably more competitive than you'd expect".

andrewchambers 2y ago

I wrote a general purpose delta debugger in python - https://github.com/andrewchambers/ddmin-python https://github.com/andrewchambers/ddmin-python. Can be used to do the same thing.

judofyr 2y ago

Well, aren't you going to share the reduced file? Okay fine, let's see for ourselves: # Setup git clone git@github.com:RustPython/RustPython.git && cd RustPython && cargo build --release git clone git@github.com:tekknolagi/scrapscript.git && cp scrapscript/scrapscript.py . # Download interesting.sh, replace the path to RustPython chmod +x interesting.sh # Command in article: nix run nixpkgs#creduce -- --not-c interesting.sh scrapscript.py Niiice: (93.2 %, 13717 bytes) (93.2 %, 13683 bytes) (93.3 %, 13614 bytes) (93.3 %, 13592 bytes) (93.3 %, 13571 bytes) (93.3 %, 13517 bytes) (93.3 %, 13449 bytes) (93.4 %, 13412 bytes) (93.4 %, 13365 bytes) (93.4 %, 13333 bytes) (93.4 %, 13313 bytes) It seems to have stopped at "(96.4 %, 7347 bytes)" with the following output: https://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0cd8d https://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0...

tomberek 2y ago
Random thought. Another commenter worried about the runtime of the program becoming mangled and performing destructive operations on your machine. What if you run the reducer as a source-to-source Nix derivation? Protects against dangerous things, and can be easily distributed to remote builders.
- capitol_ 2y ago
  How does this protect against dangerous things? My understanding is that this would just cause the dangerous things to be repeatable.
  - dietr1ch 2y ago
    It must be that by running any program within the nix build sandbox you don't expose your files unless you discover a privilege escalation attack by chance during the reduction process.
- judofyr 2y ago
  Oh, that’s a neat idea. To reply to the sibling comment: Nix runs commands under a sandbox. It’s not bullet proof, but useful enough that it will prevent obvious commands like deleting local files and accessing the network. It took some time to get RustPython to run, but it seems to work fine: https://gist.github.com/judofyr/82d2255c92ebb0c6b3a6882ac9fde327#file-flake-nix https://gist.github.com/judofyr/82d2255c92ebb0c6b3a6882ac9fd... Also, after running it for 5 minutes it was now able of reducing it to a much smaller case: class a: def b() : c def h(d) : while d: break else: return d.b() def j(e) : f = a() if f.h () : g i = "" j(i)

def- 2y ago

Works well for SQL too, I‘ve been using it at my day job, found out via https://github.com/sqlancer/sqlancer?tab=readme-ov-file#reducing-a-bug https://github.com/sqlancer/sqlancer?tab=readme-ov-file#redu...

gmueckl 2y ago

How does this compare to dustmite (https://dlang.org/blog/2020/04/13/dustmite-the-general-purpose-data-reduction-tool/ https://dlang.org/blog/2020/04/13/dustmite-the-general-purpo...)?

dswilkerson 2y ago

Delta debugging is not new: https://en.wikipedia.org/wiki/Delta_debugging https://en.wikipedia.org/wiki/Delta_debugging My implementation of delta debugging, "delta" is 19+ years old: https://github.com/dsw/delta https://github.com/dsw/delta I released it as Open Source because Microsoft Research sent someone to my office to ask me to, back when Microsoft was calling Open Source a "cancer". The LLVM introduction by Latner refers to the "standard delta debugging tool", so it is rather well-known: https://aosabook.org/en/v1/llvm.html https://aosabook.org/en/v1/llvm.html 'unlike the standard "delta" command line tool.'

arxanas 2y ago
For other readers' benefit: C-Reduce is a little more sophisticated than plain delta-debugging. From the abstract of Test-Case Reduction for C Compiler Bugs (2012): > [...] [C-Reduce] produces outputs that are, on average, more than 25 times smaller than those produced by our other reducers or by the existing reducer that is most commonly used by compiler developers. We conclude that effective program reduction requires more than straightforward delta debugging. (Of course, this means that C-Reduce is 12 years old now.) At the same time, C-Reduce seems to be more general than the LLVM tool you linked ("BugPoint", dating to 2002), since that one works with LLVM IR specifically. I think most developers are generally unfamiliar with automatic test case minimization tools and techniques, so the post may be helpful even if the ideas have been known in their respective circles for quite some time.

jheriko 2y ago

the seems somewhat interesting but the example given is incredibly stupid.

tekknolagi 2y ago
Thank you for your feedback. I'll take that into consideration for my next blog post and compiler.

wyldfire 2y ago

A good companion/ successor is cvise. I've used c-reduce/cvise to reduce assembly programs to the minimal set that evokes an assembler defect quite a few times. It's a real handy program. [1] https://github.com/marxin/cvise https://github.com/marxin/cvise

ndesaulniers 2y ago

True, I've used it for asm, though these days I prefer c-vise.

af3d 2y ago

The link to the documentation seems to be dead. Archived version: https://web.archive.org/web/20221203043431/https://embed.cs.utah.edu/creduce/using/ https://web.archive.org/web/20221203043431/https://embed.cs....

rurban 2y ago

Of course, because it's perl, the Swiss army knife. Reducing token sets, blocks, statements is pretty language agnostic. It would have been an overarchitectured multi-file mess in python

edwcross 2y ago
A "super-parallel Python port" of C-Reduce, cvise (https://github.com/marxin/cvise https://github.com/marxin/cvise), is actually written in Python.
- rurban 2y ago
  See? What I said

ajb 2y ago

This kind of algorithm needs to be better known. For example, the original DD algorithm can be used to automatically minimise the set of cloud permissions for a service (from a given set) (A PoC is aws-policy-minimize here: https://github.com/kanocomputing/aws-tools/ https://github.com/kanocomputing/aws-tools/)

pyrolistical 2y ago

Makes me think about an alternative one that is language specific and uses genetic algorithm. You start with your large repo case 1. Use language specific mutations that both add/delete 2. Crossover 3. Test fitness to see if they retain the compiler bug and sort by code size 4. Keep top N 5. Repeat This allows the code temporarily get larger to get out of local minimums.

snthpy 2y ago

This project should be called: re{pro,ducer}

snthpy 2y ago
i.e. $ echo re{pro,ducer} repro reducer