이 글은 https://dreamhack.io/lecture/courses/98 을 토대로 작성된 글입니다.

1. Introduction

운영체제는 한정된 메모리 자원들을 각 프로세스에 할당하는 것이 중요하다.

모든 프로세스는 실행 중에 메모리를 동적으로 할당하고, 할당된 메모리가 할 일을 다 했으면 해제한다.

이러한 과정은 자주 일어난다.

그래서 운영체제의 Memory Allocator는 이 동작이 빠르고, 메모리의 낭비 없이 이뤄지도록 특수한 알고리즘으로 구현된다.

Memory Allocator는 구현에 사용된 알고리즘에 따라 여러 종류가 있다.

리눅스는 ptmalloc2, 구글은 tcmalloc, 페이스북이나 파이어폭스는 jemalloc을 사용한다.

여기서 ptmalloc2는 어떤 메모리가 해제되면, 해제된 메모리의 특징을 기억하고 있다가 비슷한 메모리의 할당 요청이 발생하면 이를 빠르게 반환해준다.

이를 통해 메모리 할당의 속도를 높일 수 있고, 불필요한 메모리 사용을 막을 수 있다.

2. ptmalloc2

ptmalloc2(pthread malloc 2)는 Wolfram Gloger가 개발한 Memory Allocator로, Doug Lea의 dlmalloc의 개선한 ptmalloc의 두번째 버전이다.

ptmalloc은 리눅스에서 사용하고 있으며, GLibc에 구현되어 있다.

ptmalloc의 구현 목표는 메모리의 효율적인 관리이다.

핵심은

1. 메모리 낭비 방지

2. 빠른 메모리 재사용

3. 메모리 단편화 방지

이렇게 볼 수 있다.

2.1 메모리 낭비 방지

메모리의 동적 할당과 해제는 매우 빈번하게 일어난다.

그런데 컴퓨터의 전체 메모리는 한정적이므로 새로운 메모리 공간을 무한히 할당할 수 없다.

그래서 ptmalloc은 메모리 할당 요청이 발생하면, 먼저 해제도니 메모리 공간 중에서 재사용 가능한 공간이 있는지 탐색한다.

해제된 메모리 공간 중에서 요청된 크기와 같은 크기의 메모리 공간이 있다면 이를 그대로 재사용하게 한다.

또한, 작은 크기의 할당 요청이 발생했을 때, 해제된 메모리 공간 중 매우 큰 메모리 공간이 있으면 그 영역을 나눠주기도 한다.

2.2 빠른 메모리 재사용

운영체제가 프로세스에게 제공해주는 가상 메모리 공간은 넓다.

따라서 특정 메모리 공간을 해제한 이후에 이를 빠르게 재사용하려면 해제된 메모리 공간의 주소를 기억하고 있어야 한다.

이를 위해 ptmalloc2는 메모리 공간을 해제할 때, tcache 또는 bin이라는 연결 리스트에 해제된 공간의 정보를 저장해둔다.

tache와 bin은 여러 개가 정의되어 있고, 각각은 서로 다른 크기의 메모리 공간들을 저장한다.

이렇게 하면 특정 크기의 할당 요청이 발생했을 때, 그 크기와 관련된 저장소만 탐색하면 되므로 더욱 효율적으로 공간을 재사용할 수 있다.

2.3 메모리 단편화 방지

메모리 단편화(Memory Fragmentation)는 컴퓨터 과학의 메모리 관리 이론에서 다루는 중요한 문제 중 하나이다.

이 문제는 내부 단편화(Internal Fragmentation)과 외부 단편화(External Fragmentation)가 있다.

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

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

단편화라고 하는 이유는 전체 메모리 공간이 여러 데이터들에 의해 부분적으로 점유되기 때문이다.

단편화가 심해질수록, 각 데이터 사이에 공간이 많아져서 메모리 사용의 효율이 감소한다.

ptmalloc은 단편화를 줄이기 위해 정렬(Alignment)와 병합(Coalescence) 그리고 분할(Split)을 사용한다. 64비트 환경에서 ptmalloc은 메모리 공간을 16바이트 단위로 할당해준다.

