WINDOWS 10 SEGMENT HEAP INTERNALSMark Vincent Yason
IBM X-Force Advanced Research
yasonm[at]ph[dot]ibm[dot]com@MarkYason

ABSTRACTIntroduced in Windows 10, Segment Heap is the native heap implementation used in Windows apps (formerly
called Modern/Metro apps) and certain system processes. This new heap implementation is an addition to thewell-researched and widely documented NT Heap that is still used in traditional applications and in certain types ofallocations in Windows apps.
One important aspect of the Segment Heap is that it is enabled for Microsoft Edge which means thatcomponents/dependencies running in Edge that do not use a custom heap manager will use the Segment Heap.
Therefore, reliably exploiting memory corruption vulnerabilities in these Edge components/dependencies would
require some level of understanding of the Segment Heap.
In this presentation, I’ll discuss the data structures, algorithms and security mechanisms of the Segment Heap.
Knowledge of the Segment Heap is also applied by discussing and demonstrating how a memory corruption
vulnerability in the Microsoft WinRT PDF library (CVE-2016-0117) is leveraged for a reliable arbitrary write in thecontext of the Edge content process.

© 2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > INTRODUCTION

2

CONTENTS
1.

Introduction ...........................................................................................................................................................52.

Internals .................................................................................................................................................................6
2.1.

Overview ......................................................................................................................................................6

Architecture ...........................................................................................................................................................6
Defaults and Configuration ....................................................................................................................................6
Heap Creation ........................................................................................................................................................7
HeapBase and _SEGMENT_HEAP Structure ..........................................................................................................8
Block Allocation .....................................................................................................................................................9
Block Freeing .......................................................................................................................................................10
2.2.

Backend Allocation .....................................................................................................................................12

Segment Structure ...............................................................................................................................................12_HEAP_PAGE_SEGMENT Structure .....................................................................................................................13_HEAP_PAGE_RANGE_DESCRIPTOR Structure ....................................................................................................13
Backend Free Tree ...............................................................................................................................................15
Backend Allocation ..............................................................................................................................................15
Backend Freeing ..................................................................................................................................................17
2.3.

Variable Size Allocation ..............................................................................................................................18

VS Subsegments...................................................................................................................................................18_HEAP_VS_CONTEXT Structure ...........................................................................................................................18_HEAP_VS_SUBSEGMENT Structure ....................................................................................................................18_HEAP_VS_CHUNK_HEADER Structure ...............................................................................................................19_HEAP_VS_CHUNK_FREE_HEADER Structure .....................................................................................................20
VS Free Tree .........................................................................................................................................................21
VS Allocation ........................................................................................................................................................21
VS Freeing ............................................................................................................................................................23
2.4.

Low Fragmentation Heap ...........................................................................................................................24

LFH Subsegments .................................................................................................................................................25_HEAP_LFH_CONTEXT Structure .........................................................................................................................25_HEAP_LFH_ONDEMAND_POINTER Structure ....................................................................................................25_HEAP_LFH_BUCKET Structure ............................................................................................................................26_HEAP_LFH_AFFINITY_SLOT Structure ................................................................................................................26_HEAP_LFH_SUBSEGMENT_OWNER Structure ...................................................................................................27

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > INTRODUCTION

3_HEAP_LFH_SUBSEGMENT Structure .................................................................................................................27
LFH Block Bitmap .................................................................................................................................................29
LFH Bucket Activation ..........................................................................................................................................30
LFH Allocation ......................................................................................................................................................30
LFH Freeing ..........................................................................................................................................................32
2.5.

Large Blocks Allocation ..............................................................................................................................32_HEAP_LARGE_ALLOC_DATA Structure ..............................................................................................................33
Large Block Allocation..........................................................................................................................................33
Large Block Freeing ..............................................................................................................................................34

3.

4.

2.6.

Block Padding .............................................................................................................................................34

2.7.

Summary and Analysis: Internals ...............................................................................................................35

Security Mechanisms ...........................................................................................................................................36
3.1.

Fast Fail on Linked List Node Corruption....................................................................................................36

3.2.

Fast Fail on RB Tree Node Corruption ........................................................................................................36

3.3.

Heap Address Randomization ....................................................................................................................37

3.4.

Guard Pages ...............................................................................................................................................38

3.5.

Function Pointer Encoding .........................................................................................................................39

3.6.

VS Block Header Encoding..........................................................................................................................39

3.7.

LFH Subsegment BlockOffsets Encoding ....................................................................................................40

3.8.

LFH Allocation Randomization ...................................................................................................................40

3.9.

Summary and Analysis: Security Mechanisms ...........................................................................................41

Case Study ...........................................................................................................................................................42
4.1.

CVE-2016-0117 Vulnerability Details .........................................................................................................42

4.2.

Plan for Implanting the Target Address .....................................................................................................43

4.3.

Manipulating the MSVCRT Heap with Chakra’s ArrayBuffer .....................................................................44

Allocation and Setting Controlled Values ............................................................................................................44
LFH Bucket Activation ..........................................................................................................................................44
Freeing and Garbage Collection ..........................................................................................................................45
4.4.

Preventing Target Address Corruption ......................................................................................................45

4.5.

Preventing Free Blocks Coalescing .............................................................................................................46

4.6.

Preventing Unintended Use of Free Blocks ................................................................................................47

4.7.

Adjusted Plan for Implanting the Target Address ......................................................................................47

4.8.

Successful Arbitrary Write..........................................................................................................................48

4.9.

Analysis and Summary: Case Study ............................................................................................................48
IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > INTRODUCTION

45.

Conclusion ...........................................................................................................................................................50

6.

Appendix: WinDbg !heap Extension Commands for Segment Heap ...................................................................51!heap -x <address> ..............................................................................................................................................51!heap -i <address> -h <heap> ..............................................................................................................................51!heap -s -a -h <heap> ...........................................................................................................................................51

7.

Bibliography .........................................................................................................................................................53

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > INTRODUCTION

5

1. INTRODUCTION
With the introduction of Windows 10, Segment Heap, a new native heap implementation was also introduced. It iscurrently the native heap implementation used in Windows apps (formerly called Modern/Metro apps) and incertain system processes, while the older native heap implementation (NT Heap) is still the default for traditional
applications.
From a security researcher’s perspective, understanding the internals of the Segment Heap is important as
attackers may leverage or exploit this new and critical component in the near future, especially because it is being
used by the Edge browser. Additionally, a security researcher performing software audits may need to develop a
proof-of-concept for a vulnerability in order to prove exploitability to the vendor/developer. If creating the proofof-concept requires precise manipulation of a heap managed by the Segment Heap, an understanding of its
internals will definitely help. This paper aims to help the reader have a deep understanding of the Segment Heap.
This paper is divided into three major sections. The first section (Internals) discusses in depth the different
components of the Segment Heap. It includes the data structures and algorithms used by each Segment Heap
component when performing their functions. The second section (Security Mechanisms) discusses the different
mechanisms that make it difficult or unreliable to attack important Segment Heap metadata, and in certain cases,
make it difficult to conduct precise heap layout manipulation. The third section (Case Study) is where theunderstanding of the Segment Heap is applied by discussing methods for manipulating the layout of a heap
managed by the Segment Heap in order to leverage a vulnerability for a reliable arbitrary write.
Since the Segment Heap and NT Heap share similar concepts, the reader is encouraged to read prior works that
discuss NT Heap internals [1, 2, 3, 4, 5]. These prior works and the various papers/presentations they reference
also discuss the security mechanisms and attack techniques for the NT Heap which will give the reader an idea why
certain heap security mechanisms are in place in the Segment Heap.
All information in this paper is based on NTDLL.DLL (64-bit) version 10.0.14295.1000 from the Windows 10
Redstone 1 Preview (Build 14295).

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

6

2. INTERNALSThis section discusses in depth the internals of the Segment Heap. The discussion will start with an overview of thedifferent components of the Segment Heap and then describing the instances when the Segment Heap will beenabled. After the overview, each Segment Heap component will be discussed in details in their own subsections.
Note that internal NTDLL functions discussed here may be inlined in some NTDLL builds. Therefore, the internalfunctions may not be seen in IDA’s functions listing and a copy of the functions may be seen embedded in otherfunctions.

2.1. OVERVIEW
Architecture
The Segment Heap is consists of four components: (1) The backend which services allocation requests for >128KB
to 508KB. It uses the virtual memory functions provided by the NT Memory Manager to create and manage thesegments where backend blocks are allocated from. (2) The variable size (VS) allocation component which services
allocation requests for <=128KB. It uses the backend to create the VS subsegments where VS blocks are allocatedfrom. (3) The Low Fragmentation Heap (LFH) services allocation requests for <=16,368 bytes but only if theallocation size is detected to be commonly used in allocations. It uses the backend to create the LFH subsegments
where LFH blocks are allocated from. (4) The large blocks allocation component services allocation requests for>508KB. It uses the virtual memory functions provided by the NT Memory Manager for the allocation and freeingof large blocks.

Defaults and Configuration
The Segment Heap is currently an opt-in feature. Windows apps are opted-in by default and executables with aname that matches any of the following (names of system executables) are also opted-in by default to use theSegment Heap:
csrss.exe

IBM Security | ©2016 IBM Corporation

7

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS






lsass.exe
runtimebroker.exe
services.exe
smss.exesvchost.exe

To enable or disable the Segment Heap for a specific executable, the following Image File Execution Options (IFEO)
registry entry can be set:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\
Image File Execution Options\(executable)
FrontEndHeapDebugOptions = (DWORD)
Bit 2 (0x04): Disable Segment Heap
Bit 3 (0x08): Enable Segment Heap

To globally enable or disable the Segment Heap for all executables, the following registry entry can be set:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Session Manager\Segment Heap
Enabled = (DWORD)
0: Disable Segment Heap
(Not 0): Enable Segment Heap

If after all the checks it is determined that a process will use the Segment Heap, bit 0 of the global variable
RtlpHpHeapFeatures will be set.
Note that even if Segment Heap is enabled in a process, not all heaps created by the process will be managed by
the Segment Heap as there are specific types of heaps that still need to be managed by the NT Heap (this will be
discussed in the next subsection).

