String Oriented Programming: When ASLR is not Enough

Mathias Payer Thomas R. Gross

Department of Computer Science Department of Computer Science
ETH Zurich, Switzerland ETH Zurich, Switzerland

Abstract ble due to Data Execution Prevention (DEP), which prohibits

Control-data attacks are a well known attack vector; these the CPU from executing instructions on non-code memory
attacks either inject new code into running applications or pages. DEP uses the executable bit for memory pages in
reuse existing code in an unintended way to execute their modern CPUs to enable non-executable data regions (i.e., the
malicious payload. stack and the heap of the application). A stronger guarantee
Current software systems are protected against control- is W ⊕ X which ensures that a page is either writable or ex-
data attacks using numerous mechanisms like Data Execu- ecutable but not both. Linux uses an W ⊕ X approach called
tion Prevention (DEP), stack canaries, and Address Space Exec Shield [26]. Second, canaries [15] (variables with spe-
Layout Randomization (ASLR). ASLR turns deterministic cial values) are placed next to buffers on the stack or on the
attacks into probabilistic attacks and reduces the probabil- heap and their values are validated to protect the application
ity of a successful attack. Unfortunately, the current ASLR from buffer overflows. Third, Address Space Layout Ran-
implementation for Linux leaves some memory regions non- domization [4, 5, 18] (ASLR) is a probabilistic protection
randomized. These static memory regions can be used to ex- that randomizes the locations of code, stack, heap, and other
ploit applications that have ASLR, DEP, and stack canaries data.
enabled. On the other hand, Return Oriented Programming [20]
Format string exploits are an often overlooked attack vec- (ROP) and Jump Oriented Programming [7] (JOP) are two
tor that enables attacker-controlled memory writes in an ap- modern attack techniques that no longer rely on injected ex-
plication. A format string bug exists if a user-supplied string ecutable code but reuse existing application code. ROP uses
is passed as a first argument to any printf function. The only so-called stack invocation frames to combine different al-
prerequisite for a successful format string exploit is that the ready existing code snippets. In addition, ROP relies on an
attacker must be able to control that format string. unchecked application stack: return addresses must not be
This paper presents String Oriented Programming (SOP), verified. Modern runtime guards (e.g., libdetox [19]) use a
an approach that exploits static memory regions in ASLR en- separate shadow stack to check return addresses and there-
abled applications. SOP uses a format string bug to exploit fore prohibit ROP based attacks. JOP based attacks gener-
applications that are protected by a combination of weak alize ROP attacks by exploiting any attacker-controlled in-
ASLR, DEP, and stack canaries. Similar to return oriented direct control flow instruction and are more complicated to
programming or jump oriented programming, SOP does not protect against. A runtime system either checks the integrity
rely on existing code but concatenates gadgets in the appli- of every dynamic control flow instruction or the compiler
cation using static program analysis. ensures that no open dynamic control flow instructions (e.g.,
jmp *%eax; an indirect jump through the eax register) are
available in the compiled source (e.g., CFI [1] or XFI [11]).
1. Introduction
Both ROP and JOP rely on well-known code locations
Software running on current computer systems is protected to be effective (i.e., either on non-randomized code regions
against a wide variety of control-data attacks using three pro- or on information leaks in the application that disclose code
tection mechanisms. First, code injection is no longer possi- locations); in addition ROP relies on constant, well-known
stack addresses and JOP relies on constant, well-known heap
data locations.
Permission to make digital or hard copies of all or part of this work for personal or
Unfortunately, the current ASLR implementation for
classroom use is granted without fee provided that copies are not made or distributed Linux [18] randomizes only the locations of the stack, the
for profit or commercial advantage and that copies bear this notice and the full citation
on the first page. To copy otherwise, to republish, to post on servers or to redistribute
heap, and the code and data locations of all dynamically
to lists, requires prior specific permission and/or a fee. loaded libraries; the main executable itself is often not ran-
PPREW ’13 Jan 26, 2013 Rome, Italy domized. Most applications on Linux are not compiled as
Copyright c 2013 ACM 978-1-4503-1857-0/13/01. . . $15.00
Position Independent Executables (PIE) and are mapped to vented by using either ROP or JOP. To add realism to this
a static memory address (currently, only 27 out of all bi- discussion, this paper focuses on IA32 and Linux but the
naries on Ubuntu 11.10 are compiled as PIE). Static code discussed technique applies to, e.g., Windows and x86-64 as
regions create an opportunity for ROP and JOP. The com- well.
bination of writable sections (e.g., the Global Offset Table -
GOT1 ), indirect control flow transfers (e.g., in the Procedure 2. Building blocks for String Oriented
Linkage Table - PLT2 ), and gadgets in the static application Programming (SOP)
can be used to break ASLR. A gadget is a sequence of as-
SOP relies on an existing format string bug in an application
sembler instructions (not necessarily a function) that already
and escalates to any possible control-data attack (code injec-
exists in the memory image of the application and executes
tion) or non-control-data attack (this paper uses either ROP
some specific computation that is valuable to the attacker.
or JOP as examples). This section introduces the different
One different class of bugs has not yet received ade-
building blocks needed to set up SOP and relates these at-
quate attention in the context of DEP, stack canaries, and
tack vectors to protection mechanisms that are the security
ASLR: format string vulnerabilities. If an attacker controls
standard of current applications.
the first parameter to a function of the printf family, the
string is parsed as a format string. Using such a bug and 2.1 Attack vectors
special format markers result in arbitrary memory writes.
This section describes existing attack vectors that are used
Existing exploits use format string vulnerabilities to mount
to exploit an application. A successful attack (i) redirects the
stack or heap-based code injection attacks or to set up re-
control flow of the application to an alternate location that
turn oriented programming. Format string vulnerabilities are
would not be reached otherwise (i.e., new code is injected
not a vulnerability of the past but still pose a significant
into the application) or (ii) executes already existing code
threat (e.g., CVE-2012-0809 reports a format string bug in
in a different context (i.e., existing code is executed with
sudo and allows local privilege escalation; CVE-2012-1152
different - malicious - data). Both forms of attack rely on
reports multiple format string bugs in perl-YAML and al-
the following features:
lows remote exploitation, CVE-2012-2369 reports a format
string bug in pidgin-otr and allows remote exploitation) 1. The runtime environment must allow the redirection of
and usually result in full code execution for the attacker. the control flow to alternate locations using a control flow
This paper assumes the following attack model: an at- transfer instruction. Control flow transfer instructions are
tacker with restricted privileges tries to escalate privileges jump instructions, indirect jump instructions, conditional
using String Oriented Programming. The attacker has access jump instructions, call instructions, indirect call instruc-
to the binary (either because the application is open-source tions, return instructions, interrupts, and system calls. Di-
or through some information leak). The attacker is either re- rect control flow transfers encode the target in the instruc-
mote and tries to get user access, or the attacker is local and tion and cannot be used for exploits.
tries to attack a “SUID” based binary to get administrator
Indirect control flow transfers (indirect jumps, indirect
privileges. The attacker supplies specially crafted malicious
calls, and return instructions) read the absolute target ad-
input to the application to exploit a format string bug.
dress from a data region or register. An attacker can redi-
String Oriented Programming (SOP) leverages format
rect a legitimate indirect control flow transfer by control-
string vulnerabilities in combination with ROP and JOP at-
ling either the memory location or the specified register
tacks to bypass ASLR, DEP, and stack canaries. We describe
(depending on the encoding of the indirect control flow
an approach that exploits arbitrary non-PIE binaries that use
transfer). Exploits either overwrite the register with an
a combination of ASLR, DEP, and stack canaries. Stack ca-
attacker supplied value or overwrite the data region that
naries are bypassed by using attacker-controlled memory
contains the target pointer to achieve the initial control
writes that leave the canaries intact. ASLR is circumvented
flow redirection: (i) for return instructions the EIP on the
by storing exploit data in well-known locations in static
stack is overwritten, (ii) for indirect calls either a func-
memory regions; control flow is redirected by overwriting
tion pointer on the heap, a GOT entry in a shared library,
GOT slots that are used by code in the PLT. DEP is circum-
or vtable entries of objects is changed, or (iii) for indi-
1 The
rect jump instructions data-structures of the memory al-
GOT enables dynamically shared libraries. Every imported function
that is used in a module has a corresponding GOT entry. The GOT entry
locator [6] are changed.
points to the runtime address of the imported function and is resolved by 2. The exploit must inject some form of payload into the
the dynamic loader.
2 Each runtime module, e.g., a library or an executable, has a PLT that
application. Control-data attacks inject machine code in-
structions into an executable memory region of the ap-
contains function stubs for each imported function. The code in the runtime
module calls the local stub in the PLT which then redirects control flow plication. These instructions are executed after the initial
through the GOT to the dynamically resolved imported function. control flow redirection. Data-based attacks like ROP or
 JOP modify data structures of the application, a shared i n t f o o ( char ∗cmp ) {
library, or the standard loader to execute their malicious / / a s s e r t ( s t r l e n ( cmp ) < MAX LEN )
payload. char tmp [MAX LEN ] ;
s t r c p y ( tmp , cmp ) ; / / m i s s i n g bound c h e c k
An exploit is only successful if both requirements are r e t u r n s t r c m p ( tmp , ” f o o b a r ” ) ;
met. The following sections present four possible attack }
...
vectors in more detail. / / u s e r s t r i s > MAX LEN
if ( is foobar ( user str ))
2.1.1 Code injection ...
A code injection attack writes code to an executable region Listing 1. A potential stack-based overflow.
of the application’s memory image and transfers control
to that injected code [2]. Code injection attacks often use
a buffer overflow (e.g., for a C based string or array) to
Original layout After exploit
inject code and to overwrite the stored return instruction
0xff don't care
pointer on the stack in one step. Code injection attacks are no next stack frame
1st argument to system()
longer effective due to increased protection through ASLR, 1st argument: cmp* ebp after system call
DEP [26], and non-executable stacks that are enabled by return address points to &system()

