[Dreamhack] Background: ptmalloc2

부동산 중개업자가 하는 일이 새로운 주거리를 찾는 사람들과 주거지를 파려는 사람들의 만남을 도와서 주거지의 공실을 최대한 줄이고, 부동산 시장의 효율을 높이는 것이라고 할 수 있듯이, 운영체제에서 이러한 중개업자와 비슷한 역할을 하는 것이 Memory Allocator이다.

운영 체제의 핵심 역할 중 하나는 한정된 메모리 자원을 각 프로세스에 효율적으로 배분하는 일이다. 모든 프로세스는 실행중에 메모리를 동적으로 할당하고, 할당한 메모리의 쓰임이 다하면 이를 해제한다. 이 과정은 매우 빈번하게 일어난다. 그래서 운영체제의 Memory Allocator는 이 동작이 빠르고, 메모리의 낭비 없이 이뤄지도록 특수한 알고리즘으로 구현한다. 몇몇 소프트웨어는 직접 구현한 Memory Allocator를 사용하기도 한다.

Memory Allocator는 구현에 사용된 알고리즘에 따라 여러 종류가 있다. 리눅스는 ptmalloc2, 구글은 tcmalloc, 페이스북이나 파이어폭스는 jemalloc을 사용한다. 그 중 강의에서 다룰 Memory Allocator는 리눅스의 ptmalloc2이다.

ptmalloc2는 어떤 메모리가 해제되면, 해제된 메모리의 특징을 기억하고 있다가 비슷한 메모리의 할당 요청이 발생하면 이를 빠르게 반환해준다. 이는 부동산 중개업의 원리와 비슷하다. 이를 통해 메모리 할당의 속도를 높일 수 있고, 불필요한 메모리 사용을 막을 수 있다. 

ptmalloc2는 동적 메모리를 관리하는 리눅스의 핵심 알고리즘이며, 이와 관련하여 과거부터 다양한 공격 기법이 연구되었다. 물론, 이제까지의 강의들에서 살폈듯, 이런 새로운 공격 기법은 새로운 보호 기법들을 탄생하게 했다. 그 결과 ptmalloc2는 ptmalloc2가 구현된 GLibc의 버전에 따라서 적용할 수 있는 공격 기법에 큰 차이가 생기기도 한다.

본 강의는 Ubuntu 18.04 64-bit(Glibc 2.27 버전) 환경을 기준으로 취약점과 공격 기법을 소개한다.

이 강의에서는 ptmalloc2의 핵심 개념을 개괄적으로 설명하는 한편, GLibc 2.26부터 도입된 tcache와 관련된 공격 기법들을 간단히 살펴볼 것이다. ptmalloc2와 관련된 공격 기법들을 모두 익히려면 배워야할 내용이 매우 많으며, 입문 강의에서 다루기에는 다소 지엽적이기도 하다. 강의에서 소개하지 않는 ptmalloc2와 관련된 다양한 공격기법들은 심화 강의에서 소개할 예정이다.

 

** ptmalloc2

* ptmalloc2

ptmalloc2(pthread malloc 2)는 Wolfram Gloger가 개발한 Memory Allocator로 Doug Lea의 dlmalloc을 개선한 ptmalloc의 두 번째 버전이다. 이하에서는 버전을 제거하고 ptmalloc이라고 부를 것이다. ptmalloc은 리눅스에서 사용하고 있으며 GLibc에 구현되어 있다.

ptmalloc의 구현 목표는 메모리의 효율적인 관리이다. 이 한 문장에는 여러 세부 목표가 함축되어있다. 그 중 핵심을 추려보면 다음과 같다.

1. 메모리 낭비 방지
2. 빠른 메모리 재사용
3. 메모리 단편화 방지

ptmalloc을 구성하는 핵심 객체들을 살펴보기 전에, 이 목표들에 대응되는 ptmalloc의 메모리 관리 전략을 알아보자

 

* 메모리 낭비 방지

메모리의 동적 할당과 해제는 매우 빈번하게 일어난다. 그런데 컴퓨터의 전체 메모리는 한정적이므로 새로운 메모리 공간을 무한히 할당할 수는 없다. 그래서 ptmalloc은 메모리 할당 요청이 발생하면, 먼저 해제된 메모리 공간 중에서 재사용할 수 있는 공간이 있는지 탐색한다.

