[Heap] Background : Tcache

728x90

tcache를 알기 전에 왜 tcache가 도입되었는지 배경을 살펴보자. 이전에 우리는 'Arena'라는 개념을 알아야 한다. 이에 대해 포스트를 작성할 예정이지만 여기서는 간단히만 arena가 무엇인지 살펴보고 tcache로 넘어가자.

Arena란?

'멀티스레드' 환경을 지원하기 위해 도입된 것으로, arena는 각 스레드의 freelist와 chunk들을 관리하는 malloc_state 구조체이다.
기존 dlmalloc은 멀티스레드 환경을 지원하지 않았기에 동시에 두 스레드가 malloc을 호출할 경우, 한 스레드는 다른 스레드의 malloc이 끝날 때까지 그저 기다려야만 했다. 하지만 ptmalloc에서는 각각의 스레드가 분배된 힙 영역을 사용하고 freelist 또한 분배되어 사용할 수 있게 하여 즉시 할당할 수 있게되어 위 문제를 해결할 수 있었다. (참고로 이렇게 스레드의 유지를 위해 분배된 힙과 freelist data structure의 행동을 per thread arena라고 부른다.)

메인 스레드는 main arena라는 아레나를 가지고 다른 sub thread들은 다른 아레나들에 할당된다. 하지만 스레드 별로 아레나를 할당받는 것은 아니다. 그렇게 되면 자원의 손실이 커지기 때문에 아레나의 수는 현재 core의 수에 기반한다.
그래서 아레나의 수를 최대치만큼 다 사용하였다면 하나의 아레나에 여러 스레드가 들어갈 수 있게 된다. 여기서 Heap 데이터의 부정 접근 혹은 변경이나 레이스 컨디션 같은 문제점이 발생할 수 있게 된다. 그래서 tcache라는 개념이 도입된 것이다.

Tcache란?

tcache(Thread local Caching)는 Thread 별로 가지는 cache 데이터들이라고 볼 수 있다. 위에서 일정 수 이상 넘어가면 스레드가 아레나를 공유하여 여러 문제가 생겼다면, tcache는 스레드 별로 존재한다! 즉 tcache도 멀티 스레드 환경에서 힙 동작을 효율적이고 빠르게 수행할 수 있기 위해 도입된 개념이다.

tcache는 작은 크기의 메모리 할당이 필요한 경우 Arena를 참조하지 않고 바로 tcache에서 메모리를 찾아 할당할 수 있게 해준다. 그래서 메모리 할당 속도가 높아진다.

특징 및 구조

/* We want 64 entries.  This is an arbitrary limit, which tunables can reduce.  */
# define TCACHE_MAX_BINS 64
 
/* This is another arbitrary limit, which tunables can change.  Each
   tcache bin will hold at most this number of chunks.  */
# define TCACHE_FILL_COUNT 7

각 스레드 별로 64개의 tcache bin이 존재한다. 각 빈 안에는 7개의 청크가 들어갈 수 있다.

gdb에서 heapinfo 명령어를 사용하면 맨 아래 tcache 정보가 출력된다.

위에 출력된 entry 배열 요소의 개수는 64개가 존재한다. 각각의 줄이 하나의 빈이 되는 것이다.

각 bin에는 7개의 동일한 크기의 청크가 존재한다 (한 bin 당 담당하는 청크 사이즈가 다르다!!)
- 32bit system : 12 ~ 516byte 범위의 청크 사이즈
- 64bit system : 24 ~ 1032byte 범위의 청크 사이즈
LIFO, Single-Linked List 사용
병합 x
fastbin, unsorted bin, small bin에 저장되어 있는 free 청크를 재할당하는데 사용되면 나머지 free 청크들은 tcache로 옮겨진다.

tcache_entry

/* We overlay this structure on the user-data portion of a chunk when
   the chunk is stored in the per-thread cache.  */
