Superion: Grammar-Aware Greybox Fuzzing
Junjie Wang, Bihuan Chen, Lei Wei, Yang Liu
I Introduction
Fuzzing or fuzz testing is an automated software testing technique to feed a large amount of invalid or unexpected test inputs to a target program in the hope of triggering unintended program behaviors, e.g., assertion failures, crashes, or hangs. Since its introduction in early 1990s , fuzzing has become one of the most effective techniques for finding bugs or vulnerabilities in real-world programs. It has been successfully applied to testing various applications, ranging from rendering engines and image processors to compilers and interpreters.
A fuzzer can be classified as generation-based (e.g., ) or mutation-based (e.g., ), depending on whether test inputs are generated by the knowledge of the input format or grammar or by modifying well-formed test inputs. A fuzzer can also be classified as whitebox (e.g., ), greybox (e.g., ) or blackbox (e.g., ), depending on the degree of leveraging a target program’s internal structure, which reflects the tradeoffs between effectiveness and efficiency. In this paper, we focus on mutation-based greybox fuzzing.
Coverage-Based Greybox Fuzzing. One of the most successful mutation-based greybox fuzzing techniques is coverage-based greybox fuzzing, which uses the coverage information of each executed test input to determine the test inputs that should be retained for further incremental fuzzing. AFL is a state-of-the-art coverage-based greybox fuzzer, which has discovered thousands of high-profile vulnerabilities. Thus, without the loss of generality, we consider AFL as the typical implementation of coverage-based greybox fuzzing.
As shown in Fig. 1, AFL takes the target program as an input, and works in two steps: instrumenting the target program and fuzzing the instrumented program. The instrumentation step injects code at branch points to capture branch (edge) coverage together with branch hit counts (which are bucketized to small powers of two). A test input is said to have new coverage if it either hits a new branch, or achieves a new hit count for an already-exercised branch. The fuzzing step can be broken down into five sub-steps. Specifically, a test input is first selected from a queue where the initial test inputs as well as the test inputs that have new coverage are stored. Then the test input is trimmed to the smallest size that does not change the measured behavior of the program, as the size of test inputs has a dramatic impact on the fuzzing efficiency. The trimmed test input is then mutated to generate new test inputs; and the program is executed with respect to each mutated test input. Finally, the queue is updated by adding those mutated test inputs to the queue if they achieve new coverage, while the mutated test inputs that achieve no new coverage are discarded. This fuzzing loop continues by selecting a new test input from the queue.
Challenges. The current coverage-based greybox fuzzers can effectively fuzz programs that process compact and unstructured inputs (e.g., images). However, some challenges arise when they are used to target programs that process structured inputs (e.g., XML and JavaScript) that often follow specific grammars. Such programs often process the inputs in stages, i.e., syntax parsing, semantic checking, and application execution .
On one hand, the trimming strategies (e.g., removal of chunks of data) in AFL are grammar-blind, and hence can easily violate the grammar or destroy the input structure. As a result, most test inputs in the queue cannot be effectively trimmed to keep them syntax-valid. This is especially the case when the target program can process a part of a test input (triggering coverage) but errors out on the remaining part. This will greatly affect the efficiency of AFL because it needs to spend more time on fuzzing the test inputs whose structures are destroyed, but only finds parsing errors and gets stuck at the syntax parsing stage, which heavily limits the capability of fuzzers in finding deep bugs.
On the other hand, the mutation strategies (e.g., bit flipping) in AFL are grammar-blind, and hence most of the mutated test inputs fail to pass syntax parsing and are rejected at an early stage of processing. As a result, it is difficult for AFL to achieve large-step mutations. For example, it is very difficult to obtain Content-Length: -1 from mutating Set-Cookie: FOO=BAR via small-step bit flipping mutations . Meanwhile, AFL needs to spend a large amount of time struggling with syntax correctness, while only finding parsing errors. Therefore, the effectiveness of AFL to find deep bugs is heavily limited for programs that process structured inputs.
The Proposed Approach. To address the challenges, we propose a new grammar-aware coverage-based greybox fuzzing approach for programs that process structured inputs. We also implement the proposed approach as an extension to AFL, named Superion Superion is an Autobot combiners in the cartoon The Transformers.. Our approach takes as inputs a target program and a grammar of the test inputs that is often publicly available. Based on the grammar, we parse each test input into an abstract syntax tree (AST). Using ASTs, we introduce a grammar-aware trimming strategy that can effectively trim test inputs while keeping the input structure valid. This is realized by iteratively removing each subtree in the AST of a test input and observing coverage differences. Moreover, we propose two grammar-aware mutation strategies that can quickly carry the fuzzing exploration beyond syntax parsing. We first enhance AFL’s dictionary-based mutation strategy by inserting/overwriting tokens in a grammar-aware manner, and then propose a tree-based mutation strategy that replaces one subtree in the AST of a test input with the subtree from itself or another test input in the queue.
To evaluate the effectiveness of Superion, we conducted experiments on one XML engine libplist and three JavaScript engines WebKit, Jerryscript and ChakraCore. We compared our approach with AFL with respect to the code coverage and bug-finding capability. The results have demonstrated that Superion can effectively improve the code coverage over AFL by 16.7% in line coverage and 8.8% in function coverage; and Superion can significantly improve the bug-finding capability over AFL by finding 31 new bugs (among which six were found by AFL). Among these bugs, 21 new vulnerabilities were discovered with 16 CVEs assigned; and we received 3.2K USD bug bounty rewards. Besides, we compared Superion with jsfunfuzz , which is a successful fuzzer specifically designed for JavaScript. However, it failed to find any new bugs. Moreover, we have demonstrated that our grammar-aware trimming strategy can effectively trim test inputs while keeping them syntax-valid; and our grammar-aware mutation strategies can effectively generate new test inputs that can trigger new coverage.
Contributions. The contributions of this work are:
We proposed a novel grammar-aware coverage-based greybox fuzzing approach for programs that process structured inputs, which complements existing coverage-based greybox fuzzers.
We implemented our approach and made it open-source https://github.com/zhunki/gramFuzz, and conducted experiments to demonstrate its effectiveness.
We found 31 new bugs, among which we found 21 new vulnerabilities with 16 CVEs assigned and received 3.2K USD bug bounty rewards.
II Our Approach
To address the challenges of coverage-based greybox fuzzing (Section I), we propose a novel grammar-aware coverage-based greybox fuzzing approach, which targets programs that process structured inputs. We implement the approach as an extension to AFL , named Superion. Fig. 2 introduces the workflow of Superion, and highlights the differences from AFL (see Fig. 1). In particular, a context-free grammar of the test inputs is needed, which is often publicly available (e.g., in ANTLR’s community ). We introduce a grammar-aware trimming strategy (Section II-A) and two grammar-aware mutation strategies (Section II-B) with the purpose of making AFL grammar-aware.
The built-in trimming strategy in AFL is grammar-blind, and treats a test input as chunks of data. Basically, it first divides the test input to be trimmed into chunks of bytes where is the length of the test inputs in bytes, and then tries to remove each chunk sequentially. If the coverage remains the same after the removal of a chunk, this chunk is trimmed. Note that starts at 16 and increments by a power of two up to 1024. This strategy is very effective for unstructured inputs. However, it cannot effectively prune structured inputs while keeping them syntax-valid, possibly making AFL stuck in the fuzzing exploration of syntax parsing without finding deep bugs.
Example. Fig. 3 gives an example of AFL’s built-in trimming on an XML test input with respect to libplist (an XML engine), where “l versio” and “dict /plis” are trimmed (highlighted by strikethrough). The trimmed test input is syntax-invalid, but has the same coverage with the original test input due to the gap between implementation of libplist and grammar specification. Hence, the trimmed test input is used for further fuzzing even though its grammar is destroyed by AFL’s built-in trimming.
To ensure the syntax-validity of trimmed test inputs, we propose a grammar-aware trimming strategy, whose procedure is given in Algorithm 1. It first parses the test input to be trimmed according to the grammar into an AST (Line 4). If any parsing errors occur (as ’s structure may be destroyed by mutations), then it uses AFL’s built-in trimming strategy rather than directly discarding it (Line 5–7); otherwise, it attempts to trim a subtree from (Line 8–9). If the coverage is different after is trimmed, then cannot be trimmed (Line 14–16), and it tries to trim next subtree; otherwise, is trimmed, and it re-parses the remaining test input (Line 11–13), and then repeats the procedure until no subtree can be trimmed (Line 17–18). Thus, we resort to AFL’s built-in trimming only when our tree-based trimming is not applicable. This is because sometimes invalidity is also useful.
Example. Fig. 4 shows an example of our trimming strategy on a JavaScript test input, where a complete try-catch statement (highlighted by strikethrough) is trimmed without introducing any coverage differences. However, it is almost impossible for AFL’s built-in trimming strategy to prune such a complete statement.
II-B Grammar-Aware Mutation Strategies
The default mutation strategies (e.g., bit flipping or token insertion) in AFL are too fine-grained and grammar-blind to keep the input structure following the underlying grammar. Therefore, we propose two grammar-aware mutation strategies to improve the mutation effectiveness on triggering new program behaviors.
Dictionary-based mutation was introduced to make up for the grammar-blind nature of AFL. The dictionary is referred as a list of basic syntax tokens (e.g., reserved keywords) which can be provided by users or automatically identified by AFL. Every token is inserted between every two bytes of the test input to be mutated, or written over every byte sequence of the same length of the token. Such mutations can generate syntax-valid test inputs but is inefficient as most of the generated inputs have destroyed structure.
Therefore, we propose the enhanced dictionary-based mutation as shown in Algorithm 2. This algorithm leverages the key fact that the tokens (e.g., variable names, function names, or reserved keywords) in a structured test input normally only consist of alphabets or digits. Hence, it first locates the token boundaries in a test input by iteratively checking whether the current and next byte are both alphabet or digit (Line 5–12). Then it inserts each token in the dictionary to each located boundary, which avoids the insertion between consecutive sequence of alphabets and digits and thus greatly decreases the number of token insertions (Line 13–16). Similarly, it writes each token in the dictionary over the content between every two located boundaries, which also greatly decreases the number of token overwrites. Such token insertions and overwrites not only maintains the structure of mutated test inputs but also decreases the number of mutated test inputs, hence greatly improving the effectiveness and efficiency of dictionary-based mutation.
Example. Fig. 5 illustrates the difference between the original and enhanced dictionary-based mutation. In the original one, 01 is not treated as a whole, and thus 1 can be overwritten by + and const can be inserted between 0 and 1, which destroys the structure without introducing any new coverage. In the enhanced one, 01 is identified as a whole, and hence the mutated test inputs in Fig. 5(a) will not be produced. Instead, it can generate the mutated test inputs in Fig. 5(b) more efficiently, which are taken from our experiments and both lead to new coverage.
II-B2 Tree-Based Mutation
Dictionary-based mutation is aware of the underlying grammar in an implicit way. To be explicitly aware of the grammar and thus producing syntax-valid test inputs, we utilize the grammar knowledge and design a tree-based mutation, which works at the level of ASTs. Different from the tokens used in dictionary-based mutation, AST actually models a test input as objects with named properties, and is designed to represent all the information about a test input. Thus, ASTs provide a suitable granularity for a fuzzer to mutate test inputs.
Algorithm 3 shows the procedure of our tree-based mutation. It takes as inputs a test input to be mutated, the grammar , and a test input that is randomly chosen from the queue. It first parses according to into an AST ; and if any parsing errors occur, is a syntax-invalid test input and we do not apply tree-based mutation to (Line 5–8). If no error occurs, it traverses , and stores each subtree in a set (Line 9–11). Then it parses into an AST , and stores each subtree of in if there is no parsing error (Line 12–17). Here serves as the content provider of mutation. Then, for each subtree in , it replaces with each of the subtree in to generate a new mutated test input (Line 18–23). Finally, it returns the set of mutated test inputs.
The size of this returned set can be the multiplication of the number of subtrees in and the number of subtrees in and , which could be very large. As an example, our tree-based mutation on and whose number of subtrees is respectively 100 and 500 will generate test inputs. This will add burden to the program execution step during fuzzing, making fuzzing less efficient. To relieve the burden, we design three heuristics to reduce the number of mutated test inputs. For clarity, we do not elaborate these heuristics in Algorithm 3, but only show where they are applied.
Heuristic 1: Restricting the size of test inputs. We limit the size of test inputs (i.e., and in Algorithm 3) as 10,000 bytes long (Line 5 and 12). Hence we do not apply tree-based mutation to if is more than 10,000 bytes long; and we do not use subtrees of as the content provider of mutation if is more than 10,000 bytes long. The reasons are that, a larger test input usually needs a larger number of mutations; more memory is required to store the AST of a larger test input; and a larger test input often has a slower execution speed.
Heuristic 2: Restricting the number of mutations. If there are more than 10,000 subtrees in and , we randomly select 10,000 from all subtrees in as the content provider of mutation (Line 18). Thus, we keep the number of mutations on each test input in the queue under 10,000 to make sure that each test input in the queue has the chance to get mutated.
Heuristic 3: Restricting the size of subtrees. We limit the size of subtrees (i.e., each subtree in in Algorithm 3) as 200 bytes long (Line 9 and 14). Thus we do not use the subtrees of and as the content provider of mutation if the subtree is more than 200 bytes long. Notice that 200 bytes are long enough to include complex statements.
The threshold values in these heuristics were empirically established as good ones.
Example. Fig. 6 shows an example of our tree-based mutation. The left-side is the AST of the test input to be mutated (i.e., in Algorithm 3), and the right-side is the AST of the test input that provides the content of mutation (i.e., in Algorithm 3). Here the subtree corresponding to the expression in is replaced with the subtree corresponding to the expression in , resulting in a new test input.
III Evaluation
We implemented Superion in 3,372 lines of C/C++ code by extending AFL . Particularly, given the grammar of test inputs, we adopted ANTLR 4 to generate the lexer and parser, and used ANTLR 4 C++ runtime to parse test inputs and realize our trimming and mutation strategies. Hence, our approach is general and easily adoptable for other structured test inputs.
To evaluate the effectiveness and generality of our approach, we selected two target languages and four target programs, and compared our approach with AFL with respect to the bug-finding capability and code coverage.
Target Languages. We chose XML and JavaScript as the target languages with different structure level. Their grammars are all publicly available in ANTLR’s community . In particular, XML is a widely-used markup language, which defines a set of rules for encoding documents. It has been widely used in a variety of applications. As shown in the second column of Table I, the XML grammar only contains eight symbols. Thus, XML can be considered to be weakly-structured. On the other hand, JavaScript is an interpreted programming language, which is employed by most websites and supported by all modern web browsers. The JavaScript grammar contains 98 symbols, and thus its structure level can be regarded as strong.
As indicated by the last column of Table I, we crawled 9,467 XML samples from the Internet, and 20,845 JavaScript samples from the test inputs of the two open-source JavaScript engines WebKit and Jerryscript. They were used as the initial test inputs (i.e., seeds) for fuzzing. As suggested by AFL, afl-cmin should be used to identify the set of functionally distinct seeds that exercise different code paths in the target program when a large amount of seeds are available. Therefore, we used afl-cmin on the samples, and identified 534 and 2,569 distinct XML and JavaScript samples as the seeds for fuzzing, as shown in the parentheses in the last column of Table I. Notice that, before fuzzing, we pre-processed the JavaScript samples by removing all the comments as comments, especially multi-line comments, account for a considerable percentage of waste of mutation.
Target Programs. We selected one open-source XML engine libplist and three open-source JavaScript engines WebKit, Jerryscript and ChakraCore as the programs for fuzzing. The first four columns of Table II list the program details, including the version, the number of lines of code, and the number of functions. Particularly, libplist is a small portable C library to handle Apple Property List format files in binary or XML. It is widely used on iOS and Mac OS. WebKit is a cross-platform web browser engine. It powers Safari, iBooks and App Store, and various Mac OS, iOS and Linux applications. Jerryscript is a lightweight JavaScript engine for Internet of Things, intended to run on a very constrained devices. ChakraCore is the core part of the Chakra Javascript engine that powers Microsoft Edge. We chose these programs because they are security-critical and widely-fuzzed. Thus, finding bugs in them are significant.
As shown in the fifth column of Table II, we used edge coverage for libplist and Jerryscript during fuzzing, but block coverage for others due to non-determinism (i.e., different executions of a test input lead to different coverage). Besides, we excluded the non-deterministic code in WebKit and ChakraCore from instrumentation, following the technique in kAFL .
At the time of writing, we have fuzzed these programs for about three months. For libplist and Jerryscript, we have completed more than 100 cycles of fuzzing. For WebKit and ChakraCore, due to their large size, we have not finished one cycle yet. Here a cycle means the fuzzer went over all the interesting test inputs (triggering new coverage) discovered so far, fuzzed them, and looped back to the very beginning.
Research Questions. Using the previous evaluation setup, we aim to answer the following five research questions.
RQ1: How is the bug-finding capability of Superion?
RQ2: How is the code coverage of Superion?
RQ3: How effective is our grammar-aware trimming?
RQ4: How effective is our grammar-aware mutation?
RQ5: What is the performance overhead of Superion?
We conducted all the experiments on machines with 28 Intel Xeon CPU E5-2697v3 cores and 64GB memory, running 64-bit Ubuntu 16.04 as the operating system.
III-B Discovered Bugs and Vulnerabilities (RQ1)
Table III lists the unique bugs discovered in the four programs by Superion. In libplist, we discovered 11 new bugs, from which we found 10 new vulnerabilities with CVE identifiers assigned. In WebKit, 13 new bugs were found; and 6 of them were vulnerabilities with 3 CVE identifiers assigned, while others are pending for advisories. It is worth mentioning that these bugs obtained high appraisals, e.g., “This bug is really interesting”, “Thank you for the awesome test case” and “This bug has existed for a long time. A quick look through blame would say for 4-5 years or so”. In Jerryscript, we found 4 previously unknown bugs, from which we found 4 vulnerability with 3 CVE identifiers assigned. In ChakraCore, we discovered 3 new bugs, and one of them is a vulnerability. Note that we received 3.2K USD bug bounty rewards.
With respect to the type of these bugs (see the third column of Table III), 12 of them are buffer overflow, 2 of them are integer overflow, 4 of them are memory corruption, 2 of them are arbitrary address access, and 1 of them is use-after-free. These are all vulnerabilities. Besides, 4 of them are null pointer dereference, and 6 of them are assertion failure. These are all denial of service bugs. All these 31 bugs have been confirmed, and 25 of them have been fixed.
Comparison to AFL. Among these 31 bugs, AFL only discovered six of them (as shown in the fourth column of Table III) and did not discover any other new bugs. This demonstrates that our approach significantly improves the bug finding capability of coverage-based grey-box fuzzers, which owes to the grammar-awareness in Superion. Specifically, for relatively weakly-structured inputs such as XML, AFL itself found 5 bugs, while Superion not only found all these 5 bugs, but also found 6 more bugs than AFL. Differently, for highly-structured inputs such as JavaScript, AFL barely found bugs. Only one bug about utf-8 encoding problem was found by AFL in Jerryscript. All other bugs in JavaScript engines were actually found by Superion’s tree-based mutation. This further demonstrates the significance of injecting grammar-awareness into coverage-based grey-box fuzzers.
Comparison to jsfunfuzz. We also compared Superion with jsfunfuzz , which is a successful grammar-aware fuzzer specifically designed for testing JavaScript engines. jsfunfuzz can be used to fuzz WebKit and ChakraCore; but it fails to fuzz Jerryscript because its generated JavaScript inputs have many JavaScript features that are not supported by Jerryscript. After three months of fuzzing, jsfunfuzz only found hundreds of out-of-memory crashes in WebKit and ChakraCore, but failed to find any bugs (as indicated by the last column of Table III). This is because jsfunfuzz uses manually-specified rules to express the grammar rules the generated inputs should satisfy. However, it is daunting, or even impossible to manually express all the required rules. Instead, Superion directly uses the grammar automatically during trimming and mutation.
In summary, Superion can significantly improve the bug-finding capability of coverage-based grey-box fuzzers (e.g., we found 31 new bugs, among which we discovered 21 new vulnerabilities with 16 CVE identifiers assigned).
III-C Code Coverage (RQ2)
As empirically studied that 1% increase in code coverage can increase the percentage of found bugs by 0.92% . Hence, apart from the bug-finding capability, we measured the code coverage achieved by fuzzing. The results are shown in Table IV, including the line and function coverage of the target programs. In particular, we list the coverage achieved by initial seeds, AFL and Superion. The coverage was calculated using afl-cov . We were not able to calculate the coverage for jsfunfuzz due to two reasons: jsfunfuzz does not keep the JavaScript samples executed; and jsfunfuzz is verfy efficient and executes millions of JavaScript samples until it triggers a crash, which makes the coverage computation infeasible.
For line coverage, the initial seeds covered 33.3% lines of libplist, 52.4% lines of WebKit, 81.3% lines of Jerryscript and 46.7% lines of ChakraCore. By fuzzing, AFL respectively increased their line coverage to 50.8%, 56.0%, 84.0% and 54.5%. On average, AFL further covered 7.9% of the code. Superion improved the line coverage to 68.9%, 78.0%, 88.2% and 76.9%, respectively; and it further covered 24.6% of the code on average. Overall, Superion outperformed AFL by 16.7% in line coverage, because the grammar-awareness in Superion carries the fuzzing exploration towards the application execution stage.
On the other hand, for function coverage, the initial seeds covered 44.8% functions on average, and AFL and Superion increased the function coverage to 49.1% and 57.9%, respectively. Generally, Superion outperformed AFL by 8.8% in function coverage due to its grammar-awareness.
In summary, Superion can significantly improve the code coverage of coverage-based grey-box fuzzers (e.g., 16.7% in line coverage and 8.8% in function coverage).
III-D Effectiveness of Grammar-Aware Trimming (RQ3)
Table V compares the trimming ratio (i.e., the ratio of bytes trimmed from test inputs) and the grammar validity ratio (i.e., the ratio of test inputs that are grammar-valid after trimming) using the built-in trimming in AFL and the tree-based trimming in Superion. Numerically, for libplist, the built-in trimming in AFL trimmed out 21.7% of bytes in XML test inputs on average, while our tree-based trimming trimmed out 11.7% on average. On the other hand, 74.1% of test inputs after the built-in trimming were grammar-valid, but 100% of test inputs after our tree-based trimming were grammar-valid and can be further used to conduct our grammar-aware mutation.
Similarly, the built-in trimming respectively trimmed out 10.6%, 5.1% and 12.7% of bytes in JavaScript test inputs for WebKit, Jerryscript and ChakraCore, while our tree-based trimming respectively trimmed out 7.6%, 4.7% and 11.3% for WebKit, Jerryscript and ChakraCore. On the other hand, our tree-based trimming increased the grammar validity ratio for WebKit, Jerryscript and ChakraCore from 86.4%, 89.3% and 83.7% to 100%, which can facilitate our grammar-aware mutation by improving the chance of applying grammar-aware mutation (which is more effective in generating test inputs that can trigger new coverage as will be discussed in Section III-E).
In summary, although with a relatively low trimming ratio, our grammar-aware trimming strategy can significantly improve the grammar validity ratio for the test inputs after trimming, which facilitates our grammar-aware mutation.
III-E Effectiveness of Grammar-Aware Mutation (RQ4)
To evaluate the effectiveness of our grammar-aware mutation strategies, we compared them with those built-in mutation strategies of AFL , which include bit flips (flip1/flip2/flip4 – one/two/four bit(s) flips), byte flips (flip8/flip16/flip32 – one/two/four byte(s) flips), arithmetics (arith8/arith16/arith32 – subtracting or adding small integers to 8-/16-/32-bit values), value overwrite (interest8/interest16/interest32 – setting “interesting” 8-/16-/32-bit values to 8-/16-/32-bit values), havoc (random application of bit flips, byte flips, arithmetics, and value overwrite), and splice (splicing together two random test inputs from the queue, and then applying havoc). For the ease of presentation, our enhanced dictionary-based mutation strategy is referred as ui (insertion of user-supplied tokens), uo (overwrite with user-supplied tokens), ai (insertion of automatically extracted tokens), and ao (overwrite with automatically extracted tokens); and our tree-based mutation strategy is referred as tree.
Fig. 7 shows the number of interesting test inputs (i.e., triggering new coverage) discovered by different mutation strategies as we fuzzed WebKit. For space limit, we omit the similar results for libplist, Jerryscript and ChakraCore. The -axis denotes the number of test inputs that Superion sequentially took from the queue and processed, and the -axis denotes the corresponding number of interesting test inputs produced by different mutation strategies. As the process of different test inputs often takes different time, we do not use time to represent the -axis. Besides, for clarity, Fig. 7 omits the results when all the mutation strategies become ineffective in continuously producing interesting test inputs (i.e., when the curves in Fig. 7 change gently).
The results vary across different seeds. Even with seeds fixed, the results may also vary across different runs due to the random nature of some mutation strategies (i.e., havoc, splice and tree). However, the trend remains the same across runs, and we only discuss the trend which holds across runs. In the beginning, bit and byte flips take a leading position in producing interesting test inputs. The reasons are that i) bit and byte flips often destroy the input structure, and trigger previously unseen error handling paths; and ii) bit and byte flips are the first mutation strategy to be sequentially applied, thus having the opportunity to first trigger the new coverage that could also be triggered by other mutation strategies. Gradually, the number of interesting test inputs generated by our grammar-aware mutation strategies outperform other mutation strategies. Specifically, tree and uo significantly outperform other mutation strategies. These results indicate that grammar-aware mutation strategies are effective in producing interesting test inputs.
Besides, we also explore the efficiency of different mutation strategies in producing interesting test inputs. The results are shown in Fig. 8, where the -axis is the same to Fig. 7 and the -axis denotes the ratio of interesting test inputs to the total number of generated test inputs. Surprisingly, all the mutation strategies are very inefficient in producing interesting test inputs, i.e., only two of the 1000 mutated test inputs can trigger new coverage. Thus, a huge amount of fuzzing efforts are wasted in mutating and executed test inputs. Therefore, adaptive mutation rather than exhaustive mutation should be designed to smartly apply mutation strategies.
Moreover, to evaluate our enhancement to dictionary-based mutation, we compared the dictionary overwrite and insertion in AFL with those in Superion. The results are reported in Fig. 9, where the -axis is the same to Fig. 7, and the -axis in Fig. 9(a) and Fig. 9(b) represent the number of times each mutation is applied and the number of interesting test inputs generated. We can see that our enhanced dictionary-based mutation greatly decreases the number of mutation applications by half, while still generating significantly more interesting test inputs.
In summary, our grammar-aware mutation strategies are effective in generating test inputs that can trigger new coverage, compared to the built-in mutation strategies in AFL. However, the efficiency of all mutation strategies need to be improved.
III-F Performance Overhead (RQ5)
The fuzzing process of a test input includes three major steps: parsing, mutation and execution. Among them, the parsing step is one-off for each test input, followed by a large number of mutations and executions. In Fig. 10(a) and 10(b), we show the parsing time of JavaScript and XML test inputs in seconds (the -axis) with respect to the size of test input files in bytes (the -axis). Without loss of generality, we only report the results for the initial test inputs (see the last column in Table I). In detail, the parsing time includes the time to read, parse and traverse a test input file. Generally, the parsing time is linearly correlated to the size of test input files. Most of the JavaScript test inputs’ size is under 10 KB and their parsing time is under 10 seconds, and the parsing time of XML test inputs is under 0.045 seconds. Notice that the parser generated using ANLTR is not optimized for the performance. We may reduce the execution time further by improving the parser’s implementation.
Apart from the parsing time, the major performance overhead Superion imposes on mutation and execution is caused by our tree-based mutation. Table VI reports the overhead of applying tree-based mutation (in the second column) as well as the corresponding overhead of executing the mutated test input (in the third column). For small projects like libplist, it is very fast to perform tree-based mutation and execution, i.e., the mutation took 0.63 ms and the execution took 0.39 ms on average. For large projects such as WebKit, Jerryscript and ChakraCore, the execution took much more time; e.g., executing a JavaScript input on ChakraCore took 20.00 ms, while the mutation took 5.65 ms on average. Considering the improvements to bug-finding capability and code coverage, the performance overhead introduced by Superion is acceptable.
In summary, Superion introduces additional overhead due to our grammar-aware tree-based mutation strategy. However, such overhead is still acceptable considering the improved bug-finding capability and code coverage.
III-G Case Study
The JavaScript code fragment in Fig. 11 gives a representative test input that was generated by Superion and triggered an integer overflow vulnerability in WebKit, assigned CVE-2017-7xxx. In particular, this vulnerability is triggered because the method setInput in class RegExpCachedResult forgets to reify the leftContext and rightContext. As a result, when later WebKit attempts to reify them, it will end up using indices into an old input string to create a substring of a new input string. For the test input in Fig. 11, WebKit tried to get a substring through jsSubstring, whose length is 1 (i.e., length of “a”) - 2 (i.e., m_result.end of “ss”) = -1, as shown in Fig. 12, which is a very large number when treated as positive. Thus, an integer overflow vulnerability is caused.
The test input in Fig. 11 was actually simplified from a large test input for the ease of presentation. It was generated by applying our tree-based mutation on the two test inputs in Fig. 13 and Fig. 14. This proof-of-concept was not generated through one mutation, but was generated after several times of mutations. The intermediate test inputs that triggered new coverage were kept and added to the queue for further mutations. Eventually, it evolved into the proof-of-concept. This vulnerability was not triggered by AFL. This indicates that AFL’s built-in mutation strategies is not effective in fuzzing programs that process structured inputs, where our tree-based mutation becomes effective.
III-H Discussion
One threat to the validity of our evaluation is that we did not evaluate Superion on standardized data sets such as LAVA and CGC . However, many of the programs in these data sets process unstructured inputs, or are difficult to come up with a grammar. Therefore, we did not use them. Instead, we used four real-life programs, whose evaluation results are representative.
Another threat is that we did not empirically compare Superion with LangFuzz and IFuzzer , two general-purpose grammar-aware mutation-based fuzzers. LangFuzz is not publicly available, and IFuzzer lacks sufficient documentation to set up. Instead, we compared Superion with jsfunfuzz, a successful grammar-aware generation-based fuzzer for JavaScript engines.
One limitation of Superion is that it needs a grammar, which limits the applicability to only publicly documented formats that have specified grammars. Therefore, Superion may have trouble finding proprietary grammars or undocumented extensions to standard grammars. However, several automatic grammar inference techniques have been proposed, we plan to integrate such techniques to have a wider applicability.
IV Related Work
Instead of listing all related work, we focus our discussion on the most relevant fuzzing work in five aspects: guided mutation, grammar-based mutation, block-based generation, grammar-based generation, and fuzzing boosting.
Guided Mutation. Mutation-based fuzzing was proposed to generate test inputs by randomly mutating well-formed test inputs . Then, a large body of work has been developed to use heuristics to guide mutation. AFL , Steelix , FairFuzz and CollAFL use coverage to achieve the guidance, and SlowFuzz and PerfFuzz further use resource usage to realize the guidance. BuzzFuzz , Vuzzer and Angora leverage taint analysis to identify those interesting bytes for mutation. SAGE , Babić et al. , Pham et al. and Badger leverage symbolic execution to facilitate fuzzing. Dowser , TaintScope and BORG integrate taint analysis with symbolic execution to guide fuzzing. Driller combines fuzzing and concolic execution to discover deep bugs. Kargén and Shahmehri perform mutations on the machine code of the generating programs instead of directly on a test input in order to leverage the information about the input format encoded in the generating programs. In summary, these fuzzing techniques target programs that process compact or unstructured inputs, which become less effective for programs that process structured inputs. Complementary to them, Superion can effectively fuzz programs that process structured inputs.
It is worth mentioning that application-specific fuzzers have been attracting great interests, e.g., compiler fuzzing , kernel fuzzing , IoT (Internet of Things) fuzzing , OS fuzzing , smart contract fuzzing , GUI testing , and deep learning system testing . It is interesting to investigate how to extend our general-purpose fuzzer (e.g., by designing new mutation operators or feedback mechanisms) to be effective in fuzzing specific applications.
LangFuzz uses a grammar to separate previously failing test input to code fragments and save them into a fragment pool. Then, some code fragments of a test input are mutated by replacing them with the same type of code fragments in the pool. Similarly, IFuzzer uses the grammar to extract code fragments from test inputs and recomposes them in an evolutionary way. Different from these two blackbox fuzzers, Superion brings grammar-awareness into coverage-based greybox fuzzers.
Block-Based Generation. As some bytes in a test input are used collectively as a single value in the program, they should be considered together as a block during fuzzing. Following this observation, TestMiner first mines literals from a corpus of test inputs and then queries the mined data for values suitable for a given method under test. These predicted values are then used as test inputs during test generation. It is not clear whether it works well for highly-structured inputs such as JavaScript as they experimented with simple formats such as IBAN, SQL, E-mail and Network address. Spike and Peach use input models, specifying the format of data chunks and integrity constraints, to regard test inputs as blocks of data, and leverage mutations to generate new test inputs. While being effective in fuzzing programs that process weakly-structured inputs (e.g., images and protocols), these approaches become less effective for highly-structured inputs (e.g., JavaScript). Complementary to them, Superion is designed for such highly-structured inputs.
Grammar-Based Generation. Another line of work is to use the grammar to directly generate test inputs. mangleme is an automated broken HTML generator and browser fuzzer. jsfunfuzz uses specific knowledge about past and common vulnerabilities and hard-coded rules to generate new test inputs. Dewey et al. propose to use constraint logic programming for program generation. Valotta uses his domain knowledge to manually build a fuzzer to test browsers. While being effective in finding vulnerabilities, they all rely on some hard-coded or manually-specified rules to express semantic rules, which hinder their applications to a wider audience.
Godefroid et al. apply symbolic execution to generate grammar-based constraints, and use grammar-based constraint solver to generate test inputs. CSmith iteratively and randomly selects one production rule in the grammar to generate C programs. Domato generates test inputs from scratch given the grammars that specify HTML/CSS structures and JavaScript objects, properties and functions. Domato also fuzzed WebKit for three months; but none of our bugs were found by Domato. This is a strong evidence that Superion has the characteristics that grammar-aware fuzzers without coverage feedback do not have. Skyfire and TreeFuzz learn a probabilistic model from the grammar and a corpus of test inputs to generate test inputs. They are generation-based, while Superion is grammar-aware mutation-based, which incrementally utilizes the interesting behaviors embedded in previous interesting test inputs.
Fuzzing Boosting. Another thread of work focuses on improving the efficiency of fuzzing, e.g., seed selection , seed scheduling , parameter tuning , directed fuzzing to reproduce crashes or assess potential bugs found by vulnerable code matching , and operating primitives . These boosting techniques are orthogonal to Superion.
V Conclusions
In this paper, we propose a grammar-aware coverage-based greybox fuzzing approach, Superion, for programs that process structured inputs. Specifically, we propose a grammar-aware trimming strategy and two grammar-aware mutation strategies to effectively trim and mutate test inputs while keeping the input structure valid, quickly carrying the fuzzing exploration into width and depth. Our experimental study on several XML and JavaScript engines has demonstrated that Superion improved code coverage and bug-finding capability over AFL. Moreover, Superion found 31 new bugs, among which 21 new vulnerabilities were discovered and 16 CVEs were assigned.