Heap 0x01

Introduction

Before getting into the glibc’s heap, let’s take a really brief look at the stack. Then we can take a look at the heap. On the part 2, we will cover the free function and its bins.

The stack

On modern operating systems, each thread of an application has its own stack. The stack has a fixed size, which is allocated by the operating system and given to the process when it starts. It works LIFO and generally stores local variables, return address pointers, function arguments, etc.

The heap

The heap is a tad different. It deals with dynamically allocated memory. This means that the heap won’t have a fixed size, as it grows as more memory is needed. The way the heap is managed can vary according to the implementation being used: The heap implementation and how it works on Linux can vary from the Windows implementation.

Let’s see what happens when you issue a malloc request (assuming you are using glibc) and there is no heap region mapped yet (usually happens when you’ve just started a program). This is the source code of the program I will be showing:

#include<stdlib.h>  
  
int main(void) {  
	malloc(24);
	return 0;  
}

If you just run it, nothing will happen (as expected). We will be taking a look into it using gdb. I will be using pwndbg, but you can use anything of your choice (or maybe not even anything at all and just gdb by itself), but I really recommend pwndbg.

Putting a breakpoint at the main function and running it, issue a vmmap command:

If you take a closer look, there is no heap mappings yet. Let’s use the n command to execute the malloc function and then take another look at the vmmap:

As you can see, there is a heap region now! This is because we just issued the malloc function. Cool, right?

With pwndbg, now use the vis command (this is a shortcut for vis_heap_chunks)

This will show all of the chunks located on the heap. There is a big chunk at the start of it (that we won’t get into much details right now), and there is a chunk just after it (colored purple) which has a 0x0000000000000021 written on it. At the end, there is a 0x0000000000020d51 (which we also won’t get into much details right now).

Why not using something like a mmap?

The biggest problem with this is that it won’t give us a flexible size of memory to work with (as it must be a multiple of 4096, a page size).

Also, it requires kernel involvement. This means that it won’t be a blazingly fast operation.

The heap implementation will more or less do one big memory allocation and then distribute it on smaller heap chunks. This will eliminate the previous problems just mentioned, as we won’t need kernel involvement every time and we will have a possibility of distributing smaller chunks when an allocation is issued.

A heap chunk

Metadata and data

Let’s keep it simple by looking at just the purple chunk. This is the chunk we got when a malloc(24) function got called. There is a 0x21 written on it. This is actually the size of the chunk we just got. This counts the first 8 bytes (which will count as the metadata) and the actual chunk data region. 8 bytes (metadata) + 24 bytes (actual data) = 32 bytes (0x20). But what is this metadata stuff for?

The metadata

At the first 8 bytes, there is a 0x21 written on it. Why is it 0x21 instead of 0x20 then? The chunks must not be misaligned, this is not good for a series of reasons. As so, they will always need to be a multiple of 8 (on 32 bits systems) or 16 (on 64 bits systems). See what is happening now? The last 3 bits will always be zero.

Let’s see it at the level of the bits. Imagine you have some weird number like 397: 0b110001101 Now multiply it by 8: 0b110001101000 Multiplying by 8 simply means adding 3 zeros at the end of a binary number.

As it will always be zero, we will just use them for other purposes like saving flags. There is a 0x21 written on it because the last bit is set for a flag that is called prev_inuse. This flag will have some functionalities we will see later on this series.

Let’s keep poking at the metadata with other stuff. Change the malloc(24) on the code to a malloc(8) and issue another vis command:

The size on the metadata of our chunk didn’t change, even though we changed the requested size on the malloc function. This is because the heap implementation will use “fixed” chunk sizes for optimizations (specially for when we free the chunk). So we won’t get a 16 bits sized chunk. We will be taking a better look at the free function and the free bins on the next post.

Top chunk

Remember that value at the end of the heap chunks that I said we would talk about later on? Well, let’s take a look at it now !

This value is the top chunk size. When we first issue the malloc function, it will ask the kernel for memory for the heap region. As it turns out, it will ask way more memory than what we are requesting, the biggest reason is that it doesn’t want to ask for it again as it is not that fast. This means we can request more chunks with malloc without asking the kernel for more memory.

Let’s look at it. This is the source code I will be debugging:

#include<stdlib.h>  
  
int main(void) {  
	void *a = malloc(0x8);
	void *b = malloc(0x8);
	void *c = malloc(0x8);
	return 0;  
}

Put a breakpoint on the main function and run. I recommend compiling the source code with debug information (you can do that by using the -g flag)

Run the first malloc and issue a vis command:

This is at the bottom of the chunks.

Ok, everything is as usual and we have already seen that.

Now, issue another malloc by using the n command. Use vis to see what happens: As you can see, we got ourselves another chunk. But if you pay close attention, the last value (the top chunk size) is now 0x20d31 instead of 0x20d51. It actually shrink! Instead of having to request more memory to the kernel, we simply use the top chunk at the end of the region to serve the malloc request.

This process would be different if we had an available chunk on one of the free lists, but we still didn’t cover them, so let’s look at only this case for now.

Nice, right? Let’s do another allocation then:

Nothing new around here. Let’s make things a bit more interesting.

Requesting more memory than the top chunk

On the last example, there was a 0x20d11 value at the top chunk. What if we spend all of it?

This is the modified source code:

#include<stdlib.h>  
  
int main(void) {  
	void *a = malloc(0x8);  
	void *b = malloc(0x8);  
	void *c = malloc(0x8);  
	void *d = malloc(0x20ce0);  
	void *e = malloc(0x8);  
	return 0;  
}

I added 2 malloc calls at it. Look at the chunks just after the malloc at the d variable.

The top chunk is now of size 0x20. Making another malloc request:

We can see that the heap grew in size as it got a new top chunk (you can check it by using a vmmap command just after the last allocation and just before it). We will take a better look at the top chunk and how some stuff works around it when we see the House of Force and House of Orange attacks, which will be covered on a future blog post.

Arenas

There is an important concept when we are talking about the heap which is called “arena”. Basically, an arena is a memory region related to each thread and it contains a reference to one or more heaps (each heap can only be at an unique arena). There is this cool image I saw on this amazing blog post.

Before using arenas, the way of blocking more than one thread using the same heap was through the use of a mutex. Nowadays, each arena still uses a mutex, but now threads can make operations on the heap without worrying with each other (as they are interacting with other arenas). When there is no way of creating more arenas, some threads will have to share the same arena and we will be having slower performances using mutexes to block threads accessing the same heap.

References

Azeria Labs
https://ir0nstone.gitbook.io/notes/binexp/heap/
The toddler’s introduction to Heap exploitation (Part 1) | by +Ch0pin🕷️ | InfoSec Write-ups
Introduction To GLIBC Heap Exploitation - Max Kamper
Heap Exploitation - Nightmare
Heap exploitation, glibc internals and nifty tricks. - Quarkslab’s blog