5 ms·

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 o

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.

setr 7y ago
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).
- WalterBright 7y ago
  > 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.
  - recursivecaveat 7y ago
    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.
    - zellyn 7y ago
      regehr's posts on program minimization are quite fascinating in their own right: https://blog.regehr.org/archives/1679 https://blog.regehr.org/archives/1679
  - kazinator 7y ago
    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.
- hoseja 7y ago
  Unless all are wrong in the same way, which doesn't seem too impossible.
  - tuukkah 7y ago
    One of their compilers is never wrong: "Formal Methods as Bugscreen [--] the formally-verified CompCert compiler"
    - jcranmer 7y ago
      John Regehr did find 11 bugs in CompCert (the unverified portion).
      - tuukkah 7y ago
        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.
    - setr 7y ago
      There were no bugs that their program could find; not that there are no bugs at all :-)
  - setr 7y ago
    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
debatem1 7y ago
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.
tuukkah 7y ago
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.
- pfdietz 7y ago
  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.
- kazinator 7y ago
  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.
  - tuukkah 7y ago
    > Just maybe the combination of all three is what is new. Precisely.

setr 7y ago

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).

WalterBright 7y ago
> 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.
- recursivecaveat 7y ago
  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.
  - zellyn 7y ago
    regehr's posts on program minimization are quite fascinating in their own right: https://blog.regehr.org/archives/1679 https://blog.regehr.org/archives/1679
- kazinator 7y ago
  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.
hoseja 7y ago
Unless all are wrong in the same way, which doesn't seem too impossible.
- tuukkah 7y ago
  One of their compilers is never wrong: "Formal Methods as Bugscreen [--] the formally-verified CompCert compiler"
  - jcranmer 7y ago
    John Regehr did find 11 bugs in CompCert (the unverified portion).
    - tuukkah 7y ago
      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.
  - setr 7y ago
    There were no bugs that their program could find; not that there are no bugs at all :-)
- setr 7y ago
  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

debatem1 7y ago

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.

tuukkah 7y ago

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.

pfdietz 7y ago
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.
kazinator 7y ago
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.
- tuukkah 7y ago
  > Just maybe the combination of all three is what is new. Precisely.