사용자가 어떤 크기의 메모리 공간을 요청하면, 그보다 조금 크거나 같은 16바이트 단위의 메모리 공간을 제공한다.

3. ptmalloc의 객체

ptmalloc2는 청크(Chunk), bin, arena, tcache를 주요 객체로 사용한다.

4. chunk

청크는 덩어리라는 뜻으로, 여기서는 ptmalloc이 할당한 메모리 공간을 의미한다.

(stack에서 buf처럼)

청크는 헤더와 데이터로 구성된다.

헤더는 청크 관리에 필요한 정보를 담고 있고, 데이터 영역에는 사용자가 입력한 데이터가 저장된다.

헤더는 청크의 상태를 나타내므로 사용 중인 청크(inuse)의 헤더와 해제된 청크(freed)의 헤더는 구조가 다르다.

사용 중인 청크는 fd와 bk를 사용하지 않고, 그 영역에 사용자가 입력한 데이터를 저장한다.

4.1 chunk's header

4.2 chunk's structure

5. bin

bin은 문자 그대로, 사용이 끝난 청크들이 저장되는 객체이다.(쓰레기통)

메모리의 낭비를 막고, 해제된 청크를 빠르게 재사용할 수 있게 한다.

ptmalloc에는 총 128개의 bin이 정의되어 있다.

이 중 62개는 smallbin, 63개는 largebin, 1개는 unsortedbin으로 사용되고, 나머지 2개는 사용되지 않는다.

bin's structure

청크 관리 방법

1. LIFO(Last-In-First-Out)

나중에 해제된 청크가 먼저 재할당 된다.

LIFO는 속도 빠름, 파편화 심함

2. FIFO(First-In-First-Out)

먼저 해제된 청크가 먼저 재할당 된다.

FIFO는 속도 평법, 파편화 평범

3. address-ordered

address-ordered는 속도 느림, 파편화 적음

정렬을 해서 속도 느림

5.1 smallbin

5.1.1 설명

smallbin에는 32 바이트 이상 1024 바이트 미만의 크기를 갖는 청크들이 보관된다.

하나의 smallbin에는 같은 크기의 청크들만 보관되며, index가 증가하면 저장되는 청크들의 크기는 16바이트씩 커진다.

즉, smallbin[0]는 32바이트 크기의 청크를 ,smallbin[61]은 1008 바이트 크기의 청크를 보관한다.

5.1.2 연결 방식

smallbin은 원형 이중 연결 리스트(circular doubly-linked list)이며, FIFO 방식이다.

5.1.3 unlink

이중 연결 리스트에서, smallbin에 청크를 추가하거나 꺼낼 때 연결 고리를 끊는 과정이 있다.

ptmalloc에서 이 과정을 unlink라고 부른다.

5.1.4 consolidation

smallbin의 청크들은 ptmalloc의 병합 대상이다.

메모리상에서 인접한 두 청크가 해제되어 있고, 이들이 smallbin에 들어있으면 이 둘은 병합된다.

ptmalloc에서 이 과정을 consolidation이라고 한다.

5.1.5 실습

1. A, B, C 할당

A = malloc(0x80)

B = malloc(0x80)

C = malloc(0x80)

2. A 해제

A가 해제 되면, A의 시작 주소를 smallbin에 추가한다.

3. C 해제

C가 해제 되면, FIFO 방식으로 C의 시작 주소가 A 다음에 추가된다.

(이유는, A의 주소가 먼저 나가야하기 때문)

4. D 할당

D를 할당하기 위해 이전 A 시작주소인 0x12340000가 smallbin에서 unlink되어 D 할당에 쓰인다.

그리고, smallbin에는 C의 이전 주소인 0x12340120만 있다.

5. B 해제

원래 smallbin에는 0x12340120만 있었다.

메모리 상에서의 0x12340120은 해제된 상태이다.

B가 해제 된 후에는, smallbin에 B의 시작 주소인 0x12340090이 추가된다.

두 주소는,

1. 메모리에서 해제된 상태이고,

2. 인접해 있다.

3. smallbin에도 존재하므로

병합된다.

continue

https://velog.io/@securitykss/Dreamhack-Use-After-Free-1-ptmalloc2-cont#52-fastbin

Reference

https://dreamhack.io/lecture/courses/98