length of user input

saved base pointer don't care
default on modern systems.
0xf0
Code injection is a mature attack vector that has been
used for many years. Until recently Intel IA32 did not sup- tmp don't care

port the separation of code and data and the CPU tried to garbage
0xe0
interpret any memory region as executable, enabling code
injection attacks into data regions. x64, the 64 bit exten- Figure 1. Stack before and after a ROP attack.
sion of the x86 ISA introduced an additional executable flag
for each memory page. The executable flag enables sepa-
ration of data and code. Only code on pages that have the Q [22] is a system that analyzes binaries for ROP pos-
executable flag set is executed by the CPU. If an exploit sibilities. The automatic scanning works around ASLR for
redirects control flow to a data page then an exception is non-PIE binaries but relies on a system without stack ca-
triggered. Current operating systems support some form of naries. Q is therefore not effective on Linux systems like
W ⊕ X; a memory page is either writable or executable. Ubuntu that enable ProPolice (stack canaries) by default.
Due to W ⊕ X this attack vector is only applicable if the Listing 1 shows a vulnerable C snippet that is prone to
application uses memory pages that are both writable and a stack-based buffer overflow. An attacker can inject any
executable which is not common except for (i) some old ap- data into the buffer and write over the bounds of the buffer
plications that use executable trampolines on the stack, (ii) to overwrite data structures that are higher up in the stack
misconfigured memory regions, or (iii) memory pages that frame. Figure 1 illustrates a simple return oriented program-
are used to place code that is dynamically generated by a ming attack that exploits the missing bound check in List-
just-in-time compiler. ing 1 to create one stack invocation frame that executes the
system() function with forged parameters.
2.1.2 Return Oriented Programming
Return to libc and Return Oriented Programming [16, 20, 2.1.3 Jump Oriented Programming
22] (ROP) rely on control of both the stack pointer and the Jump Oriented Programming [7, 20] (JOP) is similar to ROP
contents of a data buffer on the stack. One way to satisfy in that JOP manipulates the control flow of the application.
these preconditions is through a stack-based buffer overflow. Jump oriented data is not limited to stack overflows but
A ROP attack constructs a set of stack invocation frames uses modified indirect control flow transfers to construct the
that are popped one after the other. Each stack invocation chain of executed gadgets. Indirect control flow transfers are
frame prepares a set of parameters on the stack and targets a used in the application to support, e.g., library calls, function
gadget that uses the parameters and executes some computa- pointers (callbacks), and object oriented programming. JOP
tion. A ret2libc attack [23] is a simple ROP attack that uses has similar limitations like ROP and needs static addresses
only one stack invocation frame to execute a libc function for the gadgets and a known heap location for the JOP
(e.g., system()) with a set of attacker-controlled parame- dispatcher. In addition JOP needs to redirect control flow
ters. ROP works around DEP but relies on static addresses to the first JOP dispatcher. ASLR severely limits the initial
for the stack and for the gadgets. In addition ROP needs a redirection for JOP on current Linux systems.
way to initially redirect control flow to the first ROP invoca- Figure 2 illustrates a simple JOP dispatcher on a modified
tion frame. heap object. The dispatcher is a special gadget that uses one
register to dispatch individual JOP frames. Each JOP frame 2.2 Protection mechanisms
contains data and a pointer to a code gadget. The gadget This section discusses protection mechanisms that try to
returns control flow to the dispatcher after execution. detect possible attacks on different levels of granularity. The
protection mechanisms either (i) check the integrity of the
2.1.4 Format string attacks stack, (ii) verify library usage, (iii) encrypt pointers, (iv)
A format string attack [13, 14, 17, 21] exploits that an change the instruction set, (v) protect format strings, (vi)
attacker controls the first parameter to a function of the randomize memory locations, or (vii) check and verify every
printf-family (all functions that accept a format string as a instruction that changes control flow.
parameter, e.g., printf, fprintf, sprintf, and vprintf). Most languages place buffers and variables alongside
The printf-family parses the format string argument for with return instruction pointers and frame pointers on the
control tokens (of the form %T) to determine the number of regular application stack. Several protection mechanisms [10,
variable parameters that follow. The token determines how 15] verify the stored return instruction pointer on the stack
the output on the n-th position on the stack is formatted in the or a canary next to the instruction pointer before the return
string. Many programmers forget to check user-controlled instruction dereferences the stored address. These mecha-
strings for these control tokens and pass the string directly nisms protect from malicious changes of the return address
to the function (e.g., printf(usr str)). A safe implemen- and the stack layout.
tation would use a static parameter to pass a single string Libsafe/Libverify [3] implements wrappers for library
(e.g., printf("%s", usr str)). functions that are used in attacks. This approach protects
The malicious format string can use tokens like %p to read applications from common errors and adds extra checks to
specific pointers on the stack, and %s to read specific stack “dangerous” functions. A disadvantage of this approach is
addresses as strings. An attacker uses these parameters to get that it only protects specific functions and general patterns of
information about the application during the construction of attack vectors. The glibc has a set of similar patches that are
the format string attack. enabled if the FORTIFY SOURCE switch is enabled at com-
The %n token reverses the order of input and writes the pile time on a per-application basis. These patches check
number of already printed characters to the specified pointer. every parameter of format strings. Under certain constella-
Any argument on the stack can be used as a target address for tions the fortify patches are not secure and can be disabled
%n, e.g., %4$hn writes 2 bytes to the pointer specified 4 ∗ 4 = at runtime [21].
16 bytes upwards on the stack. The format string itself can Pointer encryption [9] is an interesting approach to pro-
be used to store pointers to specific addresses if it is placed tect instruction pointers from malicious changes. All instruc-
on the stack. The number of written bytes can be controlled tion pointers are encrypted (e.g., using a hash). The appli-
with additional parameters (e.g., printf("%NNc"); prints cation uses the encrypted pointers in all computation (e.g.,
N N bytes) and increases the counter used for %n. For exam- comparing different function pointers). The compiler adds
ple, printf("AAAA%1$49391c%6$hn") writes 0xc0f3 (2 additional code that resolves the original instruction pointer
bytes, 0xc0f 3 − 4 = 49391) to 0x41414141 if the string using the given encrypted pointer whenever it is derefer-
itself is on the 6th slot up on the stack. In this example enced. The attacker does not know the encryption function
an input string of 18 bytes length is used to generate an and therefore cannot forge a pointer to an arbitrary address.
attacker-controlled 2 byte memory write. Format string at- Instruction set randomization [12] is a similar approach. The
tacks write arbitrary values to arbitrary memory locations. application uses a randomized instruction set and an attacker
These attacker-controlled memory writes are used to, e.g., is unable to guess the instruction set.
redirect control flow to injected code. Format Guard [8] warns if format strings and functions
of the printf family are used with unchecked user input.
These guards protect the already existing functions of the
libc but do not protect from format string exploits in the
Scratch space (at static addrs) application code.
gadget address Gadget catalog (at static addrs)

