Windows 10 Segment HeapInternals

Mark Vincent Yason
IBM X-Force Advanced Researchyasonm[at]ph[dot]ibm[dot]com@MarkYason

Agenda: Windows 10 Segment Heap
• Internals• Security Mechanisms• Case Study and Demonstration

2IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Notes• Companion white paper is available

̶ Details of data structures, algorithms and internal functions• Paper and presentation are based on the following NTDLL build

̶ NTDLL.DLL (64-bit) version 10.0.14295.1000
̶ From Windows 10 Redstone 1 Preview (Build 14295)

3IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSWINDOWS 10 SEGMENT HEAP INTERNALSInternals: Overview

Architecture

5IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Defaults• Segment Heap is currently an opt-in feature• Windows apps (Modern/Metro apps) are opted-in by default

̶ Apps from the Windows Store, Microsoft Edge, etc.
• Executables with the following names are also opted-in bydefault (system processes)

̶ csrss.exe, lsass.exe, runtimebroker.exe, services.exe, smss.exe,svchost.exe• NT Heap (older heap implementation) is still the default fortraditional applications

6IBM SecurityWINDOWS 10 SEGMENT HEAP INTERNALS

Configuration• Per-executable
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

• Global
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Session Manager\Segment Heap
Enabled = (DWORD)
0: Disable Segment Heap
(Not 0): Enable Segment Heap

7

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Edge Content Process Heaps• Segment Heap: default process heap, MSVCRT heap, etc.
• Some heaps are still managed by the NT Heap (e.g.: sharedheaps, heaps that are not growable)

8IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSHeapBase• Heap address/handle returned by HeapCreate() orRtlCreateHeap()• Signature field (+0x10): 0xDDEEDDEE (Segment Heap)

9IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSWINDOWS 10 SEGMENT HEAP INTERNALSInternals: Backend

Backend• Allocation Size: >128KB to 508KB (page size granularity)• Segments are 1MB virtual memory allocated via
NtAllocateVirtualMemory()• Backend blocks are group of pages in a segment

11IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Backend Page Range Descriptors• Describe the pages in the segment• “First” page range descriptors additionally describe the start ofa backend block

12IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Backend Page Range Descriptors Example• Example: 131,328 (0x20100) bytes busy backend block• “First” page range descriptor is highlighted

13IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Backend Free Tree
• Red-black tree (RB tree) of free backend blocks• Key: Page count, encoded commit count (bitwise NOT of thenumber of committed pages)

14IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Backend Allocation and Freeing• Allocation

̶ Best-fit search with preference to most committed block̶ Large free blocks are split• Freeing̶ Coalesce to-be-freed block with neighbors

15IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSWINDOWS 10 SEGMENT HEAP INTERNALSInternals: Variable Size Allocation

Variable Size (VS) Allocation• Allocation Size: <=128 KB (16 bytes granularity, 16 bytes busyblock header)• VS blocks are allocated from VS subsegments

17IBM SecurityWINDOWS 10 SEGMENT HEAP INTERNALSVS Subsegment• Backend block with “VS Subsegment (0x20)” bit set in page
range descriptor’s RangeFlags field• VS blocks start at offset 0x30

18IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSVS Block Header• Busy VS block (first 9 bytes are encoded)• Free VS block (first 8 bytes are encoded)

19

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSVS Free Tree
• RB tree of free VS blocks• Key: Block size (in 16-byte blocks), memory cost (mostcommitted blocks have a lower memory cost)

20

IBM SecurityWINDOWS 10 SEGMENT HEAP INTERNALSVS Allocation and Freeing• Allocation

̶ Best-fit search with preference to most committed block̶ Large free blocks are split unless the block size of the resulting
remaining block will be less than 0x20 bytes• Freeing̶ Coalesce to-be-freed block with neighbors

21IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSWINDOWS 10 SEGMENT HEAP INTERNALSInternals: Low Fragmentation Heap

Low Fragmentation Heap (LFH)• Allocation Size: <=16,368 bytes (granularity depends on theallocation size)• Prevents fragmentation by allocating similarly-sized blocks fromlarger pre-allocated blocks of memory (LFH subsegments)

23

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSLFH Buckets• Allocation sizes are distributed to buckets• Bucket is activated on the 17th active allocation or the 2,040th
allocation request for the bucket’s allocation size

24

Bucket

Allocation Size

Granularity

1 – 641 – 1,024 bytes(0x1 – 0x400)

16 bytes

65 – 80

1,025 – 2,048 bytes(0x401 – 0x800)

64 bytes

81 – 962,049 – 4,096 bytes(0x801 – 0x1000)

128 bytes

97 – 112

4,097 – 8,192 bytes(0x1001 – 0x2000)

256 bytes

113 – 128

