Heap Exploitation Basics

Heap is a really nice thing :/

Chunks

Memories in heap are allocated in chunks:

low
curr -> |   prev_size*                    | 8 
        |   size        | | | PREV_INUSE  | 8 
        |   fd*                           | 8 -
        |   bw*                           | 8 | data
        /                                 /   |
next -> |   prev_size*                    |   -
        |   size        | | | PREV_INUSE  |
        /                                 / 
high
*:  Present if the previous chunk is freed.
    The data of curr uses prev_size of the next chunk!

The size field is 8 bytes, but the last 3 bits are reserved for flags.
The most important flag is bit 0: PREV_INUSE, which will be discussed later.

Now we have different types of bins/chunks.

Bin	Size	List	Merge	Number of Lists	Order
tcache	`[0x20;0x410]`	doubly-linked	❌	each size	LIFO
fastbin	`[0x20;0x80]`	singly-linked	(✅)	each size	LIFO
smallbin	`(0x80;0x400)`	doubly-linked	✅	each size	FIFO
largebin	`[0x400;0x20000)`	doubly-linked	✅	logarithmic	size-sorted
unsorted chunks	`(0x80;0x20000)`	doubly-linked	✅	one	LIFO-ish

Chunk sizes are always 0x10 aligned, and the minimum is 0x20.
We also have a special top chunk that keeps track of the heap memory!

Tcache:

most prioritized, max = 7 for each possible size!
Per-thread management structure on heap!
tcache key stored on bk pointer for double-free detection

FD Corruption (fastbin / tcache)

Let’s say we have a chunk A with size 0x20,
and somewhere in the memory we have the arena (or tcache struct) with a list pointing to B.

A ->  |   ...   | 8 
size  |   0x21  | 8 (bit 1 for PREV_INUSE)
data  /   ...   /
      /   ...   /

arena / tcache_struct:
   ->  |   &B   |

Steps:

free A, now the chunk looks like this:

A ->  |   ...   | 8 
size  |   0x21  | 8
fd    |   &B    | 8
bw    |   (tcache_key)   | 8

arena / tcache_struct:
   ->  |   &A   |

Now we overflow fd of A to 0xdeadbeef:

A ->  |   ...           | 8 
size  |   0x21          | 8
fd    |   0xDEADBEEF    | 8
bw    |   (tcache_key)  | 8

arena / tcache_struct:
bin (0x20)   ->  |   &A   |

Alloc a new chunk C with size 0x20

C ->  |   ...           | 8 
size  |   0x21          | 8
fd    |   0xDEADBEEF    | 8
bw    |   (tcache_key)  | 8

arena / tcache_struct:
bin (0x20)   ->  |   0xDEADBEEF   |

Now, if we try to alloc a new chunk with size 0x20, it will get the address from the bin and alloc a new chunk at address 0xDEADBEEF

Size Corruption

Let’s say we have two chunks A and B with size 0x20:

A ->  |   ...   | 
size  |   0x21  |
      /   ...   /
B ->  |   ...   |
size  |   0x21  |
      /   ...   /

Overflow size of A to 0x41

A ->  |   ...   | 
size  |   0x41  |
      /   ...   /
B ->  |   ...   |
size  |   0x21  |
      /   ...   /

Free A

A ->  |   ...   |  <- freed
size  |   0x41  |
      /   ...   /
B ->  |   ...   |
size  |   0x21  |
      /   ...   |

Alloc chunk C with size 0x38, now chunk B is inside C

C ->  |   ...   | -
size  |   0x41  | |
      /   ...   / | belongs to C
B ->  |   ...   | |
size  |   0x21  | |
      /   ...   | -

Note

Usually we want to alloc size chunk_size - 0x8 to allow full control of the victim chunk.

Smallbin Consolidation (WIP)

Now we want to work with smallbins.
Let’s say we have four chunks A B C D with size 0x90.

A ->  |   ...   | 
size  |   0x91  |
      /   ...   /
B ->  |   ...   |
size  |   0x91  |
      /   ...   /
C ->  |   ...   |
size  |   0x91  |
      /   ...   /
D ->  |   ...   | <- prevents consolidation with top chunk
size  |   0x91  |
      /   ...   /
top-> /   ...   /

Fill tcache, so that we are working with smallbins
Free A, (A could also be a fake chunk, as long as free() works!)
Overflow to C: PREV_INUSE = 0 and prev_size -> A
On glibc >= 2.29, overflow to A: size -> C

A ->  |   ...     | <- freed in unsorted bin
size  |   0x121   | <- size = 0x90+0x90
      /   ...     /
B ->  |   0x90    |
size  |   0x90    |
      /   ...     /
C ->  |   0x120   | <- prev_size = 0x90+0x90
size  |   0x90    |
      /   ...     /
D ->  |   ...     | 
size  |   0x91    |
      /   ...     /

Now we free C, and cause consilidation

A ->  |   ...     | -
size  |   0x121   | |
      /   ...     / |
B ->  |   ...     | |
size  |   0x90    | | freed in unsorted bin
      /   ...     / |
C ->  |   0x120   | |
size  |   0x90    | |
      /   ...     / -
D ->  |   0x1b0   |
size  |   0x91    |
      /   ...     /

Alloc chunk E with size 0x1a8

A ->  |   ...     | -
size  |   0x121   | |
      /   ...     / |
B ->  |   ...     | |
size  |   0x90    | | now chunk E
      /   ...     / |
C ->  |   0x120   | |
size  |   0x90    | |
      /   ...     / |
D ->  |   ...     | -
size  |   0x91    |
      /   ...     /