Heap in Windows

作者: Kirin_say | 来源:发表于2020-01-01 23:07 被阅读0次

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

Back-End

Struct

_heap

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段开头位置

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:

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)

//有些偏移处值不一定??（多套成员??）
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:

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

_HEAP_VIRTUAL_ALLOC_ENTRY(mmap chunk)

Flink
Blink
_HEAP_ENTRY
user_date

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

For example:

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
对齐方式:

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

BlocksIndex(_HEAP_LIST_LOOKUP)

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

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

+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

Size<=0x4000
0x4000<size<=0xﬀ000
Size>0xﬀ000

Size<=0x4000

1->基本上主要分配都会在RtlpAllocateHeap
2->接着查看size对应到的FrontEndHeapStatusBitmap使否有启用LFH
3->有的话会对对应到的FrontEndHeapUsageData加上0x21
并且检查值是否超过0xﬀ00或者 &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<=0xﬀ000

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

Size>0xﬀ000

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

Free(RtlpFreeHeap)

Size<=0xﬀ000

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&0xﬀ)^(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>0xﬀ000

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

Front-End (LFH)

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

Struct

_LFH_HEAP

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)

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)

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)

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)

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)

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
EncodeOﬀsets： check chunk header
BusyBitmap: bitmap,用于记录该UserBlock中正在使用的chunk
下面区域为Block (chunk)

LFH中的_HEAP_ENTRY (chunk)

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:

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

Alloc

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

_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:

当满足条件时，下一次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

Unlink in Back-End

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

Heap in Windows

Back-End

Struct

_heap

_HEAP_ENTRY (chunk)

_HEAP_VIRTUAL_ALLOC_ENTRY(mmap chunk)

For example:

Attention

BlocksIndex(_HEAP_LIST_LOOKUP)

For Example

Alloc

Size<=0x4000

0x4000<size<=0xﬀ000

Size>0xﬀ000

Free(RtlpFreeHeap)

Size<=0xﬀ000

Size>0xﬀ000

Front-End (LFH)

Struct

Header Encoding in LFH

Alloc

Free

Exploitation in Windows

Unlink in Back-End

UAF in LFH

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

CTF Re&&Pwn