First Fit

Reading time: 8 minutes

First Fit

Όταν απελευθερώνετε μνήμη σε ένα πρόγραμμα χρησιμοποιώντας glibc, χρησιμοποιούνται διαφορετικά "bins" για τη διαχείριση των κομματιών μνήμης. Ακολουθεί μια απλοποιημένη εξήγηση δύο κοινών σεναρίων: unsorted bins και fastbins.

Unsorted Bins

Όταν απελευθερώνετε ένα κομμάτι μνήμης που δεν είναι γρήγορο κομμάτι, πηγαίνει στο unsorted bin. Αυτό το bin λειτουργεί σαν μια λίστα όπου τα νέα απελευθερωμένα κομμάτια προστίθενται στην αρχή (την "κεφαλή"). Όταν ζητάτε ένα νέο κομμάτι μνήμης, ο αλγόριθμος αναθέσεων κοιτάζει το unsorted bin από το πίσω μέρος (την "ουρά") για να βρει ένα κομμάτι που είναι αρκετά μεγάλο. Αν ένα κομμάτι από το unsorted bin είναι μεγαλύτερο από αυτό που χρειάζεστε, χωρίζεται, με το μπροστινό μέρος να επιστρέφεται και το υπόλοιπο να παραμένει στο bin.

Παράδειγμα:

• Αποδεσμεύετε 300 bytes (a), στη συνέχεια 250 bytes (b), στη συνέχεια απελευθερώνετε a και ζητάτε ξανά 250 bytes (c).
• Όταν απελευθερώνετε a, πηγαίνει στο unsorted bin.
• Αν ζητήσετε ξανά 250 bytes, ο αλγόριθμος αναθέσεων βρίσκει το a στην ουρά και το χωρίζει, επιστρέφοντας το μέρος που ταιριάζει με το αίτημά σας και κρατώντας το υπόλοιπο στο bin.
• Το c θα δείχνει στο προηγούμενο a και θα είναι γεμάτο με τα περιεχόμενα του a.

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

Fastbins

Τα Fastbins χρησιμοποιούνται για μικρές μνήμες. Σε αντίθεση με τα unsorted bins, τα fastbins προσθέτουν νέα κομμάτια στην κεφαλή, δημιουργώντας μια συμπεριφορά last-in-first-out (LIFO). Εάν ζητήσετε ένα μικρό κομμάτι μνήμης, ο allocator θα τραβήξει από την κεφαλή του fastbin.

Example:

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

🔥 Σύγχρονες εκτιμήσεις glibc (tcache ≥ 2.26)

Από την glibc 2.26, κάθε νήμα διατηρεί το δικό του tcache που ερωτάται πριν από το unsorted bin. Επομένως, ένα σενάριο first-fit θα φτάσει μόνο αν:

1. Το ζητούμενο μέγεθος είναι μεγαλύτερο από το tcache_max (0x420 σε 64-bit από προεπιλογή), ή
2. Ο αντίστοιχος tcache bin είναι ήδη γεμάτος ή έχει αδειάσει χειροκίνητα (με την εκχώρηση 7 στοιχείων και τη διατήρησή τους σε χρήση).

Σε πραγματικές εκμεταλλεύσεις, συνήθως θα προσθέσετε μια βοηθητική ρουτίνα όπως:

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

Μόλις εξαντληθεί το tcache, οι επόμενες απελευθερώσεις πηγαίνουν στο unsorted bin και μπορεί να ενεργοποιηθεί ξανά η κλασική συμπεριφορά first-fit (αναζήτηση ουράς, εισαγωγή κεφαλής).

🚩 Δημιουργία ενός overlapping-chunk UAF με first-fit

Το παρακάτω απόσπασμα (δοκιμασμένο σε glibc 2.38) δείχνει πώς μπορεί να καταχραστεί ο διαχωριστής στο unsorted bin για να δημιουργήσει 2 overlapping pointers – μια ισχυρή πρωτοβουλία που μετατρέπει μια μόνο απελευθέρωση σε 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. Use after free: Δημιουργήστε ένα αντικείμενο χρήστη, απελευθερώστε το, δημιουργήστε ένα αντικείμενο που θα πάρει το απελευθερωμένο κομμάτι και επιτρέψτε να γράψει σε αυτό, επικαλύπτοντας τη θέση του user->password από το προηγούμενο. Επαναχρησιμοποιήστε τον χρήστη για να παρακάμψετε τον έλεγχο κωδικού πρόσβασης
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• Το πρόγραμμα επιτρέπει τη δημιουργία σημειώσεων. Μια σημείωση θα έχει τις πληροφορίες της σημείωσης σε μια malloc(8) (με έναν δείκτη σε μια συνάρτηση που θα μπορούσε να κληθεί) και έναν δείκτη σε άλλη malloc() με το περιεχόμενο της σημείωσης.
• Η επίθεση θα ήταν να δημιουργηθούν 2 σημειώσεις (note0 και note1) με μεγαλύτερο περιεχόμενο malloc από το μέγεθος των πληροφοριών της σημείωσης και στη συνέχεια να απελευθερωθούν ώστε να μπουν στο γρήγορο bin (ή tcache).
• Στη συνέχεια, δημιουργήστε μια άλλη σημείωση (note2) με μέγεθος περιεχομένου 8. Το περιεχόμενο θα είναι στη note1 καθώς το κομμάτι θα επαναχρησιμοποιηθεί, όπου θα μπορούσαμε να τροποποιήσουμε τον δείκτη συνάρτησης ώστε να δείχνει στη συνάρτηση win και στη συνέχεια να χρησιμοποιήσουμε το Use-After-Free στη note1 για να καλέσουμε τον νέο δείκτη συνάρτησης.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• Είναι δυνατόν να δεσμεύσετε κάποια μνήμη, να γράψετε την επιθυμητή τιμή, να την απελευθερώσετε, να την επαναδεσμεύσετε και καθώς τα προηγούμενα δεδομένα είναι ακόμα εκεί, θα αντιμετωπιστούν σύμφωνα με τη νέα αναμενόμενη δομή στο κομμάτι, καθιστώντας δυνατή την ρύθμιση της τιμής για να αποκτήσετε τη σημαία.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• Σε αυτή την περίπτωση, είναι απαραίτητο να γράψετε 4 μέσα σε ένα συγκεκριμένο κομμάτι που είναι το πρώτο που δεσμεύεται (ακόμα και μετά την αναγκαστική απελευθέρωση όλων τους). Σε κάθε νέο δεσμευμένο κομμάτι, ο αριθμός του αποθηκεύεται στον δείκτη του πίνακα. Στη συνέχεια, δεσμεύστε 4 κομμάτια (+ το αρχικά δεσμευμένο), το τελευταίο θα έχει 4 μέσα του, απελευθερώστε τα και αναγκάστε την επαναδέσμευση του πρώτου, το οποίο θα χρησιμοποιήσει το τελευταίο κομμάτι που απελευθερώθηκε, το οποίο είναι αυτό με 4 μέσα του.
• 2024 HITCON Quals Setjmp write-up (Quarkslab) – πρακτική επίθεση πρώτης εφαρμογής / υπερκάλυψης μη ταξινομημένων: https://ctftime.org/writeup/39355
• Angstrom CTF 2024 heapify write-up – εκμετάλλευση της διαίρεσης μη ταξινομημένων για να διαρρεύσει τη libc και να αποκτήσει υπερκάλυψη: https://hackmd.io/@aneii11/H1S2snV40