[fuzzing] Fuzzing tradeoffs - where previously described?

Fri Feb 2 07:25:03 CST 2007

On 01/02/07, Ari Takanen <ari.takanen at codenomicon.com> wrote:
>
> Hello,
>
> On Thu, Feb 01, 2007 at 04:09:17PM +0000, Disco Jonny wrote:
> > >Note that because the input space is always infinite,
> >
> > pardon? no it isnt. it might be huge, phenomenally huge, but physics
> > stops it being infinite.
>
> Well, actually the input space is infinite. Protocols travel in a
> pipe, and there is nothing that says there is an end to them... Bits
> do not run out, or take space. You might think input space is finite,
> like the way Mr. Bill though we never need more than 640k of memory
> (well it was not him but lets blame it on him anyways).

This is very much like the vector vs. bitmap graphics debate.
If the input space are all the points on a line, the collection of those
points is infinite (bitmap) although the input space could also be defined
by an origin and a destination (vector). Now to test the correctness of the
program processing this input, what needs to be tested is the correctness at
the endpoints.
The problem with the vector approach is we don't know if the line we are
trying to describe (thus test) is in fact a line, we assume it is a line,
but one discontinuity will cause the endpoint-tests to be insufficient as
the discontinuity also needs to be tested, in fact, there are now 2 new
endpoints on the line and at least 1 on the discontinuity.
So how do we know what are the endpoints of the input space? Analysis of
1) Inputs: given large enough datasets and the right algorithm the different
endpoints could be found.
2) Program behaviour: asm tracing, return values: different inputs may yield
different results.

So imho you are both right.
To create better fuzzers we need better algorithms for analysing the inputs
and creating fuzz inputs. Some sort of xml library would be great:

e.g.
packet in xml:

<input>
  <head>
    <source type="int"  size="2">xx</source>
    <dest type="int"  size="2">yy</dest>
    ....
  </head>
  <payload type="text" size="512">
    blahblah
  </payload>
 </input>

then use xsl to create other packets. The fuzzing logic is described by the
xsl transformations.
Maybe I'll implement something like this next time I'm too bored, would be
kewl to test on odf and the like.

Regards,
Thomas

E.g. if a protocol specification says that:
>
> <protocol> = <data>
> <data> = 1..256 * <16bit-integer>
>
> How many tests would we need? Fuzzing that will still have infinite
> tests, provided it does not have any other limitations. Is 2^16+1 long
> enough stream to inject? Is 16GB too much to try? What about if we
> send even more?  Where should we stop? But as you said, it might not
> be sensible to go that far, but what if it will crash with one more
> additional byte of data? And one more? Why set limits like Mr Bill (or
> whoever) did when he did not know better?
>
> With some protocols, you can potentially measure the maximum size of
> input space. Just keep increasing the message size until the server
> side will refuse any more data and close the connection (it probably
> crashed in the process). But then, what if the flaw is due to a
> combination of two different packets? Or three? ...
>
> /Ari
> _______________________________________________
> fuzzing mailing list
> fuzzing at whitestar.linuxbox.org
> http://www.whitestar.linuxbox.org/mailman/listinfo/fuzzing
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.whitestar.linuxbox.org/pipermail/fuzzing/attachments/20070202/a254f3ba/attachment.htm 