  Binary rewriting is a rapidly-maturing technique for modifying software for
instrumentation, customization, optimization, and hardening without access to
source code. Unfortunately, the practical applications of binary rewriting
tools are often unclear to users because their limitations are glossed over in
the literature. This, among other challenges, has prohibited the widespread
adoption of these tools. To address this shortcoming, we collect ten popular
binary rewriters and assess their generality across a broad range of input
binary classes and the functional reliability of the resulting rewritten
binaries. Additionally, we evaluate the performance of the rewriters themselves
as well as the rewritten binaries they produce.
  The goal of this broad evaluation is to establish a shared context for future
research and development of binary rewriting tools by providing a state of the
practice for their capabilities. To support potential binary rewriter users, we
also identify input binary features that are predictive of tool success and
show that a simple decision tree model can accurately predict whether a
particular tool can rewrite a target binary. The binary rewriters, our corpus
of 3344 sample binaries, and the evaluation infrastructure itself are all
freely available as open-source software.
