rop

Return-Oriented Programming: Systems, Languages, and Applications RYAN ROEMER, ERIK BUCHANAN, HOVAV SHACHAM and STEFAN SAVAGE University of California, San Diego We introduce return-oriented programming, a technique by which an attacker can induce arbi- trary behavior in a program whose control flow he has diverted — without injecting any code. A return-oriented program chains together short instruction sequences already present in a program’s address space, each of which ends in a “return” instruction. Return-oriented programming defeats the W⊕X protections recently deployed by Microsoft, Intel, and AMD; in this context, it can be seen as a generalization of traditional return-into-libc attacks. But the threat is more general. Return-oriented programming is readily exploitable on multiple architectures and systems, and bypasses an entire category of security measures: those that seek to prevent malicious computation by preventing the execution of malicious code. To demonstrate the wide applicability of return-oriented programming, we construct a Turing- complete set of building blocks called gadgets using the standard C library from each of two very different architectures: Linux/x86 and Solaris/SPARC. To demonstrate the power of return- oriented programming, we present a high-level, general-purpose language for describing return- oriented exploits and a compiler that translates it to gadgets. Categories and Subject Descriptors: D.4.6 [Operating Systems]: Security and Protection General Terms: Security, Algorithms Additional Key Words and Phrases: Return-oriented programming, return-into-libc, W-xor-X, NX, x86, SPARC, RISC, attacks, memory safety, control flow integrity 1. INTRODUCTION The conundrum of malicious code is one that has long vexed the security community. Since we cannot accurately predict whether a particular execution will be benign or not, most work over the past two decades has instead focused on preventing the introduction and execution of new malicious code. Roughly speaking, most of this activity falls into two categories: efforts that attempt to guarantee the integrity of control flow in existing pro- grams (e.g., type-safe languages, stack cookies, XFI [Erlingsson et al. 2006]) and efforts that attempt to isolate “bad” code that has been introduced into the system (e.g., W⊕X, memory tainting, virus scanners, and most of “trusted computing”). The W⊕X protection model typifies this latter class of efforts. Under this regime, mem- ory is either marked as writable or executable, but never both. Thus, an adversary may not inject data into a process and then execute it simply by diverting control flow to that Permission to make digital/hard copy of all or part of this material without fee for personal or classroom use provided that the copies are not made or distributed for profit or commercial advantage, the ACM copyright/server notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists requires prior specific permission and/or a fee. c© 20YY ACM 0000-0000/20YY/0000-0001 $5.00 ACM Journal Name, Vol. V, No. N, Month 20YY, Pages 1–36. 2 · Ryan Roemer et al. memory, as the execution of the data will cause a processor exception. While the security community understood that W⊕X is not foolproof [Solar Designer 1997; McDonald 1999; Krahmer 2005], it was thought to be a sufficiently strong mitigation that both Intel and AMD modified their processor architectures to accommodate it and operating systems as varied as Windows Vista, Mac OS X, Linux, and OpenBSD now support it. In this paper, we present a new form of attack, dubbed return-oriented programming, that categorically evades W⊕X protections. Attacks using our technique inject no code, yet can induce arbitrary behavior in the targeted system. Instead, our technique aggregates malicious computation by linking together short code snippets already present in the program’s address space. Each snippet ends in a ret in- struction, which allows an attacker who controls the stack to chain them together. Because the executed code is stored in memory marked executable (and hence “safe”), the W⊕X technique will not prevent it from running. The organizational unit of a return-oriented attack is the gadget. Each gadget is an arrangement of words on the stack, both pointers to instruction sequences and immediate data words, that when invoked accomplishes some well-defined task. One gadget might perform a load operation, another an xor, and another a conditional branch. Once he has put together a Turing-complete collection of gadgets, an attacker can synthesize any malicious behavior he wishes. We show how to build such gadgets using short instruction sequences we find in target binaries on both the x86 and SPARC architectures — specifically, the Standard C Library on Linux and Solaris, respectively. We conjecture from our experience on two radically different platforms that any sufficiently large body of executable code on any architecture and operating system will feature sequences that allow the construction of similar gadgets. (As we discuss below, subsequent work has buttressed our conjecture.) Our paper makes four major contributions: (1) We describe efficient algorithms for analyzing a target library to recover the instruction sequences that can be used in our attack. In our x86 variant, we describe techniques to discover “unintended” sequences by jumping in the middle of other instructions. (2) Using sequences recovered from target libraries on x86 and SPARC, we describe gad- gets that allow arbitrary computation, introducing many techniques that lay the foun- dation for return-oriented programming. (3) We discuss common aspects of gadget construction and return-oriented attack struc- turing and injection across two popular architectures. (4) We demonstrate the applicability and power of our techniques with a generic gadget exploit language and compiler that simplify the creation of general-purpose return- oriented programs. We challenge the flawed, but pervasive, assumption that preventing the introduction of malicious code is sufficient to prevent the introduction of malicious computation. By means of return-oriented programming, an attacker who has subverted the control flow of a program can induce arbitrary computation, without injecting any code. Because it ap- plies to two very different architectures and can be abstracted and automated into a general programming framework, we argue that return-oriented programming is a usable, power- ful (Turing-complete), generally applicable threat to systems assumed to be protected by W⊕X and other code-injection defenses. ACM Journal Name, Vol. V, No. N, Month 20YY. Return-Oriented Programming · 3 Previous publication. Two extended abstracts by the present authors introduced return- oriented programming on the x86 [Shacham 2007] and SPARC [Buchanan et al. 2008]. The present full paper (with its Web-only appendix) supersedes both these previous publi- cations and is intended to be the definitive statement on return-oriented programming. Return-oriented programming, 2007–2011. Much work has followed up the conference publications that make up the present paper. Besides the x86 and SPARC, return-oriented programming has been extended to the Atmel AVR [Francillon and Castelluccia 2008], PowerPC [Lidner 2009], Z80 [Checkoway et al. 2009], and ARM [Kornau 2010] architec- tures. Gadget creation has been partly automated [Roemer 2009; Hund et al. 2009; Dullien et al. 2010; Schwartz et al. 2011]. Return-oriented programming has been used to attack platforms where W⊕X cannot be disabled, including the Sequoia AVC Advantage voting machine [Checkoway et al. 2009] and the iPhone [Iozzo and Miller 2009; Naraine 2010]. Defenses have been proposed to return-oriented programming that depend on its use of return instructions [Davi et al. 2009; Chen et al. 2009; Francillon et al. 2009; Li et al. 2010; Davi et al. 2011]; these are defeated by a variant of return-oriented programming that uses no return instructions [Checkoway et al. 2010]. More comprehensive defenses remain unbroken [Onarlioglu et al. 2010], but approach control-flow integrity [Erlingsson et al. 2006] in complexity. In an important development, return-oriented programming has been embraced by the industrial security community. Much work on return-oriented programming is being con- ducted outside of traditional academic venues (e.g., [Dai Zovi 2010; Iozzo et al. 2010; Le 2010]), and return-oriented support has been incorporated into commercial tools such as Immunity Debugger [Heelan 2010]. 2. BACKGROUND: ATTACKS AND DEFENSES With return-oriented programming, an attacker who has diverted a program’s control flow can induce it to undertake arbitrary behavior without introducing any new code. This makes return-oriented programming a threat to any defense that works by ruling out the injection of malicious code. A notable example of this class of defense is “W⊕X,” widely deployed on desktop operating systems to make memory errors more difficult to exploit. In this section, we focus on the implications of return-oriented programming on W⊕X as the natural next step in a series of attacks and defenses whose history we recall here. In particular, return-oriented programming can be seen as a generalization and refinement of return-into-libc attacks in which the attacker’s power is increased at the same time that the assumptions made about the exploited environment are reduced. Consider an attacker who has discovered a vulnerability in some program and wishes to exploit it. Exploitation, in this context, means subverting the program’s control flow so that it performs attacker-directed actions with its credentials. The most familiar such vulnera- bility class is the stack buffer overflow [Aleph One 1996], though many other classes of have been considered, such as buffer overflows on the heap [Solar Designer 2000; Anony- mous 2001; Kaempf 2001], integer overflows [Zalewski 2001; Horovitz 2002; blexim 2002], and format string vulnerabilities [Scut/team teso 2001; gera and riq 2001]. To achieve his goal, the attacker must (1) subvert the program’s control flow from its normal course, and (2) redirect the program’s execution. In traditional stack-smashing attacks, an attacker completes the first task by overwriting a return address on the stack, so that it points to code of his choosing rather than to the function that made the call. (Though ACM Journal Name, Vol. V, No. N, Month 20YY. 4 · Ryan Roemer et al. even in this case other techniques can be used, such as frame-pointer overwriting [klog 1999].) He completes the second task by injecting code into the process image; he points the modified return address on the stack to this code. For historical reasons, appropriate code to inject is called shellcode, whether or not it spawns a shell. In this paper, we restrict our attention to the attacker’s second task above. There are many security measures designed to mitigate against the first task — each aimed at a spe- cific class of attacks such as stack smashing or heap overflows — and we briefly consider their implications for return-oriented programming in Section 2.2. An important defenders’ gambit focused on making the attacker’s second task harder. The earliest iterations of such a defense, notably Solar Designer’s StackPatch [Solar De- signer 1998], modified the memory layout of executables to make the stack non-executable. Since in stack-smashing attacks the shellcode was typically injected onto the stack, this was already useful. A more complete defense, dubbed “W⊕X,” ensures that no memory location in a process image is marked both writable (“W”) and executable (“X”). With W⊕X, there is no location in memory into which the attacker can inject code to execute. The PaX project has developed a patch for Linux implementing W⊕X [PaX Team 2003b]. Similar protections are included in recent versions of OpenBSD. AMD and Intel recently added to their processors a per-page execute disable (“NX” in AMD parlance, “XD” in Intel parlance) bit to ease W⊕X implementation, and Microsoft Windows (as of XP SP2) implements W⊕X — which Microsoft called “DEP” — on processors with NX/XD sup- port. The attackers responded to code injection defenses by reusing code already present in the process image they were attacking. (It was Solar Designer who first suggested this approach [Solar Designer 1997].) The standard C library, libc, was the usual target, since is loaded in nearly every Unix program and contains routines of the sort that are useful for an attacker (e.g., wrappers for system calls). Such attacks are therefore known as return- into-libc attacks. However, in principle any available code, either from the program’s text segment or from a library to which it links, could be used. By carefully arranging values on the stack, an attacker can cause an arbitrary function to be invoked, with arbitrary arguments. In fact, he can cause a series of functions to be invoked, one after the other [Nergal 2001]. Why, then, did W⊕X see widespread deployment despite the existence of return-into- libc attacks? Perhaps the perception was that it would raise the bar for successful exploita- tion; or perhaps because only straight-line return-into-libc exploits had been demonstrated; or perhaps because it was thought possible to weaken the attacker by removing certain functions from libc. As we show, this perception is false: Return-oriented programming generalizes return-into-libc to allow arbitrary (Turing complete) computation, without call- ing any functions. 2.1 What Is Not Our Contribution Since the publication of the original paper on return-oriented programming, many re- searchers have begun referring to all exploits that reuse existing program code, including traditional return-into-libc attacks, as return-oriented programming.1 This makes some sense: these exploits all leverage control of the stack to run existing code sequences of the attacker’s choosing, usually chained together with the “return” instruction. But if return- 1Alex Sotirov, in personal communication, August 2009. ACM Journal Name, Vol. V, No. N, Month 20YY. Return-Oriented Programming · 5 into-libc attacks and the like are return-oriented programming, then it no longer correct to say that we introduced return-oriented programming. Clearly, exploitation that leverages control of the stack to execute existing code rather than injecting new code dates back to 1997 at least, with Solar Designer’s work [Solar De- signer 1997]. Chaining several libc function calls together was demonstrated for SPARC by McDonald in 1999 [McDonald 1999] and by Newsham [Newsham 2000] and then Ner- gal [Nergal 2001] for the x86. Newsham [Newsham 1997] and, later, dark spyrit [dark spyrit 1999], pioneered the use of short instruction sequences in addition to libc func- tions; Krahmer, in 2005 [Krahmer 2005], was the first to use short instruction sequences exclusively. Gera [Richarte 2000; 2001] even showed how to use such ideas to obtain un- conditional loops. As McDonald [McDonald 1999] showed, these techniques are usually sufficient to exploit W⊕X platforms: a first stage, return-into-libc style, loads and runs new machine code in an executable segment, by means of a call to mprotect (on Unix) or VirtualProtect (on Windows). On platforms that allow the protection associated with memory regions to be changed in this way, McDonald’s technique is a natural choice for the attacker. Turing complete- ness in the return-oriented first stage is not necessary: the machine code run in the second stage is, of course, Turing complete. Our contribution is in showing that Turing com- pleteness can be achieved without code injection. This has theoretical interest as an argu- ment against defenses such as W⊕X. But it has practical interest only on those platforms where memory protections are immutable, such as the Sequoia AVC Advantage voting ma- chine [Checkoway et al. 2009] and the iPhone [Miller and Iozzo 2009]. On less esoteric platforms, Turing completeness without code injection is irrelevant as a practical matter; and if “return-oriented programming” (meaning code reuse) is employed in exploits for these platforms it is Solar Designer, Newsham, McDonald, Gera, Nergal, and Krahmer who should get the credit, not we. 2.2 Mitigations We briefly consider some proposed mitigations against memory error exploitation and their effects on return-oriented programming. Traditional stack-smashing protection on the x86, in a line of work starting with StackGuard [Cowan et al. 1998] and including ProPolice [Etoh and Yoda 2001] and the Microsoft C compiler’s “/GS” flag, provides a defense orthogonal to W⊕X: preventing subversion of a program’s control flow with typ- ical buffer overflows on the stack. Although these defenses do limit many buffer overflow exploits, there are known circumvention methods [Bulba and Kil3r 2000]. And, as we note in Section 4.2, stack smashing is not necessary for a return-oriented attack. Address-space layout randomization (ASLR) [PaX Team 2003a] is another relevant and widely deployed defense. When an attack requires knowledge of addresses in the target program image, it is defeated by ASLR — at least barring brute force search [Shacham et al. 2004], partial address overwrites [Durden 2002], and information disclosure [Blaza- kis 2010]. This applies to code-injection and code-reuse attacks equally well; assuming ef- fective ASLR, the presence or absence of W⊕X is irrelevant. (For return-oriented exploits it often suffices to draw on a single library as an instruction corpus. In ASLR as deployed only the basepoint of each library is randomized, meaning that return-oriented exploits require no more address information to pull off than traditional return-into-libc exploits.) The SPARC traps into the kernel when a register window must be restored from the stack, giving an opportunity for SPARC-specific defensive measures. A notable example ACM Journal Name, Vol. V, No. N, Month 20YY. 6 · Ryan Roemer et al. is StackGhost [Frantzen and Shuey 2001], which implements extra kernel-level stack return address checks on OpenBSD 2.8 for SPARC. Finally, control-flow integrity [Erlingsson et al. 2006; Abadi et al. 2009] systems can provably prevent a program’s control-flow from being hijacked, at a runtime overhead that is likely acceptable for many applications. One way of interpreting the results in this paper is that mitigations like W⊕X that are not accompanied by security proofs can provide less security than their designers intended. We believe that control-flow integrity and other principled defenses ought to see wider adoption. 3. THE X86 AND SPARC ARCHITECTURES We present implementations of return-oriented exploits on two extremely different archi- tectures: the Intel x86 and the Sun SPARC architectures. The two architectures differ in ways that are fundamental to the particulars of return-oriented attack implementation. One has variable-length instructions that need not be aligned in memory, and the other requires fixed-length aligned instructions; one has many diverse, complex instructions, while the other has a concise set of simple instructions; one features very few general-purpose regis- ters, while the other has so many general-purpose registers that it even uses them to store function return addresses and stack and frame pointers. We present the relevant features of each architecture, both to highlight their differences and to assist in the understanding of the mechanics of each exploit implementation. 3.1 The x86 Architecture Intel’s x86 or IA-32 architecture is a descendant of the instruction set of the 16-bit 8086 processor that