Heap in Windows

Heap details in Windows
Mainly from Angelboy‘s analysis and Some details When I Debugging

Back-End

Struct

_heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
0:001> dt _heap
ntdll!_HEAP
+0x000 Segment : _HEAP_SEGMENT
+0x000 Entry : _HEAP_ENTRY
+0x010 SegmentSignature : Uint4B
+0x014 SegmentFlags : Uint4B
+0x018 SegmentListEntry : _LIST_ENTRY
+0x028 Heap : Ptr64 _HEAP
+0x030 BaseAddress : Ptr64 Void
+0x038 NumberOfPages : Uint4B
+0x040 FirstEntry : Ptr64 _HEAP_ENTRY
+0x048 LastValidEntry : Ptr64 _HEAP_ENTRY
+0x050 NumberOfUnCommittedPages : Uint4B
+0x054 NumberOfUnCommittedRanges : Uint4B
+0x058 SegmentAllocatorBackTraceIndex : Uint2B
+0x05a Reserved : Uint2B
+0x060 UCRSegmentList : _LIST_ENTRY
+0x070 Flags : Uint4B
+0x074 ForceFlags : Uint4B
+0x078 CompatibilityFlags : Uint4B
+0x07c EncodeFlagMask : Uint4B
+0x080 Encoding : _HEAP_ENTRY
+0x090 Interceptor : Uint4B
+0x094 VirtualMemoryThreshold : Uint4B
+0x098 Signature : Uint4B
+0x0a0 SegmentReserve : Uint8B
+0x0a8 SegmentCommit : Uint8B
+0x0b0 DeCommitFreeBlockThreshold : Uint8B
+0x0b8 DeCommitTotalFreeThreshold : Uint8B
+0x0c0 TotalFreeSize : Uint8B
+0x0c8 MaximumAllocationSize : Uint8B
+0x0d0 ProcessHeapsListIndex : Uint2B
+0x0d2 HeaderValidateLength : Uint2B
+0x0d8 HeaderValidateCopy : Ptr64 Void
+0x0e0 NextAvailableTagIndex : Uint2B
+0x0e2 MaximumTagIndex : Uint2B
+0x0e8 TagEntries : Ptr64 _HEAP_TAG_ENTRY
+0x0f0 UCRList : _LIST_ENTRY
+0x100 AlignRound : Uint8B
+0x108 AlignMask : Uint8B
+0x110 VirtualAllocdBlocks : _LIST_ENTRY
+0x120 SegmentList : _LIST_ENTRY
+0x130 AllocatorBackTraceIndex : Uint2B
+0x134 NonDedicatedListLength : Uint4B
+0x138 BlocksIndex : Ptr64 Void
+0x140 UCRIndex : Ptr64 Void
+0x148 PseudoTagEntries : Ptr64 _HEAP_PSEUDO_TAG_ENTRY
+0x150 FreeLists : _LIST_ENTRY
+0x160 LockVariable : Ptr64 _HEAP_LOCK
+0x168 CommitRoutine : Ptr64 long
+0x170 StackTraceInitVar : _RTL_RUN_ONCE
+0x178 CommitLimitData : _RTL_HEAP_MEMORY_LIMIT_DATA
+0x198 FrontEndHeap : Ptr64 Void
+0x1a0 FrontHeapLockCount : Uint2B
+0x1a2 FrontEndHeapType : UChar
+0x1a3 RequestedFrontEndHeapType : UChar
+0x1a8 FrontEndHeapUsageData : Ptr64 Wchar
+0x1b0 FrontEndHeapMaximumIndex : Uint2B
+0x1b2 FrontEndHeapStatusBitmap : [129] UChar
+0x238 Counters : _HEAP_COUNTERS
+0x2b0 TuningParameters : _HEAP_TUNING_PARAMETERS

管理heap的结构,一般在每个heap段开头位置

1
2
3
4
5
6
7
EncodeFlagMask: Heap 初始化设置为0x100000,用于判断是否encode该heap的chunk中的header
Encoding: 用于encode(xor)的cookie
BlocksIndex (_HEAP_LIST_LOOKUP_):用来管理Back-End中的chunk
FreeList (_HEAP_ENTRY):串接 Back-End 中的所有 free chunk,类似unsorted bin
FrontEndHeap:指向管理 FrontEnd 的 Heap 的结构
FrontEndHeapUsageData:指向⼀个对应各⼤⼩ chunk 的阵列/记录各种⼤⼩ chunk 的使⽤次数,到达某种程度则 enable 该对应⼤
⼩ chunk 的 Front-End allocator

