Memory Allocator와 UAF, DF
2024년 7월 14일
Memory Allocator #
관련 자료: 신비한 malloc 사전
운영체제는 한정된 메모리를 각 프로세스에 효율적으로 배분해야 한다. 모든 프로세스는 실행중에 메모리를 동적으로 할당하고 해제하기도 하는데, 최대한 낭비없이 동작하도록 Memory Allocator가 관리하게 된다.
운영체제에서는 기본 메모리 할당기로 이미 구현되어 있지만, 일부 앱에서는 앱의 메모리 사용에대한 특성에 따라 직접 구현한 Memory Allocator를 사용하기도 한다.
- 리눅스: 기본 할당기로 사용되는 pmalloc
- 크롬 브라우저: 앱에서 구현된 tcmalloc → PartitionAlloc
- 안드로이드: 기본 할당기로 사용되는 jemalloc(~AOS 9) → tcmalloc 변형(AOS 10) → scudo(AOS 11~)
- 파이어폭스: 앱에서 구현된 jemalloc
ptmalloc2 (pthread malloc 2) #
dlmalloc을 개선한 버전이며, 리눅스의 GLIBC에 구현되어 있다.
메모리 낭비 방지 #
해제된 메모리중에 재사용할 수 있는 공간이 있는지 탐색하고 동일하게 요청된 공간을 재할당 해주거나 작은 크기의 할당 요청이 발생했을 때 해제된 아주큰 공간을 나눠주기도 한다.
빠른 메모리 재사용 #
메모리를 해제할때 크기에 따라 여러개로 나눠진 tcache나 bin 이라는 연결리스트에 해제된 공간의 정보를 저장해둔다.
단편화 방지 #
ptmalloc은 64bit기준 16byte 블록 단위로 할당해주기 때문에 재할당한 메모리 공간에서 빈공간이 많이 남는 내부 단편화가 발생할 수 있다.
하지만 역설적으로 애매한 공간이 사라져서 할당받지 못한 메모리 공간 사이의 공간이 많아지는 외부 단편화를 줄일 수 있고, 특정 조건을 만족할 때 연속된 작은 공간들을 병합해서 재사용률을 높인다.
ptmalloc2의 객체 #
청크 #
ptmalloc이 할당한 메모리 공간을 의미하며, 헤더(16byte)와 데이터(요청한만큼) 영역으로 구성된다.
헤더는 청크 관리에 필요한 정보를 담고있으며, free하게되면 추가로 연결리스트의 다음 청크를 가리키는 fd와 이전청크를 가리키는 bk가 data영역에 추가된다.
bin #
재사용을 위해 해제된 청크들이 저장된다. 총 128개의 bin이 있으며, 62개는 smallbin, 64개는 largebin, 1개는unsortedbin, 처음[0]과 끝[127] 2개는 사용되지 않는다.
하나의 smallbin에는 같은 크기의 청크들만 보관되며 smallbin[0]에는 32byte 크기의 청크가, smallbin[61]에는 1008(32+idx*16)byte크기의 청크가 저장된다.
가장먼저 해제된 청크가 재할당에 먼저 사용되는 FIFO방식인데, LIFO 방식은 속도는 빠르지만 파편화가 심하고, address-ordered방식은 그 반대이며, FIFO는 중간에 있다.
bin은 이중연결리스트라 해제된 청크가 bin에 연결될때, bin에서 재할당될때 기존의 연결을 끊어야 하는데 이 작업을 unlink라고 한다.
인접한 청크가 free되는 경우 상황에서는 bin의 청크들이 병합되어 병합된 크기의 smallbin으로 이동되는데 이것을 consolidation이라고 한다.
fastbin #
작은 크기(32~176byte)의 청크는 자주 재할당되는데, 빠르게 재할당하기 위해 별도로 fastbin에 저장한다. 리눅스에서는 128byte까지만 fastbin을 사용한다.
fastbin은 단일 연결리스트이기 때문에 unlink과정이 없으며, 속도가 빠르지만 파편화가 심한 LIFO 방식을 사용해야 한다.
단일 연결리스트는 가장 늦게 해제된 청크가 맨앞에 연결되고, 재할당 시 맨앞의 청크를 가져와야 순회할 필요가 없기 때문에 LIFO 방식으로 사용된다.
인접한 청크가 해제된다 하더라도 메모리를 병합하지 않는다.
largebin #
정확한 크기만 저장하는 smallbin, fastbin과 달리 일정 크기 범위에 해당하는 모든 청크를 저장한다. largebin에서 재할당이 일어날 때 ptmalloc은 가장 가까운 청크(best-fit)를 꺼내 재할당하며, 빠르게 할당하기 위해 내림차순으로 정렬해둔다.
정렬을 위해서 unlink 오버헤드도 추가되며, 연속적인 위치의 메모리는 병합되는 과정도 동일하다.
unsortedbin #
분류되지 않은 청크를 보관하는 bin인데, 메모리에서 처음 해제될 때 fastbin에 들어가지 않으면 모두 unsortedbin에 저장된다.
smallbin 크기에 해당하는 청크를 요청하면 fastbin, smallbin을 확인하고 unsortedbin을 확인하게 되는데, largebin 크기에 해당하는 청크를 요청하면 unsortedbin을 확인하고 largebin을 확인하는 순서로 진행된다.
할당 후 남는 메모리나 주기적으로 정리되는 타이밍에 unsortedbin에 있는 청크가 smallbin이나 largebin으로 이동된다.
arena #
위의 bin들의 정보를 모두 담고있는 공유 객체이다. 멀티스레드에서 arena에 접근할때는 ptmalloc이 락을 걸고 사용하는데 병목현상이 발생할 수 있기 때문에 락이 걸려서 대기하는 경우 새로운 arena를 최대 64개까지 생성해서 병목현상을 최대한 피하게된다.
tcache #
GLIBC 2.26에서 도입된 thread local cache를 의미하며 각 스레드에 독립적으로 할당되는 캐시 저장소이다.
LIFO 방식의 단일 연결리스트로, 64개의 인덱스(32+63*16byte = 1040byte)를 가지고있다. 한 인덱스에는 같은 크기의 청크로 7개까지 저장되며, 메모리 할당시 가장 먼저 참조하기 때문에 arena의 병목현상을 피할 수 있다.
메모리 할당기는 tcache/bin에서 가져오는 경우를 제외하고는 동일한 메모리 주소를 재할당하지 않기 위해 아레나에 락을 걸고 할당하기 때문에 멀티스레드 환경에서 tcache와 새로 할당받은 메모리 주소가 겹치지 않는다.
요약하면 한번 할당받고 나면 재할당되지 않는 상황에서 스레드 별로 tcache를 통해 관리된다.
인접한 청크가 해제된다 하더라도 메모리를 병합하지 않는다.
Use After Free #
메모리를 해제 후 포인터변수를 null로 초기화 하지 않아서 남아있던 주소값으로 특정 영역을 접근할 수도 있고,
사용한 메모리를 해제하며 내부 데이터를 정리하지 않고, 다음 청크에 재할당 됐을 때 이전에 사용했던 기록들이 남아있는 취약점이다.
이전에 사용했던 메모리 내부의 값만 읽어올 수 있는 취약점이 아니라 미리 같은 크기의 객체를 생성 후 데이터를 넣어두고 free를 하게되면 새로운 다른 객체가 잘못된 로직을 실행시키도록 유도할 수 있다.
공격에 사용될 수 있는 정보 #
- tcache에 포함되는 최대 크기는 1040byte이며, 그 이상의 경우 처음엔 unsorted bin에 연결된다.
- 모든 bin들의 헤더는 main_arena에 있으며, bin에 연결된 청크 리스트의 맨 처음 fd와 마지막 bk는 main_arena영역의 bin헤더를 가리킨다.
- tcache에 포함되지 않는 큰메모리(1041 이상)를 할당 후 해제하고, fd, bk 영역을 확인한다.
- main_arena는 심볼 제거된 전역변수로 존재해서 라이브러리 내 오프셋은 같기 때문에 LD_PRELOAD로 라이브러리 로드 후 오프셋을 구하고 런타임에 구한 주소를 빼면 libc의 base 주소를 얻을 수 있다.
- uaf_overwrite 문제에서는 libc의 원 가젯을 사용해서 문제를 해결한다.
Double Free #
메모리를 해제하면 청크가 free list(tcache, bins)으로 이동되는데 두번 free하는 경우 청크를 중복해서 free list에 담을 수 있게 된다.
중복된 청크를 다시 할당하면, 같은 주소가 하나는 힙영역에 할당되어 있고, 하나는 free list에 포함되는데, 힙에 할당받은 메모리의 data를 변경하면 free list의 fd, bk를 조작해서 원하는 메모리 주소를 free list에 포함시킬 수 있게 된다.
원하는 메모리 주소가 free list에 포함되면, 그 주소를 재할당 받아서 다른 특별한 취약점이 없더라도 값을 읽거나, 쓰는것이 모두 가능해진다.
tcache 보호기법 분석 #
요즘은 더블프리를 감지해서 abort로 종료되는데, tcache에 도입된 보호 기법을 분석하기 위해 malloc에서 코드가 변한 부분을 살펴보자
tcache_entry이기 때문에 단일 링크드리스트로 구현되어 있고, next 포인터는 다음 청크를 가리킨다. key가 추가된 것을 확인할 수 있는데, 이걸 이용해서 double free를 체크한다.
key는 tcache_perthread_struct 구조체이며, 이 구조체는 전체 tcache list (64개의 인덱스)를 관리하는 구조체이다.
1 typedef struct tcache_entry
2 {
3 struct tcache_entry *next;
4+ /* This field exists to detect double frees. */
5+ struct tcache_perthread_struct *key;
6 } tcache_entry;
7
8// key의 타입
9typedef struct tcache_perthread_struct
10{
11 char counts[TCACHE_MAX_BINS];
12 tcache_entry *entries[TCACHE_MAX_BINS];
13} tcache_perthread_struct;
이 key값은 tcache에 청크를 넣을때 tcache_put 에서 tcache 구조체가 저장되고,
재 할당을 위해 tcache에서 청크를 가져올때 tcache_get 에서 NULL로 초기화된다.
1@@ -2927,6 +2929,11 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
2+ e->key = tcache;
3
4@@ -2942,6 +2949,7 @@ tcache_get (size_t tc_idx)
5+ e->key = NULL;
free를 호출하면 _int_free가 호출되면서 e->key가 tcache인지 확인하고, 같으면 재할당 되지 않은 메모리로 판단하고 프로세스를 abort 시킨다.
1@@ -4165,13 +4173,33 @@ _int_free (mstate av, mchunkptr p, int have_lock)
2+ /* This test succeeds on double free. However, we don't 100%
3+ trust it (it also matches random payload data at a 1 in
4+ 2^<size_t> chance), so verify it's not an unlikely
5+ coincidence before aborting. */
6+ if (__glibc_unlikely (e->key == tcache))
7+ {
8+ tcache_entry *tmp;
9+ LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
10+ for (tmp = tcache->entries[tc_idx]; tmp; tmp = tmp->next)
11+ if (tmp == e)
12+ malloc_printerr ("free(): double free detected in tcache 2");
13+ }
14+
15+ if (tcache->counts[tc_idx] < mp_.tcache_count)
16+ {
17+ tcache_put (p, tc_idx);
18+ return;
19+ }
Tcache Duplication #
tcache에 적용된 보호기법은 key 값이 조금이라도 변경되면 더블프리가 감지되지 않기 때문에 free 이후 청크에서 key가 가리키는 위치를 조금 수정하면 double free가 된다.
1#include <stdio.h>
2#include <stdlib.h>
3int main() {
4 void *chunk = malloc(0x20);
5 printf("Chunk to be double-freed: %p\n", chunk);
6 free(chunk);
7 *(char *)(chunk + 8) = 0xff; // manipulate chunk->key
8 free(chunk); // free chunk in twice
9 printf("First allocation: %p\n", malloc(0x20));
10 printf("Second allocation: %p\n", malloc(0x20));
11 return 0;
12}
더블프리 후 연속으로 할당했을때 같은 주소의 청크가 할당되어 반환되는 것을 볼 수 있다.
1$ ./tcache_dup
2Chunk to be double-freed: 0x55d4db927260
3First allocation: 0x55d4db927260
4Second allocation: 0x55d4db927260