First Fit

Reading time: 4 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 vinaongezwa mbele ( "head"). Wakati unahitaji kipande kipya cha kumbukumbu, mtoaji anatazama bin isiyo na mpangilio kutoka nyuma ( "tail") ili kupata kipande ambacho ni kikubwa vya kutosha. Ikiwa kipande kutoka kwenye bin isiyo na mpangilio ni kikubwa kuliko unavyohitaji, kinagawanywa, huku sehemu ya mbele ikirudishwa na sehemu iliyobaki ikibaki kwenye bin.

Mfano:

• Unapotoa 300 bytes (a), kisha 250 bytes (b), 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 kuacha zingine kwenye bin.
• c itakuwa ikielekeza kwenye a ya awali na kujazwa na a's.

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 itavuta kutoka kichwa cha fastbin.

Mfano:

• Unapoweka vipande vinne vya byte 20 kila kimoja (a, b, c, d).
• Unapofungua kwa mpangilio wowote, vipande vilivyofunguliwa vinaongezwa kwenye kichwa cha fastbin.
• Ikiwa kisha unahitaji kipande cha byte 20, allocator itarudisha kipande kilichofunguliwa hivi karibuni kutoka kichwa cha 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

Mreferensi Mengine & Mifano

• 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 upya nafasi ya user->password 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 taarifa za noti katika malloc(8) (ikiwa na kiashiria kwa kazi inayoweza kuitwa) na kiashiria kwa malloc(<size>) nyingine yenye maudhui ya noti.
• Shambulio litakuwa kuunda noti 2 (note0 na note1) zikiwa na maudhui makubwa ya malloc kuliko saizi ya taarifa 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 noti1 ili kuita kiashiria kipya cha kazi.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• Inawezekana kugawa kumbukumbu, kuandika thamani inayotakiwa, kuachilia, kuigawa tena na kwa kuwa data ya awali bado ipo, itatendewa 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 ni cha kwanza kinachotolewa (hata baada ya kuachilia kwa nguvu yote). Kila kipande kipya kinachotolewa kina nambari yake katika orodha ya kiashiria. Kisha, toa vipande 4 (+ kile kilichotolewa awali), cha mwisho kitakuwa na 4 ndani yake, kiache na kulazimisha kuigawa tena kwa cha kwanza, ambacho kitatumia kipande cha mwisho kilichoachiliwa ambacho ni kile chenye 4 ndani yake.