For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
0:001> dt _heap 00af0000
ntdll!_HEAP
+0x000 Segment : _HEAP_SEGMENT
+0x000 Entry : _HEAP_ENTRY
+0x010 SegmentSignature : 0xffeeffee
+0x014 SegmentFlags : 2
+0x018 SegmentListEntry : _LIST_ENTRY [ 0x00000000`00af0120 - 0xaf0120 ]
+0x028 Heap : 0x00000000`00af0000 _HEAP
+0x030 BaseAddress : 0x00000000`00af0000 Void
+0x038 NumberOfPages : 0xf
+0x040 FirstEntry : 0x00000000`00af0740 _HEAP_ENTRY
+0x048 LastValidEntry : 0x00000000`00aff000 _HEAP_ENTRY
+0x050 NumberOfUnCommittedPages : 8
+0x054 NumberOfUnCommittedRanges : 1
+0x058 SegmentAllocatorBackTraceIndex : 0
+0x05a Reserved : 0
+0x060 UCRSegmentList : _LIST_ENTRY [ 0x00000000`00af6fe0 - 0xaf6fe0 ]
+0x070 Flags : 0x40001062
+0x074 ForceFlags : 0x40000060
+0x078 CompatibilityFlags : 0
+0x07c EncodeFlagMask : 0x100000
+0x080 Encoding : _HEAP_ENTRY
+0x090 Interceptor : 0
+0x094 VirtualMemoryThreshold : 0xff00
+0x098 Signature : 0xeeffeeff
+0x0a0 SegmentReserve : 0x100000
+0x0a8 SegmentCommit : 0x2000
+0x0b0 DeCommitFreeBlockThreshold : 0x100
+0x0b8 DeCommitTotalFreeThreshold : 0x1000
+0x0c0 TotalFreeSize : 0x25e
+0x0c8 MaximumAllocationSize : 0x7fff`fffdefff
+0x0d0 ProcessHeapsListIndex : 3
+0x0d2 HeaderValidateLength : 0x2c0
+0x0d8 HeaderValidateCopy : (null)
+0x0e0 NextAvailableTagIndex : 0
+0x0e2 MaximumTagIndex : 0
+0x0e8 TagEntries : (null)
+0x0f0 UCRList : _LIST_ENTRY [ 0x00000000`00af6fd0 - 0xaf6fd0 ]
+0x100 AlignRound : 0x2f
+0x108 AlignMask : 0xffffffff`fffffff0
+0x110 VirtualAllocdBlocks : _LIST_ENTRY [ 0x00000000`00af0110 - 0xaf0110 ]
+0x120 SegmentList : _LIST_ENTRY [ 0x00000000`00af0018 - 0xaf0018 ]
+0x130 AllocatorBackTraceIndex : 0
+0x134 NonDedicatedListLength : 0
+0x138 BlocksIndex : 0x00000000`00af02e8 Void
+0x140 UCRIndex : (null)
+0x148 PseudoTagEntries : (null)
+0x150 FreeLists : _LIST_ENTRY [ 0x00000000`00af1430 - 0xaf5760 ]
+0x160 LockVariable : 0x00000000`00af02c0 _HEAP_LOCK
+0x168 CommitRoutine : 0x6cb01100`6bd136b5 long +6cb011006bd136b5
+0x170 StackTraceInitVar : _RTL_RUN_ONCE
+0x178 CommitLimitData : _RTL_HEAP_MEMORY_LIMIT_DATA
+0x198 FrontEndHeap : (null)
+0x1a0 FrontHeapLockCount : 0
+0x1a2 FrontEndHeapType : 0 ''
+0x1a3 RequestedFrontEndHeapType : 0 ''
+0x1a8 FrontEndHeapUsageData : 0x00000000`00af0750 ""
+0x1b0 FrontEndHeapMaximumIndex : 0x80
+0x1b2 FrontEndHeapStatusBitmap : [129] ""
+0x238 Counters : _HEAP_COUNTERS
+0x2b0 TuningParameters : _HEAP_TUNING_PARAMETERS

_HEAP_ENTRY (chunk)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//有些偏移处值不一定??(多套成员??)
0:001> dt _HEAP_ENTRY
ntdll!_HEAP_ENTRY
+0x000 UnpackedEntry : _HEAP_UNPACKED_ENTRY
+0x000 PreviousBlockPrivateData : Ptr64 Void
+0x008 Size : Uint2B
+0x00a Flags : UChar
+0x00b SmallTagIndex : UChar
+0x008 SubSegmentCode : Uint4B
+0x00c PreviousSize : Uint2B
+0x00e SegmentOffset : UChar
+0x00e LFHFlags : UChar
+0x00f UnusedBytes : UChar
+0x008 CompactHeader : Uint8B
+0x000 ExtendedEntry : _HEAP_EXTENDED_ENTRY
+0x000 Reserved : Ptr64 Void
+0x008 FunctionIndex : Uint2B
+0x00a ContextValue : Uint2B
+0x008 InterceptorValue : Uint4B
+0x00c UnusedBytesLength : Uint2B
+0x00e EntryOffset : UChar
+0x00f ExtendedBlockSignature : UChar
+0x000 ReservedForAlignment : Ptr64 Void
+0x008 Code1 : Uint4B
+0x00c Code2 : Uint2B
+0x00e Code3 : UChar
+0x00f Code4 : UChar
+0x00c Code234 : Uint4B
+0x008 AgregateCode : Uint8B

Member:

1
2
3
4
5
6
7
8
9
10
11
PreviousBlockPrivateData: 前一个chunk的date(0x10对齐)
size(2bytes): chunk_size>>4
Flag: 当前chunk是否inused
SmallTagIndex: checksum(xor) of previous 3 bytes
PreviousSize: 相邻前一块chunk 的 size(>>4)
SegmentOffset: 有些情况下用于寻找segment
Unusedbyte: 记录malloc后所剩chunk的空间大小,可以⽤来判断chunk是FrontEnd or BackEnd
freed:
Flink: 指向linkedlist中下⼀块chunk
Blink: 指向linkedlist中上⼀块chunk
Unusedbyte===0

_HEAP_VIRTUAL_ALLOC_ENTRY(mmap chunk)

1
2
3
4
5
6
7
8
9
Flink
Blink
_HEAP_ENTRY
user_date

Flink: 指向下⼀块VirtualAlloc出来的chunk
Blink: 指向上⼀块VirtualAlloc出来的chunk
size: 这里指的是unusedsize,且无需shift
Unusedbyte===4

For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
0:002> dq 007a0000+0x80
00000000`007a0080 00000000`00000000 0000a2f8`03506ab9
00000000`007a0090 0000ff00`00000000 00000000`eeffeeff
00000000`007a00a0 00000000`00100000 00000000`00002000
00000000`007a00b0 00000000`00000100 00000000`00001000
00000000`007a00c0 00000000`00000258 00007fff`fffdefff
00000000`007a00d0 00000000`02c00003 00000000`00000000
00000000`007a00e0 00000000`00000000 00000000`00000000
00000000`007a00f0 00000000`007a6fd0 00000000`007a6fd0
0:002> dq 0x00000000007A13F0-0x10
00000000`007a13e0 00000000`00000000 3c00a2eb`0e576ab3
00000000`007a13f0 ba0a0a61`61616161 baadf00d`baadf00d
00000000`007a1400 baadf00d`baadf00d baadf00d`baadf00d
00000000`007a1410 baadf00d`baadf00d baadf00d`baadf00d
00000000`007a1420 baadf00d`baadf00d baadf00d`baadf00d
00000000`007a1430 baadf00d`baadf00d baadf00d`baadf00d
00000000`007a1440 baadf00d`baadf00d baadf00d`baadf00d
00000000`007a1450 abababab`baadf00d abababab`abababab
0:002> ? 0000a2f8`03506ab9^1
Evaluate expression: 179186091190968 = 0000a2f8`03506ab8
0:002> ? 0000a2f8`03506ab9^3c00a2eb`0e576ab3
Evaluate expression: 4323455724098617354 = 3c000013`0d07000a

size=000a (little endian)
0a^00^07=0d

Attention

所有header都会encode(xor)后存入
验证时先用cookie decode,而后前三位校验checksum==第四位
FreeList: Flink->从小到大插入(Blink从大到小),相同大小,后free的chunk在前,并更新ListHint(LIFO)
BlocksIndex(_HEAP_LIST_LOOKUP): 主要⽤来管理各种不同⼤⼩的freedchunk的结构,⽅便快速找到合适大小的chunk
对齐方式:

1
2
size size&0xF==0? size:(((size>>4)<<4)+0x10)
chunksize=size+0x30 (Windows10)

BlocksIndex(_HEAP_LIST_LOOKUP)

1
2
3
4
5
6
7
8
9
10
11
0:002> dt _HEAP_LIST_LOOKUP
ntdll!_HEAP_LIST_LOOKUP
+0x000 ExtendedLookup : Ptr64 _HEAP_LIST_LOOKUP
+0x008 ArraySize : Uint4B
+0x00c ExtraItem : Uint4B
+0x010 ItemCount : Uint4B
+0x014 OutOfRangeItems : Uint4B
+0x018 BaseIndex : Uint4B
+0x020 ListHead : Ptr64 _LIST_ENTRY
+0x028 ListsInUseUlong : Ptr64 Uint4B
+0x030 ListHints : Ptr64 Ptr64 _LIST_ENTRY
1
2
3
4
5
6
7
ExtendedLookup(_HEAP_LIST_LOOKUP):指向下⼀个ExtendedLookup,通常下⼀个会管理更⼤块chunk所⽤的结构
ArraySize:该结构管理的,最⼤chunk的⼤⼩,通常为0x80(实际为0x800)
ItemCount:目前该结构管理的chunk数目
OutofRangeItems:超出该结构所管理⼤⼩的chunk的数量
ListHead(_HEAP_ENTRY):FreeList的Head
ListsInUseUlong:⽤在判断ListHint中是否有合适⼤⼩的chunk,是⼀个bitmap
ListHint:重要结构,⽤来指向相对应⼤⼩的chunk array,其⽬的就在于更快速找到合适⼤⼩的chunk (0x10 size为一个间隔)

For Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
+0x150 FreeLists        : _LIST_ENTRY [ 0x00000000`007a1490 - 0x7a5760 ]

0:002> dq 007a0000+0x150
00000000`007a0150 00000000`007a1490 00000000`007a5760

FreeLists: Flink(007a0150)->007a1490->007a5760->007a0150
Blink(007a0150)->07a5760->007a1490->007a0150

007a1490:
Evaluate expression: 46523482321 = 0000000a`d50400d1
007a5760:
Evaluate expression: 1114577830279 = 00000103`82040187

size:0xd10->0x1870

BlocksIndex:
0:002> dq 007a0000+0x138
00000000`007a0138 00000000`007a02e8

0:002> dt _HEAP_LIST_LOOKUP 00000000`007a02e8
ntdll!_HEAP_LIST_LOOKUP
+0x000 ExtendedLookup : (null)
+0x008 ArraySize : 0x80
+0x00c ExtraItem : 0
+0x010 ItemCount : 2
+0x014 OutOfRangeItems : 2
+0x018 BaseIndex : 0
+0x020 ListHead : 0x00000000`007a0150 _LIST_ENTRY [ 0x00000000`007a1490 - 0x7a5760 ]
+0x028 ListsInUseUlong : 0x00000000`007a0320 -> 0
+0x030 ListHints : 0x00000000`007a0330 -> (null)
因为ArraySize为0x80-> FreeLists中没有小于0x800大小的chunk,所以ListsInUseUlong和ListHints中为空

