Re: [Xen-devel] [PATCH 11/14] fuzz/x86_emulate: Make input more compact

[George Dunlap <george.dunlap@xxxxxxxxxx>]

On 08/25/2017 05:43 PM, George Dunlap wrote:
> At the moment, AFL reckons that for any given input, 87% of it is
> completely irrelevant: that is, it can change it as much as it wants
> but have no impact on the result of the test; and yet it can't remove
> it.
> 
> This is largely because we interpret the blob handed to us as a large
> struct, including CR values, MSR values, segment registers, and a full
> cpu_user_regs.
> 
> Instead, modify our interpretation to have a "set state" stanza at the
> front.  Begin by reading a byte; if it is lower than a certain
> threshold, set some state according to what byte it is, and repeat.
> Continue until the byte is above a certain threshold.
> 
> This allows AFL to compact any given test case much smaller; to the
> point where now it reckons there is not a single byte of the test file
> which becomes irrelevant.  Testing have shown that this option both
> allows AFL to reach coverage much faster, and to have a total coverage
> higher than with the old format.
> 
> Make this an option (rather than a unilateral change) to enable
> side-by-side performance comparison of the old and new formats.
> 
> Signed-off-by: George Dunlap <george.dunlap@xxxxxxxxxx>
> ---
> I'll reply to this e-mail with a graph of some tests I ran.

Here are the results of my testing justifying the new defaults for
whether to use 'compact' state definition or not, and how many
instructions to execute.

'new-format' had --compact=1, 'old-format' was run with --compact=0.

no-limit was run with --instruction-limit=0, limit-1 with
--instruction-limit=1, and so on.

In each case I ran 4 parallel AFL instances on my workstation for 24
hours.

The attached graph shows the number of unique AFL 'tuples' touched
over time.  (See [1] for more information.)  Having the line be higher
overall at the end of the run (i.e., best branch coverage) is the
primary goal; having the line shift over to the left (quickest
discovery) is a secondary goal.  The two are related in the sense that
quicker discovery should allow more time to explore further search
space.

The combination that had both the quickest discovery and the highest
overall branch coverage was the new 'compact' format with no
instruction limit (the defaults set by this patch).

In the 'compact' format, limiting the number of instructions seemed
only to slow things down and reduce the final coverage amount
(although the final coverage for limit-1 did beat the final coverages
for other limits).

In the 'non-compact' format, having unlimited instructions seems very
much to slow down discovery; but it also increased the final coverage
count.

 -George

[1] http://lcamtuf.coredump.cx/afl/technical_details.txt

Attachment: afl-effectiveness-tuples.png
Description: PNG image

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