[Pwnable] Heap1

Memory Allocator

힙 익스플로잇을 구현하기 위해서는 메모리 관리를 위해 사용되는 Allocator에 대한 이해가 필요하다.

 - dlmalloc, ptmalloc2, jemalloc, tcmalloc, libumem, 등 다양한 종류의 메모리 할당자가 있다.

 

여기서는 GNU C Library의 메모리 할당자인 ptmalloc2에 대해 설명하겠다.

 - ptmalloc2는 dlmalloc 코드를 기반으로 하며 멀티 스레드에서 사용되도록 확장되었다. 

 

 

ptmalloc2 (2.23)

ptmalloc2은 동일한 시간에 2개의 스레드가 malloc을 호출할 경우, 메모리는 각각의 스레드가 분배된 힙 영역을 일정하게 유지하고, 힙을 유지하기 위한 freelist data structures 또한 분배되어 있기 때문에 즉시 할당된다.

 

dlmalloc에서 쓰레드 기능이 추가된 것이 ptmalloc2이라고 하였는데, 쓰레드 관련 처리가 어떤식으로 진행되는지 코드로 알아보자.

 

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/types.h>
 
void* threadFunc(void* arg) {
        printf("Before malloc in thread 1\n");
        getchar();
        char* addr = (char*) malloc(1000);
        printf("After malloc and before free in thread 1\n");
        getchar();
        free(addr);
        printf("After free in thread 1\n");
        getchar();
}
 
int main() {
        pthread_t t1;
        void* s;
        int ret;
        char* addr;
 
        printf("Welcome to per thread arena example::%d\n",getpid());
        printf("Before malloc in main thread\n");
        getchar();
        addr = (char*) malloc(1000);
        printf("After malloc and before free in main thread\n");
        getchar();
        free(addr);
        printf("After free in main thread\n");
        getchar();
        ret = pthread_create(&t1, NULL, threadFunc, NULL);
        if(ret)
        {
                printf("Thread creation error\n");
                return -1;
        }
        ret = pthread_join(t1, &s);
        if(ret)
        {
                printf("Thread join error\n");
                return -1;
        }
        return 0;
}

코드에서 확인 할 부분은 다음과 같다.

 1. main thread에서 malloc 호출 이전

 2. main thread에서 malloc 호출 이후, free 호출 이전

 3. main thread에서 free 호출 이후

 4. thread 생성후, 생성한 쓰레드에서 malloc 호출 이전

 5. 생성한 쓰레드에서 malloc 호출 이후, free 호출 이전

 6. 생성한 쓰레드에서 free 호출 이후

 

 

1) main thread에서 malloc 호출 이전

main() 에서 malloc이 호출되기 전 메모리 상태이다. 아직 메인 thread 밖에 없고, 힙영역 또한 아직 없다.

 

 

2) main thread에서 malloc 호출 이후, free 호출 이전

malloc이 호출되고, free 되기 전 상황. 힙 영역이 0x602000 ~ 0x623000 에 생성된 것을 확인할 수 있다.

-> brk syscall을 사용하여 program break 위치를 증가시킴으로 확장된 영역이다.( 데이터 세그먼트 영역을 늘렸다는 뜻)

 

또한, malloc 시 1000바이트만 요청했으나, 힙 메모리의 크기는 135168바이트(0x623000-0x602000)나 생성되었다. 이러한 힙 메모리의 인접한 지역을 arena라고 부른다. 이 arena는 메인 쓰레드로에 생성되었기 때문에 main arena라고 부른다.

 

이후, 할당 요청은 이 arena를 사용하여 비어있는 공간이 없어질 때 까지 사용한다. arena가 꽉찰 경우, 프로그램의 break 위치를 증가시킴으로써 관리한다.

 

3) main thread에서 free 호출 이후

-> 메모리 영역에 변화가 없는 것을 확인할 수 있다. free가 호출되어 메모리가 해제된 경우에, 즉각 운영체제에 반환되지 않았다는 소리이다. 할당된 메모리의 일부분(1000바이트)은 오로지 main_arena의 bin에 이 해제된 청크를 추가하고, gblic malloc 라이브러리에 반환된다.

 

