On the Effectiveness of Mutational Grammar Fuzzing
Mutational grammar fuzzing, a technique that uses predefined grammars to guide sample mutation while preserving structural integrity, faces significant challenges that can hinder bug discovery despite its proven effectiveness. While the approach ensures generated samples adhere to structural rules, leading to the discovery of complex issues in areas like XSLT implementations and JIT engines, its reliance on coverage as a primary metric for progress can be misleading.
A key flaw identified is that increased code coverage does not necessarily equate to finding more bugs. This is particularly problematic for targets like programming languages where bugs often depend on specific sequences of function calls or the use of one function's output as another's input. For instance, a bug in libxslt requires the `document()` and `generate-id()` XPath functions to be called in a specific order, with the output of `document()` feeding into `generate-id()`. A standard coverage-guided mutational fuzzer might generate separate samples containing each function, or even a single sample with both functions operating on independent data. While the combined coverage of these samples might match that of a bug-triggering sample, the necessary functional chaining is not achieved, and the fuzzer receives no feedback that it is progressing towards the bug. This issue is exacerbated when more than two function calls are required in sequence, making bug discovery increasingly improbable and suggesting that generative fuzzing without coverage feedback might even be more effective in such scenarios. While coverage feedback is still beneficial in many cases, this limitation highlights the need for more sophisticated coverage metrics, such as dataflow coverage, which are not yet widely implemented.
Another significant drawback is the tendency for mutational grammar fuzzing to produce corpora with low diversity. Because mutational fuzzing greedily saves samples that achieve new coverage, even if only a small portion of the original sample was mutated, the resulting corpus can contain many highly similar samples. This lack of diversity can slow down the overall fuzzing process. While fuzzers can be configured to generate samples from scratch, this approach is less likely to discover new coverage compared to localized mutations, especially later in a fuzzing session. Strategies to combat this, such as minimizing samples to only include the parts that triggered new coverage, have also proven suboptimal, as retaining some of the original sample structure can be beneficial.
These issues suggest potential benefits in combining generative and mutational fuzzing techniques. Generative fuzzing typically offers greater sample diversity but can produce a high volume of samples that trigger errors without necessarily finding deeper bugs. Coverage, despite its limitations, remains a valuable signal for bug discovery.
To address these challenges, a technique involving delayed synchronization of fuzzing workers has been employed. In a distributed fuzzing setup, individual workers can initially operate with independent corpora. Periodically, these workers can exchange sample sets, allowing each to acquire samples that cover areas it has missed. For single-machine fuzzing, a similar approach can be implemented by running a worker with an empty corpus for a set duration, then synchronizing it with a fuzzing server to obtain missing coverage and corresponding samples, while also uploading any unique coverage discovered by the worker.
