1. Memory Allocator
- 메모리 관리를 위해 사용되는 Allocator에는 dlmalloc, ptmalloc2, jemalloc, tcmallc, libumem 등 다양한 종류의 메모리 할당자가 존재한다.
- 본 글에서는 "GNU C Library"의 메모리 할당자인 ptmalloc2에 대한 내용이다.
1-1. ptmalloc2
- dlmalloc코드를 기반이고 멀티 스레드에서 사용되도록 확장되었다.
- 한 번에 두 개 이상의 메모리 영역을 활성화하여, 멀티 스레드 애플리케이션을 효율적으로 처리할 수 있다.
- 복수 스레드가 동시에 malloc을 호출하면, 각 스레드는 별도의 힙 세그먼트가 생성되고 해당 힙을 유지 보수하는 데이터 구조도 분리되어 메모리에 할당된다.
- 즉, ptmalloc2를 사용하면 서로 다른 스레드가 서로 간섭하지 않고 서로 다른 메모리 영역에 접근할 수 있다.
2. Chunk
- Malloc에 메모리할당을 요청하면, 넓은 메모리의 영역(heap)을 다양한 크기의 덩어리로 나누는데, 이를 Chunk라고 한다.
- Chunk에는 In-use Chunk, Free Chunk, Top Chunk, Last Remainder가 존재한다.
- 32bit에서는 8byte단위로 할당되며, 64bit에서는 16byte로 할당된다.
- 일반적으로 malloc을 호출하고 반환되는 주소를 이용해, 데이터를 입력하는데 이는 청크의 시작 부분이 아닌 페이로드 주소이다.
- 페이로드 바로 위에는 meta-data를 포함하는 청크 헤더가 존재한다. 이는 현재 청크의 사이즈가 몇이고 인접한 청크의 사이즈는 몇인지에 대해 알 수 있으며, 해당 chunk가 사용 중인지 해제되었는지에 대해 알 수 있다.
| In-use chunk | 응용프로그램에서 할당받아 사용중인 덩어리이다. |
| Free chunk | 응용프로그램에서 시스템에 반환한 덩어리이다. |
| Top chunk | Arena의 가장 상단에 있는 덩어리이다. |
| Last Remainder chunk | Allocator는 메모리 할당할 때, Free chunk중에서 사용가능한 chunk를 확인하는데, 만약 일치하는 chunk가 없고, 요청된 크기보다 큰 chunk가 있다면 해당 덩어리를 분할한다. 이때, 분할되고 남은 덩어리를 "Last Remainder chunk"라고 한다. |
| Arena란? - 각각의 스레드가 서로 간섭하지 않고, 서로 다른 메모리 영역에서 액세스할 수 있게 도와주는 힙 영역을 의미한다. - 단일 스레드 경우는 하나의 Arena를 가지지만, 멀티 스레드는 하나 이상의 Arena를 갖고 있으며 서로 다른 Arena안에 존재하는 각각의 스레드는 정지하지 않고 힙 작업을 수행한다. - 자원고갈 문제로, 각각의 스레드마다 자신의 Arena를 갖고 있는 것은 아니며, 32bit 또는 64bit 시스템 Core의 갯수에 따라 Arena의 개수가 제한되어 있다. - 제한된 크기만큼 Arena 개수가 증가하여 더 늘릴 수 없다면 여러 스레드가 하나의 Arena안에서 공유하며 힙작업을 한다. |
3. Struct of malloc_chunk
- malloc()은 각 chunk를 관리하기 위해, malloc_chunk구조체인 mchunkptr을 선언한다.
- malloc_chunk구조체는 페이로드 위에 있는 meta-data를 의미한다.
983 /* Forward declarations. */
984 struct malloc_chunk;
985 typedef struct malloc_chunk* mchunkptr;3-1. 구조체 malloc_chunk
- 6개의 정보를 관리한다.
- 이전 Chunk가 Free Chunk가 되면, 이전 Chunk의 크기가 "mchunk_prev_size"에 저장된다.
- 반대로 이전 Chunk가 In-use chunk가 되면, 이전 Chunk의 사용자 데이터가 배치된다.
- In-use Chunk의 크기는 "mchunk_size"에 저장되며, 필드 맨 끝 3bit는 flag정보를 나타낸다.
- Free chunk는 크기와 히스토리에 따라 다양한 목록에 저장되는데, 이러한 목록들을 "bins"라고 한다.
- fd, bk, fd_nextsize, bk_nextsize는 chunk가 Free Chunk일 경우에만 사용된다.
- fd (Forward pointer) : 다음 Free Chunk의 포인터를 가진다.
- bk (Backward pointer) : 이전 Free Chunk의 포인터를 가진다.
- fd_nextsize, bk_nextsize : large bin에서 사용하는 포인터이다.
- 모든 청크 크기는 MALLOC_ALIGNMENT(2 * sizeof(size_t))의 배수이다.
- 32bit는 size_t의 크기가 4byte이기 때문에, chunk의 크기는 8의 배수가 된다.
984 struct malloc_chunk {
985
986 INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */
987 INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */
988
989 struct malloc_chunk* fd; /* double links -- used only if free. */
990 struct malloc_chunk* bk;
991
992 /* Only used for large blocks: pointer to next larger size. */
993 struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
994 struct malloc_chunk* bk_nextsize;
995 };- mchunk_size필드 맨 끝 3bit는 플래그로 사용되며, 아래와 같이 정의된다.
| PREV_INUSE [P](0X1) 플래그 | 인접한 이전 청크가 사용중일 때 또는 free된 청크가 fastins에 들어가는 경우 1로 세팅된다. |
| IS_MMAPPED [M](0X2) 플래그 | chunk가 mmap()으로 할당받은 경우 1로 세팅되며, free될 경우 allocator는 해당 청크가 사용하고 있는 영역(mmap으로 할당받은 영역을 mummap()을 통해 바로 커널에 돌려주는데 사용된다. |
| NON_MAIN_ARENA [A](0X4) 플래그 | Main Arena가 아닌 Arena로부터 할당받은 경우 1로 세팅된다. |
1221 /*
1222 --------------- Physical chunk operations ---------------
1223 */
1224
1225
1226 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1227 #define PREV_INUSE 0x1
1228
1229 /* extract inuse bit of previous chunk */
1230 #define prev_inuse(p) ((p)->size & PREV_INUSE)
1231
1232
1233 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1234 #define IS_MMAPPED 0x2
1235
1236 /* check for mmap()'ed chunk */
1237 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1238
1239
1240 /* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
1241 from a non-main arena. This is only set immediately before handing
1242 the chunk to the user, if necessary. */
1243 #define NON_MAIN_ARENA 0x4
1244
1245 /* check for chunk from non-main arena */
1246 #define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)3-2. In-use chunk
- 할당자로부터 메모리를 할당받아 사용중인 메모리 덩어리를 의미한다.
- 해당 chunk의 크기는 mchunk_size에 저장되며, 필드의 맨 끝 3bit는 flag정보를 나타낸다.
(1) in-use chunk를 확인하기 위한 코드
- malloc 크기가 136byte와 80byte인 메모리 할당을 요청하며, 이를 통해 반환된 포인터를 heap1, heap2에 저장한다.
- free함수를 통해, heap1이 가르키는 메모리의 해제를 요청한다.
- 이후, 다시 malloc 크기가 136byte인 메모리 할당을 요청하며, 이번에는 heap3에 반환된 포인터를 저장한다.
- read함수를 이용하여, heap3이 가르키는 메모리에 데이터를 입력한다.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
void main(){
char *heap1 = malloc(136);
char *heap2 = malloc(80);
free(heap1);
char *heap3 = malloc(136);
read(STDIN_FILENO,heap3,136);
}
(2) gdb를 통해, 디버깅하여 메모리 변화를 확인한다.
- 디버깅 코드
① 첫번째, malloc() 호출되기 전 상황이다.
- 시스템은 Heap 공간이 필요한 경우에만 프로세스에 해당 공간을 맵핑하므로, malloc호출 후에 해당 프로세스에 Heap 공간이 매핑되는 것을 확인할 수 있다.
- 할당자로부터 할당받은 첫 번째 heap의 포인터는 0x5555555592a0이다.
- size(0x555555559298)에 0x91(145)가 저장되어 있다.
- 본 바이너리는 64bit이기 때문에, 청크의 크기는 모두 16의 배수가 된다.
따라서, 136(0x88)은 16의 배수가 아니라서, 해당 수와 가장 가까운 16의 배수인 144(0x90)가 청크의 크기이다. - 144에 PREV_INUSE [P](0x1)에 대한 플래그 값을 더해, 145(0x91)가 들어있는 것을 확인할 수 있다.
- 할당 가능한 메모리의 크기가 0x555555559328에 저장된 것을 확인할 수 있다.
② 두번째 malloc() 호출된 후 상황이다.
- 두번째 heap의 포인터는 0x555555559330이며, 청크의 크기는 0x61(97)임을 알 수 있다.
- 하지만, 실제적으로 코드에서 요청했던 사이즈는 0x50(80)이다.
이는 할당자가 청크 관리하기 위해, 필요한 메타데이터(fd, bk)를 저장하기 위해 요청된 크기 16byte를 더했기 때문이다. - 또한, 0x60에 PREV_INUSE [P](0x1)에 대한 플래그 값을 더해, 0x61이 들어있는 것을 확인할 수 있다.
③ free함수로 heap1인 첫번째 청크를 해제한 상황이다.
- 0x5555555592a0 ~ 0x5555555592a8 메모리에 fd, bk값이 저장된다.
④ 세번째 malloc() 호출된 후 상황이다.
- 세번째 heap의 포인터는 0x5555555592a0이며, 처음에 할당했던 heap1 포인터와 동일하다.
- 이는 malloc() 함수가 메모리 효율성을 위해, free chunk를 관리하기 때문이다.
따라서, 할당자는 메모리 할당 요청을 받으면, free chunk를 먼저 사용한다. - 다시 할당된 chunk는 이전에 저장된 데이터가 초기화되지 않고 그대로 존재한다.
- 새로 할당받은 heap3메모리는 정상적으로 사용이 가능하며, 값을 입력하게 되면 이전에 저장되어있던 heap1의 값을 덮어쓰게 된다.
3-3. Free chunk
- 할당자에게 반환된 메모리 덩어리를 의미한다.
- chunk의 크기에 따라 fd, bk, fd_nextsize, bk_nextsize의 값이 해당 chunk내에 저장된다.
- chunk의 크기가 최소 크기일 경우, fd_nextsize, bk_nextsize의 값을 저장할 수 없다.
- Free chunk의 크기는 커지지 않으므로, chunk 크기가 최소의 경우는 prev_size, size, fd, bk값만 메모리에 저장된다.
- fd_nextsize, bk_next size는 큰 블록에서만 사용된다.
(1) Free chunk를 확인하기 위한 코드
- malloc에 128byte와 8byte 크기인 메모리를 각각 3개씩 할당 요청한다.
- 그리고 128byte 크기인 메모리 3개를 해제한다.
#include <stdio.h>
#include <stdlib.h>
void main(){
char *heap1 = malloc(128);
char *tmp1 = malloc(8);
char *heap2 = malloc(128);
char *tmp2 = malloc(8);
char *heap3 = malloc(128);
char *tmp3 = malloc(8);
free(heap1);
free(heap2);
free(heap3);
}
(2) gdb를 통해, 디버깅하여 메모리 변화를 확인한다.
- 디버깅 코드
pwndbg> disassemble main
Dump of assembler code for function main:
0x0000555555555169 <+0>: endbr64
0x000055555555516d <+4>: push rbp
0x000055555555516e <+5>: mov rbp,rsp
0x0000555555555171 <+8>: sub rsp,0x30
0x0000555555555175 <+12>: mov edi,0x80
0x000055555555517a <+17>: call 0x555555555070 <malloc@plt>
0x000055555555517f <+22>: mov QWORD PTR [rbp-0x30],rax
0x0000555555555183 <+26>: mov edi,0x8
0x0000555555555188 <+31>: call 0x555555555070 <malloc@plt>
0x000055555555518d <+36>: mov QWORD PTR [rbp-0x28],rax
0x0000555555555191 <+40>: mov edi,0x80
0x0000555555555196 <+45>: call 0x555555555070 <malloc@plt>
0x000055555555519b <+50>: mov QWORD PTR [rbp-0x20],rax
0x000055555555519f <+54>: mov edi,0x8
0x00005555555551a4 <+59>: call 0x555555555070 <malloc@plt>
0x00005555555551a9 <+64>: mov QWORD PTR [rbp-0x18],rax
0x00005555555551ad <+68>: mov edi,0x80
0x00005555555551b2 <+73>: call 0x555555555070 <malloc@plt>
0x00005555555551b7 <+78>: mov QWORD PTR [rbp-0x10],rax
0x00005555555551bb <+82>: mov edi,0x8
0x00005555555551c0 <+87>: call 0x555555555070 <malloc@plt>
0x00005555555551c5 <+92>: mov QWORD PTR [rbp-0x8],rax
0x00005555555551c9 <+96>: mov rax,QWORD PTR [rbp-0x30]
0x00005555555551cd <+100>: mov rdi,rax
0x00005555555551d0 <+103>: call 0x555555555060 <free@plt>
0x00005555555551d5 <+108>: mov rax,QWORD PTR [rbp-0x20]
0x00005555555551d9 <+112>: mov rdi,rax
0x00005555555551dc <+115>: call 0x555555555060 <free@plt>
0x00005555555551e1 <+120>: mov rax,QWORD PTR [rbp-0x10]
0x00005555555551e5 <+124>: mov rdi,rax
0x00005555555551e8 <+127>: call 0x555555555060 <free@plt>
0x00005555555551ed <+132>: nop
0x00005555555551ee <+133>: leave
0x00005555555551ef <+134>: ret
End of assembler dump.
① 첫번째 malloc() 호출된 후 상황이다.
- heap의 어디 주소부터 할당되었는지 확인할 수 있다.
② 마지막 malloc할당을 끝마친 상황이다.
- chunk 크기 128byte 메모리 3개가 각각 0x5555555592a0, 0x555555559350, 0x555555559400에 할당된 것을 확인할 수 있다.
- chunk 크기 8byte 메모리 3개가 각각 0x555555559330, 0x5555555593e0, 0x555555559490에 할당된 것을 확인할 수 있다.
③ 첫번째 free() 호출된 후 상황이다.
- heap1이 해제되면, 해당 chunk에 fd, bk가 저장된다.
④ 두번째 free() 호출된 후 상황이다.
- heap2이 해제되면, 해당 chunk에 fd, bk가 저장된다.
⑤ 세번째 free() 호출된 후 상황이다.
- heap3이 해제되면, 해당 chunk에 fd, bk가 저장된다.
# 참고주소
'System Hacking' 카테고리의 다른 글
| Malloc(3) - Arena (glibc의 ptmalloc2) (0) | 2022.09.16 |
|---|---|
| Malloc(2) - Bin (glibc의 ptmalloc2) (0) | 2022.09.14 |
| Fake EBP (0) | 2022.08.03 |
| RTC (Return To CSU) (0) | 2022.07.04 |
| RTL (Return to Library) (0) | 2022.06.29 |