A small security research group with solid background.     We do research to solve real problems with real solutions.
Hector Ismael

Copyright © Ismael Ripoll-Ripoll & Hector Marco-Gisbert, 6 April 2016.

ASLR-NG: ASLR Next Generation

Samples x sec: Sample:
Memory layouts of 100 executions (exec()).
Obtained using the ASLRA tool.

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.

ASLR Weaknesses in Linux and PaX

In the following we sketch four weakness present in current Linux and PaX ASLRs.

1) Low entropy

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.

Fig 1: 32-bit (x86) systemFig 2: 64-bit (x86_64) system
  • 32-bit Linux needs much more entropy to be effective.
  • PaX implementation is much better, but still not enough entropy on some scenarios.
  • In 64-bits Linux and PaX have a very similar level of protection, which are strong enough to deter most attack. But there is a lot of room for improvements.

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.

2) Non-uniform distribution

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).

Fig 3: PaX 32 on libs and mmaps Fig 4: Linux 32 on the HEAP Fig 5: PaX 64 on libs and mmaps

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.

3) Correlation between objects

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):

Hugepages:19 bits of entropy
Libraries:28 bits of entropy
Co-entropy (Libs ↔ Huge):9 bits of entropy
Brute-force Libraries: 228 (3 days)
Brute-force Hugepage then Library:219 + 29 (8 minutes)

This weakness can be abused by attackers to de-randomize objects faster when they can choose the target object.

4) Memory layout inheritance

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().

Fig 6: VMA of father and its child requesting a mmap

This weakness can be abused to bypass ASLR in sanboxing environments that use the forking model.


ASLR Next Generation

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.

  • Full VMA entropy range: all the range provided by the processor (specially useful in 32-bit systems).
  • A novel solution for reducing fragmentation, without reducing entropy
  • Addresses the four previous weakness.
  • The largest guaranteed mmap by default is similar to current Linux (it is tunable).
  • Objects containing sensitive information can be automatically isolated.
  • New randomizations forms: Per-boot, at fork, MAP_RANDOM, etc.
  • Generic code: architecture independent.
  • Simple configuration: four modes to adjust security vs. performance.
  • Fully compatible with all current executable files.
  • Specially useful for application that use the forking model as Android's Zygote, Apache, and other applications that use the forking mechanism to speed-up application launch.

In short, ASLR-NG overcomes Linux and PaX ASLR solutions in all aspects.

Key ideas

There are basically three main issues that must be taken into account in order to design a practical and non-academic ASLR.

Growable objects

Historically, the Stack and Heap have been considered as growable objects, and so, they were located at the borders of the VMA space in order to be able to grow towards the middle of the VMA. This is no longer true. Both, the Stack and the Heap, are typically bounded. Even the most demanding processes (as databases) are comfortable with just a 10Mb stack. And the Heap, implemented using the brk() system call has been marked as deprecated a long time ago.

By removing the (unrealistic) restriction of having unbounded growable objects, we are able to implement a much more flexible and powerful ASLR-NG.

Solving the fragmentation issue

Fragmentation is a strong limiting requirement, specially in 32-bit systems, where the available VMA space is very small. We have solved the fragmentation problem by randomizing objects in two phases:
  1. When the process is initialized, the upper or the lower half side of the VMA is chosen at random (one random bit);
  2. and then during the execution of the process, the allocation algorithm uses the selected part to randomly allocate the new objects.

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.

Linux 1.8 GB
PaX 692 MB
ASLR-NG1.5 GB

Largest allocatable mmap on 32-bit.

Tunning page table size

The last issue, but not the less important, is the page table size of each process. It mainly depends on how spread are the objects in memory, and so the more randomness the bigger the pagetable. To solve this issue, we have created four working modes in the ASLR-NG. Rather than reducing the absolute entropy, the solution relies on adjusting/tuning) the amount of correlation entropy. The modes are:
Concentrated:
All the objects are placed next to each other but the full VMA is used to randomize addresses. A compact layout is more efficient (smaller pagetable, and faster access) than current Linux and PaX, and has more absolute entropy.
Conservative:
Equivalent to that used in Linux and PaX. The main stack, the executable and the heap are independently randomised, while the rest (libraries and mmaps) are allocated in the same specific-zone.
Extended:
An extension of the conservative mode with additional randomisation between maps (which reduces correlation problems) and per-fork randomisation to remove the inheritance weakness. This can be considered a very secure configuration mode which addresses most of the weaknesses and sets a reasonable balance between security and performance. Therefore, this should be the default mode on most systems.
Paranoid: Every object is independently randomised. More secure but more overhead.
Fig 7: ASLR-NG: Profile mode examples.

Selecting the operation mode, ASLR-NG can be adapted to a wide range of requirements.

Evaluation

The most relevant parameter of an ASLR is the entropy, but the security of an ASLR depends also on other factors. A detailed categorization of those factors is beyond the scope of this report. Next is a brief comparative summary of the most relevant features.

Qualitative evaluation

Linux 4.5.0PaXASLR-NG
Stack sub-page randomization Yes Yes Yes
Heap and ARGV sub-page randomizationNoYes Yes
Full VMA randomization No No Yes
Library load randomization (direction)NoNo Yes
Per-boot ASLR readyNoNo Yes
Sub-Page randomizationNoNo Yes
Correlation entropyNoYes Yes*
Randomization at fork()NoNo Yes*
VMA space not used by the kernel.
Only partially for thread stacks.
* ASLR-NG mode configurable.

Quantitative Evaluation

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.

32-bit Linux vs PaX vs ASLR-NG (click the table to visit the full ASLRA analysis)

64-bit Linux vs PaX vs ASLR-NG (click the table to visit the full ASLRA analysis)

Besides the much higher entropy of ASLR-NG, it is interesting to point out the Vanilla Linux has more entropy than PaX for the executable object. This fact may have passed unnoticed due to a small issue in the paxtest tool (the address of the main() function is incorrectly read).

Future Work

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 blackguard 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).

  Contact us Home