Kernel Pwn Heap Basics

Buddy System

专门用来分配以页为单位的大内存空间, 且大小必须是 2 的整数次幂, $2^{order} \times PGSIZE$. 分配时会找 order 对应的块, 如果没有, 则向上找更大的去分割一半, 直到分割出一块 order 对应大小的 (线段树动态开点!). 释放时, 如果可以, 会将相邻的两个合并成一个大的, 一直往上合并.

TODO, 学到再说, 估计学不到 kernel heap 风水了

Slub

Slub allocator 最初是 slab allocator, 但是效率不高, 现在普遍是用的一个优化版本 slub allocator. slub allocator 是面向数据对象 (结构体) 的堆分配器, 某个或某些对象 (结构体) 的分配使用对应的某个 slub allocator. 最初 slub allocator 会向 buddy system 申请一个或多个连续页面, 这一整个空间称为一个 slub. 一个 slub 会被划分成多个大小相等的 object, 分配给特定的对象 (结构体) 使用.

slub allocator 的实现在 kernel 里是 kmem_cache 这个结构体, 可以简单认为他是 kmem_cache_cpu + kmem_cache_node. kmem_cache 管理多个 slub, 这些 slub 的 object 大小都相同. cat /proc/slabinfo 可以查看这些 slub allocator. slulb allocator 可以通过 kmem_cache_create() 来创建

kmem_cache_cpu

对于一个 kmem_cache, 不同 CPU 上都有一个不同的 kmem_cache_cpu, 彼此独立, 表示当前 CPU 正在使用的一个 slub. 这样同一个 CPU 从自己的 slub 中取 object 不用上锁, 效率高.

kmem_cache_cpu 的一些变量如下:

• freelist: 指向空闲 object 组成的链表头
• page: 指向当前 slub 对应的 page 结构体, page 结构体中有 freelist, 如果这个 page 是 kmem_cache_cpu slub 对应的, 则 freelist 不起作用, 置为 NULL.
• partial: 指向有空闲 object 也有分配了的 object 的 slub (下文称 partial slub) 对应的 page 组成的链表头.

需要注意的是, kmem_cache_cpu 的 partial 链表只会在开启了 SLUB_CPU_PARTIAL 时才有.

kmem_cache_node

不同于 kmem_cache_cpu 只有一个 slub, kmem_cache_node 维护多个 slub, 并分配给 kmem_cache_cpu. kmem_cache_cpu 不需要用的 (比如满了) slub 也会回到 kmem_cache_node 维护. kmem_cache_node 有三个 slub 链表 (由 page 结构体组成的单链表, page 结构体有 next 指针, freelist 链表):

• partial: 这里面的 slub 都是 partial slub
• full: 这里面的 slub 的 object 都被分配出去了 (full slub) (好像要开个 slub debug 才有, 好像也不是单链表?)
• free: 这里面的 slub 的 object 都没有被分配出去 (free slub) (好像没有用到这玩意???)

freelist

freelist 是单向链表, 可以类比 ptmalloc 的 tcache. 空闲的 object 的前 8 字节会指向下一个空闲 object, 组织成链表, 存取都从头节点开始.

partial 链表

每一个 slub 对应一个 page 结构体, 这个结构体中有一个 next 变量, 通过这个变量来组成单向链表. partial 链表中的 slub 是 partial slub, 其余也同理. (page 结构体在哪?)

分配

下文均假设 未开启 slub debug 和 SLUB_CPU_PARTIAL 的情况

1. 若 kmem_cache_cpu 的 freelist 不为空, 则直接从头节点取出一个 object; 否则说明这个 slub 全分配满了, (没用了就丢掉?). 接着
2. 若 kmem_cache_node 的 partial 不为空, 则会从中取一个 slub, 设置为当前的 kmem_cache_cpu (page 结构体和 freelist), 然后取. 否则
3. 说明已有的 slub 都用完了, 向 buddy system 申请新的 slub, 设置为当前的 kmem_cache_cpu, 然后取.

释放

1. 若 object 在 kmem_cache_cpu 的 page 中, 直接释放到 kmem_cache_cpu 的 freelist 中
2. 若 object 对应的 slub 是满的, 那么释放后将把这个 slub 放入 partial 链表
3. 若 object 对应的 slub 在 kmem_cache_node 的 partial 链表中, 则直接释放到对应 page 结构体的 freelist 中
4. 若释放后的 slub 是空的, 则还可能返还给 buddy system. 这里判断的是 node 的 partial 链表中的节点是否大于 kmem_cache 中的一个变量 min_partial

kmem_caches

内核中有预先分配好一些 slub allocator, 名称为 kmalloc-$size, size 是预定的大小, 表示这个 slub 中的 object 的大小. 他们被放在一个 kmem_caches 数组里, 下标从 1 到 13. 这个数组的下标和 slub 对应关系为:

• kmem_caches[0] 没有
• kmem_caches[1]: kmalloc-96
• kmem_caches[2]: kmalloc-192
• kmem_caches[i]: kmalloc-$\mathnormal{2^i}$

Heap exploitation in CTF

由于 slub 的简单机制, 并且很少有安全性检查, 目前 kernel heap 感觉没有 ptmalloc 复杂. 大概就是通过 UAF 或者溢出造成的任意地址分配, 去修改一些处于内核中的, 我们可以分配利用的, 特殊的结构体. 这些结构体通常包含函数指针, 这样就达到了控制程序流的效果.

有关 buddy system 的堆风水也开始出现在比赛上了, 暂时没看.

所以到目前, kernel pwn 学习的很多都是结构体的利用.