해제된 메모리 공간 중에서 요청된 크기와 같은 크기의 메모리 공간이 있다면 이를 그대로 재사용하게 된다. 또한 작은 크기의 할당 요청이 발생했을 대, 해제된 메모리 공간 중 매우 큰 메모리 공간이 있으면 그 영역을 나누어주기도 한다.

 

* 빠른 메모리 재사용

운영체제가 프로세스에게 제공해주는 가상 메모리 공간은 매우 넓다. 따라서 특정 메모리 공간을 해제한 이후에 이를 빠르게 재사용하려면 해제된 메모리 공간의 주소를 기억하고 있어야 한다. 이를 위해 ptmalloc은 메모리 공간을 해제할 때, tcache 또는 bin이라는 연결 리스트에 해제된 공간의 정보를 저장해둔다.

tcache와 bin은 여러 개가 정의되어 있으며, 각각은 서로 다른 크기의 메모리 공간들을 저장한다. 이렇게 하면 특정 크기의 할당 요청이 발생했을 대, 그 크기와 관련된 저장소만 탐색하면 되므로 더욱 효율적으로 공간을 재사용할 수 있다.

 

* 메모리 단편화 방지

메모리 단편화(Memory Fragmentation)는 컴퓨터 과학의 메모리 관리 이론에서 다루는 중요한 문제 중 하나이다. 물건을 포장해서 배송할 때, 물건보다 박스가 너무 크면 박스 내부에 빈 공간이 많이 남아서 배송의 효율이 떨어진다. 또한 박스의 모양이 제각각이라서 어떤 박스는 구모양이고, 어떤 박스는 별모양이면, 박스를 적재했을 때 박스들 사이에 공간이 많이 생겨서 마찬가지로 배송 효율이 떨어지게 된다. 컴퓨터 과학에서는 전자를 내부 단편화(Internal Fragmentation), 후자를 외부 단편화(External Fragmentation) 라고 부른다.

내부 단편화는 할당한 메모리 공간의 크기에 비해 실제 데이터가 점유하는 공간이 적을 때 발생한다. 반대로 외부 단편화는 할당한 메모리 공간들 사이에 공간이 많아서 발생하는 비효율을 의미한다. 이를 단편화라고 부르는 이유는 전체 메모리 공간이 여러 데이터들에 의해 부분적으로 점유되기 때문이다. 단편화가 심해질수록, 각 데이터 사이에 공간이 많아져서 메모리 사용의 효율이 감소한다.

ptmalloc은 단편화를 줄이기 위해 정렬(Alignment)과 병합(Coalescence) 그리고 분할(Split)을 사용한다. 64비트 환경에서 ptmalloc은 메모리 공간을 16바이트 단위로 할당해준다. 사용자가 어떤 크기의 메모리 공간을 요청하면 그보다 조금 크거나 같은 16바이트 단위의 메모리 공간을 제공한다. 예를 들어 4바이트를 요청하면 16바이트를, 17바이트를 요청하면 32바이트를 할당해주는 방식이다. 이렇게 공간을 정렬하면 16바이트 이내의 내부 단편화가 발생할 수 있지만, 역설적으로 외부 단편화를 감소시키는 효과가 있다.

공간을 정렬하지 않고, 프로세스가 요청하는만큼 할당할 수 있다면 모든 데이터가 연속적으로 할당되어외부 단편화를 최소화할 수 있을것 같다. 그러나 공간을 해제하고 재사용할 대, 정확히 같은 크기의 할당 요청이 발생할 확률보다 비슷한 크기의 요청이 발생할 확률이 높다. 그래서 비슷한 크기의 요청에 대해서는 모두 같은 크기의 공간을 반환해야 해제된 청크들의 재사용률을 높이고, 외부 단편화도 줄일 수 있다.

한편, ptmalloc은 특정 조건을 만족하면 해제된 공간들을 병합하기도 한다. 병합으로 생성된 큰 공간은 그 공간과 같은 크기의 요청에 의해, 또는 그보다 작은 요청에 의해 분할되어 재사용된다. 잘게 나뉜 영역을 병합하고, 필요할 때 구역을 다시 설정함으로써 해제된 공간의 재사용률을 높이고, 외부 단편화를 줄일 수 있다.

 