Heap Creation
If the Segment Heap is enabled (bit 0 of RtlpHpHeapFeatures is set), the heap created by HeapCreate() will be
managed by the Segment Heap unless the dwMaximumSize argument passed to it is not zero (means the heap is
not growable).
If the RtlCreateHeap() API is directly used to create the heap, all of the following should be true for the Segment
Heap to manage the created heap:Heap should be growable: Flags argument passed to RtlCreateHeap() should have HEAP_GROWABLE set.
Heap memory should not be pre-allocated (suggests a shared heap): HeapBase argument passed to
RtlCreateHeap() should be NULL.
If a Parameters argument is passed to RtlCreateHeap(), the following Parameters fields should be set
to 0/NULL: SegmentReserve, SegmentCommit, VirtualMemoryThreshold and CommitRoutine.
The Lock argument passed to RtlCreateHeap() should be NULL.

The illustration below shows the heaps created when the Edge content process (a Windows app) is initially loaded.

IBM Security | ©2016 IBM Corporation

8

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

Four of five are managed by the Segment Heap. The first heap is the default process heap, and the third heap isthe MSVCRT heap (msvcrt!crtheap). The second heap is a shared heap (ntdll!CsrPortHeap), and therefore, it ismanaged by the NT Heap.

HeapBase and _SEGMENT_HEAP Structure
When a heap managed by the Segment Heap is created, the heap address/handle (called HeapBase for the rest of
this paper) returned by HeapCreate() or RtlCreateHeap() will point to a _SEGMENT_HEAP structure, thecounterpart of the _HEAP structure of the NT Heap.
The HeapBase is the central location where the states of the different Segment Heap components are stored. It
has the following fields:
windbg> dt ntdll!_SEGMENT_HEAP+0x000 TotalReservedPages : Uint8B+0x008 TotalCommittedPages : Uint8B+0x010 Signature: Uint4B+0x014 GlobalFlags: Uint4B+0x018 FreeCommittedPages : Uint8B+0x020 Interceptor: Uint4B+0x024 ProcessHeapListIndex : Uint2B+0x026 GlobalLockCount : Uint2B+0x028 GlobalLockOwner : Uint4B+0x030 LargeMetadataLock : _RTL_SRWLOCK+0x038 LargeAllocMetadata : _RTL_RB_TREE+0x048 LargeReservedPages : Uint8B+0x050 LargeCommittedPages : Uint8B+0x058 SegmentAllocatorLock : _RTL_SRWLOCK+0x060 SegmentListHead : _LIST_ENTRY+0x070 SegmentCount: Uint8B+0x078 FreePageRanges: _RTL_RB_TREE+0x088 StackTraceInitVar : _RTL_RUN_ONCE+0x090 ContextExtendLock : _RTL_SRWLOCK+0x098 AllocatedBase: Ptr64 UChar+0x0a0 UncommittedBase : Ptr64 UChar+0x0a8 ReservedLimit: Ptr64 UChar+0x0b0 VsContext: _HEAP_VS_CONTEXT+0x120 LfhContext: _HEAP_LFH_CONTEXT

Signature - 0xDDEEDDEE (heap is managed by the Segment Heap).

Fields for tracking large blocks allocation state (further discussed in 2.5):

LargeAllocMetadata - Red-black tree (RB tree) [6] of large blocks metadata.
LargeReservedPages - Number of pages that are reserved for all large blocks allocation.

IBM Security | ©2016 IBM Corporation

9

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

LargeCommittedPages - Number of pages that are committed for all large blocks allocation.

Fields for tracking backend allocation state (further discussed in 2.2):

SegmentCount - Number of segments owned by the heap.
SegmentListHead - Linked list of segments owned by the heap.
FreePageRanges - RB tree of free backend blocks.

The following substructures track the variable size allocation and the Low Fragmentation Heap states:

VsContext - Tracks the state of the variable size allocation (see 2.3).
LfhContext - Tracks the state of the Low Fragmentation Heap (see 2.4).

The heap is allocated and initialized via a call to RtlpHpSegHeapCreate(). NtAllocateVirtualMemory() is used toreserve and commit the virtual memory for the heap. The reserve size varies depending on the number ofprocessors and the commit size is the size of the _SEGMENT_HEAP structure.
The remaining reserved memory below the _SEGMENT_HEAP structure is called the LFH context extension and it is
dynamically committed to store the necessary data structures for activated LFH buckets.

Block Allocation
When allocating a block via HeapAlloc() or RtlAllocateHeap(), the allocation request will eventually be routed
to RtlpHpAllocateHeap() if the heap is managed by the Segment Heap.
RtlpHpAllocateHeap() has the following function signature:
PVOID RtlpHpAllocateHeap(_SEGMENT_HEAP* HeapBase, SIZE_T UserSize, ULONG Flags, USHORT Unknown)

Where UserSize (user-requested size) is the size passed to HeapAlloc() or RtlAllocateHeap(). The return value
is the pointer to the newly allocated block (called UserAddress for the rest of this paper).
The diagram below shows the logic of RtlpHpAllocateHeap():

IBM Security | ©2016 IBM Corporation

10

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

The purpose of RtlpHpAllocateHeap() is to call the allocation function of the appropriate Segment Heap
component based on AllocSize. AllocSize (allocation size) is the adjusted UserSize depending on Flags, but by
default, AllocSize will be equal to UserSize unless UserSize is 0 (if UserSize is 0, AllocSize will be 1).
Note that the logic starting where AllocSize is checked is actually in a separate RtlpHpAllocateHeapInternal()function, it is just inlined in the diagram for brevity. Also, one part to notice is that if LFH allocation returns -1, itmeans that the LFH bucket corresponding to AllocSize is not yet activated, and therefore, the allocation request
will eventually be passed to the VS allocation component.

Block Freeing
When freeing a block via HeapFree() or RtlFreeHeap(), the call will eventually be routed to RtlpHpFreeHeap() if
the heap is managed by the Segment Heap.
RtlpHpFreeHeap() has the following function signature:
BOOLEAN RtlpHpFreeHeap(_SEGMENT_HEAP* HeapBase, PVOID UserAddress, ULONG Flags,
SIZE_T* UserSize, USHORT* Unknown)

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

11

Where UserAddress is the block address returned by HeapAlloc() or RtlAllocateHeap() and the UserSize will
become the user-requested size of the freed block.
The diagram below shows the freeing logic of RtlpHpFreeHeap():

The purpose of RtlpHpFreeHeap() is to call the freeing function of the appropriate Segment Heap component
based on the value of UserAddress and what type of subsegment it is located. Subsegments will be further
discussed later in this paper, but for now, subsegments are special types of backend blocks where VS and LFH
blocks are allocated from.
Since the address of large allocations are 64KB aligned, a UserAddress with low 16 bits cleared is first checkedagainst the large allocation bitmap. If the UserAddress (actually, UserAddress >> 16) is set in the large allocation
bitmap, large block freeing is called.

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

12

Next, the subsegment where UserAddress is located is determined. If UserAddress is less than or equal the
resulting subsegment address, it means that the UserAddress is for a backend block, because the address of VS
blocks and LFH blocks are above the subsegment address due to VS/LFH subsegment headers being located before
the VS/LFH blocks. If UserAddress points to a backend block, backend freeing is called.
Finally, if the subsegment is an LFH subsegment, LFH freeing is called. Otherwise, VS freeing is called. If VS freeing
is called, and if the returned LfhBlockSize (equivalent to the block size of the freed VS block minus 0x10) is
serviceable by the LFH, the usage counter of the LFH bucket corresponding to LfhBlockSize is updated.
Note that the logic starting where the subsegment of UserAddress is derived is actually in a separate
RtlpHpSegFree() function, it was inlined in the diagram for brevity. Also, the diagram only shows the freeing logic
of RtlpHpFreeHeap(), its other functionalities were not included.

2.2. BACKEND ALLOCATIONThe backend is used for allocations with sizes 131,073 (0x20001) to 520,192 (0x7F000) bytes. Backend blocks havea page size granularity and each does not have a block header at the beginning. In addition to allocating backend
blocks, the backend is also used by the VS and LFH component for the creation of VS/LFH subsegments (special
types of backend blocks) where VS/LFH blocks are allocated from.

Segment Structure
The backend operates on segment structures which are 1MB (0x100000) blocks of virtual memory allocated via
NtAllocateVirtualMemory(). The segments are tracked via the SegmentListHead field in the HeapBase:

The first 0x2000 bytes of a segment is used for the segment header, while the rest is used for the allocation of
backend blocks. Initially, the first 0x2000 plus an initial commit size of the segment is committed, while the rest arein the reserve state and are committed and decommitted as needed.
The segment header is consists of an array of 256 page range descriptors that describe the status of each page inthe segment. Since the data portion of the segment starts at offset 0x2000, the first page range descriptor isrepurposed to store the _HEAP_PAGE_SEGMENT structure, while the second page range descriptor is unused.

IBM Security | ©2016 IBM Corporation

13

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS_HEAP_PAGE_SEGMENT Structure
As mentioned, the first page range descriptor is repurposed to store the _HEAP_PAGE_SEGMENT structure. It has
the following fields:
windbg> dt ntdll!_HEAP_PAGE_SEGMENT+0x000 ListEntry: _LIST_ENTRY+0x010 Signature: Uint8B



ListEntry - Each segment is a node of the heap’s segments linked list ( HeapBase.SegmentListHead).
Signature - Used for verifying if an address is part of a segment. This field is computed via:
(SegmentAddress >> 0x14) ^ RtlpHeapKey ^ HeapBase ^ 0xA2E64EADA2E64EAD.

_HEAP_PAGE_RANGE_DESCRIPTOR Structure
Also mentioned are page range descriptors that describe the status of each page of the segment. Since a backend
block can span multiple pages (a page range), the page range descriptor for the first page of the backend block ismarked as “first”, and therefore, will have additional fields set.
windbg> dt ntdll!_HEAP_PAGE_RANGE_DESCRIPTOR -r+0x000 TreeNode: _RTL_BALANCED_NODE+0x000 TreeSignature: Uint4B+0x004 ExtraPresent: Pos 0, 1 Bit+0x004 Spare0: Pos 1, 15 Bits
+0x006 UnusedBytes: Uint2B+0x018 RangeFlags: UChar+0x019 Spare1: UChar+0x01a Key: _HEAP_DESCRIPTOR_KEY+0x000 Key: Uint2B+0x000 EncodedCommitCount : UChar+0x001 PageCount: UChar+0x01a Align: UChar+0x01b Offset: UChar+0x01b Size
: UChar

