large bin attack – glibc 2.23
在malloc 的源码里面，把非small bin的部分定义为large bin,在64位的系统里面大于MIN_LARGE_SIZE为640x10即0x400的chunk为largebin，而32位系统中大于MIN_LARGE_SIZE为640x8即0x200的chunk位largebin。
存储方式
large bin采用等差数列的方式进行，即是一个idx对应一组大小不同的chunk，定义：
#define largebin_index_64(sz) \
(((((unsigned long) (sz)) >> 6) <= 48) ? 48 + (((unsigned long) (sz)) >> 6) :\
((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
126)
在同样的idx的bin里面chunk排序方式：
•堆块从大到小排序。
•对于相同大小的堆块，最先释放的堆块会成为堆头，其fd_nextsize与bk_nextsize会被赋值，其余的堆块释放后都会插入到该堆头结点的下一个结点，通过fd与bk链接，形成了先释放的在链表后面的排序方式，且其fd_nextsize与bk_nextsize都为0。
•不同大小的堆块通过堆头串联，即堆头中fd_nextsize指向比它小的堆块的堆头，bk_nextsize指向比它大的堆块的堆头，从而形成了第一点中的从大到小排序堆块的方式。同时最大的堆块的堆头的bk_nextsize指向最小的堆块的堆头，最小堆块的堆头的fd_nextsize指向最大堆块的堆头，以此形成循环双链表
从unsorted bin 移入large bin
源码：
/* place chunk in bin */
if (in_smallbin_range (size))
{
... // chunk为smallbin，放入到smallbin中
}
else
{
victim_index = largebin_index (size);//第一步，获取当前要插入的chunk对应的index
bck = bin_at (av, victim_index); //当前index中最小的chunk
fwd = bck->fd; //当前index中最大的chunk
/* maintain large bins in sorted order */
if (fwd != bck)
{ // 该chunk对应的largebin index中不为空
/* Or with inuse bit to speed comparisons */
size |= PREV_INUSE;
/* if smaller than smallest, bypass loop below */
assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) //第三步，如果要插入的chunk的size小于当前index中最小chunk的大小，则直接插入到最后面。
{
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 ((fwd->size & NON_MAIN_ARENA) == 0);
while ((unsigned long) size < fwd->size) //第四步，如果插入的chunk不为最小，则通过`fd_nextsize`从大到小遍历chunk，找到小于等于要插入chunk的位置
{
fwd = fwd->fd_nextsize;
assert ((fwd->size & NON_MAIN_ARENA) == 0);
}
if ((unsigned long) size == (unsigned long) fwd->size)
/* Always insert in the second position. */
fwd = fwd->fd; //第五步，如果存在堆头，则插入到堆头的下一个节点
else
{ //第六步，否则这个chunk将会成为堆头，`bk_nextsize`和`fd_nextsize`将被置位
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
}
}
else //第二步，chunk对应的largebin index中为空
victim->fd_nextsize = victim->bk_nextsize = victim;
}
mark_bin (av, victim_index);
//设置fd与bk完成插入
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
...
}
- 找到当前要插入的chunk对应的largebin的index，并定位该index中的最小的chunkbck和最大的chunkfwd。
- 如果fwd等于bck，表明当前链表为空，则直接将该chunk插入，并设置该chunk为该大小堆块的堆头，将bk_nextsize和fd_nextsize赋值为它本身。
- 如果fwd不等于bck，表明当前链表已经存在chunk，要做的就是找到当前chunk对应的位置将其插入。首先判断其大小是否小于最小chunk的size，(size) < (bck->bk->size)，如果小于则说明该chunk为当前链表中最小的chunk，即插入位置在链表末尾，无需遍历链表，直接插入到链表的末尾，且该chunk没有对应的堆头，设置该chunk为相应堆大小堆的堆头，将bk_nextsize指向比它大的堆头，fd_nextsize指向双链表的第一个节点即最大的堆头。
- 如果当前chunk的size不是最小的chunk，则从双链表的第一个节点即最大的chunk的堆头开始遍历，通过fd_nextsize进行遍历，由于fd_nextsize指向的是比当前堆头小的堆头，因此可以加快遍历速度。直到找到小于等于要插入的chunk的size。
- 如果找到的chunk的size等于要插入chunk的size，则说明当前要插入的chunk的size已经存在堆头，那么只需将该chunk插入到堆头的下一个节点。
- 如果找到的chunk的size小于当前要插入chunk的size，则说明当前插入的chunk不存在堆头，因此该chunk会成为堆头插入到该位置，设置fd_nextsize与bk_nextsize。
unlink
源码：
if (!in_smallbin_range (nb))
{
bin = bin_at (av, idx);
/* skip scan if empty or largest chunk is too small */
if ((victim = first (bin)) != bin &&
(unsigned long) (victim->size) >= (unsigned long) (nb))//先判断申请的size是否小于large bin里面最大的chunk的size
{
victim = victim->bk_nextsize;
while (((unsigned long) (size = chunksize (victim)) <
(unsigned long) (nb))) //从最小chunk开始遍历找出合适的chunk
victim = victim->bk_nextsize;
/* Avoid removing the first entry for a size so that the skip
list does not have to be rerouted. */
if (victim != last (bin) && victim->size == victim->fd->size) //合适的size可能含有多个chunk的，如果是的话不能拿出头部哪个。
victim = victim->fd;
remainder_size = size - nb; //分割large chunk
unlink (av, victim, bck, fwd); 进行unlink
/* Exhaust */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
/* Split */
else
{
remainder = chunk_at_offset (victim, nb);
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
bck = unsorted_chunks (av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "malloc(): corrupted unsorted chunks";
goto errout;
}
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
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;
}
}
- 先判断申请的size是否小于large bin里面最大的chunk的size
- 从最小chunk开始遍历找出合适的chunk
- 分割large chunk
- 进入unlink,跟small bin的unlink有相同之处，不过四个参数的最后两个传入的是fd_nextsize和bk_nextsize
- 判断剩余空间是否小于MINSIZE，如果小于直接返回给用户。
- 否则将剩余的空间构成新的chunk放入到unsorted bin中。
large bin 操作总结
至此largebin链表的形成以及申请largebin都已经阐述清楚。再小结下，对于largebin的链表的插入，双链表是从大到小的chunk排序，相同大小的chunk会有一个堆头，只有堆头的fd_nextsize与bk_nextsize会被赋值，其余堆块的该字段为0。插入的遍历是通过fd_nextsize从大到小进行的，如果该插入的chunk存在对应堆头，则插入到该堆头的下一个结点，否则的话该chunk会成为堆头插入到链表中。
对于largebin的申请，通过判断双链表的第一个结点（最大结点）的大小来判断是否存在满足的堆块，如果有则从小到大通过bk_nextsize反向遍历双链表，找到最小的满足申请需求的堆块，如果该堆头下一个结点的大小也满足则将该结点作为目标分配给用户，以此减少链表的fd_nextsize与bk_nextsize操作，提高效率。对于双链表的unlink，需要注意的就是fd_nextsize与bk_nextsize检查，特别需要注意的是当结点是堆头的下一个结点时，它的fd_nextsize与bk_nextsize为0，此时unlink操作与smallbin的unlink操作一致，没有fd_nextsize与bk_nextsize的检查与操作。
large bin attack 方式
• 在申请largebin的过程中，伪造largebin的bk_nextsize，实现非预期内存申请。
• 在largebin插入的过程中，伪造largebin的bk_nextsize以及bk，实现任意地址写堆地址。
伪造伪造largebin的bk_nextsize
问题出现在通过bk_nextsize反向遍历双链表的过程，如果能够伪造某个堆头结点中的bk_nextsize，将其指向非预期的内存地址，构造好数据使得非预期内存地址在通过unlink的检查之后，会将该空间返回给用户，最终使得可以申请出非预期的内存。最常见的就是用它来构造overlap chunk。
至于绕过unlink的检查，最好的方式就是伪造的内存空间将fd与bk按照smallbinunlink的利用方式设置，而将bk_nextsize和fd_nextsize设置成0，这样就不会对这两个字段进行操作了。
伪造largebin的bk_nextsize以及bk
...//将largebin从unsorted bin中取下
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);
...
//否则这个chunk将会成为堆头，`bk_nextsize`和`fd_nextsize`将被置位
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize; //由于fwd->bk_nextsize可控，因此victim->bk_nextsize可控
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim; //victim->bk_nextsize可控，因此实现了往任意地址写victim的能力
}
bck = fwd->bk; //由于fwd->bk可控，因此bck可控
...
mark_bin (av, victim_index);
//设置fd与bk完成插入
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim; //bck可控，因此实现了往任意地址写victim的能力
...
}
这样利用伪造在largebin中的bk_nextsize与bk，我们获得了两次任意地址写堆地址的能力。我们可以写global_max_fast，这样就可以扩大fast bin的范围进而实现fast bin attack.
house of storm
利用伪造在largebin中的bk_nextsize与bk，我们获得了两次任意地址写堆地址的能力。除了覆盖global_max_fast之外，另一种用法则是house-of-storm，与unsorted bin attack的结合可以使得该利用方法变成任意可以内存申请的攻击方式。
这个就是利用unsorted bin attack把对应链表的bk改成堆地址，large bin attack 实现堆块伪造，进而在下一次unsorted bin 分配的时候可以实现任意堆块的分配。
举个demo
A=malloc(0x400-0x10) //A
malloc(0x10) //gap
B=malloc(0x420-0x10) //B
malloc(0x10) //gap
free(A) //free A into unsorted bin.
malloc(0x500) //sort A into largebin.
free(B) //free B into unsorted bin.
A+0x18=evil_addr-0x20+8-5 //A->bk_nextsize=evil_addr-0x20+8-5.
A+0x8=evil_addr+8 //A->bk=evil_addr+8.
B+0x8=evil_addr //B->bk=evil_addr
malloc(0x48) //evil_addr are malloced out here.
large bin 伪造的堆块chunk
heap &__free_hook
$1={
prev_size = xxxxxxxxxx,
size = 0x56,
fd = 0x0,
bk = 0x56xxxxxxxxxxxx,
fd_nextsize = 0,
bk_nextsize = 0
}