8,193 – 16,368 bytes 512 bytes(0x2001 – 0x3FF0)

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSLFH Affinity Slots• Affinity slots own the LFH subsegments where LFH blocks areallocated from• After bucket activation: 1 affinity slot is created with allprocessors assigned to it• Too much contention: new affinity slots are created andprocessors are re-assigned to the new affinity slots

25IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSLFH Subsegment• Backend block with “LFH Subsegment (0x01)” bit set in page
range descriptor’s RangeFlags field• LFH blocks are stored after the LFH subsegment metadata

26

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSLFH Block Bitmap• 2 bits per LFH block (BUSY bit and UNUSED BYTES bit)
• Divided into BitmapBits (64 bits each = 32 LFH blocks)

27

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSLFH Allocation and Freeing• Allocation

̶ Select a BitmapBits from block bitmap (biased by a free hint)̶ Randomly select a bit position (where BUSY bit is clear) in
BitmapBits, set BUSY and UNUSED BYTES bits; result:• Freeing̶ Clear block’s BUSY and UNUSED BYTES bits in the block bitmap

28

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSWINDOWS 10 SEGMENT HEAP INTERNALSInternals: Large Blocks Allocation

Large Blocks Allocation• Allocation Size: >508KB• Blocks are allocated via NtAllocateVirtualMemory()• Block metadata is stored in a separate heap

30

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSLarge Blocks Allocation and Freeing• Allocation

̶ Allocate block’s metadata̶ Allocate block’s virtual memory̶ Mark block’s address in the large allocation bitmap• Freeing̶ Unmark block’s address in the large allocation bitmap
̶ Free block’s virtual memory

̶ Free block’s metadata

31

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSWINDOWS 10 SEGMENT HEAP INTERNALSInternals: Block Padding

Block Padding• Added if the application is not opted-in by default to use theSegment Heap

• Padding increases the total block size and changes the layout ofbackend blocks, VS blocks and LFH blocks

33

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSWINDOWS 10 SEGMENT HEAP INTERNALSInternals: SummaryInternals: Summary• Four components: Backend, VS allocation, LFH, and large blocks
allocation• Largely different data structures compared to the NT Heap
• Free trees instead of free lists• Only VS blocks have a header at the beginning of each block• Backend/VS allocation: Best-fit search algorithm with preference
to most committed block• LFH allocation: Free blocks are randomly selected

35IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSWINDOWS 10 SEGMENT HEAP INTERNALS

Security Mechanisms

FastFail on Linked List Node Corruption• Segment and subsegment lists are linked lists• Prevents classic arbitrary writes due to corrupted linked listnodes

37

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSFastFail on Tree Node Corruption• Backend and VS free trees are RB trees• Prevents arbitrary writes due to corrupted tree nodes

38

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSHeap Address Randomization• Makes guessing of the heap address unreliable

39

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Guard Pages• Prevents overflow outside the subsegment (VS and LFH blocks)
or outside the block (large blocks)• VS/LFH subsegment size should be >=64KB• Backend blocks (non-subsegment) do not have a guard page40

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Function Pointer Encoding• Protects function pointers in the HeapBase from trivial
modification

41

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSVS Block Header Encoding• Protects important VS block header fields from trivial
modification

42

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSLFH Subsegment BlockOffsets Encoding• Protects important LFH subsegment header fields from trivial
modification

43

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSLFH Allocation Randomization• Makes exploitation of LFH-based buffer overflows and use-afterfrees unreliable• Example: 8 sequential allocations in a new LFH subsegment

44

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Security Mechanisms: Summary• Important Segment Heap metadata are encoded• Linked list nodes and tree nodes are checked• Guard pages and some randomization are added• Precise LFH allocation layout manipulation is difficult• Precise backend and VS allocation layout manipulation isachievable (no randomization)

45

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSWINDOWS 10 SEGMENT HEAP INTERNALS

Case Study and Demonstration

WinRT PDF• Built-in PDF library since Windows 8.1 (Windows.Data.Pdf.dll)• Used by Edge in Windows 10 to render PDFs
• Vulnerabilities can be used in Edge drive-by attacks

47

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSWinRT PDF: PostScript Operand Stack• Used by the WinRT PDF’s PostScript interpreter for Type 4(PostScript Calculator) functions• 0x65 CType4Operand pointers stored in the MSVCRT heap

48

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSWinRT PDF: CVE-2016-0117• PostScript interpreter allows access to PostScript operand stackindex 0x65 (out-of-bounds)• Arbitrary write possible if value after the end of PostScriptoperand stack is attacker-controlled

49

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSPlan for Implanting the Target Address• Allocate a controlled buffer, free it, and the PostScript operand
stack will be allocated in its place• Controlled buffer and PostScript operand stack will be VSallocated for reliability

