This post is part of a series, check out the others in the series here:
Fastbin'd chunks are chosen to be covered here because they work as extensions to the base malloc_chunk format used for plain old unsorted or "normal sized" heap chunks, and they offer a couple of cool tricks to try out as well! So no large chunks in this post just yet (sorry about that) - but I will give them a look once I get enough data ;) Anyway, on to fastbins!
Fastbins are reserved for small memory objects (small structs and strings). The idea is that if you are not using chunk sizes that will benefit from the usual compute overhead and accounting information; you just use a simple list of small memory regions that fit the size requested. Fastbins are according to some research present in the heap as a collection of different sizes of fast bins (so not just a single list is possible, multiple fastbins could be operating for each size group), to quote:
"Fastbin is a special design optimized for performance and cache locality. It is a single linked list similar to look aside table of Windows, in which free chunks of same size are linked in a LIFO way. Chunk size of different fastbins varies. There are [totally] 10 fastbins in an arena yet the first 7 are used by default, ranging from 16 to 64 bytes on 32-bit systems or 32 to 128 bytes on 64-bit systems" - https://loccs.sjtu.edu.cn/wiki/lib/exe/fetch.php?media=gossip:overview:ptmalloc_camera.pdf
Another caveat is that fastbins are not coalesced if they are free'd; this is again to save spinning the wheels over such small regions. There's much more about fast bins in the documentation in glibc-[version]/malloc/malloc.c is fantastic and I full suggest giving it a read through - I'd hate to blindly copy it here.
That's pretty much the opening blurb on fastbins lets get into what they look like and how they work.
The size threshold defined for fastbins defined in malloc/malloc.c: As it stands in glibc-2.23 its defined as MAX_FAST_SIZE =(SIZE_SZ*80)/4, which will evaluate to 80 bytes. So anything below 80 bytes will pretty much end up getting fast bin'd.
To provide a good example of the format; here's a chain of fastbins in memory:
I've grabbed an example screenshot here that also compares a non-fastbinned chunk, just a plain old chunk 0xb0 bytes in size (the first one allocated with a mem pointer at 0x602010) - this is to show the difference between formats a littler clearer.
On the left you see the "live" fastbin'd chunks (starting at the 0x6020b0) . Nothing really gives them away as fastbins in this state except for their sizes. On the right you will see the free'd fastbin'd chunks; a key thing to notice here is that they have a single back-pointer (forming a linked list of fastbin chunks) indicating where the next free fastbin'd chunk is.
What you will notice as well is that we definitely have the case here that fastbin'd chunks next to each other in memory are free'd; but none of the size fields overlap or rather none of the chunks are joined together. As mentioned before they will not be coalesced.
Okay so we know what they look like, lets talk about another important mechanism, the fastbin first fit.
The fastbins have a slightly different reallocation dance, they sit inside an Last In First Out (LIFO) queue when issued for reallocation. What this means is; if we were to free them one after the other in series; the first one returned for re-allocation; would be the last one free'd in the series.
In the screenshot below; the memory dump on the left shows the state of the heap just before a malloc is called and after all the fastbin chunks have been free'd. On the right is the heap after the second malloc (or reallocation) has been called. So we should essentially see which fastbin chunks get returned and used and in which order (mostly because I wrote some info into the heap chunks using the program - each allocation writes 0xAA, 0xBB into the heap in the order they are allocated in):
You should be able to pretty easily work out which chunks came back first. Also please keep in mind the pointers showing up on the free list; these 0x602yyy looking values in the heap chunks are the malloc_chunk->bk pointers.
The next question you will naturally ask is how do we make it returned a pointer we want, or how do we influence free chunks lets say, to force a certain free chunk to be returned? What happens when we overwrite this information "in flight" and then see which fastbin is returned? Well here's a recipe for testing this out:
You can also redirect the heap to a fake chunk somewhere else in a writeable-readable portion of memory. To do this the following needs to be done:
This is not a full on security exploit, but it definitely inches us closer to one. And it also introduces an important little trick for getting the heap to do reliably weird things lol.
This is pretty much it for this post, I'll covering more heap meta-data in the next post. Stay tuned!
- Introduction to ptmalloc2 internals (Part 1) - https://blog.k3170makan.com/2018/11/glibc-heap-exploitation-basics.html
- (this)
- Unsorted Bin - This is basically a list that is meant to temporarily hold any chunks that don't fit into the Fast, Large or Small bin categories. To quote some random persons paper about this:
When freeing chunks not in
the range of fastbin, they are inserted into unsorted bin at
first rather than the small bins or large bins - https://loccs.sjtu.edu.cn/wiki/lib/exe/fetch.php?media=gossip:overview:ptmalloc_camera.pdf
- Small bins - again, as with many things this is just another list or group of lists for holding a particular size of free heap chunk. The threshold may vary per architecture and glibc implementation or even build. But the basic idea is that they are larger than Fast Bins but Smaller than Large Bins. I will dig into these with fair amount of detail in future posts
- Large Bins - for chunks bigger than a maximum size, they are pretty illusive to me at the moment so I'm going to leave these out for a later post as well.
- Fast Bins - the star of the show, for all free chunks in a range of sizes below a certain maximum (more details to follow shortly!)
Fastbin'd chunks are chosen to be covered here because they work as extensions to the base malloc_chunk format used for plain old unsorted or "normal sized" heap chunks, and they offer a couple of cool tricks to try out as well! So no large chunks in this post just yet (sorry about that) - but I will give them a look once I get enough data ;) Anyway, on to fastbins!
Fast Bin Format
The fastbins are just a "chunk" yard of unloved memoryFastbins are reserved for small memory objects (small structs and strings). The idea is that if you are not using chunk sizes that will benefit from the usual compute overhead and accounting information; you just use a simple list of small memory regions that fit the size requested. Fastbins are according to some research present in the heap as a collection of different sizes of fast bins (so not just a single list is possible, multiple fastbins could be operating for each size group), to quote:
"Fastbin is a special design optimized for performance and cache locality. It is a single linked list similar to look aside table of Windows, in which free chunks of same size are linked in a LIFO way. Chunk size of different fastbins varies. There are [totally] 10 fastbins in an arena yet the first 7 are used by default, ranging from 16 to 64 bytes on 32-bit systems or 32 to 128 bytes on 64-bit systems" - https://loccs.sjtu.edu.cn/wiki/lib/exe/fetch.php?media=gossip:overview:ptmalloc_camera.pdf
Another caveat is that fastbins are not coalesced if they are free'd; this is again to save spinning the wheels over such small regions. There's much more about fast bins in the documentation in glibc-[version]/malloc/malloc.c is fantastic and I full suggest giving it a read through - I'd hate to blindly copy it here.
That's pretty much the opening blurb on fastbins lets get into what they look like and how they work.
The size threshold defined for fastbins defined in malloc/malloc.c: As it stands in glibc-2.23 its defined as MAX_FAST_SIZE =(SIZE_SZ*80)/4, which will evaluate to 80 bytes. So anything below 80 bytes will pretty much end up getting fast bin'd.
To provide a good example of the format; here's a chain of fastbins in memory:
I've grabbed an example screenshot here that also compares a non-fastbinned chunk, just a plain old chunk 0xb0 bytes in size (the first one allocated with a mem pointer at 0x602010) - this is to show the difference between formats a littler clearer.
On the left you see the "live" fastbin'd chunks (starting at the 0x6020b0) . Nothing really gives them away as fastbins in this state except for their sizes. On the right you will see the free'd fastbin'd chunks; a key thing to notice here is that they have a single back-pointer (forming a linked list of fastbin chunks) indicating where the next free fastbin'd chunk is.
What you will notice as well is that we definitely have the case here that fastbin'd chunks next to each other in memory are free'd; but none of the size fields overlap or rather none of the chunks are joined together. As mentioned before they will not be coalesced.
Okay so we know what they look like, lets talk about another important mechanism, the fastbin first fit.
Fastbin First Fit
The fastbins have a slightly different reallocation dance, they sit inside an Last In First Out (LIFO) queue when issued for reallocation. What this means is; if we were to free them one after the other in series; the first one returned for re-allocation; would be the last one free'd in the series.
In the screenshot below; the memory dump on the left shows the state of the heap just before a malloc is called and after all the fastbin chunks have been free'd. On the right is the heap after the second malloc (or reallocation) has been called. So we should essentially see which fastbin chunks get returned and used and in which order (mostly because I wrote some info into the heap chunks using the program - each allocation writes 0xAA, 0xBB into the heap in the order they are allocated in):
You should be able to pretty easily work out which chunks came back first. Also please keep in mind the pointers showing up on the free list; these 0x602yyy looking values in the heap chunks are the malloc_chunk->bk pointers.
The next question you will naturally ask is how do we make it returned a pointer we want, or how do we influence free chunks lets say, to force a certain free chunk to be returned? What happens when we overwrite this information "in flight" and then see which fastbin is returned? Well here's a recipe for testing this out:
- Free up some chunks
- Re-point the malloc_chunk->bk pointers of the fastbins
- Check out which of the available chunks get 0x4242 written into them (again this 0x4242/0x4141 stuff is purely because I'm making the program pain the heap helpfully for me)
Lets see what this looks like:
So just to explain. First I overwrite the bk pointer with the set {size_t} 0x602100 = 0x0000000000602000 command; which essentially tells the heap that after the first fast bin is returned (the first one in the LIFO at 0x6020f0) it should follow the linked list to the "next" free fastbin which is at 0x0602000.
The next screenshot shows how allocation was redirected; instead of allocating the next chunk just above the bottom most one, it jumps all the way to the top:
One can clearly see, we just redirected the heap reallocation! The linked list powers belong to us now!!
So just to explain. First I overwrite the bk pointer with the set {size_t} 0x602100 = 0x0000000000602000 command; which essentially tells the heap that after the first fast bin is returned (the first one in the LIFO at 0x6020f0) it should follow the linked list to the "next" free fastbin which is at 0x0602000.
The next screenshot shows how allocation was redirected; instead of allocating the next chunk just above the bottom most one, it jumps all the way to the top:
You can also redirect the heap to a fake chunk somewhere else in a writeable-readable portion of memory. To do this the following needs to be done:
- Free up all the fastbins
- Just before the first re-alloc; Re-point the fastbin that's going to be first fitted to your fake fastbin like so for instance: set {size_t} 0x602100 = 0x601050 (this sets the bk pointer of the chunk at 0x6020f0)
- Set the size of the fast bin to something acceptable, here I'm just recycling the same size as the one being replaced, like this: set {size_t} 0x601058 = 0x0000000000000051
This is not a full on security exploit, but it definitely inches us closer to one. And it also introduces an important little trick for getting the heap to do reliably weird things lol.
This is pretty much it for this post, I'll covering more heap meta-data in the next post. Stay tuned!
References and Reading
- Malloc.c https://fossies.org/linux/glibc/malloc/malloc.c
- "How2heap" - https://github.com/shellphish/how2heap
- https://loccs.sjtu.edu.cn/wiki/lib/exe/fetch.php?media=gossip:overview:ptmalloc_camera.pdf
- https://www.contextis.com/media/downloads/Glibc_Adventures__The_forgotten_chunks.pdf
Comments
Post a Comment