TreeNode - “First” page range descriptors of free backend blocks are nodes of the backend free tree

(HeapBase.FreePageRanges).
UnusedBytes - For “first” page range descriptors. The difference between UserSize and the block size.
RangeFlags – Bit field representing the type of the backend block and the state of the page represented
by the page range descriptor.
 0x01: PAGE_RANGE_FLAGS_LFH_SUBSEGMENT. For “first” page range descriptors. Backend block is
an LFH subsegment.
 0x02: PAGE_RANGE_FLAGS_COMMITED. Page is committed.
 0x04: PAGE_RANGE_FLAGS_ALLOCATED. Page is allocated/busy.
 0x08: PAGE_RANGE_FLAGS_FIRST. Page range descriptor is marked as “first”.
 0x20: PAGE_RANGE_FLAGS_VS_SUBSEGMENT. For “first” page range descriptors. Backend block is a
VS subsegment.
Key - For “first” page range descriptors of free backend blocks. This is used when a free backend block isinserted to the backend free tree.
 Key - WORD-sized key used for the backend free tree, high BYTE is the PageCount field and the
low BYTE is the EncodedCommitCount field (see below).
 EncodedCommitCount - Bitwise NOT of the number of committed pages of the backend block.
The larger number of committed pages the free backend block has, the lower
EncodedCommitCount will be.
IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS




14

 PageCount - Number pages of the backend block.
Offset - For non-“first” page range descriptors. Offset of the page range descriptor from the “first” page
range descriptor.
Size - For “first” page range descriptors. Same value as Key.PageCount (overlapping fields).

Below is an illustration of a segment:

And below is an illustration of a 131,328 bytes (0x20100) busy backend block and the corresponding page range
descriptors (the “first” page range descriptor is highlighted):

Note that because the page range descriptors that describe the backend blocks are stored at the top of thesegment, it means that each backend block does not have a block header at the beginning.

IBM Security | ©2016 IBM Corporation

15

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

Backend Free Tree
Backend allocation and freeing use the backend free tree for finding and storing information on free backend
blocks.
The root of the backend free tree is stored in HeapBase.FreePageRanges and the tree nodes are the “first” page
range descriptors of free backend blocks. The key used for inserting nodes in the backend free tree is the “first”
page range descriptor’s Key.Key field (see details of Key.Key in the previous subsection).
Below is an illustration of a backend free tree in which there are three free backend blocks with sizes 0x21000,
0x23000 and 0x4F000 (all pages of the free blocks are decommitted - Key.EncodedCommitCount is 0xFF):

Backend Allocation
Backend allocation is performed via RtlpHpSegAlloc() which has the following function signature:
PVOID RtlpHpSegAlloc(_SEGMENT_HEAP* HeapBase, SIZE_T UserSize, SIZE_T AllocSize, ULONG Flags)

calls RtlpHpSegPageRangeAllocate() to allocate a backend block.
RtlpHpSegPageRangeAllocate(), on the other hand, accepts the number of pages to allocate and returns the“first” page range descriptor of the allocated backend block. Then, RtlpHpSegAlloc() converts the returned“first” page range descriptor to the actual backend block address (UserAddress) which it will then use as thereturn value.
RtlpHpSegAlloc()

first

The diagram below shows the logic of RtlpHpSegPageRangeAllocate():IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

16

RtlpHpSegPageRangeAllocate() first traverses the backend free tree to find a free backend block that can fit theallocation. The search key used for finding a free backend block is a WORD-sized value in which the high BYTE is
the requested number of pages and the low BYTE is the bitwise NOT of the number of requested pages. Thismeans that a best-fit search is conducted with the most committed block given preference, in other words, if two
or more free blocks with equivalent size will best fit the allocation, the most committed free block will be selected
for the allocation. If any of the free backend blocks cannot fit the allocation, a new segment is created.
Since the selected free backend block can have more pages than the requested number of pages, the free block is
first split if necessary via RtlpHpSegPageRangeSplit() and the “first” page range descriptor of the resulting
remaining free block is inserted to the backend free tree.

IBM Security | ©2016 IBM Corporation

17

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

Finally, the RangeFlags field of the block’s page range descriptors are updated (PAGE_RANGE_FLAGS_ALLOCATED bit
is set) to mark the block’s pages as allocated.

Backend Freeing
Backend freeing is performed via RtlpHpSegPageRangeShrink() which has the following function signature:
BOOLEAN RtlpHpSegPageRangeShrink(_SEGMENT_HEAP* HeapBase,_HEAP_PAGE_RANGE_DESCRIPTOR* FirstPageRangeDescriptor,
ULONG NewPageCount, ULONG Flags)

Where FirstPageRangeDescriptor is the “first” page range descriptor of the to-be-freed backend block and
NewPageCount is 0 which means to free the block.
RtlpHpSegPageRangeShrink() first clears the PAGE_RANGE_FLAGS_ALLOCATED bit in the RangeFlags field of all(except the “first”) page range descriptors that describe the to-be-freed backend block. It then calls
RtlpHpSegPageRangeCoalesce() which coalesces the to-be-freed backend block with neighboring (before andafter) free backend blocks and clears the PAGE_RANGE_FLAGS_ALLOCATED bit in the RangeFlags field of the “first”
page range descriptor of the to-be-freed block.

The “first” page range descriptor of the resulting coalesced block is then inserted to the backend free tree making
the coalesced free block available for allocations.

IBM Security | ©2016 IBM Corporation

18

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

2.3. VARIABLE SIZE ALLOCATION
Variable size (VS) allocation is used for allocations with sizes 1 to 131,072 (0x20000) bytes. VS blocks have a 16
bytes granularity and each has a block header at the beginning.

VS Subsegments
The VS allocation component relies on the backend for creating the VS subsegments where VS blocks are allocatedfrom. A VS subsegment is a special type of a backend block in which the RangeFlags of the “first” page range
descriptor has the PAGE_RANGE_FLAGS_VS_SUBSEGMENT (0x20) bit set.
Below is an illustration of the relationship of the HeapBase, a segment and a VS subsegment:_HEAP_VS_CONTEXT Structure
The VS context structure tracks the free VS blocks, VS subsegments, and other information related to the VS
allocation state. It is stored in the VsContext field in the HeapBase and has the following fields:
windbg> dt ntdll!_HEAP_VS_CONTEXT+0x000 Lock
: _RTL_SRWLOCK+0x008 FreeChunkTree: _RTL_RB_TREE+0x018 SubsegmentList: _LIST_ENTRY+0x028 TotalCommittedUnits : Uint8B+0x030 FreeCommittedUnits : Uint8B+0x038 BackendCtx: Ptr64 Void
+0x040 Callbacks: _HEAP_SUBALLOCATOR_CALLBACKS






FreeChunkTree - RB tree of free VS blocks.
SubsegmentList - Linked list of all VS subsegments.
BackendCtx - Pointer to the _SEGMENT_HEAP structure (HeapBase).
Callbacks - Encoded (see 3.5) callbacks used for the management of VS subsegments.

_HEAP_VS_SUBSEGMENT Structure
VS subsegments are where VS blocks are allocated from. VS subsegments are allocated and initialized via
RtlpHpVsSubsegmentCreate() and will have the following _HEAP_VS_SUBSEGMENT structure as the header:
windbg> dt ntdll!_HEAP_VS_SUBSEGMENT+0x000 ListEntry: _LIST_ENTRY+0x010 CommitBitmap: Uint8B+0x018 CommitLock: _RTL_SRWLOCK+0x020 Size
: Uint2B+0x022 Signature: Uint2B

IBM Security | ©2016 IBM Corporation

19

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALSsubsegment is a node of the VS subsegments linked(VsContext.SubsegmentList).
CommitBitmap - Commit bitmap of the VS subsegment pages.
Size - Size of the VS subsegment (minus 0x30 for the VS subsegment header) in 16-byte blocks.
Signature - Used for checking if the VS subsegment is corrupted. Computed via: Size ^ 0xABED.
Listentry

-

Each

VS

list

Below is an illustration of a VS subsegment. The _HEAP_VS_SUBSEGMENT structure is at offset 0x00, while the VS
blocks start at offset 0x30:_HEAP_VS_CHUNK_HEADER Structure
Busy VS blocks have a 16-byte (0x10) header which has following structure:
windbg> dt ntdll!_HEAP_VS_CHUNK_HEADER -r+0x000 Sizes: _HEAP_VS_CHUNK_HEADER_SIZE+0x000 MemoryCost: Pos 0, 16 Bits
+0x000 UnsafeSize: Pos 16, 16 Bits
+0x004 UnsafePrevSize: Pos 0, 16 Bits
+0x004 Allocated: Pos 16, 8 Bits
+0x000 KeyUShort: Uint2B+0x000 KeyULong: Uint4B+0x000 HeaderBits: Uint8B+0x008 EncodedSegmentPageOffset : Pos 0, 8 Bits
+0x008 UnusedBytes: Pos 8, 1 Bit+0x008 SkipDuringWalk: Pos 9, 1 Bit+0x008 Spare: Pos 10, 22 Bits
+0x008 AllocatedChunkBits : Uint4B



Sizes - Encoded (see 3.6) QWORD-sized substructure that encapsulates important size and state

information:
 MemoryCost - Used in free VS blocks. A value computed based on how large the committed
portion of the block is. The larger the portion of the block is committed, the lower the memory
cost is. This means that if a low memory cost block is selected for allocation, the smaller amountof memory needs to be committed.
 UnsafeSize - Size of the VS block (includes the block header) in 16-byte blocks.
 UnsafePrevSize - Size of the previous VS block (includes the block header) in 16-byte blocks.
 Allocated - Block is busy if value is not zero.

IBM Security | ©2016 IBM Corporation

20

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

KeyULong - Used in free VS blocks. A DWORD-sized key used when inserting the free VS block to