typedef struct tcache_entry
{
  struct tcache_entry *next; //다음 tcache_entry를 가리키는 next 포인터
  
  /* This field exists to detect double frees.  */
  uintptr_t key; //DFB 막기위해 도입
} tcache_entry;

next포인터로 다음 동일한 크기의 free chunk를 연결
- 다음 tcache_entry의 next(데이터 시작부분)을 가리킴
사이즈나 prev_size 부분 없고 바로 페이로드 부분(데이터 영역)부터 시작
fastbin의 fd가 다음 청크의 prev_inuse를 가리켰다면 tcache_entry의 next는 다음 청크의 next를 가리킴
key는 DFB를 막기 위해 도입됨 -> [Heap] Exploitation : tcache dup 참고

tcache_perthread_struct

스레드 별로 고유하게 하나만 존재하는 구조체. tcache 자체를 관리함. arena가 빈들을 관리하는 것처럼 얘는 tcache bin들을 관리하는 느낌인 것 같음(?)

/* 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
{
  uint16_t counts[TCACHE_MAX_BINS]; //각 tcache bin에 들어있는 entry들의 개수로 이루어진 배열
  tcache_entry *entries[TCACHE_MAX_BINS]; //각 tcache bin이라고 생각하면 될듯?
} tcache_perthread_struct;
 
static __thread bool tcache_shutting_down = false;
static __thread tcache_perthread_struct *tcache = NULL;
 
/* Process-wide key to try and catch a double-free in the same thread.  */
static uintptr_t tcache_key;

전체적인 tcache list를 관리하는 구조체
counts[TCACHE_MAX_BINS] : entries배열의 single linked list로 연결되어 있는 청크의 개수 기록(single list당 최대 7개의 청크 제한)
entries[TCACHE_MAX_BINS] : fastbin과 같이 single linked list의 구조(+LIFO)로 동일한 크기의 free chunk들로 연결되어 있음 (일반 빈들이랑 비슷한 역할을 하는 것 같다..!)
tcache들은 다른 bin처럼 arena에서 관리되는 것이 아니라 tcache_perthread_struct에서 관리됨!!

출처 :&nbsp;https://rninche01.tistory.com/entry/heap5-tcacheThread-local-Caching

Debugging

디버깅을 통해 tcache가 어떻게 구성되어있는지 살펴보도록하자.
간단한 코드를 통해서 0x20,0x30,0x40짜리 청크를 malloc으로 할당하고 다시 해제해주었다.

각각의 청크가 entry 배열에 하나씩 들어간 것을 볼 수 있다. tcache_entry[i]뒤에있는 민트색 숫자는 tcache_perthread_struct의 count에 해당한다.

tcache_perthread_struct 구조체를 다시 확인해보자.

typedef struct tcache_perthread_struct
{
  uint16_t counts[TCACHE_MAX_BINS]; //각 tcache bin에 들어있는 entry들의 개수로 이루어진 배열
  tcache_entry *entries[TCACHE_MAX_BINS]; //각 tcache bin이라고 생각하면 될듯?
} tcache_perthread_struct;

uint16_t는 하나당 2byte이고, 배열의 원소 개수는 64이므로 총 128byte(0x80byte)를 차지한다.
또한 tcache_entry 포인터 하나의 크기는 8byte이므로 총 64*8=528byte(0x210byte)를 차지한다.
따라서 tcache_perthread_struct는 총 0x290byte를 차지한다.
디버깅해서 이게 진짠지 확인해보자!

print tcache로 해당 구조체의 주소를 확인할 수 있다.
구조체 주소는 0x555555559010이지만 0x10을 빼줘야 청크 헤더까지 포함해서 출력할 수 있다.

맨 위 청크 헤더에서 청크 사이즈가 0x290임을 확인할 수 있다(1은 flag)
또한 현재 count[0]=0, count[1]=1, count[2]=1, count[3]=1인데 그 값이 count가 있는 빨간 상자에 적혀있다.
그리고 entry 배열에 entry[1],[2],[3] 빈의 첫 tcache_entry 주소인 0x00005555555592a0, 0x00005555555592d0, 0x0000555555559310가 적혀있다!!

