TL;DR
This paper introduces TaintScope, a novel fuzzing system designed to overcome a common hurdle in security testing: checksums. By intelligently identifying and bypassing checksum checks, TaintScope significantly improves the effectiveness of fuzzing, leading to the discovery of numerous previously unknown vulnerabilities in widely used software.
What Problem Does This Paper Address?
Fuzz testing is a powerful technique for finding software vulnerabilities by feeding programs with malformed inputs. However, a major challenge arises when programs use checksums to verify input integrity. Traditional fuzzers often fail because most generated inputs are rejected early on if they don't pass these checksums. This is especially problematic for complex input formats where checksums are crucial for data validation. Existing whitebox fuzzing techniques, while advanced, struggle to automatically generate inputs that satisfy these checksum constraints, particularly for non-invertible checksum algorithms. This paper tackles the problem of making fuzzing effective in the presence of checksums, a common but difficult obstacle.
Methods
TaintScope combines three key techniques:
- Checksum-Aware Fuzzing: This is the core innovation. TaintScope first identifies checksum check points in the program using dynamic taint analysis. It then modifies the program to bypass these checks, allowing malformed inputs to proceed further into the program's execution.
- Taint-Based Fuzzing: TaintScope uses fine-grained, byte-level taint analysis to identify "hot bytes" – input bytes that significantly influence security-sensitive operations (like system calls). Instead of randomly mutating the entire input, TaintScope focuses on modifying these hot bytes with random or boundary values, making fuzzing more efficient.
- Symbolic-Execution-Based Fuzzing: For test cases that crash the modified program (after checksum bypass), TaintScope uses dynamic symbolic execution. It replays the execution trace, treats the checksum fields as symbolic values, and uses a solver to determine the correct checksum value. This allows TaintScope to repair malformed inputs so they can pass the original checksum checks, confirming the vulnerability.
Datasets
The paper evaluates TaintScope on a variety of real-world applications and file formats, including:
- Image Formats: PNG, TIFF, JPEG, GIF, BMP
- Network Protocols: PCAP (for TCP/IP packets)
- Archive Formats: Tar
- Data Formats: Intel HEX, CVD (ClamAV Virus Database), VCDIFF
The authors do not introduce new benchmark datasets but rather use existing applications and file formats to demonstrate TaintScope's effectiveness.
Key Insights and Ideas
- Checksums are a significant bottleneck for fuzzing: The paper clearly demonstrates how checksums can render traditional fuzzing ineffective by prematurely rejecting most generated inputs.
- Taint analysis is key to identifying critical input bytes: By pinpointing "hot bytes," TaintScope can focus its mutation efforts, drastically reducing the search space and increasing the likelihood of triggering vulnerabilities.
- Bypassing checksums is crucial for deeper analysis: TaintScope's ability to identify and temporarily disable checksum checks allows malformed inputs to reach more complex code paths, uncovering vulnerabilities that would otherwise remain hidden.
- Symbolic execution can repair malformed inputs: The combination of concrete and symbolic execution allows TaintScope to fix checksums in crashing test cases, confirming that the crash is not due to a failed checksum but a genuine vulnerability.
- Checksum-aware fuzzing is highly effective: The system's success in finding numerous previously unknown vulnerabilities highlights the importance of addressing this specific challenge.
Key Results
- TaintScope successfully located checksum check points in various programs and file formats.
- The system identified 30 previously unknown vulnerabilities in widely used applications, including Microsoft Paint, Adobe Acrobat, Adobe Flash Player, Google Picasa, ImageMagick, and Libtiff.
- Many of these vulnerabilities were confirmed by Secunia and oCERT and assigned CVE identifiers.
- Taint-based fuzzing significantly reduced the number of "hot bytes" in well-formed inputs (typically less than 50 bytes out of thousands), demonstrating its efficiency.
- Symbolic-execution-based fuzzing, while slower, was effective in finding subtle vulnerabilities and repairing checksums.
Limitations and Future Work
- Secure Integrity Checks: TaintScope cannot currently deal with highly secure integrity schemes like keyed cryptographic hash algorithms or digital signatures, as it's impossible to automatically generate valid signatures. The authors suggest disabling such defenses during testing.
- Encrypted Data: The effectiveness of TaintScope might be limited when input data is encrypted. Future work could involve tracking decrypted data or combining TaintScope with techniques for identifying encryption/decryption routines.
- Multi-layered Checksums: For programs with multiple layers of checksum checks, TaintScope would need to be applied iteratively.
- Control Flow Dependencies: The current taint analysis does not instrument all x86 instructions and ignores control flow dependencies. Future work could incorporate these aspects.
- Performance of Symbolic Execution: Offline dynamic symbolic execution can be slow, especially with complex traces. While TaintScope mitigates this by focusing on hot bytes, further optimizations are always beneficial.
Summary updated