tmxklab
heap(4) - glibc malloc(3) (feat. bin) 본문
참고 : GNU C Library의 Memory Allocator인 ptmalloc2(glibc 2.23)를 대상으로 설명
이번에는 Free된 Chunk들을 다시 재활용하기 위해서 Free Chunk들을 어떻게 관리하는지 자세하게 다뤄보겠다.
0. Boundary Tag
이전 시간에 Memory Allocator소개 부분 또는 Free Chunk구조에서 잠깐 Boundary Tag가 나온 것을 보았을 것이다.
그리고 여러 개의 청크들이 생성되었을 경우 메모리에 연속적으로 위치하는 것을 보았을 것이다.
이번에는 Boundary Tag를 통해 어떻게 인접한 앞/뒤 Chunk의 주소가 계산 가능한지 알아보도록 하겠다.(fastbin은 예외)
-
위와 같이 p1, p2, p3에 각각 malloc을 하고 p2를 free했을 경우 p2의 Chunk는 파란색 박스와 같이 포함된다.
-
각각 0x300, 0x400, 0x300의 malloc요청을 했는데 size값이 0x10을 더하는 이유는 헤더의 크기가 0x10이기 때문이다. (Chunk = Header + Data)
-
Boundary Tag가 없을 경우 p1에서 p2가 free된 것을 알 수는 있지만 p3에서 p2가 free된 것을 알 수 없을 것이다. (0x602000(p1) + 0x310 = 0x6023100)
-
하지만 Boundary Tag가 존재함으로써 역으로 즉, p3에서 p2가 free된 것을 알 수 있다. (0x602720 - 0x410 = 0x602310)
-
(추가로 그림에는 없지만 p3에서 인접한 이전 청크가 사용되는지 안되는지 확인할 수 있는 PREV_INUSE비트가 0으로 세팅될 것이다.)
이렇게 Boundary Tag를 사용함으로써 Chunk의 앞, 뒤에 크기 정보를 전달할 수 있어 이후에 Free되었을 경우 인접한 Free Chunk끼리 빠르게 합쳐질 수 있다.
1. Bin
지금까지 메모리 할당 또는 해제하였을 경우 각각의 구조 또는 힙이 어떻게 변화하는지 보았다. 프로그램에서는 메모리 할당 또는 해제가 빈번하게 발생하는데 Free(해제)된 Chunk들은 이후에 메모리 할당 요청이 들어올 경우 다시 재활용되어야 하기 때문에 관리되어야 한다. (물론, Free된 Chunk가 없으면 힙 맨 끝에서 새로운 Chunk가 생성됨)
단순하게 모든 Chunk들을 Linked List로 관리하면 편할수 있지만 이는 malloc할 경우 Free된 Chunk를 찾기 위해 모든 Chunk를 탐색해야하며 속도저하를 일으켜 프로그램의 전체 성능에 큰 영향을 미칠 것이다.
따라서, 성능 향상을 위해 "bins"라는 개념을 도입하여 Free된 Chunk들만 관리한다.
1.1 Bin이란?
-
Free List Data Structures이며 재사용 가능한 즉, Free Chunk들을 크기 단위로 관리(binning)하는 역할을 한다.
-
binnig을 통해 관리되는 Chunk를 bin이라 부르며 Allocator에서 메모리 할당 요청시 적합한 Chunk(Fragmentation때문에)를 신속하게 재할당하는 역할을 한다.
-
bin은 크기에 따라 4가지의 유형의 bin으로 나뉨(주의 : tcache bin(64개)은 glibc 2.26이후로 나옴)
1.2 bin의 종류
bin에 대한 정보는 malloc_state구조체(Arena의 Header)에서 확인할 수 있다.
struct malloc_state
{
/* Serialize access. */
mutex_t mutex;
/* Flags (formerly in max_fast). */
int flags;
/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;
/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];
/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];
/* Linked list */
struct malloc_state *next;
/* Linked list for free arenas. Access to this field is serialized
by free_list_lock in arena.c. */
struct malloc_state *next_free;
/* Number of threads attached to this arena. 0 if the arena is on
the free list. Access to this field is serialized by
free_list_lock in arena.c. */
INTERNAL_SIZE_T attached_threads;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};-
fastbinY[NFASTBINS] : fast bin을 관리하는 배열(10개)
-
bins[NBINS * 2 - 2] : unsorted bin, small bin, large bin을 관리하는 배열
-
bin[0] : N/A(사용되지 않음), 특수한 목적에 사용
-
bin[1] : unsorted bin(1개)
-
bin[2] ~ bin[63] : small bin(62개)
-
bin[64] ~ bin[126] : large bin(63개)
-
2. Bin의 종류(small bin, large bin, fast bin, unsorted bin)
2.1 small bin
1) small bin
chunk크기가 MIN_LARGE_SIZE보다 작은 chunk들을 포함하는 62개의 small bin이 존재하며 한 가지 크기의 chunk만 저장되기 때문에 자동으로 정렬이 되어 삽입 및 제거하는 것이 빠르다.
2) small bin 특징
-
FIFO(First In First Out)를 사용하며 double-liked list로 관리
-
먼저 해제된 청크가 먼저 재할당
-
-
서로 다른 크기의 62개의 small bin 존재
-
chunk 크기가 MIN_LARGE_SIZE보다 작은 chunk들을 관리
-
32bit system : MIN_LARGE_SIZE = 512 byte
-
64bit system : MIN_LARGE_SIZE = 1024 byte
-
chunk 크기의 범위는 0x20 ~ 0x400까지이며 0x20부터 0x80까지 fast bin과 겹침(0x400보다 미만임)
-
-
-
small bin에 포함되는 chunk들은 인접하게 배치되지 않음
-
서로 인접한 경우 PREV_INUSE bit가 clear되므로 free할 때 인접한 free chunk와 병합
-
3) Example
-
참고 : ubuntu 64bit system
3-1) [ small_1.c ]
#include<stdio.h>
#include<stdlib.h>
#define INDEX 5
int main(){
char *small_p[INDEX];
char *large_p;
char *dummy_p[INDEX];
char *malloc_p[INDEX];
int i;
// Minimum small bin
// smallbin[0] : (fast bin -> small bin)
// size : 0x20(32)bytes
small_p[0] = (char*)malloc(0x10);
dummy_p[0] = (char*)malloc(0x600);
free(small_p[0]);
malloc_p[0] = (char*)malloc(0x500);
// Maximum small bin
// smallbin[61] : (unsorted bin -> smal bin)
// size : 0x3f0(1,008)bytes
small_p[1] = (char*)malloc(0x3e0);
dummy_p[1] = (char*)malloc(0x600);
free(small_p[1]);
malloc_p[1] = (char*)malloc(0x500);
// large bin
large_p = (char*)malloc(0x3f0);
dummy_p[2] = (char*)malloc(0x600);
free(large_p);
malloc_p[2] = (char*)malloc(0x500);
puts("exit!!");
free(dummy_p[0]);
free(dummy_p[1]);
free(dummy_p[2]);
free(malloc_p[0]);
free(malloc_p[1]);
free(malloc_p[2]);
return 0;
}
Debugging [ small_1 ]
[ small_p[0] → free() 직후 ]
-
free된 chunk가 fast bin에 먼저 삽입
[ malloc_p[0] → malloc() 직후 ]
-
free된 chunk보다 더 큰 사이즈의 메모리 할당 요청할 경우 small bin으로 이동(fast bin[0] → small bin[0])
-
small bin이 가질 수 있는 최소 청크의 크기이며 헤더 사이즈까지 포함하여 0x20
[ small_p[1] → free() 직후 ]
-
free된 chunk가 unsorted bin에 먼저 삽입 → 뒤에 unsorted bin에서 설명할 예정
[ malloc_p[1] → malloc() 직후 ]
-
free된 chunk보다 더 큰 사이즈의 메모리 할당 요청할 경우 small bin으로 이동(unsorted bin → small bin[61])
-
small bin이 가질 수 있는 최대 청크의 크기이며 헤더 사이즈까지 포함하여 0x3f0
[ large_p → free() 직후 ]
-
free된 chunk가 unsorted bin에 먼저 삽입
[ malloc_p[2] → malloc() 직후 ]
-
free된 chunk보다 더 큰 사이즈의 메모리 할당 요청할 경우 large bin으로 이동(unsorted bin → large bin[0])
-
small bin[61]보다 0x10더 큰 chunk를 free하고 메모리 할당 요청할 경우 large bin으로 이동
3-2) [ small_2.c ]
#include<stdio.h>
#include<stdlib.h>
#define INDEX 3
int main(){
char *small_p[INDEX];
char *dummy_p[INDEX];
char *malloc_p[INDEX];
char *fifo_p[INDEX];
int i;
// Creation small bin (Double linked list)
for(i=0;i<INDEX;i++){
small_p[i] = (char*)malloc(0x200);
dummy_p[i] = (char*)malloc(0x500);
}
for(i=0;i<INDEX;i++){
free(small_p[i]);
malloc_p[i] = (char*)malloc(0x500);
}
puts("Creation small bin!!");
// Check FIFO
for(i=0;i<INDEX;i++){
fifo_p[i] = (char*)malloc(0x200);
}
puts("All free");
for(i=0;i<INDEX;i++){
free(dummy_p[i]);
free(malloc_p[i]);
free(fifo_p[i]);
}
return 0;
}
Debugging [ small_2 ]
[ 첫 번째 puts() 직전 → small bin 생성 ]
-
smallbin[31]에 존재하는 Free Chunk들이 fd와 bk가 세팅 → double linked list
[ fifo_p[0] → malloc(0x200) 직후 ]
-
small bin에 존재하는 Chunk의 크기에 맞게 메모리 할당 요청한 후의 모습
-
제일 먼저 Free된 0x602000위치의 Free Chunk를 메모리 할당시 사용
-
하지만, 0x602000위치의 Free Chunk에는 아직 fd와 bk가 존재
-
나머지 small bin에 존재하는 2개의 청크에 fd와 bk가 바뀐 것을 확인
[ fifo_p[1] → malloc(0x200) 직후 ]
-
두 번째로 Free된 0x602720위치의 Free Chunk를 메모리 할당시 사용
[ fifo_p[2] → malloc(0x200) 직후 ]
-
마지막으로 Free된 0x602e40위치의 Free Chunk를 메모리 할당시 사용
2.2 large bin
1) large bin
small bin과 같은 방식으로 동작하지만 small bin과 fast bin처럼 정해진 크기 단위로 관리하는 것이 아니라 특정 범위 단위에 따라 관리하기 때문에 다양한 크기를 저장하게 된다. 이로 인해 삽입에 대한 정렬이 수동으로 이루어지기 때문에 메모리 할당 또는 반환 속도가 가장 느리다. (하지만, 대부분 프로그램에서 자주 사용하지 않는다.)
2) large bin 특징
-
FIFO(First In First Out)를 사용하며 double-liked list로 관리
-
63개의 bin을 사용하며 특정 범위 단위로 관리
-
하나의 bin에 다양한 크기의 chunk들을 보관
-
bin내에서 크기 별로 정렬되어 할당의 효율성 향상
-
-
범위 내 가장 큰 size의 chunk가 제일 앞에 오도록 정렬
-
chunk의 크기가 MIN_LARGE_SIZE와 같거나 큰 chunk들을 관리
-
32bit system : 512 byte 보다 같거나 큰 청크
-
64bit system : 1024 byte 보다 같거나 큰 청크
-
-
large bin에 포함되는 chunk들은 서로 인접한 경우 PREV_INUSE bit가 clear되어 병합됨
+) bin의 개수 및 범위
-
Chunk의 크기는 0x400(512)bytes 이상부터 시작하며 범위는 다음과 같다.
-
largebin[0] ~ largebin[31] (32개) : 0x40(64) bytes씩 증가
-
largebin[32] ~ largebin[47] (16개) : 0x200(512) bytes씩 증가
-
largebin[48] ~ largebin[55] (8개) : 0x1000(4,096) bytes씩 증가
-
largebin[56] ~ largebin[59] (4개) : 0x8000(32,768) bytes씩 증가
-
largebin[60] ~ largebin[61] (2개) : 0x40000(262,144) bytes씩 증가
-
largebin[61] (1개) : 이외의 남은 크기
-
3) Example
-
참고 : ubuntu 64bit system
3-1) [ large.c ]
#include<stdio.h>
#include<stdlib.h>
#define INDEX 8
int main(){
char *large_p[INDEX];
char *dummy_p[INDEX];
char *malloc_p[INDEX];
int i;
puts("Creation large bin!!");
for(i=0;i<INDEX;i++){
large_p[i] = (char*)malloc(0x3f0+i*0x10);
dummy_p[i] = (char*)malloc(0x100);
}
for(i=0;i<INDEX;i++){
free(large_p[i]);
malloc_p[i] = (char*)malloc(0x1000);
}
puts("All free!!");
for(i=0;i<INDEX;i++){
free(dummy_p[i]);
free(malloc_p[i]);
}
puts("exit!!");
return 0;
}
Debugging [ large ]
[ 두 번째 puts() 직전 → large bin 생성 ]
-
largebin[0], largebin[1]이 생성되었으며 0x40(64)bytes의 차이가 존재
-
각 large bin에 Free Chunk들의 사이즈가 다양하며 fd와 bk가 설정되어 있음 → double linked list
-
각 인덱스마다 가장 큰 size의 chunk가 맨 앞에 존재(내림차순 정렬)
-
large bin의 Free Chunk들에는 fd_nextsize, bk_nextsize값이 세팅되어 있음
2.3 fast bin
1) fast bin이란
인접한 청크들과 병합이 일어나지 않으며 단일 고정 크기만 커버하므로 자동으로 분류되어 메모리 할당과 해제가 가장 빠른 bin으로 총 10개의 bin이 존재한다.
2) Fast bin 특징
-
10개의 bin을 관리하며 fast bin의 상한 값보다 크기가 작은 chunk들을 관리
-
32bit system
-
상한 값 : 64byte(64*4/4)
-
chunk size 종류 : 16, 24, 32, 40, 48, 56, 64, 72, 80, 88byte
-
-
64bit system
-
상한 값 : 128byte(64*8/4)
-
chunk size 종류 : 32, 48, 64, 80, 96, 112, 128, 144, 160, 176byte
-
추가로 64bit에서 일반적으로 32(0x20) ~ 128(0x80)까지 7개의 bin만 사용함
-
-
-
LIFO(Last In First Out, stack과 동일한 방식)를 사용하며 single-linked list로 관리
-
마지막으로 해제된 chunk가 먼저 재할당
-
sinle-linked list를 사용하므로 bk는 사용되지 않음
-
-
unsorted bin과 같이 빠른 성능을 위해 사용되며 이웃과 병합하지 않으므로 해당 chunk 크기에 대한 malloc요청이 빨리 응답하여 즉시 용도를 바꿀 수 있다.
-
PREV_INUSE[P]비트를 설정하지 않게 하여 병합되지 않음
-
-
단점으로는 fast bin chunk가 완전히 해제되거나 병합되지 않기 때문에 메모리가 시간이 지남에 따라 fragmentation이 심해질 수 있다.
-
이 문제를 해결하기 위해 정기적으로 "consolidates" 한다.(malloc.c line 4448) → malloc_consolidate
-
3) Example
-
참고 : ubuntu 64bit system
3-1) [ fast.c ]
#include<stdio.h>
#include<stdlib.h>
#define INDEX 14
int main(){
char *fast_p[INDEX];
char *malloc_p[INDEX];
char *lifo_p;
int i;
for(i=0;i<INDEX;i++)
fast_p[i] = (char*)malloc(0x10+i*0x8);
puts("finish malloc!!");
for(i=0;i<INDEX;i++)
free(fast_p[i]);
puts("creation fast bin!!");
lifo_p = (char*)malloc(0x10);
puts("exit!!");
return 0;
}
Debugging [ fast ]
[ 두 번째 puts() 직전 → fast bin 생성 ]
-
총 14개의 fast bin이 생성되었으며 각 size에 맞게 fastbin[0] ~ [6]까지 들어가 있다.
-
fd는 설정되있지만 bk는 설정되지 않음 → single linked list
-
Free되었음에도 불구하고 인접한 청크끼리 병합되질 않는다. → PREV_INUSE[P] bit가 0x1로 세팅
-
LIFO방식으로 관리되기 때문에 이후에 들어오는 메모리 할당 요청시 마지막에 삽입된 bin부터 메모리 할당하는데 사용될 것이다. (다음 그림을 보자)
[ lifo_p → malloc() 요청 직후 ]
-
lifo_p 포인터는 0x10(헤더 포함 0x20)bytes의 크기의 메모리 할당 요청을 시도하였다.
-
fastbin[0]에는 0x20bytes의 free된 chunk들이 모여있으며 제일 나중에 free된 0x602020을 메모리 할당에 사용된다.(LIFO)
2.4 Unsorted bin
1) unsorted bin
free된 chunk가 small bin 또는 large bin에 바로 들어가는 것이 아니라 unsorted bin에 들어가게 되며 이후에 메모리 할당 요청시 unsorted bin을 제일 먼저 확인하여 적절한 크기의 chunk가 있으면 재사용하는 cache와 같은 효과를 낸다. 만일, 적절한 크기의 chunk가 존재하지 않으면 chunk들은 각각 자신의 bin으로 들어간다.
또한, 해당 bin에는 chunk의 크기에 제한이 없으므로 다양한 크기의 chunk존재한다. (But, fast bin에 해당하는 chunk는 들어가지 않음)
2) unsorted bin 특징
-
1개의 bin이 존재, FIFO를 사용하고 double-linked list로 관리
-
best fit으로 할당된 chunk의 남은 부분인 remainder가 unsorted bin으로 들어간다.
-
free했을 때 각 chunk들은 자신의 bin(small bin, large bin)으로 들어가기 전에 먼저 unsorted bin에 들어가며 malloc했을 때 unsorted bin에 알맞은 크기가 있으면 바로 반환해주고 존재하지 않으면 각 chunk들은 자신의 bin(small bin, large bin)으로 들어간다.(fast bin은 제외)
-
이러한 방식을 통해 cache와 같은 효과를 내어 할당과 해제하는 처리가 빠르다.
-
-
unsorted chunk에는 NON_MAIN_ARENA[A]플래그를 설정하지 않음
-
chunk의 크기가 정해져 있지 않아 다양한 크기의 chunk저장
-
fast bin들이 큰 chunk의 크기를 요청받았을 때 한꺼번에 합쳐지면(malloc_consolidate) 이 때 unsorted bin에 들어감
-
새로 free된 chunk를 적절한 bin에 넣는 대신에 인접한 chunk중에 free된 chunk가 존재하면 병합하여 unsorted bin에 들어가는데 이 때, free된 chunk의 포인터 fd와 bk를 정리해줘야함 → unlink(binlist에 등록된 chunk를 제거하기 위해 포인터 fd, bk를 정리해주는 작업)
3) Example
-
참고 : ubuntu 64bit system
3-1) [ unsorted_1.c ]
#include<stdio.h>
#include<stdlib.h>
int main(){
char *small_p;
char *large_p;
char *dummy_p[2];
char *malloc_p[2];
// unsorted bin -> small bin
small_p = (char*)malloc(0x100);
dummy_p[0] = (char*)malloc(0x700);
free(small_p);
malloc_p[0] = (char*)malloc(0x700);
puts("Creation small bin!!");
// unsorted bin -> large bin
large_p = (char*)malloc(0x500);
dummy_p[1] = (char*)malloc(0x700);
free(large_p);
malloc_p[1] = (char*)malloc(0x700);
puts("Creation large bin!!");
puts("Exit!!");
free(malloc_p[0]);
free(malloc_p[1]);
free(dummy_p[0]);
free(dummy_p[1]);
return 0;
}
Debugging [ unsorted_1 ]
[ small_p → free()이후 ]
-
small bin size만큼의 chunk를 free 시켰을 때 바로 small bin으로 가는게 아니라 unsorted bin에 먼저 삽입
[ malloc_p[0] → malloc()이후 ]
-
unsorted bin은 단 1번의 기회, 즉, unsorted bin에 들어있는 chunk들의 size보다 같거나 작은 메모리 할당 요청시 제거되며 그보다 큰 메모리 할당 요청시 unsorted bin에 들어있는 bin들은 각자 자신의 bin에 맞게 삽입됨 → 현재 small bin으로 이동
[ large_p → free()이후 ]
-
large bin 또한 large bin size만큼의 chunk를 free 시켰을 때 바로 large bin으로 가는게 아니라 unsorted bin에 먼저 삽입
[ malloc_p[1] → malloc()이후 ]
-
unsorted bin에 존재하는 chunk의 크기보다 더 큰 메모리 요청 시 각자 자신의 자리로 이동 → 현재 largebin으로 이동
3-1) [ unsorted_2.c ]
#include<stdio.h>
#include<stdlib.h>
int main(){
char *small_p[2];
char *large_p[2];
char *dummy_p[4];
char *malloc_p;
// Create unsorted bin
small_p[0] = (char*)malloc(0x100);
dummy_p[0] = (char*)malloc(0x80);
small_p[1] = (char*)malloc(0x200);
dummy_p[1] = (char*)malloc(0x80);
large_p[0] = (char*)malloc(0x400);
dummy_p[2] = (char*)malloc(0x80);
large_p[1] = (char*)malloc(0x1000);
dummy_p[3] = (char*)malloc(0x80);
free(small_p[0]);
free(small_p[1]);
free(large_p[0]);
free(large_p[1]);
puts("Creation unsorted bin!!");
// best fit
malloc_p = (char*)malloc(0x180);
puts("best fit!!");
free(dummy_p[0]);
free(dummy_p[1]);
free(dummy_p[2]);
free(dummy_p[3]);
free(malloc_p);
return 0;
}
Debugging [ unsorted_2 ]
[ 첫 번째 puts 직전 → unsorted bin 생성 ]
-
현재 3개의 unsorted bin이 존재하며 double linked list로 구성
-
다양한 크기의 Free Chunk들이 포함되어 있음
-
unsorted bin : 0x410(large bin) ↔ 0x210(small bin) ↔ 0x110(small bin)
-
[ malloc_p → malloc(0x180)요청 ]
-
unsorted bin에 존재하는 Free Chunk들은 각자 자신의 bin에 들어감
-
이 때, 메모리 할당 요청 전에 unsorted bin에는 0x410, 0x210, 0x110크기의 Free Chunk가 존재하는데 요청한 메모리 크기는 0x180(헤더 포함 0x190)이다.
-
best fit에 따라 0x210이 제일 적합하므로 0x210에서 분할하여 0x190만큼을 메모리 할당에 쓰이는데 돌려주고
-
나머지(last_remainder) 0x80크기의 Chunk는 unsorted bin에 들어가게 된다.
3. 정리
1) malloc_state 구조체(Arena Header)에서 bin관련 멤버
2) 각 bin의 특징
3) bin 구성
4) 각 함수 호출 과정
malloc() 및 free()가 동작하는 과정을 보기 쉽게 잘 정리해둔 블로그가 있어 다음 그림을 참고하였다.
4-1) malloc()
4-2) free()
4. 참고자료
'Security > 01 System Hacking' 카테고리의 다른 글
| [heap exploit] - Unsafe Unlink (4) | 2020.07.31 |
|---|---|
| [heap exploit] - House Of Force (0) | 2020.07.27 |
| heap(3) - glibc malloc(2) (feat. chunk) (1) | 2020.07.07 |
| heap(2) - glibc malloc(1) (feat. Arena) (0) | 2020.07.07 |
| heap(1) - Dynamic Memory Allocation (4) | 2020.07.07 |
