How does the ASLR & DEP security work?

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 security 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 equivalent 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 a 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:

Windows Internals 5th Edition - Mark Russinovich

An Analysis of ASLR in Windows Vista - Symantec

ASLR on Wikipedia

DEP on Wikipedia

Further reading:

Stack-based exploit writing - CoreLAN

Bypassing stack cookies, SafeSEH, SEHOP, HW DEP and ASLR - CoreLAN

Bypassing ASLR/DEP - exploit-db