UC San Diego

This thesis investigates the pervasiveness and widespread applicability of "return-oriented programming" ---- an exploit technique whereby W\[oplus\]W system protections are evaded by careful stack injections (without code) that cause a vulnerable program to execute pre-existing sequences of runtime code, which in the aggregate form arbitrary computations. In this thesis, we demonstrate that this attack is not limited to the x86 architecture, its original platform of introduction, and can be fully implemented on an architecture as completely different as SPARC. We present automated search tools that effectively and efficiently find full or partially Turing-complete return-oriented "gadget" sets in arbitrary binaries using a dedicated and extensible query language. We discuss our results from searching thousands of previously unknown binaries and find that potentially exploitable return- oriented gadgets are prevalent in the wild. Finally, we pose that the risks from return-oriented programming are fundamental and general --- our data indicates that the threat of finding a Turing-complete gadget set in an arbitrary binary is correlated simply with instruction count, and not any unique or special aspects of the target program.