In this post and the others in this series, I will unpack some of the internals to glibc's dynamic heap data structures and associated beasts. This post specifically will start you off with no background insight on the heap (perhaps a little on ELF internals and debugging), and detail some experiments you can perform to learn how the heap works.
Introduction
The Heap is essentially a list of memory regions an executing program uses to store data. The data stored in heap regions are requested during runtime. It allows runtime environments like glibc to offer programs dynamic memory for allocating data. So because this offer's memory regions as kind of a "service" (this is what it is for - giving out memory regions), it must mean some where in this whole mess, there needs to be some accounting information about the memory regions. To this aid; the heap describes or decorates user data regions with an internal structure called a chunk. Chunks are in turn classified and grouped according to their properties - basically properties like:
- whether they are available for use,
- how big they are,
- and which chunks are around them in the list and other wonderful things.
The heap allocator I will focus on here is glibc version ptmalloc as implemented in versions glibc 2.23-2.28. But this of course not to say that only glibc is important to understand; there exists multiple approaches to heap allocation. Each approach is unique down to how they achieve various operations; like coalescing free chunks, sorting and searching free chunks and grouping them rapidly, as well as amongst perhaps even more things - security improvements. So there's a number of places that complexity can breed and fester into security problems. But the root of these problems will often be in how users requesting data, and the allocator managing data respond to meta-data about memory regions.
To close the introduction, Heap can often seem very intense and complex and have very gnarly internals, but most of which; aid memorization and other computer science that serves to speed up searching linked lists. Another way you can say this is that; they are nothing more than elaborate ways to store some "cheat" meta-data that doesn't require searching the whole heap memory area for stuff every time. But the meta-data is interesting to us because there are instances when we want to influence the way the list is searched and interpreted.
Heap speak
The basic unit of currency for the heap as you would have guessed is a chunk. We probably want to know what these look like in glibc code, so here ya go:
I should give each field its fair explanation (well as fair as I can be to it):
- INTERNAL_SIZE_T - is something I should probably explain, this is a size type, for the fields that define "bookeeping" functions in the heap management - stuff like pointers (addresses) and bit fields. This size definition that is left to be implementation defined. We can imagine that glibc would want to be portable and flexible across different hardware's and runtime implementations - so address sizes mapped to INTERNAL_SIZE_T can (but I don't think often do) vary. Anyway, the INTERNAL_SIZE_T is defined to be size_t - which falls back onto how ever your C runtime originally solved the problem.
- mchunk_prev_size - is the very first part of a chunk format and this is used whether its a free or used chunk. This field indicates the size of the chunk just before this one, and its least significant bit is set to 0x1 if the chunk referred to, is free. So if you are looking at a chunk, and its prev_size has a least sig bit of 0x1, just before this is a chunk that is still "alive".
- mchunk_size - pretty standard, actually just holds the current size in bytes lol.
- struct malloc_chunk* fd - so this is a field in the chunk struct defining a space for an address to another chunk. This is because it forms a linked list. This linked list being defined here is the "free list", which snaps together all the chunks that are free on the heap. Here we are defining the "forward pointer" in the linked list.
- struct malloc_chunk *bk - you guess it, this the same type as the previously mentioned field, we are here just talking about the "backward pointer".
- struct malloc_chunk *fd_nextsize - so this field is from another layer of free listing tech in the heap. This pointer is added to a free chunk if its above a certain size threshold (we will cover this later on) - so that the heap manager can track huge chunks should they appear. Its kinda like being a high roller in a casino, when you come out they track your movements and wants even more intensely because you affect the profitability of the evening more.
I know its a bit long winded you can totally skip over the other mallocs and free's if you don't want to go through each one. I added them here to give my examples and reversing some more interesting data.
In the code above I've added a simple make shift "wrapper" function (my friend Galen gave me this idea) and injected a break point just before the last return. This so that I can isolate the free and malloc calls effects on the memory regions we are studying.
And now lets see what happens to the heap as it allocates memory. We need to find a pointer to the heap first. This is pretty easy since malloc will save it in rax after returning back to the main function, I show this in the first few gdb commands:
So as I have it set up the hook-stop will just spit out everything around $rax-0x10 which is the address where the chunk header information will be saved. I do this because; when we hit this break point malloc will have just returned at set the register to its return value - which will be the address of the memory region allocated. We can see directly how these macros operate on heap metadata data in glibc/malloc/malloc.c:
So as you can see its a simple addition or subtraction of 2 addresses to get the mem (raw memory pointer to where user data starts) or the chunk information starting two addresses before. There are a number of other operations that extract and set other meta-data.
Okay so that's the basic format pretty much covered lets look at how this looks in action.
Growing heap the natural way
After the first break point hits you should see gdb display the first heap chunk allocated, here's an annotated version of that dump showing the heap format:
Now after this hits your screen, try executing the "c" gdb command to skip to the next break point. You will get a couple more examples of allocated chunks until you see the following on your screen:
This is essentially showing that we can't use the value in $rax as before in the hook-stop. As you would guess this is because $rax does not hold the memory pointer anymore, its now embroiled in a free call so it hold some other value. Anyway, we can dump the chunk using the address passed to the free_string function since it is conveniently displayed here for us. This is what the chunk looks like after it was free'd:
What is shown in the screen dump above in addition to the free chunk is where the first free chunks fd (free list forward) and bk (free list backward) pointers go. We can see here if we follow them using gdb's memory examiner functions they eventually end up at 0x602a00 which is the top chunk's address; the pointer to the top of the currently allocated heap addresses.
Okay so that's what a chunk looks like when its allocated and free'd, can we have a look at how chunks are coalesced into bigger free chunks? Yes that's what the next section is for!
Free Chunk Coalescence
After allocating the chunks, our program will free up each one in the same order they were allocated in. Now what this means is that we can expect two chunks allocated next to each other; to be free'd right after each other as well - and as a result we will have two chunks that get melded into one.Here's what that looks like:
What we can see on the left of the screen dump; is the two chunks (named chunk 1, and chunk 2) at addresses 0x602580 and 0x6024a0. On the right we have the new coalesced chunk at 0x6024a0 of course, but this time we can see that the size field after coalescing is 0x211 (which as indicated is simply 0xe1 + 0x130).
This is pretty much all there is to this coalescing action really. And thats pretty much all I have for this post, I'll continue this series by moving onto fast-bins, large chunk management and potentially some heap redirection tricks. Stay tuned for the next one folks!
References and Reading
Check out the following to see some inspiration for this post and more awesome things to find out about the heap works.
- https://sourceware.org/glibc/wiki/MallocInternals
- http://phrack.org/issues/66/10.html
- http://www.phrack.org/issues/68/13.html
- https://github.com/shellphish/how2heap
- https://www.blackhat.com/presentations/bh-usa-07/Ferguson/Whitepaper/bh-usa-07-ferguson-WP.pdf
- 2007 BlackHat Vegas V82 Ferguson Understanding the Heap 00 - https://www.youtube.com/watch?v=VLnhV1T5Ng4
- The Heap: what does malloc() do? - (bin 0x14) - https://www.youtube.com/watch?v=ZHghwsTRyzQ
- ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps
- https://www.cs.tufts.edu/~nr/cs257/archive/paul-wilson/fragmentation.pdf
- https://www.blackhat.com/docs/eu-17/materials/eu-17-Heelan-Heap-Layout-Optimisation-For-Exploitation-wp.pdf
- http://g.oswego.edu/dl/html/malloc.html
- https://fossies.org/linux/glibc/malloc/malloc.c
Comments
Post a Comment