Unsorted Bin Attack

Reading time: 12 minutes

Basic Information

For more information about what is an unsorted bin check this page:

Bins & Memory Allocations

Unsorted lists are able to write the address to unsorted_chunks (av) in the bk address of the chunk. Therefore, if an attacker can modify the address of the bk pointer in a chunk inside the unsorted bin, he could be able to write that address in an arbitrary address which could be helpful to leak a Glibc addresses or bypass some defense.

So, basically, this attack allows to set a big number at an arbitrary address. This big number is an address, which could be a heap address or a Glibc address. A traditional target was global_max_fast to allow to create fast bin bins with bigger sizes (and pass from an unsorted bin attack to a fast bin attack).

• Modern note (glibc ≥ 2.39): global_max_fast became an 8‑bit global. Blindly writing a pointer there via an unsorted-bin write will clobber adjacent libc data and will not reliably raise the fastbin limit anymore. Prefer other targets or other primitives when running against glibc 2.39+. See "Modern constraints" below and consider combining with other techniques like a large bin attack or a fast bin attack once you have a stable primitive.

The code from guyinatuxedo explains it very well, although if you modify the mallocs to allocate memory big enough so don't end in a Tcache you can see that the previously mentioned error appears preventing this technique: malloc(): unsorted double linked list corrupted

How the write actually happens

• The unsorted-bin write is triggered on free when the freed chunk is inserted at the head of the unsorted list.
• During insertion, the allocator performs bck = unsorted_chunks(av); fwd = bck->fd; victim->bk = bck; victim->fd = fwd; fwd->bk = victim; bck->fd = victim;
• If you can set victim->bk to (mchunkptr)(TARGET - 0x10) before calling free(victim), the final statement will perform the write: *(TARGET) = victim.
• Later, when the allocator processes the unsorted bin, integrity checks will verify (among other things) that bck->fd == victim and victim->fd == unsorted_chunks(av) before unlinking. Because the insertion already wrote victim into bck->fd (our TARGET), these checks can be satisfied if the write succeeded.

Modern constraints (glibc ≥ 2.33)

To use unsorted‑bin writes reliably on current glibc:

• Tcache interference: for sizes that fall into tcache, frees are diverted there and won’t touch the unsorted bin. Either
  • make requests with sizes > MAX_TCACHE_SIZE (≥ 0x410 on 64‑bit by default), or
  • fill the corresponding tcache bin (7 entries) so that additional frees reach the global bins, or
  • if the environment is controllable, disable tcache (e.g., GLIBC_TUNABLES glibc.malloc.tcache_count=0).
• Integrity checks on the unsorted list: on the next allocation path that examines the unsorted bin, glibc checks (simplified):
  • bck->fd == victim and victim->fd == unsorted_chunks(av); otherwise it aborts with malloc(): unsorted double linked list corrupted.
  • This means the address you target must tolerate two writes: first *(TARGET) = victim at free‑time; later, as the chunk is removed, *(TARGET) = unsorted_chunks(av) (the allocator rewrites bck->fd back to the bin head). Choose targets where simply forcing a large non‑zero value is useful.
• Typical stable targets in modern exploits
  • Application or global state that treats "large" values as flags/limits.
  • Indirect primitives (e.g., set up for a subsequent [fast bin attack](Fast Bin Attack) or to pivot a later write‐what‐where).
  • Avoid __malloc_hook/__free_hook on new glibc: they were removed in 2.34. Avoid global_max_fast on ≥ 2.39 (see next note).
• About global_max_fast on recent glibc
  • On glibc 2.39+, global_max_fast is an 8‑bit global. The classic trick of writing a heap pointer into it (to enlarge fastbins) no longer works cleanly and is likely to corrupt adjacent allocator state. Prefer other strategies.

Minimal exploitation recipe (modern glibc)

Goal: achieve a single arbitrary write of a heap pointer to an arbitrary address using the unsorted‑bin insertion primitive, without crashing.

• Layout/grooming
  • Allocate A, B, C with sizes large enough to bypass tcache (e.g., 0x5000). C prevents consolidation with the top chunk.
• Corruption
  • Overflow from A into B’s chunk header to set B->bk = (mchunkptr)(TARGET - 0x10).
• Trigger
  • free(B). At insertion time the allocator executes bck->fd = B, therefore *(TARGET) = B.
• Continuation
  • If you plan to continue allocating and the program uses the unsorted bin, expect the allocator to later set *(TARGET) = unsorted_chunks(av). Both values are typically large and may be enough to change size/limit semantics in targets that only check for "big".

Pseudocode skeleton:

// 64-bit glibc 2.35–2.38 style layout (tcache bypass via large sizes)
void *A = malloc(0x5000);
void *B = malloc(0x5000);
void *C = malloc(0x5000); // guard

// overflow from A into B’s metadata (prev_size/size/.../bk). You must control B->bk.
*(size_t *)((char*)B - 0x8) = (size_t)(TARGET - 0x10); // write fake bk

free(B); // triggers *(TARGET) = B (unsorted-bin insertion write)

Unsorted Bin Infoleak Attack

