Randomized allocation makes it nearly impossible to forge pointers, locate sensitive data in the heap, and makes reuse unpredictable.
This is strictly more powerful than ASLR, which does nothing prevent Heartbleed. Moving the base of the heap doesn't change the relative addresses of heap objects with a deterministic allocator. A randomized allocator does change these offsets, which makes it nearly impossible to exploit a heap buffer overrun (and quite a few other heap errors).
That paper only seems to mention heap overflows for purposes of writing to a target object that will later be used for indirection or execution. I don't see how it makes Heartbleed any better to extract a shuffled heap instead of a sorted one. What am I missing?
It's not just a shuffled heap, it's also sparse. Section 4.1 covers heap overflow attacks, with an attacker using overflows from one object to overwrite entries in a nearby object's vtable. Because the objects could be anywhere in the sparse virtual address space, the probability of overwriting the desired object is very low (see section 6.2).
The same reasoning applies to reads. If sensitive objects are distributed throughout the sparse heap, the probability of hitting a specific sensitive object is the same as the probability of overwriting the vtable in the above attack. The probability of reading out any sensitive object depends on the number of sensitive objects and the sparsity of the heap.
There are also guard pages sprinkled throughout the sparse heap. Section 6.3.1 shows the minimum probability of a one byte overflow (read or write) hitting a guard page. This probability increases with larger objects and larger overflows. You can also increase sparsity to increase this probability, at a performance cost.
An attack that reads everything is different from an attack that writes everything; 4.1 doesn't seem to understand that. The latter will just crash the computer like some kind of Core Wars champ. The former can copy out the whole heap! So a writing attacker has to worry about crashing the server or getting caught. A reading attacker can just loop, then run.
The guard pages I believe help---but random guard pages just mean I won't know quite what's protected and what is not. This last week I benefitted quite a bit from being able to reconstruct year old server memory layouts precisely.
In this case, I want a marginal chance of compromise no worse than 2^-192, about the strength of RSA-2048.
Randomized allocation makes it nearly impossible to forge pointers, locate sensitive data in the heap, and makes reuse unpredictable.
This is strictly more powerful than ASLR, which does nothing prevent Heartbleed. Moving the base of the heap doesn't change the relative addresses of heap objects with a deterministic allocator. A randomized allocator does change these offsets, which makes it nearly impossible to exploit a heap buffer overrun (and quite a few other heap errors).