First Fit

Reading time: 3 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의 헤드에서 가져옵니다.

예시:

• 20바이트 크기의 청크를 네 개 할당합니다(a, b, c, d).
• 어떤 순서로 해제하든 해제된 청크는 fastbin의 헤드에 추가됩니다.
• 그 후 20바이트 청크를 요청하면, 할당자는 fastbin의 헤드에서 가장 최근에 해제된 청크를 반환합니다.

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

기타 참고자료 및 예시

• 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(<size>)에 대한 포인터를 가집니다.
• 공격은 노트 정보 크기보다 큰 malloc 내용을 가진 2개의 노트(note0 및 note1)를 생성한 다음, 이를 해제하여 빠른 빈(fast bin) 또는 tcache에 들어가게 하는 것입니다.
• 그런 다음, 내용 크기가 8인 또 다른 노트(note2)를 생성합니다. 내용은 note1에 있을 것이며, 청크가 재사용될 것이므로 함수 포인터를 win 함수로 가리키도록 수정할 수 있으며, 그 후 note1을 Use-After-Free하여 새로운 함수 포인터를 호출합니다.
• 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를 포함하고 있습니다.