Seite 2: Der Heap

Inhaltsverzeichnis

Der Heap

Anders als bei den anderen Datenbereichen sind die Puffer auf dem Heap dynamisch. Der Entwickler beziehungsweise der Compiler muss zum Zeitpunkt der Programmerstellung noch nicht wissen, wie viele Daten er dort speichern wird, sondern das Programm kann den benötigten Platz zur Laufzeit in passender Größe anfordern. Dies geschieht über eine der zahlreichen Speicherreservierungsfunktionen, abhängig von Sprache, Plattform und Verwendungszweck der Software:

• malloc(), calloc() und realloc() sind in ANSI-C-Code die am häufigsten verwendeten Funktionen.
• Der Operator new reserviert in C++ Speicher auf dem Heap für Arrays und Objektinstanzen.
• Delphi-Programmierer verwenden GetMem() und New().
• Viele Plattformen bieten nichtportable Funktionen an, wie LocalAlloc() und HeapAlloc() unter Windows.

Der Aufruf dieser Funktionen reserviert Speicher im virtuellen Adressraum des Prozesses und liefert einen Zeiger darauf zurück. Der Programmierer kann diesen Speicher beliebig nutzen und muss ihn dann zu gegebener Zeit wieder freigeben.

Typischerweise versieht das Betriebssystem jeden Prozess mit einem Heap einer bestimmten Größe, die sich allerdings zur Laufzeit ändern lässt. Dessen Verwaltung und Aufteilung in kleine, dem Programmierer genehme Häppchen übernimmt meist eine Systembibliothek, die beim Laden des Prozesses in dessen Adressbereich eingeblendet wird.

Werden die Grenzen eines vom Kernel bereitgestellten Speicherbereichs überschritten, so führt das zu einer Zugriffsverletzung und damit in der Regel zum Beenden des Prozesses. Innerhalb des Speicherbereiches existieren allerdings keine solche Begrenzungen; weder die CPU noch der Kernel können erkennen, ob es zu Überläufen im Inneren des Heap gekommen ist.

Wie viel Speicher vom Kernel für einen Heap erbeten wird, hängt vom ausgeführten Programm ab. Viele Dateiformate für ausführbare Dateien enthalten Information für die erwartete Größe des Heap. Die Windows-Formate für ausführbare Dateien PE und PE32 führen diese Information im so genannten Optional Header, welcher alles andere als optional ist. Sowohl für den Stack als auch für den Heap enthält er die zu reservierende und die sofort benötigte Größe. Das für Linux primär verwendete ELF32-Dateiformat liefert ähnliche Vorgaben.

Auch der Heap enthält – analog zum Stack – Verwaltungsinformationen gemischt mit Nutzdaten. Entsprechend funktionieren Buffer-Overflow-Angriffe auf dem Heap prinzipiell ähnlich wie auf dem Stack: Durch das gezielte Überschreiben von Verwaltungsdaten kann der Angreifer den Programmablauf so beeinflussen, dass sein eingeschleuster Code ausgeführt wird.

Ein einfacher Heap

Jede Laufzeitumgebung hat ihr eigenes Heap-Management, das an die Eigenheiten des jeweiligen Systems angepasst ist. Prinzipiell kann ein Programm jedoch auch seine eigene Speicherverwaltung implementieren.

Für die Erläuterung von Heap-Overflows verwenden wir im Folgenden eine einfache Heap-Verwaltung, die in dieser Form wohl nicht in der Praxis zu finden ist, an der sich die grundsätzlichen Techniken aber gut zeigen lassen. Diese Beispielimplementierung, genannt SimpleHeap, besteht aus einer doppelt verketteten Liste, welche als Nutzdaten die reservierten Speicherblöcke enthält. Jeder Speicherblock startet zunächst mit einem Header für die Verwaltungsdaten: jeweils ein Zeiger zum nächsten und vorgehenden Speicherblock, die Größe des reservierten Speichers und einen Marker, der anzeigt, ob der Speicherblock verwendet wird. Anschließend folgt der eigentliche Speicherbereich. In C sieht das Ganze so aus:

typedef struct __HeapHdr__ {
 struct __HeapHdr__	*next;
 struct __HeapHdr__	*prev;
 unsigned int 	size;
 unsigned int 	used;
 // Nutzdatenbereich ab hier
} HeapHdr_t;

Beim Programmstart holt sich SimpleHeap einen ausreichend großen Speicherbereich vom Betriebssystem, den es anschließend selbst verwaltet. Die Initialisierung erzeugt ein Wurzelelement, das den gesamten freien Speicher enthält:

root = (HeapHdr_t *) memory;
root->next = NULL;
root->prev = NULL;
root->size = initial_size - sizeof(HeapHdr_t);
root->used = 0;

Alles, was SimpleHeap damit noch fehlt, sind Funktionen zum Reservieren und Freigeben von Speicher. Diese einfache Implementierung kommt ohne große Finessen aus, wodurch sich diese Funktionen sehr einfach gestalten. Die Reservierungsfunktion SimpleHeap_alloc() sucht einen freien Block mit ausreichender Größe und verwendet den gewünschten Teil davon. Die Funktion SimpleHeap_free() zur Freigabe von Speicher gestaltet sich ähnlich simpel. Sie nimmt den Zeiger auf den Datenblock entgegen und markiert ihn im zugehörigen Header als frei, indem sie das used-Feld auf 0 setzt.

Eine so einfache Implementierung hätte allerdings einen entscheidenden Nachteil: Der Heap fragmentiert im Lauf seiner Benutzung. Bei der Reservierung wird ein neuer Block vom großen Haufen abgeknapst, den ein SimpleHeap_free() zwar wieder freigibt, aber nicht wieder zum ursprünglichen freien Block hinzufügt. Soll nach der Freigabe ein neuer, größerer Block reserviert werden, könnte SimpleHeap den freigegebenen Block nicht verwenden, auch wenn er zusammen mit eventuell freien Nachbarn groß genug wäre.

Deshalb fasst die Funktion SimpleHeap_free() im Listing aufeinanderfolgende freie Blöcke zusammen und hängt den hinteren aus der doppelt verketteten Liste aus. Dazu muss sie zwei Zeiger manipulieren: Den next-Zeiger des ersten freien Blockes und den prev-Zeiger des übernächsten Blocks.

hdr->next=hdr->next->next;
hdr->next->next->prev=hdr->next->prev;

Die meisten Heap-Implementierungen arbeiten nach einem vergleichbaren Prinzip. In manchen Fällen erfolgt das Freigeben und das Zusammenfassen von freien Speicherblöcken jedoch getrennt, sodass Zusammenfassungen erst zeitlich verzögert erfolgen.