the VS free tree. The high WORD is the UnsafeSize field and the low WORD is the MemoryCost
field.
EncodedSegmentPageOffset – Encoded (see 3.6) offset of the block from the start of the VS subsegmentin pages.
UnusedBytes - Flag that indicates whether the block has unused bytes which is the difference between
the UserSize and the total block size (minus 0x10 bytes for the header). If this flag is set, the last two
bytes of the VS block is treated as a 16 bit low endian value. If the number of unused bytes is 1, the highbit of this 16 bit value is set and the rest of the bits are unused, otherwise, the high bit is clear and the low
13 bits are used to store the unused bytes value.

Below is an illustration of a busy VS block (note that the first 9 bytes are encoded):_HEAP_VS_CHUNK_FREE_HEADER Structure
Free VS blocks have a 32-byte (0x20) header where the first 8 bytes are the first 8 bytes of the_HEAP_VS_CHUNK_HEADER structure. Starting at offset 0x08 is the Node field which acts as a node in the VS free tree
(VsContext.FreeChunkTree):windbg> dt ntdll!_HEAP_VS_CHUNK_FREE_HEADER -r+0x000 Header: _HEAP_VS_CHUNK_HEADER+0x000 Sizes: _HEAP_VS_CHUNK_HEADER_SIZE+0x000 MemoryCost: Pos 0, 16 Bits
+0x000 UnsafeSize: Pos 16, 16 Bits
+0x004 UnsafePrevSize: Pos 0, 16 Bits
+0x004 Allocated: Pos 16, 8 Bits
+0x000 KeyUShort: Uint2B+0x000 KeyULong: Uint4B+0x000 HeaderBits: Uint8B+0x008 EncodedSegmentPageOffset : Pos 0, 8 Bits
+0x008 UnusedBytes: Pos 8, 1 Bit+0x008 SkipDuringWalk: Pos 9, 1 Bit+0x008 Spare: Pos 10, 22 Bits
+0x008 AllocatedChunkBits : Uint4B+0x000 OverlapsHeader: Uint8B+0x008 Node
: _RTL_BALANCED_NODE

Below is an illustration of a free VS block (note that the first 8 bytes are encoded):

IBM Security | ©2016 IBM Corporation

21

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALSVS Free TreeVS allocation and freeing use the VS free tree for finding and storing information on free VS blocks.
The root of the VS free tree is stored in VsContext.FreeChunkTree and the tree nodes are the Node field of free
VS blocks. The key used for inserting nodes in the VS free tree is the free VS block’s Header.Sizes.KeyULong field(Sizes.KeyULong is discussed in the “_HEAP_VS_CHUNK_HEADER Structure” subsection above).
Below is an illustration of a VS free tree in which there are three free VS blocks with sizes 0xF80, 0x1010 and
0x3010 (all portions of the free blocks are committed - MemoryCost is 0x0000):

VS Allocation
VS allocation is performed via RtlpHpVsContextAllocate() which has the following function signature:
PVOID RtlpHpVsContextAllocate(_HEAP_VS_CONTEXT* VsContext, SIZE_T UserSize, SIZE_T AllocSize,ULONG Flags)

The diagram below shows the logic of RtlpHpVsContextAllocate():IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

22

RtlpHpVsContextAllocate() first traverses the VS free tree to find a free VS block that can fit the allocation. The

search key used for finding a free VS block is a DWORD-sized value in which the high WORD is the number of 16byte blocks that can accommodate AllocSize plus one (for the block header) and the low WORD is 0 (forMemoryCost). This means that a best-fit search is conducted with the free VS block with the lowest memory cost(most portion of the block is committed) given preference, in other words, if two or more free blocks withequivalent size will best fit the allocation, the most committed free block will be selected for the allocation. If anyof the free VS blocks cannot fit the allocation, a new VS subsegment is created.
Since the size of the selected free VS block can be larger than the block size that can accommodate AllocSize,large free VS blocks are split unless the block size of the resulting remaining block will be less than 0x20 bytes (thesize of a free VS block header).

IBM Security | ©2016 IBM Corporation

23

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

The free VS block splitting is performed by RtlpHpVsChunkSplit(). RtlpHpVsChunkSplit() is also the functionthat removes the free VS block from VS free tree and also inserts the resulting remaining free block to the VS freetree if block splitting occurred.

VS Freeing
VS freeing is performed via RtlpHpVsContextFree() which has the following function signature:
BOOLEAN RtlpHpVsContextFree(_HEAP_VS_CONTEXT* VsContext, _HEAP_VS_SUBSEGMENT* VsSubegment,
PVOID UserAddress, ULONG Flags, ULONG* LfhBlockSize)

Where UserAddress is the address of the to-be-freed VS block and LfhBlockSize will become the block size ofthe to-be-freed VS block minus 0x10 (busy VS block header size). LfhBlockSize will be used by the caller of
RtlpHpVsContextFree() in updating the LFH bucket usage counter corresponding to LfhBlockSize.
RtlpHpVsContextFree() first checks if the VS block is indeed allocated by checking the Allocated field in theblock’s header. It will then call RtlpHpVsChunkCoalesce() which will coalesce the to-be-freed block withneighboring free blocks (before and after).

Finally, the coalesced free block is inserted to the VS free tree making it available for allocation.

IBM Security | ©2016 IBM Corporation

24

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

2.4. LOW FRAGMENTATION HEAP
The Low Fragmentation Heap (LFH) is used for allocations with sizes 1 to 16,368 (0x3FF0) bytes. Similar to the LFH
in the NT Heap, the LFH in the Segment Heap prevents fragmentation by using a bucketing scheme which causes
similarly-sized blocks to be allocated from larger pre-allocated blocks of memory.
Below is a table listing the different LFH buckets, the allocation sizes distributed to the buckets, and thecorresponding granularity of the buckets:
Bucket

Allocation Size

Granularity

1 – 641 – 1,024 bytes(0x1 – 0x400)
1,025 – 2,048 bytes(0x401 – 0x800)
2,049 – 4,096 bytes(0x801 – 0x1000)
4,097 – 8,192 bytes(0x1001 – 0x2000)
8,193 – 16,368 bytes(0x2001 – 0x3FF0)

16 bytes

65 – 80
81 – 96
97 – 112
113 – 128

64 bytes
128 bytes
256 bytes
512 bytes

The LFH buckets are only activated (enabled) if their corresponding allocation sizes are detected to be popular. LFH
bucket activation and usage counter will be further discussed later.
Below is an illustration of a few activated buckets and non-activated buckets including their corresponding
allocation sizes:

Buckets #1, #65 and #97 are activated, and therefore, the allocation requests for the corresponding allocation sizes
will be serviced via the LFH buckets. Buckets #81 and #113 are still not activated, and therefore, the allocation
requests for the corresponding allocation sizes will cause the usage counter for the LFH buckets to be updated. If
the usage counter reaches a particular value after the update, the bucket will be activated and the allocation will
be serviced via the LFH bucket, otherwise, the allocation request will eventually be passed to the VS allocation
component.

IBM Security | ©2016 IBM Corporation

25

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALSLFH Subsegments
The LFH component relies on the backend for creating the LFH subsegments where LFH blocks are allocated from.
An LFH subsegment is a special type of a backend block in which the corresponding “first” page range descriptor’s
RangeFlags field has the PAGE_RANGE_FLAGS_LFH_SUBSEGMENT (0x01) bit set.
Below is an illustration of the relationship of the HeapBase, a segment and an LFH subsegment:_HEAP_LFH_CONTEXT Structure
The LFH context tracks the LFH buckets, LFH bucket usage counters and other information related to the LFH state.
It is stored in the LfhContext field in the HeapBase and has the following fields:
windbg> dt ntdll!_HEAP_LFH_CONTEXT -r+0x000 BackendCtx: Ptr64 Void+0x008 Callbacks: _HEAP_SUBALLOCATOR_CALLBACKS+0x030 SubsegmentCreationLock : _RTL_SRWLOCK+0x038 MaxAffinity: UChar+0x040 AffinityModArray : Ptr64 UChar+0x050 SubsegmentCache : _HEAP_LFH_SUBSEGMENT_CACHE+0x000 SLists: [7] _SLIST_HEADER+0x0c0 Buckets: [129] Ptr64 _HEAP_LFH_BUCKETBackendCtx - Pointer to the _SEGMENT_HEAP structure (HeapBase).
Callbacks – Encoded (see 3.5) callbacks for managing the LFH subsegments and the LFH context

extension.
MaxAffinity - Maximum number of affinity slots that can be created.
SubsegmentCache - Tracks cached (unused) LFH subsegments.
Buckets - Array of pointers to the LFH buckets. If the bucket is activated, bit 0 of the pointer is clear andthe pointer points to a _HEAP_LFH_BUCKET structure. Otherwise (if bit 0 is set), the pointer is actually a_HEAP_LFH_ONDEMAND_POINTER structure which is used for tracking LFH bucket usage.
The reserved virtual memory located after the _SEGMENT_HEAP structure in the HeapBase, called the LFH context
extension, is dynamically committed to additionally store LFH bucket-related structures for dynamically activated
LFH buckets (see previous illustration).

_HEAP_LFH_ONDEMAND_POINTER Structure
As mentioned above, if the LFH bucket is not activated, the entry for the bucket in LfhContext.Buckets will be ausage counter. The bucket usage counter has the following structure:
windbg> dt ntdll!_HEAP_LFH_ONDEMAND_POINTERIBM Security | ©2016 IBM Corporation

26

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS+0x000 Invalid: Pos 0, 1 Bit+0x000 AllocationInProgress : Pos 1, 1 Bit+0x000 Spare0: Pos 2, 14 Bits
+0x002 UsageData: Uint2B+0x000 AllBits: Ptr64 Void

Invalid - Marker to determine if this pointer is an invalid _HEAP_LFH_BUCKET pointer (lowest bit set), andtherefore, the structure is a bucket usage counter.
UsageData – WORD-sized value describing the usage of the LFH bucket. The value represented by bit 0 to
4 is the number of active allocations for the bucket’s allocations size, it is incremented on allocations anddecremented on frees. The value represented by bit 5 to 15 is the number of allocation requests for the
bucket’s allocation size, it is incremented on allocations.

