first fit은 glibc의 메모리 할당 방법 중 하나에 속한다.
glibc의 메모리 할당 방법에는 대표적으로 3가지가 있다.
1. first fit
2. best fit
3. worst fit
그중 이 글에서 정리할 first fit은 순차적으로 할당 가능한 메모리 영역을 탐색하고,
발견하면 그 즉시 바로 할당하는 구조이다.
best fit은 External Fragmentation(외부 단편화)이 가장 적게 나는 곳에 할당하는 구조다.
worst fit은 남아 있는 공간 중 가장 큰 hole에 할당하는 구조이다.
how2heap의 first-fit은 취약점을 보여주는 것이 아닌, 할당 구조에 대해서 설명하는 코드가 있다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
fprintf(stderr, "This file doesn't demonstrate an attack, but shows the nature of glibc's allocator.\n");
fprintf(stderr, "glibc uses a first-fit algorithm to select a free chunk.\n");
fprintf(stderr, "If a chunk is free and large enough, malloc will select this chunk.\n");
fprintf(stderr, "This can be exploited in a use-after-free situation.\n");
fprintf(stderr, "Allocating 2 buffers. They can be large, don't have to be fastbin.\n");
char* a = malloc(0x512);
char* b = malloc(0x256);
char* c;
fprintf(stderr, "1st malloc(0x512): %p\n", a);
fprintf(stderr, "2nd malloc(0x256): %p\n", b);
fprintf(stderr, "we could continue mallocing here...\n");
fprintf(stderr, "now let's put a string at a that we can read later \"this is A!\"\n");
strcpy(a, "this is A!");
fprintf(stderr, "first allocation %p points to %s\n", a, a);
fprintf(stderr, "Freeing the first one...\n");
free(a);
fprintf(stderr, "We don't need to free anything again. As long as we allocate smaller than 0x512, it will end up at %p\n", a);
fprintf(stderr, "So, let's allocate 0x500 bytes\n");
c = malloc(0x500);
fprintf(stderr, "3rd malloc(0x500): %p\n", c);
fprintf(stderr, "And put a different string here, \"this is C!\"\n");
strcpy(c, "this is C!");
fprintf(stderr, "3rd allocation %p points to %s\n", c, c);
fprintf(stderr, "first allocation %p points to %s\n", a, a);
fprintf(stderr, "If we reuse the first allocation, it now holds the data from the third allocation.\n");
}하나하나 살펴보자
char* a = malloc(0x512);
char* b = malloc(0x256);
char* c;heap 영역에 a와 b 변수를 각각 0x512, 0x256만큼 chunk를 할당해준다.
strcpy(a, "this is A!");위에서 heap 영역에 할당한 a 변수에 "this is A!"라는 문자열을 넣어준다.
free(a);a를 free 해주면서 a의 주소였던 0xd1c010이 사용 가능한 주소로 bin 구조에 들어가게 된다.
glibc에서는 memory allocation과 free를 bin을 참조하면서 관리한다.
나중에 allocation request가 들어오면 bin 구조를 탐색하고 allocation이 진행된다.
bin 구조도 다양하지만 우선 이 글에 주제인 first fit에 대해서만 정리하려고 한다.
c = malloc(0x500);
c를 0x500만큼 chunk를 할당해준다.
그러면 first fit 구조이므로 아까 free 되었던 A의 주소인 0xd1c010이 c에
할당이 될 것이다.
아까 free 되었던 a의 주소랑 동일한 것을 볼 수 있다.
strcpy(c, "this is C!");
fprintf(stderr, "3rd allocation %p points to %s\n", c, c);
fprintf(stderr, "first allocation %p points to %s\n", a, a);이번에는 c에 "this is C!"라는 문자열을 넣고
c의 주소와 문자열, a의 주소와 문자열을 출력해보자.
그럼 주소와 문자열이 동일한 값을 가지게 된다.
마지막 세번째 문장을 보면 알 수 있듯이
" If we reuse the first allocation, it now holds the data from the third allocation."
만약 첫번째 allocation (A)를 재사용한다면
이것은 세번째 allocation(C)를 가지게 된다.
first fit 구조에서 알 수 있는 점은 free 한 공간보다 더 작은 공간을 다시
allocation 하려 했을 때 free 했던 공간을 사용한다는 것이다.