glibc 2.26 tcache 동작 분석 및 exploit (how2heap)

이번에 코드게이트 준비하다가 우연히 tcache dup 문제를 풀게 됐는데 한글 문서가 별로 없는것 같아서 glibc 분석 내용을 정리한다.

 

tcache(thread local caching)은 malloc과 free의 호출 횟수를 줄여 속도를 높이기 위해 고안되었다고 한다. 캐싱 작업을 통해 fastbin, unsortedbin 등등..이 불릴 일 없이 빠르게 처리하는 것 같다..

• tcache 구조체

xxxxxxxxxx
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 char tcache_shutting_down = 0;
static __thread tcache_perthread_struct *tcache = NULL;

tcache_entry 구조체는 tcache list를 관리하는 구조체이다. 오직 다음 tcache_chunk를 가르키는 포인터만을 가지고 있다.

 

tcache_perthread_struct 구조체는 tcache list를 총체적으로 관리하는 구조체이다. 배열로서 해당 tcache list의 count와 entries를 관리 한다.

 

tcache는 consolidate를 하지 않으며 때문에 prev_size와 inuse_bit도 셋팅하지 않는다.

tcache_chunk는 size와 next만 존재한다고 생각하면 된다.

 

발로 그려서 보기 힘들 수도 있지만 위 그림을 참고하면 된다.

• tcache 초기화

xxxxxxxxxx
static void
tcache_init(void)
{
  mstate ar_ptr;
  void *victim = 0;
  const size_t bytes = sizeof (tcache_perthread_struct);
​
  if (tcache_shutting_down)
    return;
​
  arena_get (ar_ptr, bytes);
  victim = _int_malloc (ar_ptr, bytes);
  if (!victim && ar_ptr != NULL)
    {
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }
​
​
  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);
​
  /* In a low memory situation, we may not be able to allocate memory
     - in which case, we just keep trying later.  However, we
     typically do this very early, so either there is sufficient
     memory, or there isn't enough memory to do non-trivial
     allocations anyway.  */
  if (victim)
    {
      tcache = (tcache_perthread_struct *) victim;
      memset (tcache, 0, sizeof (tcache_perthread_struct));
    }
​
}

tcache_perthread_struct를 처음에 할당해 준다.

 

• tcache 삽입

xxxxxxxxxx
/* Caller must ensure that we know tc_idx is valid and there's room
   for more chunks.  */
static void
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]);
}

tcache list에 chunk를 추가하는 함수이다.

들어온 chunk의 next에 이미 존재하는 tcache chunk를 넣은 후 그 자리에 들어온 chunk를 넣는다.

 

• tcache 제거

xxxxxxxxxx
/* Caller must ensure that we know tc_idx is valid and there's
   available chunks to remove.  */
static 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 list에서 chunk를 가져오는 함수이다.

tc_idx를 기준으로 next 청크를 현재 tc_idx로 넣고 요청한 chunk를 반환한다.

 

• tcache_put이 불리는 상황

  xxxxxxxxxx
  #if USE_TCACHE
    {
      size_t tc_idx = csize2tidx (size);
  ​
      if (tcache
      && tc_idx < mp_.tcache_bins // 64
      && tcache->counts[tc_idx] < mp_.tcache_count) // 7
        {
      tcache_put (p, tc_idx);
      return;
        }
    }
  

  • free: _int_free()에서 fastbin 코드가 실행되기 전 size와 count 검사를 통해 해당된다면 ( 유효한 주소인지, 유효한 사이즈인지에 대한 검사밖에 존재하지 않는다.. )

 

xxxxxxxxxx
      /* While we're here, if we see other chunks of the same size,
         stash them in the tcache.  */
      size_t tc_idx = csize2tidx (nb);
      if (tcache && tc_idx < mp_.tcache_bins)
        {
         mchunkptr tc_victim;
  
          /* While bin not empty and tcache not full, copy chunks over.  */
          while (tcache->counts[tc_idx] < mp_.tcache_count
             && (pp = *fb) != NULL)
        {
          REMOVE_FB (fb, tc_victim, pp);
          if (tc_victim != 0)
            {
              tcache_put (tc_victim, tc_idx);
                }
        }
        }

• malloc: fastbin이 return될 때 fastbin 내에 다른 chunk가 존재하고 tcache list가 비어 있을 때 fastbin의 chunk가 tcache list로 이동한다.
• malloc: smallbin도 동일하게 작동한다.

 

