Re: [Xen-devel] [PATCH 14/14] fuzz/x86_emulate: Add an option to limit the number of instructions executed

[Wei Liu <wei.liu2@xxxxxxxxxx>]

On Fri, Sep 15, 2017 at 02:55:03PM +0100, George Dunlap wrote:
> On 09/15/2017 02:38 PM, Wei Liu wrote:
> > On Fri, Aug 25, 2017 at 05:43:43PM +0100, George Dunlap wrote:
> >> AFL considers a testcase to be a useful addition not only if there are
> >> tuples exercised by that testcase which were not exercised otherwise,
> >> but also if the *number* of times an individual tuple is exercised
> >> changes significantly; in particular, if the number of the highes bit
> >> changes (i.e., if it is run 1, 2-3, 4-7, 8-15, &c).
> >>
> >> Unfortunately, one simple way to increase these stats it to execute
> >> the same (or similar) instructions multiple times.  Such long
> >> testcases take exponentially longer to fuzz: the fuzzer spends more
> >> time flipping bits looking for meaningful changes, and each execution
> >> takes longer because it is doing more things.  So long paths which add
> >> nothing to the actual code coverage but effectively "distract" the
> >> fuzzer, making it less effective.
> >>
> >> Experiments have shown that not allowing infinite number of
> >> instruction retries for the old (non-compact) format does indeed speed
> >> up and increase code coverage.  However, it has also shown that on the
> >> new, more compact format, having no instruction limit causes the highest
> >> throughput in code coverage.
> >>
> >> So leave the option in, but have it default to 0 (no limit).
> > 
> > How does limiting the number of loops help afl produce better input?
> > Wouldn't afl still try to flip bits beyond the limit (say, the >=n+1
> > instructions when the limit is n)? I assume it will give up at some
> > point, but when?
> 
> * Limiting the number of loops means longer testcases don't look
> different than shorter testcases
> 
> * If a testcase doesn't look different than existing testcases, then AFL
> will discard it rather than adding it to the queue
> 
> * Larger "queue" testcases exhibit a quadratic effect for search time:
> They are longer to fuzz (since they're bigger) and each testcase is
> longer to run.
> 
> * So limiting the number of loops causes the testcases in the queue to
> be shorter, which in turn decreases the time to fuzz and execute test
> cases in the queue, which causes higher throughput.
> 
> > I guess my point is having a limit but doesn't tell afl about it seems
> > a bit sub-optimal to me. I'm not quite sure if I understand correctly
> > how afl works though.
> 
> Well I think the key thing is to look at the graph.  Either 1) there's
> something wrong with my methodology, or 2) for the original layout,
> limiting the number of testcases helps improve AFL's performance.
> 

I was just curious how it got that behaviour, either way I don't think I
would care that much because they are all internal implementation
details which are subject to change at any time.

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
https://lists.xen.org/xen-devel