Home Heap 공부 2(chunk)
Post
Cancel
Posted Jul 21, 2023 Updated Aug 19, 2023
Preview Image
By d0razi
17 min read

청크 이론 정리 & 실습

List of Contents

Chunk

malloc함수가 호출됨으로서 할당받는 영역을 청크라고 부릅니다. 32bit 환경에서는 청크가 8byte 단위로 할당되고, 64bit에서는 16byte 단위로 할당됩니다. 일반적으로 malloc을 호출하고 반환되는 주소에 데이터를 입력하게 되는데, malloc함수가 반환해주는 주소는 청크의 시작주소가 아닌 페이로드의 주소입니다.

페이로드 위에는 meta-data를 포함하는 청크헤더가 존재합니다. 청크헤더에는 현재 청크의 사이즈, 인접한 청크의 사이즈의 정보가 있습니다.

청크는 크게 3가지 유형이 있습니다. 기본적인 구조는 동일하며 들어있는 데이터의 차이가 조금씩 있습니다. 이제 각 유형별 청크를 알아보겠습니다.

할당된 청크

Untitled

하나 알아둬야하는 정보가 있습니다. 기본적으로 malloc을 통해 할당된 청크는 prev_size, size, payload 이렇게 구성되어 있는데, 다음 청크의 prev_size필드도 현재 청크의 payload영역으로 사용됩니다. 따라서 실질적인 청크는 다음 청크의 prev_size까지 포함하고, free시에 해당 영역은 현재 청크의 크기를 중복하여 저장하는 용도로 사용합니다.

  • prev_size

    만약 현재 청크 바로 이전 청크가 해제된 경우, 이 필드는 이전 청크의 크기를 저장합니다. 만약 해제된 청크가 없으면 기본값인 0으로 세팅됩니다.

  • size

    이 필드에는 현재 할당된 청크의 사이즈를 저장합니다.

    64bit에서는 malloc으로 할당 시 16byte 단위로 저장한다고 위에서 적었습니다. 때문에 하위 3bit는 항상 0으로 고정됩니다.

    1
2
3

      00000000 00010000 = 16바이트
  00000000 00100000 = 32바이트
  00000000 00110000 = 48바이트

    따라서 하위 3bit를 부가적인 정보를 저장하는데 사용합니다.

    1. NON_MAIN_ARENA(A) : 현재 청크가 thread_arena에 위치하는 경우 1로 세팅됩니다.
    2. IS_MMAPPED(M) : 현재 청크가 mmap을 통해 할당된 경우 1로 세팅됩니다. 큰 메모리를 요청하는 경우에는 heap을 이용하지 않고, mmap() 시스템 콜을 통해 별도의 메모리 영역을 할당합니다. 이렇게 할당된 청크들은 bin 내에 속하지 않고, free시 그냥 munmap() 호출로 해제합니다.
    3. PREV_INUSE(P) - 현재 청크 바로 이전의 청크가 할당된 상태인 경우 1로 세팅됩니다.

해제된 청크

Untitled

free된 청크들은 단일 free 청크로 결합된다는 특징이 있습니다. 이 특징을 생각하면서 free된 청크 구조를 알아보겠습니다.

  • Prev_size

    아까 위에서 해당 필드에 대해 설명을 했지만, 사실 해당 필드는 free된 청크에서 사용됩니다. 위 그림을 보면 연한 노란색 부분이 전부 free 청크 영역입니다. 맨 아래에 prev_size가 포함된 것을 확인할 수 있는데, 이는 다음 Chunk의 일부임으로 현재 Chunk의 사이즈 값이 들어갑니다. 이걸 boundary tags 기법이라고 합니다. 이 기법이 왜 필요한지 아래에서 설명하겠습니다.

    Untitled

    위 그림을 보면 청크 A가 free된 상태이고, 청크 B는 할당된 상태입니다. 이 상태에서 청크 B를 free하려고 합니다. 이럴 땐 청크 A가 free된 상태이기 때문에 청크 B를 free한 뒤 A와 결합하여 하나의 청크로 만들 것입니다.

    그렇게 하려면, 청크 B를 기준으로 어디까지가 청크 A인지, 그리고 청크 A가 free되어있는지 flag 비트를 확인해야합니다. 따라서 free된 청크는 맨 아래쪽에 현재 청크의 사이즈를 복사해두어야합니다.

    그러면 청크 A가 해제될때 청크 맨 아래 청크 B의 prev_size필드에 자신의 청크 사이즈 값을 저장할 것이고, 따라서 청크 B가 해제될때 이 값을 자신의 주소에서 빼서 청크 A의 주소를 알 수 있어서 결합을 진행할 수 있게 됩니다. 또한 prev_size에 들어가는 값에는 P(PREV_INUSE) 플래그가 제거되어 들어갑니다.

    1