此时free掉一个100大小的chunk:
0:002> ? 00a2f8`03506ab9^0000a2eb`0d546ab3
Evaluate expression: 81839521802 = 00000013`0e04000a
0:002> dt _HEAP_LIST_LOOKUP 00000000`007a02e8
ntdll!_HEAP_LIST_LOOKUP
+0x000 ExtendedLookup : (null)
+0x008 ArraySize : 0x80
+0x00c ExtraItem : 0
+0x010 ItemCount : 3
+0x014 OutOfRangeItems : 2
+0x018 BaseIndex : 0
+0x020 ListHead : 0x00000000`007a0150 _LIST_ENTRY [ 0x00000000`007a13f0 - 0x7a5760 ]
+0x028 ListsInUseUlong : 0x00000000`007a0320 -> 0x400
+0x030 ListHints : 0x00000000`007a0330 -> (null)

0x400->0b10000000000:ListsInUseUlong对应0xa0的位为1
0:002> dq 007a0330
00000000`007a0330 00000000`00000000 00000000`00000000
00000000`007a0340 00000000`00000000 00000000`00000000
00000000`007a0350 00000000`00000000 00000000`00000000
00000000`007a0360 00000000`00000000 00000000`00000000
00000000`007a0370 00000000`00000000 00000000`00000000
00000000`007a0380 00000000`007a13f0 00000000`00000000
00000000`007a0390 00000000`00000000 00000000`00000000
00000000`007a03a0 00000000`00000000 00000000`00000000
ListHints对应0xa0位置存在chunk 007a13f0

