前言
關鍵的資料結構
關鍵代碼
- void* malloc(size_t)
- void free(void *)
- static int alloc_slot(int, size_t)
- static uint32_t try_avail(struct meta **)
- static struct meta * alloc_group(int, size_t)
- void* enframe(struct meta *, int, size_t, int )
- static struct mapinfo nontrivial_free(struct meta *, int)
2021 Defcon Quals mooosl
2021 強網杯初賽 easyheap

前言

文章更新時間2021.07.23
自defcon21q，那道mooosl起，就有些比賽喜歡折騰這新版的musl libc的堆，在當時打defcon的時候，相關資料幾乎沒有，只能硬磕原始碼，雖然筆者當時是審出來了dequeue()會有類似unlink的任意地址寫的可能，但是此題還是由大佬親自出手把它干掉，事后一直懶沒有復現，結果強網杯21又出一個musl libc的題，此文章開坑，也是督促自己把這一塊原始碼仔細扣一扣，做一個筆記，下文除了原始碼剖析，會以defcon21q和強網杯21的真題為例，

注： musl libc在1.2.x以后有新的堆分配演算法，與glibc有相當大的不同，盡管如此，本文適合有對glibc堆管理的基本認識的讀者，
注：截止目前2021.07，ubuntu20.04默認安裝的musl libc sudo apt install musl，仍然是老的演算法libc1.1.x，老的演算法和glibc相當類似，不多贅述，

目前也有一些資料可以參考，比較粗略，
參考資料：https://www.anquanke.com/post/id/241101

關鍵的資料結構

下圖是一個簡單的整體結構圖，有四個基本的結構體，分別是malloc_context,meta_area,meta,group，與glibc明顯不同的是，分配給用戶的chunk只是group陣列中一個元素，chunk中只有非常少的元資料用作管理，用于管理的資料結構主要在meta里，故musl libc這樣的設計就能一定程度防止溢位和UAF對libc堆管理的直接攻擊，
在這里插入123描述

//in malloc.c
//定義了一個全域變數，用于管理各個chunk
struct malloc_context ctx = { 0 };

//in glue.h
//在gdb中的符號是 __malloc_context
#define ctx __malloc_context

//in meta.h
__attribute__((__visibility__("hidden")))
extern struct malloc_context ctx;

struct malloc_context {
	uint64_t secret; 		//ctx.secret = get_random_secret();
	int init_done;			//if(init_done==0) {init, init_done = 1;}
	unsigned mmap_counter;	//使用mmap分配記憶體的次數
	//---------------------不著急弄明白下面的變數
	struct meta *free_meta_head; 
	struct meta *avail_meta; //meta_area中管理的空閑的meta首地址，用avail_meta_count表示數量
	size_t avail_meta_count, avail_meta_area_count, meta_alloc_shift;
	struct meta_area *meta_area_head, *meta_area_tail;
	unsigned char *avail_meta_areas;
	struct meta *active[48];	//快取可繼續分配的meta，陣列下標與大小有關，(類似tcache/各種 bins)
	size_t usage_by_class[48];	//對應大小的快取的所有meta的group所管理的chunk個數，
	uint8_t unmap_seq[32], bounces[32];
	uint8_t seq;
	uintptr_t brk;				//記錄目前的brk(0)
};

//in meta.h
//單獨申請一個記憶體頁，頁起始地址為一個struct meta_area結構，該記憶體頁剩下部分就是一個個的meta，
//const struct meta_area *area = (void *)((uintptr_t)meta & -4096);
struct meta_area { 
	uint64_t check;			//一個正確的meta_area應有 assert(area->check == ctx.secret);
	struct meta_area *next;	
	
	//管理meta的個數，一般是個固定值
	//ctx.meta_area_tail->nslots = (4096-sizeof(struct meta_area))/sizeof(struct meta);
	int nslots;				
	
	//指向管理的meta的指標，這種寫法算是一個trick，意思是結構體后面的記憶體是meta陣列，
	//長度不定(int nslots;)，使用者需要小心計算使用，
	struct meta slots[];	
};

//in meta.h
//struct meta管理了struct group，group中的storage就是給用戶使用的記憶體，
//group中管理多個"chunk"交由用戶使用，可類比glibc中的chunk，
//meta管理的group中chunk的個數由small_cnt_tab陣列指定，
//meta管理的group中每個chunk的大小固定，由sizeclass指定，
struct meta {
	struct meta *prev, *next;				//雙向鏈表
	//指向管理的group，一定在另一個記憶體頁，有一定程度的隔離，防止溢位攻擊，
	struct group *mem;						
	volatile int avail_mask, freed_mask;	//掩碼的形式，用一個bit表示存在與否，
	uintptr_t last_idx:5;
	uintptr_t freeable:1;
	uintptr_t sizeclass:6;					//管理的group的大小，如果mem是mmap分配，固定為63，
	uintptr_t maplen:8*sizeof(uintptr_t)-12;//如果管理的group是mmap分配的，則為記憶體頁數，否則為0，
};