xxxxxxxxxx
        /* Fill cache first, return to user only if cache fills.
     We may return one of these chunks later.  */
        if (tcache_nb
      && tcache->counts[tc_idx] < mp_.tcache_count)
    {
      tcache_put (victim, tc_idx);
      return_cached = 1;
      continue;
    }

• malloc: unsortedbin도 동일하게 작동한다. 하지만 unsortedbin은 return_cached를 1로 셋팅한다. 이 의미는 tcache_get에서 확인할 수 있다.

 

• tcache_get이 불리는 상황

  xxxxxxxxxx
    /* int_free also calls request2size, be careful to not pad twice.  */
    size_t tbytes = request2size (bytes);
    size_t tc_idx = csize2tidx (tbytes);
  ​
    MAYBE_INIT_TCACHE ();
  ​
    DIAG_PUSH_NEEDS_COMMENT;
    if (tc_idx < mp_.tcache_bins
        /*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
        && tcache
        && tcache->entries[tc_idx] != NULL)
      {
        return tcache_get (tc_idx);
      }
    DIAG_POP_NEEDS_COMMENT;
  

  • _libc_malloc()에서 tc_idx 기준으로 tcache_list가 존재한다면 ( 보호 예외처리가 하나도 없다.. fake_chunk_size 만들 필요도 없을듯 )

 

xxxxxxxxxx
    /* If we've processed as many chunks as we're allowed while
   filling the cache, return one of the cached ones.  */
    ++tcache_unsorted_count;
    if (return_cached
    && mp_.tcache_unsorted_limit > 0
    && tcache_unsorted_count > mp_.tcache_unsorted_limit)
  {
    return tcache_get (tc_idx);
  }

• return_cached=1이며 tcache_unsorted_limit를 넘지 않는다면, 즉 unsortedbin에서 tcache list로 이동한 경우, tcache list의 top chunk를 가져오겠다는 말이다. unsortedbin 외 bin은 LIFO로 chunk를 가져온다.

 

xxxxxxxxxx
    /* If all the small chunks we found ended up cached, return one now.  */
    if (return_cached)
  {
    return tcache_get (tc_idx);
  }

• binning code 이후에 return_cached=1이라면

 

 

tcache 동작을 확인하기 위해 아래의 코드를 사용하였다.

xxxxxxxxxx
#include <stdio.h>
#include <stdlib.h>
​
#define MAX 20
​
char* buf[MAX];
int main()
{
        for(int i=0;i<MAX;i++)
        {
                buf[i] = malloc(0x20);
        }
        for(int i=0;i<MAX;i++)
        {
                free(buf[i]);
        }
​
        for(int i=0;i<7;i++)
        {
                buf[i] = malloc(0x20);
        }
​
        malloc(0x20);
        return 0;
}

tcache_init()으로 생성된 첫 번째 chunk를 확인해 보면 count와 entries가 저장되어 있는 것을 볼 수 있다.

 

위와 같이 entries에 tcache_entry들이 single linked-list 형태로 저장되어 있다.

 

위와 같은 tcache chunk의 형태를 확인할 수 있다.

 

tcache list를 모두 malloc한 후 fastbin에만 chunk가 남아 있는 상황이다.

 

이 상태에서 malloc을 하게 되면 7개의 chunk가 tcache list로 이동하는 것을 확인할 수 있다.

 

return_cached의 동작을 확인하기 위해 아래의 코드를 사용하였다.

xxxxxxxxxx
#include <stdio.h>
#include <stdlib.h>
​
#define MAX 20
​
char* buf[MAX];
int main()
{
        for(int i=0;i<MAX-2;i++)
        {
                buf[i] = malloc(0x200);
                malloc(0x100); // for preventing consolidate with top chunk
        }
        for(int i=0;i<MAX;i++)
        {
                free(buf[i]);
        }
​
        for(int i=0;i<7;i++)
        {
                buf[i] = malloc(0x200);
        }
​
        //malloc(0x20); // smallbin
        malloc(0x200);
​
        return 0;
}

위와 같이 unsortedbin에 bin chain이 구성되어 있는 상황에서 malloc(0x200)을 한다면 원래라면 unsortedbin에서 주소를 가져와야 한다. 일단 위 unsortedbin의 주소를 잘 기억해 두고..

 

성공적으로 malloc 후 chunk들이 tcache list로 넘어왔다. 어떤 주소가 할당됐는지 확인해 보자.

 

위 주소는 tcache list의 topchunk의 다음 주소이다. 원래라면 unsortedbin은 FIFO기 때문에 0x55555757B30 + 0x10이 RAX에 있어야 할터..

이유는 tcache list에 옮겨 둔 후 return_cached의 값이 1로 셋팅되고 tcache list에서 top chunk를 빼왔기 때문이다. ( 근데도 tcache list가 7개인 것은 for문을 돌아 다시 채웠기 때문인 것 같다. 확실하지 않음)

 

동일하게 주석을 지운 후 smallbin에서 실험해 보자.

return_cached를 셋팅하지 않기 때문에 0x555555757b50 + 0x10이 반환되야 할터

 

tcache list에 잘 들어 갔고..

 

예상과 동일하게 RAX에 0x555555757b50 + 0x10이 반환되었다.

 

• fastbin과 다른 점?

fastbin하고 겁나 비슷하네.. fastbin은 prev_size 위치를 가르키고 있으며 tcache는 data(next) 위치를 가르키고 있다. 또한 fastbin은 main arena가 관리하지만 tcache는 tcache_perthread_struct가 관리한다.

 

• tcache dup

xxxxxxxxxx
#include <stdio.h>
#include <stdlib.h>
​
int main()
{
        int *a = malloc(8);
​
        free(a);
        free(a);
​
        fprintf(stderr, "Next allocated buffers will be same: [ %p, %p ].\n", malloc(8), malloc(8));
​
        return 0;
}

기존 malloc은 fastbin에서 free시 top chunk를 검사하지만 tcache malloc은 보호가 하나도 없기 때문에 바로 double free bug를 일으켜 동일한 주소를 계속해서 할당받을 수 있다.

 

위와 같은 상황에서 malloc을 한다면 동일한 주소를 2번 할당받을 수 있다.

 

동일한 주소가 2번 할당되었다!

 

• tcache poisoning

xxxxxxxxxx
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
​
int main()
{
        size_t stack_var;
​
        intptr_t *a = malloc(128);
​
        free(a);
​
        a[0] = (intptr_t)&stack_var;
​
        intptr_t *b = malloc(128);
        fprintf(stderr, "2nd malloc(128): %p\n", b);
        return 0;
}

tcache chunk의 next를 원하는 주소로 바꿔 공격하는 기법이다. ( 이 상황에서는 스택 주소를 알아야 공격 가능 ) fastbin dup into stack같이 tcache dup이랑 같이 사용하면 될듯

 

스택 주소가 할당되었다!

 

• tcache house of spirit

xxxxxxxxxx
#include <stdio.h>
#include <stdlib.h>
​
int main()
{
        unsigned long long *a; //pointer that will be overwritten
        unsigned long long fake_chunks[10]; //fake chunk region
​
        fprintf(stderr, "This region contains one fake chunk. It's size field is placed at %p\n", &fake_chunks[1]);
​
        fake_chunks[1] = 0x40; // this is the size
        a = &fake_chunks[2];
​
        free(a);
​
        fprintf(stderr, "malloc(0x30): %p\n", malloc(0x30));
}

tcache의 free는 invalid pointer, invalid size 검사만이 존재하기 때문에 next chunk size를 설정해줄 필요가 없다는게 특징이다.

임의의 영역에 fake chunk를 만든 뒤 데이터 영역의 주소를 free시키면 다음에 그 주소를 할당받을 수 있다.

 

위와 같은 fake chunk를 free 시키면

 

tcache list에 주소가 추가되어 다음 malloc(0x30)때 위 주소를 할당받게 된다.

 

짜잔~

 

• 결론

tcache malloc, free에 보호기법이 상당히 부족하다는 점과 fastbin보다 tcache를 먼저 참조하는 점을 감안하면 glibc 2.26 이상의 exploit에서 상당히 효율적일 듯. 위 기법들을 적절히 섞어서 exploit에 낭낭히 사용하면 될 것 같다.

 

• 참조

https://dangokyo.me/2018/01/16/extra-heap-exploitation-tcache-and-potential-exploitation/

http://tukan.farm/2017/07/08/tcache/

http://m4x.fun/post/dive-into-tcache/

http://eternal.red/2018/children_tcache-writeup-and-tcache-overview/

https://github.com/shellphish/how2heap