[fuzzing] Fuzzing tradeoffs - where previously described?

[David Alexander Molnar]

Hi everyone,

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...

Thanks,
-David Molnar