이후, 사용자가 또다시 메모리를 요청하는 경우, 아까와 같이 brk syscall로 바로 할당해주는 것이 아닌, bin에 비어있는 블록이 있는지 탐색하고, 존재한다면 비어있는 블록을 할당해준다. 만약 비어있는 블록이 없다면 아까처럼 동일하게 메모리를 할당해준다.

 

 

4) thread 생성후, 생성한 쓰레드에서 malloc 호출 이전

pthread_create 함수를 통해 ID 값이 2인 쓰레드가 생성되었다. (thread2라 하자).

thread2는 threadFunc 함수를 실행하는데 위 영역은 아직 malloc을 호출하지 않았으므로 thread2의 힙 영역은 없지만, 해당 thread2의 쓰레드 스택이 생성된 것을 확인 할 수 있다.

 

0x00007ffff6fef000 ~ 0x00007ffff77f0000 영역이 바로 thread2의 스택 영역이다.

 

 

5) 생성한 쓰레드에서 malloc 호출 이후, free 호출 이전

thread2의 힙영역(0x00007ffff0000000 ~ 0x00007ffff4000000)이 생성된 것을 확인 할 수 있다. 해당 영역은 brk를 사용해서 할당하는 main_thread와는 달리 mmap을 사용하여 힙 메로리가 생성된다.

 

그리고 또한 여기서도 볼 수 있듯이, 사용자는 1000바이트만 요청했지만, 67MB 크기의 힙 메모리가 프로세스 주소 공간에 매핑되어있다. 이 67MB 중,135KB의 영역이 rw 권한으로 세팅되어, thread2를 위한 힙 메모리로 할당되었다. 이러한 메모리의 일부분(135KB)을 thread_arena 라고 부른다.

 

 

6) 생성한 쓰레드에서 free 호출 이후

thread2에서 free 호출 이후 역시, 바로 메모리를 반환하지 않는다는 것을 확인 할 수 있다. 이 역시 아까처럼 해제한 영역은 thread_arena의 bin에 해제된 블럭을 추가하고 gblic malloc에 반환한다.

 

위와 같은 방법으로 메인 쓰레드, 쓰레드들이 관리가 된다.

그리고 'glibc malloc'의 소스 코드에서 아래와 같은 3개의 데이터 구조체를 확인할 수 있다.

 

 

---

heap_info 구조체(Heap_Header)

1.typedef struct _heap_info {
2.  mstate ar_ptr;    /* 현재 heap을 담당하고 있는 Arena */
3.  struct _heap_info *prev;  /* 이전 heap 영역 */
4.  size_t size;      /* 현재 size(bytes) */
5.  size_t mprotect_size; /* mprotected(PROT_READ|PROT_WRITE) size(bytes) */
6.  char pad[(-6*SIZE_SZ)&MALLOC_ALIGN_MASK]; /* 메모리 정렬 */
7.  /* sizeof(heap_info) + 2*SIZE_SZ는 MALLOC_ALIGN_MASK의 배수 */
} heap_info;

Heap Header - 단일 스레드 arena는 여러 개의 힙을 가질 수 있다. 각 힙은 각자의 헤더를 가진다. 왜 여러 개의 힙이 필요한가? 모든 스레드 arena는 오직 하나의 힙만을 가지고 시작하지만, 힙 영역의 공간이 부족해지는 경우, arena에 새로운 힙(인접하지 않은 영역)을 할당해주어야 한다. 

이런 힙 영역은 어떤 arena가 관리하고 있는지, 힙 영역의 크기가 어느정도인지, 이전에 사용하던 힙 영역의 정보가 어디에 있는지를 저장할 필요가 있다.

 

이런 정보를 저장하기 위한 구조체가 바로 위 구조체인 heap_info이며, 힙에 대한 정보를 저장하기 때문에

Heap_Header 라고도 한다. 

 

 

malloc_state 구조체(arena_Header)