_HEAP_LFH_BUCKET Structure
If the bucket is activated, the entry for the bucket in LfhContext.Buckets is a pointer to a _HEAP_LFH_BUCKET
structure which has the following structure:
windbg> dt ntdll!_HEAP_LFH_BUCKET+0x000 State: _HEAP_LFH_SUBSEGMENT_OWNER+0x038 TotalBlockCount : Uint8B+0x040 TotalSubsegmentCount : Uint8B+0x048 ReciprocalBlockSize : Uint4B+0x04c Shift: UChar+0x050 AffinityMappingLock : _RTL_SRWLOCK+0x058 ContentionCount : Uint4B+0x060 ProcAffinityMapping : Ptr64 UChar+0x068 AffinitySlots: Ptr64 Ptr64 _HEAP_LFH_AFFINITY_SLOT









TotalBlockCount - Total number of LFH blocks in all LFH subsegments related to the bucket.
TotalSubsegmentCount - Total number of LFH subsegments related to the bucket.
ContentionCount - Number of contentions identified when allocating blocks from the LFH subsegments.

Every time this field reaches RtlpHpLfhContentionLimit, a new affinity slot is created for the requesting
thread’s processor.
ProcAffinityMapping - Points to an array of BYTE-sized indexes to AffinitySlots. This is used for
dynamically assigning processors to affinity slots (discussed later). Initially, all are set to 0 which meansthat all processors are assigned to the initial affinity slot that was created when the bucket was activated.
AffinitySlots - Pointer to an array of affinity slot pointers (_HEAP_LFH_AFFINITY_SLOT*). When thebucket is activated, only one slot is initially created, as more contentions are detected, new affinity slots
are created.

_HEAP_LFH_AFFINITY_SLOT Structure
An affinity slot owns the LFH subsegments where LFH blocks are allocated from. Initially, only one affinity slot iscreated when the bucket is activated and all processors are assigned to the initial affinity slot.
Because only one affinity slot is initially created, it means that all processors will use the same set of LFH
subsegments, and therefore, contention can occur. If too many contentions are detected, a new affinity slot iscreated and the requesting thread’s processor is reassigned to the new affinity slot via the ProcAffinityMapping
field in the bucket.
There is only one field in an affinity slot and its structure will be described next.

IBM Security | ©2016 IBM Corporation

27

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

windbg> dt ntdll!_HEAP_LFH_AFFINITY_SLOT+0x000 State: _HEAP_LFH_SUBSEGMENT_OWNER

Below is an illustration of the relationship between buckets, processors, affinity slots, and LFH subsegments:_HEAP_LFH_SUBSEGMENT_OWNER Structure
The subsegment owner structure is used by the affinity slot (LfhAffinitySlot.State) to track the LFH
subsegments it owns, it has the following fields:
windbg> dt ntdll!_HEAP_LFH_SUBSEGMENT_OWNER+0x000 IsBucket: Pos 0, 1 Bit+0x000 Spare0: Pos 1, 7 Bits
+0x001 BucketIndex: UChar+0x002 SlotCount: UChar+0x002 SlotIndex: UChar+0x003 Spare1: UChar+0x008 AvailableSubsegmentCount : Uint8B+0x010 Lock
: _RTL_SRWLOCK+0x018 AvailableSubsegmentList : _LIST_ENTRY+0x028 FullSubsegmentList : _LIST_ENTRY

AvailableSubsegmentCount - Number of LFH subsegments in AvailableSubsegmentList.
AvailableSubsegmentList - Linked list of LFH subsegments that have free LFH blocks.
FullSubsegmentList - Linked list of LFH subsegments that have no free LFH blocks.

_HEAP_LFH_SUBSEGMENT Structure
The LFH subsegments are where LFH blocks are allocated from. LFH subsegments are created and initialized via
RtlpHpLfhSubsegmentCreate() and will have the following _HEAP_LFH_SUBSEGMENT structure as the header:
windbg> dt ntdll!_HEAP_LFH_SUBSEGMENT -r+0x000 ListEntry: _LIST_ENTRY+0x000 Link
: _SLIST_ENTRY+0x010 Owner: Ptr64 _HEAP_LFH_SUBSEGMENT_OWNER+0x010 DelayFree: _HEAP_LFH_SUBSEGMENT_DELAY_FREE+0x000 DelayFree: Pos 0, 1 Bit+0x000 Count: Pos 1, 63 Bits
+0x000 AllBits: Ptr64 Void
+0x018 CommitLock: _RTL_SRWLOCK+0x020 FreeCount: Uint2B+0x022 BlockCount: Uint2B+0x020 InterlockedShort : Int2B+0x020 InterlockedLong : Int4B+0x024 FreeHint: Uint2B+0x026 Location: UChar+0x027 Spare: UChar+0x028 BlockOffsets: _HEAP_LFH_SUBSEGMENT_ENCODED_OFFSETSIBM Security | ©2016 IBM Corporation

28

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS+0x000 BlockSize: Uint2B+0x002 FirstBlockOffset : Uint2B+0x000 EncodedData: Uint4B+0x02c CommitUnitShift : UChar+0x02d CommitUnitCount : UChar+0x02e CommitStateOffset : Uint2B+0x030 BlockBitmap: [1] Uint8B













Listentry - Each LFH subsegment is a node of one of the affinity slot’s LFH subsegments lists(LfhAffinitySlot.AvailableSubsegmentList or LfhAffinitySlot.FullSubsegmentList).
Owner - Pointer to the affinity slot that owns this LFH subsegment.
FreeHint - Block index of the recently allocated or freed LFH block. Used in the allocation algorithm whensearching for a free LFH block.
Location - Location of this LFH subsegment in the affinity slot’s LFH subsegments lists: 0:
AvailableSubsegmentList, 1: FullSubsegmentList.
FreeCount - Number of free blocks in the LFH subsegment.
BlockCount - Total number of blocks in the LFH subsegment.
BlockOffsets - Encoded (see 3.7) DWORD-sized substructure containing the size of each LFH block andthe offset of the first LFH block in the LFH subsegment.
 BlockSize - Size of each LFH block in the LFH subsegment.
 FirstBlockOffset - Offset of the first LFH block in the LFH subsegment.
CommitStateOffset - Offset of the commit state array in the LFH subsegment. An LFH subsegment isdivided into multiple “commit portions”; commit state is an array of WORD-sized values that represent
the commit state of each these “commit portions”.
BlockBitmap - Each LFH block is represented by 2 bits in this block bitmap (further discussed below).

Below is an illustration of an LFH subsegment:

And below is an illustration of the different data structures and fields that support the LFH component:

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

29

LFH Block Bitmap
Each LFH block does not have a block header at the beginning, instead, and a block bitmap(LfhSubsegment.BlockBitmap) is used to track the state of each LFH block in the LFH subsegment.
Each LFH block is represented by two bits in the block bitmap. Bit 0 represents the BUSY bit and bit 1 represents
the UNUSED BYTES bit. If the UNUSED BYTES bit is set, it means that there is a difference between the UserSize
and the LFH block size, and the last two bytes of the LFH block is treated as a 16 bit low endian value to represent
the difference. If the number of unused bytes is 1, the high bit of this 16 bit value is set and the rest of the bits areunused, otherwise, the high bit is clear and the low 14 bits are used to store the unused bytes value.
The block bitmap is also subdivided into QWORD-sized (64 bits) chunks, called BitmapBits in this paper, with each
BitmapBits representing 32 LFH blocks.
Below is an illustration of the LFH block bitmap:

IBM Security | ©2016 IBM Corporation

30

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALSLFH Bucket Activation
In every allocation request in which the allocation size is <=16,368 (0x3FF0) bytes, RtlpHpLfhContextAllocate()
is first called to check if the bucket corresponding to the allocation size is activated. If the bucket is activated, theallocation is serviced by the LFH.
If the bucket is not activated, the bucket usage counter is updated. If after the update, the bucket usage counterreaches a particular value, the bucket is activated via RtlpHpLfhBucketActivate() and the LFH will service theallocation request. Otherwise, the VS allocation component will eventually handle the allocation request.
th

Bucket activation occurs if there are 17 active allocations for the bucket’s allocation size. The 17 active allocation
thwill activate the bucket, and the 17 allocation and the next allocations afterwards will be serviced by the LFH.
Bucket activation also occurs if there are 2,040 allocation requests for the bucket’s allocation size, regardless if thethblocks from previous allocations were already freed. The 2,040 allocation will activate the bucket, and theth2,040 allocation and the next allocations afterwards will be serviced by the LFH.

LFH Allocation
LFH allocation is performed via RtlpHpLfhContextAllocate() which has the following function signature:
PVOID RtlpHpLfhContextAllocate(_HEAP_LFH_CONTEXT* LfhContext, SIZE_T UserSize, SIZE_T AllocSize,ULONG Flags)

The first action performed by RtlpHpLfhContextAllocate() is to check if the bucket corresponding to theallocation size is activated. If the bucket is not activated, the usage counter of the bucket is updated, and if theresulting bucket usage after the update is subject for activation, the bucket is activated and LFH allocation willcontinue.
Next, the appropriate affinity slot in the bucket is selected depending on the requesting thread’s processor and theprocessor-to-affinity slot mapping (LfhContext.ProcAffinityMapping). Once the affinity slot is selected,

IBM Security | ©2016 IBM Corporation

31

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

allocation

in

the

affinityslot’savailable

LFH

subsegment

will

be

performed

via

a

call

to

RtlpHpLfhSlotAllocate().
RtlpHpLfhSlotAllocate(), on the other hand, first makes sure that the slot has an available LFH subsegment by

creating a new LFH subsegment or re-using a cached LFH subsegment if needed. RtlpHpLfhSlotAllocate() willthen call RtlpHpLfhSlotReserveBlock() to attempt to reserve a block from one of the affinity slot’s available LFH
subsegments by atomically decrementing an LFH subsegment’s FreeCount field. Too many contention detectedfrom RtlpHpLfhSlotReserveBlock() will eventually cause a new affinity slot to be created for the requesting
thread’s processor.
If RtlpHpLfhSlotReserveBlock() is able to reserve a block in one of the affinity slot’s LFH subsegments,
RtlpHpLfhSlotAllocate() will call RtlpHpLfhSubsegmentAllocateBlock() to perform the actual allocationfrom the LFH subsegment where a block was reserved.
The logic of RtlpHpLfhSubsegmentAllocateBlock() for finding a free LFH block in the LFH subsegment is shownin the diagram below:

