Heap

Podstawy sterty

Sterta to miejsce, w którym program będzie mógł przechowywać dane, gdy żąda ich, wywołując funkcje takie jak malloc, calloc... Ponadto, gdy ta pamięć nie jest już potrzebna, jest ona udostępniana poprzez wywołanie funkcji free.

Jak widać na obrazku poniżej, sterta znajduje się zaraz po załadowaniu binarnego pliku do pamięci (sprawdź sekcję [heap]):

Podstawowe przydziały bloków

Gdy żądane jest przechowywanie danych na stercie, pewna przestrzeń sterty jest jej przydzielana. Ta przestrzeń będzie należeć do bloku, a zarezerwowane zostaną tylko dane żądane + przestrzeń nagłówków bloku + minimalne przesunięcie rozmiaru bloku. Celem jest zarezerwowanie jak najmniejszej ilości pamięci, aby nie komplikować procesu odnajdywania każdego bloku. W tym celu wykorzystywane są informacje o metadanych bloku, aby wiedzieć, gdzie znajduje się każdy używany/wolny blok.

Istnieją różne sposoby rezerwacji przestrzeni głównie w zależności od używanego bloku, ale ogólna metodologia wygląda następująco:

  • Program zaczyna od żądania określonej ilości pamięci.

  • Jeśli na liście bloków jest dostępny wystarczająco duży blok, aby zaspokoić żądanie, zostanie on użyty.

  • Może to nawet oznaczać, że część dostępnego bloku zostanie użyta do tego żądania, a reszta zostanie dodana do listy bloków.

  • Jeśli nie ma dostępnego bloku na liście, ale wciąż jest miejsce w przydzielonej pamięci sterty, menedżer sterty tworzy nowy blok.

  • Jeśli nie ma wystarczająco dużo miejsca na stercie, aby przydzielić nowy blok, menedżer sterty prosi jądro o rozszerzenie pamięci przydzielonej dla sterty, a następnie używa tej pamięci do wygenerowania nowego bloku.

  • Jeśli wszystko zawiedzie, malloc zwraca wartość null.

Zauważ, że jeśli żądana pamięć przekroczy pewien próg, zostanie użyte mmap do zmapowania żądanej pamięci.

Areny

W aplikacjach wielowątkowych, menedżer sterty musi zapobiegać warunkom wyścigowym, które mogą prowadzić do awarii. Początkowo było to realizowane za pomocą globalnego mutexa, aby zapewnić, że tylko jeden wątek mógł jednocześnie uzyskać dostęp do sterty, ale spowodowało to problemy wydajnościowe z powodu wąskiego gardła spowodowanego mutexem.

Aby temu zaradzić, alokator sterty ptmalloc2 wprowadził "areny", gdzie każda arena działa jako oddzielna sterta z własnymi strukturami danych i mutexem, pozwalając wielu wątkom wykonywać operacje na stercie bez ingerencji w siebie nawzajem, o ile korzystają z różnych aren.

Domyślna "główna" arena obsługuje operacje sterty dla aplikacji jednowątkowych. Gdy dodawane są nowe wątki, menedżer sterty przypisuje im areny pomocnicze w celu zmniejszenia rywalizacji. Najpierw próbuje przypisać każdy nowy wątek do nieużytej areny, tworząc nowe, jeśli jest to konieczne, aż do limitu 2 razy liczba rdzeni CPU dla systemów 32-bitowych i 8 razy dla systemów 64-bitowych. Po osiągnięciu limitu wątki muszą dzielić areny, co prowadzi do potencjalnej rywalizacji.

W przeciwieństwie do głównej areny, która rozszerza się za pomocą wywołania systemowego brk, areny pomocnicze tworzą "podsterty" za pomocą mmap i mprotect, aby symulować zachowanie sterty, umożliwiając elastyczne zarządzanie pamięcią dla operacji wielowątkowych.

Podsterty

Podsterty służą jako rezerwy pamięci dla aren pomocniczych w aplikacjach wielowątkowych, pozwalając im rosnąć i zarządzać swoimi własnymi obszarami sterty oddzielnie od głównej sterty. Oto w jaki sposób podsterty różnią się od początkowej sterty i jak działają:

  1. Początkowa sterta vs. Podsterty:

  • Początkowa sterta znajduje się bezpośrednio po binarnym programu w pamięci i rozszerza się za pomocą wywołania systemowego sbrk.

  • Podsterty, używane przez areny pomocnicze, są tworzone za pomocą mmap, wywołania systemowego mapującego określony obszar pamięci.

  1. Rezerwacja pamięci za pomocą mmap:

  • Gdy menedżer sterty tworzy podstertę, rezerwuje duży blok pamięci za pomocą mmap. Ta rezerwacja nie alokuje pamięci natychmiast; po prostu oznacza obszar, którego inne procesy systemowe lub alokacje nie powinny używać.

  • Domyślny rozmiar rezerwacji dla podsterty wynosi 1 MB dla procesów 32-bitowych i 64 MB dla procesów 64-bitowych.

  1. Stopniowe rozszerzanie za pomocą mprotect:

  • Początkowo zarezerwowany obszar pamięci jest oznaczony jako PROT_NONE, co oznacza, że jądro nie musi jeszcze alokować pamięci fizycznej dla tego obszaru.

  • Aby "rozszerzyć" podstertę, menedżer sterty używa mprotect, aby zmienić uprawnienia strony z PROT_NONE na PROT_READ | PROT_WRITE, co skłania jądro do alokacji pamięci fizycznej dla wcześniej zarezerwowanych adresów. Ten krok po kroku pozwala podstercie rosnąć w miarę potrzeb.

  • Gdy cała podsterta zostanie wyczerpana, menedżer sterty tworzy nową podstertę, aby kontynuować alokację.

