05. [How2Heap] fastbin_dup_consolidate.c

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

/*
Original reference: https://valsamaras.medium.com/the-toddlers-introduction-to-heap-exploitation-fastbin-dup-consolidate-part-4-2-ce6d68136aa8

This document is mostly used to demonstrate malloc_consolidate and how it can be leveraged with a
double free to gain two pointers to the same large-sized chunk, which is usually difficult to do
directly due to the previnuse check. Interestingly this also includes tcache-sized chunks of certain sizes.

malloc_consolidate(https://elixir.bootlin.com/glibc/glibc-2.35/source/malloc/malloc.c#L4714) essentially
merges all fastbin chunks with their neighbors, puts them in the unsorted bin and merges them with top
if possible.

As of glibc version 2.35 it is called only in the following five places:
1. _int_malloc: A large sized chunk is being allocated (https://elixir.bootlin.com/glibc/glibc-2.35/source/malloc/malloc.c#L3965)
2. _int_malloc: No bins were found for a chunk and top is too small (https://elixir.bootlin.com/glibc/glibc-2.35/source/malloc/malloc.c#L4394)
3. _int_free: If the chunk size is >= FASTBIN_CONSOLIDATION_THRESHOLD (65536) (https://elixir.bootlin.com/glibc/glibc-2.35/source/malloc/malloc.c#L4674)
4. mtrim: Always (https://elixir.bootlin.com/glibc/glibc-2.35/source/malloc/malloc.c#L5041)
5. __libc_mallopt: Always (https://elixir.bootlin.com/glibc/glibc-2.35/source/malloc/malloc.c#L5463)

We will be targeting the first place, so we will need to allocate a chunk that does not belong in the
small bin (since we are trying to get into the 'else' branch of this check: https://elixir.bootlin.com/glibc/glibc-2.35/source/malloc/malloc.c#L3901).
This means our chunk will need to be of size >= 0x400 (it is thus large-sized). Notably, the
biggest tcache sized chunk is 0x410, so if our chunk is in the [0x400, 0x410] range we can utilize
a double free to gain control of a tcache sized chunk.
*/

#define CHUNK_SIZE 0x400

int main() {
        printf("This technique will make use of malloc_consolidate and a double free to gain a duplication in the tcache.\n");
        printf("Lets prepare to fill up the tcache in order to force fastbin usage...\n\n");

        void *ptr[7];

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

        void* p1 = malloc(0x40);
        printf("Allocate another chunk of the same size p1=%p \n", p1);

        printf("Fill up the tcache...\n");
        for(int i = 0; i < 7; i++)
                free(ptr[i]);

        printf("Now freeing p1 will add it to the fastbin.\n\n");
        free(p1);

        printf("To trigger malloc_consolidate we need to allocate a chunk with large chunk size (>= 0x400)\n");
        printf("which corresponds to request size >= 0x3f0. We will request 0x400 bytes, which will gives us\n");
        printf("a tcache-sized chunk with chunk size 0x410 ");
        void* p2 = malloc(CHUNK_SIZE);

        printf("p2=%p.\n", p2);

        printf("\nFirst, malloc_consolidate will merge the fast chunk p1 with top.\n");
        printf("Then, p2 is allocated from top since there is no free chunk bigger (or equal) than it. Thus, p1 = p2.\n");

        assert(p1 == p2);

        printf("We will double free p1, which now points to the 0x410 chunk we just allocated (p2).\n\n");
        free(p1); // vulnerability (double free)
        printf("It is now in the tcache (or merged with top if we had initially chosen a chunk size > 0x410).\n");

        printf("So p1 is double freed, and p2 hasn't been freed although it now points to a free chunk.\n");

        printf("We will request 0x400 bytes. This will give us the 0x410 chunk that's currently in\n");
        printf("the tcache bin. p2 and p1 will still be pointing to it.\n");
        void *p3 = malloc(CHUNK_SIZE);

        assert(p3 == p2);

        printf("We now have two pointers (p2 and p3) that haven't been directly freed\n");
        printf("and both point to the same tcache sized chunk. p2=%p p3=%p\n", p2, p3);
        printf("We have achieved duplication!\n\n");

        printf("Note: This duplication would have also worked with a larger chunk size, the chunks would\n");
        printf("have behaved the same, just being taken from the top instead of from the tcache bin.\n");
        printf("This is pretty cool because it is usually difficult to duplicate large sized chunks\n");
        printf("because they are resistant to direct double free's due to their PREV_INUSE check.\n");

        return 0;
}

    for(int i = 0; i < 7; i++)

        ptr[i] = malloc(0x40);

    for(int i = 0; i < 7; i++)

        free(ptr[i]);

