-01.first_fit.c

서론

first_fit.c를 공부 하였지만, 추가적인 학습이 필요하다 생각하였다. 따라서 개념에 대한 정리를 하려한다.

 

본론

힙이란?

프로세스가 실행되는 동안 프로그램이 동적으로(실행 중에) 메모리를 할당하고 해제하는 영역이라고 한다. 쉽게 말하자면

프로그램이 실행중일 때 크기가 정해지지 않은 데이터를 저장할 때 힙 영역에서 메모리를 할당하고, 데이터를 더이상 안쓸때 해제한다는 뜻이다.

 

동적할당, 정적할당, 자동할당?

힙은 동적할당이다. 동적할당이란

프로그램이 실행중에 메모리를 할당하고 해제하는 것이다.

여기서 메모리를 할당한다는 말은 코드로 표현하면 malloc() 을 뜻한다.

또한 해제를 뜻하는 코드 free(), delete() 이다.

이는 힙 영역에 저장된다.

 

정적할당은 뭘까?

정적할당은 전역변수나, static 변수이고,

프로그램이 실행되고 딱 한번 할당하고, 프로그램이 끝나면 해제된다. 

이는 데이터세그먼트(.data/.bss)에 저장된다.

 

자동할당은 뭘까?

함수나 블럭 내부에서 static 없이 써진 변수를 스택에 자동으로 올리 함수나, 블럭에서 벗어나 자동으로 해제된다.

스택에 저장이 된다.

 

청크, 섹션

청크란?

힙에서는 메모리를 청크단위로 나눈다.

청크는 일정한 크기의 저장공간이다. 힙에서는 청크를 구성할 때 다음과 같이 따른다.

헤더 : 청크가 사용중인지 아닌지 상태 저장

페이로드 : 사용자가 쓰는 데이터 영역

푸터 : 뒤쪽의 청크의 크기 정보를 중복 저장 => 인접 청크와 병합할 때 참조

역할은

malloc 호출 시 → 적당한 크기의 청크를 골라 헤더를 업데이트한 뒤 페이로드 주소 반환

free 호출 시 → 해당 청크의 헤더를 “free”로 표시하고, 빈(bin) 리스트에 넣어 재사용

청크(bin => 청크를 크기별로 모아두 저장소)

 

• tcache
  
  • 256바이트 이하의 작은 크기 청크를 최대 7개까지 보관
  • malloc/free 호출을 아주 빠르게 처리
• fastbin
  • 64바이트 이하의 작은 청크를 LIFO 방식으로 관리
  • 스레드 안전 처리가 없어서 빠르지만, 이중 해제(double free) 취약점에 특히 취약
• smallbin / largebin
  • smallbin: 64바이트 초과~512KB 이하 정도 청크를 크기별로 이중 연결 리스트 관리
  • largebin: 512KB 초과 청크를 이중 연결 리스트 관리
  • 분할(splitting)·병합(coalescing) 기능으로 내부 단편화를 줄임
• unsorted bin
  • 가장 최근에 해제된 청크들이 임시로 모이는 곳
  • 다음 malloc 요청 때 사이즈가 맞지 않아도 먼저 여기서 검색 후, 맞는 크기의 청크를 smallbin/largebin으로 옮겨 감
• top chunk
  • 힙의 끝부분에 남은 “아직 한 번도 분할되지 않은” 자유 공간
  • 더 큰 크기 malloc 요청 시 이 공간에서 잘라서 사용하거나, 필요 시 sbrk/mmap으로 힙을 확장

 

 

섹션이란?

코드, 초기화된 데이터, 초기화되지 않은 데이터 등을 구분해서 실행 파일 내부에 나눠 담아 두는 단위다.

섹션은 여려 섹션이 있지만 .data/.bss 만 다루겠다.

.data : 초기값이 명시된 전역 변수나 static 변수의 실제 값이 저장된 영역, 읽기·쓰기 가능

.bss : 초기값이 0이거나 별도 초기화되지 않은 전역/static 변수들이 올라가는 영역, 실행 파일에는 크기 정보만 기록되고, 로더가 메모리에 매핑할 때 0으로 채워 넣음

 

pwndbg로 실습

우선 malloc() 부분을 보겠다.

► 0x555555555221 <main+184>    mov    edi, 0x512             EDI => 0x512
  0x555555555226 <main+189>    call   malloc@plt                  <malloc@plt>

