Lecture Notes: Address Space Layout Randomization

One of the most commonly deployed defenses is address space layout randomization (ASLR). As the name suggests, ASLR randomizes the address space layout to make it difficult for attackers to find gadgets, the address of libc functions, the objects on the stack, and the objects in the heap. Intuitively, if the attacker does not know these addresses then constructing a working exploit becomes significantly more difficult.

While there are many different proposed and implemented variations of ASLR, this post will focus on the version proposed by the PAX team and implemented in Linux 32-bit and 64-bit systems.

The Basics for 32-bit x86

In 32-bit Linux, ASLR randomizes the starting locating for three areas of memory:

  • the executable area which contains the code, initialized data, and uninitialized data,
  • the mapped area which contains dynamically linked libraries, the heap, and thread stacks,
  • and the stack area which contains the main user stack.

The starting location for each area, also called the base offset, is selected randomly for each area at process start. In other words, each region will be given a different base offset for each execution of the program.

There are restrictions for what those random offsets can be. Take the mapped area for example, while the base address is a 32-bit number, ASLR will only randomize bits 12-27. ASLR won’t randomize bits 0-11 because it would break page alignment and it won’t randomize bits 28-31 because that would make it harder to allocate big pages (Ref. 1). As a result of these restrictions, there are only 2^16 possible starting offsets for the mapped area. In other words, ASLR provides 16 bits of randomness for the mapped area. The stack and executable areas have similar restrictions and ASLR provides 24 and 16 bits of randomness for those areas, respectively.

Now lets take a quick glance at what ASLR actually looks like from the perspective of a user on a 64-bit system. First, let’s turn it on (though it is probably enabled by default). To turn ASLR on in Ubuntu run echo 2 | sudo tee /proc/sys/kernel/randomize_va_space and if you want to turn it off run echo 0 | sudo tee /proc/sys/kernel/randomize_va_space. Now consider this simple C program:

#include <stdio.h>

int main(int argv, char **argc){
    int target = 42;
    printf("The address of target: %p\n", &target);
    return 0;
}

If we run the program a few times, we should see something similar to the following:

$ ./aslr
The address of target: 0x7ffde80b5e14
$ ./aslr
The address of target: 0x7fff2bff9bb4
$ ./aslr
The address of target: 0x7ffeae3f9a54
$ ./aslr
The address of target: 0x7ffec254dde4

From the output, we can see that the address of target is different for every execution. The first 3 bits and the last 4 bits appear to be constant but the remaining bits change for every execution. This is ASLR’s doing. The target variable is placed on the stack and every time we a start new process the stack is moved.

Lets also look where libc (we’re calling printf from this library) is located with every new process. After running ldd aslr a few times we see the following:

$ ldd aslr
    linux-vdso.so.1 =>  (0x00007ffcaa9f6000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f3a5829c000)
    /lib64/ld-linux-x86-64.so.2 (0x00007f3a58666000)

$ ldd aslr
    linux-vdso.so.1 =>  (0x00007ffc7953c000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f58e459f000)
    /lib64/ld-linux-x86-64.so.2 (0x00007f58e4969000)

$ ldd aslr
    linux-vdso.so.1 =>  (0x00007ffdaccb0000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fd94bf69000)
    /lib64/ld-linux-x86-64.so.2 (0x00007fd94c333000)

By comparing the addresses given in this output, we can conclude that the leading bits and the last 12 bits stay the same while the remaining bits are randomized.

Defeating Coarse-Grained ASLR

The ASLR scheme we’ve described above is also called coarse-grained ALSR. The term “coarse-grained” here refers to the fact that this variety of ASLR does not randomize within each area. For example, while the starting offset of libc is placed in a random location on each run, libc itself is not changed. Think of coarse-grained ASLR as the rough equivalent of placing a book at a random location on a bookshelf; the book itself moves around, but the order and number of pages in that book stay the same.

