# The art of exploiting heap overflow, part 6

With enough knowledge of ptmalloc internals, now it is time to see how to exploit a heap overflow. `Unlink()` is the classic and probably the simplest one.

We see free memory chunks are chained in different bins, either singly linked or doubly linked. For a doubly linked list, `unlink()` is a very simple and common function to remove a node from the list. You had probably already implemented one even in your college.

Old Glibc implemented it as a macro like this:

`#define unlink( P, BK, FD ) {          \  BK = P->bk;                          \  FD = P->fd;                          \  FD->bk = BK;                         \  BK->fd = FD;                         \}`

where `P` is the pointer to the chunk to remove, `BK` and `FD` are two temporary local variables to store `P`’s neighbors, which are not necessarily needed in our context.

Now, imagine we fully control the chunk pointed by `P`, we are free to put any values to `P->bk` and `P->fd`. What would we get after glibc calls this `unlink()` on our chunk?

Forget the meaning of `unlink()`, it is not what we are interested. If we break down the above pieces of code and re-examine it from the pure C language’s point of view, we can derive (assume 32bit CPU):

`BK = *(P + 12);FD = *(P + 8);*(FD + 12) = BK;*(BK + 8) = FD;`

So what memory changes?

1. The memory at `FD+12` is overwritten with `BK`, 4 bytes (on 32bit CPU)
2. The memory at `BK+8` is overwritten with `FD`, 4 bytes (on 32bit CPU)
3. `BK` and `FD` are what we could fill into the chunk at `P`

In short: we can overwrite arbitrary 4 bytes at two specified places!!! This is more than enough to redirect the control flow.

But hold on… we can’t fully control the values we write, can we? If `FD+12` points to the return address on stack, `BK` is the address of our shellcode, our shellcode is forced to be overwritten at offset 8 too! This means our shellcode has to jump over this part!

Now, we can see why this is a beautiful piece of art: `unlink()` is a function normally used to remove a node from a doubly linked list, now turned into a “weapon” to overwrite arbitrary 4-byte memory, which is totally irrelevant to its intention!

This is just amazing…

The next step is, of course, we have to find out which `unlink()` we can “reuse” in glibc. Our first reaction is probably `malloc()` where we possibly get a memory chunk from a doubly linked bin, this rules out fast bins, and non-fast bins are harder to control because of one more indirection in unsorted bin…

In fact, there is a nice place in `free()` path which I didn’t mention earlier. For memory chunks don’t fit in fast bins, they could be coalesced into either previous chunk or next chunk, and of course only if that chunk is free too, so it has to be unlinked before coalesce!

`    /* consolidate backward */    if (!prev_inuse(p)) {      prevsize = prev_size (p);      size += prevsize;      p = chunk_at_offset(p, -((long) prevsize));      unlink(p, bck, fwd);    }`

But wait… Doesn’t this depend on the state of its previous chunk too? No, we can cheat again here, because glibc checks `prev_size` to know if its previous chunk is free or not, we control the whole chunk metadata including `prev_size` ! Bingo!

Putting every piece together, here is what we have to do in order to make this work:

1. Allocate two adjacent chunks, overflow happens on the first one so that we could totally control the second one.
2. Control the metadata of the second chunk:

2.1 Unset the `prev_inuse` bit in `prev_size` .

2.2 Set `prev_size` to `0` so we unlink this chunk instead of the first!

2.3 Set `size` to a value larger than the max of fast bins.

2.4 Change `FD` in the second chunk’s metadata to our `\$target_address-12` , where `\$target_address`, for example, is the address of the return address of on the current stack; change `BK` to the address of our shellcode.

3. `Free()` the second chunk, during which time our target address is changed to the address of our shellcode by `unlink()` itself.

4. Control flow will be redirected to our shellcode when, for example, the current function returns.

5. Pwned!

Newer glibc already hardens this by adding sanity checks for chunk headers in `unlink()`:

`if (__builtin_expect (chunksize(P) != prev_size (next_chunk(P)), 0))      \      malloc_printerr (check_action, "corrupted size vs. prev_size", P, AV);  \    FD = P->fd;              \    BK = P->bk;              \    if (__builtin_expect (FD->bk != P || BK->fd != P, 0))        \      malloc_printerr (check_action, "corrupted double-linked list", P, AV);  \    ...`

so this “unlink me” exploit no longer works. But we get the spirit, the spirit that inspires us to find new ways to exploit with more than just unlink, the spirit will go beyond just glibc. And in fact we will see another exploit with very similar spirit later.

Linux kernel and security stuffs

Love podcasts or audiobooks? Learn on the go with our new app.

## Cong Wang

Linux kernel and security stuffs