# Address Space Layout Randomization Next Generation
## 7 ASLR-NG: Address Space Layout Randomization Next Generation
### Addressing Fragmentation  
When virtual memory size is small, fragmentation is an issue, because the more objects that are independently randomized, the more fragmented the memory. In dynamic memory, the fragmentation problem is defined as [43] \"the inability to reuse memory that is free.\"  
There is no simple way to measure fragmentation, but the worst case depend on: (1) the number of objects already allocated, (2) their size, (3) the relative position of each one and (4) the size of the new request. If all objects, \(n\), are independently randomized, the worst case occurs when the allocated objects are of one page size and they are evenly distributed along the whole memory space. In this case, the maximum guaranteed size is approximated by:  
\[\text{new\_obj\_size}\lesssim\frac{\text{VM\_SIZE}}{n+1}\]  
On x86_64 fragmentation is not a issue because of the very large number of mapped objects needed to cause an error. For example, a 1 GB memory request will not fail until 2\({}^{17}\) = 131,072 objects have been mapped.  
On the other hand, fragmentation is a real problem in 32-bit systems. For example, a memory request of 25 MB is not guaranteed after just 122 requests (of page size), while a request for 256 MB may fail after mapping just 12 objects, including the stack, vDSO, executable, heap, each library, etc. Therefore, it is not practical to randomize each object independently in 32-bit systems, without addressing the fragmentation issue.  
ASLR-NG addresses this issue by reserving a range of virtual space, the amount of which is specified as a percentage of the available VM size. When a requested object does not fit into the non-reserved space, the allocation algorithm automatically uses the reserved space, without degrading the entropy of these objects and regardless of their size.  
Figure 15 shows the result of allocating multiple objects in ASLR-NG. Objects 1 and 3 fit into the non-reserved area, and so they are placed there, but for objects 2 and 4, there are no free gaps to hold them on the non-reserved area. In this case, the algorithm performs a top-down, first-fit strategy. Note that objects allocated in the reserved area will 'inherit' the entropy of the lowest object in the non-reserved area.  
Although reserving a percentage of the VM will reduce the range for available randomization, ASLR-NG uses a novel strategy to regain lost entropy, whereby the reserved area is randomly placed at the top or the bottom of the virtual memory space. For example, by reserving 50%, an attacker cannot know on which side (top or bottom) the objects will be located, which forces them to consider the whole VM space. As a result, there is no entropy penalty with this strategy. Only when the reserved area is larger than 50%, is there a small amount of entropy degradation. The expression which relates the loss of entropy to the percentage of reserved area is:  
Figure 15: ASLR-NG: A 50% example of a reserved area.  
\[f(x)=\begin{cases}0,&\text{if }x\leq 50\%\\ -1-\log_{2}\left(1-\frac{x}{100}\right),&\text{otherwise}\end{cases}\]  
where \(x\) is the percentage of the reserved area, and \(f(x)\) gives the number of bits that have to be subtracted from the total VM space entropy. For example, reserving 50% on an i386, the largest guaranteed object is 1.5 GB and entropy is not reduced. If 2/3 of the VM space is reserved, then it is possible to allocate an object up to 2 GB in size, and at the cost of reducing entropy by only 0.5 bits. Therefore, the ASLR-NG design has both more entropy and less fragmentation.