(data)
insns … … jmp * Address Space Layout Randomization (ASLR) [4, 5, 18]
gadget address insns … … jmp * randomizes all memory regions of an application (e.g., dy-
(data) insns … … jmp * namically loaded libraries, heap, and stack). A potential ex-
gadget address insns … … jmp *
ploit can no longer rely on constant addresses for, e.g., li-
(data)
brary routines and gadgets. A drawback of this approach is
that the address space for 32bit binaries is small and only a
Dispatcher, e.g.,
add %edx, 4; jmp *(%edx) few bits can be randomized which opens the possibility of
probabilistic attacks [24].
Figure 2. Modified heap object after JOP attack.
 CFI/XFI [1, 11] uses static binary translation to verify 3.1 Executing code
every target of all control flow transfers. A set of targets SOP uses two scenarios to get control of the application
is associated with every control flow transfer location. The without executing injected code. The scenarios are similar
group of targets is identified with a secret number. This to either ROP or JOP. The first (simpler) scenario exploits
number is verified when the control flow transfer is executed. DEP and stack canaries, while the second scenario exploits
The control flow transfer is allowed only if the target number DEP, stack canaries, and weak ASLR.
(in the target code) matches the verification code at the
source location. 3.1.1 Direct control flow redirect
Libdetox [19] is a dynamic binary translation approach
The first code execution scenario uses an attacker-controlled
that uses runtime information to construct a control flow
memory write and a user-controlled buffer on the heap or on
graph. This control flow graph is enforced at runtime using
the stack (often the format string itself) to prepare the attack.
dynamic checks that are encoded into the translated code.
The attacker-controlled memory write redirects control flow
by overwriting the return instruction pointer on the stack to a
2.3 Weak ASLR: static regions gadget that adjusts the stack frame to the attacker-controlled
The Linux ASLR implementation [18] on x86 is limited if buffer. The buffer contains a set of invocation frames that
the application itself is not compiled as a Position Indepen- concatenate several available gadgets to execute arbitrary
dent Executable (PIE). In particular non-PIE ASLR appli- code. If the buffer is on the stack then SOP can use ROP,
cations are mapped to a constant address (this includes the if the buffer is on the heap then SOP can use JOP. This
data section, bss section, code section, GOT section, and approach combines format string exploits and ROP similar
PLT section). An application can be compiled into a PIE, to Section 7.2 of Nergal’s paper on advanced return to libc
which can then be loaded at random addresses. Linux distri- attacks [16].
butions like Ubuntu only compile a small set of binaries (27
for Ubuntu 11.10) as PIE due to a high performance penalty 3.1.2 Indirect control flow redirect
on x86 [25]. All other programs are compiled without PIE The second code execution scenario uses static data regions
and remain vulnerable in the presence of weak ASLR. in the main application to store all exploit data. Control flow
The application image starts at a specific constant address is redirected in two steps: SOP first overwrites the GOT slot
(0x0804800). The PLT and GOT regions remain constant as that is used by the PLT jump that resolves the next imported
well. The GOT region is writable; writes to a GOT slot can function (in the control flow), the application then continues
be used to store attack data at static addresses or to redirect until the next imported function is called. The PLT jump then
control flow by redirecting PLT slots to other locations. redirects the control flow to either a ROP gadget or to a JOP
dispatcher.

