==Phrack Inc.==

Volume 0x0b, Issue 0x39, Phile #0x09 of 0x12

|=---------------------=[ Once upon a free()... ]=-----------------------=|

|=-----------------------------------------------------------------------=|

|=--------------=[ anonymous <d45a312a@author.phrack.org> ]=-------------=|

On the Unix system, and later in the C standard library there are functions

to handle variable amounts of memory in a dynamic way. This allows programs

to dynamically request memory blocks from the system. The operating system

only provides a very rough system call 'brk' to change the size of a big

memory chunk, which is known as the heap.

On top of this system call the malloc interface is located, which provides

a layer between the application and the system call. It can dynamically

split the large single block into smaller chunks, free those chunks on

request of the application and avoid fragmentation while doing so. You can

compare the malloc interface to a linear file system on a large, but

dynamically sized raw device.

There are a few design goals which have to be met by the malloc interface:

- stability

- performance

- avoidance of fragmentation

- low space overhead

There are only a few common malloc implementations. The most common ones

are the System V one, implemented by AT&T, the GNU C Library implementation

and the malloc-similar interface of the Microsoft operating systems

(RtlHeap*).

Here is a table of algorithms and which operating systems use them:

Algorithm | Operating System

------------------------+--------------------------------------------------

BSD kingsley | 4.4BSD, AIX (compatibility), Ultrix

BSD phk | BSDI, FreeBSD, OpenBSD

GNU Lib C (Doug Lea) | Hurd, Linux

System V AT&T | Solaris, IRIX

Yorktown | AIX (default)

RtlHeap* | Microsoft Windows *

------------------------+--------------------------------------------------

It is interesting to see that most of the malloc implementations are very

easy to port and that they are architecture independent. Most of those

implementations just build an interface with the 'brk' system call. You can

change this behaviour with a #define. All of the implementations I have

come across are written in ANSI C and just do very minimal or even no

sanity checking. Most of them have a special compilation define that

includes asserts and extra checks. Those are turned off by default in the

final build for performance reasons. Some of the implementations also

offer extra reliability checks that will detect buffer overflows. Those

are made to detect overflows while development, not to stop exploitation

in the final release.

Storing management info in-band

Most malloc implementations share the behaviour of storing their own

management information, such as lists of used or free blocks, sizes of

memory blocks and other useful data within the heap space itself. Since the

whole idea of malloc/free is based on the dynamic requirements the

application has, the management info itself occupies a variable amount of

data too. Because of this, the implementation can seldomly just reserve a

certain amount of memory for its own purposes, but stores the management

information "in-band", right after and before the blocks of memory that are

used by the application.

Some applications do request a block of memory using the malloc interface,

which later happens to be vulnerable to a buffer overflow. This way, the

data behind the chunk can be changed. Possibly the malloc management

structures can be compromised. This has been demonstrated first by Solar

Designer's wizard-like exploit [1].

The central attack of exploiting malloc allocated buffer overflows is to

modify this management information in a way that will allow arbitrary

memory overwrites afterwards. This way pointers can be overwritten within

the writeable process memory, hence allowing modification of return

addresses, linkage tables or application level data.

To mount such an attack, we have to take a deep look within the internal

workings of the implementation we want to exploit. This article discusses

the commonly used GNU C Library and the System V implementation and how to

gain control over a process using buffer overflows which occur in malloced

buffers under Linux, Solaris and IRIX systems.

System V malloc implementation

==============================

IRIX and Solaris use an implementation which is based on self-adjusting

binary trees. The theoretical background of this implementation has been

described in [2].

The basic idea of this implementation is to keep lists of equally sized

malloc chunks within a binary tree. If you allocate two chunks of the

same size, they will be within the same node and within the same list of this

node. The tree is ordered by the size of its elements.

The TREE structure

The definition of the TREE structure can be found in the mallint.h, along

with some easy-to-use macros to access its elements. The mallint.h file

can be found in the source distribution of the Solaris operating system

