1. Design The goal of Address Space Layout Randomization is to introduce randomness into addresses used by a given task. This will make a class of exploit techniques fail with a quantifiable probability and also allow their detection since failed attempts will most likely crash the attacked task. To help understand the ideas behind ASLR, let's look at an example task and its address space: we made a copy of /bin/cat into /tmp/cat then disabled all PaX features on it and executed "/tmp/cat /proc/self/maps". The [x] marks are not part of the original output, we use them to refer to the various lines in the explanation (note that the VMMIRROR document contains more examples with various PaX features active). [1] 08048000-0804a000 R+Xp 00000000 00:0b 812 /tmp/cat [2] 0804a000-0804b000 RW+p 00002000 00:0b 812 /tmp/cat [3] 40000000-40015000 R+Xp 00000000 03:07 110818 /lib/ld-2.2.5.so [4] 40015000-40016000 RW+p 00014000 03:07 110818 /lib/ld-2.2.5.so [5] 4001e000-40143000 R+Xp 00000000 03:07 106687 /lib/libc-2.2.5.so [6] 40143000-40149000 RW+p 00125000 03:07 106687 /lib/libc-2.2.5.so [7] 40149000-4014d000 RW+p 00000000 00:00 0 [8] bfffe000-c0000000 RWXp fffff000 00:00 0 As we can see, /tmp/cat is a dynamically linked ELF executable, its address space contains several file mappings. [1] and [2] correspond to the loadable ELF segments of /tmp/cat containing code and data (both initialized and uninitialized), respectively. [3] and [4] represent the dynamic linker whereas [5], [6] and [7] are the segments of the C runtime library ([7] holds its uninitialized data that is big enough to not fit into the last page of [6]). [8] is the stack which grows downwards. There are other mappings as well that this simple example does not show us: the brk() managed heap that would directly follow [2] and various anonymous and file mappings that the task can create via mmap() and would be placed between [7] and [8] (unless an explicit mapping address outside this region was requested using the MAP_FIXED flag). For our purposes all these possible mappings can be split into three groups: - [1], [2] and the brk() managed heap following them, - [3]-[7] and all the other mappings created by mmap(), - [8], the stack. The mappings in the first and last groups are established during execve() and do not move (only their size can change) whereas the mappings in the second group may come and go during the lifetime of the task. Since the base addresses used to map each group are not related to each other, we can apply different amount of randomization to each. This also has the benefit that whenever a given attack technique needs advance knowledge of addresses from more than group, the attacker will likely have to guess or brute force all entropies at once which further reduces the chances of success. Let's analyze now the (side) effects of ASLR. For our purposes the most important effect is on the class of exploit techniques that need advance knowledge of certain addresses in the attacked task, such as the address of the current stack pointer or libraries. If there is no way to exploit a given bug to divulge information about the attacked task's randomized address space layout then there is only one way left to exploit the bug: guessing or brute forcing the randomization. Guessing occurs when the randomization applied to a task changes in every attacked task in an unpredictable manner. This means that the attacker cannot learn anything of future randomizations and has the same chance of succeeding in each attack attempt. Brute forcing occurs when the attacker can learn something about future randomizations and build that knowledge into his attack. In practice brute forcing can be applied to bugs that are in network daemons that fork() on each connection since fork() preserves the randomized layout, as opposed to execve() which replaces it with a new one. This distinction between the attack methods becomes meaningless if the system has monitoring and reaction mechanisms for program crashes because the reaction can then be triggered at such low levels that the two attack methods will have practically the same (im)probability to succeed. To quantify the above statements about probability of success, let's first introduce a few variables: Rs: number of bits randomized in the stack area, Rm: number of bits randomized in the mmap() area, Rx: number of bits randomized in the main executable area, Ls: least significant randomized bit position in the stack area, Lm: least significant randomized bit position in the mmap() area, Lx: least significant randomized bit position in the main executable area, As: number of bits of stack randomness attacked in one attempt, Am: number of bits of mmap() randomness attacked in one attempt, Ax: number of bits of main executable randomness attacked in one attempt. For example, for i386 we have Rs = 24, Rm = 16, Rx = 16, Ls = 4, Lm = 12 and Lx = 12 (e.g., the stack addresses have 24 bits of randomness in bit positions 4-27 leaving the least and most significant four bits unaffected by randomization). The number of attacked bits represents the fact that in a given situation more than one bit at a time can be attacked (obviously A <= R), e.g., by duplicating the attack payload multiple times in memory one can overcome the least significant bits of the randomization. The probabilities of success within x number of attempts are given by the following formulae (for guessing and brute forcing, respectively): (1) Pg(x) = 1 - (1 - 2^-N)^x, 0 <= x (2) Pb(x) = x / 2^N, 0 <= x <= 2^N where N = Rs-As + Rm-Am + Rx-Ax, the number of randomized bits to find. Based on the above the following tables summarize the probabilities of success as a function of how many bits are tried in one attempt and the number of attempts. Pg(x)| x -----+---------------------------------------------------------------------- N| 1 4 16 64 256 2^10 2^14 2^18 2^20 2^24 2^32 2^40 2^56 2^64 -----+---------------------------------------------------------------------- 1| 0.50 0.94 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 2| 0.25 0.68 0.99 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 4| 0.06 0.23 0.64 0.98 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 8| ~0 0.02 0.06 0.22 0.63 0.98 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 16| ~0 ~0 ~0 ~0 ~0 0.02 0.22 0.98 ~1 ~1 ~1 ~1 ~1 ~1 24| ~0 ~0 ~0 ~0 ~0 ~0 ~0 0.02 0.06 0.63 ~1 ~1 ~1 ~1 32| ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 0.63 ~1 ~1 ~1 40| ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 0.63 ~1 ~1 56| ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 0.63 ~1 Pb(x)| x -----+---------------------------------------------------------------------- N| 1 4 16 64 256 2^10 2^14 2^18 2^20 2^24 2^32 2^40 2^56 2^64 -----+---------------------------------------------------------------------- 1| 0.50 2| 0.25 1 4| 0.06 0.25 1 8| ~0 0.02 0.06 0.25 1 16| ~0 ~0 ~0 ~0 ~0 0.02 0.25 24| ~0 ~0 ~0 ~0 ~0 ~0 ~0 0.02 0.06 1 32| ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 1 40| ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 1 56| ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 1 It is obvious that from the defense point of view the goal would be to make N as high as possible while keeping x as low as possible. Unfortunately N is not under control by the defense side (re-randomizing the address space at runtime is not feasible because part of the necessary relocation information is simply lost), but rather that of the nature of the bug and the attacker's exploit skills. What we know is that there has been very little research done and published on countering ASLR so far (e.g., it is unknown how certain real-life bugs such as stack or heap overflows can be used for information leaking in a general way). Reducing N is possible if an attacker can store multiple instances of the attack payload (e.g., stack frame chain if NOEXEC is active, or some shellcode when it is not) in the attacked task's address space. This would typically be possible by exploiting an overflow style bug where the attacker can fill a contiguous range of memory with data of his choice. As the size of this memory range grows above the value of L relevant to the given range, more and more randomized bits can be ignored in the attack payload. For example, to overcome all of R for a given range on i386, the attacker would have to send 256 MB of data, something that is not always possible (e.g., the stack typically has a maximum limit of 8 MB and grows to much less in practice). It is also unknown how bugs that have been neglected so far can be used against ASLR, that is, bugs that give only read access (vs. write) to the attacker and were not considered as a serious security problem before but may now be used to help counter ASLR in an exploit attempt of another bug. On the other hand however the defense side has quite some control over the value of x: whenever an attack attempt makes a wrong guess on the randomized bits, the attacked application will go into a state that will likely result in a crash and hence becomes detectable by the kernel. It is therefore a good strategy to use a crash detection and reaction mechanism together with ASLR (PaX itself contains no such mechanism). The last set of side effects of ASLR is address space fragmentation and entropy pool exhaustion. Since randomization shifts entire ranges of memory, it will also randomly change the gaps between them (which were constant before). This in turn will change the maximum size of memory mappings that will fit in there and applications expecting to be able to create them will fail. Finally, ASLR increases the consumption of the system's entropy pool since every task creation (through the execve() system call) requires some bits of randomness to determine the new address space layout. Depending on the system's threat model however a given implementation can relax the requirements for the quality of this entropy. In particular, if only remote attacks are considered, then ASLR does not need cryptographically secure random bits as a remote attacker cannot observe them (or if he can, he does not need to care about ASLR at all). 2. Implementation PaX can apply ASLR to tasks that are created from ELF executables and use ELF libraries. The randomized layout is determined at task creation time in the load_elf_binary() function in fs/binfmt_elf.c where three per task (or more precisely, mm_struct) variables are initialized with random numbers: delta_exec, delta_mmap and delta_stack. The following list specifies which ASLR feature affects which part of the task address space layout (they are discussed in detail in separate documents): RANDEXEC/RANDMMAP (delta_exec) - main executable code/data/bss segments RANDEXEC/RANDMMAP (delta_exec) - brk() managed memory (heap) RANDMMAP (delta_mmap) - mmap() managed memory (libraries, heap, thread stacks, shared memory) RANDUSTACK (delta_stack) - user stack RANDKSTACK - kernel stack (not part of the task's address space) The main executable and the brk() managed heap can be randomized in two different ways depending on the file format of the main executable. If it is an ET_EXEC ELF file, then RANDEXEC can be applied to it, if it is an ET_DYN ELF file then RANDMMAP.