First Fit

Reading time: 7 minutes

First Fit

Wakati unachomoa kumbukumbu katika programu ukitumia glibc, "bins" tofauti zinatumika kusimamia vipande vya kumbukumbu. Hapa kuna maelezo rahisi ya hali mbili za kawaida: bins zisizo na mpangilio na fastbins.

Bins Zisizo na Mpangilio

Wakati unachomoa kipande cha kumbukumbu ambacho si kipande cha haraka, kinaenda kwenye bin isiyo na mpangilio. Bin hii inafanya kazi kama orodha ambapo vipande vipya vilivyotolewa vinapowekwa mbele (the "head"). Wakati unahitaji kipande kipya cha kumbukumbu, mtoaji anatazama bin isiyo na mpangilio kutoka nyuma (the "tail") ili kupata kipande ambacho ni kikubwa vya kutosha. Ikiwa kipande kutoka kwenye bin isiyo na mpangilio ni kikubwa kuliko unavyohitaji, kinagawanywa, ambapo sehemu ya mbele inarudishwa na sehemu iliyobaki inabaki kwenye bin.

Mfano:

• Unapoweka 300 bytes (a), kisha 250 bytes (b), kisha unachomoa a na kuomba tena 250 bytes (c).
• Wakati unachomoa a, inaenda kwenye bin isiyo na mpangilio.
• Ikiwa kisha unahitaji 250 bytes tena, mtoaji anapata a kwenye tail na kuigawanya, akirudisha sehemu inayofaa ombi lako na kuweka zingine kwenye bin.
• c itakuwa ikielekeza kwenye a ya awali na kujazwa na maudhui ya a.

char *a = malloc(300);
char *b = malloc(250);
free(a);
char *c = malloc(250);

Fastbins

Fastbins zinatumika kwa vipande vidogo vya kumbukumbu. Tofauti na unsorted bins, fastbins zinaongeza vipande vipya kwenye kichwa, na kuunda tabia ya last-in-first-out (LIFO). Ikiwa unahitaji kipande kidogo cha kumbukumbu, allocator atavuta kutoka kwenye kichwa cha fastbin.

Mfano:

char *a = malloc(20);
char *b = malloc(20);
char *c = malloc(20);
char *d = malloc(20);
free(a);
free(b);
free(c);
free(d);
a = malloc(20);   // d
b = malloc(20);   // c
c = malloc(20);   // b
d = malloc(20);   // a

🔥 Mambo ya kisasa ya glibc (tcache ≥ 2.26)

Tangu glibc 2.26 kila thread inashikilia tcache yake ambayo inachunguzwa kabla ya bin isiyo na mpangilio. Hivyo basi, hali ya first-fit itafikiwa tu ikiwa:

1. Ukubwa ulioombwa ni kubwa kuliko tcache_max (0x420 kwenye 64-bit kwa chaguo-msingi), au
2. Bin inayohusiana ya tcache tayari imejaa au kutolewa kwa mikono (kwa kugawa vipengele 7 na kuviweka katika matumizi).

Katika mashambulizi halisi, kwa kawaida utaongeza utaratibu wa msaada kama:

// Drain the tcache for a given size
for(int i = 0; i < 7; i++) pool[i] = malloc(0x100);
for(int i = 0; i < 7; i++) free(pool[i]);

Once the tcache is exhausted, subsequent frees go to the unsorted bin and classic first-fit behaviour (tail search, head insertion) can be triggered again.

🚩 Kuunda UAF ya kipande kinachoshirikiana na first-fit

The fragment below (tested on glibc 2.38) shows how the splitter in the unsorted bin can be abused to create 2 overlapping pointers – a powerful primitive that converts a single free into a write-after-free.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
setbuf(stdout, NULL);

/* 1. prepare 2 adjacent chunks and free the first one */
char *A = malloc(0x420);   // big enough to bypass tcache
char *B = malloc(0x420);
strcpy(A, "AAAA\n");
free(A);                   // A → unsorted

/* 2. request a *smaller* size to force a split of A */
char *C = malloc(0x400);   // returns lower half of former A