Alloc

1
2
3
Size<=0x4000
0x4000<size<=0xff000
Size>0xff000

Size<=0x4000

1->基本上主要分配都会在RtlpAllocateHeap
2->接着查看size对应到的FrontEndHeapStatusBitmap使否有启用LFH
3->有的话会对对应到的FrontEndHeapUsageData加上0x21
并且检查值是否超过0xff00或者 &0x1f 后超过0x10 : 超过则启用LFH

1: 下面首先查看对应的ListHint中是否有chunk,有则优先分配
2: 如果有大小合适的chunk在ListHint上则移除ListHint,并且查看chunk的Flink⼤⼩是否size与此chunk相同(注意FreeLists按大小排序):
为空则清空
否则将LintHint填上Flink
最后则unlink该chunk,把此chunk从linkedlist中移除返回给user,并将header xor回去(返回时header被encode)

3: 若没有大小合适的chunk: 则从比较⼤的ListHint中找,有找到比较大的chunk后,同样查看下⼀块chunk的size是不是一样大小,有则填上,并且unlink该chunk, 从freelist移除。最后将chunk做切割,剩下的⼤⼩重新加入Freelist,如果可以放进ListHint就会放进去,将切割好的chunk返回给使用者(chunk header同样encode)

如果FreeList中没有可以操作的chunk,则尝试ExtendHeap来加大heap空间,再从extend出来的heap取chunk,接着像上面一样分割返回(chunk header encode),剩下的放回ListHint

