ZTaint-Havoc: From Havoc Mode to Zero-Execution Fuzzing-Driven Taint Inference

Yuchong Xie, Wenhui Zhang, Dongdong She

TL;DR

This paper introduces ZTaint-Havoc, a novel technique that integrates taint inference directly into the "havoc mode" of fuzzers, eliminating the need for additional program executions. By cleverly adapting existing mutation strategies, ZTaint-Havoc identifies "hot bytes" that influence program behavior, leading to significantly improved code coverage and more efficient fuzzing.

What Problem Does This Paper Address?

Fuzzing is a powerful technique for finding software vulnerabilities, but a key challenge is identifying which parts of an input file (known as "hot bytes") actually affect the program's execution path. Traditional methods for this, like taint analysis, are often too slow and resource-intensive for large, real-world programs. A simpler approach called Fuzzing-Driven Taint Inference (FTI) exists, but it requires many extra program runs, leading to significant overhead. The authors aim to solve this by developing a lightweight FTI that requires zero additional program executions, leveraging the inherent properties of existing fuzzing mutation techniques.

Methods

The core innovation of ZTaint-Havoc lies in its integration with the "havoc mode" of fuzzers, a common mutation strategy that applies a series of random changes to input data. The authors first develop a computational model of havoc mode to formally understand its mutation process.

Their key contributions are:

  • Zero-Execution FTI: Instead of running the program multiple times for each input to infer taint, ZTaint-Havoc uses the mutations generated by havoc mode itself as inference instances. Each mutation in havoc mode is treated as a potential taint inference.
  • Mutation Threshold (k): A parameter k is introduced to control the divergence between an original seed and its mutated version. This ensures that mutations are "minimal" (satisfying FTI requirement R1) and helps maintain a balance between exploration and inference accuracy.
  • Cumulative Taint Inference: A mechanism to record the "taint count" for each byte position across many mutations. Bytes that consistently influence program behavior will accumulate higher counts, allowing for a more accurate identification of true "hot bytes" and mitigating "over-tainting."
  • Taint-Guided Mutation: After identifying hot bytes, ZTaint-Havoc biases its mutation strategy to focus on these influential bytes, leading to more effective exploration of the input space.

Datasets

The authors evaluate their approach on two widely-used fuzzing benchmarks:

  • FuzzBench: A standard benchmark suite for fuzzing research, providing a controlled environment with well-designed harnesses.
  • UniBench: A dataset featuring a diverse collection of real-world applications processing various data formats.

They selected 19 targets from FuzzBench and 17 from UniBench, excluding those with compilation issues.

Key Insights and Ideas

  • Havoc Mode is Naturally Suited for FTI: The paper demonstrates that the random, incremental, and byte-level nature of havoc mode mutations inherently aligns with the requirements of effective taint inference.
  • Zero Additional Executions is Achievable: The most significant insight is that taint inference doesn't require separate program runs; it can be piggybacked onto existing fuzzing mutation processes.
  • Thresholding is Crucial for Balancing: The k parameter is vital for preventing mutations from becoming too drastic (which can obscure program behavior) or too minor (which might miss multi-byte dependencies).
  • Cumulative Taint Counts Filter Noise: By aggregating taint information over many mutations, the system can distinguish between bytes that truly influence program behavior and those that are merely affected by random mutations.

Key Results

  • Improved Code Coverage: ZTaint-Havoc consistently outperforms the baseline AFL++ fuzzer. It achieves average edge coverage improvements of 2.97% on FuzzBench and 6.12% on UniBench in 24-hour campaigns. In some cases, improvements were as high as 33.71% (FuzzBench) and 51.12% (UniBench).
  • Minimal Runtime Overhead: The additional computational cost of ZTaint-Havoc is modest, with a runtime overhead of 3.84% on UniBench and 12.58% on FuzzBench. This is considered acceptable for the gains in coverage.
  • Adaptive Thresholding is Best: An adaptive k setting performed best across diverse targets, outperforming fixed k values and eliminating the need for manual parameter tuning.
  • Uniform Mutation Distribution: The thresholding mechanism helps to create a more uniform distribution of influenced bytes across the input space, which is beneficial for comprehensive testing.

Limitations and Future Work

  • Feedback Requirement: The method still requires code instrumentation to gather feedback, which can introduce some overhead.
  • Threshold Sensitivity: The effectiveness of the approach is dependent on the chosen threshold value. While an adaptive threshold is proposed, finding the optimal balance between undertaint and overtaint remains a consideration.
  • Filtering Noise: The filtering of noisy taint data to enhance quality reduces the sample size for inference, potentially impacting efficiency.
  • Future Work: The authors mention plans to incorporate features like floating-point number processing and string comparisons for more robust solver capabilities in future work.

Summary updated

BibTeX
@article{xie2025ztaint,
  author = {Yuchong Xie and Wenhui Zhang and Dongdong She},
  title = {{ZTaint-Havoc: From Havoc Mode to Zero-Execution Fuzzing-Driven Taint Inference}},
  journal = {Proc. ACM Softw. Eng.},
  year = {2025},
  doi = {10.1145/3728916},
}
Figure