What does this coarse-grained property mean for security? To answer this question, let’s consider a simple return-to-libc attack that exploits a buffer overflow. To execute this attack, the attacker needs to know the address of system (which is in the mapped area) and the address of the attacker-supplied string to pass to system (which is on the stack). In a perfect world, this means the attacker has to deal with 16+24 bits of randomness (on a 32-bit system), i.e., it is extremely unlikely that the attacker will correctly guess the address of system and the address of the argument string in the randomized address space layout. Further, the attacker has to get it right on the first try, otherwise the process will crash and the new process will have a completely different random layout. However, as Shacham et al. point out in their seminal work, “On the effectiveness of address-space randomization,” ASLR has a few problems in practice.

The first problem is the one we mentioned above: ASLR does not randomize within each area. This decision is great for performance and simplicity of implementation, but once the attacker can determine one known address in the area they effectively know all other addresses in that area. For example, the functions usleep and system are always the same distance apart for the same version of libc. So if the attacker figures out the address of usleep, they now know the address of system as well. This lack of internal randomization is also a problem on the stack and the heap for similar reasons.

So how does the attacker figure out one of these addresses? One way is through a memory leak. For example, an attacker can use a format string vulnerability to print out the contents of the stack. Leaking memory on the stack is useful because the stack contains pointers into executable code (e.g., saved return addresses) and the stack area (e.g., saved frame pointers).

Another technique to defeat ASLR on 32-bit systems is for the attacker to simply guess addresses until she guesses correctly. This style of attack is typically referred to as brute-forcing. Given that ASLR provides only 16 bits of randomness, the attacker has a 1 in 2^16 change of guessing the correct address for the libc function system. It seems like 1 in 2^16 is incredibly bad odds for the attacker, but brute-forcing is actually practical in many deployed system.

To understand why brute-forcing works against ASLR on 32-bit systems, we have to discuss the next major problem with ASLR. The second problem is that ASLR randomizes at process start but ALSR does not re-randomize on a process fork. In other words, the forked process (and process threads) will have the exact same layout as the parent process. For example, web servers are especially at risk due to this ASLR weakness as many use process forking (and threading) to handle requests. Shacham et al. describe how this forking behavior leads to an attacker being able to exploit a webserver by guessing the locations needed for a return-to-libc attack—the whole attack only requires a few minutes of guessing to succeed. In short, every web request becomes an opportunity for the attacker to guess the correct location of system as a crash of one child process won’t impact the parent process. That is, . While there are 2^16=65,536 possible locations for system, with forking system stays at the same location for every guess, and the attacker guess all possible locations.

Fortunately, the brute-forcing attack described above becomes impractical on 64-bit systems given the much (much much) larger address space. However, 64-bit ASLR can still be defeated by memory leaks.

Finally, ASLR works best on binaries that are compiled to be position independent (i.e., position independence executables or PIE). Without PIE support, then ALSR can only randomize some parts of the address space. For example, the locations of the stack, heap, and libc can be randomized; but the code section and procedure linkage table must stay at a fixed location.

Hint: Use PwnTools

You might wonder what’s the point of an information leak if your exploit is statically crafted and all of those addresses you leak will change once execution ends. There exist tools, like pwntools, that allow you to start a new process, read output from the program, and programmatically craft your exploit string for the process based on the output obtained. If you want to learn more, read the post on pwntools.

Summary

With ASLR enabled, code reuse attacks become more difficult to execute because the location of the code changes unpredictably between every execution of the process. For instance, an attacker cannot construct a ROP chain if she doesn’t know the addresses of the gadgets used in the chain.

There are two common to bypass coarse-grained ASLR:

  • Brute forcing is often practical due to a lack of entropy in 32-bit address spaces.
  • Information leaks can directly tell an attacker the important addresses.

Finally, it is important to realize that ASLR does not remove the initial memory error used to hi-jack control flow (e.g., a stack buffer overflow), it just makes that bug harder to exploit.

Additional Reading

  1. https://pax.grsecurity.net/docs/aslr.txt
  2. https://www.youtube.com/watch?v=Ec4UEtO7dPI
  3. https://askubuntu.com/questions/32441/does-ubuntu-use-security-features-like-dep-and-alsr
  4. https://benpfaff.org/papers/asrandom.pdf
  5. https://www.corelan.be/index.php/2010/06/16/exploit-writing-tutorial-part-10-chaining-dep-with-rop-the-rubikstm-cube/