** ptmalloc2의 객체

ptmalloc2는 청크(Chunk), bin, tcache, arena를 주요 객체로 사용한다. 각각에 대해 간략히 짚어보자

 

* 청크

청크(chunk)는 덩어리라는 뜻으로, 여기서는 ptmalloc이 할당한 메모리 공간을 의미한다. 청크는 헤더와 데이터로 구성된다. 헤더는 청크 관리에 필요한 정보를 담고 있으며, 데이터 영역에는 사용자가 입력한 데이터가 저장된다.

청크의 구조

 

헤더는 청크의 상태를 나타내므로 사용중인 청크(in-use)의 헤더와 해제된 청크(freed)의 헤더는 구조가 다소 다르다. 사용 중인 청크는 fd와 bk를 사용하지 않고, 그 영역에 사용자가 입력한 데이터를 저장한다.

청크 헤더의 각 요소는 다음과 같다.

이름	크기	의미
prev_size	8바이트	인접한 직전 청크의 크기. 청크를 병합할 때 직전 청크를 찾는 데 사용됩니다.
size	8바이트	현재 청크의 크기. 헤더의 크기도 포함한 값입니다. 64비트 환경에서, 사용 중인 청크 헤더의 크기는 16바이트이므로 사용자가 요청한 크기를 정렬하고, 그 값에 16바이트를 더한 값이 됩니다.
flags	3비트	64비트 환경에서 청크는 16바이트 단위로 할당되므로, size의 하위 4비트는 의미를 갖지 않습니다. 그래서 ptmalloc은 size의 하위 3비트를 청크 관리에 필요한 플래그 값으로 사용합니다. 각 플래그는 순서대로 allocated arena(A), mmap’d(M), prev-in-use(P)를 나타냅니다. prev-in-use 플래그는 직전 청크가 사용 중인지를 나타내므로, ptmalloc은 이 플래그를 참조하여 병합이 필요한지 판단할 수 있습니다. 나머지 플래그에 대해서는 여기서 설명하지 않겠습니다.
fd	8바이트	연결 리스트에서 다음 청크를 가리킴. 해제된 청크에만 있습니다.
bk	8바이트	연결 리스트에서 이전 청크를 가리킴. 해제된 청크에만 있습니다.

 

* bin

bin은 문자 그대로, 사용이 끝난 청크들이 저장되는 객체이다. 메모리의 낭비를 막고, 해제된 청크를 빠르게 재사용할 수 있게 한다.

ptmalloc에는 총 128개의 bin이 저장되어 있다. 이중 62개는 smallbin, 63개는 largebin, 1개는 unsortedbin으로 사용되고, 나머지 2개는 사용되지 않는다.

bin

 

* smallbin

smallbin에는 32바이트 이상 1024바이트 미만의 크기를 갖는 청크들이 보관된다. 하나의 smallbin에는 같은 크기의 청크들만 보관되며, index가 증가하면 저장되는 청크들의 크기는 16바이트씩 커진다. 즉 smallbin[0]은 32바이트 크기의 청크를, smallbin[61]은 1008 바이트 크기의 청크를 보관한다.

smallbin은 원형 이중 연결 리스트(circular doubly-linked list)이며, 먼저 해제된 청크가 먼저 재할당된다. 이같은 방식을 FIFO(선입선출)이라고 부른다. 청크를 관리하는 방법에는 크게 LIFO, FIFO, address-ordered가 있다. 연구에 따르면 LIFO는 속도가 빠르지만 파편화가 심하고, address-ordered는 정렬을 해야해서 속도는 느리지만 파편화가 가장 적다. FIFO는 그 중간에 있다.

이중연결 리스트의 특성 상, smallbin에 청크를 추가하거나 꺼낼 때 연결 고리를 끊는 과정이 필요한다. 열쇠고리에서 열쇠를 빼내려면 고리를 잠시 끊어야하는 것과 같은 이치이다. ptmalloc은 이 과정을 unlink라고 부른다. 또한, smallbin의 청크들은 ptmalloc의 병합 대상이다. 메모리상에서 인접한 두 청크가 해제되어 있고, 이들이 smallbin에 들어있으면 이 둘은 병합된다. ptmalloc은 이 과정을 consolidation이라고 부른다.