2
3
4

      <예외사항>
    
  참고로 fastbins의 경우에는 free 청크들끼리 결합하지 않으므로 해당 free 되어도 boundary tags를 
  세팅하지 않습니다.bin과 관련된 설명은 다른 문서에 정리해두었습니다.

  • Fd(forward pointer), Bk(backward pointer)

    fd와 bk는 각각 해제된 다음 청크, 해제된 이전 청크를 가리키는 포인터입니다. 이러한 포인터들은 bin의 따라 단일 연결 리스트, 혹은 이중 연결 리스트 형태로 구현되어있습니다다. bin에서 free된 청크들이 관리됩니다. 아래에서 간단하게 알아보겠습니다.

    Untitled

    bin에 free된 청크들이 이중 연결 리스트로 연결되어 있습니다. fd, bk가 각각 다음, 이전 청크를 가리키고 있기 때문에 전체 청크들을 탐색이 가능합니다. 헷갈리면 안되는 부분이 bin에 등록된 청크들은 물리적으로 붙어있는 것이 아닌 논리적으로 연결되어있는 것입니다(아래 그림).

    Untitled

    bin이 free된 청크들을 관리하기 위한 방법으로 실제 heap영역에서 free된 청크들을 이중 연결 리스트로 연결시켜 놓습니다(fastbin은 단일 연결 리스트입니다).

  • fd_nextsize, bk_nextsize

    bin의 종류는 사이즈에 따라 fastbin, unsorted bin, small bin, large bin이 있습니다. 총 4개중 이번 필드는 largebin에서만 사용됩니다.

    large bin에서만 해당 포인터들을 사용하는 이유는 large bin을 제외한 다른 bin들은 각 인덱스별로 동일한 사이즈의 청크들로만 리스트가 생깁니다. 하지만 large bin은 리스트의 청크들을 범위로 구분해서 관리하기 때문에 청크들의 사이즈를 알아야합니다.

Top chunk

  • Top Chunk는 Arena의 가장 상위 영역에 있는 청크입니다. 맨 처음 malloc 호출시 사용자가 요청한 사이즈 만큼만이 아닌, 충분한 크기의 메모리를 받아옵니다. 그리고 이 메모리를 Top chunk에 넣습니다.
  • free chunk중에 메모리 할당 요청 사이즈를 만족하는 사이즈의 청크가 없는 경우, Top 청크를 2개로 분할하여 요청을 처리합니다.
    1. User chunk : 사용자가 요청한 크기
    2. Remainder chunk : 나머지크기. 이 청크가 새로운 Top 청크가 됩니다.
  • 만약 현재 top 청크 크기보다 더 큰 사이즈의 메모리를 요청하는 경우는 아래와 같이 2가지의 경우로 동작합니다.
    1. main_arena인 경우 : sbrk로 top청크의 크기를 확장시킵니다.
    2. thread_arena인 경우 : mmap으로 메모리를 받아옵니다.

실제 Chunk 구조 확인

실습환경 : Ubuntu 16.04

아래 코드를 디버깅 하면서 Chunk의 구조를 확인해보겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

int main() {
    char* a=(char*)malloc(0x20);

		char* b=(char*)malloc(0x14);

    char* c=(char*)malloc(0x30);

    char* d=(char*)malloc(0x14);

    char* e=(char*)malloc(0x22);

    strcpy(a,"AAAAAAAA");
    strcpy(b,"BBBBBBBBBBBBBBBBBBBB");
    strcpy(c,"CCCCCCCC");
    strcpy(d,"CCCCCCCC");
    strcpy(e,"BBBBBBBB");

    free(b);    // fastbin fd, bk checking
    free(d);    // fastbin fd, bk checking

    char* sg=(char*)malloc(0x100);
    strcpy(sg,"SSSSSSSS");
    free(sg);       // prev_size checking

    char* z=(char*)malloc(0x100);
    char* test=(char*)malloc(140000);       // mmap'd flag checking
    free(test);
    return 0;
}

bp 설정

  • char* a=(char*)malloc(0x20);
  • strcpy(e,”BBBBBBBB”);
  • free(b); // fastbin fd, bk checking
  • free(d); // fastbin fd, bk checking
  • char* test=(char*)malloc(140000);
  • free(test);