malloc_state

Każda sterta (główna arena lub areny innych wątków) ma strukturę malloc_state. Warto zauważyć, że struktura malloc_state głównej areny jest zmienną globalną w libc (dlatego znajduje się w przestrzeni pamięci libc). W przypadku struktur malloc_state stert wątków, znajdują się wewnątrz własnej "sterty" wątku.

Istnieje kilka interesujących rzeczy do zauważenia w tej strukturze (patrz kod C poniżej):

  • mchunkptr bins[NBINS * 2 - 2]; zawiera wskaźniki do pierwszego i ostatniego bloku małych, dużych i nieposortowanych bloków (liczba -2 wynika z tego, że indeks 0 nie jest używany)

  • Dlatego pierwszy blok tych bloków będzie miał wskaźnik wstecz do tej struktury, a ostatni blok tych bloków będzie miał wskaźnik do przodu do tej struktury. Oznacza to w zasadzie, że jeśli uda ci się wyciec te adresy w głównej arenie, będziesz miał wskaźnik do struktury w libc.

  • Struktury struct malloc_state *next; i struct malloc_state *next_free; są listami połączonymi areny

  • Blok top to ostatni "blok", który w zasadzie jest całą przestrzenią przypominającą stertę. Gdy blok top jest "pusty", sterta jest całkowicie użyta i musi zażądać więcej miejsca.

  • Blok last reminder pochodzi z przypadków, gdy dostępny nie jest dokładny blok o określonym rozmiarze, a zatem większy blok jest dzielony, a pozostała część wskaźnika jest umieszczana tutaj.

// 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

Ta struktura reprezentuje konkretny fragment pamięci. Różne pola mają różne znaczenie dla przydzielonych i nieprzydzielonych fragmentów.

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

Jak już wcześniej skomentowano, te fragmenty mają również pewne metadane, bardzo dobrze przedstawione na tym obrazie:

Metadane to zazwyczaj 0x08B wskazujący aktualny rozmiar fragmentu, używając ostatnich 3 bitów do wskazania:

  • A: Jeśli 1, pochodzi z podstrefy, jeśli 0, jest w głównej arenie

  • M: Jeśli 1, ten fragment jest częścią przestrzeni przydzielonej za pomocą mmap i nie jest częścią sterty

  • P: Jeśli 1, poprzedni fragment jest w użyciu

Następnie miejsce na dane użytkownika, a na końcu 0x08B wskazujący rozmiar poprzedniego fragmentu, gdy fragment jest dostępny (lub do przechowywania danych użytkownika, gdy jest przydzielony).

Co więcej, gdy jest dostępny, dane użytkownika są używane do przechowywania również pewnych danych:

  • Wskaźnik do następnego fragmentu

  • Wskaźnik do poprzedniego fragmentu

  • Rozmiar następnego fragmentu na liście

  • Rozmiar poprzedniego fragmentu na liście

Zauważ, jak ułożenie listy w ten sposób zapobiega konieczności posiadania tablicy, w której każdy pojedynczy fragment jest rejestrowany.

Szybki Przykład Sterty

Szybki przykład sterty z https://guyinatuxedo.github.io/25-heap/index.html ale w arm64:

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

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

Ustaw punkt przerwania na końcu funkcji main i sprawdź, gdzie zostały przechowane informacje:

Można zauważyć, że ciąg znaków panda został przechowany pod adresem 0xaaaaaaac12a0 (który został podany jako odpowiedź przez malloc wewnątrz x0). Sprawdzając 0x10 bajtów przed nim, można zobaczyć, że 0x0 oznacza, że poprzedni blok nie jest używany (długość 0) i że długość tego bloku to 0x21.

Dodatkowe miejsce zarezerwowane (0x21-0x10=0x11) pochodzi od dodanych nagłówków (0x10) i 0x1 nie oznacza, że zarezerwowano 0x21 bajtów, ale ostatnie 3 bity długości bieżącego nagłówka mają pewne specjalne znaczenia. Ponieważ długość zawsze jest wyrównana do 16 bajtów (w maszynach 64-bitowych), te bity faktycznie nigdy nie zostaną użyte przez liczbę długości.

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

Kosze i Przydziały Pamięci

Sprawdź, co to są kosze, jak są zorganizowane oraz jak pamięć jest przydzielana i zwalniana w:

pageBins & Memory Allocations

Sprawdzenia Bezpieczeństwa Funkcji Stosowanych w Stosie

Funkcje związane ze stosem będą wykonywać określone sprawdzenia przed wykonaniem swoich działań, aby upewnić się, że sterta nie została zniekształcona:

pageHeap Functions Security Checks

Odnośniki

Last updated