[4]. Although I cannot verify that IRIX is based on the same source, there

are several similarities which indicated this. The malloc interface

internally creates the same memory layout and functions, besides some 64

bit alignments. You can utilize the Solaris source for your IRIX exploits,

too.

To allow each tree element to be used for a different purpose to avoid

overhead and force an alignment, each TREE structure element is defined

as a union:

/* the proto-word; size must be ALIGN bytes */

typedef union _w_ {

size_t w_i; /* an unsigned int */

struct _t_ *w_p; /* a pointer */

char w_a[ALIGN]; /* to force size */

} WORD;

Central TREE structure definition:

/* structure of a node in the free tree */

typedef struct _t_ {

WORD t_s; /* size of this element */

WORD t_p; /* parent node */

WORD t_l; /* left child */

WORD t_r; /* right child */

WORD t_n; /* next in link list */

WORD t_d; /* dummy to reserve space for self-pointer */

} TREE;

The 't_s' element of the chunk header contains the rounded up value of the

size the user requested when he called malloc. Since this size is always

rounded up to a word boundary, at least the lower two bits of the 't_s'

elements are unused - they normally would have the value of zero all the

time. Instead of being zero, they are ignored for all size-related

operations. They are used as flag elements.

From the malloc.c source it reads:

BIT0: 1 for busy (block is in use), 0 for free.

BIT1: if the block is busy, this bit is 1 if the preceding block in

contiguous memory is free. Otherwise, it is always 0.

TREE Access macros:

/* usable # of bytes in the block */

#define SIZE(b) (((b)->t_s).w_i)

/* free tree pointers */

#define PARENT(b) (((b)->t_p).w_p)

#define LEFT(b) (((b)->t_l).w_p)

#define RIGHT(b) (((b)->t_r).w_p)

/* forward link in lists of small blocks */

#define AFTER(b) (((b)->t_p).w_p)

/* forward and backward links for lists in the tree */

#define LINKFOR(b) (((b)->t_n).w_p)

#define LINKBAK(b) (((b)->t_p).w_p)

For all allocation operations a certain alignment and minimum size is

enforced, which is defined here:

#define WORDSIZE (sizeof (WORD))

#define MINSIZE (sizeof (TREE) - sizeof (WORD))

#define ROUND(s) if (s % WORDSIZE) s += (WORDSIZE - (s % WORDSIZE))

The tree structure is the central element of each allocated chunk. Normally

only the 't_s' and 't_p' elements are used, and user data is stored from

't_l' on. Once the node is freed, this changes and the data is reused to

manage the free elements more efficiently. The chunk represents an element

within the splay tree. As more chunks get freed, the malloc implementation

tries to merge the free chunks right next to it. At most FREESIZE (32 by

default) chunks can be in this dangling free state at the same time. They

are all stored within the 'flist' array. If a call to free is made while

the list is already full, the old element at this place falls out and is

forwarded to realfree. The place is then occupied by the newly freed

element.

This is done to speed up and avoid defragmentation in cases where a lot of

calls to free are made in a row. The real merging process is done by

realfree. It inserts the chunk into the central tree, which starts at the

'Root' pointer. The tree is ordered by the size of its elements and

is self-balancing. It is a so called "splay tree", in which the elements

cycle in a special way to speed up searches (see google.com "splay tree"

for further information). This is not much of importance here, but keep in

mind that there are two stages of free chunks: one being within the flist

array, and one within the free-elements tree starting at 'Root'.

There are some special management routines for allocating small chunks of

memory, which happen to have a size below 40 bytes. Those are not

considered here, but the basic idea is to have extra lists of them, not

keeping them within a tree but in lists, one for each WORD matching size

below 40.

There is more than one way to exploit a malloc based buffer overflow,

however here is one method which works against both, IRIX and Solaris.

As a chunk is realfree'd, it is checked whether the neighbor-chunks are

already within the realfree'd tree. If it is the case, the only thing

