When Control Flows Deviate: Directed Grey-box Fuzzing with Probabilistic Reachability Analysis

Directed grey-box fuzzing (DGF) steers testing toward high-value targets, but developing effective DGF for commercial off-the-shelf (COTS) binaries is challenging due to the lack of accurate structural information (e.g., control-flow graphs and call graphs), which can cause control flows to deviate and misguide DGF’s reachability analysis. In this paper, we introduce BinGo, a tailored binary-level directed grey-box fuzzer, which can accommodate the flawed control-flow graphs (CFGs) of COTS binaries and enable accurate and efficient reachability analysis. First, to quantify the inevitable inaccuracies of uncovered indirect edges and analyze their impact on the reachability of basic blocks, we propose a Bayesian-based method. This method combines prior knowledge from static analysis with dynamic observations from fuzzing to estimate the confidence in correctly recovering indirect edges. Then, we present a new concept called a region, which redefines granularity for efficient reachability analysis by transforming the CFG into a region graph. Using the Bayesian results and region graph, we propose a custom fitness metric for binary-level DGF, termed probabilistic reachability. This metric, based on a dynamically updated region graph and reachability scores, is adaptive, lightweight, and accommodates inaccurate binary-level CFGs. We implemented a prototype tool, BinGo, and evaluated it on the CGC dataset, CVE-Benchmark, and UniBench benchmark. Experimental results show that BinGo surpasses baseline fuzzers (AFL++, AFLGo, PDGF, UAFuzz, and 1dVul) in reaching target locations and exposing known vulnerabilities. Additionally, BinGo discovered three new vulnerabilities in the real-world application cscope-15.9.