Trimmed data returned by custom mutator is larger than original data

[h1994st]

Error message:

[-] PROGRAM ABORT : Trimmed data returned by custom mutator is larger than original data
         Location : trim_case_custom(), src/afl-fuzz-mutators.c:287

The trimming strategies in the grammar mutator aim at reducing the tree size (i.e., the total number of non-terminal nodes). However, this does not guarantee the corresponding string is relatively small. For example, in JSON:

• An input buffer is "\r-10", which is 4 bytes and has 16 non-terminal nodes.
• The output trimmed buffer is "false", which is 5 bytes and has 6 non-terminal nodes.

Potential solution: we can allow the execution of the target, even if the trimmed data returned by the custom mutator is larger than the original data. This moves the responsibility of checking the trimming "size" to the custom mutator instead of the fuzzer.

(Need to think more on the solution)

[vanhauser-thc]

hmm I think ... yes and no... trimming means shortening the input, and yes with objects a smaller/simpler object might maybe be longer in binary. however I rather think that objects should only be removed when being trimmed, not changing it contents. And removing objects/subobjects should never make them larger (I think) however they could result in the same binary size. or what do you think? and @andreafioraldi ?

[vanhauser-thc]

I am not an expert in grammar (I only know basic stuff), hence I want to avoid making the fuzzer bad by my limited knowledge :)

[andreafioraldi]

I agree with @h1994st

[andreafioraldi]

Trimming is to make the input faster, if changing a terminal content does it it should be allowed.

[vanhauser-thc]

trimming is not to make the input faster but smaller. to have the smallest possible input that still triggers the same path. the trimming function does not check the timing at all, only if the path is the same.

so for a grammar I think this translate to either remove objects (or whatever you call this in grammar-speak ;) ) or simply it.

[h1994st]

@vanhauser-thc

hmm I think ... yes and no... trimming means shortening the input, and yes with objects a smaller/simpler object might maybe be longer in binary. however I rather think that objects should only be removed when being trimmed, not changing it contents.

The issue I met comes from the subtree trimming in Nautilus. In summary, this trimming strategy replaces a tree node and its subtree with the smallest possible subtree at this position. The root node of the original subtree and the replaced subtree have the same type, but they may represent different contents (i.e., binary buffer).

And removing objects/subobjects should never make them larger (I think) however they could result in the same binary size. or what do you think?

The normal fuzzer like AFL++ has a different definition of the "size" from the grammar mutator. The trimming functions in the grammar mutator do remove objects (i.e., tree nodes), but do not guarantee a smaller binary size.

I may submit a pull request to AFL++ to allow the custom mutator to generate the trimmed data that is larger than the original data. What do you think? : )

[vanhauser-thc]

I may submit a pull request to AFL++ to allow the custom mutator to generate the trimmed data that is larger than the original data. What do you think? : )

if that makes the grammar fuzzer better then yes. the question is however how ... I think it is easier if just the check + FATAL is removed rather than doing complex stuff in either the mutator or afl-fuzz.

[h1994st]

Just submitted a pull request (merged).

Simply replace the FATAL with WARN so that the custom mutator can keep running even if generating larger trimmed data.