3. String Oriented Programming 3.2 Resolving addresses

String Oriented Programming (SOP) combines a format Without ASLR, SOP can be used to easily construct a set of
string vulnerability and ROP/JOP code-reuse techniques into invocation stack frames using direct control flow redirection
one technique that bypasses ASLR, stack canaries and DEP as in Section 3.1.1 that execute arbitrary functions of the libc
for non-PIE binaries. SOP uses gadgets that are available in (e.g., mmap to map an executable memory region, strcpy to
the code region of the application. SOP assumes that some copy the shellcode), and an indirect control flow transfer to
form of DEP is enforced by the system. Otherwise it would the injected shellcode). If (weak) ASLR is enabled, then the
be simple to inject some code and to redirect the control flow only option for an exploit is to use an indirect control flow
to the injected code. redirection as in Section 3.1.2.
Format string exploits enable attacker-controlled writes to Exploits are limited to imported library functions and
attacker-controlled addresses (encoded in the format string) code sequences available in the application. The dynamic
to any memory location that is referenced through a pointer loader resolves the dynamic locations for all imported li-
on the stack. An attacker can place arbitrary pointers in an brary functions when they are called, enabling indirect calls
attacker-controlled buffer on the stack; these pointers are of library functions through the PLT slots of the application.
then used in the format string attack to write arbitrary mem- The imported library functions in the PLT region can be
ory locations. We assume that the FORTIFY SOURCE patches used to resolve unimported and unreferenced functions. The
of the glibc are not enabled (or that we can call printf di- location of resolved library functions are stored at static
rectly). Under some assumptions the fortify patches can be addresses in the GOT region. Gadgets can read and modify
disabled using the format string attack itself or some other these addresses. If the binary of the library is known then
auxiliary attack [21]. The fortify patches only add some the (dynamic) addresses of other library functions that are
complexity (and length to the format string). not imported can be computed. The gadget adds the offset
v o i d f o o ( char ∗ a r g ) { ProPolice layout After exploit
char t e x t [ 1 0 2 4 ] ; printf data printf data
i f ( s t r l e n ( a r g ) >= 1 0 2 4 ) r e t u r n ; saved ebp saved ebp
strcpy ( text , arg ) ; Original layout eip to foo eip to lift-slide
printf ( text ); ptr to buffer ptr to buffer
printf data copy of canary &arg copy of canary &arg
puts ( ” logged in ” ) ;
} saved ebp 16b unused 16b unused
eip to foo
... ptr to buffer
canary copy of &arg canary copy of &arg
foo ( u s e r s t r ) ; copy of &arg 12b unused 12b unused
...
Listing 2. A potential format string attack …
1024b buffer
… …
1024b buffer 1024b buffer
... ... ...

