Heap 시리즈
[Heap] Background : Memory Allocator
[Heap] Background : Bin (Fastbin, Unsorted bin, Small bin, Large bin)
[Heap] Memory Corruption : Use After Free(UAF) (1)
Chunk
malloc 등을 통해 메모리를 동적할당하면 Memory Allocator는 heap을 다양한 크기의 덩어리(chunk)로 나눠 반환해준다.
즉, 동적 할당으로 인해 할당받은 메모리 (혹은 반환한 메모리)와 같이 '힙을 쪼개서 얻어진 덩어리'를 청크라고 한다.
아니면 힙을 통해 동적 할당을 받은 메모리들의 단위라고 볼 수도 있겠다!
또한 memory allocator의 정렬기법을 통해 32bit에선 chunk가 8byte 단위로 할당이 되고 64bit에서는 16byte 단위로 할당이 된다.
청크 종류를 간단하게 요약하면 아래와 같다. 이 청크들에 대해서는 아래에서 하나하나 자세히 살펴볼 것이다.
- Allocated Chunk(In-use Chunk) : 메모리가 할당되어 현재 사용되고 있는 청크
- Free Chunk : free등을 통해 반환된 청크. bin이나 tcache 등에 정보 저장됨
- Top Chunk : heap 맨 아래(주소는 가장 높은 곳에) 있는 청크. 즉 heap의 맨끝. bin에서 원하는 크기가 없으면 top chunk를 쪼개서 반환함.
- Last-Remainder Chunk : free 청크가 쪼개지고 남은 청크
Structure
청크는 In-use(Allocated),freed,top,last-remainder 청크들로 나뉠 수 있는데, 일단 간단하게 In-use 청크와 Freed 청크의 구조를 보자. In-use(Allocated) 청크는 현재 메모리를 할당받아 사용되고 있는 청크이고, Free 청크는 해제된 청크이다.
컴퓨터를 공부해보았다면 익숙하겠지만, 보통 데이터에는 데이터 그 자체만 있지 않다. 그 데이터의 '정보', 즉 메타 정보도고 함께 포함하고 있다. 청크도 마찬가지로 '헤더'에 청크의 정보가 담겨있다. 이에 대해 자세히 살펴보자.
위 그림처럼 청크는 1)헤더(메타정보)와 2)데이터 영역으로 이루어져있다.
데이터영역에는 실제 우리가 적은 데이터가 들어가며, 헤더에는 메타정보가 들어간다. 이제 헤더에 정확히 어떠한 정보가 들어가는지 살펴보자!!
그림에서는 In-use 청크, Free 청크 모두 Data 이외에 공통적으로 prev_size, size 부분을 가지고 있다. 각 부분에 대해서는 밑에서 자세히 살펴볼 것이다. 청크는 아래처럼 malloc_chunk 구조체로 구현되어있다.
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};
일단 Allocated Chunk와 Free Chunk의 구조가 살짝 다른데, size 부분은 거의 비슷하므로 size부터 보고 나머지 멤버들은 각 청크들 별로 설명하도록 하겠다.
size
할당받은 메모리의 크기 + 헤더의 크기 (헤더의 크기를 합치는 것 주의!!!)
64비트 환경에서, 사용 중인 청크 헤더의 크기는 16바이트(prev_size 8byte+size 8byte)이므로 사용자가 요청한 크기를 정렬하고, 그 값에 16바이트를 더한 값이 된다. ([Heap] Basic : Memory Allocator 에서 ptmalloc2는 '정렬'이라는 기법을 통해 데이터를 효율적으로 관리한다고 언급했었다.)
한편, size의 마지막 3bit는 flag로 사용된다.
64bit환경에서 chunk는 16byte의 배열로 정렬되어 할당이 된다(16byte,32byte....)
예를 들어 16-byte alignment에서 가능한 사이즈를 살펴보면 아래와 같다.
00000000 00010000 = 16바이트
00000000 00100000 = 32바이트
00000000 00110000 = 48바이트따라서 청크의 사이즈(비트가 아닌 바이트!)를 나타낼때 최소 1000(2) ,즉 16byte가 되는 것이다. 왜냐하면 2진수의 1000은 16을 의미하므로! 따라서 하단 3bit는 항상 0이 되므로 이부분을 플래그 3개를 적는걸로 공간을 활용하는 것이다.
- NON_MAIN_ARENA(A) - 현재 청크가 thread_arena에 위치하는 경우 1로 세팅됨 (즉, main_arena에서 관리 x)
- IS_MMAPPED(M) - 현재 청크가 mmap을 통해 할당된 경우 1로 세팅됨. 큰 메모리를 요청하는 경우에는 heap을 이용하지 않고, mmap() 시스템 콜을 통해 별도의 메모리 영역을 할당함. 이러한 청크들은 bin 내에 속하지 않음(??) free시 그냥 munmap() 호출로 해지함
- PREV_INUSE(P) - 현재 청크 바로 이전의 청크가 할당되어 있는 경우 1로 세팅됨
Allocated Chunk (할당된 청크)
Allocated Chunk(혹은 In-use Chunk)는 현재 메모리를 할당받아 사용되고 있는 청크이다.
Allocated-Chunk인 경우 간단하다. size는 위에서 설명했으니 넘어가도록 하겠다.
prev_size
"이전 청크가 free chunk"일 경우, 이전 청크의 크기 (병합을 위해 사용함)
만약 이전 청크가 free chunk가 아닌 경우 이 부분은 이전 payload(데이터 영역)의 일부로 사용됨 (뒤에서 설명 예정)
Free Chunk (해제된 청크)
Free Chunk는 free 등의 동적 메모리 해제 함수로로 해제된 청크를 의미한다. 아래 그림을 통해 Free Chunk 구조를 확인해보자.
fd, bk (Free chunk일 때만 쓰임)
fd(FowarD) - 연결된 청크에서 같은 bin의 다음 free 청크를 가리킴
bk(BacKward) - 연결된 청크에서 같은 bin의 이전 free 청크를 가리킴
chunk가 free되면 bin에 들어가는데 이 bin은 연결리스트로 되어있다. 이때 fd,bk를 통해서 리스트를 순회할 수 있게되는 것이다.
한편 fd_nextsize, bk_nextsize는 large bin에서만 사용된다.
fd_nextsize는 large bin에서 다음 free chunk를 가리키는데, 현재 힙 청크의 크기보다 작은 크기의 청크를 가리킨다.
bk_nextsize는 large bin에서 이전 free chunk를 가리키는데, 현재 힙 청크의 크기보다 큰 크기의 청크를 가리킨다.
이 이유는 large bin에서는 크기가 내림차순으로 정렬되기 때문에 다음으로 갈 수록 청크의 크기가 작아진다.
(만약 large bin에서 같은 크기의 청크들이 연결되어 있다면 fd_nextsize나 bk_nextsize는 사용하지 않는다. 자세한 내용은 Bin 포스트 참고)
주의해야할 것은 이 Free Bin들이 '물리적'으로 연결된 것이 아닌 '논리적'으로 연결된 것이라는 것이다. 마치 아래 그림처럼 말이다!!! 그리고 fd,bk는 '같은 bin'에서의 연결 고리이다! 따라서 물리적으로 연결된 free chunk들이어도 다른 bin에 각기 존재하면 fd,bk가 서로를 가리키기지 않을 수도 있다.
Boundary Tag 기법
Boundary Tag 기법에 대해 조금 더 살펴보자. Boundary Tag기법은 청크가 해제되었을 때 size부분을 아래에 복사해서 저장하는 것을 의미한다. 이부분은 다음 청크의 Prev_size 영역으로 공유해서 사용하게 된다.
이를 그림으로 정리하면 아래와 같다.
최종적으로 Allocated Chunk(In-use Chunk)와 Free Chunk의 구조를 비교하면 아래와 같다.
Top Chunk
힙의 마지막, 즉 가장 아래(가장 높은 주소)에 있는 청크를 말한다. 그리고 Top Chunk는 어느 bin에도 들어가지 않는다!
Malloc을 통해 동적 할당을 처음하게 되면, Top Chunk에 충분한 크기에 메모리를 할당하게 된다. 그리고 이 청크를 쪼개서 새로운 청크들을 만들어낸다.
만약 top chunk에 인접한 청크가 해제되면 top chunk와 병합하게 된다.
Top Chunk에서 청크를 할당할 때에는 Top Chunk가 User Chunk(할당하려는 청크)와 Remainder Chunk(남은 청크. 이 것이 새로운 Top Chunk가 된다.)로 나뉘어진다. 이런 경우는 처음으로 청크를 할당하거나, 사용자가 요청한 size의 청크가 bin이나 tcache에 없을 때이다.
1. 사용자가 요청한 size가 어느 bin에서도 찾을 수 없을 때
= Top chunk에서 분할하여 할당
2. 사용자가 요청한 size가 어느 bin에서도 찾을 수 없고, top chunk size보다 커서 분할할 수 없을 때
※ top chunk < 요청 size < 128kb인 경우에는 main_arena = sbrk syscall로 확장, thread_arena = mmap으로 확장
※ top chunk < 128kb < 요청 size인 경우는 main_arena, thread_arena 모두 mmap으로 확장
Last Remainder Chunk
청크를 할당할 때 allocator는 먼저 free chunk들 중에서 쓸만한 청크가 있는지 살펴보는데, 만약 사용자가 요청한 size와 같같은게 없을 때 그보다 큰 청크를 할당하게 되는데, 이때 할당하고 남은 나머지를 Last Remainder Chunk라고 하게된다.
Last Remainder Chunk는 연속된 작은 사이즈의 할당 요청이 들어왔을 때 비슷한 주소에 힙 청크가 할당되는 할당의 지역성을 유지시키기 위해 사용된다.
실습
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 int main()
5 {
6 char* a=(char*)malloc(0x20);
7
8 char* b=(char*)malloc(0x14);
9
10 char* c=(char*)malloc(0x30);
11
12 char* d=(char*)malloc(0x14);
13
14 char* e=(char*)malloc(0x22);
15
16 strcpy(a,"AAAAAAAA");
17 strcpy(b,"BBBBBBBBBBBBBBBBBBBB");
18 strcpy(c,"CCCCCCCC");
19 strcpy(d,"CCCCCCCC");
20 strcpy(e,"BBBBBBBB");
21
22 free(b); // fastbin fd, bk checking
23 free(d); // fastbin fd, bk checking
24
25 char* sg=(char*)malloc(0x100);
26 strcpy(sg,"SSSSSSSS");
27 free(sg); // prev_size checking
28
29 char* z=(char*)malloc(0x100);
30 char* test=(char*)malloc(140000); // mmap'd flag checking
31 free(test);
32 return 0;
33 }
1. char*e=(char*)malloc(0x22); 직후에 b를 걸어줬다. (청크 a,b,c,d,e 할당 직후!)
2. strcpy를 통해 각 청크들에 데이터를 적었다.
이후의 heap 구조를 알기 위해 strcpy(e,"BBBBBBBB");직후에 b를 걸었다.
3. free(b), free(d) 이후의 heap 상황
청크 b,d 사이즈가 다 작아서 일단 tcache에 저장되어있는 것을 볼 수 있다.
heapinfo명령어로 확인해봐도 아직 fastbin에는 아무것도 없고 tcache_entry에만 청크들이 들어가있는 것을 확인할 수 있었다.
그런데 이거 fd가 이상하네,,, 왜 이럴까 ㅠ
4. char* test=(char*)malloc(140000); 직후에 breakpoint를 걸어 rax를 확인하자.
rax에는 0x7ffff...어쩌고 이렇게 되어있는데, 아까 청크들이 0x5555..이런 주소에 할당받은 것과는 완전히 다른 위치다.
이는 할당한 메모리의 사이즈가 너무 커서(140000) mmap으로 할당해주었기 때문이다.
참고로 malloc이 반환하는 주소는 청크주소가 아니라 청크의 메모리 주소부터이므로, rax-0x10을 해줘 헤더부터 출력해보자.
우측 상단에 23002를 10진수로 바꿔보면 143,362가 나오고 이는 우리가 할당한 140000에 맞춰 할당해준 것임을 알 수 있다. 일단은 사이즈가 크므로 mmap으로 할당했다는 것만 알아가자.
그렇다면 0x7ffff7da7000이 어디인지 vmmap으로 살펴보자
References
01.Malloc - glibc(ptmalloc2)[Korean] - TechNote - Lazenca.0x0
Heap 기초2 (oopy.io) <- 많이 참고했습니다!!
Structure of Chunk — Ro_ll_ing (tistory.com)
https://confidence-10211.tistory.com/109
'Linux Exploitation > Heap' 카테고리의 다른 글
| [Heap] Exploitation : Double Free Bug (0) | 2023.06.15 |
|---|---|
| [Heap] Exploitation : Unsorted Bin Memory Leak (0) | 2023.06.11 |
| [Heap] Background : Bin (Fastbin, Unsorted bin, Small bin, Large bin) (1) | 2023.06.09 |
| [Heap] Memory Corruption : Use After Free(UAF) (0) | 2023.05.30 |
| [Heap] Background : Memory Allocator (0) | 2023.05.18 |
