Related Blog Items

• Differences between new, malloc; delete, free
• What if I forget the [] when deleteing array allocated via new T[n]?
• C/C++ Questions asked in various job interviews
• What are the two steps that happen when I say delete p?
• Buffer Overruns - part1

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

[highlight lang=”CPP”]
#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: %pn”,pcBuf1,pcBuf2)
strcpy(pcBuf1,argv[1]);
free(pcBuf2);
free(pcBuf1);
}
[/highlight]

$> gcc -o cprog1 cprog1.c
$> ./cprog1
Buffer1: 0×9017008 Buffer2: 0×90172a8***glibc detected *** double free or corruption (out): 0×90172a8 ***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

[tags] heap usage, heap, heap overview, heap information, new malloc heap[/tags]

Popularity: 11%

You need to log on to convert this article into PDF

Related Blog Items

• Differences between new, malloc; delete, free
• What if I forget the [] when deleteing array allocated via new T[n]?
• C/C++ Questions asked in various job interviews
• What are the two steps that happen when I say delete p?
• Buffer Overruns - part1

This entry was written by openasthra and posted on December 22, 2006 at 10:19 am and filed under C/C++ Programming Concepts, Multithreading. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.