In this post, i talk about some QuRT internals and about the userland allocator. I worked with the online available Qualcomm’s SDK top extract the binaries that implement the allocator’s logic.
Most of this logic is found in a file called libc.a which is an archive that stores .o binaries like malloc.o, free.o…etc. A quick way to extract these binaries, after downloading the SDK, is:
cp ./tools/HEXAGON_Tools/19.0.07/Tools/target/hexagon/lib/v81/libc.a /tmp/
mkdir /tmp/libc ; cd /tmp/libc ; ar xo /tmp/libc.a
And inside the /tmp/libc all the binaries will be extracted into; and from there, the disassembly and decompilation process starts.
The terms
cellandchunkare used interchangeably in the rest of this post.
A chunk has this structure:
typedef struct _Cell {
size_t _Size;
struct _Cell *_Next;
} _Cell;
The freed cells are stored in a singly-linked list :
typedef struct {
_Cell **_Plast;
_Cell *_Head;
} _Altab;
_Altab.*_Plast is used as a starting point for the allocating cells/chunks in the list; and _Altab._Head is used as a starting point for freeing cells/chunks in the list. Though, if _Altab._Plast == 0, the allocator looks in _Altab._Head instead.
Allocation Path - Malloc
So, understanding how malloc(...) allocates cells is key to understand this whole allocator’s mechanism.
malloc is defined in libc.a (./tools/HEXAGON_Tools/19.0.07/Tools/target/hexagon/lib/v81/libc.a), specifically inside malloc.o.
use
ar xo libc.atool to recover its .o files.
Using ./tools/HEXAGON_Tools/19.0.07/Tools/bin/hexagon-llvm-objdump we disassemble our target functions codes: malloc.o & free.o
$ ./tools/HEXAGON_Tools/19.0.07/Tools/bin/hexagon-llvm-objdump --mv81 --disassemble-all --demangle --reloc /tmp/libc/malloc.o
To understand to the opcodes and the Hexagon assembly, refer to https://docs.qualcomm.com/doc/80-N2040-53/80-N2040-53.pdf.
After translating the malloc function into C, let’s see step by step how it allocates a cell:
Allocation Steps:
void *malloc(size_t nbytes)
{
size_t need;
size_t ask;
_Cell *cell;
_Cell *prev;
_Cell *start;
_Cell *next;
_Cell **link;
_Locksyslock(_LOCK_MALLOC);
need = (nbytes + 15u) & ~(size_t)7u; // [1]
if (need <= nbytes) {
_Unlocksyslock(_LOCK_MALLOC);
return 0;
}
// [...]
At the very start, there’s pointer variables that will be used later; these are just my own translation of it; the real thing starts at [1] : the requested nbytes bytes is added to 15;
this is because it takes into account the two fields Size and _Next which make 8 bytes, and then the remaining +7 is used to compensate for the ~(size_t)7u which is used to make sure that the requested size is aligned to 8.
7 = 00000111, thus~7 = 11111000which is f8 is hexadecimal.
Moving onto the next step:
// [...]
for (;;) {
if (_Aldata._Plast != 0) { // [2]
link = _Aldata._Plast;
start = *link; // [2.1]
if (start != 0) {
cell = start;
if (need <= cell->_Size) {
goto found; // [2.2]
}
for (;;) {
prev = cell;
cell = cell->_Next;
if (cell == 0) {
break;
}
if (need <= cell->_Size) {
link = &prev->_Next;
goto found; // [2.3]
}
}
}
// [...]
At [2], the allocator checks first for _Aldata._Plast, the head of the allocation freelist as we said, and if it is not null, it grabs the first cell from it [2.1], and then loops and takes whichever first cell that fits the needed size; so we can think of as a first fit algorithm.
Once a cell is found at [2.2] or [2.3], it jumps to found which is the tail of the function:
found:
if (cell->_Size - need < 8) {
next = cell->_Next;
*link = next;
_Aldata._Plast = next ? &next->_Next : 0;
} else {
next = (_Cell *)((char *)cell + need);
next->_Size = cell->_Size - need;
next->_Next = cell->_Next;
*link = next;
cell->_Size = need;
_Aldata._Plast = &next->_Next;
}
_Unlocksyslock(_LOCK_MALLOC);
return (char *)cell + sizeof(_Cell);
}
This phase simply unlinks the chosen cell, and optimizes memory usage by creating a new free cell if the gap between the allocated cell’s size and the needed size is superior or equal 8.
The returned value is the cell’s pointer stripped from the header :
(char*)cell + sizeof(_Cell);.
This is not the end, because many questions arise: Q1) what if _Aldata._Plast is empty or does not contain a fitting chunk ? Q2) And how is _Aldata._Plast initialized in the first place ?
A1) If _Aldata._Plast or *_Aldata._Plast are 0, malloc switches to _Aldata._Head, and does the same looping over it.
A2) Before the first malloc, _Aldata._Plast = _Aldata._Head = 0, therefore, neither can satisfy an allocation. In this case, malloc jump to this snippet:
// [...]
ask = (_Size_block > need) ? _Size_block : need;
for (;;) {
cell = (_Cell *)_Getmem(ask); // [3]
if (cell != 0) {
break;
}
if (_Size_block <= need) {
_Unlocksyslock(_LOCK_MALLOC);
return 0;
}
ask >>= 1;
if (ask < need) {
ask = need;
}
}
free((char *)cell + sizeof(_Cell));
// [...]
At [3], it basically calls for help from _Getmem(...) which calls sys_sbrk underhood and satisfies the allocation. And so, that’s how we get many cells.
sys_sbrkforges the cell’s Size member too upon this allocation.
Freeing Path - Free:
Now that we understand malloc and the strctures around, freeing should be simple and intuitive to understand.
void free(void *ptr)
{
// [...]
if (ptr == 0) {
return;
}
cell = (_Cell *)((char *)ptr - sizeof(_Cell));
if (cell->_Size <= 7u) {
return;
}
if ((cell->_Size & 7u) != 0) {
return;
}
// [...]
free verifies first that the pointer to be freed points to a valid chunk and has valid size and alignment; if not, it simply returns.
Next up:
// [...]
next = _Aldata._Head; // <-----
if (next == 0 || cell < next) {
cell->_Next = next;
_Aldata._Head = cell;
} else {
prev = next;
next = next->_Next;
while (next != 0 && cell > next) {
prev = next;
next = next->_Next;
}
// [...]
As mentioned before, for deallocation, _Aldata._Head is used; and free loops over it until it finds the right spot. It should be noted that the freelist is sorted by the pointer address(Not by the size), so at the head of the list there’s the lowest address, and then for each free cell the address increases. So it loops while the cell to be freed has a superior address; once the right spot found, the cell is inserted back where, prev <= cell <= next. (Yeah, the = is intentional since double frees may occur ;-) ).
After a cell is freed, If its previous or next cell in the freelist are adjacent(contiguous) in memory, they are coalesced(merged) into one free cell.
A word on Exploitation
This allocator is a much more simple than the usual glibc’s ptmalloc; and for this one, there’s the excellent how2heap where it documents many techniques, that we call Houses, about heap corruption that lead to arbitrary writes; though, the more complex an implementation is, the more we can find interesting attack vectors.
For this allocator, the implementation is relatively simple, and one scenario that we can think of is the following:
- Forge a fake target cell in the stack:
char target[20];
char next[4];
*(unsigned int*)next = &next; // whatever address
// we use unsigned int(4-bytes), since the DSP has 32-bit addressing
*(unsigned int*)target = 0x20 ; // Fake size: target->size = 0x20;
*(unsigned int*)(target+4) = &next ; // Fake _Next: target->_Next = 0x20;
- Use some OOB write bug to overwrite a free cell’s
_Nextto make it point to&target:
This way, we get an arbitrary write on &target+8.
But of course, there’s many other things that can be done to make the allocator behave as we want to certain degree.
Here is the gist for the decompiled code: https://gist.github.com/MohandAcherir/4baecf91c4a5734299477bc572281e7a