tcache의 구조 및 함수들의 동작 & Double Free Bug 개요

Double Free Bug & Duplicated Free List의 정의

-Double Free Bug란 임의의 청크를 두 번 혹은 그 이상 free 시킬 수 있는 버그를 뜻한다.

-Duplicated Free List란 free list(tcache 또는 bins)에 임의의 청크가 중복해서 들어있는 것을 뜻한다.

-Double Free Bug를 통해 duplicated free list를 만들 수 있다면 우리는 임의의 청크를 우리가 원하는 주소에 할당하여 그 청크를 통해 그 주소에 있는 데이터 값을 읽거나, overwrite 할 수 있게 된다.

 

*Double Free Bug가 발생하는 가장 주된 이유는 바로 Stage 11에서 언급됐던 Dangling Pointer 때문이다.

 

이 글에서는 tcache에 대한 Double Free Bug에 대해 자세히 다룰 것이다.

따라서 bins와 관련된 Double Free Bug에 대해서는 꼭 따로 공부해보길 바란다.

 

 

tcache 청크의 구조와 함수

-tcache는 glibc 2.26버전부터 도입돼, glibc 2.29버전 이전까지는 Double Free에 관한 보호 기법이 존재하지 않았다.

-tcache는 LIFO(Last-In-First-Out) 방식으로 동작한다

 

glibc 2.26버전의 tcache_entry

// GLIBC 2.26
typedef struct tcache_entry
{
  struct tcache_entry *next;
} tcache_entry;

tcache_entry란 tcache의 청크들이 갖는 구조이다. tcache의 청크에는 fd의 위치에 next라는 포인터 변수가 존재하고 bk는 존재하지 않음을 알 수 있다. glibc 2.26버전의 tcache 청크의 구조를 그림으로 그려보자면 다음과 같을 것이다.

 

그러나 glibc 2.29 이후 버전부터는 Double Free Bug와 관련된 보호 기법들이 추가로 적용되어 tcache에 관한 내용들이 변경되었다.

 

 

이후부터는 모두 glibc 2.29 이후 버전부터 추가된 내용에 관한 것들이다.(***다만 glibc 2.27 이후 버전에도 해당 내용이 패치되었다는 내용이 있다. 따라서 glibc 버전만 보고 판단할 것이 아니라, 해당 환경에서 이 내용이 패치되어 있는지를 동작을 통해 확인하는 것이 가장 정확하겠다***)

 

tcache_entry

typedef struct tcache_entry {
  struct tcache_entry *next;
+ /* This field exists to detect double frees.  */
+ struct tcache_perthread_struct *key;
} tcache_entry;

설명: double free를 감지하기 위해 tcache_entry에 key라는 변수가 추가되었다. 이 key라는 변수가 어떻게 double free를 감지하는 데 쓰이는지는 잠시 후에 설명할 것이다. glibc 2.29 이후 버전의 tcache 청크의 구조를 그림으로 나타내면 다음과 같을 것이다.

 

tcache_perthread_struct

typedef struct tcache_perthread_struct
{
  char counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

-tcache_perthread_struct는 tcache list를 관리하는 구조체이다.

-counts는 tcache에 몇 개의 청크가 저장되어 있는지를 나타내는 변수이다.

-entries에는 tcache_entry의 주소가 저장된다 

 

 

tcache_put

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]);
}

-tcache_put은 해제한 청크를 tcache에 추가하는 함수이다.

-tcache_put()은 해제되는 청크의 key에 tcache라는 값을 넣도록 되어있다. 여기서 tcache라는 값은 tcache_perthread_struct라는 구조체를 가리킨다.

-tcache에 추가될 청크의 next에 현재 tcache에 있는 청크의 주소를 넣은 후, tcache에 추가될 청크를 tcache에 추가한다.

-tcache->entries에는 tcache에 추가될 청크의 tcache_entry 주소가 담긴다 

-그런 뒤 tcache(tcache_perthread_struct를 가리킴)의 count를 증가시켜준다(여기서 count란 변수는 tcache에 있는 청크의 개수를 나타내준다. tcache에 청크가 추가되면 count는 +1이 되고, tcache에서 청크가 빠져나가면 count는 -1이 된다. 그리고 count의 값이 0이라면, ptmalloc은 청크를 할당해줄 때 tcache를 참조하지 않는다.)

 

 

tcache_get

tcache_get (size_t tc_idx)
   assert (tcache->entries[tc_idx] > 0);
   tcache->entries[tc_idx] = e->next;
   --(tcache->counts[tc_idx]);
+  e->key = NULL;
   return (void *) e;
 }

tcache_get은 tcache에 있는 청크를 할당해줄 때 사용되는 함수이다.

-next가 가리키는 청크를 할당될 청크가 있는 자리에 위치시키고, count를 -1 시킨다.

 

 

_int_free

_int_free (mstate av, mchunkptr p, int have_lock)
 #if USE_TCACHE
   {
     size_t tc_idx = csize2tidx (size);
-
-    if (tcache
-       && tc_idx < mp_.tcache_bins
-       && tcache->counts[tc_idx] < mp_.tcache_count)
+    if (tcache != NULL && tc_idx < mp_.tcache_bins)
       {
-       tcache_put (p, tc_idx);
-       return;
+       /* Check to see if it's already in the tcache.  */
+       tcache_entry *e = (tcache_entry *) chunk2mem (p);
+
+       /* This test succeeds on double free.  However, we don't 100%
+          trust it (it also matches random payload data at a 1 in
+          2^<size_t> chance), so verify it's not an unlikely
+          coincidence before aborting.  */
+       if (__glibc_unlikely (e->key == tcache))
+         {
+           tcache_entry *tmp;
+           LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
+           for (tmp = tcache->entries[tc_idx];
+                tmp;
+                tmp = tmp->next)
+             if (tmp == e)
+               malloc_printerr ("free(): double free detected in tcache 2");
+           /* If we get here, it was a coincidence.  We've wasted a
+              few cycles, but don't abort.  */
+         }
+
+       if (tcache->counts[tc_idx] < mp_.tcache_count)
+         {
+           tcache_put (p, tc_idx);
+           return;
+         }
       }
   }

_int_free 함수는 free를 호출하면 호출되는 함수이다.

-count 변수가 7보다 작다면 tcache_put 함수를 호출하여 tcache에 청크를 담는다.

-20번째 줄을 보면 Double Free 버그를 탐지하는 코드가 glibc 2.29버전부터 추가되었음을 확인할 수 있다

 if (__glibc_unlikely (e->key == tcache))
+         {
+           tcache_entry *tmp;
+           LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
+           for (tmp = tcache->entries[tc_idx];
+                tmp;
+                tmp = tmp->next)
+             if (tmp == e)
+               malloc_printerr ("free(): double free detected in tcache 2");
+           /* If we get here, it was a coincidence.  We've wasted a
+              few cycles, but don't abort.  */
+         }

"free할 chunk의 key == tcache"이면 double free가 일어났다고 간주하고, 프로그램을 abort 시킨다.

-20번째 줄 외의 double free 보호 기법은 없으므로 20번째 줄의 조건문만 우회할 수 있다면 tcache에 Double Free를 일으킬 수 있다.

즉, 해제된 청크의 key 값을 1비트만큼이라도 변경시킨다면 이 보호기법을 우회하여 tcache에 Double Free를 발생시킬 수 있다.

 

지금까지의 내용이 tcache poisoning 기법을 이해하기 위한 기초적인 내용들이다.

위 내용을 충분히 숙지한다면 tcache poisoning을 이용한 exploit을 이해하는 데 큰 무리는 없을 것이다.