Hacking

Heap overflow: Vulnerability and heap internals explained

ViperEye
June 26, 2013 by
ViperEye

A heap overflow is a form of buffer overflow; it happens when a chunk of memory is allocated to the heap and data is written to this memory without any bound checking being done on the data. This is can lead to overwriting some critical data structures in the heap such as the heap headers, or any heap-based data such as dynamic object pointers, which in turn can lead to overwriting the virtual function table. Here we'll see some details about the inner working of the Windows heap, then move on to discuss how heap overflow vulnerability occurs.

What should you learn next?

What should you learn next?

From SOC Analyst to Secure Coder to Security Manager — our team of experts has 12 free training plans to help you hit your goals. Get your free copy now.

The paper will start with basic information on how Windows heap management is done and then move to understanding the vulnerability.

 Windows heap basics

Windows has two kinds of heap:

  1. Default heap
  2. Dynamic heap

The default heap is used by the win32 subsystem to manage and allocate memory for local and global variables and local memory management functions [malloc()].

The dynamic heap is created by functions such as HeapCreate() that return a handle/address to a memory chunk that contains the heap header; the information in this header includes the segment table, virtual allocation list, free list usage bitmap, free list table, lookaside table, etc. This data is used by heap allocation functions such as HeapAlloc(), HeapReAlloc(), which allocates memory from this particular heap.

Heap-Overflow-Fig1

As we can see from the above image, PEB stores the details of the heaps initialized in the system. This can be useful in enumerating heaps in the system.

The above image shows the structure of the heap header.

Next we will take a look at some of the important data structures in the heap that will help us understand the heap exploit better.

..

Segment List

..

..

Virtual Allocation List

..

..

Free List

..

..

Pointer to Lookaside List

..

..

The condition where the heap is not used is when the allocation chunk is greater than 512KB (4096 bytes); in this case, the allocation is done in virtual memory by VirtualAlloc().

Let's see how this happens:

The above image shows how the heap allocation is done; certain constraints are verified before passing it forward. As we can see, all the calculation is done based on dividing by 8, the size of the allocated block is always divisible by 8, and we can also conclude from the code that there cannot exist a block of size 8 bytes because the header itself will amount to 16 bytes.

Here's the decision path during the heap allocation process:

  1. If block size is greater than 1024 bytes, go to step2.
  2. If it is less than 1024 bytes, check the lookaside list if there are no free entries check free list.
  3. If the above condition is true, then check whether the memory to be allocated is greater than 0xFE00 (512 KB).
  4. If the above condition is not true, then the memory is allocated from the free list.
  5. If the above condition is true, then check whether the heap was created with a fixed size; if true, and then throw an error (STATUS_BUFFER_TOO_SMALL) 0xC0000023.
  6. If not true, use ntdll.ZwAllocateVirtualMemory to allocate new memory.

Now's let's look at how heap memory is freed; memory is freed based on whether it is in the default heap or the dynamically allocated heap.

If the buffer is in default heap then:

  1. Try to free lookaside list.
  2. Or coalesce buffer and place it on free list.

If it is virtually allocated:

  1. Remove from busy list
  2. Or free it to OS.

Free buffer to lookaside happens only if:

  • There is a lookaside table
  • Lookaside is not locked
  • Requested size is smaller than 1024 (to fit the table)
  • Lookaside is not "full" yet.

If buffer can be placed on lookaside, keep the buffer flags set to busy and return to caller.

The other option is to coalesce and place in free buffer. This happens only if the buffer can't be freed to lookaside.

The conditions where coalesce fails:

  • Freed buffer flags & 0x80 is true
  • Freed buffer is first → no backward coalesce
  • Freed buffer is last → no forward coalesce
  • Adjacent buffer is busy
  • The total size of two adjacent buffers is bigger than the virtual allocate threshold (0xFE00 * 8 bytes == ~64k)

Insert to free list if:

  • Coalesced block size < 1024 insert to proper free list entry.
  • Coalesced block size > De-commit threshold and total heap free size is over De-commit total free threshold, then De-commit buffer back to the OS.
  • Coalesced is smaller than virtual allocate threshold, insert the block into free list [0].
  • Coalesced block is bigger than virtual allocate threshold, break the buffer into smaller chunks, each one as big as possible, and place them on free list [0].
Heap Overflows

Let`s take a look at this rather simple example of a vulnerable function:

[c]

HANDLE h = HeapCreate(0, 0, 0); // default flags

DWORD vulner(LPVOID str)

{

LPVOID mem = HeapAlloc(h, 0, 128);

//

strcpy(mem, str);

//

return 0;

}

[/c]

As we can see, here the vulner() function copies data from a string pointed by str to an allocated memory block pointed at by buf, without a bound check. A string larger than 127 bytes passed to it will thereby overwrite the data coincidental to this memory block (which is, actually, a header of the following memory block).

The lookaside list has two pointers pointing to the lookaside entries before and after it, called the FLINK and BLINK pointers. The layout for a single lookaside entry is given below:

So, when an overflow occurs, we can overwrite the FLINK and BLINK pointers.

Now let's modify the above code:

[c]

DWORD vulner(LPVOID str)

{

HANDLE h = HeapCreate(0, 0, 0);

LPVOID m1 = HeapAlloc(h, 0 , 64);

LPVOID m2 = HeapAlloc(h, 0,128);

HeapFree(m1);

HeapFree(m2);

// The above steps place the buffers in lookaside list

LPVOID m1 = HeapAlloc(h, 0 , 64);

// This sets up the memory for overwrite into adjacent memory blocks

memcpy((char *)m, 0x31, 64+16);

m2 = HeapAlloc(h, 0, 128-8);

//

strcpy(mem, str);

//

return 0;

}

[/c]

From the above code we can see that we have allocated two memory chunks and then freed them to the lookaside list; as mentioned above, any memory below 1024-8 bytes will be sent to the lookaside list.

After that, an allocation of 64 bytes is done again. This will move the memory back to the busy list. But, in this case, the memory of 128 bytes will still be right next to the 64-byte chunk, so if we overflow the 64-byte chunk the data will write into 128-byte chunk.

In the next line we are overwriting with 64+16 bytes of data which will overwrite the header and the FLINK, BLINK pointers of the 128 byte block. This is shown in the image below:

[caption id="" align="alignnone" width="630"]Click to Enlarge Click to Enlarge[/caption]

Heap-Overflow-Fig2

The whole process of unlinking is shown below:

Entry2BLINK→FLINK = Entry2→FLINK

Entry2→FLINK→BLINK = Entry2→BLINK

So now, when the 128-byte buffer is allocated, it has already corrupted FLINK and BLINK pointers. This can be in an attacker's control.

So the entry "Entry2→BLINK→FLINK" will be in an attacker-controlled memory location; this can be overwritten with the value of Entry2→FLINK, which is also attacker-controlled.

Become a Certified Ethical Hacker, guaranteed!

Become a Certified Ethical Hacker, guaranteed!

Get training from anywhere to earn your Certified Ethical Hacker (CEH) Certification — backed with an Exam Pass Guarantee.

Conclusion

This paper simply gives an understanding of the heap overflow process. The next article will give the details about how this vulnerability can be exploited.

ViperEye
ViperEye

ViperEye works for a leading IT company and is deeply passionate about Information Security and Reverse Engineering. ViperEye research interests include Malware Analysis, specifically directed towards executable protections techniques. His other interests include product security, in particular: web applications, stand alone clients, etc.