tcache 관련 주요 함수

tcache_put

tcache에 새로운 요소 넣는 함수이다. 즉 청크가 free될 때!
glibc 2.23에는 key가 없었지만 패치 후 Double Free를 방지하기 위해 key멤버가 추가되었다. 이 key에서는 tcache의 주소를 넣는다. 자세한 내용은 여기 참고 바람-> [Heap] Exploitation : tcache dup

/* Caller must ensure that we know tc_idx is valid and there's room
   for more chunks.  */
static __always_inline void

tcache_put (mchunkptr chunk, size_t tc_idx) //tcache에 원소 집어넣는 함수
{   tcache_entry *e = (tcache_entry *) chunk2mem (chunk); //청크를 tcache_entry 구조체에 맞게 캐스팅
 
  /* Mark this chunk as "in the tcache" so the test in _int_free will
     detect a double free.  */
  e->key = tcache_key; //e의 key에 tcache_key(아마 tcache_perthread_struct의 주소) 대입
 
  e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]); //현재 엔트리 맨 앞에있는 요소에 연결
  tcache->entries[tc_idx] = e; //entry[tc_idx]에 e 대입
  ++(tcache->counts[tc_idx]); //count 증가시킴
}

tcache_get

이 함수는 malloc 등을 통해서 청크를 할당할 때 tcache에서 알맞은 청크를 찾아 재할당하는 함수이다.
참고로 이 함수를 통해 key값이 NULL(0)이 되게 된다.

/* Caller must ensure that we know tc_idx is valid and there's
   available chunks to remove.  */
//tc_idx가 valid인지 확인하고 제거할 청크가 있는지 확인해야 한다.
static __always_inline void *
tcache_get (size_t tc_idx) //tc_idx를 인자로 넣어줌
{
  tcache_entry *e = tcache->entries[tc_idx]; //e에 tcache->entries[tc_idx] 할당
  if (__glibc_unlikely (!aligned_OK (e)))
    malloc_printerr ("malloc(): unaligned tcache chunk detected");
  tcache->entries[tc_idx] = REVEAL_PTR (e->next); //첫 원소에 e->next 대입
  --(tcache->counts[tc_idx]); //카운트 감소
  e->key = 0; //key에 0대입
  return (void *) e;
}

(주의) tc_idx가 valid인지 확인하고 count를 통해 제거할 청크가 있는지 확인해야 한다.
참고로 free할 때 사용하는 _int_free 함수에서 double free를 방지하기 위해 청크의 key가 tcache인지 확인한다. tcache인 경우 double free가 발생했다는 것을 의미하므로(왜냐하면 이미 free되었다면 tcache에 들어가 key가 tcache으로 설정되어있을 것이므로) 프로세스를 abort시키게된다.

(주의) count가 0이 되면 tcache에서 가져오지 않는다!!!!

(주의) count 값같은 거는 우리가 poisoning을 한다고 해서 바뀌는 것이 아님 tcache_get을 쓸 때 바뀌는 것 !!!

References

https://rninche01.tistory.com/entry/heap5-tcacheThread-local-Caching
02.tcache(Thread Local Cache )[Korean] - TechNote - Lazenca.0x0
https://blog.naver.com/yjw_sz/221481149348
https://jeongzero.oopy.io/2c5b7648-5f96-42c4-8366-300e7b5ebac4#2c5b7648-5f96-42c4-8366-300e7b5ebac4

'Linux Exploitation > Heap' 카테고리의 다른 글

[Heap] Exploitation : House of Spirit (0)	2023.10.03
[Heap] Exploitation : House of Force (5)	2023.09.30
[Heap] Exploitation : tcache dup (0)	2023.06.27
[Heap] Exploitation : fastbin dup & poisoning (1)	2023.06.16
[Heap] Exploitation : Poison NULL Byte (0)	2023.06.15