FREE BOOK

Chapter 6: Memory Corruption Part II - Heaps

Posted by Addison Wesley Free Book | C# Language November 16, 2009
This chapter discusses a myriad of stability issues that can surface in an application when the heap is used in a nonconventional fashion. Although the stack and the heap are managed very differently in Windows, the process by which we analyze stack- and heap-related problems is the same.

It is important to note that the size reported is the true size of the heap block divided by the heap granularity. The heap granularity is easily found by taking the size of the _HEAP_ENTY_STRUCTURE. A heap block, the size of which is reported to be 0xab, is in reality 0xb8*8 = 0x558 (1368) bytes.
 
The free heap block we are looking at definitely seems to be big enough to fit our allocation request of size 16. In the debug session, step over the first instruction that calls HeapAlloc. If successful, we can then check free list[0] again and see if the allocation we looked at prior to the call has changed:
 
 0:000> dt _LIST_ENTRY 0x00080000+0x178
 [ 0x82ad8 - 0x82ad8 ]
 +0x000 Flink : 0x00082ad8 _LIST_ENTRY [ 0x80178 - 0x80178 ]
 +0x004 Blink : 0x00082ad8 _LIST_ENTRY [ 0x80178 - 0x80178 ]
 0:000> dt _HEAP_ENTRY 0x00082ad8-0x8
 +0x000 Size : 0xa6
 +0x002 PreviousSize : 5
 +0x000 SubSegmentCode : 0x000500a6
 +0x004 SmallTagIndex : 0xee "
 +0x005 Flags : 0x14 "
 +0x006 UnusedBytes : 0xee "
 +0x007 SegmentIndex : 0 "
 
Sure enough, what used to be the first entry in free list[0] has now changed. Instead of a free block of size 0xab, we now have a free block of size 0xa6. The difference in size (0x5) is due to our allocation request breaking up the larger free block we saw previously. If we are allocating 16 bytes (0x10), why is the difference in size of the free block before splitting and after only 0x5 bytes? The key is to remember that the size reported must first be multiplied by the heap granularity factor of 0x8. The true size of the new free allocation is then 0x00000530 (0xa6*8), with the true size difference being 0x28. 0x10 of those 0x28 bytes are our allocation size, and the remaining 0x18 bytes are all metadata associated with our heap block.
 
The next call to HeapAlloc attempts to allocate memory of size 1500. We know that free heap blocks of this size must be located in the free list[0]. However, from our previous investigation, we also know that the only free heap block on the free list[0] is too small to accommodate the size we are requesting. With its hands tied, the heap manager is now forced to commit more memory in the heap segment. To get a better picture of the state of our heap segment, it is useful to do a manual walk of the segment. The _HEAP structure contains an array of pointers to all segments currently active in the heap. The array is located at the base _HEAP address plus an offset of 0x58.
 
 0:000> dd 0x00080000+0x58 l4
 00080058 00080640 00000000 00000000 00000000
 0:000> dt _HEAP_SEGMENT 0x00080640
 +0x000 Entry : _HEAP_ENTRY
 +0x008 Signature : 0xffeeffee
 +0x00c Flags : 0
 +0x010 Heap : 0x00080000 _HEAP
 +0x014 LargestUnCommittedRange : 0xfd000
 +0x018 BaseAddress : 0x00080000
 +0x01c NumberOfPages : 0x100
 +0x020 FirstEntry : 0x00080680 _HEAP_ENTRY
 +0x024 LastValidEntry : 0x00180000 _HEAP_ENTRY
 +0x028 NumberOfUnCommittedPages : 0xfd
 +0x02c NumberOfUnCommittedRanges : 1
 +0x030 UnCommittedRanges : 0x00080588 _HEAP_UNCOMMMTTED_RANGE
 +0x034 AllocatorBackTraceIndex : 0
 +0x036 Reserved : 0
 +0x038 LastEntryInSegment : 0x00082ad0 _HEAP_ENTRY
 
The _HEAP_SEGMENT data structure contains a slew of information used by the heap manager to efficiently manage all the active segments in the heap. When walking a segment, the most useful piece of information is the FirstEntry field located at the base segment address plus an offset of 0x20. This field represents the first heap block in the segment. If we dump out this block and get the size, we can dump out the next heap block by adding the size to the first heap block's address. If we continue this process, the entire segment can be walked, and each allocation can be investigated for correctness.
 
 0:000> dt _HEAP_ENTRY 0x00080680
 +0x000 Size : 0x303
 +0x002 PreviousSize : 8
 +0x000 SubSegmentCode : 0x00080303
 +0x004 SmallTagIndex : 0x9a "
 +0x005 Flags : 0x7 "
 +0x006 UnusedBytes : 0x18 "
 +0x007 SegmentIndex : 0 "
 0:000> dt _HEAP_ENTRY 0x00080680+(0x303*8)
 +0x000 Size : 8
 +0x002 PreviousSize : 0x303
 +0x000 SubSegmentCode : 0x03030008
 +0x004 SmallTagIndex : 0x99 "
 +0x005 Flags : 0x7 "
 +0x006 UnusedBytes : 0x1e "
 +0x007 SegmentIndex : 0 "
 0:000> dt _HEAP_ENTRY 0x00080680+(0x303*8)+(8*8)
 +0x000 Size : 5
 +0x002 PreviousSize : 8
 +0x000 SubSegmentCode : 0x00080005
 +0x004 SmallTagIndex : 0x91 "
 +0x005 Flags : 0x7 "
 +0x006 UnusedBytes : 0x1a "
 +0x007 SegmentIndex : 0 "
