Theses Doctoral

Improving Security Through Egalitarian Binary Recompilation

Williams-King, David Christopher

In this thesis, we try to bridge the gap between which program transformations are possible at source-level and which are possible at binary-level. While binaries are typically seen as opaque artifacts, our binary recompiler Egalito (ASPLOS 2020) enables users to parse and modify stripped binaries on existing systems. Our technique of binary recompilation is not robust to errors in disassembly, but with an accurate analysis, provides near-zero transformation overhead.

We wrote several demonstration security tools with Egalito, including code randomization, control-flow integrity, retpoline insertion, and a fuzzing backend. We also wrote Nibbler (ACSAC 2019, DTRAP 2020), which detects unused code and removes it. Many of these features, including Nibbler, can be combined with other defenses resulting in multiplicatively stronger or more effective hardening. Enabled by our recompiler, an overriding theme of this thesis is our focus on deployable software transformation. Egalito has been tested by collaborators across tens of thousands of Debian programs and libraries.

We coined this term egalitarian in the context of binary security. Simply put, an egalitarian analysis or security mechanism is one that can operate on itself (and is usually more deployable as a result). As one demonstration of this idea, we created a strong, deployable defense against code reuse attacks. Shuffler (OSDI 2016) randomizes function addresses, moving functions periodically every few milliseconds. This makes an attacker's job extremely difficult, especially if they are located across a network (which necessitates ping time) -- JIT-ROP attacks take 2.3 to 378 seconds to complete. Shuffler is egalitarian and defends its own code and target code simultaneously; Shuffler actually shuffles itself.

We hope our deployable, egalitarian binary defenses will allow others to improve upon state-of-the-art and paint binaries as far more malleable than they have been in the past.


  • thumnail for WilliamsKing_columbia_0054D_16397.pdf WilliamsKing_columbia_0054D_16397.pdf application/pdf 1.21 MB Download File

More About This Work

Academic Units
Computer Science
Thesis Advisors
Yang, Junfeng
Ph.D., Columbia University
Published Here
March 8, 2021