Document Type



Doctor of Philosophy


Computer Science

First Adviser

Tan, Gang

Other advisers/committee members

Chuah, Mooi-Choo; Spear, Michael F.; McCamant, Stephen


Control-Flow Integrity (CFI) is effective at defending against prevalent control-flow hijacking attacks. CFI extracts a control-flow graph (CFG) for a given program and instruments the program to respect the CFG. Specifically, checks are inserted before indirect branch instructions. Before these instructions are executed during runtime, the checks consult the CFG to ensure that the indirect branch is allowed to reach the intended target. Hence, any sort of control-flow hijacking would be prevented.However, CFI traditionally suffered from several problems that thwarted its practicality. The first problem is about precise CFG generation. CFI’s security squarely relies on the CFG, therefore the more precise the CFG is, the more security CFI improves, but precise CFG generation was considered hard. The second problem is modularity, or support for dynamic linking. When two CFI modules are linked together dynamically, their CFGs also need to be merged. However, the merge process has to be thread-safe to avoid concurrency issues. The third problem is efficiency. CFI instrumentation adds extra instructions to programs, so it is critical to minimize the performance impact of the CFI checks. Fourth, interoperability is required for CFI solutions to enable gradual adoption in practice, which means that CFI-instrumented modules can be linked with uninstrumented modules without breaking the program.In this dissertation, we propose several practical solutions to the above problems. To generate a precise CFG, we compile the program being protected using a modified compilation toolchain, which can propagate source-level information such as type information to the binary level. At runtime, such information is gathered to generate a relatively precise CFG. On top of this CFG, we further instrument the code so that only if a function’s address is dynamically taken can it be reachable. This approach results in lazily computed per-input CFGs, which provide better precision. To address modularity, we design a lightweight Software Transactional Memory (STM) algorithm to synchronize accesses to the CFG’s data structure at runtime. To minimize the performance overhead, we optimize the CFG representation and access operations so that no heavy buslockinginstructions are needed. For interoperability, we consider addresses in uninstrumented modules as special targets and make the CFI instrumentation aware of them. Finally, we propose a new architecture for Just-In-Time compilers to adopt our proposed CFI schemes.