  Fuzzing has become a commonly used approach to identifying bugs in complex,
real-world programs. However, interpreters are notoriously difficult to fuzz
effectively, as they expect highly structured inputs, which are rarely produced
by most fuzzing mutations. For this class of programs, grammar-based fuzzing
has been shown to be effective. Tools based on this approach can find bugs in
the code that is executed after parsing the interpreter inputs, by following
language-specific rules when generating and mutating test cases. Unfortunately,
grammar-based fuzzing is often unable to discover subtle bugs associated with
the parsing and handling of the language syntax. Additionally, if the grammar
provided to the fuzzer is incomplete, or does not match the implementation
completely, the fuzzer will fail to exercise important parts of the available
functionality. In this paper, we propose a new fuzzing technique, called
Token-Level Fuzzing. Instead of applying mutations either at the byte level or
at the grammar level, Token-Level Fuzzing applies mutations at the token level.
Evolutionary fuzzers can leverage this technique to both generate inputs that
are parsed successfully and generate inputs that do not conform strictly to the
grammar. As a result, the proposed approach can find bugs that neither
byte-level fuzzing nor grammar-based fuzzing can find. We evaluated Token-Level
Fuzzing by modifying AFL and fuzzing four popular JavaScript engines, finding
29 previously unknown bugs, several of which could not be found with
state-of-the-art byte-level and grammar-based fuzzers.
