首页PWN专栏CTFLinuxlarge bin attack

# 1.Large bin

# 1.

在释放堆块时，想要进入 large bin 的堆块需要大于等于 512 （1024）字节【用户空间需要 大于等于 0x3F0，用户空间小于 0x3F0 进入 small bin 】

而 largebin 还要考虑 fd_nextsiez 和 bk_nextsize ，这两个是因为，在 largebin 中，会按着相同大小的 chunk 归到一起，不同 chunk 组直接的联系就需要 fd_nextsize 和 bk_nextsize 。这里除了每组的第一个 chunk ，其他的 fd_nextsize 和 bk_nextsize 都为 0

fd_nextsize指向了下一组的第一个chunk
bk_nextsize指向了上一组的第一个chunk

# 2. 结构：

large chunk 在 fd 的遍历顺序为从大到小【图中 szie 大小为 1>2>3 ，相同组号的 size 相同（1-1，1-2，1-3 相同）】

【自己画完才发现别人的（自己画的应该有误）】

原地址：https://www.cnblogs.com/hyq2/p/15998570.html

# 3. 插入顺序：

  1. 插入位置按照大小，从大到小排序（小的连接 large bin 块）
  2. 大小相同按照 free 时间排序
  3. 多个大小相同的堆块，只有首堆块的 fd_nextsize 和 bk_nextsize 会指向其他堆块，后面的堆块的 fd_nextsize 和 bk_nextsize 均为 0
  4. size 最大的 chunk 的 bk_nextsize 指向最小的 chunk，size 最小的 chunk 的 fd_nextsize 指向最大的 chunk

# 2. 原理：

# 1. 我自己的理解：

由于在 largebin 中插入 chunk 时会按照大小排序，这就给了我们机会去在比大小时作手脚；

# 在 glibc2.23 中 malloc.c 文件中，比较过程如下：

c
while((unsigned long) size< fwd->size){ // 这里 size 为新插入的，fwd 为已经在 largebin 中的 前一个刚释放  的 chunk
	fwd=fwd->fd_nextsize;
	assert((fwd->size & NON_MAIN_ARENA) == 0);
}

在 largebin 中的 chunk 如果 index相同 的情况下，是按照从小到大的顺序排列的，也就是说在 index 相同的情况下 size 越小的 chunk，越接近 largebin (fd 指向 largebin, 与图对应)，上面的代码是比较 新插入 的 chunk 的 size (size) 是否 小于 上一个刚释放进入 largebin 中的 chunk 的 size (fwd_size) 的过程

当小于成立时，执行 while 中的流程；不成立时，判断：

c
if ( (unsigned long) size == (unsigned long) fwd->size)
//Always insert in the second position
	fwd=fwd->fd;

上面的这个对我们来说无法利用，接下来判断大于时：

c
else
	{
	  victim->fd_nextsize = fwd;                     //victim 是当前新插入的 chunk
	  victim->bk_nextsize = fwd->bk_nextsize; //fwd 是前一个释放的 chunk
	  fwd->bk_nextsize = victim;// 将前一个释放的 bk_nextsize 指向新的 chunk
	  victim->bk_nextsize->fd_nextsize = victim;// 修改新的 chunk 的上一个大小不相同的 chunk 的 fd_nextsize 指向自己
	}
	bck = fwd ->bk; //bck 为上一个释放的 chunk 的 bk

上面这一段我们可以进行利用，当我们对 fwd 的内容进行修改后，改变其 bk 和 bk_nextsize 的指向然后在执行上面这一段代码就会将一些值改变：

1. 选择两个地址为我们想要修改的 值 的地址：

这里选择stack1和stack2

2. 然后修改 fwd 的值 (fwd 为上一个释放的 large_chunk ):

3. 修改完后就会变成如下情况：

4. 再当执行上面判断大小结果为大于的时候的代码时：

c
else
	{
	  victim->fd_nextsize = fwd;                     //victim 是当前新插入的 chunk
	  victim->bk_nextsize = fwd->bk_nextsize; //fwd 是前一个释放的 chunk
	  fwd->bk_nextsize = victim;// 将前一个释放的 bk_nextsize 指向新的 chunk
	  victim->bk_nextsize->fd_nextsize = victim;// 修改新的 chunk 的上一个大小不相同的 chunk 的 fd_nextsize 指向自己
	}
	bck = fwd ->bk; //bck 为上一个释放的 chunk 的 bk

将 victim 插入时发现

c
victim->bk_nextsize->fd_nextsize = victim;
//victim-bk_nextsize 已经指向了 fake_chunk2
// 这里就将 fake_chunk2 的 fd_nextsize 的值变为了 victim 的地址，也就将 stack2 原来的值变为了 victim 的地址

5. 修改 stack1 的值

在执行完对 victim 和 fwd 的 fd_nextsize 和 bk_nextsize 的修改后，会继续对他俩的 fd 和 bk 修改

c
mark_bin(av,victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;  //bck 为 fwd 的 bk 指针

这里会发现：

c
bck->fd = victim;
// 这里 bck = fwd -> bk
// 也就等于 fwd->bk->fd = victim
// 就将 fack_chunk1 的 stack（fd）的值改为了 victim 的地址

最后我们就将

fake_chunk1 的 fd（stack1）的值改为了 victim 的地址
fake_chunk2 的 fd（stack2）的值改为了 victim 的地址

# Large bin 的利用条件：

  • 可以修改一个 large bin chunk 的 data 域（fwd 的 bk 和 bk_nextsize）
  • 从 unsorted bin 中来的 large bin chunk （victim）要紧跟在 被构造 过的 chunk (fwd) 后面【为了判断大小时能够插入到正确的地方】

# 在 malloc.c 中从 unsorted bin 去将 chunk 放入对应的 bin（large bin）的完整代码：

c
/* 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)
                victim->size |= NON_MAIN_ARENA;
              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 ((bck->bk->size & NON_MAIN_ARENA) == 0);
                  if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
                    {
                      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)
                        {
                          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
                        {
                          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;