First Fit

Reading time: 7 minutes

First Fit

glibc를 사용하여 프로그램에서 메모리를 해제할 때, 서로 다른 "빈"이 메모리 청크를 관리하는 데 사용됩니다. 다음은 두 가지 일반적인 시나리오에 대한 간단한 설명입니다: 정렬되지 않은 빈과 패스트 빈.

Unsorted Bins

패스트 청크가 아닌 메모리 청크를 해제하면, 그것은 정렬되지 않은 빈으로 이동합니다. 이 빈은 새로 해제된 청크가 앞쪽(“헤드”)에 추가되는 목록처럼 작동합니다. 새로운 메모리 청크를 요청할 때, 할당자는 정렬되지 않은 빈의 뒤쪽(“테일”)에서 충분히 큰 청크를 찾습니다. 정렬되지 않은 빈의 청크가 필요한 것보다 크면, 그것은 분할되어 앞부분이 반환되고 나머지 부분은 빈에 남아 있습니다.

예시:

• 300 바이트(a)를 할당한 다음, 250 바이트(b)를 할당하고, a를 해제한 후 다시 250 바이트(c)를 요청합니다.
• a를 해제하면, 그것은 정렬되지 않은 빈으로 이동합니다.
• 그 후 다시 250 바이트를 요청하면, 할당자는 테일에서 a를 찾아 분할하고, 요청에 맞는 부분을 반환하며 나머지는 빈에 남깁니다.
• c는 이전의 a를 가리키며 a의 내용으로 채워집니다.

char *a = malloc(300);
char *b = malloc(250);
free(a);
char *c = malloc(250);

Fastbins

Fastbins은 작은 메모리 청크에 사용됩니다. 정렬되지 않은 빈과 달리, fastbins은 새로운 청크를 머리에 추가하여 후입선출(LIFO) 동작을 생성합니다. 작은 메모리 청크를 요청하면, 할당자는 fastbin의 머리에서 가져옵니다.

Example:

char *a = malloc(20);
char *b = malloc(20);
char *c = malloc(20);
char *d = malloc(20);
free(a);
free(b);
free(c);
free(d);
a = malloc(20);   // d
b = malloc(20);   // c
c = malloc(20);   // b
d = malloc(20);   // a

🔥 현대 glibc 고려사항 (tcache ≥ 2.26)

glibc 2.26부터 각 스레드는 tcache를 유지하며, 이는 정렬되지 않은 빈 앞에서 쿼리됩니다. 따라서 첫 번째 적합 시나리오는 다음과 같은 경우에만 도달할 수 있습니다:

1. 요청된 크기가 tcache_max (기본적으로 64비트에서 0x420)보다 커야 하며, 또는
2. 해당 tcache 빈이 이미 가득 차 있거나 수동으로 비워졌을 때 (7개의 요소를 할당하고 사용 중으로 유지).

실제 익스플로잇에서는 일반적으로 다음과 같은 도우미 루틴을 추가합니다:

// Drain the tcache for a given size
for(int i = 0; i < 7; i++) pool[i] = malloc(0x100);
for(int i = 0; i < 7; i++) free(pool[i]);

tcache가 소진되면, 이후의 free는 unsorted bin으로 가고 고전적인 first-fit 동작(꼬리 검색, 머리 삽입)이 다시 발생할 수 있습니다.

🚩 first-fit을 이용한 겹치는 청크 UAF 만들기

아래의 조각(테스트는 glibc 2.38에서 수행됨)은 unsorted bin의 분할기를 악용하여 2개의 겹치는 포인터를 생성하는 방법을 보여줍니다. 이는 단일 free를 write-after-free로 변환하는 강력한 원시 기능입니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
setbuf(stdout, NULL);

/* 1. prepare 2 adjacent chunks and free the first one */
char *A = malloc(0x420);   // big enough to bypass tcache
char *B = malloc(0x420);
strcpy(A, "AAAA\n");
free(A);                   // A → unsorted

/* 2. request a *smaller* size to force a split of A */
char *C = malloc(0x400);   // returns lower half of former A

/* 3. The remainder of A is still in the unsorted bin.
Another 0x400-byte malloc will now return the *same*
region pointed to by B – creating a UAF/overlap. */
char *C2 = malloc(0x400);

printf("B  = %p\nC2 = %p (overlaps B)\n", B, C2);