아래에서 smallbin의 할당 및 해제, 그리고 병합 과정을 간단히살펴볼 수 있다.

 

* fastbin

일반적으로 크기가 작은 청크들이 큰 청크들보다 빈번하게 할당되고 해제된다. 그래서 작은 청크들의 할당과 해제를 효율적으로 하는 게 전체적인 효율성 측면에서 중요하다. 이런 이유로 ptmalloc은 어떤 크기를 정해두고, 이보다 작은 청크들은 smallbin이 아니라 fastbin에 저장한다. 그리고 이들을 관리할 때는 메모리 단편화보다 속도를 조금 더 우선순위로 둔다.

fastbin에는 32바이트 이상 176바이트 이하 크기의 청크들이 보관되며, 이에 따라 16바이트 단위로 총 10개의 fastbin이 있다. 리눅스는 이 중에서 작은 크기부터  7개의 fastbin만을 사용한다. 즉, 리눅스에서는 32바이트 이상, 128바이트 이하의 청크들을 fastbin에 저장한다.

fastbin은 단일연결 리스트이다. 단일연결리스트이므로 청크를 꺼낼 때 꺼낸 청크의 앞과 뒤를 연결하는 unlink 과정을 수행하지 않아도 된다. 또한, fastbin은 속도는 빠르지만 다른 방법에 비해 파편화가 심한 LIFO의 방법으로 사용된다. 이에 따라 나중에 해체된 청크가 먼저 재할당된다. 마지막으로 fastbin에 저장되는 청크들은 서로 병합되지 않는다. 그래서 청크 간 병합에 사용되는 연산도 아낄 수 있다.

아래에서 fastbin의 할당과 해제 과정을 살필 수 있다.

 

* largebin

largebin은 1024바이트 이상의 크기를 갖는 청크들이 보관된다. 총 63개의 largebin이 있는데, smallbin, fastbin과 달리 한 largebin에서 일정 범위 안의 크기를 갖는 청크들을 모두 보관한다. 이 범위는 largebin의 인덱스가 증가하면 로그적으로 증가한다. 예를 들어, largebin[0]은 1024바이트 이상, 1088 바이트 미만의 청크를 보관하며, large[32]는 3072바이트 이상, 3584바이트 미만의 청크를 보관한다. 이런 방법을 사용하면 적은 수의 largebin으로 다양한 크기를 갖는 청크들을 관리할 수 있다.

largebin은 범위에 해당하는 모든 청크를 보관하기 때문에, 재할당 요청이 발생했을 대 ptmalloc은 그 안에서 크기가 가장 비슷한 청크(best-fit)를 꺼내 재할당한다.이 과정을 빠르게 하려고 ptmalloc은 largebin 안의 청크를 크기 내림차순으로 정렬한다. largebin은 이중연결 리스트이므로 재할당과정에서 unlink도 동반된다. 또한 연속된 largebin 청크들은 병합의 대상이 된다.

 

* unsortedbin

unsortedbin은 문자 그대로, 분류되지 않은 청크들을 보관하는 bin이다. unsortedbin은 하나만 존재하며, fastbin에 들어가지 않는 모든 청크들은 해제되었을 때 크기를 구분하지 않고 unsortedbin에 보관된다. unsortedbin은 원형 이중 연결 리스트이며 내부적으로 정렬되지는 않는다.

smallbin크기에 해당하는 청크를 할당 요청하면, ptmalloc은 fastbin 또는 smallbin을 탐색한 뒤 unsortedbin을 탐색한다. largebin 크기에 해당하는 청크는 unsortedbin을 먼저 탐색한다. unsortedbin에서 적절한 청크가 발견되면 해당 청크를 꺼내어 사용한다. 이 과정에서, 탐색된 청크들은 크기에 따라 적절한 bin으로 분류된다.

