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