Heap

Misingi ya Heap

Heap ni mahali ambapo programu itaweza kuhifadhi data wakati inahitaji data kwa kuita kazi kama vile malloc, calloc... Zaidi ya hayo, wakati kumbukumbu hii haifai tena, inapatikana kwa kuita kazi free.

Kama inavyoonekana, iko baada ya ambapo binary inapakiwa kwenye kumbukumbu (angalia sehemu ya [heap]):

Ugawaji wa Kipande Msingi

Wakati data fulani inahitajika kuhifadhiwa kwenye heap, sehemu ya heap inatengwa kwa hiyo. Sehemu hii itakuwa ya benki na tu data iliyohitajika + nafasi ya vichwa vya benki + kisawe cha ukubwa wa benki kitahifadhiwa kwa kipande. lengo ni kuweka kumbukumbu kama ndogo iwezekanavyo bila kufanya iwe ngumu kujua wapi kila kipande kipo. Kwa hili, habari ya kipande cha metadata hutumiwa kujua wapi kila kipande kilichotumiwa/cha bure kipo.

Kuna njia tofauti za kutenga nafasi hasa ikitegemea benki iliyotumiwa, lakini njia ya jumla ni kama ifuatavyo:

  • Programu inaanza kwa kuomba kiasi fulani cha kumbukumbu.

  • Ikiwa kwenye orodha ya vipande kuna mtu anayeweza kutosha kutosheleza ombi, itatumika

  • Hii inaweza hata maanisha sehemu ya kipande kinachopatikana kitatumika kwa ombi hili na sehemu iliyobaki itaongezwa kwenye orodha ya vipande

  • Ikiwa hakuna kipande kinachopatikana kwenye orodha lakini bado kuna nafasi katika kumbukumbu iliyotengwa, meneja wa heap anaunda kipande kipya

  • Ikiwa hakuna nafasi ya kutosha ya heap kutenga kipande kipya, meneja wa heap anauliza kernel kupanua kumbukumbu iliyotengwa kwa heap na kisha kutumia kumbukumbu hii kuunda kipande kipya

  • Ikiwa kila kitu kinafeli, malloc inarudisha null.

Tambua kwamba ikiwa kumbukumbu inayohitajika inapita kizingiti, mmap itatumika kutafuta kumbukumbu iliyohitajika.

Maeneo

Katika maombi ya multithreaded, meneja wa heap lazima azuie hali za mbio ambazo zinaweza kusababisha ajali. Awali, hii ilifanywa kwa kutumia mutex ya ulimwengu kuhakikisha kwamba thread moja tu inaweza kupata heap kwa wakati mmoja, lakini hii ilisababisha matatizo ya utendaji kutokana na kizuizi kilichosababishwa na mutex.

Kushughulikia hili, mpangilio wa heap wa ptmalloc2 uliingiza "maeneo," ambapo kila eneo hufanya kazi kama heap tofauti na muundo wake wa data na mutex, kuruhusu nyuzi nyingi kufanya shughuli za heap bila kuingiliana, ikiwa wanatumia maeneo tofauti.

Eneo la "kuu" la msingi linashughulikia shughuli za heap kwa maombi ya nyuzi moja. Wakati nyuzi mpya zinaongezwa, meneja wa heap huwapa maeneo ya pili kupunguza mzozo. Kwanza inajaribu kuambatisha kila nyuzi mpya kwenye eneo lisilotumiwa, kuunda maeneo mapya ikihitajika, hadi kufikia kikomo cha mara 2 ya viingilio vya CPU kwa mifumo ya biti 32 na mara 8 kwa mifumo ya biti 64. Mara kikomo kinapofikiwa, nyuzi lazima washiriki maeneo, ikiongoza kwa mzozo wa uwezekano.

Tofauti na eneo kuu, ambalo linapanuka kwa kutumia wito wa mfumo wa brk, maeneo ya pili hujenga "subheaps" kwa kutumia mmap na mprotect kusimuliza tabia ya heap, kuruhusu mabadiliko katika kusimamia kumbukumbu kwa shughuli za multithreaded.

Subheaps

