Post

ptmalloc2

Posted
By hogbal 10 min read

리눅스에서 동적 메모리 할당과 해제시 Heap 영역을 사용해서 할당합니다. 이 때, 사용하는 것이 ptmalloc2라는 Memory Allocator입니다. 해당 포스트에서 ptmalloc2에 대해서 자세하게 설명하겠습니다. 추가적으로, glibc 버전 별 보호기법에 대해서 간략하게 설명하겠습니다.

ptmalloc2 객체

ptmalloc2의 객체에는 다음과 같은 것들이 있습니다.

  • Chunk
  • bin
  • tcache
  • arena

여기서 tacahe는 glibc 2.26 버전부터 등장한 개념입니다.

객체의 구성요소를 하나씩 자세하게 설명드리겠습니다.

Chunk

우선 Chunk는 다음의 그림과 같이 할당됐을 때와 해제됐을 때 구조가 다릅니다. 우선 할당된 Chunk부터 살펴보겠습니다.

0할당된 Chunk

할당된 Chunk는 다음의 필드를 가지고 있습니다.

  • prev_size : 이전 Chunk의 크기를 나타냅니다.
  • size : 현재 Chunk의 크기를 나타냅니다.
  • p : 해당 Chunk가 사용중인지 판별하는 값입니다.
  • Data : 실질적으로 사용자가 입력한 Data가 들어가는 공간입니다.

다음으로 해제된 Chunk입니다.

1해제된 Chunk

해제된 Chunk는 다음의 필드를 가지고 있습니다.

  • prev_size : 이전 Chunk의 크기를 나타냅니다.
  • size : 현재 Chunk의 크기를 나타냅니다.
  • p : 해당 Chunk가 사용중인지 판별하는 값입니다.
  • fd : 연결리스트에서 다음 Chunk를 가리킵니다.
  • bk : 연결리스트에서 이전 Chunk를 가리킵니다.
  • Remain Data : 해제되고 남은 Data입니다.

💡 해제된 Chunk는 할당된 Chunk의 Data 시작부분에서 0x10 크기만큼 새로운 필드로 사용합니다.

bin

bin은 문자 그대로, 사용이 끝난 청크들이 저장되는 객체입니다. 메모리의 낭비를 막고, 해제된 Chunk를 빠르게 재사용할 수 있게 합니다. bin의 종류는 다음과 같습니다.

  • small bin
    • 62개의 small bin이 존재
    • 32byte~1024byte, 같은 크기의 Chunk만 저장
    • index가 증가하면 저장되는 Chunk의 크기는 16byte씩 증가
    • 이중 연결 리스트
    • FIFO
  • fast bin
    • 10개의 fast bin이 존재
    • 32byte~176byte
    • 단일 연결 리스트
  • large bin
    • 63개의 large bin이 존재
    • 1024byte 이상
    • Chunk의 크기를 내림차순으로 저장
    • 이중 연결 리스트
  • unsorted bin
    • 1개의 unsorted bin이 존재
    • fast bin에 들어가지 않는 모든 Chunk는 해제되었을 때 unsorted bin에 저장
    • 원형 이중 연결 리스트
    • small bin 크기에 해당하는 Chunk를 할당 요청하면, ptmalloc2은 fast bin 또는 small bin을 탐색한 뒤 unsorted bin을 탐색
    • large bin의 크기에 해당하는 Chunk는 unsorted bin을 먼저 탐색
    • 해당 과정에서 탐색된 Chunk는 적절한 bin에 배치

arena

arena는 fastbin, smallbin, largebin 등의 정보를 모두 담고 있는 객체입니다. 멀티 스레드에서 ptmalloc2는 레이스 컨디션을 막기 위해 arena에 접근할 때 arena에 락을 적용합니다. 그런데 이 방식을 사용하면 레이스 컨디션은 막을 수 있지만, 반대로 병목 현상을 일으킬 수 있습니다.

ptmalloc은 이를 최대한 피하기 위해 최대 64개의 arena를 생성할 수 있게 하고 있습니다. arena에 락이 걸려서 대기해야 하는 경우, 새로운 arena를 생성해서 이를 피할 수 있습니다. 그런데, 생성할 수 있는 갯수가 64개로 제한되어 있으므로 과도한 멀티 스레드 환경에서는 결국 병목 현상이 발생합니다. 그래서 glibc 2.26에서는 tcache를 추가적으로 도입했습니다.

