Recent research has shown that mutational search with appropriate instrumentation can generate short inputs that demonstrate performance issues. Another thread of fuzzing research has shown that substituting subtrees from a forest of derivation trees is an effective grammar-based fuzzing technique for finding deep semantic bugs. We combine performance fuzzing with grammar-based search by generating length-limited derivation trees in which each subtree is labeled with its length. In addition we use performance instrumentation feedback to guide search. In contrast to fuzzing for security issues, for which fuzzing campaigns of many hours or even weeks can be appropriate, we focus on searches that are short enough (up to an hour with modest computational resources) to be part of a routine incremental test process. We have evaluated combinations of these approaches, with baselines including the best prior performance fuzzer. No single search technique dominates across all examples, but both Monte Carlo tree search and length-limited tree hybridization perform consistently well on example applications in which semantic performance bugs can be found with syntactically correct input. In the course of our evaluation we discovered a hang bug in LunaSVG, which the developers have acknowledged and corrected.

TreeLine and SlackLine are grammar-based fuzzers for quickly finding performance problems in programs driven by richly structured text that can be described by context-free grammar. In contrast to long fuzzing campaigns to find (mostly invalid) inputs that trigger security vulnerabilities, TreeLine and SlackLine are designed to search for performance problems in the space of valid inputs in minutes rather than hours. The TreeLine and SlackLine front-ends differ in search strategy (Monte Carlo Tree Search or derivation tree splicing, respectively) but accept the same grammar specifications and rely on a common back-end for instrumented execution. Separation of concerns should facilitate use by other researchers who wish to explore alternatives and extensions of either the front or back ends.