[System_Hacking] stage12_ptmalloc2

*ptmalloc2

 

지난 시간에 use after free 취약점을 설명하면서 이런 말을 한 적이 있다. 

 

"ptmalloc2는 청크 할당 요청이 들어오면 해제된 청크 중 유사한 크기의 것이 있는지 확인한 후 그것을 우선으로 내어준다."

그리고 이를 이용해 원샷 가젯을 써 익스플로잇까지 해 보았다. 여기서 ptmalloc2는 메모리 allocator의 일종이다. memory allocator는 말 그대로 할당 요청이 들어오면 메모리를 할당해주는 친구인데, 운영체제마다 (혹은 소프트웨어마다) 상이한 allocator를 이용한다. -> 리눅스의 allocator가 ptmalloc2이다.

 

ptmalloc2가 하는 일은 메모리를 효율적으로 관리할 수 있도록 하는 것이다.

 

1. 메모리 낭비 방지

2. 빠른 메모리 재사용 

3. 메모리 단편화 방지

 

이 세 가지가 ptmalloc2의 목적이라고 할 수 있음.

 

1. ptmalloc2는 메모리 할당 요청이 발생하면 이전에 해제된 메모리 공간 중 재사용 가능한 공간이 있는지 탐색하고, 같은 크기의 해제된 메모리 공간이 있으면 이를 바로 재사용, 해제된 메모리 공간보다 작은 크기의 할당 요청이 발생하면 그 영역을 나누어 주기도 한다.

 

2. 운영체제가 프로세스에게 제공하는 가상 메모리 공간은 매우 넓기 때문에, 1번과 같이 해제했던 메모리 공간을 빠르게 재할당해주려면 해제되었던 메모리 공간의 주소를 기억하고 있어야 함 -> ptmalloc2는 해제 시 tcache나 bin이라는 연결 리스트에 해제된 공간의 정보를 저장한다. (tcache와 bin은 여러 개 정의되어 있고, 각각은 서로 다른 크기의 메모리 공간들을 저장함 -> 특정 크기의 할당 요청이 들어왔을 때 그 크기와 관련된 저장소만 탐색하면 됨 -> 효율적)

 

3. 메모리 단편화는 크게 두 가지가 있다. 내부 단편화와 외부 단편화.

 

내부 단편화 : 할당한 메모리 공간의 크기에 비해 실제 데이터가 점유하는 공간이 적음.

외부 단편화 : 할당한 메모리 공간들 사이에 공간이 많아 발생하는 비효율.

 

-> ptmalloc2는 이러한 단편화를 줄이기 위해 정렬, 병합, 분할을 사용함. 

 

정렬 : 64비트 환경에서 메모리 공간을 16바이트 단위로 할당해줌. 요청한 사이즈에 가장 근접하면서 같거나 큰 16의 배수만큼 할당해줌. -> 16바이트 이내의 내부 단편화가 발생 가능하긴 하지만 외부 단편화를 감소시킴.

 

만약 정렬하지 않고 요청하는 크기만큼 붙여서 쭉 할당해주면 외부 단편화를 최소화 할 수 있지 않음? -> 메모리 공간 재사용 시 정확히 같은 크기의 할당 요청이 발생할 확률보다 비슷한 사이즈 요청이 있을 확률이 높음 -> 비슷한 크기의 요청에 대해서는 모두 같은 크기의 공간(16배수)을 내줘야 해제된 청크들을 재사용하기 쉬움. + 외부 단편화도 감소.

 

병합 : 특정 조건을 만족하면 해제된 공간들을 병합하기도 함. -> 병합된 공간만큼의 크기를 요청하면 내주거나, 혹은 그보다 작은 요청이 들어왔을 때 분할되어 사용된다. -> 재사용률 높이고 외부 단편화 줄일 수 있음.

 

 

*ptmalloc2의 객체

 

청크(chunk), bin, tcache, arena 가 ptmalloc2의 주요 객체임

 

