Heap Exploitation系列翻译-06 Core functions

| categories translations  | tags CTF  pwn  heap 

Core functions

本文是对Dhaval Kapil的Heap Exploitation系列教程的译文

void * _int_malloc (mstate av, size_t bytes)

  1. Updates bytes to take care of alignments, etc.
  2. 检查av是否为NULL
  3. 缺少可用arena的情况(av = NULL),会使用mmap方式调用sysmalloc来获得堆块,如果成功,则调用alloc_perturb返回堆块指针
    • 如果堆块大小在fastbins范围内
      1. 根据申请的堆块大小在fastbins数组里获取一个指向合适bin的索引
      2. 移除那个bin中的第一个堆块并用victim指针指向它
      3. 如果victim = NULL,则退出继续到下一个情形(smallbin)
      4. 如果victim != NULL,则检查堆块大小,则检查堆块大小以确保它确实是属于要求的那个bin的,如果不符合,则抛出error(“malloc(): memory corruption (fast)”)
      5. 继续调用alloc_perturb并返回指针
    • 如果堆块大小在smallbin的范围内
      1. 根据申请的堆块大小,在smallbins数组中获取一个指向合适bin的索引
      2. 如果该bin中没有堆块,那么就退出继续到下一情形。这是通过比较指针binbin->bk来检查的
      3. 创建victim指针使等于bin->bk(bin中的最后一个堆块).如果它为NULL(在初始化过程中会发生这种情况), 就调用malloc_consolidate并跳过bins是否相同的检查
      4. 否则,当victim != NULL, 检查victim->bk->fdvictim是否相等,如果不等,则抛出error(“malloc(): smallbin double linked list corrupted”)
      5. victim设置下一个堆块(内存意义上的,并非指双向链表中)的PREV_INUSE位为1
      6. 从bin中移除该堆块
      7. 根据av为该堆块设置相应的arena位
      8. 调用alloc_perturb并返回堆块指针
    • 如果大小不在smallbin范围内
      1. 根据申请的堆块大小,在largebin数组中获取一个指向合适bin的索引
      2. av是否有fastchunks. 这是通过av->flags中的FASTCHUNKS_BIT位来进行检查的, 如果确实有fastchunks,那么就调用av中的malloc_consolidate
  4. 如果到目前为止依旧没有任何指针返回, 那么只会是以下几种情形之一:
  5. 大小在fastbin范围内,但是没有fastchunk是可用的
  6. 大小在smallbin范围内,但是没有smallchunk是可用的(在初始化过程中调用malloc_consolidate)
  7. 大小在largebin范围内

  8. 接下来, 检查unsorted chunks, 遍历bin中的各个堆块
  9. victim指针指向当前处理的堆块
  10. 检查victim的堆块大小是否在最小范围(2*SIZE_SZ)和最大范围(av->system_mem)之间, 不在范围内的话则抛出error(“malloc(): memory corruption”)
  11. 如果(申请堆块的大小在smallbin范围)并且(victim是last remainder chunl)并且同时(它是unsorted bin中唯一的堆块)同时(该堆块的大小>=所需求的大小) 将该堆块分成两部分
    • 第一个堆块大小为所申请的大小并将其返回
    • 剩下的那块会成为新的last remainder chunk, 并插回到unsorted bin中:
      1. 为该堆块设置好对应的chunl_sizechunk_prev_size
      2. 在调用alloc_perturb后返回第一个堆块
  12. 如果上述情形都不满足, 进行如下控制. 在unsorted bin中移除victim, 如果victim的大小刚好满足所申请的堆块大小, 那么就在调用alloc_perturb后返回该堆块的指针
  13. 如果victim的大小在smallbin范围内, 那么就将该堆块添加到对应的smallbin的首部
  14. 不在smallbin范围内的话, 就将其插入到合适的largebin中并维持原有的排序顺序 * 首先检查最后一个堆块(也是最小的). 如果victim小过这最后一个堆块, 那么就将其插入到最后 * 不然, 循环遍历寻找一个大小恰好大于等于victim大小的堆块, 并将victim插入到这个堆块后面. 如果恰好相等, 则将其插入到第二个的位置上
  15. 重复这整个步骤最多MAX_ITERS(10000)次直到所有的堆块都插入到unsorted bin中合适的位置

  16. 在检查完unsorted chunks, 检查需求的堆块大小是否不在smallbin范围内, 如果不在的话, 那么就将检查largebins
  17. 根据申请的大小, 从largebin数组中获取一个合适的bin的索引
  18. 如果最大的堆块大小(bin中的第一个堆块)大于我们所申请的大小 1. 从链表尾部开始迭代, 直到找到一个大于等于申请大小的最小堆块victim 2. 调用unlink移除bin中的victim堆块 3. 为victim堆块计算remainder_size(remainder_size大小为victim的堆块大小减去所申请的堆块大小) 4.如果remainder_size >= MINSIZE(包括头部在内的最小堆块大小), 那么就切分该该堆块成两部分. 否则, 返回整个victim. 将remainder chunk插入到unsorted bin中(插到尾部). 在unsorted bin中会检查unsorted_chunks(av)->fd->bk是否等于unsorted_chunks(av). 不等的话抛出error(“malloc(): corrupted unsorted chunks”) 5. 在调用alloc_perturb后返回victim堆块

  19. 到目前为止, 我们以及检查了unsorted bin以及各个fastbin, smallbin以及largebin. 要注意的是我们会根据所申请的堆块大小来检查每个bin(fast或small), 重复以下步骤直到所有的bin都被检查完.
  20. bin数组的索引通过自增来检查下一个bin
  21. 使用av->binmap来跳过那些空的bin
  22. victim指向当前bin的尾部
  23. 使用binmap确保跳过的bin(在上述第二个步骤中)确实是空的. 然而这还不能确保所有的空白bin会被跳过, 还需要检查victim是否为空. 如果为空, 那么再次跳过该bin并重复以上步骤(或继续本次循环)直到到达一个非空的bin
  24. 切分堆块(victim指向非空bin中的最后一个堆块)成两部分, 将remainder chunk插入到unsorted bin中(插入到尾部). 在unsorted bin中胡检查unsorted_chunks(av)->fd->bk是否等于unsorted_chunks(av), 如果不等,则抛出一个error(“malloc(): corrupted unsorted chunks 2”)
  25. 在调用alloc_perturb后返回victim堆块

  26. 如果还是没能找到非空bin, 那么会使用top chunk来满足需求
  27. victim指向av->top
  28. 如果size of top chunk >= requested size + MINSIZE, 那么就将其分成两部分, 在这里, 剩下的remainder chun会变成新的top chunk, 另外一个chunk则会在调用alloc_perturb后返回给用户
  29. 观察av是否有fastchunks, 这是通过av->flags中的FASTCHUNKS_BIT来检查的. 如果有fastchunks, 就对av调用malloc_consolidate并返回到步骤6(我们检查unsorted bin的地方)
  30. 如果av没有fastchunks, 那么就调用sysmalloc并返回调用alloc_perturb获得的指针

