Skip to content

Heap Vulnerabilities and Attacks

:material-circle-edit-outline: 约 2089 个字 :fontawesome-solid-code: 31 行代码 :material-clock-time-two-outline: 预计阅读时间 7 分钟

04_Heap

软件安全原理和实践（本）2024-11-05 第 3-5 节

Malloc/free

chunk 是 heap 里的最小内存单位，是 malloc 返回的指针所指向的一块空间

最小内存单位不是指大小最小，而是指其是一个整体进行操作，其大小不是固定的

malloc 输入 0 时如果不报错，也返回一个 chunk

Heap Rules

malloc allocate 的内存空间就在 heap

  • Use-After-Free （UFA）
    • 读写已经 free 后的 malloc 创建的指针
    • Do not read from or write to a pointer returned by malloc after the pointer has been passed to free.
  • Information Leaks or Uninitialized Data，heap
    • 未初始化时可能残存一些数据，可能被 leak
    • Do not use or leak uninitialized information in a heap allocation.
  • Heap Overflow and Out-of-Bounds Read
    • 不要读写越界 end of an allocation 了
    • Do not read or write bytes beyond the end of an allocation.
  • Heap Underflow
    • 不要读写越界 beginning of an allocation 了
    • Do not read or write bytes before the beginning of an allocation.
  • Double Free
    • 重复 free 一个 malloc 创建的指针
    • Do not pass a pointer that originated from malloc to free more than once.
  • Invalid Free
    • 不要把不是 malloc 产生的指针应用在 free
    • Do not pass a pointer that did not originate from malloc to free.
  • NULL Dereference Bugs
    • Do not use a pointer returned by malloc before checking if the function returned NULL.

Heap Memory

Heap memory is allocated by invoking the sbrk system call from the kernel.

Large memory allocations are handled using mmap — an off-heap allocation.

This means that such memory is not managed using the mechanism we will discuss later

img

How Memory Allocation Works

Alignment: 8 bytes on 32-bit systems and 16 bytes on 64-bit systems.

即 heap 指针指向的地址是 8/16 的倍数，chunk 也需要对齐

下图为两个连续的 chunk

img

有两个 metadata，均为 8byte（32 位）

  • 第一个 metadata mchunk_prev_size 是记录上一个 chunk 的大小
    • 如果上一个 chunk 不是空闲的，就可以 merge 进上一个 chunk 的 data ，复用一下

  • 第二个 metadata mchunk_size 有好几个信息，一个是 the size of current chunk, 然后考虑到 Alignment 就多了 3bit 作为 flag,

    • 其中，P(PREV_INUSE) 指示 mem 层面的 prev chunk 是否繁忙（此外还有 linked list 层面上的 prev），P = 0 表示 prev chunk 是 free 的
      • 一个 chunk free 时，如果 P 是 false 的，就可以 merge 上一个 free chunk
    • M (IS_MMAPPED)标记 chunk 从哪分配出来的，具体不用管
    • A (NON_MAIN_ARENA)，0 表示 chunk 来自 main arena，每个线程有自己的区域 arena，就用 A 进行标记

这是我们攻击的入口，溢出覆盖

两个 metadata 后的地址就是 malloc 返回的指针地址，即返回的是 data 空间

chunk 空闲的时候 data 会存 fd 和 bk 两个指针，其将所有 free chunk 链接起来组成一个双向链表

  • fd: Forward pointer to next free chunk in list
    • 后一个
  • bk: Back pointer to previous free chunk in list
    • 前一个

img

Bins

The heap manager needs to keep track of freed chunks so that malloc can reuse them during allocation requests

do this by storing all freed chunks together on some enormous linked list → Slow

To improve performance, the heap manager instead maintains a series of lists called “bins”, which are designed to maximize speed of allocations and frees. - 就是多个不同类别的链表

