Deep Fuzzing Through Cataloging Common Loop Termination Patterns

Proposal

In general, there are too many possible paths of execution through a non-trivial program for a fuzz tester to execute them all. Each branch instruction a fuzzer encounters while tracing forward from a program’s entry point presents it with a choice between a diverging left and right fork, doubling the number of paths it must explore in search of vulnerabilities. Repeated doublings inevitably exhaust a fuzzer’s resources before it can come close to complete coverage. The median coverage of program statements of traditional fuzzers is roughly 20% [WAN2020]. Even the innovative American Fuzzy Lop (AFL) grey-box fuzzer reaches only 15% modified condition/decision coverage [RAN2022]. Undiscovered vulnerabilities doubtless hide in the uncovered space.

We have surveyed several recent efforts to develop fuzzing techniques that trace backwards from a potential vulnerability to a program’s entry point, arriving with a symbolic description of a concrete test input capable of reaching the potential vulnerability to confirm or refute it [STE2016, KIM2019, ZHU2019]. This backwards search conserves resources by turning the if-then-else control structure branches that forward-searching fuzzers perceive as forks into merges that do not double the number of paths. However, it does nothing to help with branches that implement loops; backwards-searching fuzzers must still discover the termination conditions of loops whose repetitions threaten to consume all resources just as forward-searching fuzzers do. We offer the following insights:

1. The present practice of treating looping branches with the same approach as if-then-else branches is unlikely to yield good results; loop approaches must be aware of and focus on termination conditions.
2. Efforts seeking to come close to the impossible ideal of an automated analysis capable of correctly identifying the termination condition of any general loop [RIC1953] are misdirected; if a broad empirical study of loops in real-world software were made, if would likely find that the majority match one of a manageable number of specific common loop patterns whose termination conditions could be understood and cataloged in practice.

We hypothesize that even an incomplete catalog would enable a backwards searching fuzzer to efficiently navigate through more loops than today’s best fuzzers and thus reach deeper into the control flow of programs where previously undiscovered vulnerabilities are likely to lie.

Our prior work on DARPA/I2O’s Space/Time Analysis for Cybersecurity (STAC) program provides us with some confidence that a broad study would catalog sufficient common loop patterns to enable superior fuzzing. This work developed and demonstrated novel human-in-the-loop program analysis techniques and tools to characterize the behavior of loops and identify vulnerabilities to algorithmic complexity and side-channel attacks. We used these analyses to mount a small but significant survey of 5000 loops drawn from the STAC program’s 18 challenge applications and four popular open-source libraries. The survey produced a catalog of 14 common loop termination patterns covering 78.4% of the surveyed loops, with the most popular patterns contributing the most coverage as shown in the histogram below [AWA2017].

Our analysis technique is a human-on-the-loop approach based on prior work to speed up verification of high-assurance software (e.g. Boeing 787). We build a graph database that captures the control flow and data flow of software as an attributed graph and then annotate the graph with the results of a suite of program analyses. This allows the user to build and visualize more sophisticated loop patterns than would otherwise be possible with a monolithic analyzer.

A backwards-searching fuzzing technique with efficiency boosted by a loop termination pattern catalog could enable DoD to identify more vulnerabilities in software and vulnerabilities hiding deeper in programs than can be discovered with traditional fuzzing techniques. We propose a 1-year effort at a cost not to exceed $500,000 to (1) mount a larger survey of loop termination patterns in popular Internet-facing software such as the Apache web server, (2) prototype a backwards-searching fuzzer that uses a catalog of these loop termination patterns to efficiently trace through loops, and (3) test our hypothesis by comparing the ability of our experimental prototype to generate inputs that reach program points of interest against the ability of a popular control fuzzer such as AFL.