Software Vulnerabilities and Exploit: Heap Overflow Explained

According to Wikipedia, "A heap overflow is a type of buffer overflow that occurs in the heap data area.". Before we continue with the details of this type of vulnerability, we have to understand how computer memory is structured for any given program. Also we need to keep in mind the following concepts:

• 1 Byte = 8 Bits.
• sizeof(char) = 1 byte.
• sizeof(int) = 4 bytes.
• If we locate an integer at address 0x00000000, the next integer will be at 0x00000004.
• If we locate a character at address 0x00000000, the next character will be at 0x00000001.

Also you must have basic knowledge about how the memory of a program looks like.

How to Exploit The Heap?

One possible scenario is as follows, we locate two memory locations to hold two pieces of data. We try to place more data in the first located location to override the data on the second location. This seems simple. Before we try to do it in C Language, we need to look at the structure of the heap in memory.

Heap Memory Structure

The first thing to know is that heap memory is divided into chunks. One chunk can have one of two states:

• Allocated Chunk
• Free Chunk

An allocated chunk contain the following information: Size of previous chunk (if allocated), Size of chunk (in bytes) with some bit flags and  User data. A free chunk contain the following information: Size of previous chunk, Size of chunk (in bytes),  Forward pointer to next chunk (FD), Back pointer to previous chunk (BK) and unused space (it can be 0).

 Exploiting the Heap

 Now let's return to the scenario that we have talked about before and explain it in more details. When we locate memory in the heap, the top chunks will be the last chunks that was located.

 Heap over flow can happen when we try to fit more data in the first chunk than its size. The next code example shows a vulnerable code in C. 

int main(int c, char ** argv) {

//buffer for 2 chars
char *buf = (char *)malloc(sizeof(char)*2);
//the buffer can have only 2 bytes
//argv[0] will be the name of file
//it can be more than 2 characters -> overflow
strcpy(buf, argv[0]);
}

The next picture shows how the heap will look like when buffer overflow happen.

This is the  basics behind buffer heap overflow. 

Overview of Program Memory Structure

One of the most important concepts that a computer scientist must know about is how the program looks like when its executing. The first thing that happens when we double click a program icon in Windows OS is that it is loaded into memory. The program is not loaded randomly for sure. Each program has a small part of the memory. That small part is partitioned into smaller parts.

The next picture shows a basic overview of how program memory is  divided.

Usual Memory Structure of a Program.

 This structure is used by almost any program that is loaded into memory. Now, let's start by explaining the meaning of each part of the given diagram. In many cases, the higher address are put at the bottom. For instance, the address 0xffffffff will be at the bottom of the diagram (Reverse the diagram).

The Stack

The stack is a place where the program stack is located. From its name, we can infer that it is a "Stack Data structure". A program stack is manly consist of method calls. When a method is called, the return address is "pushed" to the stack. Once the execution of the method is completed, the address is "poped" from the top of the stack. Usually the term "Call Stack" is used to describe this type of stack.

The Heap

For sure you have heard of this term before. The memory heap is something difference from the heap data structure. The memory heap is a place that is used for dynamically located memory. It is used for the data that is given at the run time. For example, the size of input string from the user is unknown. In this case, it will be placed at the heap. The heap will only contain program data. In C programming language, the system call "malloc" is used to locate heap space and the system call "free" is used to free the space. The next code example shows how it is done in C language.

#include <stdio.h>
#include <stdlib.h>

int main() {
    int numOfBytes = 100;
    //a buffer that will contain user input
    char * input;
    //locate space for user input
    input = malloc(numOfBytes);
    //read string from the user
    fgets(input,numOfBytes,stdin);
    printf("You give me '%s'",input);
    //must free memory after use
    free(input);
    return 0;
}

Uninitialized Data

Also known as BSS Segment. This segment of memory contains the global variables and static data that has not been initialized. For example, the variable "static int myInt; " will be located at uninitialized data segment.

Initialized Data 

This part of memory will contain the global and static variables which have been initialized within the code. This means that the variable can be accessed from any where in the program.

Code 

This part of memory contains the actual instructions of the program. Usually, this part of memory is placed in the top of the stack or bellow the heap in order to prevent overflows from override the data inside it.


This is the most basic view of program memory. For sure there are many thins inside each section of the memory but we only want to look at the abstract view.