The art of exploiting heap overflow, part 2

Memory layout

Virtual memory is a wonderful abstraction provided by modern operating systems, it greatly simplifies the memory management in user-space, with it every process has a unified, contiguous and flat memory space.

For example, on 32bit x86, the virtual memory space of each process is as simple as the following:

The operating system transparently handles all the complexity behind the scenes: it maps a virtual memory page to a physical memory page, loads or unloads a page from/to memory to/from disk on demand. This is what you learned from your OS class in college.

But in practice:

1. 0x00000000 is a very special address, it is “reserved” for NULL pointer, so you can’t access it no matter how. For Linux kernel, this is specified via /proc/sys/vm/mmap_min_addr, by default the first 16 pages are “reserved”.
2. On i386 Linux, the bottom of the address space (1G) is mapped to kernel address space, user-space can’t access it.

Therefore the memory space is actually something like this:

Except the above, each process is free to manage the rest of its memory space. The problem now becomes how does each process manage it?

This is still a hard problem, because at very first we have to decide where in memory to load our code before running any code to manage it! There is no magic, the answer is the linker initially picks an address for OS to load the code (.text) into memory space, this address is recorded in the ELF (the format of the binary) program header of the binary on disk. (ld defines this as SEGMENT_START in ld script)

And because we separate code from data, the linker has to pick up an address for the data (.data and .bss) too. We end up having the following layout:

In order to make a program running, we need a stack too. And stack, by definition, is FILO, therefore it “naturally” grows from bottom up (at least on x86). Where to put the stack in our memory space anyway?

Quiz: what if stack grew from top down?

It is surprisingly simple: as it grows up, Linux kernel just puts it at the bottom of the user-space address, in other words, right above the kernel address space. This happens when we execute a program via the syscall execve(). (Linux kernel defines it as STACK_TOP_MAX) And of course, kernel also helps us to setup the initial arguments for the main() function on this stack too: argc, argv and envp.

Now comes the heap!

Stack is for these statically allocated storage, it is transparent to your C code. But it is not enough, we can’t decide everything at compile-time, we want to dynamically allocate memory at run-time too, therefore we need some interface to manage this kinda of memory dynamically, this is what we called heap.

Where to put the heap into our memory space? Heap doesn’t have any order in nature, essentially it is fine to put it anywhere as long as not conflict with the rest. A simple solution is to let it grow downwards, so we can just put is right after the data of the program: a) the program itself won’t grow, so won’t conflict with heap, b) it is the furthest place away from stack, so hard to have a clash.

Now an overview of the process memory layout is:

x86_64 is pretty much similar except it splits the address space evenly for kernel space and user space.

Remember the last point, it is important for the following part. In the next part, we will see how the heap itself is managed.