Both allocations sit next to each other, because allocations are taken from the start of a free chunk when splitting. As both allocations are taken from the same larger chunk, it is expected from them to sit together. What is left of the original 0xba0 byte chunk is 0x590 bytes (as expected, showing up as a free chunk which starts at 01561a50 and ends at 01561FE0)<\/p>\n
WinDBG: !heap -p -h <address of default process heap> (output limited to the 3 chunks that are relevant to this exercise: the 2 "new" allocations, and the remaining space)<\/p>\n
01561438 0061 0201 [00] 01561440 00300 - (busy) <\/p>
01561740 0061 0061 [00] 01561748 00300 - (busy) \n<\/p>
01561a48 00b3 0061 [00] 01561a50 00590 - (free)<\/p><\/pre>\n
Great, but we have not been really using the FreeList mechanisms of the BEA at this point. All we have been doing is allocate chunks from within a normal segment, consuming the free space that was there all the time. To trigger the BEA FreeList mechanism and see how it behaves, we'll have to "free" some chunks ourselves first.<\/p>\n
BEA_Alloc2<\/h4>\n
In this second example, we'll create a series of allocations of 0x300 bytes. We'll free the last one and then cause 2 allocations of 0x100 bytes. <\/p>\n
The purpose of the exercise is to check where these 2 allocations will be placed. <\/p>\n
As we intend to evaluate the BEA mechanism, we have to avoid that the LFH gets triggered. We know that the heap manager in Windows 7 will trigger the LFH when it sees 18 consecutive allocations of a size in the same bucket (i.e. the next request will be allocated from within a LFH managed subsegment). <\/p>\n
For that reason, we'll only cause 10 allocations of 0x300 bytes, hopefully avoiding that the LFH will be used.<\/p>\n
After causing the 10 allocations, let's examine the last one and see if LFH is on or off.<\/p>\n
App:<\/p>\n
C:\\Users\\corelan\\Desktop\\vc++\\win10\\BEA_Alloc2\\Release>BEA_Alloc2.exe\nDefault process heap found at 0x009B0000\nPress a key to start...\nAllocated chunk of 0x300 bytes at 0x009BF1D0\nAllocated chunk of 0x300 bytes at 0x009BF4D8\nAllocated chunk of 0x300 bytes at 0x009BF7E0\nAllocated chunk of 0x300 bytes at 0x009BFAE8\nAllocated chunk of 0x300 bytes at 0x009BFDF0\nAllocated chunk of 0x300 bytes at 0x009C00F8\nAllocated chunk of 0x300 bytes at 0x009C0400\nAllocated chunk of 0x300 bytes at 0x009C0708\nAllocated chunk of 0x300 bytes at 0x009C0A10\nAllocated chunk of 0x300 bytes at 0x009C0D18
\nPress return to continue<\/p><\/pre>\n
WinDBG:<\/p>\n
0:003> !heap -x 0x009C0D18\n<\/p>
Entry User Heap Segment Size PrevSize Unused Flags\n<\/p>
-----------------------------------------------------------------------------\n<\/p>
009c0d10 009c0d18 009b0000 009b0000 308 308 8 busy<\/p><\/pre>\n
<\/div>\n
So far so good, no sign of LFH at this point. Next, the application will free this last chunk:<\/div>\n
<\/div>\n
App:<\/div>\n
Free chunk at 0x009C0D18\nPress return to continue\n<\/div><\/pre>\n
<\/div>\n
WinDBG:<\/div>\n
0:003> !heap -x 0x009C0D18
Entry User Heap Segment Size PrevSize Unused Flags\n<\/div>
-----------------------------------------------------------------------------\n<\/div>
009c0d10 009c0d18 009b0000 009b0000 12d0 308 0 free <\/div><\/div><\/pre>\n
Before running the rest of the application, let's look at the current state of the heap, looking for "free" chunks of 0x300 bytes or larger. The output below only contains the relevant lines:<\/p>\n
WinDBG:<\/p>\n
0:003> !heap -p -h 0x009B0000\n<\/p>
_HEAP @ 9b0000\n<\/p>
_LFH_HEAP @ 610000\n<\/p>
_HEAP_SEGMENT @ 9b0000\n<\/p>
CommittedRange @ 9b0498\n<\/p>
HEAP_ENTRY Size Prev Flags UserPtr UserSize - state\n<\/p>
009c0d10 025a 0061 [00] 009c0d18 012c8 - (free)<\/p><\/pre>\n
As we can see in the output, as the last chunk of 0x300 bytes was allocated right before the remaining free space in the segment, this now freed chunk got merged with the adjacent free space in the segment, and has now become a 0x12c8 byte free chunk. This larger free chunk starts at 009c0d10, which is also the start address of the 0x300 byte chunk that was freed. <\/div>\n
<\/div>\n
Our test application will now cause 2 allocations of 0x100 bytes each. Sure enough, this is large enough to satisfy 2 requests for 0x100 bytes, but in order to predict what exactly will happen, we need to look at the heap state again first.<\/div>\n
<\/div>\n
The output of !heap -p -h <default process heap> shows the following lines that refer to free chunks of 0x100 bytes or more:<\/div>\n
<\/div>\n
WinDBG:<\/div>\n
\n
0:003> !heap -p -h 0x009B0000 <\/div>
_HEAP @ 9b0000 <\/div>
_LFH_HEAP @ 610000\n<\/div>
_HEAP_SEGMENT @ 9b0000\n<\/div>
CommittedRange @ 9b0498 <\/div>
HEAP_ENTRY Size Prev Flags UserPtr UserSize - state\n<\/div>
009b2b00 0021 0012 [00] 009b2b08 00100 - (free)\n<\/div>
009bc330 0034 0089 [00] 009bc338 00198 - (free)\n<\/div>
009c0d10 025a 0061 [00] 009c0d18 012c8 - (free)\n<\/div><\/div><\/pre>\n
Based on the output, we can see<\/div>\n
\n
\n- A free chunk of exactly 0x100 bytes (entry starts at 009b2b00, userptr is 009b2b08) <\/font><\/li>\n
- A free chunk of 0x198 bytes (entry starts at 009bc330, userptr is 009bc338) <\/font><\/li>\n
- The remaining free space in the segment, at 009c0d10<\/font><\/li>\n<\/ul>\n<\/div>\n
<\/div>\n
Let's see what logic is applied by the BEA to reuse those freed chunks:<\/div>\n
<\/div>\n
App:<\/div>\n
Allocated chunk of 0x100 bytes at 0x009B2B08\n<\/div>
Allocated chunk of 0x100 bytes at 0x009BC338\n<\/div>
Done...<\/div><\/pre>\n
This makes sense. The chunk that is exactly the size of the allocation request gets reused first. Next, the next one that is larger gets split. The remaining space near the end of the segment, which is now a combination of the original free space and the 0x300 byte chunk that was freed, does not get used.<\/div>\n
<\/div>\n
The 2 chunks are not adjacent (despite the allocations happened right after each other). None of the 2 chunks were able to take memory space back from one the 0x300 byte chunk that was freed earlier. <\/div>\n
<\/div>\n
The behavior is absolutely normal, but this means that we cannot simply use the BEA to take a previously-allocated-and-now-freed chunk back... at least not without doing some "massaging". <\/div>\n
On the other hand, because the BEA does not keep chunks together based on buckets, and if we can improve control, we may be able to use a smaller or a larger allocation size to take a position back in memory that has been freed, regardless of the original size of that freed chunk. <\/div>\n
<\/div>\n
Let's try to increase control over what happens, increasing our chances that we can take a freed chunk back.<\/div>\n
<\/div>\n
<\/div>\n
BEA_Alloc3<\/h4>\nAs demonstrated in the previous exercise, the fact that the BEA is managing freed chunks means that, by default, we may not be able to predict where a new allocation will be placed relative to another chunk or in relation with taking the space of a freed chunk (which would be useful in a Use After Free scenario). <\/div>\n
<\/div>\n
Let's start with the latter scenario first. What does it take to take a freed chunk back?<\/div>\n
<\/div>\n
The answer is quite simple: it depends on what else is free. <\/div>\n
A possible approach to control what else is free, is to simply reduce what is free at the time the free happens that you would like to take back. The idea is to exhaust the freelist as much as possible... and to do that, we need to cause allocations.<\/div>\n
<\/div>\n
Additionally, we may want to check that the freed chunk (the one we're trying to take back... we'll call this one the 'vulnerable' freed chunk) does not sit after an already freed chunk. This would cause both chunks to be merged, and subsequent allocation requests would start consuming the start of the new (bigger chunk). Depending on the size of the first part, it may be difficult to get perfect control over the contents. On the other hand, if you can control the size of that first freed chunk (which will eventually get merged with the 'vulnerable' freed chunk), it might actually allow you to improve control over what bytes exactly you will manage if you don't control all bytes of the new allocation. <\/div>\n
<\/div>\n
Again, it all depends on the layout that you create, and your understanding of what is inside the free list at the time of the allocation that is supposed to take the place of the "vulnerable" freed chunk.<\/div>\n
<\/div>\n
Anyway, let's look at an example. BEA_Alloc3 contains the following scenario: we'll free a 0x58 byte chunk, and the goal is to use a 0x58 byte allocation that will take its position back<\/div>\n
<\/div>\n
Obviously we have to make sure that LFH is never activated (as we are playing with the BEA), and that we can avoid that the 0x58 byte chunk gets merged with an adjacent free chunk. This means that we could try to surround the 0x58 byte chunk by 2 allocations that we created as well, but won't allow to be freed. <\/div>\n
<\/div>\n
In order for all 3 allocations to be adjacent, we have to make sure there is nothing on the free list already that will satisfy any of the 3 allocation requests. In the example application, I am using 10 allocations for both sizes, but of course in reality, you'll need to check how many allocations you need to truly remove all free chunks; while being careful about avoiding LFH at the same time.<\/div>\n
<\/div>\n
As the size of the 1st and 3rd allocation (the ones before and after the 0x58 byte chunk) is not so important, we can choose a size that is not on the freelist yet. (Sizes are not important, because we don't have to take LFH bucket sizes into account. Again, we're playing with the BEA). Anyway, I'll use 0x100 byte chunk to surround the 0x58 chunk.<\/div>\n
<\/div>\n
Run the application, and check the heap after causing a series of allocations for 0x58 and 0x100 bytes, to exhaust the freelist for those sizes.<\/div>\n
<\/div>\n
App:<\/div>\n
\nC:\\Users\\corelan\\Desktop\\vc++\\win10\\BEA_Alloc3\\Release>BEA_Alloc3.exe \n
Default process heap found at 0x016C0000
Press a key to start...\n
Allocated chunk of 0x58 bytes at 0x016C96D0
Allocated chunk of 0x100 bytes at 0x016C2B08
Allocated chunk of 0x58 bytes at 0x016CDF50
Allocated chunk of 0x100 bytes at 0x016CD328
Allocated chunk of 0x58 bytes at 0x016CD430
Allocated chunk of 0x100 bytes at 0x016CFFF8
Allocated chunk of 0x58 bytes at 0x016C2CB8
Allocated chunk of 0x100 bytes at 0x016D0100
Allocated chunk of 0x58 bytes at 0x016CDC18
Allocated chunk of 0x100 bytes at 0x016D0208
Allocated chunk of 0x58 bytes at 0x016CDC78
Allocated chunk of 0x100 bytes at 0x016D0310
Allocated chunk of 0x58 bytes at 0x016D0418
Allocated chunk of 0x100 bytes at 0x016D0478
Allocated chunk of 0x58 bytes at 0x016D0580
Allocated chunk of 0x100 bytes at 0x016D05E0
Allocated chunk of 0x58 bytes at 0x016D06E8
Allocated chunk of 0x100 bytes at 0x016D0748
Allocated chunk of 0x58 bytes at 0x016D0850
Allocated chunk of 0x100 bytes at 0x016D08B0 \n
Press return to continue\n<\/p><\/div><\/pre>\n
WinDBG shows that the last 2 allocations are not part of LFH (which means LFH is not active yet). We can also see that these allocations are taken from the large free chunk at the end of the segment (thus no longer taking already freed chunks that might have been part of the freelist)<\/div>\n
\n0:003> !heap -x 0x016D08B0 \n
Entry User Heap Segment Size PrevSize Unused Flags
-----------------------------------------------------------------------------
016d08a8 016d08b0 016c0000 016c0000 108 60 8 busy\n\n
0:003> !heap -x 0x016D0850
<\/p>
Entry User Heap Segment Size PrevSize Unused Flags
-----------------------------------------------------------------------------
016d0848 016d0850 016c0000 016c0000 60 108 8 busy\n<\/p><\/div><\/pre>\n
Next, the application will cause the necessary layout. As a segment doesn't necessarily want to keep chunks of the same bucket size together, and operates in a first ask, first serve manner (unlike the LFH), the 3 allocations should be placed right next to each other:<\/div>\n
<\/div>\n
App:<\/div>\n
\nAllocated chunk of 0x100 bytes at 0x016D09B8
Allocated chunk of 0x58 bytes at 0x016D0AC0, filled with 'A'
Allocated chunk of 0x100 bytes at 0x016D0B20 \n
Press return to continue\n <\/div><\/pre>\n
Great! We can use WinDBG to confirm that the 3 chunks are adjacent indeed, and that the middle chunk (0x58) is filled with A's<\/p>\n
(from output of !heap -p -h 0x016C0000)<\/p>\n
016d09b0 0021 0021 [00] 016d09b8 00100 - (busy)
016d0ab8 000c 0021 [00] 016d0ac0 00058 - (busy)
016d0b18 0021 000c [00] 016d0b20 00100 - (busy)\n<\/p>
0:001> dd 0x016d0ac0 L 0x58\/4
016d0ac0 41414141 41414141 41414141 41414141
016d0ad0 41414141 41414141 41414141 41414141
016d0ae0 41414141 41414141 41414141 41414141
016d0af0 41414141 41414141 41414141 41414141
016d0b00 41414141 41414141 41414141 41414141
016d0b10 41414141 41414141\n <\/p><\/pre>\n
Next, the 0x58 byte chunk will be freed (which means it should end up on the freelist, and not merged with an adjacent free chunk as long as we don't free the adjacent 0x100 byte chunks ourselves). Finally, a new allocation request for 0x58 is supposed to take that position back. The example application will populate it with B's:<\/p>\n
App:<\/p>\n
Free chunk of 0x58 bytes at 0x016D0AC0
Allocated chunk of 0x58 bytes at 0x016D0AC0, filled with 'B' \n
Done... <\/p><\/pre>\n
WinDBG:<\/p>\n
\n0:001> dd 0x016d0ac0 L 0x58\/4
016d0ac0 42424242 42424242 42424242 42424242
016d0ad0 42424242 42424242 42424242 42424242
016d0ae0 42424242 42424242 42424242 42424242
016d0af0 42424242 42424242 42424242 42424242
016d0b00 42424242 42424242 42424242 42424242
016d0b10 42424242 42424242\n\n<\/div><\/pre>\n
Bingo.<\/p>\n
BEA_Alloc4<\/h4>\n
Let's take it one step further.<\/p>\n
This time we'll free a 0x58 byte chunk, and we'll try to use a 0x80 byte allocation (where we only control the last 4 dwords), to control the exact 4 first dwords in the original 0x58 byte chunk. (I know, replacing one object with another object of a different size sounds kinky... but hey, who knows this could be useful one time ... or not)<\/p>\n
The approach is pretty much the same: we'll start by (trying) to exhaust the freelist for the sizes that we are going to use, to make sure we have better control over what will be returned when we ask for a chunk of those sizes. <\/div>\n
What is different in this case, is the layout we need to allow magic to happen - i.e. to take the first 4 dwords of the 0x58 byte chunk using the last 4 dwords of the 0x80 byte allocation.<\/div>\n
<\/div>\n
The idea is to try to force 2 freed chunks to merge (by placing them next to each other and then freeing both). The so-called "vulnerable" object that gets freed in our imaginary "use after free" scenario is 0x58 bytes, and the goal is to to control the first 4 dwords. The object we can use to replace it with is 0x80 bytes, and we'll pretend we can only control the last 4 dwords of that one. In other words, we have to make sure that we position those 4 dwords with surgical precision, making sure that the "overlap" will happen in the right place. <\/div>\n
<\/div>\n
I generally suck at math, but after spending some time on the abacus, finger counting and scratching my head, I came up with the complex formula that results in trying to position a 0x80-4-4-4-4-8 = 0x68 byte object before the 0x58 byte object. The 4 times 4 bytes are needed to cause overlap, and the additional 8 bytes are there to compensate for the chunk header of the 0x58 byte chunk that sits before the contents of the 0x58 byte chunk, and is thus also consuming space in memory. <\/div>\n
This means that we also have to make sure to remove 0x68 byte chunks from the free list in order to increase control over allocations of that size. <\/div>\n
<\/div>\n
We'll create a layout that consists of 4 allocations: our 'magic' 0x68 and 0x58 objects in the middle, surrounded by 2 other objects, to avoid that a merge of one of the 2 in the middle will cause us to lose control when things start to merge with the wrong objects. We'll also cause a little bit more allocations to try to exhaust the heap, as some of these sizes may be popular sizes. <\/div>\n
<\/div>\n
(Again, the number of allocations you need to properly clear out the free list depends on the applicaiton, the context, basically on what is already free at that time)<\/div>\n
<\/div>\n
Let's see what it looks like:<\/div>\n
<\/div>\n
App:<\/div>\n
\nC:\\Users\\corelan\\Desktop\\vc++\\win10\\BEA_Alloc4\\Release>BEA_Alloc4.exe<\/p>
Default process heap found at 0x010D0000\n<\/p>
Press a key to start...<\/div>\n
<...snip...><\/div>
Allocated chunk of 0x68 bytes at 0x010E1D68<\/div>
Allocated chunk of 0x58 bytes at 0x010E1DD8\n<\/div>
Allocated chunk of 0x80 bytes at 0x010E1E38\n<\/div>
Allocated chunk of 0x68 bytes at 0x010E1EC0\n<\/div>
Allocated chunk of 0x58 bytes at 0x010E1F30\n<\/div>
Allocated chunk of 0x80 bytes at 0x010E1F90\n<\/div>
Allocated chunk of 0x68 bytes at 0x010E2018<\/div>\n\n
Press return to continue<\/div><\/pre>\n
(Check the last 3 chunks in WinDBG (using !heap -x <address>) to make sure that none of them is LFH managed at this point.)<\/div>\n
<\/div>\n
Next, the application creates the initial layout (0x80 \/\/ 0x68 \/\/ 0x58 \/\/ 0x80). The first and last one are just there to prevent the 0x68 and 0x58 sized chunks to accidentally merge with the wrong one. <\/div>\n
<\/div>\n
App:<\/div>\n
\nAllocated start chunk (0x80 bytes) at 0x010E2088
Allocated first chunk (0x68 bytes) at 0x010E2110\n<\/div>
Allocated second 'vulnerable' chunk (0x58 bytes) at 0x010E2180, filled with 'A'\n<\/div>
Allocated end chunk (0x80 bytes) at 0x010E21E0<\/div>\n
Press return to continue<\/div>\n<\/div><\/pre>\n
WinDBG (output from !heap -p -h <address of default process heap>):<\/div>\n
010e2080 0011 000e [00] 010e2088 00080 - (busy)
010e2108 000e 0011 [00] 010e2110 00068 - (busy)\n<\/div>
010e2178 000c 000e [00] 010e2180 00058 - (busy)\n<\/div>
010e21d8 0011 000c [00] 010e21e0 00080 - (busy)<\/div><\/div><\/div><\/pre>\n
Sure enough, the 4 chunks are in the right place. When the 'vulnerable' 0x58 byte chunk gets freed, we'll also cause the first one to free ourselves. This should merge the 2 together.<\/div>\n
<\/div>\n
App:<\/div>\n
\nFree chunk of 0x58 bytes at 0x010E2180\n
Free first chunk of 0x68 bytes at 0x010E2110<\/div>
Press return to continue<\/div><\/div><\/pre>\n
WinDBG shows that we now have one big free chunk at 0x010E2110, of 0xc8 bytes. If we dump it, we see the original 0x68 chunk followed by the vulnerable 0x58 byte chunk.<\/div>\n
0:003> !heap -p -a 0x010E2110\n
address 010e2110 found in <\/div>
_HEAP @ 10d0000\n<\/div>
HEAP_ENTRY Size Prev Flags UserPtr UserSize - state\n<\/div>
010e2108 001a 0000 [00] 010e2110 000c8 - (free)<\/div>\n
0:003> dd 0x010E2110 L 0xc8\/4<\/div>
010e2110 010e2268 010de858 00000000 00000000 <\/div>
010e2120 00000000 00000000 00000000 00000000<\/div>
010e2130 00000000 00000000 00000000 00000000<\/div>
010e2140 00000000 00000000 00000000 00000000<\/div>
010e2150 00000000 00000000 00000000 00000000<\/div>
010e2160 00000000 00000000 00000000 00000000<\/div>
010e2170 00000000 00000000 0c00000c 00008812<\/div>
010e2180 010e2268 010de858 41414141 41414141<\/div>
010e2190 41414141 41414141 41414141 41414141<\/div>
010e21a0 41414141 41414141 41414141 41414141 <\/div>
010e21b0 41414141 41414141 41414141 41414141<\/div>
010e21c0 41414141 41414141 41414141 41414141<\/div>
010e21d0 41414141 41414141<\/div>\n<\/div><\/pre>\n
Finally, our 0x80 byte allocation is now supposed to take the first 0x80 bytes of this free chunk, overwriting the first 4 dwords inside the chunk with A's with the last 4 dwords of the 0x80 byte chunk. <\/div>\n
<\/div>\n
App:<\/div>\n
Allocated chunk of 0x80 bytes at 0x010E2110, filled with 'B'<\/div>
Done...<\/div><\/div><\/pre>\n
WinDBG:<\/div>\n
0:001> !heap -p -a 0x010E2110<\/div>
address 010e2110 found in<\/div>
_HEAP @ 10d0000<\/div>
HEAP_ENTRY Size Prev Flags UserPtr UserSize - state<\/div>
010e2108 0011 0000 [00] 010e2110 00080 - (busy)<\/div><\/div>
\n
0:001> dd 0x010E2110 L 0xc8\/4<\/div>
010e2110 42424242 42424242 42424242 42424242<\/div>
010e2120 42424242 42424242 42424242 42424242<\/div>
010e2130 42424242 42424242 42424242 42424242<\/div>
010e2140 42424242 42424242 42424242 42424242<\/div>
![\"heap1\"](\"https:\/\/www.corelan.be\/wp-content\/uploads\/2016\/07\/heap1_thumb.png\" "\\"heap1\\"")
<\/a><\/p>\n