The glibc heap: chunks, bins, and the four bugs that matter

You can spot a heap challenge before you open the binary: it is a menu. Add a note, edit a note, delete a note, view a note, exit. That menu is an allocator API with the safety removed, and the whole challenge is deciding which of malloc, free, read and printf the author forgot to constrain.

This post covers the glibc allocator specifically, because that is what Linux CTF binaries link against. The version matters enormously - the exploit that works on 2.27 fails on 2.32 - and the first thing to do with any heap binary is find out which libc it ships. The stack overflow post covers getting a shell once you have a write primitive; this one is about getting the primitive.

What a chunk looks like

malloc does not hand you a bare buffer. It hands you a pointer into the middle of a structure that carries its own metadata inline, immediately before the data:

           +------------------+
  -0x10    | prev_size        |   only meaningful if the previous chunk is free
  -0x08    | size | A | M | P |   size, plus three flag bits in the low 3
   0x00    | -- your pointer  |   <- what malloc returned
           | data ...         |
           +------------------+

When free, the first two words of the data area are reused:
   0x00    | fd  (next in bin) |
   0x08    | bk  (prev in bin) |

Two consequences do most of the damage. First, the metadata is adjacent to attacker data, so an overflow of one chunk lands directly on the next chunk's size field. Second, a freed chunk stores allocator pointers inside the region the program still has a pointer to, so a use-after-free read leaks heap addresses and a use-after-free write corrupts the allocator's linked lists.

The bins, in the order malloc checks them

Bug 1: use after free

The program frees a chunk and keeps the pointer. Everything follows from that.

• Read after free leaks the fd/bk the allocator wrote into the chunk - a heap pointer from tcache, a libc pointer from the unsorted bin. This is usually how you defeat ASLR and PIE.
• Write after free lets you edit the fd pointer of a chunk sitting in the tcache. That is tcache poisoning, below.
• Type confusion is the higher-level version: free a note struct, allocate a different kind of object that lands in the same chunk, and now one type's fields are read through the other's accessors. A function pointer in the second object overlapping an attacker-controlled string in the first is game over.

The tell in the source or the decompiler is a free(ptr) with no following ptr = NULL, and a bounds check on the index that permits an already-freed slot.

Bug 2: tcache poisoning, the modern default

tcache is a per-thread cache of recently freed chunks, added in glibc 2.26 for speed. It is a singly linked list and, until 2.29, it validated essentially nothing. Poisoning it is the shortest path from a heap write to an arbitrary write:

# Two chunks in the tcache: A -> B -> NULL
free(A); free(B)

# Overwrite B's fd (via UAF or an overflow from A) with the target address.
edit(B, p64(target))            # tcache is now  B -> target -> ...

malloc(size)                    # returns B
ptr = malloc(size)              # returns *target* - malloc handed us the address
write(ptr, payload)             # arbitrary write, wherever we pointed

What changed, version by version

• 2.26-2.28: no checks at all. The snippet above works verbatim.
• 2.29: a key field is added to the chunk so a double free into the same tcache bin is detected. Clear or corrupt the key and it works again.
• 2.32: fd pointers are mangled - stored as (chunk_addr >> 12) ^ fd. You now need a heap leak to compute the value to write. Also note the target must be 16-byte aligned.
• 2.34: __malloc_hook and __free_hook are removed. The classic "overwrite a hook with system" ending no longer exists and you move to FSOP or the exit handlers.

Bug 3: double free

Freeing the same chunk twice puts it in a bin twice, so malloc will hand the same address to two different logical objects - which is a use-after-free you created yourself. The classic fastbin variant needs a chunk in between to dodge the top-of-bin check:

free(A); free(B); free(A)       # fastbin: A -> B -> A -> ...
                                # (the direct free(A); free(A) is caught)
X = malloc(sz)                  # X == A
edit(X, p64(target))            # writing to X edits A's fd, still in the bin
malloc(sz); malloc(sz)          # B, then A again
ptr = malloc(sz)                # target

In tcache the equivalent is even simpler on glibc before 2.29 - free(A); free(A) is accepted outright and the bin becomes a cycle. From 2.29 the key field blocks it, unless you can overwrite the key, which a one-byte overflow from the previous chunk often lets you do.

Bug 4: the off-by-one, and chunk consolidation

A single byte written past the end of a chunk lands on the low byte of the next chunk's size field. That is enough for two well-known techniques.

• Poison null byte. Writing \x00 clears the PREV_INUSE bit and shrinks the size. free then believes the previous chunk is free and consolidates backwards using a prev_size you control - producing a chunk that overlaps chunks the program still thinks are live. Overlapping chunks are the strongest primitive on the heap: one object's data is another object's metadata.
• Size extension. Writing a larger low byte makes the allocator think the next chunk is bigger than it is, so a later allocation of that size overlaps the chunk after it. Same outcome, different direction.

Both are really the same insight: the allocator navigates the heap by walking size fields, and if you control a size field you control where it thinks the chunks are.

From arbitrary write to a shell

The write primitive is the middle of the challenge, not the end. What you overwrite depends on the libc and the binary's mitigations:

A one_gadget is a single address in libc that execs /bin/sh, subject to register or stack constraints printed by the tool of the same name. Try them in order; the constraints are usually about a register being null at the call site, and which of your primitives you use determines which one holds.

How to approach one of these

1. Enumerate the menu. For each option write down what it calls: which allocations, which frees, which reads, and with what size. That table is the exploit's alphabet.
2. Find the bug in that table. Missing null after free, index off by one, size read separately from size allocated, edit permitted on a freed slot.
3. Check the mitigations and the libc version. checksec for the binary, the libc string for the allocator.
4. Get a heap leak. Free a small chunk and read it back.
5. Get a libc leak. Free a chunk larger than 0x408 so it lands in the unsorted bin, and read it back.
6. Build the primitive. Tcache poisoning if you can, overlapping chunks if you cannot.
7. Pick a target from the table above, matched to the libc version.
8. Debug in gdb with a heap-aware plugin. heap bins and heap chunks after every step. Guessing the bin state is how these exploits fail.

The last point is the practical one. Heap exploitation is not conceptually hard, but it is unforgiving of bookkeeping errors, and a plugin that prints the bins after each operation converts an afternoon of confusion into a sequence of obvious steps.