ptmalloc은 unsortedbin을 활용하여 불필요한 연산을 줄이고, 성능을 최적화한다. 연구에 따르면,어떤 청크를 해제한 다음에 비슷한 크기의 청크를 바로 할당하거나, 또는 한 번에 여러 청크들을 연속적으로 해제하는 경우가 빈번하게 발생한다고 한다.

전자의 상황에서 unsortedbin을 사용하면, 청크 분류에 낭비되는 비용을 없앨 수 있다. 또한, 청크의 크기가 largebin의 범위에 속하면 청크를 연결할 적절한 위치를 탐색해야하느데 이 과정도 생략할 수 있다. 한편, 후자의 상황에서는 연속적으로 청크를 해제하면서, 병합하고 재분류하는 과정이 반복적으로 발생한다. unsortedbin을 사용하면 이러한 비용을 줄일 수 있다.

 

* arena

arena는 fastbin, smallbin, largebin 등의 정보를 모두 담고있는 객체이다. 멀티 쓰레드 환경에서 ptmalloc은 레이스 컨디션을 막기 위해 arena에 접근할 때 arena에 락을 적용한다. 그런데 이 방식을 사용하면 레이스 컨디션은 막을 수 있지만, 반대로 병목 현상을 일으킬 수 있다.

ptmalloc은 이를 최대한 피하기 위해 최대 64개의 arena를 생성할 수 있게 하고 있다. arena에 락이 걸려서 대기해야하는 경우, 새로운 arena를 생성해서 이를 피할 수 있다. 그런데 생성할 수 있는 갯수가 64개로 제한되어 있으므로 과도한 멀티 쓰레드 환경에서는 결국 병목현상이 발생한다. 그래서 glibc 2.26에서는 tcache를 추가적으로 도입했다

💡레이스 컨디션(Race Condition)

레이스 컨디션은 어떤 공유 자원을 여러 쓰레드나 프로세스에서 접근할 때 발생하는 오동작을 의미합니다. 예를 들어, 한 쓰레드가 어떤 사용자의 계정 정보를 참조하고 있는데, 다른 쓰레드가 그 계정 정보를 삭제하면, 참조하고 있던 쓰레드에서는 삭제된 계정 정보를 참조하게 됩니다. 이는 경우에 따라 심각한 보안 문제로 이어질 수 있습니다

이런 문제를 막기 위해 멀티 쓰레딩을 지원하는 프로그래밍 언어들은 락(Lock) 기능을 제공한다. 락은 문자 그대로 자물쇠의 역할을 한다. 한 쓰레드에서 어떤 공유 자원에 락을 걸면, 그 공유 자원을 이용하려는 다른 쓰레드는 락이 해제될 때까지 기다려야 한다. 공유 자원을 사용하는 동안락을 걸어놓음으로써 다른 쓰레드에 의한 조작을 차단할 수 있고, 레이스 컨디션을 방지할 수 있다.

그런데 락은 쓰레드를 무제한으로 대기시키기 때문에, 구현을 잘못하거나 쓰레드의 수가 과다하게 많아지면 병목현상을 일으킬 수 있다. 락으로 발생하는 대표적인 문제 중 하나가 데드락(Deadlock)이다. 여러 쓰레드가 서로 물리고 물려서 어떤 쓰레드도 락을 해제하지 못하는 상황을 의미한다.

레이스 컨디션을 이용한 공격 기법은 심화 로드맵에서 실습한다.

 

* tcache

tcache는 thread local cache의 약자이다. 이름에서 알 수 있듯, 각 쓰레드에 독립적으로 할당되는 캐시 저장소를 지칭한다. tcache는 glibc 버전 2.26에서 도입되었으며, 멀티 쓰레드 환경에 더욱 최적화된 메모리 관리 메커니즘을 제공한다.

각 쓰레드는 64개의 tcache를 가지고 있다. tcache는 fastbin과 마찬가지로 LIFO 방식으로 사용되는 단일 연결 리스트이며, 하나의 tcache는 같은 크기의 청크들만 보관한다. 리눅스는 각 tcache에 보관할 수 있는 청크의 갯수를 7개로 제한하고 있는데, 이는 쓰레드마다 정의되는 tcache의 특성 상, 무제한으로 청크를 연결할 수 있으면 메모리가 낭비될 수 있기 때문이다. tcache에 들어간 청크들은 병합되지 않는다.

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

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

