Reaching Deeper Security Threats Using Grammar-Based Fuzzers and Understanding their Effectiveness

Grammar-based fuzzing has re-emerged as a significant research topic in recent years, but the real impact of grammars and grammar inference on finding deep security bugs, relative to grammar-agnostic fuzzing, is still unclear.In this paper, we measure and compare the effectiveness of a state-of-the-art grammar-aware (TreeLine) fuzzing system and a related grammar-agnostic (SlowFuzz) system on a large and representative benchmark suite of programs spanning a wide range of structural complexity.We use maximum cumulative execution cost (CFG edge hits) as our fundamental performance metric to compare the depth of exploration achieved by the two systems.We find that in the limit of maximum time (72 hours), grammar-aware fuzzers are consistently and orders-of-magnitude more effective on structurally complex targets, and that the adaptive grammar inference techniques (Slackline and TreeLine-Arvada) yield significant speedups on these targets in the early stages of fuzzing as well.On the other hand, the gap between grammar-aware and grammar-agnostic fuzzers shrinks as the program's structural complexity is reduced, indicating that grammar awareness may be less helpful (and/or resource intensive) for targets lacking deep recursive paths or syntactic constraints.The most salient results from this work, including reaching an execution cost of up to 2.6 billion CFG edge hits on complex parsers with Slackline and Slackline-Arvada, and grammar-agnostic fuzzing tools peaking at less than 100 million, have been corroborated by a follow-up independent replication study.