청크 : 덩어리, 즉 ptmalloc이 할당한 메모리 공간. 헤더와 데이터로 구성된다. 헤더는 청크 관리에 필요한 정보를 담고 있고, 데이터는 사용자가 입력한 데이터가 저장됨.

 

헤더는 청크의 상태를 나타냄 -> 사용중(in-use) 청크와 해제된(freed) 청크의 헤더는 구조가 다르다.

 

청크 헤더가 어떻게 생겼냐면...

 

-prev_size : 8바이트, 인접한 직전 청크의 크기(청크 병합 시 직전 청크 찾는 데 사용)-size : 8바이트, 현재 청크 크기. (헤더도 포함한 값. 64비트 기준으로 사용 중인 청크 헤더의 크기는 16바이트(prev-size + size)이므로, 사용자가 요청한 크기를 정렬(16배수로 맞추기)하고, 그 값에 16을 더한 값임)

 

-flags : 3비트, 64비트 환경에서 청크는 16바이트 단위 -> size의 하위 4비트(헥스값으로 1자리) 는 무의미(어차피 0이니까요) -> size의 하위 3비트를 플래그값으로 활용함.

 

플래그는 순서대로 AMP ->  allocated arena(A), mmap’d(M), prev-in-use(P)이다. -> 여기서 P는 직전 청크의 사용 여부를 나타냄 -> ptmalloc은 이 플래그를 참조해 병합이 필요한지 판단할 수 있다

 

-fd : 8바이트, 연결 리스트에서 다음 청크를 가리킴, 해제된 청크에만 있음

 

-bk : 8바이트, 연결 리스트에서 이전 청크를 가리킴, 해제된 청크에만 있음

 

 

bin : 쓰레기통. 말 그대로 사용이 끝난 청크들이 저장되는 객체이다. -> 메모리 낭비를 막고 빠른 재할당을 가능하게 함.

 

ptmalloc2의 경우 128개의 bin이 있다. 62개는 small bin, 63개는 large bin, 1개는 unsorted bin이다. (2개는 사용 안 함)

 

0번 = not used - 1번 = unsorted bin, 2번 ~ 63번 = small bin[0] ~ [61], 64번 ~ 126번 = large bin[0] ~ [62], 127번 = not used 

 

-small bin : 32바이트 이상 ~ 1024바이트 미만의 청크들이 보관된다. 하나의 small bin에는 같은 크기의 청크들이 보관되며, 인덱스 하나 당 16바이트씩 커진다. -> smallbin[0] 은 32바이트, smallbin[61]은 1008바이트, d = 16인 등차수열

 

small bin은 원형 이중 연결 리스트이며, 먼저 해제된 청크가 먼저 재할당된다. (FIFO) -> 청크 관리에는 LIFO, FIFO, address-ordered가 있음. LIFO는 속도가 빠른 대신 파편화가 심하고, address-ordered는 느린 대신 파편화가 가장 적다 -> FIFO는 그 중간.

 

이중 연결 리스트 특성상 smallbin에 청크를 추가하거나 꺼낼 때 연결고리를 끊는 과정이 필요함. (연결고리를 잠깐 끊어야 추가할 수 있고, 빼올 수 있음. 묶여있는 열쇠뭉치에서 열쇠 하나 빼 오는 느낌) -> unlink라고 함.

 

smallbin의 청크들은 ptmalloc의 병합 대상임. 메모리상에서 인접한 두 청크가 해제되어있고, 얘들이 smallbin에 들어있다? -> 병합됨 (consolidation)

 

 

 

이 그림에서 A = malloc(0x80), B = malloc(0x80), C = malloc(0x80) 이렇게 할당해줬다.  그리고 free(A)해주면 헤더까지 해서 청크의 size는 0x90이므로 smallbin중 0x90크기를 저장하는 어딘가에 A의 정보가 보관된다.

 

그리고 A의 헤더는 유지, data의 상위 0x10바이트는 각각 fd와 bk정보를 담게 된다.

 

