Tcache Source Bit-By-Bit

本文章会对Tcache Bin在Glibc 2.29源码上的操作分析。

Tcache Struct

首先，我们需要知道，在Glibc 2.29下 Tcache bin 是主要由这两个结构体控制的 分别是tcache_entry和tcache_perthread_struct:

tcache_entry

需要注意的是，在Glibc2.29中加入了Key值，可以帮助判断Double Free

1
2
3
4
5
6
typedef struct tcache_entry
{
  	struct tcache_entry *next;
 	 /* This field exists to detect double frees.  */
  	struct tcache_perthread_struct *key;
} tcache_entry;

tcache_entry结构体是用于连接在free状态下的chunk的结构体，拥有一个next指针，会指向下一个大小相同的Free Chunk

需要注意的是这里的 next 指向 chunk 的 user data，而 fastbin 的 fd 指向 chunk 开头的地址。

tcache_perthread_struct

1
2
3
4
5
typedef struct tcache_perthread_struct
{
  char counts[TCACHE_MAX_BINS];             /*TCACHE_MAX_BINS = 64*/
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

这个结构体和他的名字一样，在每一个线程中都会申请一个为该结构体的Chunk，他的作用主要是为了管理整个Tcache Bin List

  • count[] 记录了 tcache_entry 链上Free Chunk 的数目,每条最多可以拥有7个Chunk
  • tcache_entry通过单向链表连接了Free Chunk

How It Works?

我们从malloc函数开始：

1
2
3
4
5
6
7
8
9
10
11
__libc_malloc (size_t bytes)
{
  // codes............
  #if USE_TCACHE
      /* int_free also calls request2size, be careful to not pad twice.  */
      size_t tbytes;
      checked_request2size (bytes, tbytes);
      size_t tc_idx = csize2tidx (tbytes);

      MAYBE_INIT_TCACHE ();
  	  /*Call to MAYBE_INIT_TCACHE()*/

可以看到，如果我们在第一次调用malloc函数时，会先进入到MAYBE_INIT_TCACHE()函数来初始化

1
2
3
# define MAYBE_INIT_TCACHE() 
  if (__glibc_unlikely (tcache == NULL)) 
    tcache_init();

可以看到，这里首先对Tcache进行了判断，如果Tcache不存在，则执行tcache_init()函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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进行了申请这里我们不多说

我们从MAYBE_INIT_TCACHE继续往下康康：

1
2
3
4
5
6
7
8
9
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;

好的，首先判断了在tcache_init()申请的tcache是否为空，和tcache->entries[tc_idx]是否不为空;这里正提到了tc_idx,给大家看看计算方法：

tc_idx calculation

首先，在malloc中对tc_idx的定义是：

1
2
3
size_t tbytes;
  checked_request2size (bytes, tbytes); 
size_t tc_idx = csize2tidx (tbytes);

查看 csize2tidx()的定义，和引用的变量的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#if USE_TCACHE
    /* When "x" is from chunksize().  */
    # define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)/*x - 0x20 + 0x9 / 0x10*/
	/*Other's Required*/
	#define SIZE_SZ (sizeof (size_t))
	#define MALLOC_ALIGNMENT (2 * SIZE_SZ < __alignof__ (long double) \  /*64位返回False,32没有测过*/
			  ? __alignof__ (long double) : 2 * SIZE_SZ)                /*返回 0x10*/

    #define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)
	/* The smallest possible chunk */
	#define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize)) /*0x20*/

    /* The smallest size we can malloc is an aligned minimal chunk */
    #define MINSIZE  \
      (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)) /*(0x20 + 0x1f) & ~0x1f = 32*/

    #define request2size(req)                                         \
      (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
       MINSIZE :                                                      \
       ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

可以看到 最终的tc_idx就是 size - 0x20 + 0x9 \ 0x10

我们也可以使用how2heap的模板计算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
➜  calc ./calc_tca
This file doesn't demonstrate an attack, but calculates the tcache idx for a given chunk size.
The basic formula is as follows:
        IDX = (CHUNKSIZE - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT
        On a 64 bit system the current values are:
                MINSIZE: 0x20
                MALLOC_ALIGNMENT: 0x10
        So we get the following equation:
        IDX = (CHUNKSIZE - 0x11) / 0x10

BUT be AWARE that CHUNKSIZE is not the x in malloc(x)
It is calculated as follows:
        IF x + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE(0x20) CHUNKSIZE = MINSIZE (0x20)
        ELSE: CHUNKSIZE = (x + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
        => CHUNKSIZE = (x + 0x8 + 0xf) & ~0xf


[CTRL-C to exit] Please enter a size x (malloc(x)) in hex (e.g. 0x10): 0x10

TCache Idx: 0
[CTRL-C to exit] Please enter a size x (malloc(x)) in hex (e.g. 0x10): 0x25

TCache Idx: 1
[CTRL-C to exit] Please enter a size x (malloc(x)) in hex (e.g. 0x10): 0x23

TCache Idx: 1
[CTRL-C to exit] Please enter a size x (malloc(x)) in hex (e.g. 0x10): 0x40

TCache Idx: 3
[CTRL-C to exit] Please enter a size x (malloc(x)) in hex (e.g. 0x10):

tcache_put && tcache_get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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]);
}

/* 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]);
  e->key = NULL;
  return (void *) e;
}

两兄弟函数tcache_put()和tcache_get()，分别向Tcache Bin List 添加以及拿出Tcache Bin 简单的操作，可以自己看看

About KeyTests

在glibc2.29下，新增了针对Double Free的检查：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// #if USE_TCACHE
  {
    size_t tc_idx = csize2tidx (size);
    if (tcache != NULL && tc_idx < mp_.tcache_bins)
      {
	/* 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;
	  }
      }
  }
// #endif

可以看到，Glibc 对于 key==tcache的情况做了遍历整个Tcache Bin List 的操作 也就是在free()后会遍历来查看有没有相同的chunk

How To Bypass

如果你是Double Free重度爱好者，但被glibc2.29感到伤心时，没事，我告诉你，其实还有一种简单的攻击方法，叫做House of Poortho

这个发现是在我刷picoctf往年的题目发现的，题目名称叫做zero2hero，这个程序有Off-By-Null，不说那么多，主要原理呢，大概是利用Off-By-Null 溢出单字节，修改Chunk 大小，导致在计算tc_idx时候出现了 不同大小，地址内容却相同的Chunk 这个时候，因为会储存在不同的tcache->entries[tc_idx]链中，导致遍历时不会遍历到相同的Chunk

https://robertchen.cc/blog/2019/10/17/pico19-zero-to-hero