Re: [Xen-devel] [PATCH v3 09/12] fuzz/x86_emulate: Make input more compact

[Andrew Cooper <andrew.cooper3@xxxxxxxxxx>]

On 10/10/17 18:13, George Dunlap wrote:
> On 10/10/2017 06:11 PM, Andrew Cooper wrote:
>> On 10/10/17 18:01, George Dunlap wrote:
>>> On 10/10/2017 05:59 PM, Andrew Cooper wrote:
>>>> On 10/10/17 17:20, 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 16-bit value; 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 am still of the opinion that this is a waste of effort, which would be
>>>> better spent actually removing the irrelevant state in the first place;
>>>> not building an obfuscation algorithm.
>>>>
>>>> I'm not going to nack the patch because that is probably over the top,
>>>> but I'm not in favour if this change going in.
>>> Did you look at the evidence I presented, demonstrating that this
>>> significantly increases the effectiveness of AFL?
>> I can easily believe that you've found an obfucation algorithm which
>> does better than the current state layout.
>>
>> I do not believe that any amount of obfuscation will be better than
>> actually fixing the root cause of the problem; that the current state
>> really is mostly irrelevant, and can easily be shrunk.
> Right; well I've already explained why I don't think "obfuscation" is
> the right term.

How else would describe it?  You are purposefully hiding the structure
of the data by doing conditional initialisation based on earlier values.

> For the time being, we have something which improves
> efficiency;

How much of this measured efficiently is actually ALF finding paths
around setup_state() rather than finding new paths in the emulator
itself?  I can't think of a test which would isolate this properly.

> let's check it in now, and in the future if you or someone
> else finds a way to fix it "properly" we can do that.

I wouldn't really mind so much if this change didn't make it harder to
fix the root cause.  As it is, your prerequisite patch prohibits any
ability to overlay a minimal structure over the fuzzing corpus.

~Andrew

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