__libc_malloc (size_t bytes)

  1. 调用arena_get来获得一个mstate指针
  2. 使用指向arena的指针及arena的大小作参调用_init_malloc
  3. 解锁arena
  4. 在返回堆块指针之前, 以下所列之一应该为真
    • 返回指针是NULL
    • chunk是通过mmap映射得到的
    • arena的chunk会和1中找到的那个相同

_int_free (mstate av, mchunkptr p, int have_lock)

  1. 检查p在内存上是否在p+chunksize(p)之前(避免被覆写), 不然会抛出error(“free(): invalid pointer”)
  2. 检查堆块的大小至少为MINSIZE或者是MALLOC_ALIGNMENT的倍数, 若不满足则抛出error(“free(): invalid size”)
  3. 如果堆块大小在fastbin范围内:
    1. 检查下一个堆块的大小是否在最小值和最大值之间(av->system_mem), 不然抛出error(free(): invalid next size (fast)”)
    2. 对chunk调用free_perturb
    3. av设置FASTCHUNKS_BIT位为1
    4. 根据堆块大小获取fastbin数组中的索引
    5. 检查确保bin的顶部不是我们将要添加的那个堆块, 否则抛出error(“double free or corruption (fasttop)”)
    6. 检查确保在顶部的fastbin堆块的大小跟我们所要添加的堆块大小相同, 否则抛出error(“invalid fastbin entry (free)”)
    7. 将该堆块插入到fastbin链表顶部并返回
  4. 如果堆块不是通过mmap映射得到的
    1. 检查堆块是否是top chunk, 如果是则抛出error(“double free or corruption (top)”)
    2. 检查next chunk是否是在arena的范围内, 如果不在的话, 抛出error(“double free or corruption (out)”)
    3. 检查next chunk(内存意义上的)的PREV_INUSE位是否设置为1, 如果没有, 则抛出error(“double free or corruption (!prev)”)
    4. 检查next chunk的大小是否在最小值和最大值之间(av->system_mem), 如果不在, 则抛出error(“free(): invalid next size (normal)”)
    5. 对该堆块调用free_perturb
    6. 如果前一个堆块(内存意义上的)处于空闲状态, 则对这个前一个堆块调用unlink 7.如果next chunk(内存意义上的)不是top chunk
      1. 如果next chunk处于空闲状态, 则对这个next chunk调用unlink
      2. 合并前后堆块(内存意义上的), 如果都是空闲状态, 则将其加入到unsorted bin的首部. 在插入之前, 会检查unsorted_chunks(av)->fd->bk是否等于unsorted_chunks(av), 如果不等,则抛出error(“free(): corrupted unsorted chunks”)
    7. 如果next chunk(内存意义上的)是一个top chunk, 那么将该堆块适当地合并到top chunk去
  5. 如果堆块是通过mmap映射得到, 则调用munmap_chunk

__libc_free (void *mem)

  1. 如果mem为NULL则返回
  2. 如果相应的堆块通过mmap映射, 则会在需要调整动态brk/mmap阈的时候调用munmap_chunk
  3. 为相应堆块获取arena指针
  4. 调用 _int_free.

Previous     Next