struct group {
	struct meta *meta;							//指回管理者struct meta
	unsigned char active_idx:5;					//5個bit
	char pad[UNIT - sizeof(struct meta *) - 1];	//手動16位元組對齊，這樣給用戶的storage[]是對齊的
	unsigned char storage[];
};

關鍵代碼

void* malloc(size_t)

//in malloc.c
void *malloc(size_t n)
{
	if (size_overflows(n)) return 0;
	...
	//#define MMAP_THRESHOLD 131052
	if (n >= MMAP_THRESHOLD) {
		//mmap()
		...
		goto success;
	}
	
	sc = size_to_class(n);
	g = ctx.active[sc];
	...
	for (;;) {
		mask = g ? g->avail_mask : 0;
		first = mask&-mask;	//找到最低的為1的bit位
		if (!first) break; //沒有avail的chunk，break
		...
		//將avail這一個bit置位0，要分配出去了
		g->avail_mask = mask-first;
		...
		idx = a_ctz_32(first); //取2的指數，即group中chunk下標
		goto success;
	}

	//如果快取里沒有avail的chunk，進一步申請
	idx = alloc_slot(sc, n);
	...
	//快取可能更新了，重繪g
	g = ctx.active[sc];

	success:
	ctr = ctx.mmap_counter;
	return enframe(g, idx, n, ctr);
}

void free(void *)

//in free.c
void free(void *p)
{
	if (!p) return;
	struct meta *g = get_meta(p);	//p -> struct group -> struct meta,并且檢查
	int idx = get_slot_index(p);	//p 在group中的下標
	size_t stride = get_stride(g);	//chunk的大小

	... // check

	uint32_t self = 1u<<idx, all = (2u<<g->last_idx)-1;
	((unsigned char *)p)[-3] = 255;	//p[-3]與slot_index和reserve有關，現在置0xff
	*(uint16_t *)((char *)p-2) = 0;	//p[-1] = p[-2] = 0;

	...

	// atomic free without locking if this is neither first or last slot
	for (;;) {
		uint32_t freed = g->freed_mask;
		uint32_t avail = g->avail_mask;
		uint32_t mask = freed | avail;
		assert(!(mask&self)); //防止doubel free
	
		//如果是full的meta進行free的話，或者是free了后就empty的話，那就break，進行特殊處理，
		//不然就繼續，然后return，
		if (!freed || mask+self==all) break; 
		if (!MT)
			g->freed_mask = freed+self;

		//無鎖的同步方式，成功則return，失敗continue
		else if (a_cas(&g->freed_mask, freed, freed+self)!=freed) 
			continue;
		return;
	}

	wrlock();
	//特殊處理兩個情況，全慷訓者全滿，需要對meta的double link進行處理，可能還伴隨著meta的申請與釋放，
	struct mapinfo mi = nontrivial_free(g, idx); 
	unlock();
	...
}

static int alloc_slot(int, size_t)

//in malloc.c
//sc = size_to_class(req), req為申請的記憶體大小
static int alloc_slot(int sc, size_t req)
{
	// malloc()中初略發現ctx.active[sc]沒有avail的， 
	//詳細檢查一下快取(可能有freed mask或者meta.next有可分配的)
	uint32_t first = try_avail(&ctx.active[sc]);
	if (first) return a_ctz_32(first); //分配成功 return

	struct meta *g = alloc_group(sc, req); //進一步申請，申請全新的meta與group
	if (!g) return -1;

	g->avail_mask--;
	queue(&ctx.active[sc], g); //加入快取，此時ctx.acive[sc]應該是NULL
	return 0;
}

static uint32_t try_avail(struct meta **)

//in malloc.c
static uint32_t try_avail(struct meta **pm)
{
	struct meta *m = *pm;
	...
	uint32_t mask = m->avail_mask;
	if (!mask) { //沒有avail了
		if (!m->freed_mask) { //且沒有free的chunk，意味著meta的group中所有chunk都分配出去了
			dequeue(pm, m); //meta unlink，UNSAFE UNLINK! 可能的一次任意地址寫
			m = *pm; //此時的m為下一個meta, m不為NULL的話肯定有能分配的
			if (!m) return 0;
		} else {
			m = m->next; //優先找下一個，如果沒下一個就指回自己(回圈鏈表)
			*pm = m;
		}

		mask = m->freed_mask;

		// skip fully-free group unless it's the only one
		...

		// activate more slots in a not-fully-active group
		// if needed, but only as a last resort. prefer using
		// any other group with free slots.
		...

		//把free mask轉換成avail mask，cas同步方式
		mask = activate_group(m);
		assert(mask);
		decay_bounces(m->sizeclass); // ???
	}

	//提取出avail的第一個chunk對應的mask，return
	first = mask&-mask;
	m->avail_mask = mask-first;
	return first;
}

static struct meta * alloc_group(int, size_t)

//in malloc.c
static struct meta *alloc_group(int sc, size_t req)
{
	size_t size = UNIT*size_classes[sc];
	int i = 0, cnt;
	unsigned char *p;

