The art of exploiting heap overflow, part 1

Introduction

Let’s start with the simpler version, stack overflow.

Exploiting stack overflow is simple and fun, it turns a useless segfault into a beautiful piece of art — a root shell with full control of the system. It also exposes several essentials of the overflow-based attacks:

  1. The control flow is hijacked by overwriting the return address on the stack. Thanks to x86 CPU architecture, this is nearly handy. But we can learn that overwriting an address (4 bytes on 32bit CPU) is sufficient to change the control flow of the program.
  2. Your shellcode (a tiny asm code spawns a shell) must be placed in a right place large enough to hold it and itself must be tiny, position-independent and fit well into the “context”. For example, a strcpy()-caused overflow certainly doesn’t like any zero in your code. Writing shellcode is another art which deserves a separate post if not a book.
  3. Know when your code is going to be executed, seriously. This seems obvious for stack overflow attack, since we know we will return to caller’s code immediately after the overflowing function. This is a huge difference with heap overflows, and this is one of the obscured parts which is rarely mentioned by existing articles.
  4. The memory is flat and contiguous. The target memory location you want to overwrite is towards the copy. Some stack protection mechanism inserts canary on stack to detect stack overflows.

Heap overflows are much harder and so much fun to exploit than stack overflows because some of the essentials are so different:

  1. Clearly we still have to alert the control flow, but the way to overwrite an address is totally different, it is not as straight as an explicit memory overwrite, it is hidden under neath and in fact it is very hard to find.
  2. The control flow is no longer easy to catch up, because there is no CPU register or return address saved on heap. Instead, we need to catch the control flow somewhere else, for example, still alter the calling function’s stack, or hijack the function pointers in GOT (global offset table) section.
  3. The memory is no longer flat, nor necessarily contiguous. Memory in heap is organized by chunks, chunks contain “metadata” which links them in different free-list’s. Heap is so much stateful, thus understanding and controlling its “state” becomes the key of heap-based overflow exploits.
  4. Heap is so vulnerable because its “metadata” is completely open to users, therefore the attackers are almost free to modify them to manipulate the whole heap. These metadata are used by memory allocator itself, how would you otherwise expect it to “bootstrap” itself?

Because of these “natural” constraints, exploiting heap-based overflow requires a lot of patience and much more efforts and is therefore a much more beautiful piece of art.

On the other hand, glibc code gets more solid after learning how attackers exploit, many of the classic exploits no longer work on the latest glibc, and exploiting a newer version of glibc only becomes harder, but still we can learn their ideas and spirits which are more precious than the exploits themselves.

I will only cover the ptmalloc in glibc, since it is the most widely used one (at least for Linux). Different memory allocators have different algorithms to organize memory chunks and different metadata to represent memory chunks, so all of these exploits I will cover only apply to ptmalloc, but the spirit goes beyond that.

You may ask, there are several articles on Internet explaining heap overflow exploits, why this one? I want to explain heap overflow in a completely different way so that I hope you will not be as confused as I was.

It is going to be a long journey. Let’s start with something really simple.