Wasteful rebuilding of non-terminal trees

[trust1995]

tree_get_non_terminal_nodes() always recalculates the non_terminal_node_list, and is called for every new sample at afl_custom_fuzz_count(). Those elements are popped at afl_custom_fuzz() before being passed to the mutator. Instead, we could keep the non-terminal list in the serialized tree format and update it per mutation. It will not be recalculated for every sample.

[h1994st]

Hi @trust1995,

Thanks for your comment!

Not quite sure why tree_get_non_terminal_nodes() in afl_custom_fuzz_count() is wasteful. I agree that non_terminal_node_list is fixed for every new test case.

Does the current implementation hurt the performance of the grammar mutator badly? Actually, as you said, tree_get_non_terminal_nodes() is only called once for every new test case. No matter how you generate the non-terminal node list, we need to calculate it once for every new test case.

[trust1995]

Hi there,

I didn't perform benchmark tests so wouldn't know what exactly the performance is. The way I see it, this node list doesn't have to be "calculated" per test case, it can be loaded as part of the serialized tree in a memcpy() style copy which is much much faster. The idea is that each mutation step can easily update the non-terminal list in mutated_tree, but in fact that too takes O(n) time, so perhaps its not a big issue.

[h1994st]

I see. Thanks for your reply.

If you like, we welcome you to submit a PR for this :)

[trust1995]

Thanks, I will keep that in mind :)