[how2heap] fastbin_dup_consolidate.c

Lecture: fastbin_dup_consolidate.c

https://github.com/shellphish/how2heap/blob/master/glibc_2.35/fastbin_dup_consolidate.c

how2heap/glibc_2.35/fastbin_dup_consolidate.c at master · shellphish/how2heap

 

 

Environment : Ubuntu 18.04 LTS / ldd (Ubuntu GLIBC 2.27-3ubuntu1.6) 2.27

 

Lecture Code:

 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int main() {
	// reference: https://valsamaras.medium.com/the-toddlers-introduction-to-heap-exploitation-fastbin-dup-consolidate-part-4-2-ce6d68136aa8
	puts("This is a powerful technique that bypasses the double free check in tcachebin.");
	printf("Fill up the tcache list to force the fastbin usage...\n");

	void *ptr[7];

	for(int i = 0; i < 7; i++)
		ptr[i] = malloc(0x40);
	for(int i = 0; i < 7; i++)
		free(ptr[i]);

	void* p1 = calloc(1,0x40);

	printf("Allocate another chunk of the same size p1=%p \n", p1);
  	printf("Freeing p1 will add this chunk to the fastbin list...\n\n");
  	free(p1);

  	void* p3 = malloc(0x400);
	printf("Allocating a tcache-sized chunk (p3=%p)\n", p3);
	printf("will trigger the malloc_consolidate and merge\n");
	printf("the fastbin chunks into the top chunk, thus\n");
	printf("p1 and p3 are now pointing to the same chunk !\n\n");

	assert(p1 == p3);

  	printf("Triggering the double free vulnerability!\n\n");
	free(p1);

	void *p4 = malloc(0x400);

	assert(p4 == p3);

	printf("The double free added the chunk referenced by p1 \n");
	printf("to the tcache thus the next similar-size malloc will\n");
	printf("point to p3: p3=%p, p4=%p\n\n",p3, p4);

	return 0;
}

 

Background:

 

이전 Lecture 까지는 DFB를 트리거하기 위해서 중복된 청크 해제 과정 사이에 임의의 청크 하나를 아무거나 해제시켜서 DFB 탐지를 우회하는 방법을 이용했었다.

 

이번 Lecture에서는 청크를 연속으로 해제하는 대신 힙의 consolidate(병합) 기능을 이용해서 DFB를 트리거하는 방법을 알려준다.

 

Consolidate 는 사용하지 않는 청크를 병합해서 메모리 단편화를 줄이기 위한 힙 메커니즘이다.

 

malloc.c 파일에서 malloc_consolidate 함수가 존재하는데, 이 함수에서 병합 기능이 구현된다.

 

다음은 malloc_consolidate 함수의 스니핏이다. 핵심 부분만 가져왔다.

 

//malloc.c
static void *
_int_malloc(mstate av, size_t bytes) 
{
	...
	if (in_smallbin_range (nb))
	{
		...
	}
	else 
	{
		idx = largebin_index(nb);
		if (atomic_load_relaxed (&av->have_fastchunks))
			malloc_consolidate (av);
	}
	...

	use_top:
	// arena의 top chunk를 검사
	...
	if ((unsigned long) size >= (unsigned long) (nb + MINSIZE))
	{
	...
	}

	else if (atomic_load_relaxed (&av->have_fastchunks)) 
	{
		malloc_consolidate (av);
		...
	}
	
	...
}

 

힙 메모리 할당 시점에는 총 두 번의 병합 기회가 주어진다.

 

첫 번째는 lin_smallbin_range(nb) 조건을 통과하지 못하고 else 분기로 이동하는 경우, have_fastchunks 라는 함수를 이용해서 av(현재 아레나)의 fastbins에 청크가 존재하는지 확인한다. 청크가 존재한다면 해당 청크들을 병합한다.

 

두 번째로 (unsigned long) size >= (unsigned long) (nb + MINSIZE) 조건을 통과하지 못한 경우, 똑같이 av(현재 아레나)의 fastbins에 청크가 존재하는지 확인한다. 첫 번째외 똑같이 fastbins에 청크가 존재한다면 해당 청크들을 병합한다.

 

그렇다면 메모리 해제 시점에는 어떨까?

 

//malloc.c
static void
_int_free (mstate av, mchunkptr p, int have_lock) 
{
	...
	
	else if (!chunk_is_mmapped(p)) {
		...

		if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
			if (atomic_load_relaxed (&av->have_fastchunks))
				malloc_consolidate(av);
		}
	}
	...
}

 

