The art of exploiting heap overflow, part 6

Unlink me

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.