that has to be done is to logically merge the two chunks and reorder its

position within the tree, as the size has changed.

This merging process involves pointer modification within the tree, which

consists of nodes. These nodes are represented by the chunk header

itself. Pointers to other tree elements are stored there. If we can

overwrite them, we can possibly modify the operation when merging the

chunks.

Here is, how it is done in malloc.c:

(modified to show the interesting part of it)

static void

realfree(void *old)

{

TREE *tp, *sp, *np;

size_t ts, size;

/* pointer to the block */

tp = BLOCK(old);

ts = SIZE(tp);

if (!ISBIT0(ts))

return;

CLRBITS01(SIZE(tp));

/* see if coalescing with next block is warranted */

np = NEXT(tp);

if (!ISBIT0(SIZE(np))) {

if (np != Bottom)

t_delete(np);

SIZE(tp) += SIZE(np) + WORDSIZE;

}

We remember NEXT points to the chunk directly following the current one. So

we have this memory layout:

tp old np

| | |

[chunk A header] [chunk A data] | [chunk B or free ....]

|

chunk boundary

In the usual situation the application has allocated some space and got a

pointer (old) from malloc. It then messes up and allows a buffer overflow

of the chunk data. We cross the chunk boundary by overflowing and hit the

data behind, which is either free space or another used chunk.

np = NEXT(tp);

Since we can only overflow data behind 'old', we cannot modify the header

of our own chunk. Therefore we cannot influence the 'np' pointer in any

way. It always points to the chunk boundary.

Now a check is made to test if it is possible to merge forward, that is our

chunk and the chunk behind it. Remember that we can control the chunk

to the right of us.

if (!ISBIT0(SIZE(np))) {

if (np != Bottom)

t_delete(np);

SIZE(tp) += SIZE(np) + WORDSIZE;

}

BIT0 is zero if the chunk is free and within the free elements tree. So if

it is free and not the last chunk, the special 'Bottom' chunk, it is

deleted from the tree. Then the sizes of both chunks are added and later in

the code of the realfree function the whole resized chunk is reinserted

into the tree.

One important part is that the overflowed chunk must not be the last chunk

within the malloc space, condition:

1. Overflowed chunk must not be the last chunk

Here is how the 't_delete' function works:

static void

t_delete(TREE *op)

{

TREE *tp, *sp, *gp;

/* if this is a non-tree node */

if (ISNOTREE(op)) {

tp = LINKBAK(op);

if ((sp = LINKFOR(op)) != NULL)

LINKBAK(sp) = tp;

LINKFOR(tp) = sp;

return;

}

There are other cases, but this is the one easiest to exploit. As I am

already tired of this, I will just explain this one here. The others are

very similar (look at malloc.c).

ISNOTREE compares the 't_l' element of the TREE structure with -1. -1 is

the special marker for non-tree nodes, which are used as doubly linked list,

but that does not matter.

Anyway, this is the first condition we have to obey:

2. fake->t_l = -1;

Now the unlinking between FOR (t_n) and BAK (t_p) is done, which can be

rewritten as:

t1 = fake->t_p

t2 = fake->t_n

t2->t_p = t1

t1->t_n = t2

Which is (written in pseudo-raw-assignments which happen at the same time):

[t_n + (1 * sizeof (WORD))] = t_p

[t_p + (4 * sizeof (WORD))] = t_n

This way we can write to arbitrary addresses together with valid

addresses at the same time. We choose to use this:

t_p = retloc - 4 * sizeof (WORD)

t_n = retaddr

This way retloc will be overwritten with retaddr and *(retaddr + 8) will be

overwritten with retloc. If there is code at retaddr, there should be a

small jump over the bytes 8-11 to not execute this address as code. Also,

the addresses can be swapped if that fits the situation better.

Finally our overwrite buffer looks like this:

| <t_s> <t_p> <t_l> <j: t_r> <t_n> <j: t_d>

|

chunk boundary

Where: t_s = some small size with lower two bits zeroed out

t_p = retloc - 4 * sizeof (WORD)

t_l = -1

t_r = junk

t_n = retaddr

t_d = junk

Note that although all of the data is stored as 32 bit pointers, each

structure element occupies eight bytes. This is because of the WORD

union, which forces at least ALIGN bytes to be used for each element.

ALIGN is defined to eight by default.

So a real overflow buffer behind the chunk boundary might look like:

ff ff ff f0 41 41 41 41 ef ff fc e0 41 41 41 41 | ....AAAA....AAAA

ff ff ff ff 41 41 41 41 41 41 41 41 41 41 41 41 | ....AAAAAAAAAAAA

ef ff fc a8 41 41 41 41 41 41 41 41 41 41 41 41 | ....AAAAAAAAAAAA

All 'A' characters can be set arbitrarily. The 't_s' element has been

replaced with a small negative number to avoid NUL bytes. If you want to use

NUL bytes, use very few. Otherwise the realfree function will crash later.

The buffer above will overwrite:

[0xeffffce0 + 32] = 0xeffffca8

[0xeffffca8 + 8] = 0xeffffce0

See the example code (mxp.c) for a more in-depth explanation.

To summarize down the guts if you happen to exploit a malloc based buffer

overflow on IRIX or Solaris:

1. Create a fake chunk behind the one you overflow

2. The fake chunk is merged with the one you overflow as it is

passed to realfree

3. To make it pass to realfree it has to call malloc() again or

there have to be a lot of successive free() calls

4. The overflowed chunk must not be the last chunk (the one before

Bottom)

5. Prepend the shellcode/nop-space with jump-aheads to not execute

the unavoidable unlink-overwrite address as code

6. Using the t_splay routines attacks like this are possible too, so

if you cannot use the attack described here (say you cannot

write 0xff bytes), use the source luke.

There are a lot of other ways to exploit System V malloc management, way

more than there are available in the GNU implementation. This is a result

of the dynamic tree structure, which also makes it difficult to understand

sometimes. If you have read until here, I am sure you can find your own

ways to exploit malloc based buffer overflows.

GNU C Library implementation

============================

The GNU C library keeps the information about the memory slices the

application requests in so called 'chunks'. They look like this (adapted

from malloc.c):

+----------------------------------+

chunk -> | prev_size |

+----------------------------------+

| size |

+----------------------------------+

mem -> | data |

: ... :

+----------------------------------+

nextchunk -> | prev_size ... |

: :

Where mem is the pointer you get as return value from malloc(). So if you

do a:

unsigned char * mem = malloc (16);

Then 'mem' is equal to the pointer in the figure, and (mem - 8) would be

equal to the 'chunk' pointer.

The 'prev_size' element has a special function: If the chunk before the

current one is unused (it was free'd), it contains the length of the chunk

before. In the other case - the chunk before the current one is used -

'prev_size' is part of the 'data' of it, saving four bytes.

The 'size' field has a special meaning. As you would expect, it contains

the length of the current block of memory, the data section. As you call

malloc(), four is added to the size you pass to it and afterwards the size

is padded up to the next double-word boundary. So a malloc(7) will become a

malloc(16), and a malloc(20) will become malloc(32). For malloc(0) it will

be padded to malloc(8). The reason for this behaviour will be explained in

the latter.

Since this padding implies that the lower three bits are always zero and

are not used for real length, they are used another way. They are used to

indicate special attributes of the chunk. The lowest bit, called

PREV_INUSE, indicates whether the previous chunk is used or not. It is set

if the next chunk is in use. The second least significant bit is set if the

memory area is mmap'ed -- a special case which we will not consider. The

third least significant bit is unused.

To test whether the current chunk is in use or not, we have to check the

next chunk's PREV_INUSE bit within its size value.

Once we free() the chunk, using free(mem), some checks take place and the

memory is released. If its neighbour blocks are free, too (checked using

the PREV_INUSE flag), they will be merged to keep the number of reuseable

blocks low, but their sizes as large as possible. If a merge is not

possible, the next chunk is tagged with a cleared PREV_INUSE bit, and the

chunk changes a bit:

+----------------------------------+

chunk -> | prev_size |

+----------------------------------+

| size |

+----------------------------------+

mem -> | fd |

+----------------------------------+

| bk |

+----------------------------------+

| (old memory, can be zero bytes) |

: :

nextchunk -> | prev_size ... |

: :

You can see that there are two new values, where our data was previously

stored (at the 'mem' pointer). Those two values, called 'fd' and 'bk' -

forward and backward, that is, are pointers. They point into a double

linked list of unconsolidated blocks of free memory. Every time a new free

is issued, the list will be checked, and possibly unconsolidated blocks

are merged. The whole memory gets defragmented from time to time to release

some memory.

Since the malloc size is always at least 8 bytes, there is enough space for

both pointers. If there is old data remaining behind the 'bk' pointer, it

remains unused until it gets malloc'd again.

The interesting thing regarding this management, is that the whole internal

information is held in-band -- a clear channeling problem.

(just as with format string commands within the string itself, as control

channels in breakable phonelines, as return addresses within stack memory,

etc).

Since we can overwrite this internal management information if we can

overwrite a malloced area, we should take a look at how it is processed

later on. As every malloc'ed area is free()'d again in any sane program,

we take a look at free, which is a wrapper to chunk_free() within malloc.c

(simplified a bit, took out #ifdef's):

static void

chunk_free(arena *ar_ptr, mchunkptr p)

{

size_t hd = p->size; /* its head field */

size_t sz; /* its size */

int idx; /* its bin index */

mchunkptr next; /* next contiguous chunk */

size_t nextsz; /* its size */

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);

Since the malloc management keeps chunks within special structures called

'arenas', it is now tested whether the current chunk that should be free

directly borders to the 'top' chunk -- a special chunk. The 'top' chunk is

always the top-most available memory chunk within an arena, it is the border

of the available memory. The whole if-block is not interesting for typical

buffer overflows within the malloc space.

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 ((unsigned long)(sz) >= (unsigned long)trim_threshold)

main_trim(top_pad);

return;

}

Now the 'size' of the current chunk is tested whether the previous chunk is

unused (testing for the PREV_INUSE flag). If this is the case, both chunks

are merged.

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);

}

Now the same is done vice versa. It is checked whether the chunk in front

of the current chunk is free (testing for the PREV_INUSE flag of the size

two chunks ahead). If this is the case the chunk is also merged into the

current one.

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);

}

