PDA

View Full Version : Parsing Heap Segments from BackEnd Heap

debasishm89
February 15th, 2015, 13:06
Hello All,

Using windbg if we try to dump heap of a win32 processes(Win7) (Mostly in process which has high heap memory consumption like IE ) using !heap -a 03dc0000 I often find multiple segments of a particular heap like ,

Code:
0:029> !heap -a 03dc0000

Index   Address  Name      Debugging options enabled

  8:   03dc0000 

    Segment at 03dc0000 to 03dd0000 (00010000 bytes committed)

    Segment at 036b0000 to 037b0000 (00100000 bytes committed)

    Segment at 04ff0000 to 051f0000 (00200000 bytes committed)

    Segment at 05b50000 to 05f50000 (00160000 bytes committed)


My questions is how can I find the total number of segments (of any particular heap) and their base addresses from process memory manually??

I know we need to parse some singly Linked list (possibly located @ heap_handle +0x010 offset ) to get all the segments but not sure exactly how I should parse it.

Code:
0:029> dt _heap 03dc0000

ntdll!_HEAP

   +0x000 Entry            : _HEAP_ENTRY

   +0x008 SegmentSignature : 0xffeeffee

   +0x00c SegmentFlags     : 0

   +0x010 SegmentListEntry : _LIST_ENTRY [ 0x36b0010 - 0x3dc00a8 ]

   +0x018 Heap             : 0x03dc0000 _HEAP

   +0x01c BaseAddress      : 0x03dc0000 Void

   +0x020 NumberOfPages    : 0x10

   +0x024 FirstEntry       : 0x03dc0588 _HEAP_ENTRY

   +0x028 LastValidEntry   : 0x03dd0000 _HEAP_ENTRY

   +0x02c NumberOfUnCommittedPages : 0

   +0x030 NumberOfUnCommittedRanges : 1

   +0x034 SegmentAllocatorBackTraceIndex : 0

   +0x036 Reserved         : 0

   +0x038 UCRSegmentList   : _LIST_ENTRY [ 0x3dcfff0 - 0x3dcfff0 ]

   +0x040 Flags            : 0x1002

   +0x044 ForceFlags       : 0

   +0x048 CompatibilityFlags : 0

   +0x04c EncodeFlagMask   : 0x100000

   +0x050 Encoding         : _HEAP_ENTRY

   +0x058 PointerKey       : 0x57eb514f

   +0x05c Interceptor      : 0

   +0x060 VirtualMemoryThreshold : 0xfe00

   +0x064 Signature        : 0xeeffeeff

   +0x068 SegmentReserve   : 0x800000

   +0x06c SegmentCommit    : 0x2000

   +0x070 DeCommitFreeBlockThreshold : 0x800

   +0x074 DeCommitTotalFreeThreshold : 0x2000

   +0x078 TotalFreeSize    : 0x2a7e6

   +0x07c MaximumAllocationSize : 0x7ffdefff

   +0x080 ProcessHeapsListIndex : 8



THANKS,
BanMe_2
February 17th, 2015, 12:04
http://doxygen.reactos.org/d8/d68/lib_2rtl_2heap_8c_aec1df0ad68b09a8132773d9bc46a406b.html

this might help you.
Kayaker
February 19th, 2015, 01:08
Not sure if this leads to your goal, but one thing you could do is walk the contiguous heap memory blocks directly. At the start of each memory chunk is a _HEAP_ENTRY header containing the Size and PreviousSize, so you can walk backwards and forwards from any one memory block.

One thing I found out while playing with this is that since Vista, the _HEAP_ENTRY header for related blocks are encrypted with a random XOR encoding determined on allocation of the heap segment, to thwart heap exploits. Before anything is done with them, various Windows functions verify that encoding. The best description I found explaining that check was from the ShellCoders Handbook. The example is for 32 bit but you can find a similar sequence in x64 ntdll.

Code:


Starting with Windows Vista, the situation has changed a lot: eight random bytes are generated when every heap is created. 

These bytes are xored to the first bytes of a block’s header, and integrity is verified by xoring the three first

bytes and comparing the result to the fourth, as shown in the following code extracted from RtlpCoalesceFreeBlocks() :



    mov eax, [ebx+50h] ; ebx -> Heap. +50 = _HEAP.Encoding

    xor [esi], eax ; esi -> BlockHeader (HEAP_ENTRY)

    mov al, [esi+1] ; HEAP_ENTRY.Size+1

    xor al, [esi] ; HEAP_ENTRY.Size

    xor al, [esi+2] ; HEAP_ENTRY.SmallTagIndex

    cmp [esi+3], al ; HEAP_ENTRY.SubSegmentCode (Vista)

    jnz no_corruption_detected_here



This very same code pattern is repeated several times, and there are other integrity checks.

This is in addition to the fact that Vista implements some degree of ASLR for heap allocations.


So here's an attempt at decoding and walking the heap blocks in Win 7 x64. Attach 64 bit Windbg to notepad.exe

Code:


> !heap -a 1



    Heap entries for Segment00 in Heap 0000000000260000

    

    // Second column is PreviousSize, third column is Size

    

    0000000000260000: 00000 . 00a80 [101] - busy (a7f)

    0000000000260a80: 00a80 . 00860 [101] - busy (85f)

    00000000002612e0: 00860 . 00030 [101] - busy (28)

    ...

    00000000002d4fc0: 09b70 . 00040 [111] - busy (3d)

    00000000002d5000:      0008b000      - uncommitted bytes.


Code:


> dt _HEAP 260000



    ntdll!_HEAP

       +0x000 Entry            : _HEAP_ENTRY

       +0x010 SegmentSignature : 0xffeeffee

       +0x014 SegmentFlags     : 0

       +0x018 SegmentListEntry : _LIST_ENTRY [ 0x00000000`00260128 - 0x260128 ]

       +0x028 Heap             : 0x00000000`00260000 _HEAP

       +0x030 BaseAddress      : 0x00000000`00260000 Void

       +0x038 NumberOfPages    : 0x100

       +0x040 FirstEntry       : 0x00000000`00260a80 _HEAP_ENTRY

       +0x048 LastValidEntry   : 0x00000000`00360000 _HEAP_ENTRY

    

       +0x07c EncodeFlagMask   : 0x100000

       +0x080 Encoding         : _HEAP_ENTRY  //XOR value


To be able to "read" the Size/PreviousSize from the _HEAP_ENTRY header for each memory chunk we first need to XOR decode it with the common _HEAP->Encoding value for the parent memory allocation. The Encoding field is itself a _HEAP_ENTRY structure. On the surface this doesn't make much sense since we're simply using the value as an int64, but for the verification checks above, the Code1 - Code4 fields may provide some coding logic:

Code:


> dt _HEAP_ENTRY



    ntdll!_HEAP_ENTRY

       +0x000 PreviousBlockPrivateData : Ptr64 Void

       +0x008 Size             : Uint2B

       +0x00a Flags            : UChar

       +0x00b SmallTagIndex    : UChar

       +0x00c PreviousSize     : Uint2B

       +0x00e SegmentOffset    : UChar

       +0x00e LFHFlags         : UChar

       +0x00f UnusedBytes      : UChar

       +0x008 CompactHeader    : Uint8B

       +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

       +0x008 AgregateCode     : Uint8B



I found it easiest to get the XOR value from the AgregateCode subfield:

Code:


> ?? ((_HEAP *) 0x260000)->Encoding.AgregateCode



    unsigned int64 0x137f`4bf55a9a



or, as a byte sequence:



> db 260000 + 80 L10



    00000000`00260080  00 00 00 00 00 00 00 00-9a 5a f5 4b 7f 13 00 00


The block header that we want to decode (in this case the very first block chunk at 260000) can be had with:

Code:


> ?? ((_HEAP_ENTRY *) 0x260000)->AgregateCode



    unsigned int64 0x100137f`e2f45a32



or, as a byte sequence:



> db 260000 L10



    00000000`00260000  00 00 00 00 00 00 00 00-32 5a f4 e2 7f 13 00 01



Combining the two commands into an XOR we can decode the first block header:
(Encoding value XOR 10h bytes of block header)

Code:


> ?? ((_HEAP *) 0x260000)->Encoding.AgregateCode ^ ((_HEAP_ENTRY *) 0x260000)->AgregateCode



    unsigned int64 0x1000000`a90100a8



or, as the decoded byte sequence (manually put together)



        00000000`00260000  00 00 00 00 00 00 00 00-a8 00 01 a9 00 00 00 01


If you parse this decoded sequence against the _HEAP_ENTRY structure you can find the relevant values
The sizes are given relative to a 16 byte (0x10) granularity

Code:


(as Windbg tells us with !heap -a 260000)

0000000000260000: 00000 . 00a80 [101] - busy (a7f)



    _HEAP_ENTRY

       +0x000 PreviousBlockPrivateData : (null) 

       +0x008 Size             : 0x0a80

       +0x00a Flags            : 0x01 ''

       +0x00b SmallTagIndex    : 0xa9 ''

       +0x00c PreviousSize     : 0x0000 (this was the first block)

       +0x00e SegmentOffset    : 0 ''

       +0x00f UnusedBytes      : 0x1 ''



Let's try the same thing with the next block at 0x260a80

Code:


> ?? ((_HEAP *) 0x260000)->Encoding.AgregateCode ^ ((_HEAP_ENTRY *) 0x260a80)->AgregateCode



    unsigned int64 0x10000a8`87010086



    00000000`00260a80  00 00 00 00 00 00 00 00-86 00 01 87 a8 00 00 01

    

0000000000260a80: 00a80 . 00860 [101] - busy (85f)



    _HEAP_ENTRY

       +0x000 PreviousBlockPrivateData : (null) 

       +0x008 Size             : 0x0860

       +0x00a Flags            : 0x01 ''

       +0x00b SmallTagIndex    : 0x87 ''

       +0x00c PreviousSize     : 0x0a80

       +0x00e SegmentOffset    : 0 ''

       +0x00f UnusedBytes      : 0x1 ''


As an experiment you can try running the bytes through the Windows verification assembly code above to see how it works.

You could keep walking and decoding the blocks in this manner by adding the Size to get the offset of the next heap chunk until you reach the end of the commited blocks. Note that _HEAP->LastValidEntry is given as 0x360000 in this example, but if you were to look at the last entry listed by !heap -a 1 above, those are uncommitted bytes (????) and not readable, so you'd have to be careful if doing this with a script.
I will leave writing an automatic script for something like this to someone else

Kayaker
debasishm89
February 19th, 2015, 01:21
Thanks a lot

Actually my concern was to find out segments of a heap.I found a way to do this. Not sure if its very legitimate way to do the same. I've posted the solution in SO also(http://stackoverflow.com/questions/28524619/process-heap-segments-and-their-necessity), Just sopy pasting the solution. Please take a look,



I think, I've found a "hacky" way to get the segment base address from memory.

Code:
0:027> !heap

Index   Address  Name      Debugging options enabled

  1:   00790000                

  2:   004d0000                

  3:   028b0000                

  4:   02a40000                

  5:   02fa0000                

  6:   03b00000                

  7:   02ca0000                

  8:   03ac0000                

  9:   04d80000                

 10:   0a850000


We take heap 0x00790000 and list all Segments in it.

Code:


0:027> !heap 00790000

Index   Address  Name      Debugging options enabled

  1:   00790000 

    Segment at 00790000 to 00890000 (00100000 bytes committed)

    Segment at 053a0000 to 054a0000 (00100000 bytes committed)

    Segment at 05d40000 to 05f40000 (00200000 bytes committed)

    Segment at 063e0000 to 067e0000 (00400000 bytes committed)

    Segment at 09ce0000 to 0a4e0000 (007fa000 bytes committed)


Now its time to get the same Segment base addresses manually from memory.

Code:


0:027> dt _HEAP 00790000 

ntdll!_HEAP

   +0x000 Entry            : _HEAP_ENTRY

   +0x008 SegmentSignature : 0xffeeffee

   +0x00c SegmentFlags     : 0

   +0x010 SegmentListEntry : _LIST_ENTRY [ 0x53a0010 - 0x7900a8 ]

   +0x018 Heap             : 0x00790000 _HEAP

   +0x01c BaseAddress      : 0x00790000 Void

   ..

   ..


We are interested in SegmentListEntry (Which is @ offset 0x010)

We dump 2 DWORD from address heap_base + 0x10

Code:
0:027> dd 00790000 + 0x10 L2

00790010  053a0010 007900a8


Then we take the BLINK (which means the 2nd DWORD of above output, which is 0x007900a8) and dump 2 DWROD from there. And we keep doing it until we reach the same pointer from where we started, which is 0x007900a8

Code:
0:027> dd 007900a8 L2

007900a8  00790010 09ce0010

0:027> dd 09ce0010 L2

09ce0010  007900a8 063e0010

0:027> dd 063e0010 L2

063e0010  09ce0010 05d40010

0:027> dd 05d40010 L2

05d40010  063e0010 053a0010

0:027> dd 053a0010 L2

053a0010  05d40010 00790010

0:027> dd 00790010 L2

00790010  053a0010 007900a8



Since we reached the same point from where we started, we can stop here.

Code:
0:027> dd 007900a8 L2

007900a8  00790010 09ce0010

Now take a look at the values we got above. If you subtract 16 from all (except 0x007900a8 and 0x007900a8)them you will get Segment Base addresses.

Code:
0:027> ? 09ce0000 + 16

Evaluate expression: 164495382 = 09ce0016


Which are

Code:


00790000

053a0000

05d40000

063e0000

09ce0000
blabberer
February 22nd, 2015, 03:44
if you were playing with heap in xp the segments were simply available as an array in latest os these have been ostrichisized so you should aim to dig around the sand where it has hidden its head

Code:


0:048> !grep -c "dt ntdll!_HEAP -a Segments 170000" -e "_SEGMENT"

    [00] 0x00170c50 _HEAP_SEGMENT

    [01] 0x07c00000 _HEAP_SEGMENT

    [02] 0x13f00000 _HEAP_SEGMENT

    [03] 0x15960000 _HEAP_SEGMENT

0:048> ?? ((ntdll!_HEAP_SEGMENT *) 0x7c00000 )->BaseAddress

void * 0x07c00000

0:048> ?? ((ntdll!_HEAP_SEGMENT *) 0x170c50 )->BaseAddress

void * 0x00170000

0:048> ?? ((ntdll!_HEAP_SEGMENT *) 0x13f00000 )->BaseAddress

void * 0x13f00000

0:048> ?? ((ntdll!_HEAP_SEGMENT *) 0x15960000 )->BaseAddress

void * 0x15960000
debasishm89
February 22nd, 2015, 05:02
@blabberer

Thanks for your reply. In my case it was Win7 and I wanted to get the segments "manually" from memory, without using any debugger extension/ buitin feature . BTW I posted what I did and how.