PTrix: Efficient Hardware-Assisted Fuzzing for COTS Binary

Yaohui Chen, Dongliang Mu, Jun Xu, Zhichuang Sun, Wenbo Shen, Xinyu Xing, Long Lu, Bing Mao

TL;DR

This paper introduces PTRIX, a novel hardware-assisted fuzzing tool that significantly speeds up binary-only fuzzing by leveraging Intel Processor Tracing (PT). PTRIX overcomes the limitations of existing PT-based fuzzers by introducing parallel trace processing and a new, path-sensitive feedback mechanism, leading to faster execution and the discovery of previously unknown vulnerabilities.

What Problem Does This Paper Address?

Fuzzing is a powerful technique for finding software bugs, especially in security-critical applications. However, when source code isn't available (common for commercial off-the-shelf or COTS software), fuzzers like American Fuzzy Lop (AFL) rely on slow binary instrumentation, often using QEMU. This "binary-only" mode can be 2-5 times slower than AFL's source-based mode. While Intel Processor Tracing (PT) offers a hardware-accelerated way to trace program execution, existing PT-based fuzzing tools have surprisingly been even slower than QEMU-AFL. The core problem identified is the inefficient extraction of code coverage information from the highly compressed PT traces, creating a bottleneck.

Methods

PTRIX tackles this challenge with three key innovations:

  • Highly Parallelized Trace Processing: Instead of processing PT traces sequentially, PTRIX uses a concurrent thread to decode PT traces in parallel with the target program's execution. An "elastic scheme" dynamically adjusts the timing of trace processing to keep it synchronized without hindering the target program.
  • Direct PT Trace Feedback: PTRIX bypasses the expensive reconstruction of traditional edge-based code coverage. Instead, it directly uses the decoded PT trace packets as feedback. This "PT-friendly feedback" is richer than simple edge coverage, capturing not just which code was executed, but also the order and combinations of execution paths.
  • Stronger, Path-Sensitive Feedback: The new feedback mechanism provides a more detailed view of program execution, akin to path guidance. This helps PTRIX explore deeper code regions and uncover bugs that edge-based coverage might miss. To manage the potentially large amount of path information, PTRIX employs techniques like limiting the number of traced branches between key points (descending path sensitivity) and using a smaller, more efficient bitmap.

Datasets

The paper evaluates PTRIX on a set of 9 commonly used benchmark programs, including libpng, libjpeg, libxml, c++filt, nm, objdump, exif+libexif, perl, and mupdf. These programs are chosen for their diversity in functionality and complexity. The authors also mention applying PTRIX to four other well-tested programs (gnu-ld, curl, nasm, and tcpdump) for vulnerability discovery. No new datasets were introduced; rather, existing programs were used to evaluate PTRIX's performance against established fuzzing techniques.

Key Insights and Ideas

  • PT is Not a Silver Bullet (Out-of-the-Box): Simply using Intel PT to capture traces and then reconstructing traditional code coverage is less efficient than QEMU-based fuzzing. The bottleneck is the trace processing and coverage extraction.
  • Path-Sensitive Feedback is Powerful: Moving beyond simple edge coverage to a more detailed path-based feedback significantly improves fuzzing effectiveness, allowing PTRIX to reach code and find bugs that AFL misses.
  • Efficiency and Effectiveness Go Hand-in-Hand: PTRIX's speedup isn't just about running faster; it enables more thorough exploration of the program's state space within a given time, leading to better bug discovery.
  • Hardware Features Need Smart Software: The paper demonstrates how to effectively leverage a hardware feature (Intel PT) by designing complementary software techniques (parallel processing, novel feedback) to overcome its inherent limitations.

Key Results

  • Speedup: PTRIX achieved an average speedup of 4.3x compared to QEMU-AFL in dry-run tests. In specific cases, it was significantly faster, with some programs running 25.8x and 54.9x faster than other PT-based fuzzers (Edge-PT and PTFuzzer).
  • Code Coverage: PTRIX generally explored code space quicker and covered more edges than QEMU-AFL over a 72-hour period across various programs.
  • Vulnerability Discovery: PTRIX identified 35 new vulnerabilities in previously well-fuzzed binaries, including 25 memory corruption bugs and 10 Denial-of-Service (DoS) flaws. 11 of these vulnerabilities were assigned CVE IDs. Many of these bugs were found due to the path-sensitive feedback, particularly those involving deep loops or recursive calls that AFL would typically miss.

Limitations and Future Work

  • Platform Dependency: PTRIX currently relies on Intel PT, which is primarily available on x86 architectures. While the authors believe the design philosophy is transferable to other architectures with similar hardware tracing capabilities (like ARM's ETM), porting would require effort.
  • Path Explosion: The path-sensitive feedback, while powerful, can lead to "path explosion," where the fuzzer generates an overwhelming number of paths and potentially exhausts bitmap entries. PTRIX mitigates this with descending path sensitivity, but it remains a challenge.
  • Future Work: The authors suggest exploring the generality of their design for other architectures and further refining techniques to manage path explosion. They also aim to continue discovering and reporting vulnerabilities found by PTRIX.

Summary updated

Abstract

Despite its effectiveness in uncovering software defects, American Fuzzy Lop (AFL), one of the best grey-box fuzzers, is inefficient when fuzz-testing source-unavailable programs. AFL's binary-only fuzzing mode, QEMU-AFL, is typically 2-5× slower than its source- available fuzzing mode. The slowdown is largely caused by the heavy dynamic instrumentation. Recent fuzzing techniques use Intel Processor Tracing (PT), a light-weight tracing feature supported by recent Intel CPUs, to re- move the need of dynamic instrumentation. However, we found that these PT-based fuzzing techniques are even slower than QEMU-AFL when fuzzing real-world programs, making them less effective than QEMU-AFL. This poor performance is caused by the slow extraction of code coverage information from highly compressed PT traces. In this work, we present the design and implementation of PTrix, which fully unleashes the benefits of PT for fuzzing via three novel techniques. First, PTrix introduces a scheme to highly parallel the processing of PT trace and target program execution. Second, it directly takes decoded PT trace as feedback for fuzzing, avoiding the expensive reconstruction of code coverage information. Third, PTrix maintains the new feedback with stronger feedback than edge-based code coverage, which helps reach new code space and defects that AFL may not. We evaluated PTrix by comparing its performance with the state- of-the-art fuzzers. Our results show that, given the same amount of time, PTrix achieves a significantly higher fuzzing speed and reaches into code regions missed by the other fuzzers. In addition, PTrix identifies 35 new vulnerabilities in a set of previously well- fuzzed binaries, showing its ability to complement existing fuzzers.
BibTeX
@inproceedings{chen2019ptrix,
  author = {Yaohui Chen and Dongliang Mu and Jun Xu and Zhichuang Sun and Wenbo Shen and Xinyu Xing and Long Lu and Bing Mao},
  title = {{PTrix: Efficient Hardware-Assisted Fuzzing for COTS Binary}},
  booktitle = {AsiaCCS},
  year = {2019},
  url = {https://openreview.net/forum?id=aakMiLKt5u},
}
Figure