Heap 시리즈
[Heap] Background : Memory Allocator
[Heap] Background : Bin (Fastbin, Unsorted bin, Small bin, Large bin)
[Heap] Memory Corruption : Use After Free(UAF) (1)
Bin
bin은 free chunk들을 저장하는 freelist이다. freelist는 간단히 free된 청크들의 리스트라고 생각하면된다.
청크가 해제되면 Free chunk가 되어 tcache나 bin에 들어간다. 그리고 새로운 청크를 할당할 때 메모리를 새로 할당하는 것이 아니라 bin이나 tcache에서 꺼내 쓴다. (참고로 할당할 청크의 크기가 일정 크기 이상이면 메모리를 새로 할당하긴 한다.) tcache는 다음에 살펴보도록 하고 오늘은 bin에 대해서만 살펴보도록 하겠다.
주의) Top Chunk는 어느 bin에도 들어가지 않는다!
ptmalloc에는 위처럼 128개의 bin이 정의되어있다.
- 0,127번째 인덱스는 사용 x
- 1번째 인덱스는 unsorted bin
- 2~63 (62개) 인덱스는 small bin
- 64~127(63) 인덱스는 large bin
그리고 fastbin이라는 것이 또 있는데 이렇게 fastbin, unsortedbin, small bin, large bin 4개의 bin으로 bin이 구성된다.
bin은 아래와 같은 malloc_state라는 구조체에 의해 관리된다.
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들은 mchunkptr bins에 정의되어있다.
그리고 fastbin들은 fastbinsY라는 배열에 의해 관리된다.
한편 청크들은 사이즈에 따라 아래처럼 구분할 수 있다.
이렇게 구분된 청크들은 크기에 따라 알맞은 bin에 저장된다.
각 bin들에 대해서는 아래에서 살펴보도록 하고 지금부터는 청크들이 병합하는 것에 대해 알아보도록 하겠다. 위 표에서 일단 기억하고 넘어갈 것은 Fast bin(tcache도!)은 병합을 하지않고 나머지 bin들은 병합이 된다. (Unsorted bin도 병합된다고 함!!! 헷갈렸는데 ㅎㅎ)
병합
해제된 청크들이 물리적으로!! 연달아 붙어있으면 이 청크들은 하나로 병합하여 큰 Free Chunk가 된다. (참고로 fastbin과 tcacache에서는 병합 x)
다음 청크와 병합하는 경우 : 다음 청크의 해제여부 필요 -> 다음다음 청크의 P비트 확인
A가 해제할 때는 B의 해제 여부만 확인하면 되므로, C의 P 플래그(prev_inuse 비트)를 확인하게된다.
이런 경우 A주소에서 A size + B size로해서 C에 접근할 수 있다. 이처럼 사이즈를 통해 이전, 이후 청크에 접근한다는 점을 기억하자.
아래와 같이 병합된다.
이전 청크와 병합하는 경우 : 이전 청크의 해제여부 필요 -> 현재 청크의 P 비트 확인
이런 경우 A의 해제 여부만 확인하면 되고, 그 정보는 자신의 Prev_inuse 비트에 적혀있기 때문에 그것만 보면 된다.
(사실 완전 자세하게 보면 조금 더 확인하는데 여기에서는 간단히만 보고 넘어가겠다. 병합에 관한 내용은 unlink 포스트에서 다룬다.)
병합에 대해서 읽어보면 좋을만한 글 -> https://infosecwriteups.com/the-toddlers-introduction-to-heap-exploitation-fastbin-dup-consolidate-part-4-2-ce6d68136aa8
참고로 주의해야할 상황을 보자. 예를 들어 물리적으로 인접해있는 2 청크가 있고 하나는 fastbin, 하나는 unsorted bin에 있으면 둘은 병합되지 않는다. 왜냐하면 fastbin은 원래 병합을 안하기 때문이다. 이처럼 어떤 bin에 청크가 들어있는지도 병합할 때 고려사항이 된다.
이와 같은 특별한? 병합 상황들은 저 아래에서 다룬다.
Fastbin
- 사이즈 작은 청크들을 보관하기 위해서 사용됨
- LIFO (Stack) 구조 사용 -> 속도 빠름
- 병합 x (왜냐하면 용도 자체가 사이즈 작은 청크들 보관하는 거여서 굳이 병합 x)
- 따라서 해제되어도 prev_inuse bit를 변화시키지 않는다.
- 단일 연결리스트 사용
- 따라서 fd만 사용하고 bk는 사용 x
- 따라서 unlink 과정도 필요 없음
- 10개 bin 사용 (64bit에서는 7개만 사용한다고 함)
- 32byte이상 128byte이하의 청크들 저장
- 정확히 말해서는 fast bin의 메모리의 최대 크기는 "global_max_fast" 에 의해서 결정됨
- malloc_state 구조체의 fastbinsY 배열에 의해 관리되는 듯
LIFO 배열이고 아래처럼 연결된다!! 오른쪽이 가장 old한 원소이고 0x4567의 fd는 0x1234 (아마 오른쪽 꺼 가리키는게 fd같다..)
실습
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char* tcache_temp[7]={};
/*
조그만 청크들은 해제되면 tcache에 먼저 저장되기 때문에 일단
7개의 청크를 tcache에 담을 것이다. 이후 애들은 해제되면 fastbin에 저장된다
*/
for(int i=0; i<7; i++){
tcache_temp[i]=(char*)malloc(0x20);
} //이해 안가면 그냥 밑에서부터 봐도 된다
char* a=(char*)malloc(0x20);
char* b=(char*)malloc(0x20);
char* b2=(char*)malloc(0x20);
char* c=(char*)malloc(0x20);
char* d=(char*)malloc(0x20);
char* d2=(char*)malloc(0x20);
char* e=(char*)malloc(0x20);
char* f=(char*)malloc(0x20);
char* g=(char*)malloc(0x20);
for(int i=0; i<7; i++){
free(tcache_temp[i]);
}
free(a);
free(b);
free(b2);
free(c);
free(d);
free(d2);
free(e);
free(f);
free(g);
return 0;
}
우리는 fastbin을 보고 싶은데, 조그만 청크들은 먼저 tcache에 저장된다. 그래서 일단 tcache에 7개 담고 나머지 청크(a,b,..g)들을 관찰하자. tcache에 대해서는 다른 포스트에서 다룰 것이다.
for(int i=0; i<7; i++){
free(tcache_temp[i]);
}
위 코드 뒤에 브레이크 포인트를 걸어줬다.
7개의 청크들이 tcache에 저장된 것을 볼 수있다.
우리는 위 사진에서 11번째 청크(Freed 다음에 처음으로 Used인 청크)부터 보면된다.
사이즈가 0x20이 아니라 0x30인 이유는 헤더가 추가되어서 그렇다.
다시 모든 청크를 free하고 브레이크 포인트를 걸어주었다!
역시 fastbin에 9개의 청크들이 저장된 것을 확인할 수 있었다.
또한 맨처음에 free한 a청크(0x5555555593e0)의 fd는 0x0으로 세팅되어있는 것을 볼 수 있다.
참고로 우리는 chunk의 크기를 다 같게 해주었지만, 만약 크기를 다르게 할당했다면 아래 그림처럼 fastbin에 저장된다.
fastbin의 한 인덱스에 청크는 아래처럼 추가된다. (fd 연결)
또한 p main_arena를 통해 main_arena의 정보를 출력해보았다. main arena는 brk로 할당된 청크들을 관리해주는 구조체다.
fastbinsY에 fastbin[1]의 첫번째 주소가 적혀있는 것을 확인할 수 있었다.
또한 살펴봐야할 것은 fastbin에서는 병합을 하지 않는다는 점이다.
아래에 free된 청크들을 출력해보았다.
free되었음에도 size의 Prev_inuse bit가 1로 설정되어있는 것을 볼 수 있다. (size가 1로 끝나고 있음) 이렇기 때문에 병합을 하지 않을 수 있는 것이다(?)
fastbin에 해제된 청크가 들어가는 과정 (즉 fastbin크기의 청크가 해제되는 과정)
if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())청크가 해제될 때 해당 청크가 fastbin 크기의 범위에 속해 있다면 위 조건문을 통과한다.
fb = &fastbin (av, idx);이후 현재 청크에 해당하는 청크의 리스트를 가져온다.
p->fd = old2 = old;만약 해당 리스트에 이미 원소가 존재한다면, 넣을 청크의 fd를 그 리스트안에 있는 청크의 주소로 연결한다. 이로써 해제된 청크가 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;
}
}
Unsorted Bin
fastbin 크기에 해당하는 청크들은 unsorted bin에 할당되지 않음
(참고로 fastbin 크기보다는 크지만 unsorted bin에 들어있는 청크 크기보다 작다면 그냥 unsorted bin 안의 chunk를 할당해주는 것 같다.)
smallbin 크기에 해당하는 청크를 할당 요청하면, ptmalloc은 fastbin 또는 smallbin을 탐색한 뒤 unsortedbin을 탐색함.
largebin의 크기에 해당하는 청크는 unsortedbin을 먼저 탐색함. unsortedbin에서 적절한 청크가 발견되면 해당 청크를 꺼내어 사용함. 이 과정에서, 탐색된 청크들은 크기에 따라 적절한 bin으로 분류함
- bin의 1번째 인덱스로(0번째 아님) 쓰임! 그리고 단 하나의 bin만을 사용
- unsorted bin은 마치 캐시처럼 작용함. fastbin 사이즈가 아닌 애들은 일단 해제되면 unsorted bin에 저장된다!
- small, large chunk 저장
- 크기 제한이 없어서 다양한 크기의 청크가 저장될 수 있음
- FIFO (Queue)
- (원형)이중 연결리스트 사용
- 내부적으로 정렬 x
- NON_MAIN_ARENA 플래그를 절대 세팅하지 않음
- 한번의 탐색으로 청크에게 일어날 수 있는 결과는 재할당 or 원래 빈으로 재배치되기이다. (밑에서 자세히 설명 예정)
- 익스플로잇 관점 : 청크가 처음 unsorted bin에 들어가게 될때 main arena의 특정 주소와 이중 연결리스트를 이루게 되어 fd,bk에 main arena의 주소가 쓰이게 됨 -> 라이브러리 릭 가능
실습
#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);
free(g);
char* e=(char*)malloc(0x130);
return 0;
}
free(d)뒤에 breakpoint 걸어주었다.
(내 칼리가 넘 최신버전을 쓰는건지 fastbin말고 tcache만 죽어라 써서,,, 사진은 어쩔 수 없이 다른 블로그 꺼를 참고했다)
청크 b,d는 모두 fastbin에 들어가는 사이즈이므로 unsortedbin이 아니라 fastbin에 들어간 것을 볼 수 있다.
free(c2) 까지 하고 bp 걸어주었다.
청크 a2,b2,c2는 small chunk에 해당하는 청크이므로 free되었을 때 unsorted bin으로 들어갔다.
이처럼 fastbin을 제외한 크기의 청크들은 대부분 unsorted bin으로 먼저 들어간다. 한편 unsorted bin에서는 크기 또한 정렬되지 않는다!
이제 (char*)malloc(0x100); 후에 bp를 걸어줄 것이다. smallbin크기이지만 smallbin이 비어있으므로 unsorted bin을 찾을 것을 추측할 수 있다. 또한 0x100만큼의 요청을 하는데 헤더까지 추가될 것이니까 총 0x110 사이즈의 청크가 할당될 것이다. 그래서 unsorted bin에서 맨 오른쪽의 0x110짜리(0x602030)가 재할당될 것이다.
unsortedbin에서 맨 오른 쪽에 있었던 0x110짜리 청크가 이중 연결 리스트에서 빠진 것을 볼 수 있다. 또한 parseheap 출력화면에서 해당 청크(0x602030)의 status가 Freed에서 Used로 바뀐 것 또한 확인할 수 있었다.
이제 char* e=(char*)malloc(0x130); 뒤에 bp를 걸어줄 것이다.
unsortedbin에 있는 청크들이 빠지고 smallbin에 들어간 것을 확인할 수 있다!! 그 이유를 살펴보자.
unsortedbin은 오른쪽부터 탐색하므로(FIFO) 0x120짜리보고 안되니까 0x130짜리도 볼것이다. 그런데
0x130를 요청했으니까 실제 청크 사이즈는 0x140 이상을 할당해야한다. 그런데 그런 애가 unsortedbin에 없으므로 둘다 탈락된다. 이 탈락된 애들은 원래 자기가 있어야할 빈, 여기서는 smallbin에 재배치되게 된다.
이처럼 한번이라도 탐색된 청크들은 재할당되거나 아니면 바로 자기 사이즈에 맞는 bin으로 들어가게된다.
상황 1
여기서 헷갈릴 만한 상황을 가정해보자.
아래처럼 물리적으로 free chunk가 붙어있는데, 하나는 unsorted bin에 들어있고 하나는 fastbin에 들어가 있으면 어떻게 될까? 왜냐하면 unsorted는 병합을 진행하지만 fastbin은 병합을 안하니까 말이다.
일단 0x20짜리 청크가 해제되어 fast bin에 들어가면 free되었음에도 불구하고 0x20청크 뒤 청크에 prev_inuse를 0으로 설정하지 않는다. 하지만 0x100짜리 청크는 자기 자신의 다음 청크(0x20짜리)의 prev_inuse를 0으로 세팅한다.
하지만 0x100짜리가 병합을 하고 싶어 0x20뒤 청크의 prev_inuse를 확인해도 1로 되어있기 때문에 병합이 일어나지 않는다.
(이처럼 fastbin 안의 청크들은 free되어도 뒤 청크의 prev_inuse bit을 변화하지 않기 때문에 병합되지 않는 것을 확인할 수 있다)
상황 2
한 가지 코드만 더 보고 small bin으로 넘어가자.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void){
char *a = (char *)malloc(0x110);
char *temp = (char *)malloc(0x20);
free(a); //insert into unsorted bin
char *b = (char *)malloc(0x80);
return 0;
}free(a)에 breakpoint를 걸어주었다.
unsorted bin에 0x120짜리 청크가 있는 것을 확인할 수 있다.
그리고 이제 0x90짜리 청크를 할당하고 싶다. 그러면 어떻게 될까?
헤더 포함 0x90만큼의 chunk를 할당하였을때, unsorted bin에 있던 0x120의 chunk에서 0x90만큼 재할당해주고 남은 0x90은 last_reminder에 들어가게 된다.
Small Bin
결론적으로 말하자면 1024byte 아래 청크들은 다 smallbin으로 분류가 된다.
물론 fastbin안에 있는 청크들도 smallbin 범위 안에 포함된다. fastbin 인덱스 리스트 안에 연결된 청크 개수가 10개가 넘어가면 smallbin으로 넘어가게 된다.
sz< MIN_LARGE_SIZE이면 smallbin으로 분류가 된다.
아무튼 청크의 최소 사이즈 0x20~0x400 미만 까지는 smallbin으로 들어간다. (그런데 맨처음에는 unsorted bin들어갔다가 뒤에 재할당되거나 다시 smallbin으로 들어가는거지 ㅇㅇ)
- FIFO (Queue)
- 0x20~0x400미만까지의 청크 저장
- 이중연결리스트 사용
- 청크 빼내거나 삽입할 때 청크 연결 끊는 과정 필요 -> 이를 unlink 라고 함
- 62개의 bin 사용
- 하나의 인덱스에는 같은 크기만 들어감!! 그리고 인덱스가 1 커질때마다 저장되는 청크 크기는 16byte만큼 커짐
- 즉 smallbin[0] 에는 32byte 청크들의 리스트가, ......smallbin[61]에는 1008byte 청크들의 리스트가 저장되는 것
- 서로 인접한 경우 PREV_INUSE bit가 clear되므로 free할 때 인접한 free small chunk와 병합
- 하지만!! 같은 free small chunk가 아닌 fast,unsorted, in-use chunk와 인접해있는 경우는 경우는 병합하지 않음
실습
#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;
}
Large Bin
- 0x400 이상의 청크 저장
- 메모리 할당과 반환의 속도가 fastbin, unsorted bin, small bin 중에서 가장 느림
- bin의 개수는 63개
- 이중연결리스트 (-> unlink 필요!)
- 각 bin에 들어있는 청크들의 크기가 동일하지 않고 일정 범위 안의 청크가 한 리스트에 다 저장됨
- 이 범위는 largebin의 인덱스가 증가하면 로그적으로 증가함!! 예를 들어, largebin[0]는 1024 바이트 이상, 1088 바이트 미만의 청크를 보관하며, largebin[32]는 3072 바이트 이상, 3584 바이트 미만의 청크를 보관함. 이런 방법을 사용하면 적은 수의 largebin으로 다양한 크기를 갖는 청크들을 관리할 수 있음
- 범위 안에 있는 다른 크기들의 청크를 다 저장하기 때문에 bin 안에 있는 청크들을 '내림차순'으로 정렬
- 같은 사이즈의 청크들끼리는 fd_nextsize, bk_nextsize를 사용하지 x
위 그림을 보면 크기가 8192인 청크들끼리는 서로 fd_nextsize, bk_nextsize를 설정하지 않은 것을 확인할 수 있다!
#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;
}
- 현재 largebin[0]에 0x400부터 0x430 까지의 사이즈를 가진 청크가 들어가 있다. 또한 정렬이 되어 맨 왼쪽이 가장 큰 사이즈를 갖는다.
- larebin[0] 의 각 청크들은 모두 사이즈가 다르므로 fd,bk와 fd_nextsize,bk_nextsize 모두 동일할 것이다.
- 해당 크기의 청크는 bin에 속하지 않는다
- 이러한 청크들은 IS_MMAPPED 플래그가 설정됨
- 해당 영역이 Free될 경우 munmap()을 호출해 해당 메모리 영역을 해지함
정리
References
https://learn.dreamhack.io/98
Heap 기초3 (oopy.io)
ptmalloc free & bin — Ro_ll_ing (tistory.com) https://rninche01.tistory.com/m/entry/heap4-glibc-malloc3-feat-bin?category=838537
https://learn.dreamhack.io/16
F/OSS study (zum.com)
'Linux Exploitation > Heap' 카테고리의 다른 글
| [Heap] Exploitation : Double Free Bug (0) | 2023.06.15 |
|---|---|
| [Heap] Exploitation : Unsorted Bin Memory Leak (0) | 2023.06.11 |
| [Heap] Background : Chunk (3) | 2023.06.07 |
| [Heap] Memory Corruption : Use After Free(UAF) (0) | 2023.05.30 |
| [Heap] Background : Memory Allocator (0) | 2023.05.18 |