There are 5 type of bins: 62 small bins, 63 large bins, 1 unsorted bin, 10 fast bins and 64 tcache bins per thread (if tcache is enabled).

The small, large, and unsorted bins are the oldest type of bin

The fast bins and tcache bins are optimizations that layer on top of these.

img

top 指针指向目前已分配的最高的 chunk，即 heap 的顶端/末尾，紧挨着未分配的内存

img

The Free() rule

  1. If the chunk has the M bit set in the metadata, the allocation was allocated off-heap and should be munmap ed.
    • 这种情况 chunk 就不是由 heap 分配的了，我们不需要管
  2. Otherwise, if the chunk before this one is free, the chunk is merged backwards to create a bigger free chunk.
    • 即，当前被 free 的 chunk 和前面那个已经 free 的 chunk merge 在一起
  3. Similarly, if the chunk after this one is free, the chunk is merged forwards to create a bigger free chunk.
    • 后面的也 free 那也 merge
  4. If this potentially-larger chunk borders the “top” of the heap, the whole chunk is absorbed into the end of the heap, rather than stored in a “bin”.
    • 即，merge 后的 chunk 如果挨着 top，那就会直接释放进未分配内存里，不会进入 bins
    • top 指针也会相应地下移
  5. Otherwise, the chunk is marked as free and placed in an appropriate bin.
    • 不挨着 top 就会被标记为 free，并放入合适的 bin 里
    • 注意不是直接释放进未分配内存

Small Bin

There are 62 of them, and each small bin stores chunks that are all the same fixed size

这意味着只能同时存储 62 种大小的 chunk，每个 bin 只能存相同大小的 chunk

small bins is great for small allocations, but we can’t have a bin for every possible chunk size

each small bin stores only one size of chunk，they are automatically ordered, so insertion and removal of entries on these lists is incredibly fast.

img

Large Bin

Each of the 63 “large bins” operates mostly the same way as small bins, but instead of storing chunks with a fixed size, they instead store chunks within a size range.

范围存储，且每次插入 chunk 会同时维护大小顺序，方便取出

insertions onto the bin have to be manually sorted, and allocations from the list require traversing the list.

Unsorted Bin

考虑到有些情景是，刚 free 一个 chunk 马上又用到相同大小的 chunk（局部性原理）

所以，我们就把 free 的 chunk 先放进 Unsorted Bin，下一次 malloc 就先在 Unsorted Bin 里找，找不到再去其它 bin，此外，malloc 会将不匹配的 chunk 移到其它 bin

Fast Bin

考虑到，small chunks 的释放和利用十分频繁

These bins essentially keep recently released small chunks on a “fast-turnaround queue”, intentionally keeping the chunk live and not merging the chunk with its neighbors

so that it can be immediately repurposed if a malloc request for that chunk size comes in very soon after the chunk is freed.

即，小 chunk 假装 free（不清空），存起来，不要 merge，如果有相同大小的请求就能马上提供

行为上就是一个 chunk 的 cache，而且也是相同大小的放一个 bin 里

Like small bins, each fast bin is responsible only for a single fixed chunk size.

There are 10 such fast bins, covering chunks of size 16, 24, 32, 40, 48, 56, 64, 72, 80, and 88 bytes plus chunk metadata.

当然，有些 chunk 长时间没用就会 merge 并丢到其它 bin

Tcache bin

Fastbin Example

我们来看看实际中 chunk 是怎么被分配、再利用的

int main()
{
    char *a, *b, *c;
    char *protect, *recatch;

    a = (char *)malloc(0x8);
    b = (char *)malloc(0x18);
    c = (char *)malloc(0x20);
    protect = malloc(0x100);

    free(a);
    free(b);
    free(c);

    recatch = malloc(0x10);

    free(protect);
    free(recatch);
}

gdb 使用插件 gef，通过 heap chunks 可查看 chunk 情况

