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 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
memcpylengths 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 fuzzerzzuf, 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