Securing Binary Programs Without Perfect Disassembly

This dissertation introduces several approaches to improving the security, performance, and generality of binary software without source code. These source-free approaches have the advantage of being applicable to closed-source software products, which constitute the majority of software today. Many such products suffer from security vulnerabilities, performance issues in certain deployment contexts, or insufficient generality to address specialized consumer needs. Since such software is typically distributed in purely binary form, it is difficult to improve or repurpose its code via alternative approaches that analyze and modify source code. Unfortunately, binary code is much more difficult to analyze and modify than source code, due in part to the general undecidability of perfectly disassembling raw bytes to instruction sequences. Implementing critical fixes and improvements to mission-critical legacy software, or software from vendors unwilling or unable to implement functionality or security patches, therefore demands new methodologies for modifying binary code without the assistance of sources. Three systems are presented that address several of these challenges. The first system, SgxElide, increases the confidentiality of code in SGX binaries by encrypting SGX enclave contents without knowing the contents of the encrypted functions. SgxElide leverages a whitelist of all essential functions to encrypt all the bytes in an enclave other than those in essential functions for runtime enclave decryption. The second system, Multiverse, introduces the concept of superset disassembly, a disassembly algorithm that elegantly sidesteps the problem of obtaining accurate disassembly by obtaining a superset of all possible instruction sequences. This allows for the construction of a static binary rewriting framework that does not rely on any heuristics for binary rewriting. The third system, Miniverse, builds on the ideas of Multiverse to provide binary rewriting for dynamically generated code using superset disassembly. Finally, this dissertation provides an argument that superset disassembly is unsuitable for runtime re-randomization, and why its apparent benefits are actually counterproductive for re-randomization.