gef➤  heap chunks
Chunk(addr=0x55555555b010, size=0x20, flags=PREV_INUSE)
    [0x000055555555b010     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0x55555555b030, size=0x20, flags=PREV_INUSE)
    [0x000055555555b030     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0x55555555b050, size=0x30, flags=PREV_INUSE)
    [0x000055555555b050     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0x55555555b080, size=0x110, flags=PREV_INUSE)
    [0x000055555555b080     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0x55555555b190, size=0x20e80, flags=PREV_INUSE)
    [0x000055555555b190     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0x55555555b190, size=0x20e80, flags=PREV_INUSE)  ←  top chunk

我们发现，怎么 malloc 0x8 和 0x16 都被分配了 0x20 大小的 chunk

首先，chunk 的两个 metadata 分别占 8byte，那就是 0x10

malloc 0x8 时由于要 16 字节对齐，所以给了 0x20

malloc 0x16 时，复用了下一个 chunk 的第一个 metadata，所以也只分配了 0x20 的 chunk

可见一个 chunk 的大小不包括复用的 metadata

最下面的 chunk 被 top 指向

img

free 掉 abc 后，chunk 会被移入 fastbin，相同大小的在一起

gef➤  heap bins
────────────────────────────────────────────────────────────────── 
Fastbins for arena at 0x7ffff7dd0c20 ──────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20]  ←  Chunk(addr=0x55555555b030, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x55555555b010, size=0x20, flags=PREV_INUSE)
Fastbins[idx=1, size=0x30]  ←  Chunk(addr=0x55555555b050, size=0x30, flags=PREV_INUSE)
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
──────────────────────────────────────────────────────────────── 
Unsorted Bin for arena at 0x7ffff7dd0c20 ────────────────────────────────────────────────────────────────
[+] Found 0 chunks in unsorted bin.
───────────────────────────────────────────────────────────────── 
Small Bins for arena at 0x7ffff7dd0c20 ─────────────────────────────────────────────────────────────────
[+] Found 0 chunks in 0 small non-empty bins.
───────────────────────────────────────────────────────────────── 
Large Bins for arena at 0x7ffff7dd0c20 ─────────────────────────────────────────────────────────────────
[+] Found 0 chunks in 0 large non-empty bins.

再执行 recatch = malloc(0x10); 就会从 fastbin 取 chunk

gef➤  heap bins
──────────────────────────────────────────────────────────────────────── ────────────────────────────────────────────────────────────────── 
Fastbins for arena at 0x7ffff7dd0c20 ──────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20]  ←  Chunk(addr=0x55555555b010, size=0x20, flags=PREV_INUSE)
Fastbins[idx=1, size=0x30]  ←  Chunk(addr=0x55555555b050, size=0x30, flags=PREV_INUSE)
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00

UAF

例如下面这个程序，a 先申请又释放，但是 b 又马上申请，这样 a 和 b 指针指向的是同一个地址的 chunk，这意味着你可以用 a 访问 b 指向的地址并进行修改

int main()
{
    char *a, *b, *c;
    int BUFSIZE = 0x10;

    a = (char *)malloc(BUFSIZE);
    free(a);
    b = (char *)malloc(BUFSIZE);
}

所以我们要将 free 后的指针指向 NULL

还有一个例子

for (struct node *p = head; p != NULL; p = p->next) {
    free(p);
}

这里循环先 free 了 p 又用了 p-> next，也是 UAF

还有一个例子

复杂的例子

Advanced One: Off-by-Null

Basic idea is to change the P bit from 1 to 0, this will cause the previous block as free space

the free of the next chunk will merge the free block together (or unlink one free block)

？？？？？？为什么会 unlink 中间那个，为什么要合并中间隔了一个 chunk 的两个 chunk

[!NOTE] merge 的过程 img

How to Exploit?

What if we can control p's content, including FD, BK

FD→bk = BK mean *(FD + 24) = BK

？？？？？？？？？？？？？

An Example

04_Heap