  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-5X 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 remove 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.