... stack canary stack canary

between the imported function and the requested function to 12b unused
... 8b unused 8b unused
the resolved address in the PLT slot. This enables gadgets
saved ebp saved ebp saved ebp
to resolve any (unimported) library function whenever a eip to caller eip to caller eip to caller
&arg &arg &arg
symbol of that library is used.
… … …
? ? ?
4. SOP case study ... ... ...

The SOP case study shows how the sample program in List-
ing 2 can be exploited under different environmental con- Figure 3. Stack before and after a format string based ex-
figurations. The host system uses a set of different protec- ploit that prepares stack invocation frames and works around
tion features that are either enabled or disabled. The protec- ProPolice (blue: callee, orange: foo, green: printf).
tion features are ASLR, DEP, stack canaries[15] (protecting
the application against buffer overflows), and if specific libc
functions are already imported in the main application. The the %esp pointer into the user-controlled string. The combi-
application is compiled without PIE, i.e., the main applica- nation of gcc version 4.5.2 and libc-2.13 adds the function
tion image is mapped to a fixed address. This is the standard libc csu init to all compiled binaries; this function
configuration for Ubuntu 11.10. contains a gadget (add $0x1c,%esp; pop %ebx; pop
%esi; pop %edi; pop %ebp; ret) that lifts the %esp
4.1 Mo DEP, no ProPolice, no ASLR by 44 bytes. The format string is prepared so that it contains
If neither ASLR nor DEP are active then the format string a set of invocation frames that enable ROP at that specific
contains an attacker-controlled memory write to, e.g., the address.
return instruction pointer, a GOT slot, or a function pointer Figure 3 compares the stack layouts of Listing 2 when
to redirect control flow to the injected code on the buffer on the control flow is inside the printf function. ProPolice (i)
the stack. This attack conforms to the simple code injection adds a secure canary behind the buffer (that is checked be-
attack in Section 2.1.1. fore the return instruction pointer is dereferenced) and (ii)
copies the arguments below the buffer. The stack invocation
4.2 DEP, no ProPolice, no ASLR frames in the buffer contain sets of arguments plus return
instruction pointers to libc functions (e.g., a call to system
Exploits rely on data oriented attacks if DEP is enabled. In
would be encoded as &system; pointer to argument
this configuration a buffer overflow is the simplest solution
string). Pointers to, e.g., string arguments, can be directly
to set up a ROP attack as described in Section 2.1.2 or a JOP
encoded because the stack addresses are known due to the
attack as shown in Section 2.1.3.
missing ASLR protection.
4.3 DEP, ProPolice, no ASLR
4.4 DEP, ProPolice, ASLR, imports available
Enabling the ProPolice extension changes the threat land-
If ASLR is enabled then the stack and library addresses are
scape and buffer overflows can no longer (easily) be used
no longer constant and therefore unknown. The application
to exploit systems. ProPolice is enabled by default in recent
itself is located at a static address. In this section we assume
versions of gcc3 . On the other hand ASLR is not enabled in
that all the gadgets and all the library functions that we want
this configuration therefore a format string attack is used to
to call are imported in the main application. SOP uses the
redirect control flow (by overwriting the return instruction
same basic technique as in Section 4.3 with two differences.
pointer of the printf function itself) to a gadget that adjusts
The first difference is that the functions are not called di-
3 ProPolice
is on by default and can be disabled on request using the rectly but through their PLT slots in the application (i.e.,
-fno-stack-protector compile-time switch. the address of function is replaced by the address of
Libraries (ASLR) Application (static) Stack (ASLR) through offset calculation and GOT updating between the
RX different function calls, thereby circumventing ASLR, DEP,
.init printf stack frame
libc .plt and ProPolice.
(text, data, got) system@plt
puts@plt foo stack frame
.text 5. Possible mitigation techniques
lift_esp_gadget &system@plt
.fini &"/bin/sh\0" This section discusses two possible mitigation techniques to
heap .got:
RW protect applications from SOP. The first mitigation technique
… discusses a possible extension of ASLR to all memory seg-
.got.plt: ments of an application while the second mitigation tech-
… main stack frame
printf
&puts nique focuses on fixing the printf function.
__stack_chk_fail
"/bin/sh\0"
puts
&system 5.1 Full ASLR
Full ASLR randomizes the address layout of the main ap-
Figure 4. Static and dynamic data regions using weak
plication (including writable sections like the GOT section)
ASLR. Listing 2 is stopped after the call to printf.
as well as the layout of all libraries. A PIE application
has no static memory addresses during subsequent execu-
tions. Possible exploits techniques need additional informa-
function@PLT). The PLT section contains an entry for each tion leaks in the application that disclose the location of code
imported function. This code stub executes an indirect jump sequences as a first step.
through a corresponding GOT entry. The standard loader Current applications on IA32 use weak ASLR that is lim-
resolves the correct address for the application. SOP piggy- ited to libraries because of performance reasons. The ASLR
backs on the standard loading process to resolve the correct implementation uses an additional register as a relative code
references to randomized library functions before they are reference pointer. Registers are sparse on IA32 and the use
executed. of one of the few registers leads to a huge performance im-
The second difference is that addresses on the stack are no pact.
longer encoded directly. Any data that is used in the exploit This section supports the performance overhead claim
must first be copied to a static region in the application. SOP and presents an evaluation for the PIE feature of GCC that
uses a sequence of format string writes (or an invocation of produces position independent executables. The PIE fea-
strcpy) to prepare the static data. The invocation frames ture enables ASLR for binaries. The evaluation uses GCC
then use the well-known locations as arguments. version 4.5.2-8ubuntu on Ubuntu 11.04 with Linux ker-
Figure 4 shows a simple exploit that uses a sequence nel version 2.6.38-15-generic and glibc version 2.13. The
of three four byte writes to (i) write the 8 bytes string evaluation system uses an Intel Core i7 dual core CPU
“/bin/sh\0” into two GOT slots, (ii) overwrite the GOT clocked at 3.07 GHz with active SMP and 12GB RAM.
entry of the imported function that is called next with the lift The evaluation uses all benchmarks of the SPEC CPU2006
esp gadget that we used in Section 4.3, and (iii) prepare the v1.01 benchmark suite that compile using recent GCC ver-
beginning of the exploit string with a stack invocation frame sions. The evaluation uses two different compilation set-
that calls system trough the static address of system@PLT. tings. The benchmarks are compiled with either -O3 or -O2.
After printf returns the function would continue and try The benchmarks are executed using the runspec program
to execute puts, the next imported function in our program. and the configuration uses 3 runs.
But the PLT entry of puts is redirected to our lift esp gad- Table 1 compares SPEC CPU2006 performance for -O3
get that pops some values from the stack and returns into (the most aggressive optimization level of GCC) with and
the beginning of the format string on the stack that con- without -fPIE. We see that PIE executables are never faster
tains the ROP stack invocation frames. The ROP invocation than non-PIE executables and the overhead varies between
frame then executes system("/bin/bash"); (or any other 0.37% and 26% depending on the benchmark. The bench-
attacker-controlled payload). marks can be grouped into 4 groups: negligible overhead be-
tween 0% and 2% (4 benchmarks), small overhead up to 5%
4.5 DEP, ProPolice, ASLR, no imports available (3 benchmarks), medium overhead between 5% and 10% (5
If all protection mechanisms are enabled and the application benchmarks), and high overhead with more than 10% per-
does not import specific library functions then missing func- formance penalty (7 benchmarks).
tion addresses are resolved on the fly. Any missing imports The benchmarks with high overhead either have a highly
are resolved using the approach described in Section 3.2. irregular workload with a large amount of indirect con-
A single imported libc function allows an exploit to call trol flow transfers (400.perlbench and 458.sjeng) or process
any sequence of libc functions with arbitrary arguments streams of data (401.bzip2, 453.povray, and 482.sphinx3).
 Overhead for -fPIE
