This article explains a fast method of enumerating heaps on Windows. Traditional Windows heap enumeration functions are slower and takes lot of time while traversing large number of heap blocks. This article uncovers the reason behind it and shows you a new efficient way of enumerating process heaps based on reverse engineering of Windows heap API functions.

Some days back I was doing password strength related research on Yahoo Messenger. It used to store the password on the heap and I wrote an sample code using normal heap functions to locate and retrieve the password. The password was basically stored on one of the heap block which was near the end of 60,000th block. So I had to traverse all the 60,000 heap blocks to read the target block and the execution took more than 10 minutes..! I tried running the program on multiple machines but no change. Naturally I was getting irritated as I had to wait for so long just to see the results.

To find a way around this problem, I tried looking on the internet for answers but found nothing. Then I finally resort to finding the truth myself and started reverse engineering the Windows heap functions. Finally after few hours of work, I discovered the reason behind the delay and wrote my own tool which enumerated the complete heaps within few seconds.

This enumeration method does not present any problem when listing small number of heap blocks. However when it comes to enumerating large number of heap blocks (more than 50,000) in each node then it takes more than 10 minutes. This delay cannot be justified in today's computing world.

The reason lies in the poor implementation of Heap32First and Heap32Next functions. Code for both the functions are almost similar except some arithmetic routines used to move to right block. Here is the assembly code for Heap32Next function from kernel32.dll.Let us see what is happening behind the screen...

First it invokes RtlCreateQueryDebugBuffer(0, FALSE) which allocates buffer for storing heap data.On success, it returns pointer to allocated debug buffer which is stored in ebx. If the function fails to allocate buffer then it jumpts to the end of the function otherwise continues with the code below.

Next RtlQueryProcessDebugInformation is called to load all heap blocks of the process. This function in fact loads entire heap nodes and corresponding heap blocks of the process.

Debug Buffer contains the pointer to heap information structure at offset 0x38. First parameter of this heap structure is node count and after that it contains array of DEBUG_HEAP_INFORMATION structure which represent each heap node. The heap information structure is shown below.

Once the node count is retrieved ecx is incremented by 4 to point to the first heap node.

This is simple loop which checks if we are at the right heap node. If not then ecx is incremented by size of DEBUG_HEAP_INFORMATION to move to the next heap node. Here is its structure information.

Once the right heap node is found, it uses the curHeapNode->Blocks pointer to traverse the heap blocks to find the current heap block. Here HEAPENTRY32-> dwResvd is internally used to keep track of block count.

The above code looks for valid heap block based on certain flags. Each heap block has following structure

The above code is error handler which just destroys the buffer created at the beginning, sets the last error code and returns to the caller.

For the first block, if the value curBlock->flag & 2 != 2 then the current block address is computed by adding previos block address and block size.

Once the right heap block is found, its type is determined which can be either LF32_FIXED, LF32_FREE or LF32_MOVEABLE. Using this information, HEAPENTRY32->dwFlags value is updated.

At the end, the allocated buffer is destroyed by calling the function RtlDestroyQueryDebugBuffer.

If there is an error then function BaseSetLastNTError is called to set last error. Otherwise function returns normally.

To summarize, following action takes place during execution of Heap32Next function

This sequence is executed every time Heap32Next is called. Assume that you are enumerating large number of heap blocks (say 50,000) then for every heap block, buffer is created, entire process heap is loaded, traversed and finally the buffer is destroyed. This is the reason behind the long delay while enumerating thousands of heap blocks.

Clearly, its the poor design, one could have just done the allocation & storing heaps during initialization and whenever heap32next is called, it can just traverse the blocks to return the next valid heap block. Using the later approach any large number of heaps can be enumerated in few seconds.

Based on above information found during my reverse engineering of Heap32Next and several other heap functions, I wrote my own heap enumeration function which is much more faster and efficient than using Windows heap functions. Here are the complete details of the implementation

To keep the code simple & readable, I have removed all error checking and other unnecessary instructions.

Here is the sample code demonstrating the traversing through all the heap nodes of a process. It starts with creating debug buffer and then loading entire process heaps using RtlQueryProcessDebugInformation function.Then it enumerates through all the heap nodes and displays the relevant information. At the end, internal buffer is destroyed.

This function initialize heaps and then traverses through all the heap nodes to find the specified heap node. Next it enumerates all the heap blocks within this node using GetFirstHeapBlock & GetNextHeapBlock functions and displays the information.

Much of the functionality for the above functions is derived from the assembly code of Heap32First and Heap32Next functions.

GetFirstHeapBlock returns the first valid heap block in the current heap node. GetNextHeapBlock does the similar task to find next valid heap block. Information about the previous heap block is stored in the HeapBlock structure and it should not be modified by the caller.

If you want to implement heap enumeration functionality in your project, then you can use the following template.

This article gives insight on implementation of Windows heap API functions and explains reason for their slower execution. Then it presents a new way to implement faster and efficient heap enumeration functionality.