0x4000<size<=0xff000

Allocate(RtlpAllocateHeap)
除了没有对LFH的相关操作外,其他都跟0x4000相同

Size>0xff000

Allocate(RtlpAllocateHeap)
Size>0xff000(VirtualMemoryThreshold<<4)
直接使⽤ZwAllocateVirtualMemory,类似直接mmap一大块空间,并且会插入到_HEAP->VirtualAllocdBlocks这个linked list中(这个linked list用来串接该HeapVirtualAllocate出来的区段)

Free(RtlpFreeHeap)

Size<=0xff000

1:首先检查alignment,利⽤unusedbyte判断该chunk状态
如果是非LFH模式下,会对对应到的FrontEndHeapUsageData减1
2:接下来会判断前后的chunk是否为freed,是的话就合并
此时会把可以合并的chunk unlink,并从ListHint移除(移除⽅式与前⾯相同,查看下一个chunk是不是相同⼤⼩,是则补上ListHint)
3:合并之后,update size&prevsize,然后查看是不是最前跟最后,是就插入,否则就从ListHint中插入,并且update ListHint,插入 时也会对linked list进行检查(此检查不会abort,其原因主要是因为不做unlink写入)

For example:
free chunk
->find prev_chunk
->decode prev_chunk_header
->checksum(SmallTagInex==(size&0xff)^(size>>8)^flag)
->check linked list(prevchunk->Flink->Blink==prevchunk->Blink->Flink==prevchunk)
->Find BlocksIndex
->Find suitable BlocksIndex
->check ListHint(==prevchunk)(不等就可以直接合并,无需更新)
->equ: Check prevchunk->Flink==ListHead (相等说明后面没有chunk,直接更新ListHint)
->上个判断 !=ListHead :则decode prevchunk->Flink && check checksum
-> 判断prevchunk->Flink的size和prevchunk的size是否相等,如果相等,直接换掉对应ListHint位置,否则置空
-> unlink prevchunk(Prevchunk->Blink->Flink=Prevchunk->Flink && Prevchunk->Flink->Blink=Prevchunk->Blink)
-> update prevchunk & next chunk: Prevchunk->size && next chunk->prevsize
-> check next chunk,若freed,则继续上面操作来合并
-> Find suitable BlocksIndex: Check prevchunk->Size<ArraySize
-> search insert point:按照大小排序(size前同->LIFO并更新ListHint)
-> insert: 检测对应位置Check S->Blink->Flink==S(check linked list or just check chunk->blink->flink???—>这里没有具体调)(不满足->不会abort,但是不会insert进linked list,并且依然会update ListHint)
-> update ListHint:若对应位置为Null,则填入
-> update header: 根据checksum填充SmallTagIndex
-> encode header
-> Finish
(unlink顺序:chunk->Bink->Flink=chunk->Flink;then chunk->Flink->Blink=chunk->Blink)

Size>0xff000

检查该chunk的linkedlist并从_HEAP->VirtualAllocdBlocks移除
接着使⽤RtlpSecMemFreeVirtualMemory将chunk整个munmap掉

Front-End (LFH)

Windows 10:LowFragmentationHeap
非Debug下Enable
Size < 0x4000

