[fuzzing] Fuzzing tradeoffs - where previously described?

[Disco Jonny]

On 30/01/07, David Alexander Molnar <dmolnar at eecs.berkeley.edu> wrote:
>
> Hi everyone,

Hi,

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

In this example you just mention bugs, i take it you are only looking
for exploitable bugs? (if you are looking for any bugs then this is
email is more or less irrelevant - and I have loads of links about
cost analysis of automating testing, how, where, when, why, etc. let
me know and I will pass them across.)

If you just want to find exploitable bugs then it will form a large
part of the equation.
Also you will need to look at how much information you will get and
how long it will take to
make the bug exploitable.  - This is where a lot of buffer length
checkers (some dubbed fuzzers) shine. *if* they find a bug it is
generally quite easy to exploit it. but the % of bugs found is low.

If however you are just changing random bytes in a file then the
number of bugs you will find will be high, however it could take a
long time to get a working exploit for it - or even just to know it is
exploitable. (it may not... but generally it is.)

you would need to come up with a ranking system for different
techniques, and also for exploitability of bugs. - heh, I can imagine
it kinda being like top trumps...

I have not found such a system yet, it all seems quite arbitrary, with
different people wanting to put in different amounts of effort - and
also needing to put in different levels of effort.  It can get to the
point where it would just be easier to reverse that dll, or whatever
making fuzzing moot.

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

Finding only one class of bug is quite wasteful of resources and will
drive the costs up of any approach (unless you use your fuzzers to
find other bugs too, that really drives the cost down), except the
most random - but the most random have the highest cost in terms of
work needed after you have found the bug.

> changes over time
> on a given code base, usually going down as the easy bugs are found.

So you would need to add "exposure to test" as variable in the equation.

> So I find this helpful for thinking about what has to happen before a "smart"
> fuzzer is justified.

When the amount of effort that you have to put into post finding a bug
- to determine if it is exploitable/risk outweighs the time and effort
put into developing a fuzzer that will make that work easier... does
that make sense?

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

cost will always be directly proportional to time...

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

not that I have seen, but it would be cool to see someone attempt
something like this.  not really my sort of thing though.

let me know if you find anything.

cheers,

disco.