Free
free chunk는 bin이라는 freelist 구조체를 통해 관리
* freelist: 동적으로 메모리를 할당하고 해제할 때 메모리 관리의 효율을 높이기 위해 할당되지 않은 영역을 관리하는 연결 리스트
메모리 해제 : 해제하려는 영역을 freelist에 추가 / 메모리 할당 : freelist에 추가된 영역을 제거하고 해당 영역을 사용
-> 할당자는 할당 요청을 충족시키기 위해 적합한 청크를 bins에서 신속하게 찾아서 재할당한다.
-> bins의 종류에는 Fast bin, Small bin, Large bin, Unsorted bin이 있다.
-> 이는 malloc_state구조체(Arena_Header)에서 확인 가능하다.
malloc_state구조체(Arena_Header)
struct malloc_state
{
/* Serialize access. */
mutex_t mutex;
/* Flags (formerly in max_fast). */
int flags;
/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
/* topchunk의 base address */
mchunkptr top;
/* 가장 최근의 작은 요청으로부터 분리된 나머지 */
mchunkptr last_remainder;
/* 위에서 설명한대로 pack된 일반적인 bins */
mchunkptr bins[NBINS * 2 - 2];
/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];
/* 연결 리스트 */
struct malloc_state *next;
/* 해제된 아레나를 위한 연결 리스트 */
struct malloc_state *next_free;
/* 현재 Arena의 시스템으로부터 메모리 할당 */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};Bin 정보는 위의 malloc_state 구조체에서 관리된다.
- FastbinsY : Fast bin을 관리함
- Bins : 총 127개의 빈중 제일 처음 빈은 특별한 용도(Unsorted bin)으로 사용되고 나머지 126개가 unsorted bin, small bin, large bin으로 사용된다.
자세한 Bins의 구성은 다음과 같다(Index 0은 특별한 용도로 쓰임)
- Index 1 : Unsorted bin
- Index 2 ~ 63 : Small bin
- Index 64 ~ 126 : Large bin
할당된 청크는 청크 사이즈의 크기에 따라서 다음과 같이 구분된다.
| Chunk | Chunk size(32 bit) | Chunk size(64 bit) |
| Fast chunk | 16 ~ 64 byte | 32 ~ 128 byte |
| Small chunk | Size of User data < 1024 byte | |
| Large chunk | Size of User data >= 1024 byte | |
이러한 빈들이 존재하는 이유는, malloc 요청시 매번 메모리 할당을 요청하는것이 아닌, free 청크들을 재사용하기 위함이다. 사용자가 요청한 특정 사이즈의 청크가 특정 bin에 존재한다면, 그것을 재할당해준다.
또한 물리적으로 인접해 있는 free 청크들은 일반적으로 서로 병합을 하여 큰 free 청크를 만드려고 한다. (fastbin 제외)크게 현재 청크의 이전 청크와 병합하거나, 다음 청크와 병합하는 경우가 있다.
Fast bin
작은 크기의 힙 청크를 할당하고 해제할 때 사용하는 bin
Symbol param # default allowed param values
M_MXFAST 1 64 0-80 (0 disables fastbins)
M_TRIM_THRESHOLD -1 128*1024 any (-1U disables trimming)
M_TOP_PAD -2 0 any
M_MMAP_THRESHOLD -3 128*1024 any (or 0 if no MMAP support)
M_MMAP_MAX -4 65536 any (0 disables use of mmap)
/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
#ifndef M_MXFAST
#define M_MXFAST 1
#endif
#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST (64 * SIZE_SZ / 4)
#endif* M_MXFAST(1)라는 매개변수를 사용해서 "fastbin"에 포함되는 청크의 범위를 설정한다.
* 32비트 아키텍처에서 패스트빈의 상한은 64byte(64*4/4)이며, 64비트 아키텍처에서는 128byte(64*8/4)이다.
* LIFO(last in, first out) 방식 -> 마지막으로 해제된 chunk가 먼저 재 할당된다.
* 최대 10개의 bin 관리 할 수 있으며, 패스트빈의 상한 값보다 크기가 작은 chunk들을 관리한다.
* single-linked list -> ptmalloc2의 bin 중 할당 및 해제 속도가 가장 빠름.
(청크 해제 시 같은 크기의 청크가 이미 bin에 존재한다면, 그 청크의 주소를 현재 해제된 청크의 FD에 저장)
* 해당 bin에 포함되는 chunk들은 서로 인접해 있어도 병합하지 않는다.
fastbin 크기를 가진 청크의 해제 과정
if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
#if TRIM_FASTBINS
/*
If TRIM_FASTBINS set, don't place chunks
bordering top into fastbins
*/
&& (chunk_at_offset(p, size) != av->top)
#endif
) {
if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect (chunksize (chunk_at_offset (p, size))
>= av->system_mem, 0))
{
/* We might not have a lock at this point and concurrent modifications
of system_mem might have let to a false positive. Redo the test
after getting the lock. */
if (have_lock
|| ({ assert (locked == 0);
mutex_lock(&av->mutex);
locked = 1;
chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
|| chunksize (chunk_at_offset (p, size)) >= av->system_mem;
}))
{
errstr = "free(): invalid next size (fast)";
goto errout;
}
if (! have_lock)
{
(void)mutex_unlock(&av->mutex);
locked = 0;
}
}
free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
set_fastchunks(av);
unsigned int idx = fastbin_index(size);
fb = &fastbin (av, idx);
/* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */
mchunkptr old = *fb, old2;
unsigned int old_idx = ~0u;
do
{
/* Check that the top of the bin is not the record we are going to add
(i.e., double free). */
if (__builtin_expect (old == p, 0))
{
errstr = "double free or corruption (fasttop)";
goto errout;
}
/* Check that size of fastbin chunk at the top is the same as
size of the chunk that we are adding. We can dereference OLD
only if we have the lock, otherwise it might have already been
deallocated. See use of OLD_IDX below for the actual check. */
if (have_lock && old != NULL)
old_idx = fastbin_index(chunksize(old));
p->fd = old2 = old;
}
while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
{
errstr = "invalid fastbin entry (free)";
goto errout;
}
}△ free 함수에서 fastbin 청크를 처리하는 코드
line 1 : 청크가 해제될 때 해당 청크가 fastbin 크기의 범위에 속해 있다면 line 1의 조건문을 통과
line 41 : 이후 line 41에서 현재 청크의 크기에 해당하는 fastbin의 리스트를 가져옴.
line 61 : 만약 해당 fastbin freelist에 먼저 저장되어있는 청크가 존재한다면, line 61에서 그 청크의 주소를 현재 해제된 청크의 FD에 저장한다.
-> 이로 인해 해제된 청크가 fastbin의 단일 연결 리스트에 추가된다는 것을 알 수 있다.
fastbin freelist에 들어있는 청크를 할당하는 과정
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
idx = fastbin_index (nb);
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp = *fb;
do
{
victim = pp;
if (victim == NULL)
break;
}
while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
!= victim);
if (victim != 0)
{
if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
{
errstr = "malloc(): memory corruption (fast)";
errout:
malloc_printerr (check_action, errstr, chunk2mem (victim), av);
return NULL;
}
check_remalloced_chunk (av, victim, nb);
void *p = chunk2mem (victim); //return chunk ptr
alloc_perturb (p, bytes); //init
return p;
}
}△ malloc 함수에서 fastbin 청크를 처리하는 코드
line 4 : 현재 요청된 fastbin 크기와 부합하는 fastbin의 인덱스를 찾음.
line 12 : 선택된 청크의 FD를 참조하여 대상 청크의 FD가 가리키는 청크를 fastbin의 첫 번째 리스트로 업데이트하여 LIFO 구조를 유지
line 26 : line 26에서 청크를 반환하면 해당 과정은 종료됌.
다음 코드를 통해 fastbin이 어떻게 관리되는지 확인해보자
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char* a=(char*)malloc(0x10);
char* b=(char*)malloc(0x20);
char* b2=(char*)malloc(0x25);
char* c=(char*)malloc(0x30);
char* d=(char*)malloc(0x40);
char* d2=(char*)malloc(0x45);
char* e=(char*)malloc(0x50);
char* f=(char*)malloc(0x60);
char* g=(char*)malloc(0x70);
free(a);
free(b);
free(b2);
free(c);
free(d);
free(d2);
free(e);
free(f);
free(g);
return 0;
}총 10번의 malloc 호출을 하고 전부다 free를 하는 단순한 코드이다. fastbin이 관리하는 0x20 ~ 0x80 사이즈를 확인하기 위해 사이즈별로 동적할당을 진행한다. 또한 단일연결 리스트로 구성되는 걸 확인하기 위해 b2와 d2를 추가적으로 삽입하였다.
- fastbin[0] : 0x20 : 요청한 크기 0x10 + 헤더 0x10 이 합쳐져 총 0x20 bytes의 청크가 만들어졌고 0번 인덱스 binlist에 추가됨
- fastbin[1] : 0x30 : 청크는 0x10 단위로 할당되므로 요청 사이즈 0x20과 0x25은 0x30 사이즈로 할당된다. 따라서 binlist의 0x30 사이즈인 인덱스 1에 추가된다. b청크(0x602020)이 먼저 추가되고, 그 이후에 b2청크(0x602050)가 추가된것을 확인할 수 있다
- fastbin[2] : 0x40
- fastbin[3] : 0x50 : d청크와 d2청크 모두 헤더포함 0x50 사이즈이므로 3번 인덱스에 추가됨
- fastbin[4] : 0x60
- fastbin[5] : 0x70
- fastbin[6] : 0x80
위 그림을 보면 a, c, e, f, g 청크들이 위치한 인덱스에는 단 하나밖에 free 청크가 없다. 이러한 청크들은 next free chunk를 가리키는 포인터가 저장되있는 fd가 0으로 세팅된다.
반면 b2, d2의 fd는 set 되있는 것을 알 수 있다.
- fastbin[1]→b2(0x602050)→b(0x602020)
- fastbin[3]→d2(0x602120)→d(0x6020c0)
Small bin
: 512 바이트 미만의 사이즈로 청크가 해제 되었을 때 unsorted bin에 리스트가 추가된 후 저장되는 bin
* 32bit 시스템에서 Small bin의 범위는 16~504byte(64*8-8)이며 64bit에서는 32~1008byte이다.
* 해당 bin은 64개의 bin들을 관리하며, doubly-linked list로 구성된다.
-> 같은 크기의 chunk가 해제되면 마지막으로 해제된 chunk의 fd에 새로 해제된 chunk의 mchunkptr가 저장된다.
-> 새로 해제된 chunk의 bk에 마지막으로 해제된 같은 크기의 chunk의 mchunkptr가 저장된다.
* FIFO(First In, First Out) 방식 -> 먼저 해제 된 청크가 먼저 재 할당된다.
* Small bin에 해당되는 chunk들은 서로 인접하게 배치될 수 없다.
-> 해당 chunk가 서로 인접해 있을 경우 하나의 chunk로 병합된다.
일반적인 경우 0x80까지는 fastbin에 들어가지만, 리스트에 연결된 청크가 10개가 넘어가는 경우 0x20 ~ 0x80 사이즈 청크는 small bin에 들어간다.
다음 코드를 통해 smallbin이 어떻게 동작하는지 확인해보자.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char* a=(char*)malloc(0x80);
char* b=(char*)malloc(0x400);
char* c=(char*)malloc(0x40);
char* d=(char*)malloc(0x3e0);
free(a);
char* e=(char*)malloc(0x500);
free(d);
char* f=(char*)malloc(0x500);
return 0;
}a는 fast chunk 사이즈 큰 청크중 가장 작은 사이즈이고, d는 small bin 중 제일 큰 청크가 될 것이다.
또한 일부러 보기쉽게 인접하지 않게 free를 했다. return 0 바로 위 라인 (char* f 부분)이 실행된 직후의 메모리 상황을 살펴보자.
fast chunk size 보다 큰 값중 제일 작은 small bin size에 헤더포함 0x90 청크가 들어가있다. 또한 small bin의 가장 큰 사이즈인 0x3f0 사이즈의 청크가 들어가 있는걸 확인 할 수 있다.
Large bin
large bin은 0x400 이상의 청크가 저장되는 bin으로써, 메모리 할당과 반환의 속도가 fastbin, unsorted bin, small bin 중에서 가장 느리다.
* Large bin이 포함하는 chunk의 크기 : MIN_LARGE_SIZE와 같거나 큰 chunk들.
64bit 아키텍처의 경우 free chunk의 크기가 1024와 같거나 큰 경우
* Large bin이 포함하는 chunk들은 서로 인접해 있을 경우 하나의 chunk로 병합된다.
* 63개의 bin을 사용하며, small bin과 같이 doubly-linked list로 구성
* Small Bin과 다르게 하나의 bin에 다양한 크기의 chunk들을 보관
-> 해당 bin들은 bin내에서 크기 별로 정렬되어 할당의 효율성을 높임.
하나의 빈에 다양한 크기의 청크가 저장되기 때문에 빈 내부에서 적당한 크기의 청크를 찾기 쉽도록 내림차순으로 정렬하여 저장된다. 따라서 맨 왼쪽이 가장 큰 청크가 되고, 맨 오른쪽이 가장 작은 청크가 된다.
다음 코드를 통해 largebin이 어떻게 동작하는지 확인해보자.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char* a0=(char*)malloc(0x3f0);
char* b0=(char*)malloc(0x80);
char* a1=(char*)malloc(0x400);
char* b1=(char*)malloc(0x40);
char* a2=(char*)malloc(0x410);
char* b2=(char*)malloc(0x200);
char* a3=(char*)malloc(0x420);
char* b3=(char*)malloc(0x200);
char* a4=(char*)malloc(0x430);
char* b4=(char*)malloc(0x300);
char* a5=(char*)malloc(0x440);
char* b5=(char*)malloc(0x300);
char* a6=(char*)malloc(0x450);
char* b6=(char*)malloc(0x300);
char* a7=(char*)malloc(0x460);
char* b7=(char*)malloc(0x300);
char* a8=(char*)malloc(0x470);
char* b8=(char*)malloc(0x300);
free(a0);
char* e0=(char*)malloc(0x500);
free(a1);
char* e1=(char*)malloc(0x500);
free(a2);
char* e2=(char*)malloc(0x500);
free(a3);
char* e3=(char*)malloc(0x600);
free(a4);
char* e4=(char*)malloc(0x600);
free(a5);
char* e5=(char*)malloc(0x500);
free(a6);
char* e6=(char*)malloc(0x500);
free(a7);
char* e7=(char*)malloc(0x600);
free(a8);
char* e8=(char*)malloc(0x600);
return 0;
}위 코드는 보기 쉽게 병합이 진행되지 않게 malloc 및 free가 되는 로직으로 짜여졌다.
맨 마지막 malloc이 호출된 직후 메모리 상황을 봐보자. (a로 시작하는 변수들이 살펴볼 부분)
정리하자면 다음과 같은 상황이다.
largebin[0] : 0x602f20 (size : 0x430) <---> 0x6828f0 (size : 0x428) <---> ....
largebin[1] : 0x604b80 (size : 0x470) <---> 0x684418 (size : 0x468) <---> ....현재 largebin[0]에 0x400부터 0x430 까지의 사이즈를 가진 청크가 들어가 있다. 또한 정렬이되어 맨 왼쪽이 가장 큰 사이즈를 갖는다.
larebin[0] 의 각 청크들은 모두 사이즈가 다르므로 fd,bk와 fd_nextsize,bk_nextsize 모두 동일할 것이다.
Unsorted bin
bins의 첫번째 인덱스가 바로 Unsorted bin의 list로 사용된다. 이는 일종의 cache와 같은 역할로 free된 청크가 자기의 빈(small bin or large bin)으로 바로 들어가지 않고 먼저 unsorted bin으로 들어간다. (단 fastbin은 예외).
그 이후 malloc 요청시 동일한 크기의 영역을 다시 요청하는 경우 unsorted bin에 들어있는 청크를 바로 재사용 할 수 있게 한다. 이는 FIFO 방식으로 동작하며, malloc 요청으로 unsorted bin에서 검색된 청크들은 알맞은 사이즈인 경우 재사용을 하게 하고 알맞은 사이즈가 아닌 경우 이때 각자 자기의 bin(small or large bin)으로 돌아간다
즉, unsorted bin의 경우 단 한번의 재사용 기회만 주어진다.
Unsorted bin 특징
small bin과 large bin 크기의 heap chunk가 해제되면 이후 재할당을 위해 사용되는 bin
* 해당 bin은 Chunk 크기에 대한 제한이 없기 때문에 다양한 크기의 청크가 해당 Bin에 저장될 수 있다.
그러나 Fast bin에 해당하는 chunk는 Unsorted bin에 x
* 할당자는 Unsorted bin에 요청받은 메모리의 크기와 같은 chunk가 있다면 해당 chunk를 재할당한다.
* Unsorted Bin은 1개의 bin만 사용하며, doubly-linked list와 FIFO 방식
* 해당 bin을 이용해 적절한 bin을 찾는 시간이 덜 걸리므로 할당과 해제의 처리가 빠르다.
* Allocator에 의해 검색된 Chunk는 바로 재할당 되거나 아니면 원래의 Bin에 배치 된다.
코드를 통해 unsorted bin의 동작 과정을 살펴보자.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char* a=(char*)malloc(0x20);
char* a2=(char*)malloc(0x100); // small chunk
char* b=(char*)malloc(0x14);
char* b2=(char*)malloc(0x111); // small chunk
char* c=(char*)malloc(0x30);
char* c2=(char*)malloc(0x122); // small chunk
char* d=(char*)malloc(0x24);
char* e=(char*)malloc(0x22);
free(b); // insert fastbin
free(d); // insert fastbin
free(a2); // insert unsorted bin
free(b2); // insert unsorted bin
free(c2); // insert unsorted bin
char* f=(char*)malloc(0x100);
char* g=(char*)malloc(0x110);
free(g);
return 0;
}- a, b, c, d, e는 fast chunk 사이즈 요청이므로 해당 청크들은 해제시 fatstbin으로 들어갈 것이다. 그리고 a2, b2, c2는 small chunk 이므로 해제시 unsorted bin을 거쳐 small bin으로 들어갈 것이다.
- f는 a2와 동일한 사이즈인 0x100를 요청한다. 위에 free(a2)를 호출했음으로 unsorted bin에 해당 청크가 들어가 있을 것이다. 따라서 이 청크를 재사용하여 할당할 것이다.
- free(a2)가 호출되기 직전 상황부터 확인해보자.
fastbin[0]과 fastbin[1]에 해제된 b, d가 들어가 있다.
unsorted bin에 a2 가 추가되어있다.
fd, bk 가 set 된 것을 통해 unsorted bin에 a2, b2, c2가 이중연결리스트로 연결되어 있는 것을 알 수 있다. unsorted bin은 FIFO 구조이므로 이 후 malloc 요청이 들어오면, unsorted bin을 뒤져 적절한 사이즈가 존재하는지를 제일 오른쪽부터 검색할 것이다.
만일 들어온 요청 사이즈가 0x100 이면 헤더 포함 0x110이므로 한번에 찾게되고, 바로 재할당을 해준다. 하지만 들어온 요청 사이즈가 0x120이면 헤더 포함 0x130이므로 제일 왼쪽에 있는 청크를 할당해줘야 한다.
이를 위해 우측부터 검색을 시작하고, 0x110 사이즈는 탈락 , 0x120 사이즈도 탈락, 마지막 청크가 딱 맞으므로 이를 재할당할것이다. 따라서 앞서 검색을 진행했던 두개의 청크는 이 즉시 small bin으로 빠질것이다.
참고
https://wogh8732.tistory.com/180?category=699165
https://www.lazenca.net/pages/viewpage.action?pageId=51970061
dreamhack - heap allocator exploit
'Hacking > Pwnable' 카테고리의 다른 글
| [Heap exploitation] Use After Free (0) | 2021.05.11 |
|---|---|
| [Heap exploitation] Heap Overflow (0) | 2021.05.08 |
| [Pwnable] Heap2 (0) | 2021.05.05 |
| [Pwnable] Heap1 (0) | 2021.05.05 |
| [P4C] pwnable problem writeup3 (0) | 2021.04.29 |