3 ms·

That's not entirely true. If you have multiple implementations, you can compare fuzz results of the implementations against each other rather than against groun

by lmkg 8y ago

That's not entirely true. If you have multiple implementations, you can compare fuzz results of the implementations against each other rather than against ground truth. There's a project that does this with several popular C compilers that's found some good bugs, but I can't remember the name right now. This approach does still have limitations, e.g. it assumes errors are independent. And, of course, it requires independent implementations. But it is sometimes more accessible than an oracle.

Joky 8y ago
Even there, you need a fuzzer that can generate code that actually execute and does something you can observe. Otherwise the output of a C compiler (as in the binary itself) is expected to differ even between different versions of the same compiler.
pfdietz 8y ago
You're probably referring to Csmith, the random C generator from John Regehr's group at U. of Utah. https://embed.cs.utah.edu/csmith/ https://embed.cs.utah.edu/csmith/ Fuzzing C compilers this way is difficult, because you can't generate programs that have undefined behaviors, and C has so many of those. The complexity and challenge of their project was to not generate bogus programs while not throwing away too much diversity. The general technique is called differential testing. For compilers, it was pioneered by William McKeeman at DEC in the 1990s. He also addressed C compilers, with a more limited set of inputs than Csmith produces. https://www.cs.dartmouth.edu/~mckeeman/references/DifferentialTestingForSoftware.pdf https://www.cs.dartmouth.edu/~mckeeman/references/Differenti... Personally, I've applied (for the last 15 years) this kind of structured random testing to Common Lisp compilers. It's my contribution to the informal development process for SBCL. In this case, the comparison is between code compiled at different optimization settings, and with functions declared NOTINLINE, and with or without type declarations. Any source of diversity that preserves program meaning can be used to expose bugs. Many of the bug reports I've submitted to SBCL come from the random tester (and some other randomized testing techniques); you can get an idea of the kind of thing the tester finds by looking at them: https://bit.ly/2PLZDuK https://bit.ly/2PLZDuK

by lmkg 8y ago

Joky 8y ago

Even there, you need a fuzzer that can generate code that actually execute and does something you can observe. Otherwise the output of a C compiler (as in the binary itself) is expected to differ even between different versions of the same compiler.

pfdietz 8y ago

You're probably referring to Csmith, the random C generator from John Regehr's group at U. of Utah. https://embed.cs.utah.edu/csmith/ https://embed.cs.utah.edu/csmith/ Fuzzing C compilers this way is difficult, because you can't generate programs that have undefined behaviors, and C has so many of those. The complexity and challenge of their project was to not generate bogus programs while not throwing away too much diversity. The general technique is called differential testing. For compilers, it was pioneered by William McKeeman at DEC in the 1990s. He also addressed C compilers, with a more limited set of inputs than Csmith produces. https://www.cs.dartmouth.edu/~mckeeman/references/DifferentialTestingForSoftware.pdf https://www.cs.dartmouth.edu/~mckeeman/references/Differenti... Personally, I've applied (for the last 15 years) this kind of structured random testing to Common Lisp compilers. It's my contribution to the informal development process for SBCL. In this case, the comparison is between code compiled at different optimization settings, and with functions declared NOTINLINE, and with or without type declarations. Any source of diversity that preserves program meaning can be used to expose bugs. Many of the bug reports I've submitted to SBCL come from the random tester (and some other randomized testing techniques); you can get an idea of the kind of thing the tester finds by looking at them: https://bit.ly/2PLZDuK https://bit.ly/2PLZDuK