(unsigned long) (size) >= FASTBIN_CONSOLIDATE_THRESHOLD 인 경우, 병합을 진행한다.

 

FASTBIN_CONSOLIDATE_THRESHOLD 매크로는 상수 매크로이며 64kb 값을 가지고 있다. 즉, 해제된 청크의 크기가 64kb보다 큰 경우에 또 다시 fastbins를 검사하여, 내부에 청크가 존재한다면 그들을 병합한다.

 

할당과 해제 시점의 모든 병합 조건을 알았으니 다음은 malloc_consolidate 함수의 동작을 알아보자.

 

//malloc.c
static void malloc_consolidate(mstate av)
{
  mfastbinptr*    fb;                 /* current fastbin being consolidated */
  mfastbinptr*    maxfb;              /* last fastbin (for loop control) */
  mchunkptr       p;                  /* current chunk being consolidated */
  mchunkptr       nextp;              /* next chunk to consolidate */
  mchunkptr       unsorted_bin;       /* bin header */
  mchunkptr       first_unsorted;     /* chunk to link to */

  /* These have same use as in free() */
  mchunkptr       nextchunk;
  INTERNAL_SIZE_T size;
  INTERNAL_SIZE_T nextsize;
  INTERNAL_SIZE_T prevsize;
  int             nextinuse;
  mchunkptr       bck;
  mchunkptr       fwd;

  atomic_store_relaxed (&av->have_fastchunks, false);

  unsorted_bin = unsorted_chunks(av);

  /*
    Remove each chunk from fast bin and consolidate it, placing it
    then in unsorted bin. Among other reasons for doing this,
    placing in unsorted bin avoids needing to calculate actual bins
    until malloc is sure that chunks aren't immediately going to be
    reused anyway.
  */

  maxfb = &fastbin (av, NFASTBINS - 1);
  fb = &fastbin (av, 0);
  do {
    p = atomic_exchange_acq (fb, NULL);
    if (p != 0) {
      do {
	{
	  unsigned int idx = fastbin_index (chunksize (p));
	  if ((&fastbin (av, idx)) != fb)
	    malloc_printerr ("malloc_consolidate(): invalid chunk size");
	}

	check_inuse_chunk(av, p);
	nextp = p->fd;

	/* Slightly streamlined version of consolidation code in free() */
	size = chunksize (p);
	nextchunk = chunk_at_offset(p, size);
	nextsize = chunksize(nextchunk);

	if (!prev_inuse(p)) {
	  prevsize = prev_size (p);
	  size += prevsize;
	  p = chunk_at_offset(p, -((long) prevsize));
	  unlink(av, p, bck, fwd);
	}

	if (nextchunk != av->top) {
	  nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

	  if (!nextinuse) {
	    size += nextsize;
	    unlink(av, nextchunk, bck, fwd);
	  } else
	    clear_inuse_bit_at_offset(nextchunk, 0);

	  first_unsorted = unsorted_bin->fd;
	  unsorted_bin->fd = p;
	  first_unsorted->bk = p;

	  if (!in_smallbin_range (size)) {
	    p->fd_nextsize = NULL;
	    p->bk_nextsize = NULL;
	  }

	  set_head(p, size | PREV_INUSE);
	  p->bk = unsorted_bin;
	  p->fd = first_unsorted;
	  set_foot(p, size);
	}

	else {
	  size += nextsize;
	  set_head(p, size | PREV_INUSE);
	  av->top = p;
	}

      } while ( (p = nextp) != 0);

    }
  } while (fb++ != maxfb);
}

 

간결하게 정리하면 다음과 같다.

 

1. fastbins를 불러온다

2. 이전 청크가 비어있으면 현재 청크와 병합

3. 다음 청크가 탑 청크가 아니고 비어있으면 현재 청크와 병합

4. 2,3번을 거친 청크들은 모두 unsorted bin으로 이동 (이후에 다시 small bin, large bin으로 분류한다)

5. 2, 3번을 거치지 않은 청크들 중에서 다음 청크가 탑 청크인 경우 탑 청크와 병합

6. 모든 fastbin 인덱스에  대해서 위 과정을 반복 실행

 

정리해도 헷갈린다면 프로그램을 직접 실행해서 결과를 분석해보자.

 

Analyze:

 

한줄씩 분석해보면 다음과 같다.

 

우선 tcache를 가득채운다

 

이후 p1 청크(0x557463bdf8a0)를 할당 후 해제해서 fastbin list에 넣는다.

 

이제 malloc_consolidate 함수를 실행하기 위해서 적절한 크기의 청크를 할당한다.

