Fafnir: Type Inference Based Static Rewriting
Primary Investigator:
Mathias Payer
Sushant Dinesh, Lovepreet Singh, Mathias Payer
Abstract
Static binary rewriting modifies executables to en-
able, e.g., hot-patching vulnerabilities, retrofitting protections,
or the removal of unneeded functionality to reduce attack
surface. Current static rewriting techniques are limited to small
binaries, of the order of a few kilobytes, and do not scale to
real world software.
We propose a set of systematic, scalable analysis techniques
to statically rewrite binaries with zero runtime overhead
and memory footprint. To reflow code, absolute addresses
hardcoded in the binary must be converted to symbols – a
process termed symbolization. To distinguish pointer types
from scalar data types, we introduce a lightweight data-flow
analysis that identifies and propagates coarse-grained type
information. Unlike previous approaches based on heuristics,
our analysis is principled and marks a constant as pointer type
only if the value flows to a memory dereference. Constants
marked as pointer types are replaced by symbols, resulting in
a symbolized assembly file. After arbitrary modifications this
file is ready to be assembled by any off-the-shelf assembler.
We implement the analysis in a tool named Fafnir and
evaluate it on several Linux x86-64 binaries ranging from
the SPEC CPU2006 benchmarks, the nginx webserver, to the
binutils/coreutils. Fafnir correctly identifies symbols with
perfect (100%) accuracy across all our tests. The reassembled
binaries show no degradation in performance or memory
usage. Finally, to show practical utility of Fafnir we present
several case studies where we patch known vulnerabilities in
real world binaries without breaking functionality.