**malloc 호출시 기본 청크 구조**

  1. char* a=(char*)malloc(0x20); 호출 후

처음으로 malloc이 호출될때는 현재 free 청크도 없고, heap 영역이 할당되어 있지 않기 때문에 brk를 이용하여 메모리를 할당받습니다.

Untitled

위 그림은 malloc 호출시 실행되는 알고리즘입니다. 그림을 봤을때 맨 처음 malloc을 호출하기 때문에 아래의 어떠한 조건도 해당되지 않고, Top 청크 또한 0일 것입니다. 따라서 sysmalloc이 호출됩니다. char* a=(char*)malloc(0x20); 코드에 bp를 걸고 b*brk 를 입력한뒤 실행시켜보겠습니다.

Untitled

backtrace로 호출과정을 살펴보면, 위 그림의 알고리즘의 sysmalloc을 호출하고 sbrk→brk를 호출하는걸 확인할 수 있습니다. malloc 호출이 종료되면 아래 그림과 같습니다.

Untitled

top chunk의 사이즈가 0x20fd1로 세팅되어 있습니다. 할당된 청크는 이전 청크가 없기 때문에 prev_size가 0인걸 볼 수 있습니다. malloc함수가 사용자에게 반환해주는 주소는 mem의 시작주소로 0x256e010 일 것입니다. 이 주소부터 입력하는 데이터가 들어갑니다.

현재 청크 사이즈는 [요청 사이즈(0x20) + chunk 헤더(0x10)] 0x30입니다.

  1. strcpy(e,”BBBBBBBB”); 호출 직후

5개의 할당된 청크에 모두 데이터가 들어있는 것을 볼 수 있습니다.

Untitled

Top chunk의 사이즈가 0x20fd1 → 0x20f21로 변한걸 확인할 수 있습니다. 할당된 5개의 청크사이즈를 다 더해서 0x20fd1에서 빼면 0x20f21이 나옵니다. 이걸로 Top chunk에서 청크들이 할당되는걸 확인할 수 있습니다.

위 그림에서 청크별로 초록색으로 구분했습니다. 아까 청크 설명 부분에서 다음 청크의 prev_size 필드도 현재 청크의 페이로드 부분으로 들어간다고 했습니다. 청크 b에 입력한 데이터가 청크 c의 prev_size 필드까지 들어가는걸 확인할 수 있습니다.

  1. free(b); 호출 직후 // fastbin fd, bk checking

Untitled

첫 free가 호출된 후 메모리 상태입니다. 달라진 점은 청크 b의 fd 필드가 0으로 초기화 된것 말고는 없습니다. 그리고 fastbin에 free한 청크의 주소가 들어가 있습니다.

  1. free(d); 호출 직후 // fastbin fd, bk checking

Untitled

두번째 free가 호출된 후 메모리 상태입니다. 현재 청크 b와 d가 free된 상태입니다. 청크 d의 fd 필드에 청크 b의 주소가 들어가 있는 것을 확인이 가능합니다. fastbin의 상태는 아래와 같습니다.

Untitled

fastbin[0] ← 청크 d ← 청크 b로 연결되어 있는걸 볼 수 있습니다.

  1. char* test=(char*)malloc(140000); 호출 직후

Untitled

malloc이 반환해준 주소를 확인해보면 기존의 할당받았던 주소가 아닙니다. 반환해준 주소의 size 필드를 확인해보면 하위 2번째 bit가 1로 세팅되어 있기 때문에 mmap으로 할당받은 영역인것을 확인할 수 있습니다. 이 영역이 어디에 위치하는지는 vmmap으로 확인가능합니다.

Untitled

밑줄 친 영역에 반환받은 주소가 있는걸 확인할 수 있습니다. 이 이유는 위에 설명한대로 Top chunk보다 큰 사이즈를 요청 받아서 mmap syscall로 메모리를 할당 받았기 때문입니다. 해당 영역은 단일 청크로 사용되며, free시 munmap으로 해제되기 때문에 free이후에는 디버깅이 불가능합니다.

  1. free(test); 호출 직후

Untitled

위 그림처럼 free이후에는 해당 메모리 영역이 디버깅이 불가능합니다.

Untitled

vmmap에서도 해당 메모리 영역이 없어진 것을 볼 수 있습니다.

InfoSec, Pwn
linux heap
This post is licensed under GNU AGPL by the author.
Recently Updated
Contents