Increasing the range of address-space layout randomization [LWN.net]

Increasing the range of address-space layout randomization

Posted Dec 20, 2015 5:40 UTC (Sun) by MattJD (subscriber, #91390)
In reply to: Increasing the range of address-space layout randomization by PaXTeam
Parent article: Increasing the range of address-space layout randomization

Thanks for responding with such a thorough answer! I found the document through Google, which is why I wasn't sure when it came about. I didn't realize going up a folder would reveal the date (I'm so used to websites not having sensible navigation these days I don't even notice).

>i didn't improve anyone's ASLR, i invented the whole thing ;).

Sorry, I meant to imply how it is better then upstream's implementation. I realize you guys had ASLR first, it wasn't my intention to imply otherwise.

> i don't think i mentioned address space exhaustion anywhere, perhaps you're thinking of entropy pool exhaustion? what (carelessly implemented) ASLR can affect is address space *fragmentation* [...]

I meant address space fragmentation, which you discussed. So, in your experience, you find by dividing the sections you get bigger bang for your buck (since you get 16 bits of randomness at least per section, compared to upstream's 8). Is there anything else you do to avoid address space fragmentation? Or does this limit ASLR's effect on fragmentation enough that it is equivalent to running without?

> depends on what 'doing ROP' means. if you mean some full-blown Turing-complete computation then it's not enough to learn the code layout[...]

Ok, I can see where you are coming from. Basically you are giving the best case scenario, which is the general case. Specific exploits *may* reduce this, depending upon the details.

When you mention for ROP you need to know the stack address, is that for the case where you don't have a stack overflow that takes over a return instruction? As I understand ROP, isn't that the usual case? And once I get control over it once, isn't that enough to execute my code (with your mentioned limitation regarding data/mmap addresses)? Or am I missing something about how ROP works? I do understand why the other addresses matter.

> no, it's as written, R-A. perhaps the 'attack the bits' phrase isn't as clear as i intended it[...]

Ok, that makes sense then. That phrase did confuse me, but your comment clears that up. If I get time to take a wack at it, would a patch against the document be welcome? No guarantees on when I might surface with that though.

Also, is there any other benefits to your ASLR implementation versus upstream's? That was why I was originally looking for a design document. I recognize I know only a little versus your team's expertise, so I apologize if I missed any differences, especially if it was mentioned in the document. I'm just trying to understand the potential issues implementing ASLR.

to post comments

Increasing the range of address-space layout randomization

Posted Dec 20, 2015 13:01 UTC (Sun) by PaXTeam (guest, #24616) [Link]

re fragmentation, with the region based approach there is no fragmentation beyond what the vanilla kernel causes. what does change is the inter-region gap size which limits the maximum size of mmap requests that can fit since that gap changes on each run. to reduce *that* effect, PaX limits the randomization applied to the MSBs. my non-scientific rule-of-thumb is to leave the 4 MSBs undisturbed, that is, the largest gap changes by at most 1/8th of the address space size which in practice means that any app running into trouble with it would likely have problems regardless of ASLR.

> Specific exploits *may* reduce this, depending upon the details.

yes, i tend to describe the limits of any given defense mechanism, in case of ASLR it's obvious what the lower limit is, the less obvious case is the upper limit (of the entropy a given attack may have to overcome). any real life case will fall somewhere in-between and let's not forget about the attack detection/reaction mechanism that is also part of the ASLR design (which bounds the probability of success) that is mostly omitted in other implementations.

> When you mention for ROP you need to know the stack address, is that for the case where you don't have a stack overflow that takes over a return instruction?

well, when i speak of ROP, i actually mean 'execute existing code out of original program order' (see pax.txt about the threat model) which these days is called 'code reuse attack', i.e., it's the general case, not a specific one for just controlling a return address. in any case, when you think of the stack buffer overflow case, to pass a pointer parameter to a function where the (attacker-provided) data is also on the stack somewhere then you somehow need to learn that stack address. whether that requires learning the stack entropy or just some offsetting a register via gadgets depends on the situation.

> If I get time to take a wack at it, would a patch against the document be welcome?

sure but i'd appreciate an update on the implementation details even more ;).

> Also, is there any other benefits to your ASLR implementation versus upstream's?

if there wasn't any, i wouldn't still be maintaining my code after all these years ;). one obvious benefit is the much more concise and understandable implementation, there're basically 4 per-arch constants (PAX_DELTA_*) that will tell you what region gets randomized by how much, no need for reimplementing the effectively same helper functions for each arch as vanilla does. there're also finer details like handling corner cases on address space exhaustion or randomizing PIEs or disallowing the runtime control of ASLR (PF_RANDOMIZE) or safer brk randomization, etc.