This is actually a very basic concept. The chunks in the unsorted bin are going to have pointers. The first chunk in the unsorted bin will actually have the fd and the bk links pointing to a part of the main arena (Glibc).
Therefore, if you can put a chunk inside a unsorted bin and read it (use after free) or allocate it again without overwriting at least 1 of the pointers to then read it, you can have a Glibc info leak.

A similar attack used in this writeup, was to abuse a 4 chunks structure (A, B, C and D - D is only to prevent consolidation with top chunk) so a null byte overflow in B was used to make C indicate that B was unused. Also, in B the prev_size data was modified so the size instead of being the size of B was A+B.
Then C was deallocated, and consolidated with A+B (but B was still in used). A new chunk of size A was allocated and then the libc leaked addresses was written into B from where they were leaked.

References & Other examples

• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/unsorted_bin_attack/#hitcon-training-lab14-magic-heap
  • The goal is to overwrite a global variable with a value greater than 4869 so it's possible to get the flag and PIE is not enabled.
  • It's possible to generate chunks of arbitrary sizes and there is a heap overflow with the desired size.
  • The attack starts creating 3 chunks: chunk0 to abuse the overflow, chunk1 to be overflowed and chunk2 so top chunk doesn't consolidate the previous ones.
  • Then, chunk1 is freed and chunk0 is overflowed to the bk pointer of chunk1 points to: bk = magic - 0x10
  • Then, chunk3 is allocated with the same size as chunk1, which will trigger the unsorted bin attack and will modify the value of the global variable, making possible to get the flag.
• https://guyinatuxedo.github.io/31-unsortedbin_attack/0ctf16_zerostorage/index.html
  • The merge function is vulnerable because if both indexes passed are the same one it'll realloc on it and then free it but returning a pointer to that freed region that can be used.
  • Therefore, 2 chunks are created: chunk0 which will be merged with itself and chunk1 to prevent consolidating with the top chunk. Then, the merge function is called with chunk0 twice which will cause a use after free.
  • Then, the view function is called with index 2 (which the index of the use after free chunk), which will leak a libc address.
  • As the binary has protections to only malloc sizes bigger than global_max_fast so no fastbin is used, an unsorted bin attack is going to be used to overwrite the global variable global_max_fast.
  • Then, it's possible to call the edit function with the index 2 (the use after free pointer) and overwrite the bk pointer to point to p64(global_max_fast-0x10). Then, creating a new chunk will use the previously compromised free address (0x20) will trigger the unsorted bin attack overwriting the global_max_fast which a very big value, allowing now to create chunks in fast bins.
  • Now a fast bin attack is performed:
    • First of all it's discovered that it's possible to work with fast chunks of size 200 in the __free_hook location:

    • gef➤  p &__free_hook
      $1 = (void (**)(void *, const void *)) 0x7ff1e9e607a8 <__free_hook>
      gef➤  x/60gx 0x7ff1e9e607a8 - 0x59
      0x7ff1e9e6074f: 0x0000000000000000      0x0000000000000200
      0x7ff1e9e6075f: 0x0000000000000000      0x0000000000000000
      0x7ff1e9e6076f :      0x0000000000000000      0x0000000000000000
      0x7ff1e9e6077f <_IO_stdfile_2_lock+15>: 0x0000000000000000      0x0000000000000000
      

      • If we manage to get a fast chunk of size 0x200 in this location, it'll be possible to overwrite a function pointer that will be executed
    • For this, a new chunk of size 0xfc is created and the merged function is called with that pointer twice, this way we obtain a pointer to a freed chunk of size 0xfc*2 = 0x1f8 in the fast bin.
    • Then, the edit function is called in this chunk to modify the fd address of this fast bin to point to the previous __free_hook function.
    • Then, a chunk with size 0x1f8 is created to retrieve from the fast bin the previous useless chunk so another chunk of size 0x1f8 is created to get a fast bin chunk in the __free_hook which is overwritten with the address of system function.
    • And finally a chunk containing the string /bin/sh\x00 is freed calling the delete function, triggering the __free_hook function which points to system with /bin/sh\x00 as parameter.
  • CTF https://guyinatuxedo.github.io/33-custom_misc_heap/csaw19_traveller/index.html
    • Another example of abusing a 1B overflow to consolidate chunks in the unsorted bin and get a libc infoleak and then perform a fast bin attack to overwrite malloc hook with a one gadget address
• Robot Factory. BlackHat MEA CTF 2022
  • We can only allocate chunks of size greater than 0x100.
  • Overwrite global_max_fast using an Unsorted Bin attack (works 1/16 times due to ASLR, because we need to modify 12 bits, but we must modify 16 bits).
  • Fast Bin attack to modify the a global array of chunks. This gives an arbitrary read/write primitive, which allows to modify the GOT and set some function to point to system.

References

• Glibc malloc unsorted-bin integrity checks (example in 2.33 source): https://elixir.bootlin.com/glibc/glibc-2.33/source/malloc/malloc.c
• global_max_fast and related definitions in modern glibc (2.39): https://elixir.bootlin.com/glibc/glibc-2.39/source/malloc/malloc.c