30.00%
-O3 -fPIE
-O2 -fPIE
25.00%

20.00%

15.00%
Overhead

10.00%

5.00%

0.00%
45

40

45

40

48

44

46

46

40

47

48

45

45

47

42

44

44

47

Av

Ge
43
8.s

0.p

3.p

1.b

2.s

5.g

2.l

4.h

3.g

1.o

3.x

6.h

0.s

3.a

9.m

7.d

4.n

0.l
3.m

era

o.
ibq

bm
jen

erl

ob

26

cc

mn

ala

mm

op

s ta

ea

am

Me
ov

zip

ph

ge
cf

ilc
ua
be

ray

inx

mk

4re

lex

lII
g

nc
etp

an
er
ntu
nc

bm
f

p
h

k
SPEC CPU2006 benchmark

Figure 5. Comparison of the overhead for PIE between -O2 and -O3.

Benchmark -O3 [s] -O3 -fPIE [s] Ovhd. [%] The average overhead for PIE (when compiled with O3)
400.perlbench 369 463 25.47% is 10% and the geometric mean is 9.4%. This overall non-
401.bzip2 610 713 16.89% negligible overhead is the reason why not all applications
403.gcc 308 334 8.44% are compiled with PIE. The Ubuntu distribution chooses
429.mcf 254 262 3.15% performance over the increased security benefit that PIE
445.gobmk 479 550 14.82% offers.
456.hmmer 554 584 5.42%
458.sjeng 533 671 25.89%
462.libquantum 560 624 11.43%
464.h264ref 760 829 9.08%
471.omnetpp 298 323 8.39% 5.1.1 Fixing libc
473.astar 472 492 4.24% A second possible mitigation strategy is to fix (and patch) the
483.xalancbmk 242 259 7.02% printf functions in libc. Either the %n token could be re-
433.milc 394 400 1.52% moved, or the compiler could ensure that printf may only
444.namd 536 538 0.37% access passed parameters. FormatGuard [8] already presents
447.dealII 426 431 1.17% similar mitigation strategies. Recent GCC versions execute
450.soplex 258 270 4.65% some static checks and print a warning if format strings
453.povray 244 290 18.85% can be supplied by an external user. In addition libc uses
470.lbm 327 328 0.31% FORTIFY SOURCE to execute additional runtime checks for
482.sphinx3 520 607 16.73% format strings (e.g., a format string that uses %n must be in
Average 429 472 10.12% a non-writable memory area, and if direct parameter access
Geo. mean 405 443 9.40% is used in a format string to access the n-th parameter on the
Table 1. Performance of SPEC CPU2006 for -O3 and rela- stack then all other parameters on the stack between the first
tive overhead for PIE. parameter and the n-th must be accessed as well in the same
string). Due to implementation limitations of libc (that must
support both modes with and without FORTIFY SOURCE in
a single binary) these patches can be disabled at runtime as
described in, e.g., [21].
These workloads have a high register pressure and the re- Even if the libc is fixed and all possible format string vul-
duced set of registers is the source for the high overhead. nerabilities are removed then the problem of the unrandom-
Figure 5 compares the SPEC CPU2006 results for -O2 ized application memory image remains. Some static sec-
and -O3. The benchmarks are ordered by descending over- tions of the application are writable on IA32 and can be used
head for -O3. The overhead for both -O2 and -O3 is compa- to setup an exploit using a data attack that enables a set of
rable for all benchmarks. attacker-controlled writes to arbitrary memory locations.
6. Conclusion [11] E RLINGSSON , Ú., A BADI , M., V RABLE , M., B UDIU , M.,
AND N ECULA , G. C. XFI: Software guards for system ad-
Current Linux distributions use a variety of security features
dress spaces. In OSDI’06 (2006), pp. 75–88.
to protect the running system from security critical bugs in
applications. Security features like Data Execution Preven- [12] G ADALETA , F., YOUNAN , Y., JACOBS , B., J OOSEN , W.,
D E N EVE , E., AND B EOSIER , N. Instruction-level coun-
tion (DEP), Address Space Layout Randomization (ASLR),
termeasures against stack-based buffer overflow attacks. In
and stack protection techniques are enabled by default and VDTS ’09: Proceedings of the 1st EuroSys Workshop on Vir-
protect from a variety of attack vectors. tualization Technology for Dependable Systems (2009), ACM,
Current systems do not enable Position Independent Ex- pp. 7–12.
ecutables (PIE) by default; resulting in some static memory [13] GERA , AND RIQ . Advances in format string exploitation.
regions. String Oriented Programming (SOP) is a possible Phrack 11, 59 (2002), http://phrack.com/issues.html?
approach that exploits the weakness of non-PIE applications. issue=59&id=7.
SOP uses format string bugs to copy exploit data to static [14] H AAS , P. Advanced format string at-
data regions and escalates to Return Oriented Programming tacks. https://www.defcon.org/images/
or Jump Oriented Programming, thereby effectively bypass- defcon-18/dc-18-presentations/Haas/
ing ASLR, DEP, and stack canaries. DEFCON-18-Haas-Adv-Format-String-Attacks.pdf,
DEFCON 18 2010.
References [15] H IROAKI , E., AND K UNIKAZU , Y. ProPolice: Improved
[1] A BADI , M., B UDIU , M., E RLINGSSON , U., AND L IGATTI , stack-smashing attack detection. IPSJ SIG Notes (2001), 181–
J. Control-flow integrity. In CCS’05: Proc. 12th Conf. Com- 188.
puter and Communications Security (2005), pp. 340–353. [16] N ERGAL. The advanced return-into-lib(c) exploits. Phrack
[2] A LEPH 1. Smashing the stack for fun and profit. Phrack 7, 49 11, 58 (Nov. 2007), http://phrack.com/issues.html?
(Nov. 1996), http://phrack.com/issues.html?issue= issue=67&id=8.
49&id=14. [17] OWASP. Definition of format string attacks. https://www.
[3] BARATLOO , A., S INGH , N., AND T SAI , T. Transparent run- owasp.org/index.php/Format_string_attack.
time defense against stack smashing attacks. In Proc. USENIX [18] PA X-T EAM. PaX ASLR (Address Space Layout Random-
ATC (2000), pp. 251–262. ization). http://pax.grsecurity.net/docs/aslr.txt,
[4] B HATKAR , E., D UVARNEY, D. C., AND S EKAR , R. Address 2003.
obfuscation: an efficient approach to combat a broad range [19] PAYER , M., AND G ROSS , T. R. Fine-grained user-space
of memory error exploits. In SSYM’03: Proc. 12th USENIX security through virtualization. In VEE’11: Proc. 7th Int’l
Security Symp. (2003), pp. 105–120. Conf. Virtual Execution Environments (2011), pp. 157–168.
[5] B HATKAR , S., B HATKAR , E., S EKAR , R., AND D UVARNEY, [20] P INCUS , J., AND BAKER , B. Beyond stack smashing: Recent
D. C. Efficient techniques for comprehensive protection from advances in exploiting buffer overruns. IEEE Security and
memory error exploits. In SSYM’05: Proc. 14th USENIX Privacy 2 (2004), 20–27.
Security Symp. (2005), pp. 255–270.
[21] P LANET, C. A eulogy for format strings. Phrack 14,
[6] BLACKNGEL . The house of lore: Reloaded. Phrack 14, 67 67 (2010), http://phrack.com/issues.html?issue=
(Nov. 2010), http://phrack.com/issues.html?issue=67&id=8. 67&id=8.
[7] B LETSCH , T., J IANG , X., F REEH , V. W., AND L IANG , Z. [22] S CHWARTZ , E. J., AVGERINOS , T., AND B RUMLEY, D. Q:
Jump-oriented programming: a new class of code-reuse at- Exploit hardening made easy. In Proceedings of the USENIX
tack. In ASIACCS’11: Proc. 6th ACM Symp. on Information, Security Symposium (2011).
Computer and Communications Security (2011), pp. 30–40.
[23] S HACHAM , H. The geometry of innocent flesh on the bone:
[8] C OWAN , C., BARRINGER , M., B EATTIE , S., K ROAH - Return-into-libc without function calls (on the x86). In
H ARTMAN , G., F RANTZEN , M., AND L OKIER , J. Format- CCS’07: Proc. 14th Conf. on Computer and Communications
guard: automatic protection from printf format string vulner- Security (2007), pp. 552–561.
abilities. In SSYM’01: Proc. 10th USENIX Security Symp.
[24] S HACHAM , H., PAGE , M., P FAFF , B., G OH , E.-J.,
(2001).
M ODADUGU , N., AND B ONEH , D. On the effectiveness of
[9] C OWAN , C., B EATTIE , S., J OHANSEN , J., AND WAGLE , address-space randomization. In CCS’04: Proc. 11th Conf.
P. PointguardTM: protecting pointers from buffer overflow Computer and Communications Security (2004), pp. 298–307.
vulnerabilities. In SSYM’03: Proc. 12th USENIX Security
[25] U BUNTU. List of programs built with PIE. https://wiki.
Symp. (2003).
ubuntu.com/Security/Features#pie, May 2012.
[10] C OWAN , C., P U , C., M AIER , D., H INTONY, H., WALPOLE ,
[26] VAN DE V EN , A., AND M OLNAR , I. Exec shield.
J., BAKKE , P., B EATTIE , S., G RIER , A., WAGLE , P., AND
https://www.redhat.com/f/pdf/rhel/WHP0006US_
Z HANG , Q. StackGuard: automatic adaptive detection and
Execshield.pdf, 2004.
prevention of buffer-overflow attacks. In SSYM’98: Proc. 7th
USENIX Security Symp. (1998).