Over the past few months we have discussed a few different defense in depth mitigations (like GS [pt 1, pt2], SEHOP, and DEP [pt 1, pt 2]) which are designed to make it harder for attackers to successfully exploit memory safety vulnerabilities in software. In addition to the mitigations that we’ve discussed so far, a significant amount of effort has gone into hardening the Windows heap manager in order to complicate the exploitation of heap-based memory corruption vulnerabilities. This hardening effort started with changes that were made in Windows XP SP2 and has continued on into Windows 7. In this blog post we will give a brief recap of the relevant changes that have been made to the Windows heap manager. We will also help shed some light on the state of the art in exploitation techniques for heap-based memory corruption vulnerabilities & what relevance those techniques have to Windows Vista, Windows Server 2008, and Windows 7.
Heap mitigation techniques
The hardening changes that have been made to the Windows heap manager generally fall into two categories: metadata protection and non-determinism. Metadata protection changes focus on protecting the integrity of various data structures that are used internally by the heap manager. These changes are useful because the majority of public exploitation techniques have traditionally relied on the corruption of one or more heap data structure. On the other hand, non-determinism changes focus on making the state of the heap unpredictable which has a direct impact on the probability that an exploit will succeed.
Windows XP and Windows Server 2003
The first set of heap hardening changes were released with Windows XP SP2 and Windows Server 2003 SP1. These changes included:
- Safe unlinking: A verification check that occurs during free chunk unlinking which makes sure that the list entry stored in a free chunk is a valid doubly linked list entry (by checking E->F->B == E->B->F == E where E is the free chunk list entry). This prevents exploitation techniques that rely on using the unlink operation performed during the coalescing of free chunks to write an arbitrary value to an arbitrary address in memory. The safe unlinking check was also added to the kernel pool in Windows 7.
- Heap entry header cookie: An 8-bit random value was added to the header of each heap entry which is validated when a heap entry is freed. This makes it possible to detect corruption when a chunk is deallocated.
Windows Vista, Windows Server 2008, and Windows 7
The heap manager in Windows Vista, Windows Server 2008, and Windows 7 expanded on the hardening work that went into Windows XP SP2 and Windows Server 2003 SP1 by incorporating a number of additional security improvements. These improvements are enabled by default (with the exception of termination on heap corruption) and include:
- Removal of commonly targeted data structures: Heap data structures such as lookaside lists and array lists, which have been targeted by multiple exploitation techniques, have been removed. Lookaside lists have been replaced by the Low Fragmentation Heap (LFH).
- Heap entry metadata randomization: The header associated with each heap entry is XORd with a random value in order to protect the integrity of the metadata. The heap manager then unpacks and verifies the integrity of each heap entry prior to operating on it.
- Expanded role of heap header cookie: The 8-bit random value that is associated with the header of each heap entry has had its scope extended to enable integrity checking of more fields. The cookie’s value is also verified in many more places (rather than only checking at the time that a heap entry is freed).
- Randomized heap base address: The base address of a heap region is randomized as part of the overall Address Space Layout Randomization (ASLR) implementation and has 5 bits of entropy. This is designed to make the address of heap data structures and heap allocations unpredictable to an attacker.
- Function pointer encoding: Function pointers (e.g. CommitRoutine) in heap data structures are encoded with a random value to prevent them from being replaced with an untrusted value.
- Termination on heap corruption: If enabled, any detected corruption of a heap data structure will lead to immediate process termination. This is the default for most built-in Windows applications, and can be enabled dynamically by third parties. If disabled, corruption errors are ignored and the application is allowed to continue executing.
- Algorithm variation: The allocation algorithms used by the heap manager may shift depending on allocation patterns and policies. This can make it more difficult to deterministically predict the state of the heap when an attack occurs. This may also result in a runtime switch to code paths that have proven thus far to be more resilient to brute force attacks.
One of the side effects of these changes is that they significantly alter the structure and behavior of the heap. This means that an attacker who is looking to exploit a heap-based vulnerability on Windows XP and Windows Vista will either need to develop a separate exploit for each platform or find a common way to attack the two platforms. These complications increase the level of effort and sophistication required to develop a robust exploit. In addition to the measures that were taken to harden the heap manager itself, Windows Vista, Windows Server 2008, and Windows 7 also include support for DEP and ASLR. These mitigations further complicate the exploitation of any heap related memory corruption vulnerability by making it more difficult for an attacker to execute arbitrary code.
Heap exploitation techniques
Techniques that can be used to exploit heap-based memory corruption vulnerabilities have been a hot topic of research in recent years (see references). Most recently, John McDonald and Christopher Valasek from IBM’S ISS X-Force Research team published a comprehensive paper at Black Hat USA 2009 on the topic of heap-based exploitation techniques that apply to Windows XP and Windows Server 2003. Prior to that, Ben Hawkes presented his work on exploitation techniques that could be used against the Windows Vista heap manager[11,12]. Given the significant amount of research that has occurred in this space, we thought that it would be helpful to provide some insight into the impact and relevance of known heap-based exploitation techniques. In the interest of brevity, we will not go into the details of how these techniques work.
The following table provides a breakdown of the general classes of heap-based exploitation techniques and describes their relevance to Windows Vista, Windows Server 2008, and Windows 7 in terms of their feasibility as currently stated in the literature, perceived degree of difficulty (based on prerequisites), and the specific set of exploit mitigations that are applicable.
|Exploitation technique||Targeting Windows Vista, Windows Server 2008, or Windows 7|
|Feasible||Difficulty||Applicable exploit mitigations|
|Coalesce unlink overwrite[2,3]||No||N/A|
|Critical section unlink overwrite||No||N/A|
|Lookaside list overwrites[4,5,6,14]||No||N/A|
Heap cache attacks
|LFH bucket overwrite||Yes||High|
|HEAP data structure overwrite||Yes||High|
|App-specific data corruption[10,13]||Yes||Variable|
How to read this table (using the HEAP data structure overwrite technique as an example): The HEAP data structure overwrite technique is feasible on Windows Vista, Windows Server 2008, and Windows 7 with a high degree of perceived difficulty (due to the prerequisites required in order to make use of it). Even though this technique may be feasible, DEP and ASLR have the potential to further complicate exploitation.
* If heap metadata randomization material & cookies are secret and terminate on heap corruption is enabled (which is the default for in-box Windows applications and Internet Explorer 7/8).
The majority of the existing heap-based exploitation techniques that rely on the corruption of heap metadata cannot be used in their current form to exploit heap memory corruption vulnerabilities on Windows Vista and above. This is due to the hardening changes that have been made to the heap manager such as removing commonly targeted data structures, protecting the integrity of heap metadata, and making the state of the heap non-deterministic. While new attacks have been proposed, we are not currently aware of any public exploits targeting Windows Vista and above that rely on heap metadata corruption to exploit a real-world heap memory corruption vulnerability. With that said, we expect that heap-based exploitation techniques will continue to be an active research topic. As such, we will continue to investigate heap enhancements (such as those included in RobustHeap) that will make it more difficult for attackers to reliably exploit heap-based memory corruption vulnerabilities.
- Matt Miller, MSEC Security Science
*Postings are provided "AS IS" with no warranties, and confers no rights.*
 Michael Howard. Corrupted Heap Termination Redux. June, 2008.
 Solar Designer. JPEG COM Marker Processing Vulnerability in Netscape Browsers. Bugtraq. Jul, 2000.
 Halvar Flake. Third Generation Exploitation. Black Hat Windows Briefings 2002. Feb, 2002.
 Alexander Anisimov. Defeating Microsoft Windows XP SP2 Heap protection. 2004.
 Matt Conover, Oded Horovitz. Reliable Windows Heap Exploits. CanSecWest. 2004.
 Matt Conover. Windows Heap Exploitation (Win2KSP0 through WinXPSP2). SyScan. 2004.
 David Litchfield. Windows Heap Overflows. Black Hat USA. 2004.
 Nicolas Falliere. A new way to bypass Windows heap protections. Sep, 2005.
 Brett Moore. Exploiting FreeList on Windows XP Service Pack 2. Dec, 2005.
 Nicolas Waisman. Understanding and Bypassing Windows Heap Protection. Jul, 2007.
 Brett Moore. Heaps About Heaps. SyScan 2008. Jul, 2008.
 Ben Hawkes. Attacking the Vista Heap. Black Hat USA. Aug, 2008.
 Ben Hawkes. Attacking the Vista Heap. Ruxcon. Nov, 2008.
 John McDonald and Christopher Valasek. Practical Windows XPSP3/2003 Heap Exploitation. Black Hat USA. Jul, 2009.
Update: Slight clarification made to the exploitation technique table.