(병합 조건은 small bin에 들어가지 않을 정도의 크기를 할당 요청하는 경우, 혹은 모든 bins로 부터 재사용할 청크가 없어서 top chunk로 부터 할당받는 경우이다.)

 

여기선 0x400 크기의 p3 청크를 할당하였다.

(출력을 보면 tcache-sized chunk라 되어있는데 나중에 tcache에 넣을거라 그렇다. 어찌됐든 조건은 small bin (최대 1023byte까지 수용)에 안들어가면 되기 때문에 0x400(1024)byte 를 할당하면 된다. 참고로 tcache의 최대 크기 인덱스는 1032byte이므로 small bin과 안 겹침)

 

조건을 만족했기 때문에 p3를 할당할 때 malloc_consolidate 함수가 실행된다.

 

현재 fastbins에는 p1만 존재하고, 이 p1의 다음 청크(굳이 리스트로 연결되어있지 않더라도 인접한 주소를 레퍼런스한다.)는 현재 아레나의 top chunk일 것이다.

 

위에서 알아보았듯이 top chunk와 인접한 fastbin의 청크는 top chunk와 병합된다. 결과적으로 p1은 top chunk와 병합된다.

 

그리고 p3는 이 병합된 top chunk로 부터 메모리를 할당받는다.

 

이를 조금 더 가시적으로 보기위해서 pwndbg로 확인해보면 다음과 같다.

 

 

이 상황은 p3를 할당하기 직전이다. 여기서 top chunk와 병합되는 부분을 캐치하려면 _int_malloc 함수 내부의 malloc_consolidate 함수 실행 직후를 포착해야한다. (메인 함수에 브레이크를 걸면 병합이 순식간에 이루어져서...)

 

p3를 할당하는 malloc 함수에 브레이크를 걸고 step into 명령으로 함수를 파고들어 다음과 같이 malloc_consolidate 함수가 실행되는걸 포착했다.

 

 

(조금 시간이 걸리니까 인내심을 갖고 계속 한 스텝씩 실행)

 

여기까지 실행하고 힙 상태를 확인해보면 다음과 같다.

 

 

기존의 fastbin에 존재했던 p1(0x555555603890)이 top chunk의 시작 주소(Addr 값)가 되어버렸다. 여기서 p3 할당을 마치면 다음과 같이 top chunk로 부터 p3를 할당받는다.

 

 

찿ㅁ고로 main 함수를 디스어셈블 해보면 rbp-0x58이 p1, rbp-0x50이 p3인데 두 위치를 비교해보면 값이 똑같다.

(포인터 정리를 안하기 때문에 이런 검증이 가능하다)

 

 

힙 메모리 포인터는 청크의 시작 주소가 아니라 데이터 영역을 가리킨다는 점을 유의해야한다. 그래서 위의 Chunk의 주소와 0x10 차이가 난다.

 

이제 p1을 해제하려면 p3(0x555555603890)의 크기를 참조하므로 0x400 크기의 청크를 해제하는 것과 똑같다. 따라서 fastbin이 아니라 tcache에 들어간다. (아까도 말했듯이 tcache 최대 수용크기는 1032byte)

 

*tcache는 앞에서 꽉 채운거 아닌가?

0x40 크기의 인덱스가 꽉찬거지 0x400 크기를 수용하는 인덱스는 하나도 안찼다

 

 

예상대로 fastbin이 아닌 tcache에 p1(0x555555603890) 청크가 들어갔다.

 

이걸로 Duplicated Chunk가 되었다. (아래와 같이 p1은 p3로써 Allocated이지만, 동시에 fastbin에도 존재한다.)

 

 

이제 p4(0x400)을 할당하면 당연히 0x400 크기의 p1을 재사용한다. 결과적으로 p4는 p3와 같은 주소를 공유한다.

 

 

최종적으로 3개의 포인터 p1(rbp-0x58), p3(rbp-0x50), p4(rbp-0x48)이 같은 청크를 공유하고 되었다.

 

* 근데 이게 왜 DFB 인가? bins에 같은 청크가 존재한 적이 없는데?

 

=> 딱히 bins에 중복된 청크가 존재해야한다는 법칙은 없다. DFB는 결국 중복 해제를 의미하므로...

 

이런 병합을 이용한 DFB 트리거 방법은 아주 제한적인 상황에서 의미있다. 예를 들어 청크의 해제 순서를 강제하는 경우, 혹은 같은 크기의 청크를 연속으로 할당할 수 없는 경우, 혹은 무조건 큰 크기의 청크를 할당받아야하는 경우에는 이 방법이 유용할 것이다.

 

Reference: