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

Increasing the range of address-space layout randomization

Posted Dec 17, 2015 16:39 UTC (Thu) by MattJD (subscriber, #91390)
In reply to: Increasing the range of address-space layout randomization by spender
Parent article: Increasing the range of address-space layout randomization

In the interest of learning more about how ASLR can be improved, I did a quick google search and found https://pax.grsecurity.net/docs/aslr.txt , which I assume is an up to date reference on how you guys implement ASLR from a high level perspective? I'm just trying to understand the high level parts like this article before I dive into code.

Reading through that document suggest you guys improved on what the kernel does by allowing different amounts of randomization over different parts of the program. That seems like a good idea to move back upstream as well. However, you then mention by using ASLR you run the risk of exhausting the available virtual memory to a process, which this article mentions as the reason why upstream only does 8bits of randomization. Are you guys doing something else to minimize this problem? If I increase the number of bits used with upstream's implementation, would it run the same risks, or does your system decrease them further then upstream with comparable number of used bits?

Also, when you talk about probability you use the following formulas:

The probabilities of success within x number of attempts are given by the
following formulae (for guessing and brute forcing, respectively):

(1) Pg(x) = 1 - (1 - 2^-N)^x, 0 <= x
(2) Pb(x) = x / 2^N, 0 <= x <= 2^N

where N = Rs-As + Rm-Am + Rx-Ax, the number of randomized bits to find.
(from the above link)

Except, do I have to break all the ASLR (thus use the value of N) for all attacks? For instance, if I'm doing ROP I just need the executable layout as I would only use the stack in a relative fashion and I don't need to care about the data layout. Or once I have ROP working I can just read the mappings anyway.

Furthermore, wouldn't the probability for a section be R/A, not R-A? If I have 8 bits of random but I can attack 2 bits at a time, I can get the answer in 2^4 guess since I can attack a pair of bits at a time. Using your formula, I'd have 2^6 guesses. I'm not sure why I'd have those extra bits to get? And furthermore if A is 1, I have to find all of R, not R-1.

I'm trying to avoid NIH mindset and thus understand your system. Since Pax has been around for longer, I wouldn't be surprised that you have answers to these questions already.

Increasing the range of address-space layout randomization

Posted Dec 20, 2015 4:12 UTC (Sun) by PaXTeam (guest, #24616) [Link] (2 responses)

>[...] I assume is an up to date reference on how you guys implement ASLR from a high level perspective?

if you go back to the doc homepage (https://pax.grsecurity.net/docs/) you'll see its last modification time, so no, it's not exactly up-to-date as far as implementation details go but the design hasn't changed since 2001.

> Reading through that document suggest you guys improved on what the kernel does by allowing different
> amounts of randomization over different parts of the program.

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

> However, you then mention by using ASLR you run the risk of exhausting the available virtual memory to a process[...]

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* which is why PaX settles on per-region randomization only to minimize it (another reason is that in practice an attacker only ever really needs to know a single library's address, so there's no point in randomizing per-mmap). that said, fragmentation can cause similar effects to exhaustion (failing mmap requests) but they're different problems.

> [...]Except, do I have to break all the ASLR (thus use the value of N) for all attacks?

it always depends on the situation, this is what the A* bits represent. ad absurdum, you don't need to guess at all because you can learn the needed addresses a priori, or don't need fixed addresses at all, etc.

> For instance, if I'm doing ROP I just need the executable layout as I would only use the stack in a relative fashion and I don't need to care about the data layout.

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, you obviously have to be able to pass data to the code which means learning data addresses which may be in different regions than the ROP gadgets you found. e.g., if you take a classical stack based buffer overflow and want to call system() then you'll need to learn both stack and mmap addresses (and for general ROP, also the content at code addresses).

> Or once I have ROP working I can just read the mappings anyway.

it depends on what you can do with 'ROP working', whether your gadgets are powerful enough, whether you can access /proc/self/maps or scavenge memory for addresses to other regions, etc.

> Furthermore, wouldn't the probability for a section be R/A, not R-A?

no, it's as written, R-A. perhaps the 'attack the bits' phrase isn't as clear as i intended it, but the example i gave (it's called heap spraying these days) helps understand it: if you can control enough contiguous memory then you can effectively 'erode' the entropy in the lower bits of the randomized addresses. when R=A then you basically control a large enough region so that you can just choose a fixed address and be assured that it'll be mapped with your data during the attack (the maths is then R-A=0 -> 2^0=1 -> one shot exploit, no need to guess anything).

Increasing the range of address-space layout randomization

Posted Dec 20, 2015 5:40 UTC (Sun) by MattJD (subscriber, #91390) [Link] (1 responses)

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.

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.