At the physical level, computer memory consists of a large number of flip flops. Each flip flop consists of a few transistors, and is capable of storing one bit. Individual flip flops are addressable by a unique identifier, so we can read and overwrite them. Thus, conceptually, we can think of all of our computer’s memory as just one giant array of bits that we can read and write.
Since as humans, we are not that good at doing all of our thinking and arithmetic in bits, we group them into larger groups, which together can be used to represent numbers. 8 bits are called 1 byte; beyond bytes, there are words (which are sometimes 16, sometimes 32 bits). Thus, more often, we conceptually regard our computer’s memory as one large (size 232 or so) array of bytes.
What is the Heap and How Big is it?
When you compile a program, you’re generating an executable called a program. A program is said to be ‘executing’ when it has been loaded into main memory and has different resources allocated to it. When a process is under execution, it has its own address space that looks something like this:
A heap is a part of this address space.
The heap is part of the process memory and it does not have a fixed size. Heap memory allocation is performed by the C library when you call malloc (calloc, realloc) and free. This means that the program can ‘request’ and ‘release’ memory from the heap segment whenever it requires. Also, this memory is global, i.e. it can be accessed and modified from anywhere within a program and is not localized to the function where it is allocated. This is accomplished using ‘pointers’ to reference dynamically allocated memory which in turn leads to a small degradation in performance as compared to using local variables (on the stack).
Memory in the heap is allocated in ‘chunks’. The structure of a chunk is something like this:
Allocated chunk:
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if unallocated (P clear) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |A|M|P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User data starts here... .
. .
. (malloc_usable_size() bytes) .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (size of chunk, but used for application data) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of next chunk, in bytes |A|0|1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Free chunk:
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if unallocated (P clear) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
'head:' | Size of chunk, in bytes |A|0|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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of next chunk, in bytes |A|0|0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
A bin is list (singly or doubly linked list) of free chunks. They’re categorized based on the size of chunks they can hold.
Exploiting the Heap
Double Free ()
Freeing a resource more than once can lead to a memory leak. The data structure implemented by the allocator gets corrupter and can be exploited by the attacker. Since glibc has a protective measure against the double free() exploitation, we will free another chunk it between. By doing so, we can return the same chunk by two different malloc()s. If the attacker is in control of one of the pointers, they can modify the memory leading to different attacks, including injecting the address of a malicious program which could be executed.
Consider the following code:
a = malloc(10); //0xb16010
b = malloc(10); //0xb16030
c = malloc(10); //0xb16060
free(a);
free(b); //To circumvent glibc's check
free(a); // DOUBLE FREE!
x = malloc(10); //0xb16010
e = malloc(10); //0xb16030
z = malloc(10); //0xb16010 - Same address as 'x' !
How did that happen?
The state of the bin through the code:
- ‘a’ freed:
head -> a -> tail
- ‘b’ freed:
head -> b -> a -> tail
- ‘a’ freed:
head -> a -> b -> a -> tail
- malloc() request for ‘x’
head -> b -> a -> tail
- malloc() request for ‘y’
head -> a -> tail
- malloc() request for ‘z’
head -> tail
Now that ‘x’ and ‘y’ point to the same memory location, any change in one will reflect in the other. Note: This exploitation only works when the size of the chunks allocated are in the fastbin list.
This was an extremely simple exploitation of the heap but you can read up on some of the more sophisticated ones:
Resources
