A little while back I received a question from a blog reader asking about the difference between heap overflows and use after free vulnerabilities, and I thought it would make a good topic for a blog post, so here goes.
Now, to answer this question I am first going to have to explain something about memory management, so prepare yourself for reams of dry theory...
There are two main types of data structures in a process that are used for memory management, the stack and the heap. The stack is a LIFO (last in first out) structure, that is used mainly for storage of local variables and data related to function calls. It works very much like a stack of plates, in that you can only add or remove entries from the top of the "stack". If you want to remove the second "plate" on the stack, you need to remove the one above it first. The stack is a very simple structure, and has its own registers and instructions in the X86 processor and assembly language which are used to manage access to it.
The heap is a memory storage area used by a process to store global variables, or variables too large to be stored on the stack. The heap does not have dedicated registers or instructions in the X86 processr/assembly language, and instead is managed by higher level functions, generally written in the C programming language and included with an Operating System such as Microsoft Windows, or GNU/Linux.
From an exploitation perspective, these differences between the management methods of the stack and the heap make it much more difficult to follow changes to the heap in an assembly level debugger like OllyDbg when compared to following changes to the stack, and it also makes heap based exploits more difficult to develop than stack based exploits. However, this added level of complexity involved in heap management also provides opportunities for different types of exploitable vulnerabilities to occur. So in addition to buffer overflows, which can occur both on the stack and the heap, the heap is also subject to use after free vulnerabilities.
Considering that the use after free vulnerabilities arises because of the additional complexity introduced by the heap management process, we will need to understand how the heap works and how it is managed to understand use after free and heap overflow vulnerabilities, as well as how they differ. We will use the heap management methodology of the Windows Operating System as an example.
In the Windows Operating System, each process has one or more heaps used to store program data, a default process heap and a variable number of globally accessible dynamic heaps that can be created via the HeapCreate() function. Each of these heaps can have arbitrary sized areas of memory allocated for use by a variety of different calls such as malloc(), HeapAlloc(), LocalAlloc(), GlobalAlloc() or RtlAllocateHeap().
There also must be a way to free heap entries, so that the space in the heap can be reused when no longer needed. Functions such as HeapFree() and HeapReAlloc() are used to free or reallocate entries on the heap.
A method is also need to keep track of the allocated space on the heap. This is done by the use of a number of structures located at the beginning of the heap, as well as headers located before each heap entry, that are used to indicate where entries have been allocated within the heap. Both allocated heap entries and free space within the heap have their own types of headers. The various heap management functions mentioned above make use of these structures when assigning and freeing space on the heap, and in a similar vein, heap based exploits make use of these same heap management functions to take control of the CPU by feeding them corrupted heap data.
Specifically, heap overflows work by overflowing areas of heap memory and overwriting the headers of the next area in memory, which might contain either another used heap entry or a free section of the heap (both of which will have a header as described earlier). Then, when a heap management operation (such as allocating a new entry) is made on the area of the heap following the overwritten block, and the mangled header is accessed by the header management function, an exception will occur which under the right conditions can be exploited. As mentioned before, since exploitation of these vulnerabilities involves manipulation of the heap management functions, its important to be aware that if those functions change (such as when safe unlinking support was added in the heap management functions in Windows XP SP2), exploitation of some heap overflow vulnerabilities can become much more difficult (or perhaps impossible).
Use after free exploits operate slightly differently from heap overflows. They require that a heap entry be created (e.g. using HeapAlloc), freed (HeapFree), and then used again after the free operation has been performed. When these supposedly freed heap entries are "used", this can result in an opportunity to take control of execution of the process.
To see an example of a use after free exploit, you can check out this blog entry. In the example, we allocated memory on the heap and assigned a pointer (Element1), freed that heap entry (by setting the parent SpanID object of Element1 to a null value), overwrote that freed entry (via multiple calls to the FOverwrite function), and then accessed the original heap entry by referencing its pointer (var a = Element1.srcElement). This enabled us to take control of the process and execute arbitrary code.
That's a high level overview of the differences between heap overflows and use after free exploits. To learn more, you can check the list of references below.
The Shellcoders Handbook
http://www.blackhat.com/presentations/win-usa-04/bh-win-04-litchfield/bh-win-04-litchfield.ppt
http://www.cybertech.net/~sh0ksh0k/heap/CSW04%20-%20Reliable%20Windows%20Heap%20Exploits.ppt
http://www.symantec.com/connect/articles/new-way-bypass-windows-heap-protections
http://blogs.technet.com/srd/archive/2009/05/26/safe-unlinking-in-the-kernel-pool.aspx
http://blogs.technet.com/srd/archive/2009/08/04/preventing-the-exploitation-of-user-mode-heap-corruption-vulnerabilities.aspx
http://www.blackhat.com/presentations/bh-usa-09/MCDONALD/BHUSA09-McDonald-WindowsHeap-PAPER.pdf
http://www.blackhat.com/presentations/bh-usa-06/BH-US-06-Marinescu.pdf
http://www.cybertech.net/~sh0ksh0k/heap/XPSP2%20Heap%20Exploitation.ppt
http://cwe.mitre.org/data/definitions/416.html
http://cwe.mitre.org/data/definitions/122.html
31 Mar 2010