Definition
Ein Stack-Überlauf ist ein Laufzeit-Softwarefehler, bei dem ein Programm versucht, mehr Platz zu verwenden, als auf dem Laufzeit-Stack verfügbar ist, was typischerweise zu einem Programmabsturz führt.
Laufzeit-Stack
Ein Laufzeit-Stack ist ein spezieller Bereich des Computerspeichers, der nach dem LIFO-Prinzip arbeitet (Last in, first out: das letzte Element, das einer Struktur hinzugefügt wird, muss als erstes entfernt werden). Das Wort “Stack” bezieht sich auf die Art und Weise, wie mehrere Platten gestapelt werden: Sie bilden einen Stapel, indem Sie die Platten übereinander legen (diese Art des Hinzufügens eines Objekts in den Stapel wird “Push” genannt) und sie dann, beginnend mit der obersten Platte, wieder entfernen (diese Art des Entfernens eines Objekts vom Stapel wird “Pop” genannt). Der Laufzeitstapel wird auch als Aufrufstapel, Ausführungsstapel und Maschinenstapel bezeichnet (diese Begriffe werden verwendet, um ihn nicht mit dem “Stapel” als abstrakte Datenstruktur zu verwechseln).
Der Zweck eines Stacks ist es, dem Programmierer zu ermöglichen, Aufrufe von Unterprogrammen bequem anzuordnen. Ein Stack kann verwendet werden, um Argumente, die an eine aufgerufene Funktion übergeben werden sollen, und deren lokale Variablen zu speichern. Wenn eine andere Funktion von der ersten aufgerufen wird, kann sie die Argumente vom Stack holen und verwenden, sowie ihre eigenen Variablen in einem für diese Funktion reservierten Speicherbereich ablegen. Wenn sie die Kontrolle zurückgibt, löscht sie auch den Stapelspeicher und gibt ihn wieder frei. Hochsprachenprogrammierer kümmern sich in der Regel nicht um solche Dinge, denn die Aufgabe, den notwendigen Routinencode zu erzeugen, übernimmt allein der Compiler.
Folgen des Fehlers
Damit sind wir endlich beim Thema unserer Diskussion angelangt. Als Abstraktion ist ein Stack ein unendlicher Speicher, in den Sie endlos neue Elemente einfügen können. Leider ist in der realen Welt alles endlich – der Stack-Speicher ist da keine Ausnahme. Was passiert, wenn er zu Ende geht, während neue Argumente in ihn hineingeschoben werden oder wenn eine Funktion Speicher für ihre Variablen alloziert?
Ein Fehler, der als Stack-Überlauf bekannt ist, wird auftreten. Da ein Stack verwendet wird, um die Aufrufe von Benutzerunterprogrammen zu ordnen (und die meisten Programme, die in modernen Programmiersprachen geschrieben werden – einschließlich objektorientierter -, verwenden auf die eine oder andere Weise aktiv Funktionen), wird das Programm nach dem Auftreten des Fehlers nicht in der Lage sein, irgendeine Funktion aufzurufen. Wenn das passiert, übernimmt das Betriebssystem die Kontrolle zurück, leert den Stack und beendet das Programm. Hier liegt der Unterschied zwischen dem Buffer Overflow und dem Stack Overflow. Ersterer tritt auf, wenn das Programm versucht, auf einen Speicherbereich außerhalb der Puffergrenze zuzugreifen, und bleibt unbemerkt, wenn es keinen Schutz dagegen gibt; das Programm läuft mit etwas Glück korrekt weiter. Nur wenn es einen Speicherschutz gibt, tritt ein Segmentation Fault auf. Wenn aber ein Stack-Überlauf auftritt, stürzt das Programm unweigerlich ab.
Um genau zu sein, gilt dieses Szenario nur für native Sprachen. Die virtuelle Maschine in verwalteten Sprachen hat für verwaltete Programme einen eigenen Stack, der leichter zu überwachen ist, so dass man es sich sogar leisten kann, beim Auftreten eines Stack-Überlaufs eine Exception zu werfen. C und C++ können sich einen solchen “Luxus” aber nicht leisten.
Gründe für den Fehler
Was sind die Gründe für diesen unangenehmen Fehler? In Anbetracht des oben beschriebenen Mechanismus können wir einen nennen: zu viele eingebettete Funktionsaufrufe. Dieses Szenario ist besonders wahrscheinlich bei der Verwendung von Rekursion: es ist tatsächlich dieser Fehler, mit dem eine unendliche Rekursion endet (wenn es keinen Mechanismus für träge Auswertung gibt), im Gegensatz zu einer Endlosschleife, die manchmal nützlich sein kann. Wenn jedoch nur ein sehr kleiner Speicherbereich auf dem Stack allokiert ist (was z. B. für Mikrocontroller typisch ist), reicht eine kurze Folge von Aufrufen aus, um die Arbeit zu erledigen.
Ein weiterer Grund sind lokale Variablen, die zu viel Stack-Speicher benötigen. Es ist eine schlechte Idee, ein lokales Array mit einer Million Elementen oder einer Million lokaler Variablen anzulegen (nur für den Fall). Ein einziger Aufruf einer solchen “gierigen” Funktion kann leicht einen Stack-Überlauf auslösen. Wenn Sie große Datenmengen erhalten wollen, sollten Sie besser dynamischen Speicher verwenden, um im Falle eines Fehlers diesen verarbeiten zu können.
Dynamischer Speicher ist jedoch recht langsam beim Allokieren und Freigeben (weil er vom Betriebssystem verwaltet wird). Außerdem müssen Sie ihn manuell allozieren und freigeben, wenn er mit einem direkten Zugriff versehen ist. Im Gegensatz dazu ist Stack-Speicher sehr schnell allokiert (Sie brauchen eigentlich nur den Wert eines Registers zu ändern); außerdem werden auf dem Stack allokierte Objekte automatisch zerstört, wenn die Funktion die Kontrolle zurückgibt und den Stack leert. Man kann sich natürlich nicht des Drangs erwehren, dies auszunutzen. Der dritte Grund für den Fehler ist also die manuelle Allokation von Stack-Speicher durch den Programmierer. Die C-Bibliothek stellt dafür die spezielle Funktion alloca zur Verfügung. Interessant ist, dass die Funktion malloc (die für die Allokation von dynamischem Speicher gedacht ist) ein “Geschwisterchen” hat, das den Speicher wieder freigibt (die Funktion free), die Funktion alloca aber nicht: Der Speicher wird automatisch freigegeben, sobald die Funktion die Kontrolle zurückgibt. Dieser Umstand dürfte die Sache verkomplizieren, denn Sie können den Speicher nicht freigeben, bevor Sie die Funktion verlassen. Obwohl in der Manpage für die alloca-Funktion klar steht, dass sie “maschinen- und compilerabhängig ist; auf vielen Systemen kann sie nicht richtig verwendet werden und kann Fehler verursachen; von ihrer Verwendung wird abgeraten”, verwenden Programmierer sie trotzdem.