The bulk of the logic is from RtlpLfhBlockBitmapAllocate() (inlined in the diagram for brevity) which scans theblock bitmap for a clear BUSY bit. The starting position of the search in the block bitmap is biased by
LfhSubsegment.FreeHint and the selection of a clear BUSY bit is randomized.
IBM Security | ©2016 IBM Corporation

32

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

The logic starts by pointing BlockBitmapPos to a BitmapBits in the block bitmap where FreeHint is (block index
of recently allocated or freed LFH block). It then moves BlockBitmapPos forward until it finds a BitmapBits inwhich at least 1 BUSY bit is clear. If BlockBitmapPos reaches the end of the block bitmap, BlockBitmapPos ispointed to the start of the block bitmap and the search continues.
Once a BitmapBits is selected, the logic will randomly select a bit position in BitmapBits in which the BUSY bit isclear. After the bit position (BitIndex) is selected, the BUSY bit (and UNUSED BYTES bit, if necessary) in the bit
position is set, then, the value pointed to by BlockBitmapPos is atomically updated with the modified BitmapBits
value. Finally, the bit position along with the value of BlockBitmapPos is translated into the address of theallocated LFH block (UserAddress). Note that the retry logic when the atomic update failed is not included in the
diagram for brevity.
Below is an illustration where 8 LFH blocks are sequentially allocated from a new LFH subsegment, notice therandom position of each LFH allocation:

LFH Freeing
LFH freeing is performed via RtlpHpLfhSubsegmentFreeBlock()which has the following function signature:
BOOLEAN RtlpHpLfhSubsegmentFreeBlock(_HEAP_LFH_CONTEXT* LfhContext,_HEAP_LFH_SUBSEGMENT* LfhSubsegment,
PVOID UserAddress, ULONG Flags)

The freeing code first computes the LFH block index of UserAddress (LfhBlockIndex). If LfhBlockIndex index isless than or equal to LfhSubsegment.FreeHint, LfhSubsegment.FreeHint will be set with the value of
LfhBlockIndex.
Next, the corresponding BUSY and UNUSED BYTES bits of the LFH block in the block bitmap are atomically cleared.
Then, the LFH subsegment’s FreeCount field is atomically incremented making the LFH block available forallocation.

2.5. LARGE BLOCKS ALLOCATION
Large blocks allocation is used for allocations with sizes 520,193 bytes and above (>= 0x7F001). Large blocks do
not have a block header at the beginning and are allocated and freed using the virtual memory functions provided
by the NT Memory Manager.

IBM Security | ©2016 IBM Corporation

33

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS_HEAP_LARGE_ALLOC_DATA Structure
Each large block has a corresponding metadata with the following structure:
windbg> dt ntdll!_HEAP_LARGE_ALLOC_DATA+0x000 TreeNode: _RTL_BALANCED_NODE+0x018 VirtualAddress: Uint8B+0x018 UnusedBytes: Pos 0, 16 Bits
+0x020 ExtraPresent: Pos 0, 1 Bit+0x020 Spare: Pos 1, 11 Bits
+0x020 AllocatedPages: Pos 12, 52 Bits






- Each large block metadata is a node of the large blocks metadata tree
(HeapBase.LargeAllocMetadata).
VirtualAddress - Address of the block. First 16 bits are used for the UnusedBytes field.
UnusedBytes - Difference between the UserSize and the committed size of the block.
AllocatedPages – Committed size of the block in pages.
TreeNodeInterestingly, this metadata is stored in a separate heap which address is stored in the global variable
RtlpHpMetadataHeap.

Large Block Allocation
Large block allocation is performed via RtlpHpLargeAlloc() which has the following function signature:
PVOID RtlpHpLargeAlloc(_SEGMENT_HEAP* HeapBase, SIZE_T UserSize, SIZE_T AllocSize, ULONG Flags)

Large block allocation is straightforward since there’s no free tree/list to consult. First, an allocation of the block’s
metadata from the metadata heap is done. Next, via NtAllocateVirtualMemory(), a virtual memory with a size
equal to the allocation size plus 0x1000 bytes for the guard page is reserved. Then, a size equal to the allocation
size is committed from the initially reserved memory, leaving the last guard page still in the reserved state.
After allocating the block, the block’s metadata fields are set and the large allocation bitmap(RtlpHpLargeAllocationBitmap) is updated to mark the block’s address (actually, UserAddress >> 16) as alarge block allocation.
Finally, the block’s metadata is inserted to the large blocks metadata tree (HeapBase.LargeAllocMetadata) using
the block’s address as the key, then, the block’s address (UserAddress) is returned to the caller.
Below is an illustration of different structures and global variables that support large blocks allocation:

IBM Security | ©2016 IBM Corporation

34

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

Large Block Freeing
Large block freeing is performed via RtlpHpLargeFree() which has the following function signature:
BOOLEAN RtlpHpLargeFree(_SEGMENT_HEAP* HeapBase, PVOID UserAddress, ULONG Flags)

Similar to large block allocation, freeing a large block is a straightforward process. First, the metadata of the large
block is retrieved via RtlpHpLargeAllocGetMetadata() and then removed from the large blocks metadata tree
afterwards.
Next, the large allocation bitmap is updated to unmark the block’s address as a large block allocation. Then, thevirtual memory of the block is freed and the block’s metadata is freed.

2.6. BLOCK PADDING
In applications that are not opted-in by default to use the Segment Heap (i.e.: not a Windows app and not a system
executable as discussed in 2.1), an additional 16 (0x10) bytes padding is added to the block. The padding increases
the total block size required for the allocation and changes the layout of backend blocks, VS blocks and LFH blocks.
Below are the layout of a backend, VS and LFH block when padding is added:

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > INTERNALS

35

The padding should be taken into consideration when analyzing allocated blocks, especially if the application underobservation is neither a Windows app nor a system process.

2.7. SUMMARY AND ANALYSIS: INTERNALS
The implementation of the Segment Heap and the NT Heap are very different. The major differences can beobserved in the data structures used, the use of free trees instead of free lists to track free blocks, and the use of abest-fit search algorithm with preference to the most committed block when searching for a free block.
Also, although the LFH in the Segment Heap and the NT Heap have the same purpose of reducing fragmentationand have the same general design, the implementation of the LFH in the Segment Heap had been overhauled. The
major differences can be observed in the data structures used, the block bitmap representing the LFH blocks, andthe absence of a block header at the beginning of each LFH block.

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > SECURITY MECHANISMS

36

3. SECURITY MECHANISMSThis section discusses the different mechanisms added in the Segment Heap to make it difficult or unreliable toattack heap metadata, and in certain cases, make it unreliable to perform precise heap layout manipulation.

3.1. FAST FAIL ON LINKED LIST NODE CORRUPTIONThe Segment Heap uses linked lists for tracking segments and subsegments. Similar to the NT Heap, checks wereadded in the linked list node insertion and removal operations to prevent classic arbitrary writes due to corrupted
linked list nodes. If a corrupted node is detected, the process immediately terminates via the FastFail [7]mechanism:

3.2. FAST FAIL ON RB TREE NODE CORRUPTIONThe Segment Heap uses RB trees for tracking free backend blocks and free VS blocks. It is also used for tracking
large blocks metadata. The NTDLL-exported functions RtlRbInsertNodeEx() and RtlRbRemoveNode() performthe node insertion and removal respectively in addition to making sure that the RB tree is balanced. To prevent
arbitrary writes due to corrupted tree nodes, the aforementioned functions perform validation when manipulating
RB tree nodes. Similar to linked list nodes validation, failure in the validation of RB tree nodes will cause invocationof the FastFail mechanism.
In the example validation below, the parent of the left child will be manipulated, which in turn, may lead to anarbitrary write if the left child’s ParentValue pointer is controlled by an attacker. To prevent an arbitrary write,
the parent’s child nodes are checked if one of them is indeed the left child.

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > SECURITY MECHANISMS

37

3.3. HEAP ADDRESS RANDOMIZATION
To make guessing of the heap address unreliable, randomness is added to where the heap will be located in virtual
memory.
Heap address randomization is performed by RtlpHpSegHeapAllocate(), a function used for the creation of theheap. It is done by first reserving virtual memory with a size equal to the computed size of the heap plus a
randomly generated size (the random size is a multiple of 64KB). After reserving virtual memory, the beginning of
the reserved virtual memory up to a size equal to the initially generated random size is released. Then, HeapBase ispointed to beginning of the unreleased portion of the initially reserved virtual memory.

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > SECURITY MECHANISMS

38

3.4. GUARD PAGES
When VS subsegments, LFH subsegments and large blocks are allocated, a guard page is added at the end of thesubsegment/block. For VS and LFH subsegments, the subsegment size should be >=64KB for a guard page to be
added.
The guard page prevents a sequential overflow from VS blocks, LFH blocks and large blocks from corrupting
adjacent data outside the subsegment (for LFH/VS blocks) or outside the block (for large blocks).

Backend blocks, on the other hand, do not have a guard page after them, allowing an overflow to corrupt adjacentdata outside the block.

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > SECURITY MECHANISMS

39

3.5. FUNCTION POINTER ENCODING
In cases where the attacker is able to determine the address of the heap and assuming that the attacker has aControl Flow Guard (CFG) bypass, the attacker can target the function pointers stored in the HeapBase as a way to
directly control execution flow. To protect these function pointers from trivial modification, the functions pointers
are encoded using the heap key and the LFH/VS context address.

3.6. VS BLOCK HEADER ENCODING
Unlike backend/LFH/large blocks, VS blocks have a header at the beginning of each block which makes VS blockheaders a likely target in a buffer overflow. To protect important parts of the VS block header from trivial
modification, they are encoded using the LFH key and the VS block address.

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > SECURITY MECHANISMS

40

3.7. LFH SUBSEGMENT BLOCKOFFSETS ENCODING
To protect important LFH subsegment header fields from trivial modification, the block size field and the first blockoffset field in the LFH subsegment header are encoded using the LFH key and the LFH subsegment address.

