[fuzzing] Fuzzing tradeoffs - where previously described?

[Jared DeMott]

>
>> 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.
>
>
>   
Great conversation guys.  No there really hasn't been much formal
fuzzing work, of this sort, that I know of.  If Ari and I find time, we
intend to write a book on Fuzzing this year.  Could be out as soon as
October of this year ... assuming we get out butts in gear! :)

I really like the attempts to formulate the bug find process.  However,
as we seen in this post it's very difficult because of the many factors
involved.  For example, not only does the probability of finding a bug
go down over time as the "low hanging fruits" are weeded out, but it
also makes a difference who writes the software.  For example, jimbob's
ftp server is arguably more likely to have bugs that msftpsvc even if
it's been around 10 years longer.  But of course I would have no real
proof of this.  In fact, proving the absence of bugs is darn near
impossible as far as I'm concerned.  We can only prove that we've found one.

As far as the question: which fuzzer should I create, a smart or dumb
fuzzer?  The obvious answer to me is that we should create the fuzzer
which we believe is most likely to yield the most bugs of any type
(especially if we're fuzzing the attack surface).  However, the point
that Disco brings up is valid and very interesting.  It does seem that
as randomness in a tool increase we tend to find more null ptrs and the
like.  It's often difficult to exploit such bugs, so if we know
beforehand that we will not have the time, or the expertise, to
determine the validity of such bugs, perhaps we'd be better off limiting
the tool to other attack types such as just long buffers or something. 
To some extent this could be true, but the argument breaks down at a
coupe points:  First of all smart/dumb is a usually measure of protocol
knowledge (does the fuzzer know to first hash the data, and attach a
proper length before sending it to the target).  So for particularly
complex protocols a fuzzer with no protocol knowledge (or no ability to
learn protocol knowledge) will probably achieve low code coverage, and
will therefore find very few bugs.  Also, we can't really predict which
fuzzing heuristics would lead to "tricky" (null pts, etc.) bugs.  Long
buffers could just as easily find null ptrs.  In fact, for mature code
bases the two bugs we expect to find are, null ptrs and heap overflows. 
I'll argue that stack overflows are not likely to be in mature code
bases.  Thus, a better metric for fuzzer effectiveness is coverage of
the attack surface.  This of course is still incomplete because just
because you've covered code does not mean you've covered it correctly. 
But we do know that if we have not covered it, we have certainly not
looked for bugs.

I like another thing Disco said. ("It can get to the point where it
would just be easier to reverse that dll, or whatever making fuzzing
moot.")  It can indeed get to this point.  But again a couple things to
add.  First of all, the method used to find bugs will vary from person
to person.  For example Sinan from Immunity only likes RE because he
believes it finds "deep sea fish" that wide fuzzing nets can't find.  He
also believes the shelf life of such bugs will be better than those
found via techniques that a growing number of people possess.  There is
something to this depending on who your work for.  If you work for a
software company you want to quickly find the most bugs possible, and
fix 'em fast.  If you're a hacker, perhaps you'd like to find just one
"very tricky" bug that will stay in the wild for a long time.  So it
seems that fuzzing will turn up more bugs/code base that REing, but in
general perhaps not as "good" a bug.  This of course isn't true all the
time.  If one goes through the trouble of writing a "good" fuzzer that
probes deep into the code base and finds a few gems...  But which will
cost more, writing a really good fuzzing or doing RE?  (Disco was right
again here, cost is measured in time or man hours)  I'm guessing it
depends on an individuals skill set to some extent.  Assuming one could
do either equally well, it probably depends on the target.  Assuming the
target was well suited to either approach ... I'm not sure?

An interesting tide bit: it seems that hacking organizations now define
three fairly distinct roles.  One person to write and use fuzzing tools,
one person to do REing, and a third person to prove the exploitability
of the first two peoples results.  This shows the difficulty of doing
such work.  For software companys doing testing (Disco jump in here) I'm
guessing they also have teams of testers filling various roles.

Blessings,
Jared

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.whitestar.linuxbox.org/pipermail/fuzzing/attachments/20070130/28de9b6a/attachment.htm