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?
To complement @Polynomial's self-answer: DEP can actually be enforced on older x86 machines (which predate the NX bit), but at a price.
The easy but limited way to do DEP on old x86 hardware is to use segment registers. With current operating systems on such systems, addresses are 32-bit values in a flat 4 GB address space, but internally each memory access implicitly uses a 32-bit address and a special 16-bit register, called a "segment register".
In so-called protected mode, segment registers point to an internal table (the "descriptor table" -- actually there are two such tables, but that's a technicality) and each entry in the table specifies the characteristics of the segment. In particular, the types of allowed accesses, and the size of the segment. Moreover, code execution implicitly uses the CS segment register, while data access uses mostly DS (and stack access, e.g. with the
(Note that segments are applied on address space; the MMU is still active, on a lower layer, so the trick explained above is per-process.)
This is cheap to do: the x86 hardware does enforce segments, systematically (and the first 80386 was already doing it; actually, the 80286 already had such segments with boundaries, but only 16-bit offsets). We can usually forget them because sane operating systems set the segments to begin at offset zero and be 4 GB long, but setting them otherwise does not imply any overhead which we did not already have. However, as a DEP mechanism, it is inflexible: when some data block is requested from the kernel, the kernel must decide whether this is for code or not for code, because the boundary is fixed. We cannot decide to dynamically convert any given page between code-mode and data-mode.
The fun but somewhat more expensive way to do DEP uses something called PaX. To understand what it does, one must go into some details.
The MMU on x86 hardware uses in-memory tables, which describe the status of every 4 kB page in the address space. The address space is 4 GB, so there are 1048576 pages. Each page is described by a 32-bit entry in a sub-table; there are 1024 sub-tables, each holding 1024 entries, and there is one main table, with 1024 entries which point to the 1024 sub-tables. Each entry tells where the pointed-to object (a sub-table, or a page) is in RAM, or whether it is there at all, and what are its access rights. The root of the issue is that access rights are about privilege levels (kernel code vs userland) and only one bit for the access type, thus allowing "read-write" or "read-only". "Execution" is considered to be a kind of read access. Hence, the MMU has no notion of "execution" being distinct from data access. That which is readable, is executable.
(Since the Pentium Pro, back in the previous century, x86 processors know of another format for the tables, called PAE. It doubles the size of entries, which leaves room for addressing more physical RAM, and also adding a NX bit -- but that specific bit was implemented by the hardware only around 2004.)
However, there is a trick. RAM is slow. To perform a memory access, the processor must first read the main table to locate the sub-table that it must consult, then do another read to that sub-table, and only at that point does the processor know whether the memory access should be allowed or not, and where in physical RAM the accessed data really is. These are read accesses with full dependency (each access depends on the value read by the previous) so this pays full latency, which, on modern CPU, can represent hundreds of clock cycles. Therefore, the CPU includes a specific cache which contains the most recently accessed MMU table entries. This cache is the Translation Lookaside Buffer.
From the 80486 onwards, x86 CPU do not have one TLB, but two. Caching works on heuristics, and heuristics depend on access patterns, and access patterns for code tend to differ from access patterns for data. So the smart people at Intel/AMD/other found it worthwhile to have a TLB dedicated to code access (execution), and another for data access. Moreover, the 80486 has an opcode (
So the idea is the following: make the two TLB have different views of the same entry. All pages are marked in the tables (in RAM) as "absent", thus triggering an exception upon access. The kernel traps the exception, and the exception includes some data about the type of access, in particular whether it was for code execution, or not. The kernel then invalidates the newly read TLB entry (the one which says "absent"), then fills the entry in RAM with some rights which allow access, then forces one access of the needed type (either data read or code execution), which feeds the entry into the corresponding TLB, and only that one. The kernel then promptly sets the entry in RAM back to absent, and finally returns to the process (back to trying again the opcode which triggered the exception).
The net effect is that, when the execution comes back to the process code, the TLB for code or the TLB for data contains the appropriate entry, but the other TLB does not, and will not since the tables in RAM still say "absent". At that point, the kernel is in position to decide whether to allow execution or not, independently from whether it allows data access or not. It can thus enforce NX-like semantics.
The Devil hides in the details; in this case, there is room for a whole legion of demons. Such a dance with the hardware is not easy to implement properly. Especially on multi-core systems.
The overhead is the following: when an access is performed and the TLB does not contain the relevant entry, the tables in RAM must be accessed, and that alone implies losing a few hundred cycles. To that cost, PaX adds the overhead of the exception, and the management code which fills the right TLB, thus turning the "a few hundred cycles" into "a few thousand cycles". Fortunately, TLB misses are right. The PaX people claim to have measured a slowdown of as little as 2.7% on a big compilation job (this depends on the CPU type, though).
The NX bit makes all of this obsolete. Note that the PaX patchset also contains some other security-related features, such as ASLR, which is redundant with some functionality of newer official kernels.
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
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:
As we can see,
We've set the value at
Now we can replace the memory at
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:
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:
We know that we can't execute the code at
When this shellcode is executed, we'll get an access violation again:
The CPU has now done the following:
Now, imagine that, instead of
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
When DLLs are loaded, they go into a shared memory region between
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
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
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.