This blog post contains what I’ve learned about heap concepts and exploit techniques. I’ve gathered this knowledge after doing thorough research, using the sources mentioned below.
References:
- https://azeria-labs.com/heap-exploitation-part-1-understanding-the-glibc-heap-implementation/
- https://azeria-labs.com/heap-exploitation-part-2-glibc-heap-free-bins/
- https://ir0nstone.gitbook.io/notes/types/heap/chunks
- https://heap-exploitation.dhavalkapil.com/diving_into_glibc_heap/malloc_chunk
Introduction
Heap is an area of memory that can be dynamically allocated. In C, it is often used with functions like malloc (or similar function such as calloc, realloc, …) to request allocated space in heap and using free is used to mark the area as available
Chunks
When requesting space in the heap, the heap manager stores not only the requested size data but also the metadata, which serves to save the space size and state, along with alignment-padding bytes. The combination of metadata and user data is commonly referred to as a “chunk”
Basic chunk allocation strategies
Allocating from freed chunk: As memory gets passed back to free, the heap manager tracks these freed chunks in a series of different linked lists called “bins”. When an allocation request is made, the heap manager searches those bins for a free chunk that’s big enough to service the request. If it finds one, it can remove that chunk from the bin, mark it as “allocated”
Allocating from the top of the heap (called the “top chunk” or “remainder chunk”): the heap manager first looks at the free space at the top chunk to see if there is enough space there. If there is, the heap manager manufactures a new chunk out of this free space.
Off-heap allocations via nmap: When requesting for a large chunk (128KB-512KB on 32-bit systems or 32MB on 64 bit systems), these chunk are allocated off-head using a direct call to mmap. When these call free, the heap manager releases the entire region back to the system via munmap.
Arena and subheap: For single-threaded applications this is the only main arena that the heap manager will ever use. However, as new threads join the process, the heap manager allocates and attaches secondary arenas to each new thread. Unlike the main arena, these secondary arenas allocate chunks from one or more subheap
Allocated chunk structure:
struct malloc_chunk {
INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk, if it is free. */
INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if this chunk is free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if this chunk is free. */
struct malloc_chunk* bk_nextsize;
};
typedef struct malloc_chunk* mchunkptr;
The mchunk_prev_size stores the size of previous chunk if previous chunk is free. Otherwise, the heap saves space and mchunk_prev_size is part of the previous chunk’s user data.
The mchunk_size store the chunk size. Since chunk sizes are always 8-byte aligned (or 16-byte aligned on 64-bit systems), the low three bits of the mchunk_size are always zero. These three bits are then used to store the “A”, “M”, and “P” flags.
- P (PREV_INUSE): 0 when previous chunk is free. If the flag is set to 1, it means that the previous chunk is already in use and not available for allocation.
- M (IS_MMAPED): is used to indicate that the chunk is a huge allocation that was allocated off-heap via
mmap. The other two bits are ignored. - A (NON_MAIN_ARENA): 0 for chunks in the main arena. Each thread spawned receives its own arena and for those chunks, this bit is set.
Freed chunk structure
Free chunks store metadata stored in corresponding “free bins” that operate as linked lists. The FD and BK pointer have been added.
BINS
The heap manager needs to keep track of freed chunks so that malloc can reuse them during allocation requests. The heap manager maintains a series of lists called “bins”.
There are 5 type of bins: small bins, large bins, unsorted bin, fast bins and tcache bins. The small, large, and unsorted bins all live together in the same array
1
2
3
4
bin[0] = null
bin[1] = unsorted bin
bin[2 to 63] = small bins
bin[64 to 126] = large bins
Small bins
There are 62 small bins, each small bins stores chunks that are all the same fixed size. Every chunk less than 512 bytes (or than 1024 bytes on 64-bit systems)
Large bins
There are 63 large bins, similar to small bins, but large bins used for chunks over 512 bytes (or 1024 bytes on 64-bit systems).
Unsorted bin
The unsorted bin serves as an optimizing cache layer, taking advantage of the fact that frees often occur in clusters, followed by allocations of chunks with similar sizes. Instead of directly placing newly freed chunks into their appropriate bins, the heap manager first merges them with neighboring chunks and adds them to a general unsorted linked list.
During malloc, each item on the unsorted bin is checked to see if it “fits” the request. If it does, malloc can use it immediately. If it does not, malloc then puts the chunk into its corresponding small or large bin.
Fast bins
Similar to small bins, each fast bin is dedicated to a specific, fixed chunk size. There are a total of 10 fast bins, designed to handle chunks of size 16, 24, 32, 40, 48, 56, 64, 72, 80, and 88 bytes plus chunk metadata.
Fast bins are employed as an optimization layer, and unlike other bins, chunks in fast bins are never merged with their neighboring chunks. This behavior is due to the heap manager not setting the “P” bit at the start of the next chunk, which prevents coalescing and allows for faster and more efficient allocations and deallocations of small-sized chunks.
Tcache bins
Tcache bins is design for multithread programs.
Use-After-Free
Introduction
Use-After-Free (UAF) is a vulnerability that occurs in programming languages lacking memory safety. It happens when a pointer continues to reference a memory block that has been freed, and that same memory block is subsequently allocated again for a different purpose.
Example
For example, in C++, use malloc to allocate a 20-bytes space for storing user roles, the address of this space is stored in the variable ptr1.
Then, use free(ptr1), the heap manager will clear the data in that memory block and keeps track this freed chunk by adding it to a appropriate bin. Importantly, ptr1 still holds the memory address, as it has not been set to NULL.
Later on, allocate another 20-byte memory space to store user website information using malloc, and and the address is stored in the pointer variable ptr2. The heap manager will allocate a chunk from the previous freed chunk. At this point, both ptr1 and ptr2 reference the same memory address.
If you were to use ptr1 again within the program, you would have control over the data by modifying it via ptr2, since they now point to the same memory location.
Debugging
Let test this scenario in C++ program:
#include <iostream>
#include <string.h>
int main(int argc, char **argv)
{
std::string role_str("normal user");
std::string website_str("example.local");
char *role;
char *website;
// Allocate memory for role
role = (char *)malloc(20);
// Assign role = "normal user"
strcpy(role, role_str.c_str());
printf("[+] User role: %s\n", role);
// Releasing role
free(role);
// Allocate memory for website
website = (char *)malloc(20);
// Assign role = "normal user"
strcpy(website, website_str.c_str());
// Reuse role
printf("[+] User website: %s\n", website);
printf("[+] User role: %s", role);
}
Build then program:
1
gcc -g uaf.cpp
The output:
1
2
3
[+] User role: normal user
[+] User website: example.local
[+] User role: example.local
Let debug this vulnerable program using GDB. Begin by initiating the debugging session using GDB:
1
$ gdb ./uaf
Next, set breakpoints at critical lines that will help us analyze the use-after-free vulnerability:
1
2
3
4
5
6
pwndbg> break uaf.cpp:13
Breakpoint 1 at 0x130d: file uaf.cpp, line 13.
pwndbg> break uaf.cpp:20
Breakpoint 2 at 0x1354: file uaf.cpp, line 20.
pwndbg> break uaf.cpp:23
Breakpoint 3 at 0x1360: file uaf.cpp, line 23.
With breakpoints in place, proceed to run the program. Prior to executing line 13, the heap already contains two allocated chunks:
As you use the next command to step through the program, it will move forward without entering any functions. Upon executing the malloc function, a 32-byte (0x20 in hexadecimal) chunk is allocated by the heap manager at memory address 0x55555556b2a0 to store the role data:
Upon reaching the free command, the chunk located at 0x55555556b2a0 is marked as free and is tracked by the tcachebins:
Eventually, the program proceeds until the website variable is allocated:
Notably, the previously freed chunk at 0x55555556b2a0 has been reallocated for the “website” variable. To further investigate, we can inspect the addresses pointed to by the role and website pointers using the p (or print) command:
Remarkably, both the role and website pointers reference the same memory address. This implies that we can manipulate the role variable if it is reused without any change in its memory address. This phenomenon constitutes a use-after-free vulnerability, which we will explore and exploit further in subsequent sections.
Stay tuned as we dig deeper into the exploitation of this vulnerability and learn about potential security implications and preventive measures.