First Fit

Reading time: 4 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's.

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.

Παράδειγμα:

• Εσείς κατανέμετε τέσσερα κομμάτια των 20 bytes το καθένα (a, b, c, d).
• Όταν τα απελευθερώσετε με οποιαδήποτε σειρά, τα απελευθερωμένα κομμάτια προστίθενται στην κεφαλή του fastbin.
• Αν στη συνέχεια ζητήσετε ένα κομμάτι 20 bytes, ο allocator θα επιστρέψει το πιο πρόσφατα απελευθερωμένο κομμάτι από την κεφαλή του fastbin.

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

Άλλες Αναφορές & Παραδείγματα

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Χρήση μετά την απελευθέρωση: Δημιουργήστε ένα αντικείμενο χρήστη, απελευθερώστε το, δημιουργήστε ένα αντικείμενο που θα πάρει το απελευθερωμένο κομμάτι και επιτρέψτε να γραφτεί σε αυτό, επικαλύπτοντας τη θέση του user->password από το προηγούμενο. Επαναχρησιμοποιήστε τον χρήστη για να παρακάμψετε τον έλεγχο κωδικού πρόσβασης
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• Το πρόγραμμα επιτρέπει τη δημιουργία σημειώσεων. Μια σημείωση θα έχει τις πληροφορίες της σημείωσης σε μια malloc(8) (με έναν δείκτη σε μια συνάρτηση που θα μπορούσε να κληθεί) και έναν δείκτη σε άλλη malloc(<size>) με το περιεχόμενο της σημείωσης.
• Η επίθεση θα ήταν να δημιουργηθούν 2 σημειώσεις (note0 και note1) με μεγαλύτερο περιεχόμενο malloc από το μέγεθος των πληροφοριών της σημείωσης και στη συνέχεια να απελευθερωθούν ώστε να μπουν στο γρήγορο bin (ή tcache).
• Στη συνέχεια, δημιουργήστε μια άλλη σημείωση (note2) με μέγεθος περιεχομένου 8. Το περιεχόμενο θα είναι στη note1 καθώς το κομμάτι θα επαναχρησιμοποιηθεί, όπου θα μπορούσαμε να τροποποιήσουμε τον δείκτη συνάρτησης ώστε να δείχνει στη συνάρτηση win και στη συνέχεια να χρησιμοποιήσουμε την Χρήση-Μετά-Απελευθέρωση της 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 μέσα του.