C Programming - Heap Overview

An Overview of Heap Overflow

Each threads of a running program has a stack where local variables are stored. In linux all program has a .BSS (global and static uninitialized varibles) and .DATA segment (global and static initialized varibles) along with other segments used by malloc() and allocated with brk() - Sets the end of data segment to the values specified or mmap() - map file into memory, it ask length bytes starting at offset from the file specified by the file descriptor fd into memory, preferably at address start.




malloc() breaks up a chunk of memory allocated using brk() into small parts and gives the user one of those part when a request is made.
It used various techniques like smallest-first, best-fit, next best fit, first-fit etc.
Lot of meta-data about the location of the chunks, ths size of the chunks and other special area for small parts.
All these is information are organized into buckets and in some others into balanced tree structure.

So like stack overflow we can overflow heap also, by overwriting those meta-data.

One such vulenrable program is cprog1.c


/* cprog1.c */
#define BLOCKSIZE 666

int main(int argc, char *argv[])
{
   char *pcBuf1, *pcBuf2;
   pcBuf1 = (char *) malloc (BLOCKSIZE);
   pcBuf2 = (char *) malloc (BLOCKSIZE);
   
   printf("Buffer 1: %p Buffer 2: %p\n",pcBuf1,pcBuf2)
   
   strcpy(pcBuf1,argv[1]);
   
   free(pcBuf2);
   free(pcBuf1);
}
/* EOF */

$> gcc -o cprog1 cprog1.c
$> ./cprog1
Buffer1: 0x9017008 Buffer2: 0x90172a8
*** glibc detected *** double free or corruption (out): 0x90172a8 ***
Aborted


Here we are overflowing 
Buffer2
with the data in 
argv[1]
.
malloc implementations, including Linux's dlmalloc, store extra information in a free chunk. As free chunks can be used to store information about other chunks.

Note: The output of all the programs discussed here will be complier/platform dependent.

Instead of malloc we could have used something like

p = (char *) sbrk(BLOCKSIZE);


But it isn't efficient, portable. What about free?


Allocation Algorithms :

Following are some of the memory allocation algorithms used.


  • First Fit


    • Keep a linked list of free node

    • Search for the first one that's BIG enough


  • Best Fit


    • Keep a linked list of free node

    • Search for the smallest one that's BIG enough


  • Free list: A circular list


Labels:

About this entry

You’re currently reading “C Programming - Heap Overview,” an entry on ANOOB BACKER Technical Blog

Published:
1:08 pm
by -