dlmalloc 조지기 1탄

 

protostar heap3문제의 double free bug를 구글링 3일 동안 해가면서 공부한것을 정리하려함. 

일단 설명할 malloc()은 x86기준으로 설명할 것임. 

우리가 알고 있는 malloc함수는 Heap영역에 우리가 원하는 크기만큼 메모리를 할당하는 것인걸로 알고 있고. 

해제 할때는 해당 메모리의 포인터값을 free()함수의 인자로 넣으면 된다는 것을 알고 있다. 

그런데 여기서 이상한 점이 있다. 

free()라는 함수에 단지 Heap영역에 할당받은 포인터값을 넣었는데 어떻게 메모리에서 해제되었을까. 

그 이유는 malloc의 chunk(메모리 할당 부분)에서 찾아볼 수 있다. 

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

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

    //위의 fd와 bk는 오직 해제된 상태에서 나타나며 해제되지 않을 때는 userdata로 사용된다. 

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

위의 구조체로 이루어져 있다. 

일단 보기만 해도 추가적인 metadata들이 있다는 것을 알 수 있다. 

위의 malloc chunk구조체는 사용중일때와 free()된 상태일 때와 큰 차이를 보인다. 

그림으로 확인해보자. 

위의 사진은 현재 Heap영역에서 메모리를 사용할 때 malloc chunk의 구조이다. 

할당받은 메모리의 첫번째는 prev_size를 가지며, 다음은 size, AMP, payload의 구조를 지니고 있다. 

prev_size는 이전에 Heap에서 할당받은 메모리의 크기를 가지고 있다. 

size는 현재 chunk의 크기를 나타내면 AMP 플래그값도 포함되어 있다. 

AMP 플래그 값이란 chunk에 대한 상태값을 나타내는 플래그 값인데 

A 플래그는 

#define NON_MAIN_ARENA 0x04로 정의되어 있으며 

set가 안될 시 해당 chunk가 main arena와 main heap에서 왔다는 것을 의미한다.

set될 시 해당 chunk는 mmap'd memory에서 왔음을 의미한다. 

M 플래그는 

#define IS_MMAPPED 0x02로 정의되어 있으며

해당 chunk가 mmap() 시스템콜로 인해 할당 되었나를 의미한다. 

P 플래그는 

#define PREV_INUSE 0x01로 정의되어 있으며 

해당 chunk의 이전 chunk가 free되어 있는 상태냐(0), 사용중이냐(1)를 의미한다. 

그리고 다음 payload는 우리가 실제로 malloc을 통해 할당받아 사용할 수 있는 공간이다. 

그래서 실제로 malloc을 호출하여 반환값을 확인해보면 prev_size가 있는 포인터값에서 +8을 해서 반환한다. 

왜냐하면 &prev_size+8을 해야 우리가 쓸 수 있는 공간이 있는 payload에 접근이 가능하기 때문이다. 

여기까지가 해당 chunk를 사용중일 때의 이야기이며 free되었을 떄의 이야기를 진행할 것이다. 

해당 chunk가 free되었을 때는 payload부분이 fd와 bk로 변환게 되는 거 뺴곤 크게 달라진 점은 없다. 

할당된 chunk가 free된다면 bin이라는 구조에 의해 관리가 되어 지는데 이 bin들은 doubly-linked list자료구조로 구성되어 있기 때문에 fd포인터와 bk 포인터로 서로와 서로를 연결한다. 

그리고 이 bin은 해제된 chunk의 크기에 따라 여러가지 구조로 나뉘는데 

72바이트 이하의 chunk를 관리하는 fastbin(single-linked-list) - 스택의 구조 LIFO

-> free()된 메모리중에서 빠르게 재할당 하기위해 싱글 리스트로 구성되어 있다. 

malloc()호출시 가장 먼저 조사하게 되는 bin

80바이트 이상 512바이트 이하의 chunk를 관리하는 small-bin(doubly-linked-list) - 큐의 구조 FIFO

그 이상의 값의 chunk를 관리하는 large-bin이 존재한다. (doubly-linked-list) - 큐의 구조 FIFO

그리고 최상위 bin인 unsorted-bin이 존재하는데 

free된 chunk가 가장먼저 unsorted-bin에 들어가게 된다. (doubly-linked-list) - 큐의 구조 FIFO

(cache의 역할을 가진다.) 

unsorted-bin의 경우 free()된 chunk가 동일한 크기로 재할당하는 경우를 대비해서 FIFO의 형태로 리스트가 구성되어 있다가 

단 한번의 재사용기회(동일한 크기 요청시)를 가지게 되며 만약 재사용되지 못하면 해당 chunk의 크기에 따라 fastbin에 가게 될지, 아니면 

unlink라는 매크로를 통해 병합을 진행해서 다른 bin으로 옮기게 될지 아니면 top chunk로 다시 병합될지 결정된다. 

여기서 리스트를 구성할 수 있게 해주는 포인터들은 (chunk데이터 안에 존재하는 fd와 bk이다.) 

unlink 매크로란 

#define unlink {
    FD = P->FD
    BK = P->bk
    FD->bk = BK
    BK = P->bk
}

로 구성되어 있는데 

그림으로 자세히 표현하자면 

해당 P chunk를 빼내어 진행하게 되어 앞뒤의 BK와 FD를 서로 연결하게 된다. 즉, 병합임을 의미한다. 

여기서 중요한건 fastbin의 경우 인접한 chunk와의 병합을 진행하지 않는다.

또한,

병합을 진행할 때 해당 chunk의 P 플래그(이전 chunk가 사용중인가를 나타내는 flag)가 0으로 세트되어 있어야 한다. 

근데 여기서 Double Free Bug를 발생시킬 수 있다. 

만약 P가 fake chunk라면? unlink 매크로를 통해 서로를 연결하는 작업 중 P가 가리키고 있는 값을 근거로 진행되는데 

P가 가리키고 있는 값이 조작된 값이라면 이를 검사하지않고 BK와 FD에 덮어쓰게 되어서 exploit이 가능하게 된다. 

여기까지가 malloc()함수의 기본적인 설명인데 나중에 추가적인 공부후에 또 다시 올릴예정. 

일단 heap3 문제 write-up정리해야집

 

추가 fake chunk P에 대해 

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

위의 코드를 보면 

먼저 현재 chunk에 대해 prev_inuse플래그를 확인 

prevsize와 size값을 재설정한 후

P에 현재청크의 이전 chnuk의 크기를 빼 주소를 찾는다. 

P는 fake chunk가 된다. 

이 부분때문에 이해안되서 메이플 오지게 했는데 역시 모를땐 코드로 보는게 답이다. 

 

역시 Aegis 머장님 블로그 짱짱