...
...
...
 +0x000 Size : 0xa6
 +0x002 PreviousSize : 5
 +0x000 SubSegmentCode : 0x000500a6
 +0x004 SmallTagIndex : 0xee "
 +0x005 Flags : 0x14 "
 +0x006 UnusedBytes : 0xee "
 +0x007 SegmentIndex : 0 "
 
Let's see what the heap manager does to the segment (if anything) to try to satisfy the allocation request of size 1500 bytes. Step over the HeapAlloc call and walk the segment again. The heap block of interest is shown next.
 
 +0x000 Size : 0xbf
 +0x002 PreviousSize : 5
 +0x000 SubSegmentCode : 0x000500bf
 +0x004 SmallTagIndex : 0x10 "
 +0x005 Flags : 0x7 "
 +0x006 UnusedBytes : 0x1c "
 +0x007 SegmentIndex : 0 "
 
Before we stepped over the call to HeapAlloc, the last heap block was marked as free and with a size of 0xa6. After the call, the block status changed to busy with a size of 0xbf (0xbf*8= 0x5f8), indicating that this block is now used to hold our new allocation. Since our allocation was too big to fit into the previous size of 0xa6, the heap manager committed more memory to the segment. Did it commit just enough to hold our allocation? Actually, it committed much more and put the remaining free memory into a new block at address 0x000830c8. The heap manager is only capable of asking for page sized allocations (4KB on x86 systems) from the virtual memory manager and returns the remainder of that allocation to the free lists.
 
The next couple of lines in our application simply free the allocations we just made. What do we anticipate the heap manager to do when it executes the first HeapFree call? In addition to updating the status of the heap block to free and adding it to the free lists, we expect it to try and coalesce the heap block with other surrounding free blocks. Before we step over the first HeapFree call, let's take a look at the heap block associated with that call.
 
 0:000> dt _HEAP_ENTRY 0x000830c8-(0xbf*8)-(0x5*8)
 +0x000 Size : 5
 +0x002 PreviousSize : 0xb
 +0x000 SubSegmentCode : 0x000b0005
 +0x004 SmallTagIndex : 0x1f "
 +0x005 Flags : 0x7 "
 +0x006 UnusedBytes : 0x18 "
 +0x007 SegmentIndex : 0 "
 0:000> dt _HEAP_ENTRY 0x000830c8-(0xbf*8)-(0x5*8)-(0xb*8)
 +0x000 Size : 0xb
 +0x002 PreviousSize : 5
 +0x000 SubSegmentCode : 0x0005000b
 +0x004 SmallTagIndex : 0 "
 +0x005 Flags : 0x7 "
 +0x006 UnusedBytes : 0x1c "
 +0x007 SegmentIndex : 0 "
 0:000> dt _HEAP_ENTRY 0x000830c8-(0xbf*8)
 +0x000 Size : 0xbf
 +0x002 PreviousSize : 5
 +0x000 SubSegmentCode : 0x000500bf
 +0x004 SmallTagIndex : 0x10 "
 +0x005 Flags : 0x7 "
 +0x006 UnusedBytes : 0x1c "
 +0x007 SegmentIndex : 0 "
 
The status of the previous and next heap blocks are both busy (Flags=0x7), which means that the heap manager is not capable of coalescing the memory, and the heap block is simply put on the free lists. More specifically, the heap block will go into free list[1] because the size is 16 bytes. Let's verify our theory-step over the HeapFree call and use the same mechanism as previously used to see what happened to the heap block.
 
 0:000> dt _HEAP_ENTRY 0x000830c8-(0xbf*8)-(0x5*8)
 +0x000 Size : 5
 +0x002 PreviousSize : 0xb
 +0x000 SubSegmentCode : 0x000b0005
 +0x004 SmallTagIndex : 0x1f "
 +0x005 Flags : 0x4 "
 +0x006 UnusedBytes : 0x18 "
 +0x007 SegmentIndex : 0 "
 
As you can see, the heap block status is indeed set to be free, and the size remains the same. Since the size remains the same, it serves as an indicator that the heap manager did not coalesce the heap block with adjacent blocks. Last, we verify that the block made it into the free list[1].
 
I will leave it as an exercise for the reader to figure out what happens to the segment and heap blocks during the next call to HeapFree. Here's a hint: Remember that the size of the heap block being freed is 1500 bytes and that the state of one of the adjacent blocks is set to free.
 
This concludes our overview of the internal workings of the heap manager. Although it might seem like a daunting task to understand and be able to walk the various heap structures, after a little practice, it all becomes easier. Before we move on to the heap corruption scenarios, one important debugger command can help us be more efficient when debugging heap corruption scenarios. The extension command is called !heap and is part of the exts.dll debugger extension. Using this command, you can very easily display all the heap information you could possibly want. Actually, all the information we just manually gathered is outputted by the !heap extension command in a split second. But wait-we just spent a lot of time figuring out how to analyze the heap by hand, walk the segments, and verify the heap blocks. Why even bother if we have this beautiful command that does all the work for us? As always, the answer lies in how the debugger arrives at the information it presents. If the state of the heap is intact, the !heap extension command shows the heap state in a nice and digestible form. If, however, the state of the heap has been corrupted, it is no longer sufficient to rely on the command to tell us what and how it became corrupted. We need to know how to analyze the various parts of the heap to arrive at sound conclusions and possible culprits.

Total Pages : 11 45678

comments