As Solar Designer showed us, it is possible to use the 'unlink' macro to

overwrite arbitrary memory locations. Here is how to do:

A usual buffer overflow situation might look like:

mem = malloc (24);

gets (mem);

...

free (mem);

This way the malloc'ed chunk looks like this:

[ prev_size ] [ size P] [ 24 bytes ... ] (next chunk from now)

[ prev_size ] [ size P] [ fd ] [ bk ] or [ data ... ]

As you can see, the next chunk directly borders to our chunk we overflow.

We can overwrite anything behind the data region of our chunk, including

the header of the following chunk.

If we take a closer look at the end of the chunk_free function, we see this

code:

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);

}

The inuse_bit_at_offset, is defined as macro in the beginning of malloc.c:

#define inuse_bit_at_offset(p, s)\

(((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)

Since we control the header of the 'next' chunk we can trigger the whole if

block at will. The inner if statement is uninteresting, except our chunk is

bordering to the top-most chunk. So if we choose to trigger the outer if

statement, we will call unlink, which is defined as macro, too:

#define unlink(P, BK, FD) \

{ \

BK = P->bk; \

FD = P->fd; \

FD->bk = BK; \

BK->fd = FD; \

}

The unlink is called with a pointer to a free chunk and two temporary

pointer variables, called bck and fwd. It does this to the 'next' chunk

header:

*(next->fd + 12) = next->bk

*(next->bk + 8) = next->fd

They are not swapped, but the 'fd' and 'bk' pointers point to other chunks.

This two chunks being pointed to are linked, zapping the current chunk from

the table.

So to exploit a malloc based buffer overflow, we have to write a bogus

header in the following chunk and then wait for our chunk getting free'd.

[buffer .... ] | [ prev_size ] [ size ] [ fd ] [ bk ]

'|' is the chunk boundary.

The values we set for 'prev_size' and 'size' do not matter, but two

conditions have to be met, in case it should work:

a) the least significant bit of 'size' has to be zero

b) both, 'prev_size' and 'size' should be add-safe to a pointer that is

