Without looking at the paper, I would guess it would be like a fuzzer that apply mutations that reduce the size of the input.
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.
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.
> 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.
It runs the executed code in order to determine if the bug exists, does it not?
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.
> 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.
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.