	//分配全新的meta，不再展開源代碼
	//優先查看ctx.free_meta_head的鏈表，如果沒有->
	//再查看ctx管理的meta_area是否有剩的meta，是否有其他的meta_area， 如果都沒有->
	//嘗試使用brk()以記憶體頁為單位分配堆，會中間多分配一個無讀寫權限的記憶體頁，作為guard
	//brk()失敗會嘗試使用mmap()
	struct meta *m = alloc_meta();
	if (!m) return 0;
	size_t usage = ctx.usage_by_class[sc];
	
	//一通操作，給cnt賦了一個合適的值
	...
	cnt = xxx; //cnt是這個meta的group中chunk的數量
	...

	if (size*cnt+UNIT > pagesize/2) {
		...
		//當需求很大時，嘗試mmap()分配
		p = mmap(0, needed, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANON, -1, 0);
		...
	} else {
		int j = size_to_class(UNIT+cnt*size-IB);

		//又一次alloc_slot() 這是一個遞回程序
		//會嘗試向更大的快取要記憶體，更大快取中的chunk會成為這里的group
		int idx = alloc_slot(j, UNIT+cnt*size-IB);
		if (idx < 0) {
			free_meta(m);
			return 0;
		}
		struct meta *g = ctx.active[j];
		p = enframe(g, idx, UNIT*size_classes[j]-IB, ctx.mmap_counter);
		//--------以上代碼實質上走了類似malloc()的程序，向更大快取要了塊chunk

		m->maplen = 0;
		p[-3] = (p[-3]&31) | (6<<5);
		for (int i=0; i<=cnt; i++)
			p[UNIT+i*size-4] = 0;
		active_idx = cnt-1;
	}
	//加入快取的計數
	ctx.usage_by_class[sc] += cnt;
	//給這個全新的meta設定好初始值
	m->avail_mask = (2u<<active_idx)-1;
	m->freed_mask = (2u<<(cnt-1))-1 - m->avail_mask;
	m->mem = (void *)p;
	m->mem->meta = m;
	m->mem->active_idx = active_idx;
	m->last_idx = cnt-1;
	m->freeable = 1;
	m->sizeclass = sc;
	return m;
}

void* enframe(struct meta *, int, size_t, int )

//in malloc.c
//已經確定要分配出去的記憶體位置，enframe()這里做一些檢查和清理作業
static inline void *enframe(struct meta *g, int idx, size_t n, int ctr)
{
	
	size_t stride = get_stride(g); //一個chunk的大小
	size_t slack = (stride-IB-n)/UNIT; //chunk多余的空間
	unsigned char *p = g->mem->storage + stride*idx; //回傳給用戶使用的chunk地址
	unsigned char *end = p+stride-IB;
	// cycle offset within slot to increase interval to address
	// reuse, facilitate trapping double-free.
	//off: 計算出p離第一個chunk的距離，以16byte為單位，
	int off = (p[-3] ? *(uint16_t *)(p-2) + 1 : ctr) & 255;
	... //check
	if (off) {
		// store offset in unused header at offset zero
		// if enframing at non-zero offset.
		*(uint16_t *)(p-2) = off;
		p[-3] = 7<<5;
		p += UNIT*off;
		// for nonzero offset there is no permanent check
		// byte, so make one.
		p[-4] = 0;
	}
	*(uint16_t *)(p-2) = (size_t)(p-g->mem->storage)/UNIT;
	p[-3] = idx;
	set_size(p, end, n);
	return p;
}

static struct mapinfo nontrivial_free(struct meta *, int)

static struct mapinfo nontrivial_free(struct meta *g, int i)
{
	uint32_t self = 1u<<i;
	int sc = g->sizeclass;
	uint32_t mask = g->freed_mask | g->avail_mask;

	if (mask+self == (2u<<g->last_idx)-1 && okay_to_free(g)) { //如果是個全空的meta
		// any multi-slot group is necessarily on an active list
		// here, but single-slot groups might or might not be.
		if (g->next) {
			assert(sc < 48);
			int activate_new = (ctx.active[sc]==g);
			dequeue(&ctx.active[sc], g);
			if (activate_new && ctx.active[sc])
				activate_group(ctx.active[sc]);
		}
		//free group，其中會free meta，不再展開原始碼
		//free meta只是簡單的放入ctx.free_meta_head，不會嘗試合并
		//free group是遞回程序，如果這個group是從更大快取拿的，那么再走一遍nontrivial_free()
		return free_group(g);
	} else if (!mask) { //如果是個全滿的meta
		assert(sc < 48);
		// might still be active if there were no allocations
		// after last available slot was taken.
		if (ctx.active[sc] != g) {
			queue(&ctx.active[sc], g); //取出快取鏈表
		}
	}
	a_or(&g->freed_mask, self);
	return (struct mapinfo){ 0 };
}

2021 Defcon Quals mooosl

to be continued…

2021 強網杯初賽 easyheap