You are here: start » » 2008 » 10 » Heap smashing thesis-code

Heap smashing thesis-code

Today I stumbled across a piece of C code I wrote to illustrate some properties of the glibc's dynamic memory allocator1) in my (german) bachelor thesis and figured that the code might actually turn out to be interesting for people seeking to understand or to toy with their heap. If you've never tried to understand your dynamic memory manager this code alone probably won't explain much; however, toying with something you don't understand might not be the worst starting point to change that ,)

The code was written to run on both x86 and x86-64 and to work with glibc versions between 2.3.3 and 2.7; however, other versions might work as well. To the C-coders reading this: sorry for the camelCase and the use of vowels in my identifiers, just couldn't help it after years of python&co ,)

heap_fastbin.c

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
 
#define CHUNK_OFFSET  (2 * sizeof(size_t))
#define printFastbinList(addr)  printBinList(addr, NULL)
 
void* chunk2mem(void* ptr) {
	return ptr + CHUNK_OFFSET;
}
 
void* mem2chunk(void* ptr) {
	return ptr - CHUNK_OFFSET;
}
 
void printChunkAddress(void* ptr, char* name) {
	printf("%s:\tchunk 0x%08lx\n", name, mem2chunk(ptr));
}
 
void printBinList(long* ptr, long* abort) {
	int i = 10;
 
	ptr = mem2chunk(ptr);
 
	if(abort)
		abort = mem2chunk(abort);
 
	printf("bin list: ");
	printf("0x%08lx -> ", ptr);
 
	while(1) {
		if(i-- <= 0) {
			printf("...");
			break;
		}
		// get the address of the next chunk
		ptr = chunk2mem(ptr);
		ptr = (long*) *ptr;
 
		if(ptr == abort) {
			printf("0x%08lx", ptr);
			break;
		}
 
		printf("0x%08lx -> ", ptr);
		fflush(stdout);
	}
	puts("");
}
 
int main(void) {
	size_t size = 0xf;
 
	long* ptr;
	long* tmp;
	int i;
 
	// #1: allocating chunks
	long* x = malloc(size);
	printChunkAddress(x, "x");
 
	long* a = malloc(size);
	long* b = malloc(size);
	long* c = malloc(size);
	printChunkAddress(a, "a");
	printChunkAddress(b, "b");
	printChunkAddress(c, "c");
 
	// #2: freeing a, b, c
	free(a);
	free(b);
	free(c);
 
	puts("\n--8<-- the fastbin before the double-free");
	printFastbinList(c);
 
	// #3: freeing b again
	free(b);
 
	puts("\n--8<-- the fastbin after the double-free");
	printFastbinList(c);
 
	// #4: reallocating b
	b = malloc(size);
 
	// #5: inserting x into the list
	*b = (long) mem2chunk(x);
	*x = (long) mem2chunk(a);
 
	puts("\n--8<-- the manipulated fastbin");
	printFastbinList(c);
 
	// #6: allocating chunks from the manipulated fastbin
	puts("\n--8<-- chunks returned by malloc");
 
	for(i=0; i < 5; i++) {
		ptr = malloc(size);
		printChunkAddress(ptr, "ptr");
	}
 
	exit(0);
}

Further Reading

Basic

Advanced

Authoritative

If you really want to understand your heap you don't have a choice but to read the glibc's code. Here a few excerpts:

glibc-2.7/malloc/malloc.c

/*
  -----------------------  Chunk representations -----------------------
*/
 
 
/*
  This struct declaration is misleading (but accurate and necessary).
  It declares a "view" into memory allowing access to necessary
  fields at known offsets from a given base. See explanation below.
*/
 
struct malloc_chunk {
 
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
 
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
 
  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};
 
 
