What Is a Heap?

When a program is running, each thread has a stack where local variables are stored. But for global variables, or variables too large to fit on the stack, the program needs another section of writable memory available as a storage space. In fact, it may not know at compile time how much memory it will need, so these segments are often allocated at runtime, using a special system call. Typically a Linux program has a .bss (global variables that are uninitialized ) and a .data segment (global variables that are initialized ) along with other segments used by malloc() and allocated with the brk() or mmap() system calls. You can see these segments with the gdb command maintenance info sections . Any segment that is writable can be referred to as a heap although often only the segments specifically allocated for use by malloc() are considered true heaps. As a hacker, you should ignore terminology and focus on the fact that any writable page of memory offers you a chance to take control.

What follows is gdb before the program ( basicheap ) runs:

 (gdb) maintenance info sections Exec file:     `/home/dave/BOOK/basicheap', file type elf32-i386.         0x08049434->0x08049440 at 0x00000434: .data ALLOC LOAD DATA HAS_CONTENTS     0x08049440->0x08049444 at 0x00000440: .eh_frame ALLOC LOAD DATA HAS_CONTENTS     0x08049444->0x0804950c at 0x00000444: .dynamic ALLOC LOAD DATA HAS_CONTENTS     0x0804950c->0x08049514 at 0x0000050c: .ctors ALLOC LOAD DATA HAS_CONTENTS     0x08049514->0x0804951c at 0x00000514: .dtors ALLOC LOAD DATA HAS_CONTENTS     0x0804951c->0x08049520 at 0x0000051c: .jcr ALLOC LOAD DATA HAS_CONTENTS     0x08049520->0x08049540 at 0x00000520: .got ALLOC LOAD DATA HAS_CONTENTS     0x08049540->0x08049544 at 0x00000540: .bss ALLOC 

Here are a few lines from the run trace:

 brk(0) = 0x80495a4 brk(0x804a5a4) = 0x804a5a4 brk(0x804b000) = 0x804b000 

What follows is the output from the program, showing the addresses of two malloced spaces:

 buf=0x80495b0 buf2=0x80499b8 

Here is maintenance info sections again, showing the segments used while the program was running. Notice the stack segment (the last one) and the segments that contain the pointers themselves ( load2 ).

 0x08048000->0x08048000 at 0x00001000: load1 ALLOC LOAD READONLY CODE HAS_CONTENTS     0x08049000->0x0804a000 at 0x00001000: load2 ALLOC LOAD HAS_CONTENTS     ...     0xbfffe000->0xc0000000 at 0x0000f000: load11 ALLOC LOAD CODE HAS_CONTENTS     (gdb) print/x $esp  = 0xbffff190 

How a Heap Works

Using brk() or mmap() every time the program needs more memory is slow and unwieldy. Instead of doing that, each libc implementation has provided malloc() , realloc() , and free() for programmers to use when they need more memory, or are finished using a particular block of memory.

malloc() breaks up a big block of memory allocated with brk() into chunks and gives the user one of those chunks when a request is made (for instance, if the user asks for 1000 bytes), potentially using a large chunk and splitting it into two chunks to do so. Likewise, when free() is called, it should decide if it can take the newly freed chunk, and potentially the chunks before and after it, and collect them into one large chunk. This process reduces fragmentation (lots of little used chunks interspersed with lots of little free chunks) and prevents the program from having to use brk() too often, if at all.

To be efficient, any malloc() implementation stores a lot of meta-data about the location of the chunks, the size of the chunks, and perhaps some special areas for small chunks. It also organizes this informationin dlmalloc, it is organized into buckets, and in many other malloc implementations it is organized into a balanced tree structure. (Don't worry if you don't know exactly how a balanced tree structure worksyou can always look it up if you need to, and you likely won't.)

This information is stored in two places: in global variables used by the malloc() implementation itself, and in the memory block before and/or after the allocated user space. So just like in a stack overflow, where the frame pointer and saved instruction pointer were stored directly after a buffer you could overflow, the heap contains important information about the state of memory stored directly after any user-allocated buffer.