Subheaps hutumika kama akiba ya kumbukumbu kwa maeneo ya pili katika maombi ya multithreaded, kuruhusu kuongezeka na kusimamia maeneo yao ya heap kando na heap kuu. Hapa kuna jinsi subheaps zinavyotofautiana na heap ya awali na jinsi wanavyofanya kazi:

  1. Heap ya Awali vs. Subheaps:

  • Heap ya awali iko moja kwa moja baada ya binary ya programu kwenye kumbukumbu, na inapanuka kwa kutumia wito wa mfumo wa sbrk.

  • Subheaps, zinazotumiwa na maeneo ya pili, hujengwa kupitia mmap, wito wa mfumo unaopanga eneo maalum la kumbukumbu.

  1. Akiba ya Kumbukumbu na mmap:

  • Meneja wa heap anapounda subheap, inahifadhi kipande kikubwa cha kumbukumbu kupitia mmap. Akiba hii haialoishi kumbukumbu mara moja; inaashiria tu eneo ambalo michakato au alokesheni zingine za mfumo hazipaswi kutumia.

  • Kwa chaguo-msingi, ukubwa uliohifadhiwa kwa subheap ni 1 MB kwa michakato ya biti 32 na 64 MB kwa michakato ya biti 64.

  1. Upanuzi wa Hatua kwa Hatua na mprotect:

  • Eneo la kumbukumbu lililohifadhiwa awali linawekwa kama PROT_NONE, ikionyesha kwamba kernel hahitaji kutenga kumbukumbu ya kimwili kwa nafasi hii bado.

  • Ili "kukuza" subheap, meneja wa heap hutumia mprotect kubadilisha ruhusa za ukurasa kutoka PROT_NONE hadi PROT_READ | PROT_WRITE, kuchochea kernel kutenga kumbukumbu ya kimwili kwa anwani zilizohifadhiwa hapo awali. Hatua hii kwa hatua inaruhusu subheap kuongezeka kama inavyohitajika.

  • Mara subheap nzima inapomalizika, meneja wa heap hujenga subheap mpya kuendelea na kutenga.

malloc_state

Kila heap (eneno kuu au maeneo ya nyuzi nyingine) ina muundo wa malloc_state. Ni muhimu kugundua kwamba muundo wa malloc_state wa eneo kuu ni variable ya ulimwengu katika libc (hivyo iko katika nafasi ya kumbukumbu ya libc). Katika kesi ya muundo wa malloc_state wa heaps ya nyuzi, ziko ndani ya "heap" ya nyuzi yenyewe.

Kuna mambo ya kuvutia kutoka kwa muundo huu (angalia msimbo wa C hapa chini):

  • mchunkptr bins[NBINS * 2 - 2]; ina pointa kwa vipande vya kwanza na mwisho vya benki ndogo, kubwa na zisizoainishwa (kwa sababu -2 ni kwa sababu index 0 haikutumiwa)

  • Kwa hivyo, kipande cha kwanza cha benki hizi kitakuwa na pointa ya nyuma kwa muundo huu na kipande cha mwisho cha benki hizi kitakuwa na pointa ya mbele kwa muundo huu. Hii kimsingi inamaanisha kwamba ikiwa unaweza kuvuja anwani hizi katika eneo kuu utakuwa na pointa kwa muundo katika libc.

  • Miundo struct malloc_state *next; na struct malloc_state *next_free; ni orodha zilizounganishwa za maeneo

  • Kipande cha top ni "kipande" cha mwisho, ambacho kimsingi ni nafasi yote iliyobaki ya heap. Mara kipande cha juu kinapokuwa "tupu", heap imekamilika kutumika na inahitaji kuomba nafasi zaidi.

  • Kipande cha last reminder kinatokana na hali ambapo kipande cha saizi kamili haipatikani na kwa hivyo kipande kikubwa zaidi kinagawanywa, sehemu iliyobaki inawekwa hapa.

// From https://heap-exploitation.dhavalkapil.com/diving_into_glibc_heap/malloc_state
struct malloc_state
{
/* Serialize access.  */
__libc_lock_define (, mutex);
/* Flags (formerly in max_fast).  */
int flags;

/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;
/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];

/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];

/* Linked list */
struct malloc_state *next;
/* Linked list for free arenas.  Access to this field is serialized
by free_list_lock in arena.c.  */
struct malloc_state *next_free;
/* Number of threads attached to this arena.  0 if the arena is on
the free list.  Access to this field is serialized by
free_list_lock in arena.c.  */