3.8. LFH ALLOCATION RANDOMIZATION
To make exploitation of LFH-based buffer overflows and use-after-frees unreliable, the LFH component randomly
selects which free LFH block to use in an allocation request. The allocation randomization makes it unreliable toplace a target LFH block adjacent to an LFH block that can be overflowed, and it also makes it unreliable to reuse a

IBM Security | ©2016 IBM Corporation

41

WINDOWS 10 SEGMENT HEAP INTERNALS > SECURITY MECHANISMS

recently freed LFH block. The allocation randomization algorithm is discussed in the “LFH Allocation” subsection in
2.4.
Below is an illustration where 8 LFH blocks are sequentially allocated from a new LFH subsegment:thth

Notice the first allocation is on the 20 LFH block, the second allocation is on the 30 block, the third allocation isth
on the 5 block, and so on.

3.9. SUMMARY AND ANALYSIS: SECURITY MECHANISMS
The applied security mechanisms in the Segment Heap are mostly a carryover of the security mechanisms from the
NT Heap, notable of which are the guard pages and the LFH allocation randomization which was new when
Windows 8 was released [5, 8]. Based on this, and how important fields of the new data structures are protected,
the Segment Heap is comparable with the NT Heap in terms of applied security mechanisms. However, it is yet to
be seen how the new Segment Heap data structures will fare when metadata attack research of the Segment Heap
becomes popular.
With regards to heap layout manipulation, the best-fit search algorithm and the free block splitting mechanism of
the backend and the VS component are more welcoming to heap layout manipulation compared to the LFH
component which uses allocation randomization.

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > CASE STUDY

42

4. CASE STUDYThis section examines how the layout of a heap managed by the Segment Heap can be manipulated by discussing a
way to leverage a memory corruption vulnerability for a reliable arbitrary write in the context of the Edge content
process.

4.1. CVE-2016-0117 VULNERABILITY DETAILSThe vulnerability (CVE-2016-0117 [9], MS16-028 [10]) is in WinRT PDF’s [11] PostScript interpreter for Type 4(PostScript Calculator) functions [12]. PostScript Calculator functions use a subset of the PostScript language
operators and these PostScript operators use the PostScript operand stack when performing their functions.
The PostScript operand stack is a vector containing 0x65 CType4Operand pointers. Each CType4Operand, on theother hand, is a data structure consisting of one DWORD that represents the type and one DWORD representing
the value in the PostScript operand stack.
The PostScript operand stack and the CType4Operands are allocated from the MSVCRT heap which is managed by
the Segment Heap if WinRT PDF is loaded in the context of the Edge content process:

The issue is that the PostScript interpreter fails to validate if the PostScript operand stack index is past the end of
the PostScript operand stack (PostScript operand stack index is 0x65), allowing a dereference of a CType4Operandpointer located right after the end of the PostScript operand stack.
If an attacker is able to implant a target address right after the end of the PostScript operand stack, the attacker
will be able to perform a memory write to the target address via a PostScript operation that pushes a value in the
PostScript operand stack.
In the illustration below, multiple integers (1094795585 or 0x41414141) are pushed to the PostScript operand
stack with the last 0x41414141 pushed to invalid index 0x65 of the PostScript operand stack:

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > CASE STUDY

43

4.2. PLAN FOR IMPLANTING THE TARGET ADDRESS
After understanding the vulnerability, the following plan is used to implant the target address after the end of the
PostScript operand stack:
1.

2.
3.

Allocate a controlled buffer and set offset 0x328 of the controlled buffer to the target address(0x4242424242424242). For reliability, the controlled buffer and the PostScript operand stack will be VSallocated instead of being LFH-allocated.
Free the controlled buffer.
The PostScript operand stack will be allocated in the free VS block of the freed controlled buffer.

Below is an illustration of the plan:

Executing the above plan requires the ability to manipulate the MSVCRT heap in order to reliably implant thetarget address after the PostScript operand stack, this includes the ability to allocate a controlled block from the
MSVCRT heap and the ability to free the controlled block. In addition, there will be some issues that will affectreliability (such as free blocks coalescing) which need to be dealt with. The next subsections will discuss thesolutions to these requirements/issues.

IBM Security | ©2016 IBM Corporation

44

WINDOWS 10 SEGMENT HEAP INTERNALS > CASE STUDY

4.3. MANIPULATING THE MSVCRT HEAP WITH CHAKRA’S ARRAYBUFFERJavaScript embedded in the PDF can potentially fulfill the requirement of MSVCRT heap manipulation, but
unfortunately, as of writing, WinRT PDF still does not support embedded JavaScript.
Fortunately, a solution can be found in the Chakra’s (Edge’s JavaScript engine) ArrayBuffer implementation.
Similar to WinRT PDF’s PostScript operand stack, the data buffer of Chakra’s ArrayBuffer is also allocated from
the MSVCRT heap via msvcrt!malloc() [13, 14] if the ArrayBuffer is of a certain size (i.e.: size is less than 64KB,
or for sizes >=64KB, additional checks are performed).
This means that a JavaScript code in an HTML file can allocate and free the controlled buffer from the MSVCRT
heap (step 1 and step 2 of the plan). Then, the JavaScript code can inject an <embed> element in the page whichcauses the PDF file containing the vulnerability trigger to be loaded by WinRT PDF. Upon loading the PDF file,
WinRT PDF will allocate the PostScript operand stack from the MSVCRT heap, and the free VS block of the freed
controlled buffer would then be returned by the heap manager to WinRT PDF to fulfill the allocation request (step3 of the plan).

Allocation and Setting Controlled Values
In the illustration below, a JavaScript code in an HTML file instantiated an ArrayBuffer with a size of 0x340 which
in turn leads to an allocation of a 0x340 bytes block from the MSVCRT heap; offset 0x328 of the block is then set
with the target address:

LFH Bucket Activation
Activating the LFH bucket for a particular allocation size is also an important capability and its use in the plan will
be later discussed. To activate the LFH bucket for a specific allocation size, 17 ArrayBuffer objects with the same
size need to be instantiated:

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > CASE STUDY

45

Freeing and Garbage Collection
Freeing blocks involves removing references to the ArrayBuffer object and then triggering a garbage collection.
Note that Chakra’s CollectGarbage() is still callable but its functionality is disabled in Edge [15], therefore,
another mechanism to trigger garbage collection is needed.
Looking again at the ArrayBuffer functionality, every time an ArrayBuffer is created, the size passed to theArrayBuffer constructor is added to an internal Chakra heap manager counter [16]. If that particular counterreaches >=192MB in machines with >1GB memory (threshold is lower for machines with lower memory), a
concurrent garbage collection is triggered.
Therefore, to perform garbage collection, an ArrayBuffer with a size of 192MB is created, then a delay is
introduced to let the concurrent garbage collection to finish, and afterwards, a succeeding JavaScript code is
executed:

4.4. PREVENTING TARGET ADDRESS CORRUPTION
Since VS allocations are performed using a best-fit policy, the first idea that comes to mind is to VS-allocate thecontrolled buffer using 0x330 as the size. However, this first idea has a problem in that the highest 16 bits of thetarget address will be overwritten with unused bytes value which is stored in the last two bytes of a VS block:To solve the issue, a property of VS chunk splitting can be leveraged. Specifically, as previously mentioned in the“VS Allocation” subsection in 2.3, large free blocks are split unless the block size of the resulting remaining block
will be less than 0x20 bytes.
Therefore, if a 0x340 bytes controlled buffer (total block size including header: 0x350) is used, and that a 0x328
bytes PostScript operand stack (total block size including header: 0x340) will be allocated in the freed controlled
buffer’s free VS block, the size of the remaining block after the split will only be 0x10 bytes, thereby preventing
IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > CASE STUDY46

the split of the 0x350 bytes free VS block. And if that is the case, the unused bytes value will be stored at offset
0x33E of the VS block, leaving the target address unmodified:

4.5. PREVENTING FREE BLOCKS COALESCING
To prevent the free VS block of the freed controlled buffer from being coalesced with neighboring free VS blocks,
15 (instead of one) controlled buffers are created sequentially, then, in an alternating manner, eight are kept busy
and seven are freed.
The illustration below shows a favorable allocation pattern that prevents the free VS blocks of the freed controlled
buffers from being coalesced:

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > CASE STUDY

47

Actual allocation patterns will not always exactly match the above illustration, such as when some of thecontrolled buffers are allocated from a different VS subsegment. However, the multiple freed and busy controlled
buffers increase the chance that at least one or more free VS blocks of the freed controlled buffers will not be
coalesced.

4.6. PREVENTING UNINTENDED USE OF FREE BLOCKS
After the controlled buffers are freed in step 2, their corresponding free VS blocks might be split and used for small
allocations that might occur before step 3. In order to prevent the unintended use of these free VS blocks, thecorresponding LFH buckets for allocation sizes 0x1 to 0x320 are activated so that allocation for those sizes will beserviced by the LFH instead of the VS allocation component:

4.7. ADJUSTED PLAN FOR IMPLANTING THE TARGET ADDRESS
Now that the solutions to the issues were identified, the initial plan for implanting the target address is adjusted to
the following:
1.
2.
3.
4.
5.

HTML/JavaScript: Create 15 controlled buffers by instantiating ArrayBuffer objects with 0x340 as thesize.
HTML/JavaScript: Activate the LFH buckets corresponding to allocation sizes 0x1 to 0x320.
HTML/JavaScript: In an alternating manner, free seven controlled buffers and leave eight controlled
buffers busy.
HTML/JavaScript: Inject an <embed> element to the page in order for WinRT PDF to load the PDF file thattriggers the vulnerability.
PDF: WinRT PDF will allocate the PostScript operand stack and the block by returned by the heap manager
will be the free VS block of one of the freed controlled buffers.

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > CASE STUDY

48

4.8. SUCCESSFUL ARBITRARY WRITE
Once the target address is successfully implanted after the end of the PostScript operand stack and thevulnerability is triggered, arbitrary write is achieved:

