PWNABLE] Heap Basics - Bin

노션으로 옮김·2020년 4월 17일

SYSTEM

Study

목록 보기

21/33

개요

세부정보와 내용은 glibc 버전 별로 상이할 수 있으며, 본 포스팅에서는 glibc-2.27을 로드한 환경에서 테스트하였다.

Bin

Bin이란 힙 메모리에서 할당/해제되는 청크들을 관리하기 위한 알고리즘을 뜻한다.

종류

간략히 전체 타입을 확인한다.

1. Tcache bin (added with glibc 2.26)

for any chunks <= 0x408 bytes in size.
singly linked.
Each tcache bin stores chunks of the same size.
Each tcache bin has a max limit of 7 chunks that it can store.

2. Fast bin

for any chunks <= 0x60 bytes in size.
singly linked.
There are 10 fast bins.

3. Small bin

for any chunks <= 0x200 bytes in size.
doubly linked.

4. Large bin

for any chunks > 0x200 bytes
doubly linked.

Tcache Bin

tcache bin은 glibc 2.26부터 추가된 개념이다.

소스

glibc 소스에서 구조체를 확인해보자.

/* We overlay this structure on the user-data portion of a chunk when
   the chunk is stored in the per-thread cache.  */
# define TCACHE_MAX_BINS	64
typedef struct tcache_entry
{
  struct tcache_entry *next;
} tcache_entry;

/* There is one of these for each thread, which contains the
   per-thread cache (hence "tcache_perthread_struct").  Keeping
   overall size low is mildly important.  Note that COUNTS and ENTRIES
   are redundant (we could have just counted the linked list each
   time), this is for performance reasons.  */
typedef struct tcache_perthread_struct
{
  char counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

static __thread bool tcache_shutting_down = false;
static __thread tcache_perthread_struct *tcache = NULL;

위에서 사용되는 구조체는 다음의 그림으로 표현될 수 있다.

tcache_entry가 다음 청크의 포인터만 가지고 있다는 것, tcache_perthread_struct는 전체 tcache list를 관리한다는 것을 기억하자.

다음은 사용되는 함수이다.

tcache_put (mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);
  assert (tc_idx < TCACHE_MAX_BINS);
  e->next = tcache->entries[tc_idx];
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

/* Caller must ensure that we know tc_idx is valid and there's
   available chunks to remove.  */
static __always_inline void *
tcache_get (size_t tc_idx)
{
  tcache_entry *e = tcache->entries[tc_idx];
  assert (tc_idx < TCACHE_MAX_BINS);
  assert (tcache->entries[tc_idx] > 0);
  tcache->entries[tc_idx] = e->next;
  --(tcache->counts[tc_idx]);
  return (void *) e;
}

tcache_get()은 malloc(), tcache_put()은 free()와 매칭된다

특징

1. It follows a LIFO structure.
2. each tcache bin has a maximum of 7 chunks that it can store.
3. tcache bin takes priority over all other bins (i.e if there is a chunk of the same size in any of the other bins, they are ignored as the tcache bin is given priority)
4. Chunks stored in tcache bin do not consolidate together

여기서 가장 중요한 특징은 3번이다.
관리범위 안의 청크가 free되었을 때 tcache bin에 우선적으로 저장된다.
tcache bin이 가득 찼을 경우, 그 다음 bin에 저장하게 된다.

Unsorted Bin

최적화된 처리를 위한 임시 free 청크 저장소라고 생각하면 된다.

특징

익스플로잇을 위해, 그리고 취약점 이해를 위해 가장 중요한 내용이므로 하나씩 살펴보겠다.

1. unsorted bin은 free되는 청크가 붙어있을 경우 이를 병합하여 하나의 청크로 만든다.

다음과 같은 코드가 있을 때(free된 청크는 모두 unsort bin에 저장된다고 가정하자)

ptr = malloc(0x80);
ptr2 = malloc(0x80);

free(ptr);
free(ptr2);

ptr이 free 되면 unsort bin에 저장된 청크 크기는 0x80일 것이다.(단순화 시켜서)

다음으로 ptr2이 free 되는데, 앞서 저장되어 있던 ptr 청크와 연결되있는 청크이므로 이를 병합시킨다.
unsort bin에 저장된 청크 크기는 0x80 + 0x80으로 증가된다.

2. unsorted bin에 저장되는 청크에는 fk, bk 주소가 남게 되며, 이 주소는 둘다 unsorted bin을 가리키게 된다.

직접 확인해보자.

3. unsorted bin에 청크가 저장되는 시점은 tcache bin이 가득차있을 때이다.

예제로 확인해보자.

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

int main(void)
{
	unsigned long *chunks[8];

	// Allocate 8 chunks of size 0x80
	for (int i = 0; i < 8; i++)
	{
		chunks[i] = malloc(0x80);
	}

	// Allocate one more chunk to prevent the unsorted bin chunk from being consolidated
	// with the top chunk after it's freed
	malloc(0x80);

	// Free 7 of them to fill up the 0x80 sized tcache bin
	for (int i = 0; i < 7; i++)
	{
		free(chunks[i]);
	}

	// The next free will go into the unsorted bin as the tcache bin is full
	free(chunks[7]);

	// Print out the forward pointer of the last freed chunk by emulating a UAF vulnerability
	// This will point into libc
	printf("0x%lx\n", *chunks[7]);
}

malloc()을 총 9번하였다.

free시킬 8개의 청크와, 병합방지용의 dummy 청크이다.

병합방지

힙 메모리에서 가장 뒤에 할당된 청크의 바로 뒤 영역을 top chunk라고 한다.

만약 가장 뒤에 할당된 청크가 free되면 이 청크는 bin에 저장되는 것이 아닌 top chunk와 합쳐지게 된다.

dummy청크 없이 8개를 할당 및 해제할 경우, 7개까지 청크가 free되었을 때 이미 tcache bin이 가득찬 상태이지만 8번째 청크가 free되어도 이것이 unsorted bin에 저장되지 않고 마지막 top chunk와 합쳐지게 된다.

결국 마지막 코드에서 8번째 청크에 저장된 바이트를 읽었을 때, 목적과는 다르게 fd의 주소값이 출력되지 않을 것이다.

결과를 확인하자.

root@j-VirtualBox:/work/tmp/pico/gho# gcc -o test3 test3.cpp -fpermissive
test3.cpp: In function ‘int main()’:
test3.cpp:11:21: warning: invalid conversion from ‘void*’ to ‘long unsigned int*’ [-fpermissive]
   chunks[i] = malloc(0x80);
               ~~~~~~^~~~~~
root@j-VirtualBox:/work/tmp/pico/gho# ./test3
0x7f9bbe691ca0