3 ms·

One thing that is rarely mentioned is that fuzzying finds crashes, but not wrong code - you still need an oracle (something that tells you whether the output is

by muro 8y ago

One thing that is rarely mentioned is that fuzzying finds crashes, but not wrong code - you still need an oracle (something that tells you whether the output is correct) and those can be very hard to write. An useful tool, sure, but not a silver bullet.

adrianN 8y ago
Fuzzing works best if you sprinkle assertions generously in your code. If you do algorithm heavy stuff, you can choose a certifying algorithm [1] for your problem. That makes it a lot easier to get the oracle that you need. [1] https://en.wikipedia.org/wiki/Certifying_algorithm https://en.wikipedia.org/wiki/Certifying_algorithm
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
dbcurtis 8y ago
OK, that's fair. But one interesting case in that space is where the production code is highly optimized to be performant at the expense of simplicity. Writing an easy-to-understand but stupid-slow oracle is often a worthwhile strategy.
gnulinux 8y ago
In my side-projects I use simpler solutions as oracles to more complex solutions if I'm fuzzing. E.g. if I implemented some sophisticated `fac` implementation with secret sauce and mathematical yada yada, I use `def fac(n): return 1 if n==0 else n * fac(n-1)` as oracle, which works but is slow. I never used something like this for work, so I don't know what's the industry standard way to write an oracle, but this works fairly well. Another examples: I implemented polynomial multiplication with FFT and then tested it with canonical O(N^2) algorithm. I implemented Strassen algorithm, tested it with canonical O(N^3) algorithm. You can even have multiple levels of oracles: If canonical polynomial mul is too slow, use FFT PM to test a more sophisticated polynomial multiplication algorithm. In college, in my OS class my professor said something like in the space missions algorithms were implemented bunch of times by bunch of different teams and then in runtime they voted on output. You can do something like this to orchestrate an oracle too. Implement the same function 5 times, they vote on an output, their agreed upon output is the oracle's output and then now use this to test your real function. It goes without saying, if the problem is NP, then you can build a function that tests the output. Of course, now you need to test this function...
kqr 8y ago
Besides what the others have said, 1. Wrong code doesn't necessarily crash on all inputs, but there's usually at least one input that makes it crash, so it's not a terrible heuristic. 2. Writing oracles along the line of "the output should not be negative" , or "the output should contain this value" , or "this string should only contain printable ascii" gets you much closer for very cheap.

by muro 8y ago

adrianN 8y ago

Fuzzing works best if you sprinkle assertions generously in your code. If you do algorithm heavy stuff, you can choose a certifying algorithm [1] for your problem. That makes it a lot easier to get the oracle that you need. [1] https://en.wikipedia.org/wiki/Certifying_algorithm https://en.wikipedia.org/wiki/Certifying_algorithm

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

dbcurtis 8y ago

OK, that's fair. But one interesting case in that space is where the production code is highly optimized to be performant at the expense of simplicity. Writing an easy-to-understand but stupid-slow oracle is often a worthwhile strategy.

gnulinux 8y ago

In my side-projects I use simpler solutions as oracles to more complex solutions if I'm fuzzing. E.g. if I implemented some sophisticated `fac` implementation with secret sauce and mathematical yada yada, I use `def fac(n): return 1 if n==0 else n * fac(n-1)` as oracle, which works but is slow. I never used something like this for work, so I don't know what's the industry standard way to write an oracle, but this works fairly well. Another examples: I implemented polynomial multiplication with FFT and then tested it with canonical O(N^2) algorithm. I implemented Strassen algorithm, tested it with canonical O(N^3) algorithm. You can even have multiple levels of oracles: If canonical polynomial mul is too slow, use FFT PM to test a more sophisticated polynomial multiplication algorithm. In college, in my OS class my professor said something like in the space missions algorithms were implemented bunch of times by bunch of different teams and then in runtime they voted on output. You can do something like this to orchestrate an oracle too. Implement the same function 5 times, they vote on an output, their agreed upon output is the oracle's output and then now use this to test your real function. It goes without saying, if the problem is NP, then you can build a function that tests the output. Of course, now you need to test this function...

kqr 8y ago

Besides what the others have said, 1. Wrong code doesn't necessarily crash on all inputs, but there's usually at least one input that makes it crash, so it's not a terrible heuristic. 2. Writing oracles along the line of "the output should not be negative" , or "the output should contain this value" , or "this string should only contain printable ascii" gets you much closer for very cheap.