50

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Problem #1: MSVCRT Heap Manipulation• Embedded JavaScript in PDF could potentially help, but it is not
currently supported in WinRT PDF• Solution: Chakra (Edge’s JS engine) and Chakra’s ArrayBuffer

51

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Problem #1: MSVCRT Heap Manipulation• LFH bucket activation• CollectGarbage() does not work in Edge, but concurrent
garbage collection can be triggered

52

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Problem #2: Target Address Corruption• Showstopper: Target address will become corrupted by VSunused bytes value

53

IBM SecurityWINDOWS 10 SEGMENT HEAP INTERNALS

Problem #2: Target Address Corruption• VS internals: “Large free blocks are split unless the block size ofthe resulting remaining block will be less than 0x20 bytes”• Solution: Use 0x340 bytes controlled buffer (block size: 0x350):
0x350 free block – 0x340 block allocation == 0x10 (no split)

54

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Problem #3: Free Blocks Coalescing• Free VS block of freed controlled buffer will be coalesced• Solution: Alternating busy and free controlled buffers• Actual allocation patterns willnot always exactly match theillustration, but the chance of an
un-coalesced freed controlled
buffer block is increased

55

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Problem #4: Unintended Use of Free Blocks• Free VS blocks of freed controlled buffers will be split and will be
used for small allocations• Solution: Redirect small allocation sizes to the LFH

56

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Adjusted Plan for Implanting the Target Address• HTML/JS will setup the MSVCRT heap layout, PDF will trigger thevulnerability

57

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSDemo: Successful Arbitrary Write

58

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Case Study: Summary• Precise layout manipulation of VS allocations was performed• LFH can be used to preserve the controlled VS allocations layout
by servicing unintended allocations• Scripting capability (Chakra) plus a common heap between
components (Chakra’s Arraybuffer and WinRT PDF’s
PostScript interpreter) are key to the heap layout manipulation• Seemingly unresolvable problems can potentially be solved byknowledge of heap implementation internals

59

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSWINDOWS 10 SEGMENT HEAP INTERNALS

Conclusion

Conclusion• Internals of the Segment Heap and the NT Heap are largelydifferent• Security mechanisms are comparable with the NT Heap
• New data structures are interesting for metadata attack research• Precise heap layout manipulation is achievable in certain cases• Refer to the white paper for more detailed information

61

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALS

Prior Works / References• 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.
• B. Moore, "Heaps About Heaps," [Online]. Available:
https://www.insomniasec.com/downloads/publications/Heaps_About_Heaps.ppt.
• B. Hawkes, "Attacking the Vista Heap," [Online]. Available: http://www.blackhat.com/presentations/bhusa-08/Hawkes/BH_US_08_Hawkes_Attacking_Vista_Heap.pdf.
• C. Valasek, "Understanding the Low Fragmentation Heap," [Online]. Available:
http://illmatics.com/Understanding_the_LFH.pdf.
• C. Valasek and T. Mandt, "Windows 8 Heap Internals," [Online]. Available:
http://illmatics.com/Windows%208%20Heap%20Internals.pdf.
• K. Johnson and M. Miller, "Exploit Mitigation Improvements in Windows 8," [Online]. Available:
http://media.blackhat.com/bh-us12/Briefings/M_Miller/BH_US_12_Miller_Exploit_Mitigation_Slides.pdf.
• M. Tomassoli, "IE10: Reverse Engineering IE," [Online]. Available: http://expdevkiuhnm.rhcloud.com/2015/05/31/ie10-reverse-engineering-ie/.

62

IBM Security

WINDOWS 10 SEGMENT HEAP INTERNALSTHANK YOU
FOLLOW US ON:
ibm.com/security

securityintelligence.com
xforce.ibmcloud.com@ibmsecurityyoutube/user/ibmsecuritysolutions© Copyright IBM Corporation 2016. All rights reserved. The information contained in these materials is provided for informati onal purposes only, and is provided AS IS without warranty of any kind,
express or implied. Any statement of direction represents IBM's current intent, is subject to change or withdrawal, and represent only goals and objectives. IBM, the IBM logo, and other IBM products
and services are trademarks of the International Business Machines Corporation, in the United States, other countries or both. Other company, product, or service names may be trademarks or service
marks of others.
Statement of Good Security Practices: IT system security involves protecting systems and information through prevention, detection and response to improper access from within and outside yourenterprise. Improper access can result in information being altered, destroyed, misappropriated or misused or can result in damage to or misuse of your systems, including for use in attacks on others.
No IT system or product should be considered completely secure and no single product, service or security measure can be completely effective in preventing improper use or access. IBM systems,products and services are designed to be part of a lawful, comprehensive security approach, which will necessarily involve additional operational procedures, and may require other systems, products
or services to be most effective. IBM does not warrant that any systems, products or services are immune from, or will make your enterprise immune from, the malicious or illegal conduct of any party.

[V: 081723]