근데 이 상태에서 free(C)를 해주면 A와 C는 smallbin에 들어있지만 인접해있지 않으니 병합되지는 않음.

 

여기서 D = malloc(0x80)을 해주면 A의 위치에 D가 할당됨. (FIFO 라서 먼저 해제된 애가 먼저 재할당) 이때 데이터를 명시적으로 초기화해주지 않으면 D의 데이터 영역에 잔존하는 fd와 bk정보가 그대로 유출될 수 있고, 이를 이용해 지난 uaf_overwrite문제를 해결한 바 있다.

 

그런데 여기서 free(B)를 해주면 B와 C는 smallbin에 들어있고, 인접해 있으니 아래 그림과 같이 하나의 청크로 병합되고, 0x120사이즈를 저장하는 smallbin[idx]에 저장된다. 

 

 

-fastbin : 작은 크기의 청크 할당과 해제를 효율적으로 하기 위한 bin이다. ptmalloc2는 특정 크기 이하의 청크들은 smallbin이 아닌 fastbin에 할당한다. 

 

fastbin은 32바이트 이상 ~ 176바이트 이하의 청크들이 보관된다. -> 16바이트 단위로 10개의 fastbin존재 -> 리눅스는 이 중 작은 크기부터 7개만 이용함. -> 사실상 리눅스에서는 32바이트 이상 ~ 128바이트 이하 청크들을 fastbin에 저장하는 셈.

 

fastbin은 단일 연결 리스트이다. -> 청크를 꺼낼 때 unlink과정을 수행하지 않아도 된다. + 속도는 빠르지만 파편화가 심한 LIFO방법으로 관리된다. -> 나중에 해제된 청크가 먼저 재할당됨. + fastbin에 있는 청크들은 병합 대상이 아님. (병합 안됨)

 

 

-largebin : 1024바이트 이상의 크기를 갖는 청크들이 보관된다. smallbin과 fastbin의 각 인덱스들이 특정 크기의 청크들을 보관했던 것과 달리 largebin은 일정 범위의 청크들을 보관하며, 인덱스마다 범위는 로그적으로 증가한다. 

 

largebin[0]은 1024바이트 이상 ~ 1088바이트 미만, largebin[32]는 3072바이트 이상 ~ 3584바이트 미만 이런 식.

 

largebin은 이렇게 범위에 해당하는 모든 청크를 보관하기 때문에 재할당 요청이 들어오면 ptmalloc2는 그 안에서 크기가 가장 비슷한(best-fit) 청크를 꺼내 재할당한다. -> largebin안에서 청크들은 크기 내림차순으로 정렬되어 있다. 

 

그리고 얘는 이중 연결 리스트라 재할당 과정에서 unlink가 동반된다. + 연속된 largebin의 청크들은 병합 대상.

 

 

-unsortedbin : 분류되지 않은 청크들을 보관하는 bin이다. fastbin에 들어가지 않는 모든 청크들은 해제 시 크기 불문하고 unsortedbin에 보관된다. 원형 이중 연결 리스트이고, 내부적으로 정렬되지는 않는다.

 

smallbin크기에 해당하는 청크를 할당 요청할 시, ptmalloc2는 fastbin이나 smallbin을 탐색한 뒤 unsortedbin을 탐색한다. 만약 largebin크기에 해당하는 청크를 요청할 시 unsortedbin을 먼저 탐색함. -> 여기서 탐색된 청크는 크기에 따라 적절한 bin으로 분류된다. 

 

어떤 청크를 해제한 뒤 비슷한 크기의 청크를 바로 할당하는 경우 unsortedbin을 사용하면 청크 분류에 낭비되는 비용을 없앨 수 있다. 그리고 청크의 크기가 largebin의 범위일 경우 청크를 연결할 적절한 위치를 탐색해야 하는데, 이 과정도 생략 가능함. 

 

그리고 한번에 여러 청크들을 연속적으로 해제하는 경우 병합 및 재분류하는 과정이 반복적으로 발생해야 하는데, 이 역시 unsortedbin을 이용하면 비용 절감 가능한 부분.

 

 

 

