Retrowrite: Statically Instrumenting COTS Binaries for Fuzzing and Sanitization

End users of closed-source software currently cannot easily analyze the security

of programs or patch them if flaws are found. Notably, end users can include devel

opers who use third party libraries. The current state of the art for coverage-guided

binary fuzzing or binary sanitization is dynamic binary translation, which results

in prohibitive overhead. Existing static rewriting techniques cannot fully recover

symbolization information, and so have difficulty modifying binaries to track code

coverage for fuzzing or add security checks for sanitizers.

The ideal solution for adding instrumentation is a static rewriter that can intel

ligently add in the required instrumentation as if it were inserted at compile time.

This requires analysis to statically disambiguate between references and scalars, a

problem known to be undecidable in the general case. We show that recovering this

information is possible in practice for the most common class of software and li

braries: 64 bit, position independent code. Based on our observation, we design a

binary-rewriting instrumentation to support American Fuzzy Lop (AFL) and Address

Sanitizer (ASan), and show that we achieve compiler levels of performance, while re

taining precision. Binaries rewritten for coverage-guided fuzzing using RetroWrite

are identical in performance to compiler-instrumented binaries and outperforms the

default QEMU-based instrumentation by 7.5x while triggering more bugs. Our im

plementation of binary-only Address Sanitizer is 3x faster than Valgrind memcheck,

the state-of-the-art binary-only memory checker, and detects 80% more bugs in our

security evaluation.