And for, a regex engine, coming up with an oracle shouldn’t be hard, as they typically already come with multiple specialized implementations under a single facade, and the implementations can be cross-checked against each other.
That's differential fuzzing, which isn't quite the same as having an oracle. It's possible to have the same bug in two implementations. Differential fuzzing is also useful, and is often easier (especially for things like regexes where there are many implementations lying around), though when it finds an issue it leaves you with the additional step of figuring out which implementation is wrong.
Mostly I point this out because it's good to be aware of both things. Some problems really do have oracles (e.g. factoring a number).
We always called this a "differential pseudo-oracle" just to differentiate (heh), but interestingly the academic testing community accepts the phrase "differential oracle" to refer to this incomplete oracle.
It's possible to have the same bug in two implementations.
Worth noting that for nontrivial programs this is quite rare, to the point of negligible, unless they come from the same flawed specification.
Worth noting that for nontrivial programs this is quite rare, to the point of negligible, unless they come from the same flawed specification.
FWIW I have run into this several times fuzzing JS parsers. The JS spec has its flaws, but not in ways relevant to these bugs. It's just that the spec only gives you a grammar and you have to implement your own parser, and there's some pitfalls with recursive descent parsers for the JS grammar around quirks like async (x, y) being a function call.
Fortunately there's >> 2 JS parsers so usually someone has done it correctly.
Yes, that's why I added "nontrivial". The NVP stuff was mostly concluding that their evaluated population (students) tended to make the same classes of error when implementing (what I recall being) some relatively trivial and highly-specified programs. When implementations diverge (e.g., two implementations of a video decoder, one hardware-accelerated, the other not), you tend not to make the same mistakes because the designs are fundamentally different.
Hm, to specify even further: for the parts where the actual program design diverges, you tend not to see the same bugs. The example from ~bakkot is a bug emerging from similar designs.
It's not that it's guaranteed to have no bugs, just that it only has to check the solution rather than find it, which is (in this case and many others) a much easier problem to solve, so it's easier to have confidence in the oracle's correctness.
I believe the typical approach is that you generate your test case by first picking the prime factors, and then multiplying them together to get your input to the factorization algorithm. Then you check that the result is what you started with.
though when it finds an issue it leaves you with the additional step of figuring out which implementation is wrong.
If you have a weak quorum (e.g. 2 vs 1), you have a good indication even if it's not a proof of anything. If you have a strong quorum (e.g. 6 vs 1), it's often the case that even if everyone else is wrong, the wrong answer might be the right answer in terms of compatibility and expectations, perhaps as a configurable option, and at the very least it's something to be aware of and document for your users.
I think the real moral of the story is that you should always test in a variety of ways :P
Always just bad when people solely follow TDD unit testing dogma, or solely doing integration tests, or solely fuzzing, or solely property testing, or solely testing against known-good (or at least differently-bad) implementations, or whatever. I don't think I've once written nontrivial software that didn't have at least one notable bug caught by every distinct paradigm of testing I implemented (regression testing included too, because bugs love recurring with future changes).
"whenever you have a pest that dodged your fuzzers, your first order of business is to treat this event as a bug in the fuzzer, and change it so that it can find this and related bugs" -- agreed; in practice my typical experience is to mostly / only find bugs in areas the fuzzer straightforwardly didn't cover (as in, not as a result of needing tricky inputs to trigger some behavior, but as a result of not doing something trivial like setting a flag to trigger the behavior.)
Separately I think the trouble with the name "fuzzer" is that people came to associate it with something taking an entire program as a black box and passing random inputs to it, or with sophisticated libraries for random testing, where the easiest and most effective thing is typically to write your own "white box" randomizer [written by someone with knowledge of implementation internals and thus a good idea of what might trip the implementation] against an internal API [rather than the external communication protocol of the full program] entirely on your own [no use of fancy libraries].
The most frustrating thing about this saga (I am the source of the quote here, BTW) is that I proposed and developed differential fuzzing support for rust/regex, but it was never stable enough to be merged. Maybe I should push for this again.
I also did a bit of a replication study on my own AST-derivation based fuzzers there, and there's seemingly little advantage to using mutation (as compared to random generation) due to the havoc paradox. Not a good sign that my fuzzers are exploring the program here effectively.
bakkot | 23 hours ago
Good article! Bit of pedantry:
That's differential fuzzing, which isn't quite the same as having an oracle. It's possible to have the same bug in two implementations. Differential fuzzing is also useful, and is often easier (especially for things like regexes where there are many implementations lying around), though when it finds an issue it leaves you with the additional step of figuring out which implementation is wrong.
Mostly I point this out because it's good to be aware of both things. Some problems really do have oracles (e.g. factoring a number).
addison | 10 hours ago
We always called this a "differential pseudo-oracle" just to differentiate (heh), but interestingly the academic testing community accepts the phrase "differential oracle" to refer to this incomplete oracle.
Worth noting that for nontrivial programs this is quite rare, to the point of negligible, unless they come from the same flawed specification.
bakkot | 6 hours ago
FWIW I have run into this several times fuzzing JS parsers. The JS spec has its flaws, but not in ways relevant to these bugs. It's just that the spec only gives you a grammar and you have to implement your own parser, and there's some pitfalls with recursive descent parsers for the JS grammar around quirks like
async (x, y)being a function call.Fortunately there's >> 2 JS parsers so usually someone has done it correctly.
addison | 5 hours ago
Oh interesting! I think I would consider this somewhat of a "common flawed spec" but definitely a nice counterexample.
cceckman | 2 hours ago
I understand Knight and Leveson is a typical citation against this claim. (Sorry, I don't have a PDF of it handy)
addison | an hour ago
Yes, that's why I added "nontrivial". The NVP stuff was mostly concluding that their evaluated population (students) tended to make the same classes of error when implementing (what I recall being) some relatively trivial and highly-specified programs. When implementations diverge (e.g., two implementations of a video decoder, one hardware-accelerated, the other not), you tend not to make the same mistakes because the designs are fundamentally different.
addison | an hour ago
Hm, to specify even further: for the parts where the actual program design diverges, you tend not to see the same bugs. The example from ~bakkot is a bug emerging from similar designs.
amw-zero | 20 hours ago
What’s the oracle for factoring a number that’s guaranteed to have no bugs?
bakkot | 18 hours ago
It's not that it's guaranteed to have no bugs, just that it only has to check the solution rather than find it, which is (in this case and many others) a much easier problem to solve, so it's easier to have confidence in the oracle's correctness.
drmorr | 18 hours ago
I believe the typical approach is that you generate your test case by first picking the prime factors, and then multiplying them together to get your input to the factorization algorithm. Then you check that the result is what you started with.
pervognsen | 14 hours ago
If you have a weak quorum (e.g. 2 vs 1), you have a good indication even if it's not a proof of anything. If you have a strong quorum (e.g. 6 vs 1), it's often the case that even if everyone else is wrong, the wrong answer might be the right answer in terms of compatibility and expectations, perhaps as a configurable option, and at the very least it's something to be aware of and document for your users.
nytpu | a day ago
I think the real moral of the story is that you should always test in a variety of ways :P
Always just bad when people solely follow TDD unit testing dogma, or solely doing integration tests, or solely fuzzing, or solely property testing, or solely testing against known-good (or at least differently-bad) implementations, or whatever. I don't think I've once written nontrivial software that didn't have at least one notable bug caught by every distinct paradigm of testing I implemented (regression testing included too, because bugs love recurring with future changes).
yosefk | 11 hours ago
"whenever you have a pest that dodged your fuzzers, your first order of business is to treat this event as a bug in the fuzzer, and change it so that it can find this and related bugs" -- agreed; in practice my typical experience is to mostly / only find bugs in areas the fuzzer straightforwardly didn't cover (as in, not as a result of needing tricky inputs to trigger some behavior, but as a result of not doing something trivial like setting a flag to trigger the behavior.)
Separately I think the trouble with the name "fuzzer" is that people came to associate it with something taking an entire program as a black box and passing random inputs to it, or with sophisticated libraries for random testing, where the easiest and most effective thing is typically to write your own "white box" randomizer [written by someone with knowledge of implementation internals and thus a good idea of what might trip the implementation] against an internal API [rather than the external communication protocol of the full program] entirely on your own [no use of fancy libraries].
addison | 10 hours ago
The most frustrating thing about this saga (I am the source of the quote here, BTW) is that I proposed and developed differential fuzzing support for rust/regex, but it was never stable enough to be merged. Maybe I should push for this again.
I also did a bit of a replication study on my own AST-derivation based fuzzers there, and there's seemingly little advantage to using mutation (as compared to random generation) due to the havoc paradox. Not a good sign that my fuzzers are exploring the program here effectively.