Dynamic Test Generation to Find Integer Bugs in x86 Binary Linux Programs

David Molnar, Xue Cong Li, David A. WagnerUSENIX Security 2009 · OpenReview

Authors: David Molnar, Xue Cong Li, and David A. Wagner
Affiliation: UC Berkeley

Abstract

Integer-related vulnerabilities, including overflows and signedness errors, remain a significant threat to software security. This paper introduces SmartFuzz, a "white-box" fuzzing tool that leverages symbolic execution and a scalable cloud-based triaging infrastructure to automatically discover these bugs in x86 Linux binaries. By reconstructing type information from binary traces and using automated oracles to verify crashes, SmartFuzz identified 77 distinct bugs in widely-used media applications like mplayer and ffmpeg. The system demonstrates high efficiency, finding bugs at an average cost of $2.24 each on Amazon EC2.

1. Introduction

Integer bugs—such as overflows, width conversions, and signed/unsigned mismatches—are a leading cause of security vulnerabilities. When an integer "wraps around," it can lead to incorrect memory allocations, eventually causing buffer overflows that attackers can exploit. Traditional methods for finding these bugs often fall short: static analysis produces excessive false positives, runtime checks can break legitimate code, and black-box fuzzing often fails to reach deep program logic. SmartFuzz addresses these challenges by performing binary-only analysis to find bugs in compiled software where high-level type information has been lost.

2. SmartFuzz Architecture

SmartFuzz employs dynamic test generation to explore program paths systematically. The system is composed of several key components that work in a feedback loop to maximize bug discovery.

The SmartFuzz architecture workflow, showing the integration of symbolic execution, constraint solving, and automated triage.

The workflow begins with SymExec, which uses the Valgrind instrumentation framework to translate x86 instructions into VEX Intermediate Representation (IR). Input bytes are treated as symbolic variables. The Solve component uses the STP constraint solver to generate new inputs that force the program down unexplored paths or trigger specific error conditions, such as multiplication overflows. The Triage stage then verifies these test cases using Valgrind’s memcheck to ensure they cause real memory corruption. A Score/Pool mechanism manages the test cases, prioritizing those that lead to new coverage or potential vulnerabilities.

3. Implementation Techniques

To effectively analyze binaries, SmartFuzz incorporates several novel techniques:

  • Type Inference: Since binaries lack explicit type information, SmartFuzz observes CPU instructions. For example, values used in signed comparison instructions are inferred as signed, while those used in memcpy lengths are treated as unsigned. Mismatches between these uses flag potential signedness bugs.
  • Fuzzy Stack Hashing: To manage the volume of reports, the authors developed a hashing method to group similar crashes, accounting for minor variations in memory addresses caused by Address Space Layout Randomization (ASLR).
  • Metafuzz.com: A centralized cloud service was used to manage millions of test cases and automate the triage process across a distributed infrastructure.

4. Evaluation and Results

The authors evaluated SmartFuzz on a suite of complex Linux applications, including mplayer, ffmpeg, ImageMagick, and gzip. These tools were tested using various seed files (MP3, AVI, JPG, etc.) to initiate symbolic execution.

The experiment yielded significant results:

  • Bug Discovery: SmartFuzz found 77 total distinct bugs across the test suite.
  • Performance: On mplayer, SmartFuzz discovered 22 bugs, outperforming the popular black-box fuzzer zzuf, which found 13.
  • Scalability: The Metafuzz infrastructure processed over 2.3 million test cases and 2,614 test runs.
  • Cost-Effectiveness: The entire experiment on Amazon EC2 cost approximately $172.80, averaging out to $2.24 per unique bug found.

5. Conclusion

SmartFuzz demonstrates that combining symbolic execution with automated triage is a practical and cost-effective way to find deep-seated integer bugs in real-world binaries. While the tool faces challenges common to symbolic execution, such as path explosion and simplified memory modeling, its ability to reconstruct type information and scale in the cloud makes it a powerful asset for security researchers. Many of the bugs identified during this study have since been confirmed and fixed by software developers.

Summary updated

BibTeX
@inproceedings{molnar2009dynamic,
  author = {David Molnar and Xue Cong Li and David A. Wagner},
  title = {{Dynamic Test Generation to Find Integer Bugs in x86 Binary Linux Programs}},
  booktitle = {USENIX Security},
  year = {2009},
  url = {https://openreview.net/forum?id=PkKh9a7Wwa},
}
Figure