Fuzzing Perl: A Tale of Two American Fuzzy Lops
1–10 of 19 posts
Re: Fuzzing Perl: A Tale of Two American Fuzzy Lops
#2The paper [1] on AFLFast is, IMO, a great example of where academia shines: carefully looking at how and why something works, developing some theory and a working model, and then using that to get a substantial improvement on the state of the art (and doing a nice evaluation to show that it really works).
Re: Fuzzing Perl: A Tale of Two American Fuzzy Lops
#3The paper [1] on AFLFast is, IMO, a great example of where academia shines: carefully looking at how and why something works, developing some theory and a working model, and then using that to get a substantial improvement on the state of the art (and doing a nice evaluation to show that it really works). [1] https://www.comp.nus.edu.sg/~mboehme/paper/CCS16.pdf
The abstract sounds like it. They said with no program analysis, though. I thought program analysis was good enough that it could probably auto-generate tests for every branch in a program, possibly in less time or with more assurance. W as I wrong or is this a parallel subfield?
Re: Fuzzing Perl: A Tale of Two American Fuzzy Lops
#4My understanding is that fuzz testing uses pseudo-random variation of the seed code; given a different seed to the PRNG, how common is it for the same fuzz test to identify different flaws?
Re: Fuzzing Perl: A Tale of Two American Fuzzy Lops
#5The paper [1] on AFLFast is, IMO, a great example of where academia shines: carefully looking at how and why something works, developing some theory and a working model, and then using that to get a substantial improvement on the state of the art (and doing a nice evaluation to show that it really works). [1] https://www.comp.nus.edu.sg/~mboehme/paper/CCS16.pdf
The abstract sounds like it. They said with no program analysis, though. I thought program analysis was good enough that it could probably auto-generate tests for every branch in a program, possibly in less time or with more assurance. W as I wrong or is this a parallel subfield?
The question of whether randomized testing or program analysis gives you more coverage of a program is a really interesting one. Böhme actually has an earlier paper that addresses this question: https://www.comp.nus.edu.sg/~mboehme/paper/FSE14.pdf
> We study the relative efficiencies of the random and systematic approaches to automated software testing. Using a simple but realistic set of assumptions, we propose a general model for software testing and define sampling strategies for random (R) and systematic (S₀) testing, where each sampling is associated with a sampling cost: 1 and c units of time, respectively. The two most important goals of software testing are: (i) achieving in minimal time a given degree of confidence x in a program's correctness and (ii) discovering a maximal number of errors within a given time bound n̂. For both (i) and (ii), we show that there exists a bound on c beyond which R performs better than S₀ on the average. Moreover for (i), this bound depends asymptotically only on x. We also show that the efficiency of R can be fitted to the exponential curve. Using these results we design a hybrid strategy H that starts with R and switches to S₀ when S₀ is expected to discover more errors per unit time. In our experiments we find that H performs similarly or better than the most efficient of both and that S₀ may need to be significantly faster than our bounds suggest to retain efficiency over R.
Also, for (say) C programs of moderate size, I believe current program analysis techniques do not achieve anything near 100% branch coverage. In the KLEE paper they manage to get ~90% on average for the GNU coreutils using concolic execution – which is really impressive! But the coreutils are tiny programs. For larger programs the cost of symbolic execution is high and random testing can often get you more bugs faster.
Re: Fuzzing Perl: A Tale of Two American Fuzzy Lops
#6My understanding is that fuzz testing uses pseudo-random variation of the seed code; given a different seed to the PRNG, how common is it for the same fuzz test to identify different flaws?
In my experience very rare. It's so rare I'd say it basically doesn't happen.
You'll get some fluctuation, a bug may come up half an hour earlier or not. But results tend to be pretty reproducible. If you find a bug with a specific test and tool in x hours then the next time you try for at least x+1 hours you'll find it again.
Re: Fuzzing Perl: A Tale of Two American Fuzzy Lops
#7My understanding is that fuzz testing uses pseudo-random variation of the seed code; given a different seed to the PRNG, how common is it for the same fuzz test to identify different flaws?
In my experience very rare. It's so rare I'd say it basically doesn't happen. You'll get some fluctuation, a bug may come up half an hour earlier or not. But results tend to be pretty reproducible. If you find a bug with a specific test and tool in x hours then the next time you try for at least x+1 hours you'll find it again.
I think that's right for just picking a different PRNG seed. When you start looking at modifying the search heuristics, mutation operators, or other parts of the "strategy", you definitely start finding different bugs, though.
Re: Fuzzing Perl: A Tale of Two American Fuzzy Lops
#8Earlier quoted context omitted.
In my experience very rare. It's so rare I'd say it basically doesn't happen. You'll get some fluctuation, a bug may come up half an hour earlier or not. But results tend to be pretty reproducible. If you find a bug with a specific test and tool in x hours then the next time you try for at least x+1 hours you'll find it again.
I think that's right for just picking a different PRNG seed. When you start looking at modifying the search heuristics, mutation operators, or other parts of the "strategy", you definitely start finding different bugs, though.
Yes, absolutely. Different strategies can lead to vastly different results, often it's subtle things.
Good example: There was a bug I found in openssl that Libfuzzer was unable to find. The Libfuzzer developer was quite interested in this and has now adopted new mutation strategies: https://github.com/google/sanitizers/issues/710
Re: Fuzzing Perl: A Tale of Two American Fuzzy Lops
#9In the first pass, 6 bugs were found and reported. 3 heap-use-after-free, 3 heap-buffer-overflow. Similar numbers in the second.
I'm so glad new programming languages are making strides which prevent this sort of thing outright. They don't prevent all bugs, but they sure prevent some of the most damaging ones.
Re: Fuzzing Perl: A Tale of Two American Fuzzy Lops
#10In the first pass, 6 bugs were found and reported. 3 heap-use-after-free, 3 heap-buffer-overflow. Similar numbers in the second. I'm so glad new programming languages are making strides which prevent this sort of thing outright. They don't prevent all bugs, but they sure prevent some of the most damaging ones.
This is Perl5, not Perl6.