Revisiting Address Space Randomization - Information Security and Cryptology-ICISC 2010 - page 210

The second step can be done by executing injected code [12] or performing a
return-to-libc attack.
Address space randomization [2,3,4] and a variant of it [17] are proposed to
make both steps discussed above dicult. For example, in order to overwrite
a return address on the stack to subvert the program's control flow, an attack
needs first to locate the return address. If the base of the stack is randomized,
the location of the return address is no longer the same on different executions of
the same program and therefore the attack will be dicult. A brief summary of
the randomizing techniques to make it dicult to subvert the program's control
flow follows.
- Introducing shadow stack for buffer-type variables;
- Randomizing the base of the stack and heap;
- Introducing random sized gaps between successive stack frames and heap
allocations;
- Avoiding calls using absolute addresses by transforming them into function
pointers.
Address space randomization can also make it dicult for an attack to perform
arbitrary computation after the attack subverts the program's control flow. For
example, making memory spaces non-writable or non-executable could stop in-
jected code execution. Randomizing functions in the binary and shared library
could make return-to-libc attacks dicult. Here is a summary of randomizing
techniques to make this step dicult.
- Making certain memory spaces non-writable or non-executable;
- Randomizing the order of functions in the binary and shared libraries;
- Introducing random sized gaps and inaccessible pages between functions in
the binary and shared libraries;
- Randomizing the order of static variables;
- Randomizing the location of PLT and GOT;
- Randomizing the order of entries in PLT and GOT;
- Uses position independent code in the program.
In this paper, we assume that an attack has successfully subverted the vulnerable
program's control flow (first step), and try to evaluate how effective address space
randomization is in making the second step dicult, i.e., in making it dicult
for the attack to perform arbitrary computation.
Our attack uses the idea of return-oriented programming [14,6]. Return-oriented
programming fits the requirement of the attack well because it does not need to
execute any injected code. Only a large number of short instruction sequences
from either the original program or libc is to be executed in order for the attack
to perform arbitrary computation. However, our attack is more challenging than
return-oriented programming on a normal (non-randomized) machine in that
the addresses of the short instruction sequences are randomized and unknown
to the attacker. Although return-oriented programming has been extended to
a number of different environments [5,9,10,11,7], it is non-trivial how it can be
applied on address space randomization systems.