4.9. ANALYSIS AND SUMMARY: CASE STUDY
The case study showed that precise layout manipulation is achievable in heaps managed by the Segment Heap.
Specifically, it showed how the layout of VS allocations can be controlled, and how the LFH can be used to preserve
the controlled layout of VS allocations by redirecting unwanted allocation requests to activated LFH buckets.
The two main elements that allowed the precise heap layout manipulation in the case study are the scripting
capability provided by the Chakra JavaScript engine and a common heap used by both Chakra’s ArrayBuffer and
IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > CASE STUDY49

WinRT PDF’s PostScript interpreter. Without these two elements, precise layout manipulation of the MSVCRT heap
using WinRT PDF’s internal allocation and freeing of objects would likely be more difficult.
Finally, when developing proof-of-concepts, one might encounter issues that seem to be unresolvable, such as thetarget address corruption described in the case study. In cases such as those, understanding the internals of theheap implementation will sometimes provide the solution.

IBM Security | ©2016 IBM Corporation

50

WINDOWS 10 SEGMENT HEAP INTERNALS > CONCLUSION

5. CONCLUSION
The internals of the Segment Heap and the NT Heap are largely different. Although some components of theSegment Heap and the NT Heap have the same purpose, the data structures supporting the Segment Heap aremostly unlike their counterpart in the NT Heap. Consequently, these new Segment Heap data structures areinteresting for metadata attack research.
Also, the security mechanisms in the initial release of the Segment Heap in Windows 10 show that previous attacks
and their corresponding mitigations in the NT Heap had been taken into consideration when the Segment Heap
was developed.
In terms of heap layout manipulation, the case study showed that, given a capability to perform arbitrary
allocations and frees, precise layout manipulation of heaps managed by the Segment Heap is achievable. The casestudy also showed that in-depth knowledge of the Segment Heap can help resolve seemingly unresolvable proofof-concept reliability/functionality issues.
Finally, I hope that this paper helped you understand Windows 10’s Segment Heap.

IBM Security | ©2016 IBM Corporation

WINDOWS 10 SEGMENT HEAP INTERNALS > APPENDIX: WINDBG !HEAP EXTENSION COMMANDS FOR SEGMENT HEAP

51

6. APPENDIX: WINDBG !HEAP EXTENSION COMMANDS FOR SEGMENT HEAP
Below are some useful WinDbg !heap extension commands that work with the Segment Heap.

!heap -x <address>
This command is useful if the heap where a block was allocated from is unknown since this command only requires
the block’s address. This command will show the corresponding heap, segment, subsegment, subsegment’s “first”
page range descriptor, type and total size of the block.
Example output for a busy VS block (user-requested size is 0x328 bytes):
windbg> !heap -x 00000203`6b2b6200[100 Percent Complete][33 Percent Complete]
Search was performed for the following Address: 0x000002036b2b6200
Below is a detailed information about this address.
Heap Address: 0x000002036b140000
The address was found in backend heap.
Segment Address: 0x000002036b200000
Page range index (0-255) : 120
Page descriptor address : 0x000002036b200f00
Subsegment address: 0x000002036b278000
Subsegment Size
: 266240 Bytes
Allocation status: Variable size allocated chunk.
Chunk header address: 000002036b2b61f0
Chunk size (bytes): 848
Chunk unused bytes: 24!heap -i <address> -h <heap>
Once the corresponding heap of the block is known, this command can be used to display additional information
about the block such as its user-requested size and the decoded RangeFlags field of the corresponding
subsegment’s “first” page range descriptor.
Example output for a busy VS block (user-requested size is 0x328 bytes, same block as the previous example):windbg> !heap -i 00000203`6b2b6200 -h 000002036b140000
The address 000002036b2b6200 is in Segment 000002036b200000
Page range descriptor address: 000002036b200f00
Page range start address:
000002036b278000
Range flags (2e): First Allocated Committed VS
UserAddress:
0x000002036b2b6200
Block is :Busy
Total Block Size (Bytes): 0x350
User Size (bytes):
0x328
UnusedBytes (bytes):
0x18!heap -s -a -h <heap>
The !heap -s command with the -a option (dump all heap blocks option) can be used for examining the layout ofa heap since it displays information about each block for each Segment Heap component in sequence.
Example output:
windbg> !heap -s -a -h 000002036b140000
Large Allocation X-RAY.

IBM Security | ©2016 IBM Corporation

52

WINDOWS 10 SEGMENT HEAP INTERNALS > APPENDIX: WINDBG !HEAP EXTENSION COMMANDS FOR SEGMENT HEAP

Block Address Metadata Address
20c7fc020c0
20c7fc02080

Virtual Address

20c7fc020c0
20c7fc02080

Pages Ununsed Size
Allocated(Bytes)
227
2383
137
1912

20300df0000
20300ee0000

Backend Heap X-RAY.
Segment
Address

Page Range
Descriptor
Address

Page Range
Descriptor
Index

Subsegment
Address

Range
Flags

Subsegment
Type

Pages
Allocated

UnusedBytes

2036b200000
2036b200000
2036b200000

2036b200040
2036b200260
2036b200a80

2
19
84

2036b202000
2036b213000
2036b254000

2e
2e
f

Variable Alloc
Variable AllocLFH Subsegment

17
65
1

4096
4096
0

[...]
Variable size allocation X-RAY
Segment
Address

Subsegment
Address

Chunk Header
Address

Chunk
Size

BucketIndex

Status

UnusedBytes

2036b200000
2036b200000
2036b200000

2036b202000
2036b202000
2036b202000

2036b202030
2036b202320
2036b202a30

752
1808
272

47
77
17

Allocated
Allocated
Allocated

8
0
0

[...]
LFH X-RAY
Segment
Address

Subsegment
Address

Block
Address

Block
Size

BucketIndex

CommitStatus

Busy
Bytes

Free
Bytes

UnusedBytes

2036b200000
2036b200000
2036b200000

2036b254000
2036b254000
2036b254000

2036b254040
2036b254140
2036b254240

256
256
256

16
16
16

Committed
Committed
Committed

256
256
256

0
0
0

0
0
0

[...]

IBM Security | ©2016 IBM Corporation

53

WINDOWS 10 SEGMENT HEAP INTERNALS > BIBLIOGRAPHY

7. BIBLIOGRAPHY[1] J. McDonald and C. Valasek, "Practical Windows XP/2003 Heap Exploitation," [Online]. Available:
https://www.blackhat.com/presentations/bh-usa-09/MCDONALD/BHUSA09-McDonald-WindowsHeapPAPER.pdf.
Moore,"Heaps
About
Heaps,"[Online].
[2] B.
https://www.insomniasec.com/downloads/publications/Heaps_About_Heaps.ppt.

Available:[3] B. Hawkes, "Attacking the Vista Heap," [Online]. Available: http://www.blackhat.com/presentations/bh-usa08/Hawkes/BH_US_08_Hawkes_Attacking_Vista_Heap.pdf.
Valasek,"Understanding
theLow[4] C.
http://illmatics.com/Understanding_the_LFH.pdf.

Fragmentation

Valasek
andT.
Mandt,"Windows
8Heap[5] C.
http://illmatics.com/Windows%208%20Heap%20Internals.pdf.

Heap,"[Online].

Available:

Internals,"[Online].

Available:[6] Wikipedia, "Red–black tree," [Online]. Available: https://en.wikipedia.org/wiki/Red-black_tree.
[7] A. Ionescu, "New Security Assertions in "Windows 8"," [Online]. Available: http://www.alexionescu.com/?p=69.
[8] K. Johnson and M. Miller, "Exploit Mitigation Improvements in Windows 8," [Online]. Available:
http://media.blackhat.com/bh-us-12/Briefings/M_Miller/BH_US_12_Miller_Exploit_Mitigation_Slides.pdf.
[9] IBM, "X-FORCE ADVISORY: Microsoft Windows WinRT PDF Renderer Library PostScript Interpreter Remote
Code Execution Vulnerability," [Online]. Available: https://exchange.xforce.ibmcloud.com/collection/XFORCE-ADVISORY-Microsoft-Windows-WinRT-PDF-Renderer-Library-PostScript-Interpreter-Remote-CodeExecution-Vulnerability-736a7f02705bd90867262493dca2a2b7.
"Microsoft
Security
BulletinMS16-028[10] Microsoft,
https://technet.microsoft.com/en-us/library/security/ms16-028.aspx.

Critical,"[11] M. V. Yason, "WinRT PDF: A Potential Route for Attacking Edge,"
https://securityintelligence.com/winrt-pdf-a-potential-route-for-attacking-edge/.

[Online].

Available:[Online].

Available:[12] Adobe Systems Incorporated, "Document Management - Portable Document Format - Part 1: PDF 1.7, First
Edition," [Online]. Available: http://www.adobe.com/devnet/pdf/pdf_reference.html.
[13] Microsoft, "GitHub: Microsoft / ChakraCore / lib / Runtime / Library / ArrayBuffer.cpp(JavascriptArrayBuffer::JavascriptArrayBuffer),"[Online].
Available:
https://github.com/Microsoft/ChakraCore/blob/447fa0df2b64717c15ae95a6e4d054ab11ce5be5/lib/Runtime

IBM Security | ©2016 IBM Corporation

54

WINDOWS 10 SEGMENT HEAP INTERNALS > BIBLIOGRAPHY/Library/ArrayBuffer.cpp#L761-L764.
Tomassoli,"IE10:
ReverseEngineering
IE,"[14] M.
kiuhnm.rhcloud.com/2015/05/31/ie10-reverse-engineering-ie/.

[Online].

Available:

http://expdev-"GitHub:
Microsoft/
ChakraCore/
lib/
Common/ConfigFlagsList.h[15] Microsoft,(DEFAULT_CONFIG_CollectGarbage),"[Online].
Available:
https://github.com/Microsoft/ChakraCore/blob/5df046f68f37e8170d0fe5c6cd183fc69bbc10da/lib/Common/
ConfigFlagsList.h#L479-L480.
[16] Microsoft, "GitHub: Microsoft / ChakraCore / lib / Runtime / Library / ArrayBuffer.cpp(JavascriptArrayBuffer::Create),"[Online].
Available:
https://github.com/Microsoft/ChakraCore/blob/447fa0df2b64717c15ae95a6e4d054ab11ce5be5/lib/Runtime/Library/ArrayBuffer.cpp#L779.

[V: 081723]

IBM Security | ©2016 IBM Corporation