First Fit

Reading time: 8 minutes

First Fit

Quando si libera memoria in un programma utilizzando glibc, vengono utilizzati diversi "bins" per gestire i chunk di memoria. Ecco una spiegazione semplificata di due scenari comuni: unsorted bins e fastbins.

Unsorted Bins

Quando si libera un chunk di memoria che non è un fast chunk, va nell'unsorted bin. Questo bin funge da lista in cui i nuovi chunk liberati vengono aggiunti all'inizio (la "testa"). Quando si richiede un nuovo chunk di memoria, l'allocatore guarda l'unsorted bin dalla parte posteriore (la "coda") per trovare un chunk abbastanza grande. Se un chunk dell'unsorted bin è più grande di quanto necessario, viene diviso, con la parte anteriore restituita e la parte rimanente che rimane nel bin.

Esempio:

• Si allocano 300 byte (a), poi 250 byte (b), poi si libera a e si richiedono di nuovo 250 byte (c).
• Quando si libera a, va nell'unsorted bin.
• Se poi si richiedono di nuovo 250 byte, l'allocatore trova a alla coda e lo divide, restituendo la parte che soddisfa la richiesta e mantenendo il resto nel bin.
• c punterà al precedente a e sarà riempito con i contenuti di a.

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

Fastbins

I fastbins sono utilizzati per piccoli chunk di memoria. A differenza degli unsorted bins, i fastbins aggiungono nuovi chunk all'inizio, creando un comportamento last-in-first-out (LIFO). Se richiedi un piccolo chunk di memoria, l'allocatore preleverà dalla testa del fastbin.

Esempio:

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

🔥 Considerazioni moderne su glibc (tcache ≥ 2.26)

Dalla glibc 2.26, ogni thread mantiene il proprio tcache che viene interrogato prima del bin non ordinato. Pertanto, uno scenario di first-fit sarà raggiunto solo se:

1. La dimensione richiesta è maggiore di tcache_max (0x420 su 64-bit per impostazione predefinita), oppure
2. Il corrispondente bin tcache è già pieno o svuotato manualmente (allocando 7 elementi e mantenendoli in uso).

Negli exploit reali di solito aggiungerai una routine di supporto come:

// 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]);

Una volta che il tcache è esaurito, le liberazioni successive vanno al bin non ordinato e il comportamento classico del first-fit (ricerca dalla coda, inserimento nella testa) può essere attivato di nuovo.

🚩 Creazione di un UAF con chunk sovrapposti utilizzando first-fit

Il frammento qui sotto (testato su glibc 2.38) mostra come lo splitter nel bin non ordinato può essere abusato per creare 2 puntatori sovrapposti – un potente primitivo che converte una singola liberazione in una scrittura dopo la liberazione.

#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
}

Ricetta di sfruttamento (comune nei recenti CTF):

1. Svuota il tcache per la dimensione target.
2. Libera un chunk in modo che finisca nel bin non ordinato.
3. Alloca una dimensione leggermente più piccola – l'allocatore divide il chunk non ordinato.
4. Alloca di nuovo – la parte rimanente si sovrappone con un chunk esistente in uso → UAF.
5. Sovrascrivi campi sensibili (puntatori a funzioni, vtable di FILE, ecc.)

Un'applicazione pratica può essere trovata nella sfida Setjmp delle HITCON Quals 2024 dove questo esatto primitivo è usato per passare da un UAF a un controllo completo di __free_hook.

🛡️ Mitigazioni & Indurimento

• Safe-linking (glibc ≥ 2.32) protegge solo le liste tcache/fastbin a collegamento singolo. I bin non ordinati/piccoli/grandi memorizzano ancora puntatori raw, quindi sovrapposizioni basate su first-fit rimangono valide se riesci a ottenere una leak dell'heap.
• Crittografia dei puntatori dell'heap & MTE (ARM64) non influenzano ancora glibc x86-64, ma i flag di indurimento delle distribuzioni come GLIBC_TUNABLES=glibc.malloc.check=3 abortiranno su metadati inconsistenti e possono rompere PoC naïve.
• Riempimento del tcache alla liberazione (proposto nel 2024 per glibc 2.41) ridurrebbe ulteriormente l'uso non ordinato; monitora le future versioni durante lo sviluppo di exploit generici.

Altre Riferimenti & Esempi

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Use after free: Genera un oggetto utente, liberalo, genera un oggetto che ottiene il chunk liberato e consenti di scriverci, sovrascrivendo la posizione di user->password del precedente. Riutilizza l'utente per bypassare il controllo della password
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• Il programma consente di creare note. Una nota avrà le informazioni della nota in un malloc(8) (con un puntatore a una funzione che potrebbe essere chiamata) e un puntatore a un altro malloc() con i contenuti della nota.
• L'attacco consisterebbe nel creare 2 note (note0 e note1) con contenuti malloc più grandi della dimensione delle informazioni della nota e poi liberarle in modo che finiscano nel fast bin (o tcache).
• Poi, crea un'altra nota (note2) con una dimensione del contenuto di 8. Il contenuto andrà in note1 poiché il chunk verrà riutilizzato, dove potremmo modificare il puntatore della funzione per puntare alla funzione win e poi Use-After-Free la note1 per chiamare il nuovo puntatore della funzione.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• È possibile allocare della memoria, scrivere il valore desiderato, liberarlo, riallocarlo e poiché i dati precedenti sono ancora lì, verrà trattato secondo la nuova struttura prevista nel chunk rendendo possibile impostare il valore per ottenere il flag.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• In questo caso è necessario scrivere 4 all'interno di un chunk specifico che è il primo ad essere allocato (anche dopo aver forzato la liberazione di tutti). In ogni nuovo chunk allocato, il suo numero nell'indice dell'array è memorizzato. Poi, allocare 4 chunk (+ quello inizialmente allocato), l'ultimo avrà 4 al suo interno, liberali e forzare la riallocazione del primo, che utilizzerà l'ultimo chunk liberato che è quello con 4 al suo interno.
• 2024 HITCON Quals Setjmp write-up (Quarkslab) – attacco pratico di sovrapposizione first-fit / unsorted-split: https://ctftime.org/writeup/39355
• Angstrom CTF 2024 heapify write-up – abuso della divisione del bin non ordinato per leak libc e ottenere sovrapposizione: https://hackmd.io/@aneii11/H1S2snV40