How do ASLR and DEP work?

  • How do Address Space Layout Randomisation (ASLR) and Data Execution Prevention (DEP) work, in terms of preventing vulnerabilities from being exploited? Can they be bypassed?

  • Polynomial

    Polynomial Correct answer

    9 years ago

    Address Space Layout Randomisation (ASLR) is a technology used to help prevent shellcode from being successful. It does this by randomly offsetting the location of modules and certain in-memory structures. Data Execution Prevention (DEP) prevents certain memory sectors, e.g. the stack, from being executed. When combined it becomes exceedingly difficult to exploit vulnerabilities in applications using shellcode or return-oriented programming (ROP) techniques.

    First, let's look at how a normal vulnerability might be exploited. We'll skip all the details, but let's just say we're using a stack buffer overflow vulnerability. We've loaded a big blob of 0x41414141 values into our payload, and eip has been set to 0x41414141, so we know it's exploitable. We've then gone and used an appropriate tool (e.g. Metasploit's pattern_create.rb) to discover the offset of the value being loaded into eip. This is the start offset of our exploit code. To verify, we load 0x41 before this offset, 0x42424242 at the offset, and 0x43 after the offset.

    In a non-ASLR and non-DEP process, the stack address is the same every time we run the process. We know exactly where it is in memory. So, let's see what the stack looks like with the test data we described above:

    stack addr | value
    -----------+----------
     000ff6a0  | 41414141
     000ff6a4  | 41414141
     000ff6a8  | 41414141
     000ff6aa  | 41414141
    >000ff6b0  | 42424242   > esp points here
     000ff6b4  | 43434343
     000ff6b8  | 43434343
    

    As we can see, esp points to 000ff6b0, which has been set to 0x42424242. The values prior to this are 0x41 and the values after are 0x43, as we said they should be. We now know that the address stored at 000ff6b0 will be jumped to. So, we set it to the address of some memory that we can control:

    stack addr | value
    -----------+----------
     000ff6a0  | 41414141
     000ff6a4  | 41414141
     000ff6a8  | 41414141
     000ff6aa  | 41414141
    >000ff6b0  | 000ff6b4
     000ff6b4  | cccccccc
     000ff6b8  | 43434343
    

    We've set the value at 000ff6b0 such that eip will be set to 000ff6b4 - the next offset in the stack. This will cause 0xcc to be executed, which is an int3 instruction. Since int3 is a software interrupt breakpoint, it'll raise an exception and the debugger will halt. This allows us to verify that the exploit was successful.

    > Break instruction exception - code 80000003 (first chance)
    [snip]
    eip=000ff6b4
    

    Now we can replace the memory at 000ff6b4 with shellcode, by altering our payload. This concludes our exploit.

    In order to prevent these exploits from being successful, Data Execution Prevention was developed. DEP forces certain structures, including the stack, to be marked as non-executable. This is made stronger by CPU support with the No-Execute (NX) bit, also known as the XD bit, EVP bit, or XN bit, which allows the CPU to enforce execution rights at the hardware level. DEP was introduced in Linux in 2004 (kernel 2.6.8), and Microsoft introduced it in 2004 as part of WinXP SP2. Apple added DEP support when they moved to the x86 architecture in 2006. With DEP enabled, our previous exploit won't work:

    > Access violation - code c0000005 (!!! second chance !!!)
    [snip]
    eip=000ff6b4
    

    This fails because the stack is marked as non-executable, and we've tried to execute it. To get around this, a technique called Return-Oriented Programming (ROP) was developed. This involves looking for small snippets of code, called ROP gadgets, in legitimate modules within the process. These gadgets consist of one or more instructions, followed by a return. Chaining these together with appropriate values in the stack allows for code to be executed.

    First, let's look at how our stack looks right now:

    stack addr | value
    -----------+----------
     000ff6a0  | 41414141
     000ff6a4  | 41414141
     000ff6a8  | 41414141
     000ff6aa  | 41414141
    >000ff6b0  | 000ff6b4
     000ff6b4  | cccccccc
     000ff6b8  | 43434343
    

    We know that we can't execute the code at 000ff6b4, so we have to find some legitimate code that we can use instead. Imagine that our first task is to get a value into the eax register. We search for a pop eax; ret combination somewhere in any module within the process. Once we've found one, let's say at 00401f60, we put its address into the stack:

    stack addr | value
    -----------+----------
     000ff6a0  | 41414141
     000ff6a4  | 41414141
     000ff6a8  | 41414141
     000ff6aa  | 41414141
    >000ff6b0  | 00401f60
     000ff6b4  | cccccccc
     000ff6b8  | 43434343
    

    When this shellcode is executed, we'll get an access violation again:

    > Access violation - code c0000005 (!!! second chance !!!)
    eax=cccccccc ebx=01020304 ecx=7abcdef0 edx=00000000 esi=7777f000 edi=0000f0f1
    eip=43434343 esp=000ff6ba ebp=000ff6ff
    

    The CPU has now done the following:

    • Jumped to the pop eax instruction at 00401f60.
    • Popped cccccccc off the stack, into eax.
    • Executed the ret, popping 43434343 into eip.
    • Thrown an access violation because 43434343 isn't a valid memory address.

    Now, imagine that, instead of 43434343, the value at 000ff6b8 was set to the address of another ROP gadget. This would mean that pop eax gets executed, then our next gadget. We can chain gadgets together like this. Our ultimate goal is usually to find the address of a memory protection API, such as VirtualProtect, and mark the stack as executable. We'd then include a final ROP gadget to do a jmp esp equivilent instruction, and execute shellcode. We've successfully bypassed DEP!

    In order to combat these tricks, ASLR was developed. ASLR involves randomly offsetting memory structures and module base addresses to make guessing the location of ROP gadgets and APIs very difficult.

    On Windows Vista and 7, ASLR randomises the location of executables and DLLs in memory, as well as the stack and heaps. When an executable is loaded into memory, Windows gets the processor's timestamp counter (TSC), shifts it by four places, performs division mod 254, then adds 1. This number is then multiplied by 64KB, and the executable image is loaded at this offset. This means that there are 256 possible locations for the executable. Since DLLs are shared in memory across processes, their offsets are determined by a system-wide bias value that is computed at boot. The value is computed as the TSC of the CPU when the MiInitializeRelocations function is first called, shifted and masked into an 8-bit value. This value is computed only once per boot.

    When DLLs are loaded, they go into a shared memory region between 0x50000000 and 0x78000000. The first DLL to be loaded is always ntdll.dll, which is loaded at 0x78000000 - bias * 0x100000, where bias is the system-wide bias value computed at boot. Since it would be trivial to compute the offset of a module if you know ntdll.dll's base address, the order in which modules are loaded is randomised too.

    When threads are created, their stack base location is randomised. This is done by finding 32 appropriate locations in memory, then choosing one based on the current TSC shifted masked into a 5-bit value. Once the base address has been calculated, another 9-bit value is derived from the TSC to compute the final stack base address. This provides a high theoretical degree of randomness.

    Finally, the location of heaps and heap allocations are randomised. This is computed as a 5-bit TSC-derived value multiplied by 64KB, giving a possible heap range of 00000000 to 001f0000.

    When all of these mechanisms are combined with DEP, we are prevented from executing shellcode. This is because we cannot execute the stack, but we also don't know where any of our ROP instructions are going to be in memory. Certain tricks can be done with nop sleds to create a probabilistic exploit, but they are not entirely successful and aren't always possible to create.

    The only way to reliably bypass DEP and ASLR is through an pointer leak. This is a situation where a value on the stack, at a reliable location, might be used to locate a usable function pointer or ROP gadget. Once this is done, it is sometimes possible to create a payload that reliably bypasses both protection mechanisms.

    Sources:

    Further reading:

    obligatory tl;dr

    @TerryChia You mean ta;cr? - Too Awesome, Couldn't Read ;)

    I unofficially bestow you the title of Sir Polynomial. Neat answer. xD

    Yeah... It's almost as if the question was *made* for this answer. Wow.

    I don't usually go for these self-answers. But this is such a good answer, I've been doing this stuff for years and I leant a few things here. Great job +1

    @lynks I find that self-answered questions are either repwhoring or for the good of the community. I assure you that I posted it with the latter intention. It took me a very long time to properly understand DEP and ASLR, I just hope that this answer will help someone else understand it.

    "The only _reliable_ way to bybass DEP and ASLR": _that's_ the tricky point. The attacker does not need a reliable way; often, a way which works only once in a thousand times is good enough, since he just needs to try a thousand times (which can often be scripted). This illustrates the limits to the effectiveness of ASLR and DEP as security mechanisms.

    @ThomasPornin Yeah, the nop sled technique can be good. Downside of doing it a few thousand times is that usually there's a crash after the first time.

    Great explanation, and perfect length

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM