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
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
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
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
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
The technical details of the ASLR-NG are in the PhD. Thesis of Hector Marco-Gisbert (defended