ASLR (Address Space Layout Randomization) is a powerful security mitigation technique. The ASLR protects against memory error attacks by randomizing the memory layout of the processes. If the attacker does not know the addresses used by the target process, then ROP, ret*lib and other exploit mechanisms can not be used (or are harder to use).
The effectiveness of the ASLR depends on keeping secret the memory layout of the processes, which is achieved by randomizing the memory layout. Therefore, the more random are the addresses of a process the more secure it is. But it is generally considered that an excessive randomness also causes memory fragmentation and performance loss.
We have designed a new ASLR, called ASLR-NG, which provides the maximum entropy without jeopardizing fragmentation. ASLR-NG also addresses several other weaknesses of current designs.
In the following we sketch four weakness present in current Linux and PaX ASLRs.
Current ASLRs have been implemented by adding some randomness to the original positions of the objects (or maps), in order to: 1) maintain the relative position of each object, 2) allow growable objects (stack and heap) and also 3) to avoid fragmentation. As a result, the VMA space used to randomize each object is just a small portion of the full VMA.
Next is a comparative summary of the observed entropy. Green and red indicate the best and worst randomized object per row.
Although the idea to randomize each object using the full VMA is quite intuitive and simple, there exist multiple challenges that must be addressed. The two more important are: 1) The fragmentation and 2) the page table size. ASLR-NG can use the full VMA space and at the same time keep the fragmentation and pagetable size low.
We have observed several non-uniform distributions in Linux and PaX ASLRs: triangular, trapezoidal, Irwin-Hall (sum of several uniforms) and several irregulars.
The libraries and mmaps in 32-bit system in PaX as showed in Fig 3, are not uniformly distributed in the range. Actually, they follow a triangular distribution where the values in the center are much more likely. The same weakness is present in PaX 64-bit systems as shown in Fig 5. This effect is because the final position is calculated as the sum of two (triangular) or three (Irwin-Hall) random values respectively.
Regarding Linux, we observed also non-uniform objects but much less pronounced. As Fig 4 shows, the HEAP follows a trapezoidal but has much less concentration of the values in the center than the one of PaX. Linux heap is the result of the sum of two random numbers of different ranges (resulting in a trapezoidal).
A non-uniform distribution is not a a problem on its own. The problem arises when the distribution has a narrow band of values with higher probability. In this case, it is possible to design a better/faster attack strategy.
If knowing the position of an object (an address belonging to an object) gives information (address bits) about where another is in memory, then we said that they are correlated. According to how an attacker can use the correlation, we can have three types: total, partial and useless.
Total correlation is when knowing the position of an object gives the exact position of another one. An example can be found in how current libraries are mapped in both Linux and PaX. All libraries are mapped next to each other, and so de-randomizing one library gives the positions of all the others (for a given application). This weakness has been used by the Metaphor exploit to bypass the ASLR in the Stagefright vulnerability.
Positive or partial correlation is when knowing the position of an object gives enough information to guess another one with less effort than guessing the second one directly. Following is a simple example which affects both, Linux and PaX (assuming a brute force of 1000 trials per second):
This weakness can be abused by attackers to de-randomize objects faster when they can choose the target object.
It is widely known that child processes inherit/share the memory layout of the father. This is the expected behavior, since children are a copy of the father. Unfortunately, this enables attackers to both brute force attacks to the ASLR and allow siblings to predict future mappings of their siblings, when the allocator is predictable after the fork.
This specially affects applications/architectures that make an intensive use of the forking model like: Android with Zygote, KDEinit, Chrome browser, etc. Fig 6 shows the memory layout of the father and a child process when the two processes request an mmap().
This weakness can be abused to bypass ASLR in sanboxing environments that use the forking model.
Here, we briefly present ASLR-NG, a new ASLR design which overcomes the limitations of current designs and removes the four previously weaknesses described without introducing undesired side effects such as memory fragmentation or performance overhead.
In short, ASLR-NG overcomes Linux and PaX ASLR solutions in all aspects.
By removing the (unrealistic) restriction of having unbounded growable objects, we are able to implement a much more flexible and powerful ASLR-NG.
This allows ASLR-NG to attend a large mmap request.
Since an attacker don't know which part of the VMA is being used to allocate objects, they can not discard any of them, and so the cost of the attack (the amount of uncertainty) is equal to the full VMA space.
Obviously, if the attacker is able to leak one address, then they will know the position of that object and which part (upper/lower) is being used by the process. In other words, there is a one bit of correlation between all the maps of the process.
To guarantee a large consecutive block of memory is very important to keep the compatibility in some applications such us video player. Otherwise, applications mapping large files will crash. Therefore a design of the ASLR which increase the entropy at the cost of reducing this large consecutive block of memory is not acceptable.
Largest allocatable mmap on 32-bit.
Selecting the operation mode, ASLR-NG can be adapted to a wide range of requirements.
The security provided by the ASLR is typically measured as the amount of entropy of the memory layout. And the entropy is calculated as the number of random bits of the addresses. To be more precise, the security of the ASLR shall be measured as the "effort" needed by an attacker to bypass the ASLR. In most cases, the number of random bits is a good estimation of the cost of the attack, but not always.
We have developed a tool, called ASLRA, to make the statistical analysis of the ASLR-NG.
ASLR-NG is currently a working PoC. It requires some effort and discussion in order to make it a real replacement for current Linux ASLR. Any change into the memory manager code of the Linux Kernel must be done with extreme care and general consensus.
Other projects failed to move into the Linux kernel because they were focused only on security. We think that backward compatibility and performance are more important than security.
The technical details of the ASLR-NG are in the PhD. Thesis of Hector Marco-Gisbert (defended Nov. 2015).