이를 보면 

char* a = malloc(0x512); 이부분이다.

우선 a를 할당하는데 0x512 rdi로 할당하고

malloc()을 호출한다.

malloc()을 하기 전에는

*RDI  0x512
*RIP  0x555555555226 (main+189) ◂— call malloc@plt

다음과 같이 되어있다. 호출을 하면

*RAX  0x5555555592a0 ◂— 0

다음과 같이 주소가 나오게 된다.

사진을 보면 RAX, RCX, RDI 가 HEAP 영역에서로 0x5555555592a0값을 가지는 것을 볼 수 있다.

 

그리고 char* b = malloc(0x256); 부분을 보면

   0x55555555522b <main+194>    mov    qword ptr [rbp - 0x18], rax     [0x7fffffffdef8] <= 0x5555555592a0 ◂— 0
   0x55555555522f <main+198>    mov    edi, 0x256                      EDI => 0x256
 ► 0x555555555234 <main+203>    call   malloc@plt                  <malloc@plt>

여기서    0x55555555522b <main+194>    mov    qword ptr [rbp - 0x18], rax     [0x7fffffffdef8] <= 0x5555555592a0 ◂— 0

이 구문에서 rax의 값 즉 a의 malloc() 을 [rbp - 0x18] 위치에 저장하라는 말 fwrite를 하기 위해 사용

다음 줄은 0x256을 rdi로 전달하니 rdi에 0x256을 저장함

그리고 call malloc을 함

이를 하면

다음과 같이 rax, rcx, rdi에 0x5555555597c0 값이 입력됨

이를 [rdp -0x20]위치에 저장

이 후에 a와 b의 힙 주소를 출력

 

다음으로 넘어가 c의 힙주소 할당을 함

 ► 0x555555555376 <main+525>    mov    edi, 0x500             EDI => 0x500
   0x55555555537b <main+530>    call   malloc@plt                  <malloc@plt>

edi 에 0x500만큼 할당하여 c의 malloc 을 0x500으로 정함

그리고 malloc를 할당하면

이렇게 rax, rc, rdi에 0x5555555592a0 즉 a의 힙 주소와 똑같이 나옴 따라서 청크가 같다면 같은 힙 주소로 걸린다라는 것을 알 수 있음

 

그런데 사진을 보면 a를 malloc 시켰을 때랑 c를 malloc를 시켰을 때랑 다른 부분이 있다. rax 뒤에 보라색 이상한게 뜬다. 이는 a 때 free 가 호출되어 Unsorted Bin 에 값이 들어갔고, fd 포인터들이 값을 시각화 하는 것이다.

 

fd(forward pointer)란?

free된 chunk들이 들어가는 bin(fastbin, unsorted bin, small bin 등) 내부에서, chunk들이 연결 리스트 형태로 관리된다.

이 때 한 chunk가 다음 chunk를 가리키는 포인터가 바로 fd

 

즉 

free() 호출:

• 크기가 fastbin, tcache 범위를 초과하는 chunk는 → Unsorted Bin에 들어감

malloc(requested_size) 호출:

• glibc는 먼저 Unsorted Bin에서 적절한 chunk를 찾음
• 첫 번째로 조건을 만족하는 chunk가 선택됨 → First-Fit 전략

그 chunk가 크다면?

• → 필요한 만큼만 떼어주고 나머지는 남겨서 다시 bin에 넣음 → 이 과정을 chunk split이라고 함

frist_fit.c에서는

free()로 0x520짜리 chunk가 unsorted bin에 들어감

이후 malloc(0x500) 호출

 

1. glibc는 0x520짜리 chunk를 발견
2. 요청 크기(0x500 + 메타데이터 = 약 0x510)를 만족하므로 사용
3. 남는 0x10은 너무 작아서 split되지 않음 → 그냥 통째로 할당됨

이렇고 다른경우는 

free()로 0x600짜리 chunk가 들어감

malloc(0x200) 호출

1. 앞부분 0x210 정도만 할당
2. 나머지 0x3f0짜리 chunk는 새로 만들어서 다시 unsorted bin에 넣음

결론

glibc의 malloc은 Unsorted Bin에서 'First-Fit' 전략으로 chunk를 선택하며, 크기가 맞으면 split하여 재사용한다.

하지만 tcache, fastbin 같은 경우에는 가득 찼을 때를 제외하고 바로 들어간다.