What is heap part 1
CTF문제를 풀이함에 있어 전혀 손도 못대는 영역이 heap영역에 대한 취약점을 다룬 문제들이였는데
Koreangang에서 아주 좋은 강의가 올라와서 heap을 처음으로 공부를 해봤습니다.
영상에서도 설명이 되었지만 how2heap을 통해 공부를 시작하려고 하지만 어디서부터 어떻게 시작해야되는지 모르시는 분들에게 정말 필요한 영상인것 같습니다 :)
Heap Concept Tutorial#1(for heap exploit)
이번 글에서는 해당 영상을 토대로 공부를 하면서 정리를 한 것을 포스팅하겠습니다.
제 정리가 보기 불편하고 어렵다면 위의 링크에서 영상을 보고 오시는 것을 추천드립니다.
heap?
-> 프로그램이 실행되는 도중 동적으로 할당하고 해제하여 사용하는 메모리 영역입니다.
ex) 식당 운영
식당 운영을 예로 들었을 때 손님 두명이 왔다고 생각을 해봅시다.
여기서 stack과 heap의 차이가 나는것을 알 수 있는데요.
stack의 경우 앉을 의자가 미리 준비되어있고, 만약 손님이 두명 왔다면 두개의 의자가 남는 상황이 생지만
heap의 경우 손님의 수에 따라 의자의 개수를 준비하기 때문에 의자를 낭비하지 않고 두개의 의자를 손님 테이블에 놓아줄 수 있습니다.
이 처럼 heap은 stack과는 달리 프로그램이 실행하면서 동적으로 생성을 하기 때문에 좀 더 공간을 효율적으로 사용할 수 있다는 장점이 있습니다.
동적 메모리 할당자의 종류
프로그램이 실행되면서 다양한 크기의 데이터가 들어가는 만큼
다양한 크기의 동적 영역이 필요합니다.
이에 따라 메모리 할당자도 다른데 다음과 같이
tcmalloc, ptmalloc2, Libumem, Jemalloc, dlmalloc 등이 있습니다.
먼저 dlmalloc에 대해 알아보겠습니다.
dlmalloc
리눅스에서 사용되는 힙 관리에 사용되는 memory allocator
dlmalloc이 사용되다가 쓰레드 기능이 추가된 ptmalloc이 현재 사용된다.
ptmalloc -> dlmalloc에 쓰레드 기능만 추가되었다.
따라서 현재 Ubuntu에서 사용되는 memory allocator의 기본 알고리즘은 dlmalloc과 동일하다고 합니다.
heap은 어떻게 생기고 없어질까?
char *p = malloc(size) : 원하는 size만큼 malloc을 호출하여 동적 메모리 할당
free(p) : 사용한 메모리를 free하여 반환
char *p = malloc(size)
-> 원하는 size를 인자로 넣고 함수를 호출하면 할당된 주소를 반환값으로 받습니다.
(일반적으로 c언어에서는 포인터로 처리를 합니다.)
그리고 이 영역(p)을 다 사용하고 난뒤에 free()에 인자로 넣어서 사용한 메모리를 해제를 합니다.
여기서 착각할 수 있는것은
malloc() 를 통해 heap영역에 특정 크기를 할당받고, free()로 메모리를 해제했을 때
해제를 했기 때문에 접근할 수 없을것라고 생각할 수 있을 것입니다.
하지만 특정 크기로 할당 받은 메모리 영역에 free한 영역도 남아있게 됩니다.
따라서 접근이 가능하겠죠.
예제파일과 함께 조금 더 알아봅시다.
⚡ root@ubuntu /home/fkillrra/Study/Heap_exploit cat test.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
char *p = malloc(512);
strcpy(p, "this is malloc 512");
fprintf(stderr, "p allocation %p pints to %s\n", p, p);
free(p);
return 0;
}
p라는 포인터 변수에 malloc()를 이용하여 512byte의 크기의 heap공간을 할당받고, 마지막에 free를 해주는 간단한 프로그램입니다.
[free() 호출 후]
malloc함수를 호출하게 되면 memory map에 heap이라는 공간이 생기게 되는데 free한 영역도 이 부분에 남게됩니다.
다음으로 chunk에 대한 내용입니다.
chunk
mem : malloc으로 부터 할당 받은 부분
chunk : mem에다가 header(사이즈 정보)를 포함한 부분
size : chunk의 크기를 나타냄 (32bit는 8바이트, 64bit는 16바이트 단위로 정렬)
prev_size : 인접한 앞쪽 chunk의 크기를 나타냄
Ubuntu의 malloc.c source code를 보면
malloc을 통해서 할당 받은 부분을 mem이라고 표현을 합니다.
그리고
mem + header 즉 mem에다가 header를 더한 부분을 chunk라고 부릅니다.
header에는 prev_size와 size가 들어가있습니다.
size는 현재 chunk의 size를 가지고 있습니다.
prev_size는 밑에 보이는 그림과 같이 인접한 앞쪽의 chunk의 크기를 가지고 있습니다.
앞쪽에 있는 chunk의 크기가 뒤쪽에 있는 chunk의 prev_size에 저장이 되는데요.
일반적이게 두 개의 chunk가 나란히 할당되어있는 상황에서는 prev_size가 0으로 초기화 되어있지만
앞쪽에 있는 chunk가 free가 될 때 그 chunk의 size가 prev_size에 저장이 된다는 점을 기억해야합니다.
chunk size
이러한 chunk의 size는
32bit는 8byte, 64bit는 16byte 단위로 정렬이 됩니다.
이렇게 32bit는 8byte, 64bit는 16byte 단위를 정렬이 될 때
8byte 단위로 정렬되어 하위 3bit가 사용되지 않는데 이 부분을 이용하여 3가지 chunk의 속성정보를 나타내게 됩니다.
이렇게 non main arena is_mmaped, prev_inuse bit로 나뉘는데
여기서 중요한 bit는 prev_inuse bit입니다.
앞전 설명에서 이전의 chunk 즉, 앞의 chunk가 free가 되면 뒤쪽의 chunk에 header에 있는 prev_size가 초기화가 된다고 설명했는데요.
이 처럼를 인접한 chunk가 malloc이 되어 사용되고 있는지, 혹은 free가 되어 사용되고 있지 않은지를 나타내는 bit가 prev_inuse bit 입니다.
prev_inuse bit
그림을 통해 알아봅시다.
먼저 A와 B가 malloc을 통해 할당 된 모습입니다.
여기서 B chunk의 prev_inuse bit는 A가 할당되어있기 때문에 1이 됩니다.
A가 해제가 되고 난 뒤의 B chunk의 prev_inuse bit는 0이 됩니다.
이러한 chunk header의 size에서 prev_inuse bit의 특성을 알아야만 이후 heap 취약점에 대해 이해하실 수 있습니다.
(중요하다!! 별표 5개!)
지금까지 chunk의 특성 및 개념에 대해 설명을 했고, 이제 chunk의 종류에 대해 알아보겠습니다.
chunk의 종류
chunk의 종류는 크게 3가지 chunk로 구분을 하여 접근하는데, 다음과 같습니다.
- Allocated chunk : 할당된 chunk
- Freed chunk : 해제된 chunk
- Top chunk (a.k.a wildness chunk) // 해외 문서에서는 Top chunk를 wildness chunk라고 부르기도 함.
먼저
Allocated chunk
할당된 chunk는 malloc()를 호출했을 때 반환되는 부분이고, 통상적으로 free된 chunk와 구분짓기 위해 Allocated chunk라고 부릅니다.
ptr = malloc(); // 이 때 heap영역에 생기는 chunk
일반적으로 구조는 chunk의 header, chunk의 data 부분으로 나뉘고 이 data는 이전에 설명했듯이 malloc했을 때 return 되는 부분인 mem 부분이 됩니다.
직접 메모리영역에서 보면
이 처럼 보실 수 있습니다.
제가 디버깅한 바이너리는 protostar에 heap1입니다.
[heap1.c]
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <stdio.h>
#include <sys/types.h>
struct internet {
int priority;
char *name;
};
void winner()
{
printf("and we have a winner @ %d\n", time(NULL));
}
int main(int argc, char **argv)
{
struct internet *i1, *i2, *i3;
i1 = malloc(sizeof(struct internet)); // break point!
i1->priority = 1;
i1->name = malloc(8);
i2 = malloc(sizeof(struct internet));
i2->priority = 2;
i2->name = malloc(8);
strcpy(i1->name, argv[1]);
strcpy(i2->name, argv[2]);
printf("and that's a wrap folks!\n");
}
여기서 보면 알 수 있듯
header의 size에 0x11이 들어가 있고, 여기서 마지막 bit인 1이 prev_inuse bit이고 이전의 chunk가 사용중이라는 것을 의미합니다.
또한 size가 0x11이므로 chunk의 크기는 prev_inuse bit를 제외한 0x10 (10진수로 16)임을 알 수 있습니다.
이 때 이상하다고 생각할 수 있는 부분은
break point를 i1 = malloc(sizeof(struct internet)); 에 걸고 디버깅을 했는데, prev_inuse bit가 1로 세팅되어있는점입니다.
이는 제일 처음 할당된 chunk의 경우 기본적으로 1이 세팅되기 때문입니다.
다음으로
Freed chunk
에 대해 알아보겠습니다.
freed chunk는 해제된 chunk를 의미합니다.
위 그림에서 알 수 있듯 allocated chunk와 freed chunk와는 다른 구조를 띄고있습니다.
free된 chunk들은 메모리 할당자가 효율적으로 관리를 하기 위해 비슷한 크기끼리 관리하게 되는데 이를 linked list로 관리합니다.
linked list로 관리하기 때문에 이 linked list를 가리킬 포인터가 필요하게 되고, 이를 free된 chunk의 데이터 앞쪽에 저장하게 됩니다.
여기서 fd는 forward를 의미하고, bk는 backward를 의미합니다.
fd : Forward pointer to next chunk in list
bk : Back Pointer to previous chunk in list
따라서 fd는 뒷쪽를 가리키는 포인터가 들어가 있고, bk에는 앞쪽을 가리키는 포인터가 들어가게 됩니다.
512byte보다 큰 chunk를 large chunk라고 하는데, 이렇게 크기가 큰 경우는 비슷한 크기끼리 관리하는 heap의 특성에 따라 다른 작은 freed chunk와 구분하기 위해 fd_next_size, bk_next_size 포인터를 이용하여 다르게 관리를 하게 됩니다.
fd_next_size
bk_next_size
free()를 호출했을 때, 실제 반환되는 것이 아니라 힙 영역에 남아있으며, allocated chunk 구조에서 freed chunk 구조로 변경됨(data가 있던 부분에 fd, bk가 생기고, 크기가 큰 경우 fd_next_size, bk_next_size도 생김)
여기서 한번 짚고 넘어가면
allocated chunk가 free가 되면 freed chunk의 형태로 변경되면서 fd, bk를 통해 freed chunk를 효율적으로 관리하게 된다는 점이 allocated chunk와 freed chunk의 다른점이라고 할 수 있습니다.
그림에서 보면 알 수 있듯이 freed chunk는 데이터 영역에 fd, bk의 구조를 갖는 것을 알 수 있습니다.
마지막으로
Top chunk (wildness chunk)
입니다.
Top chunk는 heap 영역에 가장 마지막에 위치해서 새롭게 할당(malloc)되면 이 Top chunk에서 분리해서 반환하고 Top chunk에서 인접한 chunk가 free되면 이 Top chunk에 병합이 되는 특징을 갖고 있습니다.
일반적으로 heap영역에 할당되는 0x21000에서 malloc하여 할당된 chunk의 size를 뺀 값이 Top chunk의 크기가 됩니다.
Top chunk의 특징으로는 재사용가능한 chunk가 없고, top chunk의 크기가 마땅할 때 Top chunk에서 쪼개서 할당을 해준다는 점입니다.
이 말은 좀 풀어 설명하자면 만약 동일한 chunk가 이전에 free가 되서 재사용이 가능한 상태일 때는 당연히 그 free되었던 chunk를 사용할 것이고,
Top chunk도 분리할 수 있는 즉, 반환할 크기가 있을 때 반환을 할 수 있다는 것입니다.
#include <stdio.h>
#include <malloc.h>
#include <string.h>
int main(int argc, char *argv[])
{
char *p1 = (char *)malloc(32);
char *p2 = (char *)malloc(32);
char *p3 = (char *)malloc(32);
strcpy(p1,argv[1]);
printf("%s\n", p1);
free(p1);
free(p2);
free(p3);
printf("free");
return 0;
}
위 예제 코드를 통해 확인해봅시다.
malloc()을 호출할 때마다 bp를 걸고 확인을 해보면 top chunk의 size 부분이 chunk의 size만큼 계속 줄어드는 것을 확인 할 수 있습니다.
다음으로 Top chunk에 인접한 chunk가 free되면 병합하는 것을 설명하겠습니다.
이번에는 저번 예제에서 free되는 부분만 조금 고쳐서 확인을 해보겠습니다.
이때 fastbin의 경우는 병합되는것에서 제외가 되니 크기를 좀 주고 해야합니다.
#include <stdio.h>
int main(int argc, char *argv[])
{
char *p1 = malloc(0xf0);
char *p2 = malloc(0xff0);
free(p2);
return 0;
}
top chunk에 가장 인접한 p2를 free해주는 예제 코드입니다.
p1, p2에 각각 0xf0, 0xff0의 크기 만큼 heap영역을 할당 받았을 때 Top chunk의 크기는 0x1fcb0입니다.
다음으로 free(p2); 뒤 top chunk와 인접해 있던 p2는 Top chunk의 크기와 합쳐지면서 Top chunk의 크기가 0x20cb0으로 바뀐것을 확인할 수 있습니다.
이렇듯 Top chunk는 fastbin을 제외하고 좀 큰 크기를 갖은 chunk가 인접해 있을 시 병합을 하여 메모리 관리를 효율적으로 하게 됩니다.
이렇게 해서 정리를 하자면
heap : 동적할당 메모리이다.
heap은 메모리 할당자에 의해 할당 받는 곳인데, 그 종류는 dlmalloc, ptmalloc, jemalloc 등이 있는데, 오늘 다룬 내용은 dlmalloc이다.
이렇게 메모리 할당자를 통해 받은 영역은 chunk라고 부르고, 종류에는 allocated, freed, top 등이 있다.
지금까지 heap에 대한 기본적인 개념에 대해 알아봤습니다.
이상으로 포스팅을 마칩니다.
[삽질 일기 1]
디버깅을 하다보면 PIE가 걸려서 디버깅을 할 수 없을 때가 있는데
PIE를 끄면 됩니다.
No PIE option
[삽질 일기 2]
heap이 메모리상에서 어떻게 돌아가는지 직접 알고싶기에 예제 코드를 작성하고 직접 디버깅해보는 사람들이 있을거라고 생각합니다.
물론 저도 그랬습니다.
heap에 대해 전혀 알고 있는 지식이 없었기 때문에 이런 실수도 하네요..ㅎ
디버깅을 할때 free를 했음에도 fd(forward pointer)만 확인이 되고, bk(back pointer)는 확인이 안될 경우 fastbin일 경우가 다분합니다.
fastbin은 double linked list가 아니고, single linked list이기 때문에 fd만을 이용하고, 보통 작은 크기의 청크가 이에 해당합니다.
ex) 16byte, 24byte, 32byte....,80byte
따라서 예제코드를 작성하실 때 이 보다 메모리를 크게 할당하면 될것입니다.