Struct

_LFH_HEAP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
0:001> dt _LFH_HEAP
ntdll!_LFH_HEAP
+0x000 Lock : _RTL_SRWLOCK
+0x008 SubSegmentZones : _LIST_ENTRY
+0x018 Heap : Ptr64 Void
+0x020 NextSegmentInfoArrayAddress : Ptr64 Void
+0x028 FirstUncommittedAddress : Ptr64 Void
+0x030 ReservedAddressLimit : Ptr64 Void
+0x038 SegmentCreate : Uint4B
+0x03c SegmentDelete : Uint4B
+0x040 MinimumCacheDepth : Uint4B
+0x044 CacheShiftThreshold : Uint4B
+0x048 SizeInCache : Uint8B
+0x050 RunInfo : _HEAP_BUCKET_RUN_INFO
+0x060 UserBlockCache : [12] _USER_MEMORY_CACHE_ENTRY
+0x2a0 MemoryPolicies : _HEAP_LFH_MEM_POLICIES
+0x2a4 Buckets : [129] _HEAP_BUCKET
+0x4a8 SegmentInfoArrays : [129] Ptr64 _HEAP_LOCAL_SEGMENT_INFO
+0x8b0 AffinitizedInfoArrays : [129] Ptr64 _HEAP_LOCAL_SEGMENT_INFO
+0xcb8 SegmentAllocator : Ptr64 _SEGMENT_HEAP
+0xcc0 LocalData : [1] _HEAP_LOCAL_DATA


Heap指向对应的_Heap结构
Buckets (_HEAP_BUCKET):用来寻找配置⼤⼩对应到 Block ⼤⼩的阵列
SegmentInfoArray(_HEAP_LOCAL_SEGMENT_INFO):_HEAP_LOCAL_SEGMENT_INFO array,不同⼤⼩对应到不同的 Segment_info 结构,主要管理对应到的 Subsegment 的信息
LocalData (_HEAP_LOCAL_DATA):其中有一个栏位指向 LFH 本⾝,通常⽤于找回 LFH

Buckets (_HEAP_BUCKET)

1
2
3
4
5
6
7
8
9
10
0:001> dt _HEAP_BUCKET
ntdll!_HEAP_BUCKET
+0x000 BlockUnits : Uint2B
+0x002 SizeIndex : UChar
+0x003 UseAffinity : Pos 0, 1 Bit
+0x003 DebugFlags : Pos 1, 2 Bits
+0x003 Flags : UChar

BlockUnits:分配block大小>>4
SizeIndex:使用者需要大小>>4

SegmentInfoArray (_HEAP_LOCAL_SEGMENT_INFO)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
0:001> dt _HEAP_LOCAL_SEGMENT_INFO
ntdll!_HEAP_LOCAL_SEGMENT_INFO
+0x000 LocalData : Ptr64 _HEAP_LOCAL_DATA
+0x008 ActiveSubsegment : Ptr64 _HEAP_SUBSEGMENT
+0x010 CachedItems : [16] Ptr64 _HEAP_SUBSEGMENT
+0x090 SListHeader : _SLIST_HEADER
+0x0a0 Counters : _HEAP_BUCKET_COUNTERS
+0x0a8 LastOpSequence : Uint4B
+0x0ac BucketIndex : Uint2B
+0x0ae LastUsed : Uint2B
+0x0b0 NoThrashCount : Uint2B


LocalData (_HEAP_LOCAL_DATA):对应 _LFH_HEAP->LocalData ,便于从 SegmentInfo 找回 _LFH_HEAP
BucketIndex:指向对应BucketIndex

ActiveSubsegment (_HEAP_SUBSEGMENT):
对应已分配的Subsegment
用于管理Userblock:记录剩余chunk && 该Userblock 最大分配数

CachedItems (_HEAP_SUBSEGMENT):_HEAP_SUBSEGMENT array
存放对应此SegmentInfo且还有可以分配chunk给user的Subsegment
当ActiveSubsegment⽤完时,将从这里填充,并置换掉ActiveSubsegment

ActiveSubsegment (_HEAP_SUBSEGMENT)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
0:001> dt _HEAP_SUBSEGMENT
ntdll!_HEAP_SUBSEGMENT
+0x000 LocalInfo : Ptr64 _HEAP_LOCAL_SEGMENT_INFO
+0x008 UserBlocks : Ptr64 _HEAP_USERDATA_HEADER
+0x010 DelayFreeList : _SLIST_HEADER
+0x020 AggregateExchg : _INTERLOCK_SEQ
+0x024 BlockSize : Uint2B
+0x026 Flags : Uint2B
+0x028 BlockCount : Uint2B
+0x02a SizeIndex : UChar
+0x02b AffinityIndex : UChar
+0x024 Alignment : [2] Uint4B
+0x02c Lock : Uint4B
+0x030 SFreeListEntry : _SINGLE_LIST_ENTRY