1.struct malloc_state
2.{
3.  /* Serialize access.  */
4.  mutex_t mutex;
5. 
6.  /* Flags (formerly in max_fast).  */
7.  int flags;
8. 
9.  /* Fastbins */
10.  mfastbinptr fastbinsY[NFASTBINS];
11. 
12.  /* topchunk의 base address */
13.  mchunkptr top;
14. 
15.  /* 가장 최근의 작은 요청으로부터 분리된 나머지 */
16.  mchunkptr last_remainder;
17. 
18.  /* 위에서 설명한대로 pack된 일반적인 bins */
19.  mchunkptr bins[NBINS * 2 - 2];
20. 
21.  /* Bitmap of bins */
22.  unsigned int binmap[BINMAPSIZE];
23. 
24.  /* 연결 리스트 */
25.  struct malloc_state *next;
26. 
27.  /* 해제된 아레나를 위한 연결 리스트 */
28.  struct malloc_state *next_free;
29. 
30.  /* 현재 Arena의 시스템으로부터 메모리 할당  */
31.  INTERNAL_SIZE_T system_mem;
32.  INTERNAL_SIZE_T max_system_mem;
33.};

Arena Header - 단일 스레드 arena는 여러 개의 힙을 가질 수 있지만, 이러한 모든 힙에 대해서는 오직 하나의 arena header만이 존재한다. Arena header는 bin, top chunk, last remainder chunk 등에 대한 정보를 가진다.

Heap_Header 에서는 단순히 힙 영역에 대한 정보만을 저장하였다. arena는 힙 영역에 대한 정보 중에서도 어떤 부분을 사용하면 되는지를 관리하기 때문에, 이를 알고 있을 필요가 있기 때문에

 

 

malloc_chunk 구조체(Chunk Header)

1.struct malloc_chunk {
2. 
3.  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
4.  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
5. 
6.  struct malloc_chunk* fd;         /* double links -- used only if free. */
7.  struct malloc_chunk* bk;
8. 
9.  /* large block에서만 사용하고 해당 bin list의 크기 순서를 나타냄  */
10.  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
11.  struct malloc_chunk* bk_nextsize;
12.};

malloc_chunk - Chunk Header - 힙은 사용자의 요청을 기반으로 다수의 청크로 분열된다. 그리고 각 청크는 각자의 청크 헤더를 가진다.

 

Arena

출처 : http://core-analyzer.sourceforge.net/index_files/Page335.html

ptmalloc2는 각 스레드가 서로 간섭하지 않고, 서로 다른 메모리 영역에 액세스 할 수 있게 한다.

이러한 메모리 영역을 "Arena" 라고 한다.

 

각 Arena는 하나 이상의 힙 메모리를 얻는다.

• main arena는 프로그램의 초기 힙을 사용 (.bss 등 직후 시작).
• 추가 Arena는 mmap를 통해 힙에 메모리를 할당하고, 이전 힙이 소모되면 더 많은 힙을 힙목록에 추가.

 

Arena는 heap 메모리에서 할당된 chunk들을 관리한다.

• Arena에서 관리되는 chunk들은 응용 프로그램에서 사용 중이거나 사용이 가능한 chunk들이다.
• Free chunk는 크기와 히스토리에 따라 분류되어 arena에 저장된다.
• 할당자는 arena에서 할당 요청을 충족하는 chunk를 신속하게 찾을 수 있다.

 

 

main arena

메인 쓰레드로써 생성되었기 때문에 Main Arena로 부른다.

 

Main Arena는 하나의 힙만 가질 수 있으며 heap_info구조체를 가질 수 없다. 이때, 하나의 힙은 여러 개의 chunk로 나누어지며 각 chunk는 각각의 header를 갖는다.

 

 

subarena

새로운 스레드가 생성되어 힙 작업을 수행하고자 할 때 다른 스레드를 기다리는 것을 줄이기 위해 새로운 Arena를 생성하게되는데 이를 Sub Arena라고 부르며 sbrk를 사용하는 Main Arena와 달리 mmap()을 통해 새로운 힙 메모리에 할당받으며 mprotect()를 사용하여 확장한다.

 

또한, Sub Arena는 Main Arena와 달리 여러 개의 서브 힙과 heap_info구조체를 가질 수 있다.

 

 

 

참고
https://wogh8732.tistory.com/178
https://tribal1012.tistory.com/78
https://www.lazenca.net/pages/viewpage.action?pageId=51970061
dreamhack Heap Allocator Exploit
https://rninche01.tistory.com/entry/heap2-glibc-malloc1-feat-Arena