You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

209 lines
12 KiB

  1. 1. Design
  2. The goal of Address Space Layout Randomization is to introduce randomness
  3. into addresses used by a given task. This will make a class of exploit
  4. techniques fail with a quantifiable probability and also allow their
  5. detection since failed attempts will most likely crash the attacked task.
  6. To help understand the ideas behind ASLR, let's look at an example task
  7. and its address space: we made a copy of /bin/cat into /tmp/cat then
  8. disabled all PaX features on it and executed "/tmp/cat /proc/self/maps".
  9. The [x] marks are not part of the original output, we use them to refer
  10. to the various lines in the explanation (note that the VMMIRROR document
  11. contains more examples with various PaX features active).
  12. [1] 08048000-0804a000 R+Xp 00000000 00:0b 812 /tmp/cat
  13. [2] 0804a000-0804b000 RW+p 00002000 00:0b 812 /tmp/cat
  14. [3] 40000000-40015000 R+Xp 00000000 03:07 110818 /lib/ld-2.2.5.so
  15. [4] 40015000-40016000 RW+p 00014000 03:07 110818 /lib/ld-2.2.5.so
  16. [5] 4001e000-40143000 R+Xp 00000000 03:07 106687 /lib/libc-2.2.5.so
  17. [6] 40143000-40149000 RW+p 00125000 03:07 106687 /lib/libc-2.2.5.so
  18. [7] 40149000-4014d000 RW+p 00000000 00:00 0
  19. [8] bfffe000-c0000000 RWXp fffff000 00:00 0
  20. As we can see, /tmp/cat is a dynamically linked ELF executable, its address
  21. space contains several file mappings.
  22. [1] and [2] correspond to the loadable ELF segments of /tmp/cat containing
  23. code and data (both initialized and uninitialized), respectively.
  24. [3] and [4] represent the dynamic linker whereas [5], [6] and [7] are the
  25. segments of the C runtime library ([7] holds its uninitialized data that is
  26. big enough to not fit into the last page of [6]).
  27. [8] is the stack which grows downwards.
  28. There are other mappings as well that this simple example does not show us:
  29. the brk() managed heap that would directly follow [2] and various anonymous
  30. and file mappings that the task can create via mmap() and would be placed
  31. between [7] and [8] (unless an explicit mapping address outside this region
  32. was requested using the MAP_FIXED flag).
  33. For our purposes all these possible mappings can be split into three groups:
  34. - [1], [2] and the brk() managed heap following them,
  35. - [3]-[7] and all the other mappings created by mmap(),
  36. - [8], the stack.
  37. The mappings in the first and last groups are established during execve()
  38. and do not move (only their size can change) whereas the mappings in the
  39. second group may come and go during the lifetime of the task. Since the
  40. base addresses used to map each group are not related to each other, we can
  41. apply different amount of randomization to each. This also has the benefit
  42. that whenever a given attack technique needs advance knowledge of addresses
  43. from more than group, the attacker will likely have to guess or brute force
  44. all entropies at once which further reduces the chances of success.
  45. Let's analyze now the (side) effects of ASLR. For our purposes the most
  46. important effect is on the class of exploit techniques that need advance
  47. knowledge of certain addresses in the attacked task, such as the address
  48. of the current stack pointer or libraries. If there is no way to exploit
  49. a given bug to divulge information about the attacked task's randomized
  50. address space layout then there is only one way left to exploit the bug:
  51. guessing or brute forcing the randomization.
  52. Guessing occurs when the randomization applied to a task changes in every
  53. attacked task in an unpredictable manner. This means that the attacker
  54. cannot learn anything of future randomizations and has the same chance of
  55. succeeding in each attack attempt. Brute forcing occurs when the attacker
  56. can learn something about future randomizations and build that knowledge
  57. into his attack. In practice brute forcing can be applied to bugs that are
  58. in network daemons that fork() on each connection since fork() preserves
  59. the randomized layout, as opposed to execve() which replaces it with a new
  60. one. This distinction between the attack methods becomes meaningless if the
  61. system has monitoring and reaction mechanisms for program crashes because
  62. the reaction can then be triggered at such low levels that the two attack
  63. methods will have practically the same (im)probability to succeed.
  64. To quantify the above statements about probability of success, let's first
  65. introduce a few variables:
  66. Rs: number of bits randomized in the stack area,
  67. Rm: number of bits randomized in the mmap() area,
  68. Rx: number of bits randomized in the main executable area,
  69. Ls: least significant randomized bit position in the stack area,
  70. Lm: least significant randomized bit position in the mmap() area,
  71. Lx: least significant randomized bit position in the main executable area,
  72. As: number of bits of stack randomness attacked in one attempt,
  73. Am: number of bits of mmap() randomness attacked in one attempt,
  74. Ax: number of bits of main executable randomness attacked in one attempt.
  75. For example, for i386 we have Rs = 24, Rm = 16, Rx = 16, Ls = 4, Lm = 12
  76. and Lx = 12 (e.g., the stack addresses have 24 bits of randomness in bit
  77. positions 4-27 leaving the least and most significant four bits unaffected
  78. by randomization). The number of attacked bits represents the fact that in
  79. a given situation more than one bit at a time can be attacked (obviously
  80. A <= R), e.g., by duplicating the attack payload multiple times in memory
  81. one can overcome the least significant bits of the randomization.
  82. The probabilities of success within x number of attempts are given by the
  83. following formulae (for guessing and brute forcing, respectively):
  84. (1) Pg(x) = 1 - (1 - 2^-N)^x, 0 <= x
  85. (2) Pb(x) = x / 2^N, 0 <= x <= 2^N
  86. where N = Rs-As + Rm-Am + Rx-Ax, the number of randomized bits to find.
  87. Based on the above the following tables summarize the probabilities of
  88. success as a function of how many bits are tried in one attempt and the
  89. number of attempts.
  90. Pg(x)| x
  91. -----+----------------------------------------------------------------------
  92. N| 1 4 16 64 256 2^10 2^14 2^18 2^20 2^24 2^32 2^40 2^56 2^64
  93. -----+----------------------------------------------------------------------
  94. 1| 0.50 0.94 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1
  95. 2| 0.25 0.68 0.99 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1
  96. 4| 0.06 0.23 0.64 0.98 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1
  97. 8| ~0 0.02 0.06 0.22 0.63 0.98 ~1 ~1 ~1 ~1 ~1 ~1 ~1 ~1
  98. 16| ~0 ~0 ~0 ~0 ~0 0.02 0.22 0.98 ~1 ~1 ~1 ~1 ~1 ~1
  99. 24| ~0 ~0 ~0 ~0 ~0 ~0 ~0 0.02 0.06 0.63 ~1 ~1 ~1 ~1
  100. 32| ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 0.63 ~1 ~1 ~1
  101. 40| ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 0.63 ~1 ~1
  102. 56| ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 0.63 ~1
  103. Pb(x)| x
  104. -----+----------------------------------------------------------------------
  105. N| 1 4 16 64 256 2^10 2^14 2^18 2^20 2^24 2^32 2^40 2^56 2^64
  106. -----+----------------------------------------------------------------------
  107. 1| 0.50
  108. 2| 0.25 1
  109. 4| 0.06 0.25 1
  110. 8| ~0 0.02 0.06 0.25 1
  111. 16| ~0 ~0 ~0 ~0 ~0 0.02 0.25
  112. 24| ~0 ~0 ~0 ~0 ~0 ~0 ~0 0.02 0.06 1
  113. 32| ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 1
  114. 40| ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 1
  115. 56| ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 ~0 1
  116. It is obvious that from the defense point of view the goal would be to make
  117. N as high as possible while keeping x as low as possible. Unfortunately N is
  118. not under control by the defense side (re-randomizing the address space at
  119. runtime is not feasible because part of the necessary relocation information
  120. is simply lost), but rather that of the nature of the bug and the attacker's
  121. exploit skills. What we know is that there has been very little research
  122. done and published on countering ASLR so far (e.g., it is unknown how certain
  123. real-life bugs such as stack or heap overflows can be used for information
  124. leaking in a general way). Reducing N is possible if an attacker can store
  125. multiple instances of the attack payload (e.g., stack frame chain if NOEXEC
  126. is active, or some shellcode when it is not) in the attacked task's address
  127. space. This would typically be possible by exploiting an overflow style bug
  128. where the attacker can fill a contiguous range of memory with data of his
  129. choice. As the size of this memory range grows above the value of L relevant
  130. to the given range, more and more randomized bits can be ignored in the
  131. attack payload. For example, to overcome all of R for a given range on i386,
  132. the attacker would have to send 256 MB of data, something that is not always
  133. possible (e.g., the stack typically has a maximum limit of 8 MB and grows to
  134. much less in practice).
  135. It is also unknown how bugs that have been neglected so far can be used
  136. against ASLR, that is, bugs that give only read access (vs. write) to the
  137. attacker and were not considered as a serious security problem before but
  138. may now be used to help counter ASLR in an exploit attempt of another bug.
  139. On the other hand however the defense side has quite some control over the
  140. value of x: whenever an attack attempt makes a wrong guess on the randomized
  141. bits, the attacked application will go into a state that will likely result
  142. in a crash and hence becomes detectable by the kernel. It is therefore a
  143. good strategy to use a crash detection and reaction mechanism together with
  144. ASLR (PaX itself contains no such mechanism).
  145. The last set of side effects of ASLR is address space fragmentation and
  146. entropy pool exhaustion. Since randomization shifts entire ranges of memory,
  147. it will also randomly change the gaps between them (which were constant
  148. before). This in turn will change the maximum size of memory mappings that
  149. will fit in there and applications expecting to be able to create them will
  150. fail. Finally, ASLR increases the consumption of the system's entropy pool
  151. since every task creation (through the execve() system call) requires some
  152. bits of randomness to determine the new address space layout. Depending on
  153. the system's threat model however a given implementation can relax the
  154. requirements for the quality of this entropy. In particular, if only remote
  155. attacks are considered, then ASLR does not need cryptographically secure
  156. random bits as a remote attacker cannot observe them (or if he can, he does
  157. not need to care about ASLR at all).
  158. 2. Implementation
  159. PaX can apply ASLR to tasks that are created from ELF executables and
  160. use ELF libraries. The randomized layout is determined at task creation
  161. time in the load_elf_binary() function in fs/binfmt_elf.c where three per
  162. task (or more precisely, mm_struct) variables are initialized with random
  163. numbers: delta_exec, delta_mmap and delta_stack.
  164. The following list specifies which ASLR feature affects which part of
  165. the task address space layout (they are discussed in detail in separate
  166. documents):
  167. RANDEXEC/RANDMMAP (delta_exec) - main executable code/data/bss segments
  168. RANDEXEC/RANDMMAP (delta_exec) - brk() managed memory (heap)
  169. RANDMMAP (delta_mmap) - mmap() managed memory (libraries, heap,
  170. thread stacks, shared memory)
  171. RANDUSTACK (delta_stack) - user stack
  172. RANDKSTACK - kernel stack (not part of the task's
  173. address space)
  174. The main executable and the brk() managed heap can be randomized in two
  175. different ways depending on the file format of the main executable. If
  176. it is an ET_EXEC ELF file, then RANDEXEC can be applied to it, if it is
  177. an ET_DYN ELF file then RANDMMAP.