Let's continue with our second technique
the Fastbin Dup, or duplication. Beginning with some more malloc internals.
Something malloc does very efficiently is recycle unused heap memory
and this is achieved by the second of malloc's functions we're going to explore:
free(). free() is another simple function,
you pass it a pointer to a chunk that you no longer need
and then you can forget about it,
safe in the knowledge that it will be recycled
if and when is necessary.
From malloc's perspective however, the unused chunk is linked into one of several free lists which
are, as they sound,
lists of free chunks. Of particular interest to us are a collection of these free lists known as the
fastbins. Fast because the chunks in these lists are recycled fast and bins because that's what the
malloc maintainers call lists, at least when they're not calling them buckets.
The fastbins are just a small collection of singly linked non-circular free lists that each hold free
chunks of a specific size.
And to help us visualize how the fastbins operate
we're going to debug another small demo binary.
Navigate to the fastbin_dup directory and once again load the demo binary into GDB.
Use the 'set context-sections
code' command again to minimize noise.
Set a breakpoint on the main() function and run the program.
The source panel shows us that the first thing this binary does is request three minimum sized chunks.
We can pass the number of lines we want to execute as an argument to the 'next' command,
so 'next 3' will make those requests.
Then the 'vis' command shows us that the heap looks exactly as we'd expect it to,
with three minimum sized chunks, A, B and C, respectively.
The source panel shows us that this program will now use the free() function to recycle these chunks in
the same order that they were requested. Before it does that
let's check the fastbins with the 'fastbins' command.
The output reveals that there are seven fastbins, each responsible for holding free chunks with sizes
between 0x20 and 0x80.
Although there are more fastbins than this
these are the ones used under default conditions.
The null to the right of each bin indicates that it's currently empty.
Let's use the 'next' command to free chunk A, followed by 'vis' and 'fastbins' to see what's changed.
We can see that chunk A has been linked into the 0x20 fastbin, recall that malloc addresses chunks
by their metadata rather than their user data.
The 'vis' command has also annotated the same information here.
But where is pwndbg getting this information from?
There is no clear indication on the heap that anything has changed.
This brings us to arenas.
Arenas are structures in which malloc keeps all of its non-inline metadata, consisting primarily of the
heads of each of those free lists I mentioned. A single arena can administrate multiple heaps and a
new arena is created along with an initial heap
every time a thread uses malloc for the first time, up to a limit based on the number of available cores.
The main thread gets a special arena called the main arena, which resides in the libc data section.
And it's the main arena that pwndbg is getting its current information from.
pwndbg does have some arena inspection commands, but we're just going to use 'dq' to dump the
first 20 quadwords of the main arena,
the symbol for which is main_arena.
Compare what we're seeing here to the arena layout diagram in the PDF.
This is the top chunk pointer,
it keeps track of the address of an arena's top chunk,
we were indirectly manipulating this in the House of Force technique.
These are the heads of some of the other bins that we haven't covered yet.
And this is the head of the 0x20 fastbin, which currently holds the address of chunk A.
Whenever a chunk that falls into fastbin range is freed, its address is written to the head of the
appropriate fastbin in that heap's arena.
If we freed a 0x30-sized chunk, its address would be written here, a 0x40-sized chunk
here, et cetera.
Now let's use the 'next' command to free chunk
B, followed by 'vis' and 'fastbins'.
We can see that the 0x20 fastbin now holds two chunks, B and A, also annotated here. But arenas
only have one fastbin slot per size, which by reusing our
'dq' command, we can see is now occupied by the address of chunk B. The remaining metadata of the
0x20 fastbin is stored inline and we can see that the first quadword of chunk B's user data has been
repurposed as a forward pointer or fd, not to be confused with file descriptors. Chunk B's fd points
to chunk A and chunk A's
fd is null, indicating the end of the list.
Chunk user data can be repurposed like this because chunks are only supposed to be freed when no longer
in use by the program.
Freeing chunk C with 'next', followed by 'vis', 'fastbins' and our 'dq' command shows us that the process
repeats whenever a chunk of the same size is freed.
Chunk C is now the first chunk in the 0x20 fastbin, with its address written into the 0x20
fastbin slot in the main arena.
The first quadword of chunk C's user data has been repurposed as an fd, which points to chunk
B, chunk B's fd points to chunk A and chunk A's fd is null, indicating the end of the list.
Note that the prev_inuse flags belonging to chunks B and C are still set, despite their previous chunks
not being in use.
The fastbins are the exception to the prev_inuse rule and we'll see why that is in a later technique.
For now, just understand that we won't expect to see any clear prev_inuse flags quite yet, despite
dealing with free chunks.
Here's a simplified visualization of what's just happened, with our three 0x20-sized chunks on
the heap and the main arena elsewhere in memory.
When chunk A was freed, its fd became null and its address was written into the 0x20 fastbin
slot in the main arena.
Then Chunk B was freed,
its fd adopted a pointer to chunk A and chunk B's address was written into the 0x20 fastbin slot.
Finally, when chunk C was freed, it's fd adopted a pointer to chunk B and chunk C's address
was written into the 0x20 fastbin slot.
Another way to visualize the fastbins is as a collection of stacks, the stack pointers for which are
held in an arena.
Every time a 0x20-sized chunk is freed, for example, it's added to the top of the 0x20 stack.
The stack analogy is appropriate because fastbins are last in, first out or LIFO structures, meaning
that the next request for a 0x20 chunk will pop, or allocate, the chunk at the top of the 0x20
fastbin stack.
We can confirm this behavior by issuing the 'next 3' command, which executes three further requests
for minimum sized chunks, labelling them D, E and F, respectively.
We can use 'print d', 'print e' and 'print f' to confirm that malloc allocated the last chunk to be freed,
chunk C, followed by chunk B, then chunk A, effectively popping them off the top of the 0x20 fastbin
stack, rather than using more memory from the top chunk.
And that's how the fastbins work.
To summarize, they're a collection of singly linked, non-circular free lists that each hold free chunks
of a specific size, from 0x20 through 0x80 under default conditions.
They're last in, first out structures, meaning they operate just like a stack.
The head of each fastbin list resides in an arena, but the remaining links between chunks in a fastbin
are stored inline on the heap.
When a request is made, if it's in fastbin size range, malloc will search the appropriate
fastbin before attempting to allocate from the top chunk.
If you want to refresh your knowledge on the fastbins
take a look at the "fastbins" title under the "Arenas" section of the PDF.
You can also check out the "malloc flowchart" section
if you want to better understand the order in which bins are searched during allocation.
Now that we've got an understanding of the fastbins, we can move on to our second vulnerable binary
and start learning about the fastbin dup technique.