One crucial element of exploiting dynamic memory allocation issues (use-after-free, double-free, heap overflow) is to have a detailed understanding of how the memory is dynamically allocated by a given system.
All modern systems rely on heap allocators. These allocators use different allocation strategies that differs based on the developers objectives. Examples include jemalloc in BSD, kalloc in iOS kernel, and glibc’s ptmalloc.
Broadcom, for its own reasons, chose not to rely on the default heap allocator and implemented its own allocator named BcmHeapManager.
A Quick Look Into the eCos Source
If we check the eCos source code provided by the different manufacturers using the Broadcom eCos variant (see research for samples), we’ll see that this heap allocator is referenced in a few locations:
Prototypes for malloc and free are defined in packages/net/bsd_tcpip/v2_0/src/ecos/support.c:
In packages/services/memalloc/common/v2_0/src/malloc.cxx, we get the first explanation about how all of this works in the comment section:
In packages/services/memalloc/common/v2_0/include/membcm.hxx, a shim to use Broadcom memory allocator as system pool handler is defined:
The last piece of the puzzle is present in packages/services/memalloc/common/v2_0/include/mvarimpl.inl:
So we know the system uses the BcmHeapManager implementation and that it is linked at compile time. The implementation itself is closed source so we’ll need to manually reverse engineer the dynamic memory management functions (malloc, free, realloc, calloc) from an existing firmware.
Let’s start by looking at the structures used to represent allocated memory.
Reconstructing Heap Nodes Metadata
One way of understanding heap nodes metadata is by looking at dynamic memory of a running system. In the excerpt below, we list the free list content by using the CLI command ‘CM/HeapManager/walk’:
If we read the content at address 0x864e67ec (node y), we see that the two first words are pointers - the first one to the next node (0x8653fdb0, node z), the second one to the previous node (0x86429f38, node x) - and the third word is the node size (0x14 = 20).
We can repeat the experience with the previous node:
So we can consider that a heap node looks like this:
Which can be define in C like this:
BcmHeapManager Allocation Strategy
There are 3 doubly linked lists:
HEAP_ALLOC_LIST - keeps track of allocated memory
HEAP_FREE_LIST - keeps track of available memory
HEAP_FREED_LIST - used during coalescing
During the heap manager initialization, the freed list and alloc list are initialized as empty lists. The free list is initialized as a list with a single node element the size of the entire memory pool.
During a device normal operation, the content of these lists can look like the diagram below:
BcmHeapManager Data Section Variables
The following variables comes from the data section and are heavily used by the dynamic allocator:
Boolean indicating whether the heap structure has been initialized. Set by BcmHeapInit.
Heap initial size
Currently available memory on the heap
Pointer to the start of the heap
Pointer to the end of the heap.
Pointer to the end of the heap + overhead
Heap low water mark
Heap fragmentation percentage
Amount of nodes on the alloc list
Amount of nodes on the free list
Amount of nodes on the freed list
Amount of memory corruptions detected during malloc/realloc
Amount of memory corruptions found during bound checks
Amount of failed allocation
Amount of failed deallocation
Last fail size
Amount of memory corruptions detected during free/realloc
Corrupted nodes found during bounds check that could not be recovered or fixed
Corrupted nodes found during bounds check that could be recovered or fixed
Heap statistics structure
Latest allocated node size
Enable alloc tracing
Enable bounds checking on heap
Note: the BCM_HEAP naming convention comes from the presence of two strings in the binary: BCM_HEAP_BOUNDS_CHECK and BCM_HEAP_THREAD_TRACKING.
The allocation strategy relies on a FIFO-ordered first fit, where the allocator goes over the free list and carves a node out of the first node with enough memory to contain the newly requested allocation. The newly created heap node is then inserted at the head of the alloc list.
If the allocator cannot find a suitable candidate before it reaches the end of the free list or after 500 iteration over the list, the allocation simply fails.
Pretty simple, right ? I re-wrote the implementation in C for reference (see below), note that it’s just to give you a general idea.
BcmHeapAlloc Stats Counter
The dynamic memory allocator is always keeping track of the last 20 successful allocation. To do so, the code relies on a structure present in the .data section that I called ‘heap_stats’. The structure is provided in C below:
As we can see in the excerpt below, anytime a successful allocation is made, a heap_stat element is placed into the alloc_array array. The heap_stat structure holds a reference to the allocating thread, a reference to the allocated node, and the allocated node size.
In the firmwares I have looked at so far, malloc is the only function referencing this statistics structure. It’s probably used by tracing functions when the feature is enabled via the BCM_HEAP_ALLOC_TRACE_ENABLED build flag.
Here’s the reversed free function:
Over the course of this article we identified that the Broadcom variant of eCos uses its own dynamic memory allocator named BcmHeapManager. We then relied on a mix of static and dynamic analysis to understand the backing structures and strategies implemented by this custom allocator (allocation, freeing, coalescing).
With this newly acquired knowledge, we can start investigating how we can gain exploitation primitives by abusing dynamic memory allocation issues (use-after-free, double-free, heap overflow). This will be the subject of its own dedicated article.
As always, if you have any questions, feel free to get in touch via email or Twitter.