운영체제의 핵심 역할 중 하나는 한정된 메모리 자원을 각 프로세스에 효율적으로 배분하는 일입니다. 모든 프로세스는 실행 중에 메모리를 동적으로 할당하고, 할당한 메모리의 쓰임이 다하면 이를 해제합니다. 이 과정은 매우 빈번하게 일어납니다. 그래서 운영체제의는 이 동작이 빠르고, 메모리의 낭비 없이 이뤄지도록 특수한 알고리즘으로 구현됩니다.
Memory Allocator
프로세스 실행 중 메모리 동적 할당, 사용 후 할당 해제 과정을 빠르고 메모리 낭비 없이 이루어지도록 특수 알고리즘으로 구현되는 것
구현에 사용된 알고리즘에 따라 여러 종류 존재
리눅스는 ptmalloc2,
구글은 tcmalloc,
페이스북이나 파이어폭스는 jemalloc을 사용
ptmalloc2동적 메모리 관리하는 리눅스 핵심 알고리즘메모리 해제 시 해제된 메모리 특징 기억, 비슷한 메모리의 할당 요청 발생 시 빠르게 반환=> 메모리 할당 속도 향상, 불필요 메모리 사용 방지
ptmalloc2가 구현된 GLibc의 버전에 따라 적용할 수 있는 공격 기법 차이 존재
리눅스에 설치된 GLibc 버전 확인 명령어 : /lib/x86_64-linux-gnu/libc-2.27.so
Ubuntu GLIBC 2.27-3ubuntu1.4 기준 취약점, 공격 기법 공부
ㄹㅇ
ptmalloc2
ptmalloc2(pthread malloc 2)는 Wolfram Gloger가 개발한 Memory Allocator로, Doug Lea의 dlmalloc을 개선한 ptmalloc의 두 번째 버전
구현 목표 : 메모리의 효율적인 관리 = 메모리 낭비 방지 + 빠른 메모리 재사용 + 메모리 단편화 방지
메모리 단편화 방지
내부 단편화 : 할당한 메모리 공간의 크기에 비해 실제 데이터가 점유하는 공간이 적을 때 발생
외부 단편화 : 할당한 메모리 공간들 '사이'에 공간이 많아서 발생하는 비효율
단편화 심화 => 메모리 사용 효율 감소
단편화 감소 위한 ptmalloc의 방법 정렬(Alignment)과 병합(Coalescence) 그리고 분할(Split)
정렬 : 64bit 환경에서 ptmalloc은 16byte 단위 메모리 할당 => 외부 단편화 감소 효과, 16byte이내 내부 단편화 발생 가능
정확히 같은 크기의 할당 요청보다 비슷한 크기의 할당 요청 발생 확률이 높음 -> 비슷한 크기 요청에 대해 모두 같은 크기의 공간 반환 => 해제된 청크 재사용률 증가, 외부 단편화 감소
병합과 분할 : 요청에 따라 잘게 나뉜 영역 병합, 분할하여 재사용 => 해제된 공간 재사용률 상승, 외부 단편화 감소
ptmalloc의 객체
청크(Chunk), bin, tcache, arena
청크 : ptmalloc이 할당한 메모리 공간, 헤더(청크 관리 정보)+데이터(사용자 입력 데이터)로 구성
사용중인 청크(in-use) 헤더와 해제된 청크(freed) 헤더 구조 다름
| 이름 | 크기 | 의미 |
| prev_size | 8byte | 인접한 직전 청크 크기. 청크 병합 시 직전 청크 찾는 데 사용 |
| size | 8byte | 현재 청크 크기(헤더 크기 포함) 64bit 환경에서 사용중인 청크 헤더 크기 : 16byte => 사용자 요청 크기 + 16byte |
| flags | 3bit | size의 하위 3bit allocated arena(A), mmap’d(M), prev-in-use(P) prev-in-use 플래그는 직전 청크가 사용 중인지를 나타내므로, ptmalloc은 이 플래그를 참조하여 병합이 필요한지 판단할 수 있습니다. |
| fd | 8byte | 연결 리스트에서 다음 청크 가리킴 해제된 청크에만 있음 |
| bk | 8byte | 연결 리스트에서 이전 청크 가리킴 해제된 청크에만 있음 |
bin
사용 끝난 청크들 저장되는 객체
메모리 낭비 방지, 해제된 처크 빠르게 재사용할 수 있게 함
ptmalloc에 128개의 bin 정의되어 있음
smallbin
32byte~1024byte 크기 청크 보관
하나의 smallbin에는 같은 크기의 청크들만 보관
index가 증가하면 저장되는 청크들의 크기는 16바이트씩 커짐 -> smallbin[0]는 32바이트 크기의 청크를, smallbin[61]은 1008 바이트 크기의 청크를 보관
원형 이중 연결 리스트(circular doubly-linked list)
먼저 해제된 청크가 먼저 재할당(FIFO)
unlink : smallbin에 청크를 추가하거나 꺼낼 때 연결 고리를 끊는 과정이 필요
consolidation : 메모리상 인접한 두 청크 해제된 상태 + 이들이 smallbin에 들어있음 => 병합
fastbin
ptmalloc은 작은 청크들 효율적 할당, 해제 위해 특정 크기 이하 청크들은 fastbin에 저장
메모리 단편화보다 속도 우선
32byte~176byte 크기 청크 보관
16byte 단위로 10개의 fastbin 존재, 리눅스는 작은 크기부터 7개만 사용
=> 리눅스는 32byte~128byte 이하 청크들 fastbin에 저장
단일 연결 리스트(= unlink 과정 불필요)
속도 빠르나 파편화 심한 LIFO방식(나중에 해제된 청크가 먼저 재할당됨)
fastbin에 저장되는 청크들은 병합 x
largebin
1024byte 이상 크기 청크 보관
총 63개
재할당 요청 발생 시 ptmalloc은 best-fit 청크 꺼내 재할당 <- 속도 향상 위해 largebin 내 청크 크기 내림차순 정렬
이중연결리스트, 재할당 과정 unlink 과정 필요
연속된 largebin 청크들은 병합 대상
unsortedbin
미분류 청크 보관
fastbin에 들어가지 않는 모든 청크들은 해제되었을 때 크기를 구분하지 않고 unsortedbin에 보관
원형 이중 연결 리스트
내부적으로 정렬 x
smallbin 크기에 해당하는 청크를 할당 요청
ptmalloc은 fastbin / smallbin 탐색
unsortedbin을 탐색
largebin의 크기에 해당하는 청크는 unsortedbin을 먼저 탐색
탐색된 청크들은 크기에 따라 적절한 bin으로 분류됨
arena
fastbin, smallbin, largebin 등의 정보를 모두 담고 있는 객체
multi-thread 환경에서 ptmalloc은 레이스 컨디션을 막기 위해 arena에 접근할 때 arena에 락을 적용
레이스 컨디션(Race Condition) : 어떤 공유 자원을 여러 쓰레드나 프로세스에서 접근할 때 발생하는 오동작
병목 현상 유발 방지 위해 최대 64개의 arena를 생성 가능
arena에 락이 걸려서 대기해야 하는 경우, 새로운 arena를 생성
그러나 생성 갯수 64개이므로 과도한 multi-thread 환경에서는 병목 현상 발생, tcache 도입
tcache
thread local cache
각 쓰레드에 독립적으로 할당되는 캐시 저장소
각 thread 는 64개의 tcache 보유
GLibc 버전 2.26에서 도입
단일 연결리스트(LIFO)
하나의 tcache는 같은 크기의 청크들만 보관
리눅스는 각 tcache에 보관할 수 있는 청크의 갯수를 7개로 제한
내부 청크 병합 x
tcache에는 32 바이트 이상, 1040 바이트 이하의 크기를 갖는 청크들이 보관
청크가 보관될 tcache가 가득찼을 경우에는 적절한 bin으로 분류
ptmalloc은 레이스 컨디션을 고려하지 않고 이 캐시에 접근할 수 있음(각 스레드 고유 캐시이기 때문)
arena의 bin에 접근하기 전에 tcache를 먼저 사용하므로 arena에서 발생할 수 있는 병목 현상을 완화
보안 검사가 많이 생략되어 있어서 공격자들에게 힙 익스플로잇의 좋은 도구로 활용됨