Address-space layout randomization using code islands

Address-Space Layout Randomization (ASLR) techniques prevent intruders from locating target functions by randomizing the process layout. Prior ASLR techniques defended against single-target brute force attacks, which work by locating a single, omnipotent system library function such as execve(). These techniques are not sufficient to defend against chained return-into-lib(c) attacks that call a sequence of system library functions. In this paper, we describe the Island Code Transformation (ICT) that addresses chained return-into-lib(c) attacks. A code island is a block of code that is isolated in the address space from other code blocks. Island code not only randomizes the base pointers used in memory mapping, but also maximizes the entropy in function layout (that is, knowing the location and extent of one function gains the attacker little knowledge as to the memory location of other functions). We also provide an efficacy analysis of randomization schemes based on combinations of available ASLR techniques. Our analysis shows that ICT is exponentially more effective than any prior ASLR technique in defending against brute-force searches for addresses of multiple target functions - a key component of chained return-into-lib(c) attacks. ICT uses a predefined rerandomization threshold, that determines how frequently (in terms of failed attacks) the process layout is re-randomized to balance security and availability. Our overhead measurement on some well-known GNU applications shows that it takes less than 0.05 second to load/rerandomize a process with the necessary C system library functions in code islands, and our technique introduces a 3-10% run-time overhead caused by inter-island control transfers. We, therefore, conclude that ICT is well-suited for dedicated servers.