Predictive Context-sensitive Fuzzing

Coverage-guided fuzzers expose bugs by progres-
sively mutating testcases to drive execution to new program
locations. Code coverage is currently the most effective and
popular exploration feedback. For several bugs, though, also how
execution reaches a buggy program location may matter: for
those, only tracking what code a testcase exercises may lead
fuzzers to overlook interesting program states. Unfortunately,
context-sensitive coverage tracking comes with an inherent state
explosion problem. Existing attempts to implement context-
sensitive coverage-guided fuzzers struggle with it, experiencing
non-trivial issues for precision (due to coverage collisions) and
performance (due to context tracking and queue/map explosion).
In this paper, we show that a much more effective approach
to context-sensitive fuzzing is possible. First, we propose function
cloning as a backward-compatible instrumentation primitive
to enable precise (i.e., collision-free) context-sensitive coverage
tracking. Then, to tame the state explosion problem, we argue to
account for contextual information only when a fuzzer explores
contexts selected as promising. We propose a prediction scheme
to identify one pool of such contexts: we analyze the data-flow
diversity of the incoming argument values at call sites, exposing
to the fuzzer a contextually refined clone of the callee if the latter
sees incoming abstract objects that its uses at other sites do not.
Our work shows that, by applying function cloning to pro-
gram regions that we predict to benefit from context-sensitivity,
we can overcome the aforementioned issues while preserving,
and even improving, fuzzing effectiveness. On the FuzzBench
suite, our approach largely outperforms state-of-the-art coverage-
guided fuzzing embodiments, unveiling more and different bugs
without incurring explosion or other apparent inefficiencies. On
these heavily tested subjects, we also found 8 enduring security
issues in 5 of them, with 6 CVE identifiers issued.