Chongkyung Kil
North Carolina State University
USA

Jinsuk Jun
North Carolina State University
USA

Christopher Bookholt
North Carolina State University
USA

Jun Xu
North Carolina State University
USA

Peng Ning
North Carolina State University
USA

Address space randomization is an emerging and promising method for stopping a broad range of memory corruption attacks. By randomly shifting critical memory regions at process initialization time, address space randomization converts an otherwise successful malicious attack into a benign process crash. However, existing approaches either introduce insufficient randomness, or require source code modification. While insufficient randomness allows successful brute-force attacks, as shown in recent studies, the required source code modification prevents this effective method from being used for commodity software, which is the major source of exploited vulnerabilities on the Internet.

In this paper, we propose Address Space Layout Permutation (ASLP) that introduces high degree of randomness (or high entropy) with minimal performance overhead. The high entropy substantially increases the difficulty of brute-force attacks. In addition, ASLP randomly permutes different memory regions in an application's binary process address space, and does not require any changes to source code. Essential to ASLP is a novel binary rewriting tool that can place the static code and data segments of a compiled executable to a randomly specified location and performs fine-grained permutation of procedure bodies in the code segment as well as static data objects in the data segment, with the relocation information produced by a normal compiler and preserved by the compile time linker. We have also modified the Linux operating system kernel to permute stack, heap, and memory mapped regions. Together, ASLP completely permutes memory regions in an application. Our security and performance evaluation shows minimal performance overhead with orders of magnitude improvement in randomness (e.g., up to 29 bits of randomness on a 32-bit architecture).

Keywords: Address Space Randomization, Software Security, Intrusion Detection

Read Paper (in PDF)