read from. So either use very small values up to a few thousand, or -

to avoid NUL bytes - use big values such as 0xfffffffc.

c) you have to ensure that at (chunk_boundary + size + 4) the lowest bit

is zeroed out (0xfffffffc will work just fine)

'fd' and 'bk' can be set this way (as used in Solar Designers Netscape

Exploit):

fd = retloc - 12

bk = retaddr

But beware, that (retaddr + 8) is being written to and the content there

will be destroyed. You can circumvent this by a simple '\xeb\x0c' at

retaddr, which will jump twelve bytes ahead, over the destroyed content.

Well, however, exploitation is pretty straight forward now:

<jmp-ahead, 2> <6> <4 bogus> <nop> <shellcode> |

\xff\xff\xff\xfc \xff\xff\xff\xfc <retloc - 12> <retaddr>

Where '|' is the chunk boundary (from that point we overflow). Now, the

next two negative numbers are just to survive a few checks in free() and to

avoid NUL bytes. Then we store (retloc - 12) properly encoded and then the

return address, which will return to the 'jmp-ahead'. The buffer before the

'|' is the same as with any x86 exploit, except for the first 12 bytes,

because we have to take care of the extra write operation by the unlink

macro.

Off-by-one / Off-by-five

------------------------

It is possible to overwrite arbitrary pointers, even in cases where you can

