Unlink 취약점?

pwnable.kr unlink 문제를 풀어보기 위해서, unlink 취약점에 대해서 찾아 봤어요.
처음에 봤을 때는, 하나도 이해가 안 갔지만 ㅠㅠㅠ
그래도 계속 읽다보고 생각하다보니까 아주 조금 이해가 됬어요!!
조금이라도 더 기억하기 위해서 한번 끄적여 볼게요

malloc의 동적할당?

malloc을 통해서 32바이트만큼 동적할당을 한다고 생각해봐요.
실제로 heap 영역에는 32바이트만큼 메모리가 할당이 되어야할 것 같지만, 실제로는 40바이트가 할당이 됩니다.
왜 그럴까요? 바로, 할당된 메모리를 관리하기 위한 정보들이 포함되어 있기 때문이에요!
그러한 정보는 chunk라고 불리는 구조체를 통해 관리됩니다.

chunk의 구조

아까 말했듯이 동적할당된 메모리는 chunk라고 불리는 구조체로 관리하고 있어요.
이 구조체는 다음과 같이 구성되어 있죠

struct malloc_chunk{
    INTERNAL_SIZE_T mchnk_prev_size; /* Size of previous chunk (if free). */
    INTERNAL_SIZE_T mchnk_size; /* Size in bytes, including overhead. */

    struct malloc_chunk* fd; /* double links -- used only if free. */
    struct malloc_chunk* bk;

    /* Only sued for large blocks: pointer to next larger size. */
    struct malloc_chunk* fd_nextsize;
    sutrct malloc_chunk* bk_nextsize;
};
typedef struct malloc_chunk* mchunkptr;

mchunk_prev_size: 해제가 되면, 이전 chunk의 크기를 가지게 되요.

mchunk_size: overhead를 포함해서, 현재 chunk의 크기를 가지게 되요. 여기서 overhead는 하위 3비트에 set되는 플래그를 말해요.

P(PREV_INUSE): 이전의 chunk가 없으면 0으로 셋되는 데, 맨 처음 chunk에서는 free 됬을 때 합병되지 않도록 하기위해서 1로 셋이 되어 있어요.
M(IS_MMAPPED): mmap함수를 통해서 만들어진 chunk일 경우 1로 셋이 되요.
A(NON_MAIN_ARENA): main 쓰레드에서 만들어졌을 경우 0으로 셋이 되지만 그외의 쓰레드에서 만들어질 경우 1로 셋이 되요.

fd, bk: 각각 forward pointer, back pointer 라고해서 다음의 chunk를 가리키고, 이전의 chunk를 가리켜요.

할당된 메모리와 해제된 메모리의 차이?

이제 할당된 메모리와 해제된 메모리가 어떤 차이가 있는지 알아봅시다.

Allocated chunk

 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if unallocated (P clear)  |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                     |A|M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             User data starts here...                          .
            .                                                               .
            .             (malloc_usable_size() bytes)                      .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             (size of chunk, but used for application data)    |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of next chunk, in bytes                |A|0|1|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Free chunk

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if unallocated (P clear)  |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                     |A|0|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Forward pointer to next chunk in list             |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Back pointer to previous chunk in list            |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Unused space (may be 0 bytes long)                .
            .                                                               .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `foot:' |             Size of chunk, in bytes                           |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of next chunk, in bytes                |A|0|0|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

할당된 chunk와 해제된 chunk를 비교하시면 사용하고 있는 데이터 영역이 다르다는 것을 알수가 있어요.
할당된 chunk 같은 경우에는 저희가 입력한 데이터들이 들어가 있지만, 해제된 chunk에는 아까 말했던 FD와 BK가 들어가 있고, 나머지 영역은 사용하지 않는다는 것을 알 수가 있어요.

동적메모리가 어떻게 할당되는지 알았으니, 이러한 동적메모리가 여러 개가 존재를 한다고 생각해봐요.
그러면 이러한 동적메모리들을 한 곳에 모아서 보관하는 것이 편하겠죠?
그래서 bin이라는 자료구조가 존재해요!!

bin 자료구조

bin 자료구조는 총 4가지가 있다고해요.
chunk의 크기에 따라서 사용되는 bin이 달라져요.

Fast bin
Unsorted bin
Small bin
Large bin

Fast bin은 10개가 존재하고, 다른 bin들은 double linked list로 구성되어 있지만, Fast bin은 single linked list로 구성되어 있어요.
데이터를 삭제하거나 추가할 때 LIFO 방식으로 동작한다고 합니다.
그리고 각각의 bin들은 크기가 달라요. 16, 24, 32, 48, 56, 64, 72, 80, 88 순으로 구성되어 있죠.
당연히 여기에도 메타 데이터가 포함되요.

Unsorted bin은 오직 한개만 존재하는데, 이 놈은 다른놈들과 달라요. 이 bin의 목적은 cache layer처럼 빠르게 할당과 해제를 할 수 있게 도와주는 녀석이에요. 즉, 같은 크기의 chunk가 있다면 해당 chunk를 재사용하는 거에요.
메모리를 동적할당하고 사용하고 나서 어떤 값을 입력하고 해제한 후, 똑같은 크기의 메모리를 재사용할 때, 메모리를 초기화 해주는 작업을 해주지 않으면 그 메모리 안에 쓰레기 값이 존재할 수도 있어요. 그리고 이를 이용해서 exploit도 가능하다고 합니다.!!

Small bin은 62개가 존재하고, 16byte에서 시작해서 8byte씩 늘어낙서 504byte까지 존재한다고 해요. 추가하고 제거하는 방식은 FIFO 방식으로 관리 된다고 합니다.
그리고 small bin 같은 경우에는 해제된 후에, Unsorted bin에 의해 관리되기전에 서로서로가 합쳐질수도 있다고 합니다.

Large bin은 63개가 존재하고, 처음 32개의 bin들은 64byte만큼 떨어져 있지만, 특정 large bin들은 크기가 다른 chunk들을 가질 수 있다고 합니다. 그리고 추가하고 제거하는 방식은 어떤 자리에서도 일어날 수 있다고 합니다.!

동적할당 해제

이렇든 chunk들은 4가지의 bin을 통해서 관리가 되고, list를 이동해야할 일도 생긴다고 해요. 이때, free() 함수가 실행되는 과정중에 unlink라는 매크로 함수가 불릴 때 발생한다고 해요.

free된 chunk가 다시 malloc 되는 경우,
chunk의 크기가 증가해서 다른 bin으로 이동할 경우,
어떤 chunk가 free 되었을 때,
연속된 위치의 다른 chunk가 free 되었을 떄,
unlink 매크로 함수를 통해서 2개의 chunk를 합병을 해준다고 해요.

이렇게 chunk의 사이즈가 증가할 때는 원래 속해있던 bin 리스트에서 해당 chunk를 제거하고, 다시 적절한 bin에 넣어줘야 한다고 합니다.

이때 unlink corruption -> Double Free Bug가 발생한다고 합니다.
맨 처음에 봤을 때는 무슨 이상한 줏자들과 함께 써져 있어서, 헷갈리고 이게 무슨 소리인지 이해되지 않았어요.
fd와 bk를 조작해서 우리가 원하는 값을 쓸수 있다는 것만 알고 있으면 되요!!

참고자료

Heap Exploitation
Heap 영역에서 발생하는 취약점을 알아보자.