/*
   malloc_chunk details:
 
    (The following includes lightly edited explanations by Colin Plumb.)
 
    Chunks of memory are maintained using a `boundary tag' method as
    described in e.g., Knuth or Standish.  (See the paper by Paul
    Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
    survey of such techniques.)  Sizes of free chunks are stored both
    in the front of each chunk and at the end.  This makes
    consolidating fragmented chunks into bigger chunks very fast.  The
    size fields also hold bits representing whether chunks are free or
    in use.
 
    An allocated chunk looks like this:
 
 
    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if allocated            | |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                       |M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             User data starts here...                          .
            .                                                               .
            .             (malloc_usable_size() bytes)                      .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk                                     |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 
 
    Where "chunk" is the front of the chunk for the purpose of most of
    the malloc code, but "mem" is the pointer that is returned to the
    user.  "Nextchunk" is the beginning of the next contiguous chunk.
 
    Chunks always begin on even word boundries, so the mem portion
    (which is returned to the user) is also on an even word boundary, and
    thus at least double-word aligned.
 
    Free chunks are stored in circular doubly-linked lists, and look like this:
 
    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk                            |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                         |P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Forward pointer to next chunk in list             |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Back pointer to previous chunk in list            |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Unused space (may be 0 bytes long)                .
            .                                                               .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `foot:' |             Size of chunk, in bytes                           |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 
    The P (PREV_INUSE) bit, stored in the unused low-order bit of the
    chunk size (which is always a multiple of two words), is an in-use
    bit for the *previous* chunk.  If that bit is *clear*, then the
    word before the current chunk size contains the previous chunk
    size, and can be used to find the front of the previous chunk.
    The very first chunk allocated always has this bit set,
    preventing access to non-existent (or non-owned) memory. If
    prev_inuse is set for any given chunk, then you CANNOT determine
    the size of the previous chunk, and might even get a memory
    addressing fault when trying to do so.
 
    Note that the `foot' of the current chunk is actually represented
    as the prev_size of the NEXT chunk. This makes it easier to
    deal with alignments etc but can be very confusing when trying
    to extend or adapt this code.
 
    The two exceptions to all this are
 
     1. The special chunk `top' doesn't bother using the
        trailing size field since there is no next contiguous chunk
        that would have to index off it. After initialization, `top'
        is forced to always exist.  If it would become less than
        MINSIZE bytes long, it is replenished.
 
     2. Chunks allocated via mmap, which have the second-lowest-order
        bit M (IS_MMAPPED) set in their size fields.  Because they are
        allocated one-by-one, each must contain its own trailing size field.
 
*/

In case you are wondering about why I'm doing a few odd things2) in heap_fastbin.c the answer can most likely be found in the excerpt of the evolution of security measures below:

glibc-2.3.3/malloc/malloc.c

/* Take a chunk off a bin list */
#define unlink(P, BK, FD) {                                            \
  FD = P->fd;                                                          \
  BK = P->bk;                                                          \
  FD->bk = BK;                                                         \
  BK->fd = FD;                                                         \
}

glibc-2.3.4/malloc/malloc.c

/* Take a chunk off a bin list */
#define unlink(P, BK, FD) {                                            \
  FD = P->fd;                                                          \
  BK = P->bk;                                                          \
  if (__builtin_expect (FD->bk != P || BK->fd != P, 0))                \
    malloc_printerr (check_action, "corrupted double-linked list", P); \
  else {                                                               \
    FD->bk = BK;                                                       \
    BK->fd = FD;                                                       \
  }                                                                    \
}

glibc-2.7/malloc/malloc.c

/* Take a chunk off a bin list */
#define unlink(P, BK, FD) {                                            \
  FD = P->fd;                                                          \
  BK = P->bk;                                                          \
  if (__builtin_expect (FD->bk != P || BK->fd != P, 0))                \
    malloc_printerr (check_action, "corrupted double-linked list", P); \
  else {                                                               \
    FD->bk = BK;                                                       \
    BK->fd = FD;                                                       \
    if (!in_smallbin_range (P->size)				       \
	&& __builtin_expect (P->fd_nextsize != NULL, 0)) {	       \
      assert (P->fd_nextsize->bk_nextsize == P);		       \
      assert (P->bk_nextsize->fd_nextsize == P);		       \
      if (FD->fd_nextsize == NULL) {				       \
	if (P->fd_nextsize == P)				       \
	  FD->fd_nextsize = FD->bk_nextsize = FD;		       \
	else {							       \
	  FD->fd_nextsize = P->fd_nextsize;			       \
	  FD->bk_nextsize = P->bk_nextsize;			       \
	  P->fd_nextsize->bk_nextsize = FD;			       \
	  P->bk_nextsize->fd_nextsize = FD;			       \
	}							       \
      }	else {							       \
	P->fd_nextsize->bk_nextsize = P->bk_nextsize;		       \
	P->bk_nextsize->fd_nextsize = P->fd_nextsize;		       \
      }								       \
    }								       \
  }                                                                    \
}

,
1) which is basically a heavily fortified version of Wolfram Gloger's ptmalloc2
2) like not just freeing b twice, using only small chunks or reinjecting a chunk of data into the heap that already was on the heap instead of using something fresh from the stack

Discussion

jfjf, 2010/04/29 21:18

hm so is your thesis basic?

demoddemod, 2010/04/29 22:58

I wouldn't say so; however, I'm only looking into heap manipulation briefly in the thesis anyway

Enter your comment
XWYHE
 
blog/2008/10/heap_smashing.txt · Last modified: 2008/12/06 17:39 by demod