Understanding the Low Fragmentation Heap

[Nytro]

Understanding the Low Fragmentation Hea

Blackhat USA 2010

Chris Valasek

X-Force Researcher

cvalasek . gmail.com

@nudehaberdasher

Table of Contents
Introduction................................................................................................................................................ 4
Overview................................................................................................................................................. 4
Prior Works ............................................................................................................................................. 5
Prerequisites ........................................................................................................................................... 6
Terminology............................................................................................................................................ 6
Notes ...................................................................................................................................................... 7
Data Structures ........................................................................................................................................... 7
_HEAP ..................................................................................................................................................... 7
_HEAP_LIST_LOOKUP.............................................................................................................................. 9
_LFH_HEAP ........................................................................................................................................... 10
_LFH_BLOCK_ZONE............................................................................................................................... 11
_HEAP_LOCAL_DATA ............................................................................................................................ 11
_HEAP_LOCAL_SEGMENT_INFO ........................................................................................................... 12
_HEAP_SUBSEGMENT........................................................................................................................... 12
_HEAP_USERDATA_HEADER ................................................................................................................. 13
_INTERLOCK_SEQ.................................................................................................................................. 14
_HEAP_ENTRY....................................................................................................................................... 15
Overview............................................................................................................................................... 16
Architecture.............................................................................................................................................. 17
FreeLists ................................................................................................................................................ 17
Algorithms ................................................................................................................................................ 20
Allocation.............................................................................................................................................. 20
Back-end Allocation .............................................................................................................................. 21
RtlpAllocateHeap .............................................................................................................................. 21
Overview........................................................................................................................................... 27
Front-end Allocation ............................................................................................................................. 28
RtlpLowFragHeapAllocFromContext ................................................................................................. 28
Overview........................................................................................................................................... 363
Example ............................................................................................................................................ 37
Freeing .................................................................................................................................................. 40
Back-end Freeing .............................................................................................................................. 41
RtlpFreeHeap .................................................................................................................................... 41
Overview........................................................................................................................................... 47
Front-end Freeing ................................................................................................................................. 48
RtlpLowFragHeapFree....................................................................................................................... 48
Overview........................................................................................................................................... 51
Example ............................................................................................................................................ 52
Security Mechanisms ................................................................................................................................ 55
Heap Randomization............................................................................................................................. 55
Comments......................................................................................................................................... 56
Header Encoding/Decoding .................................................................................................................. 56
Comments......................................................................................................................................... 57
Death of bitmap flipping ....................................................................................................................... 58
Safe Linking........................................................................................................................................... 59
Comments......................................................................................................................................... 59
Tactics ....................................................................................................................................................... 60
Heap Determinism................................................................................................................................ 60
Activating the LFH ............................................................................................................................. 60
Defragmentation............................................................................................................................... 61
Adjacent Data ................................................................................................................................... 62
Seeding Data ..................................................................................................................................... 63
Exploitation........................................................................................................................................... 67
Ben Hawkes #1.................................................................................................................................. 67
FreeEntryOffset Overwrite................................................................................................................ 71
Observations......................................................................................................................................... 79
SubSegment Overwrite ..................................................................................................................... 79
Example ............................................................................................................................................ 83
Issues ................................................................................................................................................ 83
Conclusion ................................................................................................................................................ 85
Bibliography.............................................................................................................................................. 86

Introduction

Over the years, Windows heap exploitation has continued to increase in difficulty due to the

addition of exploitation counter measures along with the implementation of more complex

algorithms and data structures. Due to these trends and the scarcity of comprehensive heap

knowledge within the community, reliable exploitation has severely declined. Maintaining a

complete understanding of the inner workings of a heap manager can be the difference

between unpredictable failure and precise exploitation.

The Low Fragmentation heap has become the default front-end heap manager for the Windows

operating system since the introduction of Windows Vista. This new front-end manager brought

with it a different set of data structures and algorithms that replaced the Lookaside List. The

system has also changed the way back-end memory management works as well. All of this

material must be reviewed to understand the repercussions of allocating and freeing memory

within an application on Windows 7.

The main goal of this paper is to familiarize the reader with the newly created logic and data

structures associated with the Low Fragmentation heap. First, a clear and concise foundation

will be provided by explaining the new data structures and their coupled purpose within the

heap manager. Then detailed explanations concerning the underlying algorithms that

manipulate those data structures will be discussed. Finally, some newly devised exploitation

techniques will be unveiled providing practical applications from this new found knowledge.

Download:

http://illmatics.com/Understanding_the_LFH.pdf