# Pwn - heap basics
# overview
Some background information on ```glibc``` heap implementations.
The overview of memory layout is shown in the figure below:
<center style="font-size:14px;color:#C0C0C0;text-decoration:underline">Credit to ctf-wiki</center>
Heaps are essentially memory segments. The programs that are in charge of heap management are called **heap manager**, which lies in the middle of Kernel Mode and User Mode. They
1. respond to users' memory allocation/free requests (e.g., ```malloc```, ```free```) and interact with operating systems (e.g., ```sbrk```, ```mmap```)
2. manage the freed memorie space, also known as **chunks** (e.g., ```bins```, ```arena```)
## chunk
Whether chunks are in use or not, their structure are the same. For the chunks that are in use, the chunk stores the payload after the chunk header (previous chunk size and chunk size).
```
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
chunk-> | Size of previous chunk, if unallocated (P clear) | \
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ header
| Size of chunk, in bytes |A|M|P| /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
mem-> | User data starts here... .
. .
. (malloc_usable_size() bytes) .
. |
next +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
chunk-> | (size of chunk, but used for chunk's data) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of next chunk, in bytes |A|0|1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
```
For the chunks that are freed, the chunk stores pointers that points to the previous/next freed chunk in the form of a double linked list.
```
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
chunk-> | Size of previous chunk, if unallocated (P clear) | \
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ header
| Size of chunk, in bytes |A|0|P| /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
mem-> | Forward pointer to next chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Back pointer to previous chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unused space (may be 0 bytes long) .
. .
. |
next +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
chunk-> | Size of chunk, in bytes |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of next chunk, in bytes |A|0|0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
```
The size of chunks are aligned to ```2*size_t```. The ```header: size of previous chunk``` actually **overlaps** with the previous chunk:
- If the previous chunk is in use, this session stores the data of previous chunk.
- If the previous chunk is not in use, this session stores the size of the previous chunk.
## bins
Heap manager manages idel chunks by bins. Bins are sorted into 5 categories according to their sizes and status of use: 1) fast bin, 2) small bin, 3) large bin, 4) unsorted bin, 5) tcache (added after glibc version 2.26)
The small bins, large bins and unsorted bins are maintained in the same array, which is stored in ```malloc_state```. **Physically consecutive free chunks in fast bins are not allowed.** The bins in the array are:
| index | description |chunks size in bins, $s1=512$ (32-bit) or $s1=1024$ (64-bit)|
|:---------:|:-----------:|--------------------------------------------------------------|
| 1 |unsorted bin |> $88$ bytes (maximum fast bin chunk) |
| 2 |small bin |$2*\text{sizeof(size_t)}*2$ |
| n |small bin |$2*\text{sizeof(size_t)}*n$ |
| 63 |small bin |$2*\text{sizeof(size_t)}*63$ |
| 64 |large bin (1)|$\big[s1, \ s1+2^{6}*1\big)$ |
| n |large bin |$\big[s1+2^{6}*(n-64), \ s1+2^{6}*(n-63)\big)$ |
| 95 (64+31)|large bin |$\big[s1+2^{6}*31, \ s1+2^{6}*32\big)$ |
| 96 |large bin (2)|$\big[s1+2048, \ s1+2048+2^{9}*1\big)$ |
| n |large bin |$\big[s1+2048+2^{9}*(n-96), \ s1+2048+2^{9}*(n-95)\big)$ |
|111 (96+15)|large bin |$\big[s1+2048+2^{9}*15, \ s1+2048+2^{9}*16\big)$ |
| 112 |large bin (3)|$\big[s1+10240, \ s1+10240+2^{12}*1\big)$ |
| n |large bin |$\big[s1+10240+2^{12}*(n-112), \ s1+10240+2^{12}*(n-112)\big)$|
|119 (112+7)|large bin |$\big[s1+10240+2^{12}*7, \ s1+10240+2^{12}*8\big)$ |
| 120 |large bin (4)|$\big[s1+43008, \ s1+43008+2^{15}*1\big)$ |
| n |large bin |$\big[s1+43008+2^{15}*(n-120), \ s1+43008+2^{15}*(n-119)\big)$|
|123 (120+3)|large bin |$\big[s1+43008+2^{15}*3, \ \text{s1}+43008+2^{15}*4\big)$ |
| 124 |large bin (5)|$\big[s1+174080, \ s1+174080+2^{18}*1\big)$ |
| 125 |large bin |$\big[s1+174080+2^{18}*1, \ s1+174080+2^{18}*2\big)$ |
| 126 |large bin (6)|$\big[s1+698368, \ \text{unlimited}\big)$ |
In ```pwndbg```, command ``bins`` checks the status of bins.
### small bins
There are 62 small bins, maintained by a single linked list in a **FIFO** manner. The chunks in small bins are of the same size.
### large bins
The number of large bins is 63. They are classified into 6 groups. The common difference between groups are the same, the chunks in the same bin have same range of size.
| group | number of bins | common difference |
| :---: | :------------: | :----------------: |
| 1 | 32 | $2^{6}$ |
| 2 | 16 | $2^{9}$ |
| 3 | 8 | $2^{12}$ |
| 4 | 4 | $2^{15}$ |
| 5 | 2 | $2^{18}$ |
| 6 | 1 | $\text{unlimited}$ |
The schematic is as follows:
<center style="font-size:14px;color:#C0C0C0;text-decoration:underline">Credit to wiki.wgpsec.org</center>
### unsorted bin
Chunks (not adjacent to top chunk, not belong to fast bin) are stored in the unsorted bin temporarily before they are assigned to the bin they belong to according to their sizes.
The traversal order of unsorted bin is **FIFO**.
### fast bins
There are 10 fast bins, maintained by a single linked list in a **LIFO** manner. The chunks in fast bins are of the same size. The 10 fast bins have chunks of sizes $16, 24, ..., 88 \ (0\text{x}10-0\text{x}58)$.
**Physically consecutive free chunks in fast bins are allowed.** Only when ```malloc_consolidate(av)``` is called, the chunks in fast bins will be consolidated and put into unsorted bins (then might be put into small/large bins consequently). Note that since it is merged into the unsorted bin, we can sometimes use it to leak out the libc base address. Examples for fast bin consolidation are available at [this blog](https://bbs.kanxue.com/thread-257742.htm).
### tcache
Thread Local Caching creates cache for each thread. Tcache acts like bins. The data structure used are ```tcache_entry``` and ```tcache_perthread_struct```.
```c
typedef struct tcache_entry{
struct tcache_entry *next;
} tcache_entry;
typedef struct tcache_perthread_struct{
char counts[TCACHE_MAX_BINS];
tcache_entry *entries[TCACHE_MAX_BINS]; // TCACHE_MAX_BINS = 64
} tcache_perthread_struct;
```
```tcache_entry``` has a pointer that points to chunks. ```tcache_perthread_struct``` controls the entire tcache structure, where ```entries``` stores the chunks in a list and ```counts``` stores the number of chunks in the lists. **Physically consecutive free chunks in fast bins are not allowed.**
With tcache mechanism, each time a heap is allocated, a chunk of size $\text{0x250}$ (```ALIGN(sizeof(tcache_perthread_struct)+sizeof(size_t), 2*sizeof(size_t))```) will be allocated, at the head of the heap.
Many security checks are omitted in tcache, leading to more vulnerabilities.
## top chunk
Top chunk refers to the chunk with the largest physical address. When program calls ```malloc()``` for the first time, heap will be divided into 2 part, one for the user, and the other one is the top chunk.
**```prev_inuse``` bit is always 1.**
## last remainder
When ```when malloc()``` is called, the returned chunk might not be the same size of the requested size. Then the chunk will be partitioned into 2 parts, one for the user, and the other one is the remainder.
## arena
Each thread has an arena to manage the heap (not necessarily independent arenas). Main arena is the one in charge of the main process. The data structure of arena is ```malloc_state```. **```malloc_state``` of main arena is a global variable stored in the ```.data``` segment of libc**, which means that by leaking main arena, we can get the address of ```libc_base```.
```c
struct malloc_state {
/* Serialize access. */
__libc_lock_define(, mutex);
/* Flags (formerly in max_fast). */
int flags;
/* Fastbins */
mfastbinptr fastbinsY[ NFASTBINS ];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;
/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[ NBINS * 2 - 2 ];
/* Bitmap of bins, help to speed up the process of determinating if a given bin is definitely empty.*/
unsigned int binmap[ BINMAPSIZE ];
/* Linked list, points to the next arena */
struct malloc_state *next;
/* Linked list for free arenas. Access to this field is serialized
by free_list_lock in arena.c. */
struct malloc_state *next_free;
/* Number of threads attached to this arena. 0 if the arena is on
the free list. Access to this field is serialized by
free_list_lock in arena.c. */
INTERNAL_SIZE_T attached_threads;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};
```
In ```pwndbg```, command ```arena [addr]``` checks the status of arena.
# workflow
## malloc
```
void *malloc(size_t size)
```
Requests memory and returns a pointer that points to the allocated memory segment.
When ```malloc(size)``` is called, the size of the returned chunk is ```ALIGN(size+sizeof(size_t), 2*sizeof(size_t))```, which is the size of requested bytes plus the size of header (previous chunk size and chunk size). For example, for 64-bit ELF:
- ```malloc(0x18)``` will produce a chunk of size ```0x20```, where ```0x18``` bytes for data and ```0x10``` bytes for header (8 bytes overlapped).
- ```malloc(0x20)``` will produce a chunk of size ```0x30```, where ```0x20``` bytes for data and ```0x10``` bytes for header.
When ```malloc()``` is called, the heap manager will
1. Calculate the chunk_size, check if fast bins contain free chunks of this size and can be allocated
2. If 1) did not allocate chunk, check if chunk_size is in small bin, if so, allocate this chunk
3. If 2) did not allocate chunk, **consolidate the chunks in fast bins and put to unsorted bin**. Scan the chunk in unsorted bin in **FIFO** way:
- If chunk_size is in small bin, and current chunk in unsorted bin can be allocated, then allocate and return
- If not, put assign current chunk in unsorted bin to the corresponding bin according to its size
4. If 3) did not allocate chunk, search in large bins to see if any chunk can be assigned
- If any chunk fit exactly, allocate the chunk directly
- If not, split the chunk and allocate. Assign the remaining chunk as ```last_remainder```
5. If 4) did not allocate chunk, check if top_chunk can be allocated
6. If 5) did not allocate chunk, **consolidate the chunks in fast bins and put to unsorted bin** and check if the arena is main arena:
- If the arena is main arena, use ```sbrk()``` to enlarge the top chunk and allocate
- If not, check if ```chunk_size >= mmap_threashold```:
- If ```chunk_size >= mmap_threashold```, use ```mmap()``` to map memory to this chunk
- If not, use ```mmap()``` to enlarge the top chunk and allocate
Source code and more detailed illustration could be found at [ctf-wiki](https://ctf-wiki.org/pwn/linux/user-mode/heap/ptmalloc2/implementation/malloc/).
## free
```
void free(void *ptr)
```
Free the memory allocated. In heap structure, the freed chunk will be put into **bins** according to their sizes.
When ```free()``` is called, the heap manager will:
1. Check the pointer (valid address? aligned? invalid size?), and check if the memory is allocated by ```mmap()```. If so, free the pointer by ```munmap()```
2. If not freed by 1), check if ```chunk_size <= max_fast```:
- If ```chunk_size <= max_fast```, and if chunk is adjacent to top chunk, then put chunk into fast bins
3. If not freed by 2), try to coalesce with the previous and next chunks, if next chunk can be coalesced:
- If next chunk is top chunk, merge current chunk to top chunk
- Otherwise, coalesce with the next chunk and put it into unsorted bin
4. If not freed by 3), check if ```chunk_size > FASTBIN_CONSOLIDATION_THRESHOLD```:
- If so, **coalesce the chunks in fast bins and put them into unsorted bin**. If ```top chunk > mmap_threshold```, return part of the top chunk to OS
# References
- [ctf-wiki](https://ctf-wiki.org/)
- [Workflow of malloc/free](https://blog.csdn.net/zhang14916/article/details/108319252)
- [heap basic](https://wiki.wgpsec.org/knowledge/ctf/basicheap.html)
- [fast bin consolidation](https://bbs.kanxue.com/thread-257742.htm)
- [tcache bin](https://blog.csdn.net/A951860555/article/details/115442780)
Sign in with Wallet
Connect another wallet