  Fuzzing is an effective technique for discovering software vulnerabilities by
generating random test inputs and executing them against the target program.
However, fuzzing large and complex programs remains challenging due to
difficulties in uncovering deeply hidden vulnerabilities. This paper addresses
the limitations of existing coverage-guided fuzzers, focusing on the scheduler
and mutator components. Existing schedulers suffer from information sparsity
and the inability to handle fine-grained feedback metrics. The mutators are
agnostic of target program branches, leading to wasted computation and slower
coverage exploration. To overcome these issues, we propose an end-to-end online
stochastic control formulation for coverage-guided fuzzing. Our approach
incorporates a novel scheduler and custom mutator that can adapt to branch
logic, maximizing aggregate edge coverage achieved over multiple stages. The
scheduler utilizes fine-grained branch distance measures to identify frontier
branches, where new coverage is likely to be achieved. The mutator leverages
branch distance information to perform efficient and targeted seed mutations,
leading to robust progress with minimal overhead. We present FOX, a
proof-of-concept implementation of our control-theoretic approach, and compare
it to industry-standard coverage-guided fuzzers. 6 CPU-years of extensive
evaluations on the FuzzBench dataset and complex real-world programs (a total
of 38 test programs) demonstrate that FOX outperforms existing state-of-the-art
fuzzers, achieving average coverage improvements up to 26.45% in real-world
standalone programs and 6.59% in FuzzBench programs over the state-of-the-art
AFL++. In addition, it uncovers 20 unique bugs in popular real-world
applications including eight that are previously unknown, showcasing real-world
security impact.
