UC Berkeley

C, C++ and most other popular low-level languages delegate memory management to the programmer, frequently resulting in bugs. Accordingly, a longstanding problem in computer security is efficient, backwards-compatible prevention of the data and control-flow exploits that arise from writing past the end of a buffer or using memory after it has been freed.

In the first part of this dissertation, we consider protection schemes against the most popular form of control-flow hijacking: return-oriented programming (ROP), which depends on misusing RET instructions. Control-flow defenses against ROP either use strict, expensive, but strong protection against redirected RET instructions with shadow stacks or other dual-stack schemes, or much faster but weaker protections without. We study the inherent overheads of shadow stack schemes (~10%). We then design a new scheme, the parallel shadow stack, with significantly less overhead (~3.5%) and better compatibility. Our measurements suggest it will not be easy to further improve software-only shadow stack performance on current x86 processors, due to inherent costs associated with RET and memory load/store instructions.

Next, we consider defenses against heap use-after-free, which is an increasingly important class of memory safety errors. We show that, in principle, page permissions should be the most desirable approach. We then validate this experimentally by designing, implementing, and evaluating Oscar, a new protection scheme based on page permissions. Oscar does not require source code, is compatible with standard and custom memory allocators, works correctly with programs that fork, and performs favorably --- often by more than an order of magnitude --- compared to recent proposals: overall, it has similar or lower runtime overhead, and lower memory overhead than competing systems.

Yesteryear's page-permissions-based allocators, including Oscar, all place one object per virtual page, to allow physical memory to be reclaimed as soon as the object is freed. We revisit this principle in Oscar++: we place multiple objects per page, with a secure quarantine for freed objects on pages that still have other live objects, and efficient inline metadata. On average, this more than halves the overhead for allocation-intensive benchmarks. We also consider the use of object lifetime, to prevent comingling of short-lived and long-lived objects on the same virtual page; this shows some promise for reducing memory overhead from quarantine.

In the last chapter, we conclude with some lessons and common themes from the three projects.