INTERNAL_SIZE_T attached_threads;
/* Memory allocated from the system in this arena.  */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};

typedef struct malloc_state *mstate;

malloc_chunk

Muundo huu unawakilisha kipande maalum cha kumbukumbu. Maeneo mbalimbali yana maana tofauti kwa vipande vilivyotengwa na visivyotengwa.

// From https://heap-exploitation.dhavalkapil.com/diving_into_glibc_heap/malloc_chunk
struct malloc_chunk {
INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk, if it is free. */
INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */
struct malloc_chunk* fd;                /* double links -- used only if this chunk is free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size.  */
struct malloc_chunk* fd_nextsize; /* double links -- used only if this chunk is free. */
struct malloc_chunk* bk_nextsize;
};

typedef struct malloc_chunk* mchunkptr;

Kama ilivyotajwa hapo awali, vipande hivi pia vina baadhi ya metadata, vinaonyeshwa vizuri katika picha hii:

Metadata kawaida ni 0x08B ikionyesha ukubwa wa vipande wa sasa kwa kutumia biti za mwisho 3 kueleza:

  • A: Ikiwa ni 1 inatoka kwenye subheap, ikiwa ni 0 iko kwenye uwanja mkuu

  • M: Ikiwa ni 1, kipande hiki ni sehemu ya nafasi iliyotengwa na mmap na sio sehemu ya kitalu

  • P: Ikiwa ni 1, kipande kilichotangulia kina matumizi

Kisha, nafasi kwa data ya mtumiaji, na mwishowe 0x08B kuonyesha ukubwa wa kipande kilichotangulia wakati kipande kinapatikana (au kuhifadhi data ya mtumiaji wakati inatengwa).

Zaidi ya hayo, wakati inapatikana, data ya mtumiaji hutumiwa pia kuhifadhi baadhi ya data:

  • Kiashiria kwa kipande kifuatacho

  • Kiashiria kwa kipande kilichotangulia

  • Ukubwa wa kipande kifuatacho kwenye orodha

  • Ukubwa wa kipande kilichotangulia kwenye orodha

Tambua jinsi ya kuweka orodha hii huzuia haja ya kuwa na safu ambapo kila kipande kinaandikishwa.

Mfano wa Haraka wa Kitalu

Mfano wa haraka wa kitalu kutoka https://guyinatuxedo.github.io/25-heap/index.html lakini kwa arm64:

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

void main(void)
{
char *ptr;
ptr = malloc(0x10);
strcpy(ptr, "panda");
}

Wekeza kizuizi mwishoni mwa kazi kuu na tujue mahali taarifa zilikuwa zimehifadhiwa:

Inawezekana kuona kuwa herufi panda ilihifadhiwa kwa 0xaaaaaaac12a0 (ambayo ilikuwa anwani iliyotolewa kama jibu na malloc ndani ya x0). Kwa kuangalia 0x10 baada yake inawezekana kuona kuwa 0x0 inawakilisha kwamba kitengo kilichotangulia hakijatumika (urefu 0) na kwamba urefu wa kitengo hiki ni 0x21.

Nafasi za ziada zilizohifadhiwa (0x21-0x10=0x11) zinatokana na vichwa vilivyozidishwa (0x10) na 0x1 haimaanishi kuwa ilihifadhiwa 0x21B lakini biti za mwisho 3 za urefu wa kichwa cha sasa zina maana maalum. Kwa kuwa urefu daima ni kielelezo cha 16-baiti (kwenye mashine zenye bits 64), biti hizi hazitatumika kamwe na nambari ya urefu.

0x1:     Previous in Use     - Specifies that the chunk before it in memory is in use
0x2:     Is MMAPPED          - Specifies that the chunk was obtained with mmap()
0x4:     Non Main Arena      - Specifies that the chunk was obtained from outside of the main arena

Bins & Ugawaji/Frees wa Kumbukumbu

Angalia ni bins gani na jinsi zinavyoandaliwa na jinsi kumbukumbu inavyogawiwa na kuachiliwa katika:

Vipimo vya Usalama vya Kazi za Heap

Vipimo vinavyohusika na heap vitafanya uhakiki fulani kabla ya kutekeleza vitendo vyake ili kujaribu kuhakikisha kuwa heap haikuharibiwa:

Marejeo

Last updated