[fuzzing] Fuzzing tradeoffs - where previously described?
David Alexander Molnar
dmolnar at EECS.berkeley.EDU
Tue Jan 30 00:11:07 CST 2007
I have been thinking about tradeoffs between "smarter" fuzz tools that
take some time per trial but try to increase the chance that a test case
exhibits a bug over less smart tools, and "dumber" fuzzing that is very
fast per trial but doesn't do anything special. An equation that seems to
capture some of the tradeoffs is the following:
Expected # bugs = #trials/time * time * Pr[Bug per trial]
where this entire thing is conditioned on a certain type of bug we'd like
to find and on a certain code base under test. Now, we aren't going to be
able to estimate Pr[Bug per trial] precisely, but we can use this to say
things like "if fuzzer A has 6 trials per time period and fuzzer B has 3
trials per time period, then B had better be twice as likely to find bugs
than A." In practice, of course, the Pr[Bug per trial] changes over time
on a given code base, usually going down as the easy bugs are found. So I
find this helpful for thinking about what has to happen before a "smart"
fuzzer is justified.
We can also consider a variant that looks at cost per bug, since you could
use a farm full of VM images or something to drive the #trials/time as
high as you like. Maybe other variants are possible, but this is the idea.
This is all pretty obvious and straightforward, so I bet it's been written
down somewhere before. Does anyone know where? My apologies if it's a
classic thing that I should know already...
More information about the fuzzing