Coverage-guided fuzzing is exceptionally good at finding bugs by rapidly mutating inputs to explore new program paths. However, traditional greybox fuzzers suffer from a fundamental combinatorial bottleneck: they treat all input bytes equally. If a program expects a 1-megabyte file, but a critical security check or branch condition depends on only four specific bytes, a random mutation strategy will waste millions of executions flipping irrelevant bits.
To bypass complex validation logic and deep branch conditions, a parallel track of research has emerged around identifying influential input bytes—often called "hot bytes." By locating the exact coordinates in an input file that control program behavior, fuzzers can shrink their search space from the entire input down to a handful of high-leverage targets.
Researchers have converged on two primary strategies to uncover these hot bytes: taint inference (tracking data flow directly) and gradient-based sensitivity analysis (treating the program as a differentiable function).
Locating Hot Bytes via Taint Inference
The most direct way to find out which input bytes affect a specific branch is to track them as they flow through the program's execution. This is the core intuition behind dynamic taint analysis (DTA).
In TaintScope, Tielei Wang et al. demonstrated that fine-grained, byte-level taint analysis could pinpoint hot bytes responsible for security-sensitive operations, such as checksum verifications. Once these bytes are identified, the fuzzer concentrates its mutations exclusively on them, preventing the tool from getting stuck on complex validation checks. Similarly, Siyuan Li et al. developed TransferFuzz, which uses taint analysis to extract the exact bytes responsible for bypassing security checks in historical traces, turning them into a specialized mutation dictionary to navigate complex branch conditions. In the domain of smart contracts, Baotong Wang et al. implemented SCH-Hunter, utilizing dynamic taint analysis to track transaction sequences and prioritize mutations on sensitive data paths via genetic algorithms.
Lightweight and Fuzzing-Driven Taint Inference
While traditional DTA is highly precise, tracking data flow at the instruction level incurs massive runtime overhead, often slowing execution down by orders of magnitude. To solve this, recent work has shifted toward inferring taint through differential observation.
Traditional Taint (Heavy): [Input Byte] ---> [Instruction Tracking] ---> [Branch Variable]
Fuzzing-Driven (Light): [Mutate Byte] ---> [Observe Change?] ---> [Infer Taint]
Instead of monitoring every CPU instruction, Shuitao Gan et al. introduced GREYONE, which relies on "fuzzing-driven taint inference." The intuition is simple: if you tweak a specific byte in the input and a downstream program variable changes its value, that variable is functionally dependent on (or tainted by) that byte. By assigning weights to input bytes based on how many untouched branches they influence, the fuzzer can prioritize high-value targets without heavy instrumentation.
Yuchong Xie et al. took this concept to its logical conclusion with ZTaint-Havoc. They realized that a fuzzer's "havoc mode"—which applies rapid, random mutations—is inherently a form of differential testing. By piggybacking on these existing mutations and observing the execution outcomes, the authors achieved "zero-execution" taint inference, identifying hot bytes without requiring any dedicated or separate program runs.
Locating Hot Bytes via Neural Gradients
An alternative, highly mathematical approach abandons explicit data-flow tracking entirely. Instead, it treats the target program as a black-box function and uses machine learning to approximate its behavior.
Standard computer programs are discrete and step-like: a branch is either taken ($1$) or not taken ($0$). This step-function nature means the mathematical derivative (gradient) of a program with respect to its input is zero almost everywhere, making standard calculus-based optimization impossible.
To overcome this, Dongdong She et al. proposed Neural Program Smoothing in NEUZZ. By training a neural network surrogate model to predict which program branches will be triggered by a given input, they create a smooth, differentiable approximation of the program's control flow.
Discrete Program: Input [01 00] -> Branch A (True) | Gradient = 0
Smoothed Model: Input [01.0, 00.0] -> Branch A (0.87) | Gradient = Differentiable
Because the neural network is fully differentiable, you can compute the gradient of the model's output with respect to the input data. The magnitude of the gradient for a specific input byte represents the model's saliency or sensitivity to that byte. If a tiny fractional change to byte $X$ causes a massive swing in the predicted branch coverage, byte $X$ is a hot byte.
The authors expanded on this paradigm across several papers:
- In Neutaint, Dongdong She et al. used these gradient-based saliency maps as a direct replacement for traditional rule-based dynamic taint analysis, tracking information flow with significantly less overhead.
- In MTFuzz, the authors addressed data sparsity by training a Multi-Task Neural Network on multiple coverage metrics simultaneously, using the shared embeddings to calculate highly precise saliency scores across complex control flows.
From Hot Bytes to Mathematical Solutions
Once a fuzzer knows which bytes are important, how does it mutate them effectively?
Rather than randomly guessing new values for these hot bytes, systems like Angora, developed by Hao Chen et al., frame branch constraints as mathematical equations. For example, an execution path might require that input[4] == input[8] + 10. By isolating these specific bytes via taint analysis, Angora can run standard numerical optimization algorithms (like gradient descent) directly on the target bytes to solve the constraint and unlock the branch.
The Reality Check of Overhead
While gradient-guided and taint-guided mutations offer an elegant, surgical alternative to random bit-flipping, they introduce a classic trade-off between search intelligence and execution speed.
In Revisiting Neural Program Smoothing for Fuzzing, Andreas Zeller et al. performed a rigorous evaluation of neural program smoothing techniques. The authors pointed out that while gradient guidance successfully identifies critical bytes, the computational cost of constantly training and evaluating neural network models can drastically reduce the fuzzer's execution throughput. Under fair benchmarking conditions, highly optimized, "dumb" greybox fuzzers (like AFL++) can sometimes find bugs faster simply by executing orders of magnitude more test cases per second.
As a result, the cutting edge of this research direction focuses on minimizing this overhead—either by embedding taint inference directly into existing mutation loops as seen in ZTaint-Havoc, or by refining surrogate models to ensure that the mathematical precision of the mutation is worth the computational price.
Key Foundational Work
Checksum-Aware Fuzzing Combined with Dynamic Taint Analysis and Symbolic Execution (2011) — contributed 2 concept elements to this direction.
Angora: Efficient Fuzzing by Principled Search (2018) — contributed 1 concept elements to this direction.