4 ms·

Isn't that potentially unsafe though? Random permutations can reduce arbitrary programs to destructive programs, in particular any program can be mutated to `rm

Isn't that potentially unsafe though? Random permutations can reduce arbitrary programs to destructive programs, in particular any program can be mutated to `rm -rf /` given enough time. Also even the problem of finding syntactically valid programs is combinatoric, it's pretty surprising that it can go toward a local optima in such a short time without having any understanding of the function or its derivatives.

jewel 2y ago
For compiled languages it should be fine, as you're only going to compile the permuted source code, not execute it. Given a sufficiently bad compiler bug anything is possible, but I think given that it's trying to minimize the size of an input that gives a particular output I don't think it's likely to explore distant branches.
- Quekid5 2y ago
  > Given a sufficiently bad compiler bug anything is possible, ... I can't help but wonder about the consteval/constexpr machinery in the various C++ compilers... It'd be interesting to see how much adversarial input has been tested for those. (I guess Zig's comptime might also be relevant, but I'm not sure what that's allowed to do. Maybe execute arbitrary code?) ... anyway just a stray thought.
  - cztomsik 2y ago
    IIRC there's `zig reduce` builtin in Zig :) https://github.com/ziglang/zig/blob/master/lib/compiler/reduce.zig https://github.com/ziglang/zig/blob/master/lib/compiler/redu...
- adastra22 2y ago
  It runs the executed code in order to determine if the bug exists, does it not?
  - Cieric 2y ago
    That depends completely on the interesting-ness test that's provided. If you're looking for a compiler bug (like I do often for my language), then the interesting-ness test checks the compile logs for information like the "Segmentation Fault" text, no need to run the actual executable. You could also hoist everything into docker if you really want to, or ship it off to another device to run.
  - furyofantares 2y ago
    If your compiler bug is "the compiler crashes when compiling this code" then you just need to try to compile it. Or if it's "it takes 15 minutes to compile this file" then you just need to check if it compiles in a reasonable/expected amount of time. If the bug is "the compiler generates an if/else where neither branch is hit", then you would need to execute the code. However, you would likely be able to directly reduce such a bug yourself. When the compiler is generating bad code you can usually just reduce it to that section of code directly. It seems like C-Reduce must be for compiler bugs where it's not generating any code at all (crashing) or the issue isn't with the code generation (extremely slow compiles).
- 0x457 2y ago
  > For compiled languages it should be fine, as you're only going to compile the permuted source code, not execute it. Only if you'te going for compiler bug. If you're working on minimal reproducible example. You need to make sure your code isn't reduced to: int main() { return 0; } in that case.
  - _flux 2y ago
    I don't think that should trigger a reasonable interesting condition one has specified, so that should not happen. So I suppose for non-compiler-bugs you need to check (from the output) that the correct thing is being done, in addition to detecting the actual issue.
    - 0x457 2y ago
      Well, that's what I said? If you're "reducing" anything other than a compiler bug (what C-Reduce is made for), you most likely have to execute code.
      - _flux 2y ago
        I was not disagreeing with that, merely pointing out that the reproduction test shouldn't be passing with the minimal runnable C program, or indeed for many many previous iterations before that. In my mind also runnable programs would be tested with grep, instead of relying on the return code of the program.
bawolff 2y ago
It seems pretty unlikely to mutate in a malicious direction, random chance probably wouldn't get there, and there doesn't seem like any reason it would be guided in that direction. "Enough time" does a lot of work here and warrants further analysis. With enough time it might produce the works of shakespare (if you ignore its designed to minimize), but we should probably view anything that would take more than a year as too much times.
eru 2y ago
Use a sandboxed VM?
ndjdjddjsjj 2y ago
Docker saves the day again!

jewel 2y ago

For compiled languages it should be fine, as you're only going to compile the permuted source code, not execute it. Given a sufficiently bad compiler bug anything is possible, but I think given that it's trying to minimize the size of an input that gives a particular output I don't think it's likely to explore distant branches.

Quekid5 2y ago
> Given a sufficiently bad compiler bug anything is possible, ... I can't help but wonder about the consteval/constexpr machinery in the various C++ compilers... It'd be interesting to see how much adversarial input has been tested for those. (I guess Zig's comptime might also be relevant, but I'm not sure what that's allowed to do. Maybe execute arbitrary code?) ... anyway just a stray thought.
- cztomsik 2y ago
  IIRC there's `zig reduce` builtin in Zig :) https://github.com/ziglang/zig/blob/master/lib/compiler/reduce.zig https://github.com/ziglang/zig/blob/master/lib/compiler/redu...
adastra22 2y ago
It runs the executed code in order to determine if the bug exists, does it not?
- Cieric 2y ago
  That depends completely on the interesting-ness test that's provided. If you're looking for a compiler bug (like I do often for my language), then the interesting-ness test checks the compile logs for information like the "Segmentation Fault" text, no need to run the actual executable. You could also hoist everything into docker if you really want to, or ship it off to another device to run.
- furyofantares 2y ago
  If your compiler bug is "the compiler crashes when compiling this code" then you just need to try to compile it. Or if it's "it takes 15 minutes to compile this file" then you just need to check if it compiles in a reasonable/expected amount of time. If the bug is "the compiler generates an if/else where neither branch is hit", then you would need to execute the code. However, you would likely be able to directly reduce such a bug yourself. When the compiler is generating bad code you can usually just reduce it to that section of code directly. It seems like C-Reduce must be for compiler bugs where it's not generating any code at all (crashing) or the issue isn't with the code generation (extremely slow compiles).
0x457 2y ago
> For compiled languages it should be fine, as you're only going to compile the permuted source code, not execute it. Only if you'te going for compiler bug. If you're working on minimal reproducible example. You need to make sure your code isn't reduced to: int main() { return 0; } in that case.
- _flux 2y ago
  I don't think that should trigger a reasonable interesting condition one has specified, so that should not happen. So I suppose for non-compiler-bugs you need to check (from the output) that the correct thing is being done, in addition to detecting the actual issue.
  - 0x457 2y ago
    Well, that's what I said? If you're "reducing" anything other than a compiler bug (what C-Reduce is made for), you most likely have to execute code.
    - _flux 2y ago
      I was not disagreeing with that, merely pointing out that the reproduction test shouldn't be passing with the minimal runnable C program, or indeed for many many previous iterations before that. In my mind also runnable programs would be tested with grep, instead of relying on the return code of the program.

bawolff 2y ago

It seems pretty unlikely to mutate in a malicious direction, random chance probably wouldn't get there, and there doesn't seem like any reason it would be guided in that direction. "Enough time" does a lot of work here and warrants further analysis. With enough time it might produce the works of shakespare (if you ignore its designed to minimize), but we should probably view anything that would take more than a year as too much times.

eru 2y ago

Use a sandboxed VM?

ndjdjddjsjj 2y ago

Docker saves the day again!