// Arbitrary write in B is immediately visible via C2
memset(B, 'X', 0x10);
fwrite(C2, 1, 0x10, stdout);  // prints Xs
}

Exploitation recipe (common in recent CTFs):

1. 대상 크기에 대한 tcache를 비우기.
2. 청크를 해제하여 정렬되지 않은 빈에 배치하기.
3. 조금 더 작은 크기를 할당하기 – 할당자는 정렬되지 않은 청크를 분할합니다.
4. 다시 할당하기 – 남은 부분이 기존 사용 중인 청크와 겹침 → UAF.
5. 민감한 필드(함수 포인터, FILE vtable 등)를 덮어쓰기.

실용적인 응용 프로그램은 2024 HITCON Quals Setjmp 챌린지에서 이 정확한 프리미티브가 UAF에서 __free_hook의 전체 제어로 피벗하는 데 사용되는 것을 찾을 수 있습니다.

🛡️ 완화 및 강화

• **안전한 링크(glibc ≥ 2.32)**는 단일 연결된 tcache/fastbin 목록만 보호합니다. 정렬되지 않은/작은/큰 빈은 여전히 원시 포인터를 저장하므로, 힙 누수를 얻을 수 있다면 첫 번째 적합 기반의 겹침이 여전히 유효합니다.
• 힙 포인터 암호화 및 MTE (ARM64)는 아직 x86-64 glibc에 영향을 미치지 않지만, GLIBC_TUNABLES=glibc.malloc.check=3와 같은 배포 강화 플래그는 일관성 없는 메타데이터에서 중단되며 단순한 PoC를 깨뜨릴 수 있습니다.
• 해제 시 tcache 채우기 (2024년 glibc 2.41에 제안됨)는 정렬되지 않은 사용을 더욱 줄일 것입니다; 일반적인 익스플로잇을 개발할 때 향후 릴리스를 모니터링하세요.

기타 참조 및 예시

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Use after free: 사용자 객체를 생성하고, 해제한 후, 해제된 청크를 가져오는 객체를 생성하여 그에 쓸 수 있게 하여, 이전의 user->password 위치를 덮어쓰기. 사용자를 재사용하여 비밀번호 확인을 우회하기
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• 프로그램은 노트를 생성할 수 있습니다. 노트는 malloc(8)에서 노트 정보를 가지고 있으며(호출할 수 있는 함수에 대한 포인터 포함) 다른 malloc()에 노트의 내용을 가리키는 포인터를 가집니다.
• 공격은 노트 정보 크기보다 더 큰 malloc 내용을 가진 2개의 노트(note0 및 note1)를 생성한 다음, 이를 해제하여 빠른 빈(또는 tcache)으로 들어가게 하는 것입니다.
• 그런 다음, 내용 크기가 8인 또 다른 노트(note2)를 생성합니다. 내용은 note1에 있을 것이며, 청크가 재사용되므로 함수 포인터를 win 함수로 가리키도록 수정할 수 있고, 그런 다음 Use-After-Free를 통해 note1을 호출하여 새로운 함수 포인터를 사용할 수 있습니다.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• 메모리를 할당하고 원하는 값을 쓰고, 해제한 후, 재할당할 수 있으며, 이전 데이터가 여전히 존재하므로 청크의 새로운 예상 구조에 따라 처리되어 값을 설정하거나 플래그를 얻을 수 있습니다.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• 이 경우 특정 청크에 4를 써야 하며, 이는 할당된 첫 번째 청크입니다(모든 청크를 강제로 해제한 후에도). 각 새로 할당된 청크의 배열 인덱스 번호가 저장됩니다. 그런 다음 4개의 청크(+ 처음 할당된 청크)를 할당하고, 마지막 청크에는 4가 들어 있으며, 이를 해제하고 첫 번째 청크의 재할당을 강제로 하여 마지막으로 해제된 청크를 사용하게 됩니다. 이 청크에는 4가 들어 있습니다.
• 2024 HITCON Quals Setjmp write-up (Quarkslab) – 실용적인 first-fit / 정렬되지 않은 분할 겹침 공격: https://ctftime.org/writeup/39355
• Angstrom CTF 2024 heapify write-up – 정렬되지 않은 빈 분할을 악용하여 libc를 누출하고 겹침을 얻기: https://hackmd.io/@aneii11/H1S2snV40