Hacker News Reader

Comment by alain94040 | Hacker News Reader

This is a silly article.

This is the clever idea of this paper. They assume that there are at least two compilers say {X} and {Y}. Then let {A} be the output of {X(P)} and let {B} be the output of {Y(P)}. The key insight is: If {A} is not equal to {B}, then one of the compilers is wrong.

Seriously? It's called having a reference, and comparing your fancy compiler against a reference to make sure the results match.

That's the entire insight of that article, after spending half a page discussing the order of authors in a paper.

Really weird.

View on HN

The underlying idea is differential fuzzing. It's useful and can often be surprisingly effective, but is pretty obvious in application. It's disappointing to see the author bury it under such obtuse language.

The idea seems to be a bit broader than that: we can test any group of compilers, none of whom we trust to be correct, by comparing their outputs against each other.

Though it won't tell us who is wrong, it tells us one of the pairs is (or both).

> Though it won't tell us who is wrong, it tells us one of the pairs is (or both).

If it's implementation-defined behavior, it won't even tell you that.

CSmith is carefully designed to only generate fully defined programs. That obviously limits the scope of bugs it covers quite a lot, but it still managed to uncover quite a few. Its biggest weakness is the difficulty of minimizing and root-causing bugs.

regehr's posts on program minimization are quite fascinating in their own right: https://blog.regehr.org/archives/1679

That doesn't matter though; if there is any difference, we can sort out the root cause by inspection.

There are also false negatives: either, or both compilers are wrong, or else the test program is wrong (undefined behavior or non-portable), or some combination of these, yet by fluke the results agree.

That's no big loss; if you're fuzzing, you're generating a lot of this stuff. If this geneated program won't catch a problem, maybe another one will. Individually, the test cases are cheap.

Unless all are wrong in the same way, which doesn't seem too impossible.

One of their compilers is never wrong: "Formal Methods as Bugscreen [--] the formally-verified CompCert compiler"

John Regehr did find 11 bugs in CompCert (the unverified portion).

If I've understood correctly, the compiling step is verified but the parsing and assembly steps are not, and no bugs have been found where valid input would have been compiled to valid but wrong assembly. I didn't see a statement about this on CompCert's web site though.

There were no bugs that their program could find; not that there are no bugs at all :-)

The tool isn't meant to find all bugs, but rather to suggest that bugs exist. That there exist limitations to the kinds of bugs it can find is probably acceptable.

Also if everyone implements something the same way, incorrectly according to the standard, then perhaps the standard itself is wrong. But otherwise, you just need one compiler to implement more strictly according to the standard for the bug to be suggested

To me, the real insight is the fuzz testing of compilers by automatically generating test cases that don't compare the compiled binaries directly but the results of executing those binaries instead. This way, they can find bugs in optimizing compilers as well. Also, one of the compilers is formally verified so they have an oracle (a golden reference). EDIT: Plus of course, their method is able to generate test cases where the results are free of any allowed undefined behaviour.

There's a related technique called metamorphic testing where the insight is that the only part of the program being compiled that matters is the part that will be executed to compute that differentiating output. So, the other parts can be mutated (even with undefined behaving code, as those parts are not executed) and differently mutated versions can be tested against one another. This works even when one just has a single compiler.

Anyone who has bootstrapped a compiler using the interpreter for the same language, and then validated the original interpreted test suite under compilation, has done this. Likewise anyone who boostrapped a new compiler using an existing one. There is nothing earth shattering here. Fuzzing is also not new. The idea of feeding the same input to multiple implementations of the same program side by side is not new, either. Just maybe the combination of all three is what is new.

> Just maybe the combination of all three is what is new.

Precisely.

Reply on news.ycombinator.com