LocalInfo:指回对应的_HEAP_LOCAL_SEGMENT_INFO

UserBlock (_HEAP_USERDATA_HEADER):
记录要分配出去的 Chunk (Block) 所在位置
在开头存在一些metadata管理这些chunk

AggregateExchg (_INTERLOCK_SEQ):
用来管理对应的 UserBlock 中还有多少 freed chunk
LFH⽤以此判断是否继续从此UserBlock分配
同时也有 Lock 的作⽤

BlockSize:此UserBlock中每个Block(chunk)的⼤⼩
BlockCount:此UserBlock中Block总数
SizeIndex:该UserBlock对应到的SizeIndex

AggregateExchg (_INTERLOCK_SEQ)

1
2
3
4
5
6
7
8
9
10
0:001> dt _INTERLOCK_SEQ
ntdll!_INTERLOCK_SEQ
+0x000 Depth : Uint2B
+0x002 Hint : Pos 0, 15 Bits
+0x002 Lock : Pos 15, 1 Bit
+0x002 Hint16 : Uint2B
+0x000 Exchg : Int4B

Depth:该UserBlock 所剩余Freed chunk数量
Lock: 用于Lock

UserBlock (_HEAP_USERDATA_HEADER)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
0:001> dt _HEAP_USERDATA_HEADER
ntdll!_HEAP_USERDATA_HEADER
+0x000 SFreeListEntry : _SINGLE_LIST_ENTRY
+0x000 SubSegment : Ptr64 _HEAP_SUBSEGMENT
+0x008 Reserved : Ptr64 Void
+0x010 SizeIndexAndPadding : Uint4B
+0x010 SizeIndex : UChar
+0x011 GuardPagePresent : UChar
+0x012 PaddingBytes : Uint2B
+0x014 Signature : Uint4B
+0x018 EncodedOffsets : _HEAP_USERDATA_OFFSETS
+0x020 BusyBitmap : _RTL_BITMAP_EX
+0x030 BitmapData : [1] Uint8B

SubSegment:指回对应的SubSegment
EncodeOffsets: check chunk header
BusyBitmap: bitmap,用于记录该UserBlock中正在使用的chunk
下面区域为Block (chunk)

LFH中的_HEAP_ENTRY (chunk)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
0:001> dt _HEAP_ENTRY
ntdll!_HEAP_ENTRY
+0x000 UnpackedEntry : _HEAP_UNPACKED_ENTRY
+0x000 PreviousBlockPrivateData : Ptr64 Void
+0x008 Size : Uint2B
+0x00a Flags : UChar
+0x00b SmallTagIndex : UChar
+0x008 SubSegmentCode : Uint4B
+0x00c PreviousSize : Uint2B
+0x00e SegmentOffset : UChar
+0x00e LFHFlags : UChar
+0x00f UnusedBytes : UChar
+0x008 CompactHeader : Uint8B
+0x000 ExtendedEntry : _HEAP_EXTENDED_ENTRY
+0x000 Reserved : Ptr64 Void
+0x008 FunctionIndex : Uint2B
+0x00a ContextValue : Uint2B
+0x008 InterceptorValue : Uint4B
+0x00c UnusedBytesLength : Uint2B
+0x00e EntryOffset : UChar
+0x00f ExtendedBlockSignature : UChar
+0x000 ReservedForAlignment : Ptr64 Void
+0x008 Code1 : Uint4B
+0x00c Code2 : Uint2B
+0x00e Code3 : UChar
+0x00f Code4 : UChar
+0x00c Code234 : Uint4B
+0x008 AgregateCode : Uint8B

其结构为:
PreviousBlockPrivateData (8)
SubSegmentCode (4)
PreviousSize (2)
SegmentOffset (1)
Unusedbyte (1)
User Data
SubSegmentCode:Encode 过的 metadata 用于推回userblock 的位置
PreviousSize:该chunk 在 UserBlock 中对应的 index
Unusedbyte:
inuse:Unusedbyte & 0x80 is true
freed:恒为0x80,⽤于判断是否为 LFH 的 Free chunk

Header Encoding in LFH

XOR with:

1
2
3
4
_HEAP address
LFHkey
Chunk address >> 4
((chunk address) - (UserBlock address)) << 12

Alloc

首先注意到这些结构的组织方式:

1
2
3
4
5
_heap->FrontEndHeap指向_LFH_HEAP
_LFH_HEAP->Buckets[x]指向_HEAP_BUCKET
_LFH_HEAP->SegmentInfoArray[x]指向SegmentInfoArray(_HEAP_LOCAL_SEGMRNT_INFO)
_HEAP_LOCAL_SEGMRNT_INFO->ActiveSubsegment指向segment(_HEAP_SUBSEGMENT)
_HEAP_SUBSEGMENT->UserBlock指向UserBlock

何时使用LFH:
注意上述Back-End中:
分配过程中会在对应FrontEndHeapUsageData位置加上0x21,free后减一,当对应位置FrontEndHeapUsageData[x]>0xFF00或者FrontEndHeapUsageData[x]&0x1F>0x10时初始化
Init:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
当满足条件时,下一次alloc时就会对LFH初始化
会先ExtendFrontEndUsageData及增加更⼤的 BlocksIndex (0x80-0x400),并设置对应bitmap
-- 在 FrontEndHeapUsageData 写上对应的index,此时 enable LFH 范围变为 (idx: 0-0x400)
-- FrontEndHeapUsageData中分为两部分:对应用于判断LFH是否需要初始化的map以及已经enable LFH的chunk size (例如enable malloc 0x50大小的chunk,则写入0x50>>4=5)
-- 原BlocksIndex进行扩展,即新建一个BlocksIndex,写入原BlocksIndex->ExtendedLookup,进行扩展
建立 FrontEndHeap
初始化对应的SegmentInfoArrays[idx]
-- 在 SegmentInfoArrays[BucketIndex] 填上 segmentInfo
接下来再alloc相同大小chunk就会使用LFH

Example:
17次时&0x1F>0x10:enable LFH
18次时初始化FrontEndHeapUsageData和 BlocksIndex和SegmentInfoArrays[idx]
19次时Userblock初始化,设置对应的chunk和ActiviteSubsegment,并从中返回一块chunk

Alloc After Init:
Allocate (RtlpLowFragHeapAllocFromContext)
->首先尝试从当前ActiveSubsegment分配(by ActiveSubsegment->depth)
->失败则从CachedItem中分配
->分配成功则将ActiveSubsegment换为对应CachedItem中的SubSegment

Details:
如何选取UserBlock中的chunk:
RtlpLowFragHeapRandomData为一个random(0<=x<=0x7F) 256 byte序列
->首先取得 RtlpLowFragHeapRandomData[x] 上的值
->下⼀次会从RtlpLowFragHeapRandomData[x+1] 取值
->x(0~255),下次一个循环: x=rand()%256
->取RtlpLowFragHeapRandomData[x]*maxidx >> 7
->如果已分配则向后搜索最近的可分配的(检查对应的BusyBitmap->是0直接返回,非0则继续向下搜索)
-> check chunk((unused byte & 0x3f) !=0 (chunk freed)
->最后设置好index 及 unused byte并返回给使用者
(检测过程中更新bitmap和AggregateExchg(Depth信息))

Free

-> Update unused byte in chunk header
-> Find the index of the Chunk and reset Userblock->BusyBitmap
-> Update ActiveSubsegment->AggregateExchg
-> if chunk freed not belong to current ActiveSubsegment->try into cachedItems

Details:
-> chunk header中保存了在UserBlock中的index->get addr of UserBlock
-> UserBlock->SubSegment找到当前SubSegment
-> 设置chunk->unused byte = 0x80
-> 更新chunk-> bitmap
-> 更新此SubSegment对应的AggregateExchg(Depth)
-> chunk不在当前ActiveSubsegment,尝试放进CachedItems

Exploitation in Windows

Tips:
Blink&&Flink直接指向user data域,因此与Linux下不同的是无需伪造一个fake chunk即可完成unlink获得指向自身的指针从而任意地址读写(前提需要知道保存堆指针的地址)
同时unlink后的chunk重新insert的过程中由于linked链被破坏,无法pass最后一个check of Flink&&Blink->幸运的是,这里windows只会放弃insert,并且更新ListHint(without crash)

UAF in LFH

Tips:
注意到从UserBlock来Alloc chunk过程:
会通过一个随机序列决定分配位置
导致UAF无法像Linux下LIFO利用
可以先将UserBlock填满,下一步Free后再次malloc即可获得目标chunk