이 부분에서 tcache을 다 채운다.

void* p1 = malloc(0x40);

free(p1);

fastbin을 하나 채운다.

malloc_consolidate를 하기 위해선 큰 청크를 할당해야한다. (>=0x400) malloc(0x400)을 하면 청크는 0x410이 된다.

이 사진을 보면 이해가 된다. 모두 10이 추가된다. 하지만 0x401에서 10이 추가되면 0x411이되서 tcache를 나가게된다.

그러면 tcache dup가 안되고, unsorted bin이나 top에 가게 된다. (여기서 0x410이 tcache에 쌓인다는게 아니다. tcache는 이미 다 채워졌으니 다른 large chunk로 간다. 여기서 410은 tcache가 다룰 수 있는 사이즈의 최대치다.)

그래서 

#define CHUNK_SIZE 0x400

void* p2 = malloc(CHUNK_SIZE);

다음과 같이 할당한다. 이러면 glibc에서 큰 청크 할당 경로에서 malloc_consolidate를 호출한다.

 malloc_consolidate를 호출하면 다음과 같이 진행된다.

우선 p1은 0x40을 요청한다 이러면 0x50청크라서 fastbin[0x50]에 들어간다.

근데 0x410은 커서 fastbin에 안들어간다. 그래서 large bin / top에서 처리된다.

여기서 large chunk를 할당할 때 항상 consolidate를 먼저 돌린다.

consolidate는 glibc에서 fastbin 안에 쌓인 청크들을 한 번에 비운다.

순서는

1. unsorted bin으로 옮기고

2. 인접한 free 청크랑 합침

3. 가능하면 top 청크까지 병합

순이다.

여기서 p1을 free했을 때 fastbin[0x50]에 들어간다.

그 후에 malloc(0x400)을 요청한다. 그러면 consolidate를 호출한다.

이 때 fastbin[0x50]을 비우면서 p1을 꺼낸다. unsorted bin에 넣으려다보니 top과 인접하다 그래서 p1을 top에 병합한다.

그러면 top가 더 커졌다.

이어서 malloc(0x400)할당이 top에서 잘려나온다. 그 시작 주소가 곧 예전의 p1자리다.

여기서 이해가 안 될 수 있는데 p1이 top이랑 병합되어 있다. 그런데 malloc으로 할당을 해야하는데 값이 커서 top에서 잘라 할당해야한다. 그러면 top에서 할당해주는데 그 주소가 p1인 것이다. 

    assert(p1 == p2);

그러면 이 것이 성립된다.

근데 여기서 만약 p1을 free하면

    free(p1);

free(p2)랑 같아진다. 그러면 0x410청크가 tcache 로 들어간다.

근데 여기서 알아야 할 것이 tcache 구조이다. 잘못 알고 있다면 아까 tcache를 다 채운것이 아니냐~ 할 수 있다. 하지만 tcache는 크기별로 bin을 여러개 가지고 있다. (0x20, 0x30, 0x40 .... 0x410)여기서 각 bin은 최대 7개 청크까지만 저장 가능하다.

전에 malloc(0x40)으로 채우고 free했을 때는 tcache[0x50]만 채워졌고 나머지 tcache[0x410]은 비어있다.

그래서 0x410짜리 청크가 tcache로 들어간다.

그리고 여기서 한 번 더 malloc(0x400)을 하면 tcache[0x410]에서 꺼내온다. 그러면 p3와 p2는 같아진다.

그런데 처음에 mallocd(0x400)을 했을 때는 tcache에서 안꺼내왔다. 그 이유는 간단하게 처음에는 거기에 아무것도 없었기 때문이다.

결과적으로 p2와 p3는 한번도 free한 적이 없지만 같은 tcache를 가리키게 된다. 그래서 duplication을 성공하게 된다.