overwrite only five bytes, or - in special cases - only one byte. When

overwriting five bytes the memory layout has to look like:

[chunk a] [chunk b]

Where chunk a is under your control and overflowable. Chunk b is already

allocated as the overflow happens. By overwriting the first five bytes of

chunk b, we trash the 'prev_size' element of the chunks header and the

least significant byte of the 'size' element. Now, as chunk b is free()'d,

backward consolidation pops in, since 'size' has the PREV_INUSE flag

cleared (see below). If we supply a small value for 'prev_size', which is

smaller than the size of chunk a, we create a fake chunk structure:

[chunk a ... fakechunk ...] [chunk b]

|

p

Where prev_size of chunk b points relativly negative to the fake chunk.

The code which is exploitable through this setting was already discussed:

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);

}

'hd' is the size element of chunk b. When we overwrite it, we clear out the

lower two bits, so PREV_INUSE is cleared and the if condition is matched

(NUL will do it in fact). In the next few instructions 'p', which was a

pointer to chunk b originally, is relocated to our fakechunk. Then the

unlink macro is called and we can overwrite the pointers as usual. We use

backward consolidation now, while in the previous description we have used

forward consolidation. Is this all confusing? Well, when exploiting malloc

overflows, do not worry about the details, they will become clearer as you

understand the malloc functions from a broader scope.

For a really well done overview and description of the malloc

implementation in the GNU C Library, take a look at the GNU C Library

reference manual [3]. It makes a good read for non-malloc related things,

too.

Possible obstacles and how to get over with them

================================================

As with any new exploitation technique people will show up which have the

'perfect' solution to the problem in their head or in form of a patch to

the malloc functions. Those people - often ones who have never written

an exploit themselves - are misleading into a wrong sense of security and I

want to leave a few words about those approaches and why they seldomly work.

There are three host based stages where you can stop a buffer overflow

resulting in a compromise:

1. The bug/overflow stage

This is the place where the real overflow happens, where data is