arena : fastbin, largebin,  smallbin의 정보를 모두 담고 있는 객체이다. 멀티 쓰레드 환경에서 ptmalloc은 레이스 컨디션을 막기 위해 arena접근 시 arena에 락을 적용한다. 그런데 이 방식을 이용할 경우 레이스 컨디션은 막을 수 있지만 병목현상이 일어날 수 있다. -> ptmalloc2는 이를 최대한 피하기 위해 최대 64개의 arena를 생성할 수 있게 하고 있다. (arena에 락이 걸려서 대기해야 할 경우, 새로운 arena를 생성해서 이를 피할 수 있음.) -> 그래도 64개라는 한계가 있으므로 과도한 멀티 쓰레드 환경에서는 병목현상이 발생하게 된다. -> 그래서 도입된 게 tcache

 

*Race Condition(레이스 컨디션)

어떤 공유 자원을 여러 쓰레드나 프로세스에서 접근할 때 발생하는 오동작. 예를 들어 한 쓰레드가 어떤 사용자의 계정 정보를 조회중인데, 다른 쓰레드가 그 계정 정보를 삭제함 -> ???

 

이런 문제를 막기 위해 멀티 쓰레딩을 지원하는 프로그래밍 언어들은 락 기능을 제공한다. 한 쓰레드에서 어떤 공유 자원에 락을 걸면, 그 공유 자원을 이용하려는 다른 쓰레드는 락 해제까지 대기해야 함.

 

그런데 락은 쓰레드를 무제한으로 대기시킴 -> 구현을 잘못하거나 쓰레드 수가 많아지면 병목 현상 발생 가능. -> 대표적으로 데드락 문제가 있다. (여러 쓰레드가 서로 물려서 어떤 쓰레드도 락을 해제할 수 없는 상황)

 

 

 

tcache : thread local cache의 약자. 각 쓰레드에 독립적으로 할당되는 캐시 저장소이다. 멀티 쓰레드 환경에 최적화된 메모리 관리 매커니즘을 제공한다.

 

각 쓰레드는 64개의 tcache를 갖고 있다. fastbin처럼 LIFO방식의 단일 연결리스트이며, 하나의 tcache는 같은 크기의 청크들만 보관한다. 리눅스는 각 tcache에 보관할 수 있는 청크릐 개수를 7개로 제한하고 있다. (무제한으로 청크를 연결할 수 있으면 메모리 낭비 가능성이 있기 때문. tcache의 청크들은 병합되지 않는다.)

 

tcache에는 32바이트 이상 ~ 1040바이트 이하의 크기를 갖는 청크들이 보관된다. 이 범위의 청크들은 할당, 해제될 때 tcache를 가장 먼저 조회한다. -> 청크 보관될 tcache가 꽉 찼을 경우 bin으로 분류됨.

 

tcache는 각 쓰레드가 고유하게 갖는 캐시 -> ptmalloc은 레이스 컨디션을 고려하지 않고 이 캐시에 접근 가능하다. 그리고arena의 bin에 접근하기 전에 tcache를 먼저 사용하므로 arena에서 발생할 수 있는 병목 현상을 완화할 수 있다.

 

tcache는 보안 검사가 많이 생략돼있어 힙 익스플로잇의 좋은 도구로 활용되고 있다.

 

 

 

예를들어 0x20크기의 청크를 8개 할당했다고 하자. 

 

-> 그 중 7개를 해제하면 0x30크기의 청크를 보관하는 tcache가 꽉 차게 된다. (헤더 크기 고려)

 

-> 청크를 하나 더 해제할 경우 tcache가 꽉 찼으므로 사이즈 상 fastbin에 보관된다.

 

-> 청크를 새로 할당할 경우 LIFO방식으로 tcache에 있는 청크를 재할당한다.

 

-> 7개의 청크를 모두 재할당하면 tcache는 비워지게 되고, 하나 더 할당할 경우 fastbin에서 청크를 가져온다.