Parse this! Summoning Context-Sensitive Inputs with Goblin

Grammar-based fuzzers have been effective at identifying bugs in software systems with highly structured input formats (e.g., XML). Many existing grammar-based fuzzers rely on context-free grammars (CFGs) to represent input structure; however, CFGs are often insufficient to capture the context-sensitive constraints common in real-world inputs. While application-specific fuzzers can often handle such constraints, they lack the generality needed to adapt to new applications. We present Goblin, a new input generation tool that addresses this gap. Given a context-free grammar annotated with semantic constraints, Goblin generates inputs that both conform to the grammar and satisfy the constraints. A distinguishing feature of Goblin is its support—via an external SMT solver—for constraints expressed in arbitrary SMT theories. Inspired by DPLL-style SAT solvers, Goblin enjoys formal guarantees of solution soundness, solution completeness, and refutation soundness. We evaluate Goblin by comparing it with prior work and by integrating it into a grammar-based network protocol fuzzer.