# MC2: Rigorous and Efficient Directed Greybox Fuzzing

arXiv: https://arxiv.org/abs/2208.14530 · HTML: https://mlsanity.com/paper/2208.14530/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Aug 2022.

## Built on by (most cited first, 5 of 5)

- [Locus: Agentic Predicate Synthesis for Directed Fuzzing](https://mlsanity.com/paper/2508.21302/) (2025)
- [PBFuzz: Agentic Directed Fuzzing for PoV Generation](https://mlsanity.com/paper/2512.04611/) (2025)
- [Fuzzing: Randomness? Reasoning! Efficient Directed Fuzzing via Large Language Models](https://mlsanity.com/paper/2507.22065/) (2025)
- [Attention Distance: A Novel Metric for Directed Fuzzing with Large Language Models](https://mlsanity.com/paper/2512.19758/) (2025)
- [DeepGo: Predictive Directed Greybox Fuzzing](https://mlsanity.com/paper/2507.21952/) (2025)

## Abstract (arXiv)

Directed greybox fuzzing is a popular technique for targeted software testing that seeks to find inputs that reach a set of target sites in a program. Most existing directed greybox fuzzers do not provide any theoretical analysis of their performance or optimality. In this paper, we introduce a complexity-theoretic framework to pose directed greybox fuzzing as a oracle-guided search problem where some feedback about the input space (e.g., how close an input is to the target sites) is received by querying an oracle. Our framework assumes that each oracle query can return arbitrary content with a large but constant amount of information. Therefore, we use the number of oracle queries required by a fuzzing algorithm to find a target-reaching input as the performance metric. Using our framework, we design a randomized directed greybox fuzzing algorithm that makes a logarithmic (wrt. the number of all possible inputs) number of queries in expectation to find a target-reaching input. We further prove that the number of oracle queries required by our algorithm is optimal, i.e., no fuzzing algorithm can improve (i.e., minimize) the query count by more than a constant factor. We implement our approach in MC2 and outperform state-of-the-art directed greybox fuzzers on challenging benchmarks (Magma and Fuzzer Test Suite) by up to two orders of magnitude (i.e., 134×) on average. MC2 also found 15 previously undiscovered bugs that other state-of-the-art directed greybox fuzzers failed to find.