overwritten. If this place is known, the origin of the problem can be fixed

(at source level). However, most approaches argue that this place is not

known and therefore the problem cannot be fixed yet.

2. The activation stage

After the overflow happened parts of the data of the application are

corrupted. It does not matter what kind of data, whether it is a stack

frame, a malloc management record or static data behind a buffer. The

process is still running its own path of code, the overwritten data is

still passive. This stage is everything after the overflow itself and

before the seize of execution control. This is where the natural,

non-artificially introduced hurdles for the attacker lies, code which must

be passed in a certain way.

3. The seized stage

This is everything after control has been redirected from its original

path of execution. This is the stage where nopspace and shellcode is

executed, where no real exploitation hurdles are left.

Now for the protection systems. Most of the "non-exec stack" and "non-exec

heap" patches try to catch the switch from stage two to three, where

execution is seized, while some proprietary systems check for the origin of

a system call from within kernel space. They do not forbid you to run code

this way, they try to limit what code can be run.

Those systems which allow you to redirect execution in the first place are

fundamentally flawed. They try to limit the exploitation in a black-listing

way, by trying to plug the places you may want to go to. But if you can

execute legal code within the process space its almost everytime enough to

compromise the process as a whole.

Now for the more challenging protections, which try to gripe you in stage

two. Those include - among others - libsafe, StackGuard, FormatGuard, and

any compiler or library based patches. They usually require a recompilation

or relinking of your existing code, to insert their security 'measures'

into your code. This includes canary values, barriers of check bytes or

reordering and extensive checking of sanity before doing things which might

be bad. While sanity checking in general is a good policy for security, it

cannot fix stuff that was broken before. Every of those protections is

assuming a certain situation of a bug which might appear in your program

and try to predict the results of an attacker abusing the bug. They setup

traps which they assume you will or have to trigger to exploit the bug.

This is done before your control is active, so you cannot influence it

much except by choosing the input data. Those are, of course much more

tight than protection systems which only monitor stage three, but still

there are ways around them. A couple of ways have been discussed in the

past, so I will not go into depth here. Rather, I will briefly address on a

protection which I already see on the horizon under a name like

'MallocGuard'.

Such a protection would not change the mechanism of malloc management

chunks much, since the current code has proved to be effective. The malloc

function plays a key role in overall system performance, so you cannot

tweak freely here. Such a protection can only introduce a few extra checks,

it cannot verify the entire consistency everytime malloc() is called. And

this is where it is flawed: Once you seize control over one malloc chunk

information, you can seize control over other chunks too. Because chunks

are 'walked' by using either stored pointers (SysV) or stored lengths

(GlibC), it is possible to 'create' new chunks. Since a sanity check would

have to assume inconsistency of all chunks in the worst case, it would have

to check all chunks by walking them. But this would eat up too much

performance, so its impossible to check for malloc overflows easily while

still keep a good performance. So, there will be no 'MallocGuard', or it

will be a useless guard, in the tradition of useless pseudo protections. As

a friend puts it - 'for every protection there is an anti-protection'.

Thanks

======

I would like to thank all proofreaders and correctors. For some really

needed corrections I thank MaXX, who wrote the more detailed article about

GNU C Library malloc in this issue of Phrack, kudos to him ! :)

References

==========

[1] Solar Designer,

http://www.openwall.com/advisories/OW-002-netscape-jpeg.txt

[2] DD Sleator, RE Tarjan, "Self-Adjusting Binary Trees", 1985,

http://www.acm.org/pubs/citations/journals/jacm/1985-32-3/p652-sleator/

http://www.math.tau.ac.il/~haimk/adv-ds-2000/sleator-tarjan-splay.pdf

[3] The GNU C Library

http://www.gnu.org/manual/glibc-2.2.3/html_node/libc_toc.html

[4] Solaris 8 Foundation Source Program

http://www.sun.com/software/solaris/source/

|=[ EOF ]=---------------------------------------------------------------=|