The art of exploiting heap overflow, part 7

7 min readSep 1, 2017

House of unlink

Although “unlink me” no longer works on new glibc, we are inspired by this unlink hack, if we think it in another way, all link or unlink operations on a doubly-linked list node could turn into a memory overwriting weapon.

This is a type of heap overflow exploits, I call it “House of unlink”. “House of Mind” , “House of Lore” and “House of spirit” fit to this type. Now we need to find out other “unlink” or “link” hack we can trigger in glibc code.

Without going into the boring details of each exploit, let’s start from source code. If we know how to reach these “unlink”s, we know what is the scenario to exploit it.

House of Mind

Remember the how we use the unsorted bin? It is a temporary place to hold chunks before they are put into large/small bins, it is a doubly linked list too. If you free() a chunk which fits in a small/large bins, it is linked into this unsorted bin first. You can smell a “link” operation is there.

Looking into the source code of free() (_int_free()):

The size of this chunk has to fit in non-fast bins and has to be non-mapped, to skip the first check and pass the second check:

if ((unsigned long)(size) <= (unsigned long)(get_max_fast ()) 
{...
}else if (!chunk_is_mmapped(p)) {
...
}

2. There are many more checks we have to skip, don’t worry, most of them will be under control:

if (__glibc_unlikely (p == av->top))
{
...
}if (__builtin_expect (contiguous (av)
                          && (char *) nextchunk
                          >= ((char *) av->top + chunksize(av->top)), 0))
{
...
}if (__glibc_unlikely (!prev_inuse(nextchunk)))
{
...
}if (__builtin_expect (chunksize_nomask (nextchunk) <= 2 * SIZE_SZ, 0) || __builtin_expect (nextsize >= av->system_mem, 0))
{
...
}if (!prev_inuse(p)){
...
}
if (nextchunk != av->top) {
      ...
      if (!nextinuse) {
      ...
      } else
      ...

3. Eventually we want to reach this link operation:

      bck = unsorted_chunks(av);
      fwd = bck->fd;
      p->fd = fwd;
      p->bk = bck;
      ...
      bck->fd = p;
      fwd->bk = p;

Looks a lot similar to the previous “unlink”, right? Now, we do a slightly more complicated translation again (on i386):

bck = &av->bins[0] - 8;
fwd = *(av->bins[0]);

...*(&av->bins[0]) = p;
*(fwd + 12) = p;

Why bck could be a weird &av->bins[0]-8 here? It is tricky here, because inside av->bins[], only ->fd and ->bk pointer pairs are stored, however, virtually we still think it as a whole struct malloc_chunk except we can only dereference ->fd and ->bk!

#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))                           \
             - offsetof (struct malloc_chunk, fd))

Now, we have p which is the overflowed chunk we are freeing, if we put shellcode there, we could write the address of our shellcode into somewhere… Interesting now?

All what we need to do next is to control av->bins[0] and of course to pass the above awfully many checks. Sounds impossible? If we could control both p and its arena header, this task is not only possible but also doable. So how to control the arena header of p?

Usually it is impossible, because the arena header is before both p and its previous overflowing chunk, beyond what we could overwrite. However, with “House of Mind”, the author discovers and carefully crafts such a scenario: p is not just a simple memory chunk follows the overflowing chunk, but also it is the first chunk in an internal heap (remember heap_info?), and all the area between these two chunks are overflowable.

#define heap_for_ptr(ptr) \
  ((heap_info *) ((unsigned long) (ptr) & ~(HEAP_MAX_SIZE - 1)))
#define arena_for_chunk(ptr) \
  (chunk_main_arena (ptr) ? &main_arena : heap_for_ptr (ptr)->ar_ptr)

Ah, this changes the game! Because that means we can control the heap_info, and we know it contains a pointer to its arena header, so we can make it point to our own arena header! Bingo! Here is the plan:

Now this is how it works:

Carefully forge an arena header, put it in the area between the overflowing chunk and chunk pointed by p . And make sure this header will pass above listed checks. Mostly importantly, make sure its ->bins[0] contains the $target_address-12
When hitting the internal heap boundary aligned by 0x100000, forge a heap_info there, make sure its ->ar_ptr points to our forged arena.
Forge the chunk header for p make sure it pass the above listed checks.
Now, free(p) will trigger the above “link” operation, the $target_address will be overwritten with our shellcode address!

There are still two problems need to clarify:

p points to the chunk header, but our shellcode has to be after this header (otherwise we can’t pass the checks), this means we have to put a jmp +14 instruction into the beginning field prev_size (and pad with nop):

% rasm2 'jmp 0xe; nop; nop'
eb0c9090

x86 is little-endian, so the PREV_INUSE bit is set coincidentally!

2. Where the hell is the control flow going? We are right in free(p) , as the author of “House of Mind” demonstrated, it is the last function before exit, and we are not inside any sub-function… Where can we hijack it? The author wisely picks the address of an destructor entry (either when you use C++ or you mark a function with GCC destructor attribute) as the target address. And the entry in .dtors section is called after exit() . In practice, be aware that not all ELF binaries have .dtors !

House of Lore

Still the unsorted bin! After we free() a chunk fits into a small/large bin, it is linked into the unsorted bin as the last, then, if the last one in unsorted bin does not match a new malloc() request it will be unlinked from this unsorted bin and finally put into a small/large bin!

We already exploit the “link” operation in “House of Mind”, now we exploit its following “unlink”!

Let’s check the source code first, but this time it is in malloc() function:

if (in_smallbin_range (nb))
    {
      idx = smallbin_index (nb);
      bin = bin_at (av, idx);    if ((victim = last (bin)) != bin)
        {
          if (victim == 0) /* initialization check */
            malloc_consolidate (av);
          else
            {
              bck = victim->bk;
              set_inuse_bit_at_offset (victim, nb);
              bin->bk = bck;
              bck->fd = bin;            if (av != &main_arena)
                set_non_main_arena (victim);
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }
        }
    }

It is more complicated this time because it requires more steps to reach this code. Here is the list of requirements:

The overflowed chunk, p, which fits in a small bin, is freed and put into the unsorted bin first.
Allocate another chunk in small bin range whose size can’t match p, therefore p is moved from the unsorted bin to a small bin as its last.
Overflow p and overwrite p->bk with $target_address.
Allocate another chunk with exactly the same size of p , now we can reach the above quoted code
$target_address+8 now is overwritten with the address of bin, most importantly bin->bk is overwritten with $target_address too!!! p is returned to us.
Allocate yet another chunk with exactly the same size of p , now we hit the same code again, but this time we return bin->bk + 8 = $target_address+8 !!
Feel free to overwrite (again) the target address returned by malloc() with your shellcode’s address. Pwned!

It is always amazing to see how attackers put these pieces together and finally form a working exploit!

We have also learned that either we can rely on the existing code in glibc to do the target address overwrite for us (as in “unlink me”), or we can force a subsequent malloc() to return the target address to us to overwrite by ourselves. The former is better because the latter also assumes we can control the write after malloc().

House of Spirit

Forging headers is creative and brilliant, as we see in House of Mind, it extends our mind set of thinking about heap overflow exploits.

It’s time to take it to the next level: we don’t even have to allocate a forged header from scratch, instead we could pass a pointer to an arbitrary memory chunk to free() as glibc still treats whatever we pass as a chunk header anyway! Because free() knows nothing about types, it blindly interprets the pointer as a chunk! Of course, only if we can pass the sanity checks…

Now memory chunk header is merely a virtual concept in our own mind, overwriting its ->fd or ->bk is merely an overwrite at offset 8 or 12. We are now at the zen level of writing heap overflow exploits!!

Think about: what if we think our stack as a memory chunk…

Put it in another way: as long as the return address on the stack falls into the virtual memory chunk header range we could overwrite it after malloc()!

Now, let’s find the code in glibc:

 /*
    If eligible, place chunk on a fastbin so it can be found
    and used quickly in malloc.
  */

  if ((unsigned long)(size) <= (unsigned long)(av->max_fast)

#if TRIM_FASTBINS
      /*
	If TRIM_FASTBINS set, don't place chunks
	bordering top into fastbins
      */
      && (chunk_at_offset(p, size) != av->top)
#endif
      ) {

    if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
	|| __builtin_expect (chunksize (chunk_at_offset (p, size))
			     >= av->system_mem, 0))
      {
	errstr = "free(): invalid next size (fast)";
	goto errout;
      }

    [...]
    fb = &(av->fastbins[fastbin_index(size)]);
    [...]
    p->fd = *fb;
    *fb = p;
  }

Remember fast bins are singly linked and in LIFO order? So if we can fool glibc to put our stack address into this fastbin, the subsequent malloc(), with exactly the same size, will return it back it us! In order to pass the sanity checks, we have to carefully control ->size too.

References:

The art of exploiting heap overflow, part 7

House of unlink

House of Mind

House of Lore

House of Spirit

Written by Cong Wang