On the Effectiveness of Mutational Grammar Fuzzing

Mutational grammar fuzzing is a fuzzing technique in which the fuzzer uses a predefined grammar that describes the structure of the samples. When a sample gets mutated, the mutations happen in such a way that any resulting samples still adhere to the grammar rules, thus the structure of the samples gets maintained by the mutation process. In case of coverage-guided grammar fuzzing, if the resulting sample (after the mutation) triggers previously unseen code coverage, this sample is saved to the sample corpus and used as a basis for future mutations. This technique has proven capable of finding complex issues and I have used it successfully in the past, including to find issues in XSLT implementations in web browsers and even JIT engine bugs . However, despite the approach being effective, it is not without its flaws which, for a casual fuzzer user, might not be obvious. In this blogpost I will introduce what I perceive to be the flaws of the mutational coverage-guided grammar fuzzing approach. I will also describe a very simple but effective technique I use in my fuzzing runs to counter these flaws. Please note that while this blogpost focuses on grammar fuzzing, the issues discussed here are not limited to grammar fuzzing as they also affect other structure-aware fuzzing techniques to various degrees. This research is based on the grammar fuzzing implementation in my Jackalope fuzzer , but the issues are not implementation specific. Issue #1: More coverage does not mean more bugs The fact that coverage is not a great measure for finding bugs is well known and affects coverage-guided fuzzing in general, not just grammar fuzzing. However this tends to be more problematic for the types of targets where structure-aware fuzzing (including grammar fuzzing) is typically used, such as in language fuzzing. Let’s demonstrate this on an example: In language fuzzing, bugs often require functions to be called in a certain order or that a result of one function is used as an input to another function. To trigger a recent bug in libxslt two XPath functions need to be called, the document() function and the generate-id() function, where the result of the document() function is used as an input to generate-id() function. There are other requirements to trigger the bug, but for now let’s focus on this requirement. Here’s a somewhat minimal sample required to trigger the bug: ?xml version="1.0"? xsl:stylesheet xml:base= "#" version= "1.0" xmlns:xsl= "http://www.w3.org/1999/XSL/Transform" xsl:template match= "/" xsl:value-of select= "generate-id(document('')/xsl:stylesheet/xsl:template/xsl:message)" / xsl:message terminate= "no" /xsl:message /xsl:template /xsl:stylesheet With the most relevant part for this discussion being the following element and the XPath expression in the select attribute: xsl:value-of select= "generate-id(document('')/xsl:stylesheet/xsl:template/xsl:message)" / If you run a mutational, coverage guided fuzzer capable of generating XSLT stylesh