/* 3. The remainder of A is still in the unsorted bin.
Another 0x400-byte malloc will now return the *same*
region pointed to by B – creating a UAF/overlap. */
char *C2 = malloc(0x400);

printf("B  = %p\nC2 = %p (overlaps B)\n", B, C2);

// Arbitrary write in B is immediately visible via C2
memset(B, 'X', 0x10);
fwrite(C2, 1, 0x10, stdout);  // prints Xs
}

Exploitation recipe (common in recent CTFs):

1. Drain the tcache for the target size.
2. Free a chunk so it lands in the unsorted bin.
3. Allocate a slightly smaller size – the allocator splits the unsorted chunk.
4. Allocate again – the leftover part overlaps with an existing in-use chunk → UAF.
5. Overwrite sensitive fields (function pointers, FILE vtable, etc.)

A practical application can be found in the 2024 HITCON Quals Setjmp challenge where this exact primitive is used to pivot from a UAF to full control of __free_hook.

🛡️ Mitigations & Hardening

• Safe-linking (glibc ≥ 2.32) only protects the singly-linked tcache/fastbin lists. The unsorted/small/large bins still store raw pointers, so first-fit based overlaps remain viable if you can obtain a heap leak.
• Heap pointer encryption & MTE (ARM64) do not affect x86-64 glibc yet, but distro hardening flags such as GLIBC_TUNABLES=glibc.malloc.check=3 will abort on inconsistent metadata and can break naïve PoCs.
• Filling tcache on free (proposed in 2024 for glibc 2.41) would further reduce unsorted usage; monitor future releases when developing generic exploits.

Other References & Examples

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Tumia baada ya kuachiliwa: Tengeneza kitu cha mtumiaji, kiache, tengeneza kitu kinachopata kipande kilichoachiliwa na ruhusu kuandika ndani yake, kuandika nafasi ya mtumiaji->nenosiri kutoka kwa ile ya awali. Tumia tena mtumiaji ili kupita ukaguzi wa nenosiri
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• Programu inaruhusu kuunda noti. Noti itakuwa na habari za noti katika malloc(8) (ikiwa na kiashiria kwa kazi inayoweza kuitwa) na kiashiria kwa malloc nyingine () yenye maudhui ya noti.
• Shambulio litakuwa kuunda noti 2 (note0 na note1) zikiwa na maudhui makubwa ya malloc kuliko saizi ya habari za noti na kisha kuziachilia ili ziingie kwenye fast bin (au tcache).
• Kisha, tengeneza noti nyingine (note2) yenye saizi ya maudhui 8. Maudhui yatakuwa katika note1 kwani kipande kitarejelewa, ambapo tunaweza kubadilisha kiashiria cha kazi ili kiashirie kazi ya ushindi na kisha Tumia-Baada-ya-Kuachiliwa note1 ili kuita kiashiria kipya cha kazi.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• Inawezekana kutenga kumbukumbu, kuandika thamani inayotakiwa, kuachilia, kuirejesha na kwa kuwa data ya awali bado ipo, itachukuliwa kulingana na muundo mpya unaotarajiwa katika kipande, hivyo kufanya iwezekane kuweka thamani ili kupata bendera.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• Katika kesi hii inahitajika kuandika 4 ndani ya kipande maalum ambacho ndicho cha kwanza kinachotengwa (hata baada ya kuachilia kwa nguvu yote). Kila kipande kipya kinachotengwa nambari yake katika orodha ya index inahifadhiwa. Kisha, tengeneza vipande 4 (+ ile iliyotengwa awali), ya mwisho itakuwa na 4 ndani yake, ziache na kulazimisha urejeleaji wa cha kwanza, ambacho kitatumia kipande cha mwisho kilichooachiliwa ambacho ndicho chenye 4 ndani yake.
• 2024 HITCON Quals Setjmp write-up (Quarkslab) – shambulio la vitendo la first-fit / unsorted-split overlap: https://ctftime.org/writeup/39355
• Angstrom CTF 2024 heapify write-up – kutumia kugawanya unsorted-bin ili kuvuja libc na kupata overlap: https://hackmd.io/@aneii11/H1S2snV40