tcache는 보안검사가 많이 생략되어 있어서 공격자들에게 힙 익스플로잇의 좋은 도구로 활용되고 있다. 이 로드맵에서는 tcache를 이용한 힙 익스플로잇 기법을 중점적으로 살펴볼 것이다.

아래에서 tcache를 활용한 메모리 할당과 해제 과정을 살필 수 있다.

마치며

마치며

이번 강의에서는 ptmalloc2를 구성하는 핵심 객체들과 청크들을 관리하는 메커니즘을 개략적으로 알아보았습니다. ptmalloc2에는 강의에서 배운 내용보다 훨씬 복잡하고, 다양한 원리가 내재되어 있습니다. 이 내용들을 이해해야 ptmalloc2와 관련된 공격 기법들을 모두 이해할 수 있지만, 이 로드맵은 입문 로드맵이므로 관련된 내용은 이 정도로만 소개하겠습니다. ptmalloc2와 관련된 더욱 복잡한 내용과 공격 기법들은 추후에 심화 로드맵에서 다루도록 하겠습니다.

다음 강의에서는 ptmalloc2에서 발생하는 대표적인 취약점 중 하나인 Double Free Bug를 소개하겠습니다. 🚩

키워드

Memory Allocator : 프로세스의 요청에 따라 동적으로 메모리를 할당 및 해제해주는 주체, 또는 관련된 알고리즘들의 집합. dlmalloc, ptmalloc, jemalloc, tcmalloc 등이 있으며, 리눅스는 그 중에서 ptmalloc2를 사용한다. 구현되는 방식은 다소 차이가 있지만, 핵심 목표는 메모리 단편화의 최소화, 공간 복잡도 및 시간 복잡도의 최적화이다. ptmalloc(pthread memory-allocation) : dlmalloc을 모태로하는 메모리 할당자. malloc , free , realloc 등을 기반으로 사용자의 동적 메모리 요청을 처리함. 사용하는 주요 객체로는 청크, bins, arena, tcache가 있음. 청크(Chunk) : ptmalloc2가 메모리를 할당하는 단위. bins : 해제된 청크들을 보관함. ptmalloc은 bin을 이용하여 청크를 빠르게 재할당하고, 단편화를 최소화함. bins에는 fastbin, smallbin, largebin, unsortedbin이 있음. arena : ptmalloc이 관리하는 메모리들의 정보가 담겨있음. 모든 쓰레드가 공유하는 자원으로, 한 쓰레드가 이를 점유하면 race condition을 막기 위해 lock이 걸림. 병목 현상을 막기 위해 64개까지 생성 가능하지만, 이를 초과할 정도로 많은 연산이 발생하면 병목 현상이 일어남. tcache : 쓰레드마다 해제된 청크들을 보관하는 저장소. 멀티 쓰레드 환경에서 arena가 가지고 있는 병목 현상의 문제를 일부 해결해줄 수 있음. 쓰레드마다 할당되므로 용량을 고려하여 각 tcache당 7개의 청크만 보관할 수 있음.|

 

Q1. largebin에 보관할 수 있는 청크의 갯수는 10개로 제한된다.

X

개수 제한 없음.

 

Q2. 청크를 재할당 할 때, bin를 먼저 비운 뒤 tcache에서 청크를 꺼낸다.

X

tcache는 먼저 비워지지 않고, 청크를 재할당할 때 우선적으로 tcache에서 청크를 꺼내 사용한다.

 

Q3. 메모리 파편화를 막기위해 연속된 fastbin의 청크는 병합된다.

X

fastbin에 저장되는 청크들은 서로 병합되지 않는다. 그래서 청크 간 병합에 사용되는 연산도 아낄 수 있다.

 

Q4. smallbin의 청크를 재할당할 때, unlink과정을 수행해야 한다.

O

이중연결 리스트의 특성 상, smallbin에 청크를 추가하거나 꺼낼 때 연결 고리를 끊는 과정이 필요한다. 열쇠고리에서 열쇠를 빼내려면 고리를 잠시 끊어야하는 것과 같은 이치이다. ptmalloc은 이 과정을 unlink라고 부른다