💡 tcache는 arena에서 발생하는 병목 현상을 해결하기 위해 나타난 개념으로 glibc 2.26부터 도입됨!

tcache

tcache는 thread local cache의 약자입니다.

  • 각 스레드 별로 64개의 tcache
  • fast bin과 마찬가지로 단일 연결 리스트이며 LIFO
  • 32byte~1040byte

💡 tcache가 아닌 다른 bin들이 사용되는 경우는 tcache가 가득찼을 경우에 bin을 사용해서 Chunk를 관리합니다.

tcache는 각 스레드가 고유하게 갖는 캐시이기 때문에, ptmalloc은 레이스 컨디션을 고려하지 않고 tcache에 접근할 수 있습니다.

보호기법

glibc에 적용되어 있는 heap과 관련된 보호기법에 대해서 설명하겠습니다. 해당 포스트에 새로운 기법이 나올때마다 추가할 예정입니다.

tcache DFB

tcache가 처음 도입된 glibc 2.26 버전에서는 Dobule Free Bug에 대한 보호기법이 존재하지 않았습니다. 하지만 glibc 2.29 버전부터 DFB에 대한 보호기법이 적용되었습니다.

bypass?

해당 보호기법을 bypass할 수 있는 방법이 존재합니다. tcache Chunk가 생성될 때 e→key에 tcache를 삽입하고, 해제할때 해당 청크의 e→key가 tcache 포인터인지 비교하고 같은 값이면 에러가 출력되게 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);
  assert (tc_idx < TCACHE_MAX_BINS);

  /* Mark this chunk as "in the tcache" so the test in _int_free will
     detect a double free.  */
  **e->key = tcache;**

  e->next = tcache->entries[tc_idx];
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

위의 방법으로 검증을 하기 때문에 e→key의 값을 overwrite할 수 있다면 우회가 가능합니다.

safe linking

glibc 2.32부터 safe linking이라는 개념이 도입되었습니다. fast bin과 tcache bin 연결리스트를 구성하는 fd, next 포인터를 쉽게 변조하지 못하게 xor 인코딩해서 저장하는 보호 기법입니다.

2heap gdb 1

위의 그림처럼 해제된 Chunk의 fd 값이 heap영역의 주소가 아닌 다른 영역의 주소가 들어가 있는 것을 확인할 수 있습니다.

bypass?

다만, 해당 보호기법은 bypass할 수 있는 방법이 존재합니다. 다음과 같은 tcache bin이 존재한다고 가정합니다.

1

Tcachebins[idx=1, size=0x30, count=2] ←  Chunk(addr=0x5555555592a0)  ←  Chunk(addr=0x5555555592d0)

이때, tcache bin의 첫번째 Chunk인 0x5555555592a0의 fd는 다음 Chunk인 0x5555555592d0를 가리켜야되지만 safe linking때문에 아래와 같은 값을 가지고 있습니다.

3heap gdb 2

이럴 경우 다음의 코드를 이용해서 heap base 주소를 구할 수 있습니다.

1
2
3
4
5
6
7

def decrypted(fd):
	L = fd >> 36
	for i in range(3):
		temp = (fd >> (36-(i+1)*8)) & 0xff
		element = ((L >> 4) ^ temp) & 0xff
		L = (L << 8) + element
	return L << 12

위의 예시를 이용해서 베이스를 구하면 아래와 같이 구해지는 것을 확인할 수 있습니다. 또한 출력되는 값을 12만큼 shift 연산하면 heap safe의 값이 됩니다.

1
2
3
4

>>> hex(decrypted(0x000055500000c789))
'0x555555559000'
>>> hex(0x555555559000 >> 12)
'0x555555559'

해당 값을 이용해서 원하는 주소로 fd를 변조할 수 있습니다. 예를 들어 main의 rbp를 overwrite한다면 아래와 같이 할 수 있습니다.

1

chunk_fd = main_rbp ^ heap_safe

hook removed

glibc 2.34 버전부터 __malloc_hook, __realloc_hook, __memalign_hook, __free_hook이 전부 삭제되었습니다. 따라서, hook overwrite이 불가능합니다.

pwnable
ptmalloc2 heap tcache bin
This post is licensed under CC BY 4.0 by the author.