Aufrufstapel

Unter einem Aufrufstapel (englisch call stack, procedure stack^[1]) versteht man in der Softwaretechnik und Informatik einen besonders genutzten Stapelspeicher, der zur Laufzeit eines Programms den Zustand der gerade aufgerufenen Unterprogramme enthält. Er ist vorgesehener Bestandteil der meisten Prozessorarchitekturen und seine Benutzung wird daher von speziellen Instruktionen und Registern unterstützt oder sogar erfordert. Als Stack Machine (engl. für Stapelmaschine, nicht zu verwechseln mit Kellerautomat) wird eine Klasse von Prozessorarchitekturen bezeichnet, die gänzlich um einen Aufrufstapel herum konstruiert sind, demgegenüber verwenden Registermaschinen zwar üblicherweise einen Aufrufstapel, sind jedoch nicht ausschließlich auf seine Nutzung angewiesen. Die Verwaltung des Aufrufstapels wird in Hochsprachen üblicherweise abstrahiert und stattdessen von Compiler und Betriebssystem übernommen. Anders als beim paradigmatischen Stapelspeicher sind die Zugriffsmöglichkeiten auf den Aufrufstapel in vielen Architekturen jedoch nicht auf das oberste Element beschränkt und die Klassifizierung als Stapel ergibt sich aus der Verwendung als Stapelspeicher für Rücksprungadressen von Unterprogrammen. Zudem ist der Inhalt des Speichers sehr inhomogen und verknüpft Nutzdaten mit Verwaltungsdaten.

Funktionsweise

Unterprogrammaufrufe

Strukturierte Programmierung erfordert in der Regel Programme in kleinere Unterprogramme zu teilen, um eine bestimmte Funktionalität jeweils genau einmal zu implementieren und so Duplizierung von Code zu vermeiden. Da diese von verschiedenen Stellen im Programm aufgerufen werden sollen, kann ein Unterprogramm keine konkrete Adresse kennen, an der die Ausführung fortgesetzt werden soll, wenn das Unterprogramm beendet ist. Daher müssen beim Aufruf Adressen gespeichert werden, an denen die Ausführung nach dem Unterprogramm fortgesetzt wird. Dies ist die Adresse, die direkt hinter der Adresse des Unterprogrammaufrufs liegt. Am Ende des Unterprogramms lädt der Prozessor die gespeicherte Adresse wieder in den Befehlszähler und die Programmausführung setzt in der Aufrufebene hinter dem Unterprogrammaufruf fort; die Rücksprungadresse wird dabei vom Stapel genommen. Das Befüllen und Entleeren des Aufrufstapels ist allerdings nicht Aufgabe des Programmierers, sofern man in Hochsprachen programmiert, wie beispielsweise Java. Dann erzeugen Compiler die notwendigen Befehle zur Benutzung des Aufrufstapels. Nach Abschluss eines Unterprogramms muss der Aufrufstapel wieder in den ursprünglichen Zustand versetzt werden, damit sich ein Unterprogramm beliebig häufig aufrufen lässt, ohne dass der Aufrufstapel einen Über- oder Unterlauf erfährt. Ob das Unterprogramm selbst für das Freigeben des Speichers zuständig ist oder der aufrufende Code das erledigen muss, hängt von der verwendeten Aufrufkonvention ab.

Lokaler Zustand

Neben der Rücksprungadresse wird aber von vielen Architekturen auch lokaler Zustand der Unterprogramme auf dem Aufrufstapel gespeichert. So wird in der x86 Architektur beispielsweise zu diesem Zweck der Stapel in sogenannte Stapelrahmen (englisch stack frames) eingeteilt und neben der Rücksprungadresse auch immer ein Verweis auf den Beginn des letzten Stack Frames gespeichert. Im aktuellen Stack Frame ist genügend Speicherplatz für die Daten des aktuellen Unterprogramms reserviert und dieser kann über herkömmliche Speicherzugriffsmechanismen der Prozessorarchitektur angesprochen werden. Ein spezielles Register zeigt auf den aktuellen Frame und das Unterprogramm adressiert seinen Zustand relativ zu dieser Adresse.^[2] So können Unterprogramme sich gegenseitig aufrufen, indem immer neue Stack Frames alloziert werden und das Register jeweils um die Größe des Frames verschoben wird. Der Zustand der vorhergehenden, noch nicht beendeten Unterprogrammaufrufe wird dabei tiefer im Stapel erhalten.

Parameter und Rückgabewerte

Abhängig von der Aufrufkonvention werden auch einige oder alle Parameter für einen Unterprogrammaufruf über den Stack übergeben.^[3] Ergebniswerte von Unterprogrammen können, je nach Aufrufkonvention, ebenfalls über den Aufrufstapel zurückgegeben werden. Sie belegen dann denselben Block wie die Aufrufparameter. Die Größe dieses Bereichs muss daher so gewählt sein, dass jede der beiden Arten hineinpasst. Beim Rücksprung werden die Aufrufparameter nicht mehr benötigt, daher überschreiben die Rückgabewerte einfach die Aufrufparameter und stehen danach dem aufrufenden Code zur Verfügung.^[4]

Implementierung

Für jeden aktiven Unterprogrammaufruf enthält der Stack-Frame folgende Strukturen:

• optionale Eingangsparameter (geteilt mit optionalen Rückgabewerten, die später erzeugt werden)
• Rücksprungadresse
• optionale lokale Variablen

Nach einem Unterprogrammaufruf verbleibt folgende Struktur:

• optionale Rückgabewerte des Unterprogramms

Im folgenden Diagramm sind beispielhaft drei Aufrufebenen dargestellt.

1. Aufrufebene (türkis) verwendet Parameter, hat aber keine lokalen Variablen.
2. Aufrufebene (blau) verwendet keine Parameter, hat aber lokale Variablen.
3. Aufrufebene (hellblau) verwendet sowohl Parameter, als auch lokale Variablen und Rückgabewerte.

Aufrufstapel während und nach einem Unterprogrammaufruf

Während des Unterprogrammaufrufs	Nach Rückkehr des Unterprogramms	Nach Übernahme der Rückgabewerte

Nebenläufigkeit und Parallelität

Ein Aufrufstapel kann immer nur eine unverzweigte Folge von Unterprogrammaufrufen abbilden. Bei der Verwendung von Prozessen und Threads muss daher für jeden Prozess und Thread ein eigener Aufrufstapel eingerichtet werden, damit Rücksprungadressen und lokale Variablen sich nicht gegenseitig überschreiben. Moderne Ansätze zur Nebenläufigkeit erfordern zuweilen auch den Ersatz des Aufrufstapels durch flexiblere Mechanismen (siehe Activation Records).

Stapelüberlauf, Rekursion und Endrekursion

Der Speicher für den Aufrufstapel ist natürlich nicht beliebig groß. Dies wird vor allem dann zu einem Problem, wenn sich Methoden sehr oft gegenseitig oder selbst aufrufen (Rekursion). Wenn ein rekursives Problem zu groß ist, erreicht der Stack sein Speicherlimit und es können keine weiteren Stack-Frames reserviert werden: Es kommt zum Programmabsturz. Man spricht von einem Stapelüberlauf (englisch stack overflow). Gänzlich umgehen lässt sich das Problem nur, wenn der Programmierer Vorkehrungen trifft um eine zu tiefe Rekursion zu verhindern. Zusätzlich können Compiler dabei helfen, sogenannte Endrekursion zu optimieren.^[5] Dabei werden rekursive Aufrufe vom Compiler in Schleifen übersetzt, ohne die semantische Bedeutung des Codes zu ändern. Die entstehende Schleife arbeitet ausschließlich in einem einzelnen Stack-Frame.

Segmentierte Aufrufstapel

Eine weitere Möglichkeit ein Überlaufen des Stapels zu umgehen bietet ein segmentierter Aufrufstapel. Wird ein Unterprogramm aufgerufen, überprüft dieses, ob genug Speicherplatz für seinen Stack-Frame vorhanden ist. Ist dies nicht der Fall, ruft es ein weiteres Unterprogramm auf, welches ein neues sogenanntes Stacklet (englisch Stäpelchen) alloziert und in einer Liste ablegt. Dieser neu allozierte Block wird dann für folgende Stack-Frames benutzt. Über die Liste lassen sich vorhergehende Blöcke wiederfinden, sobald der Stapel wieder abgebaut wird.^[6] Allerdings führt ein segmentierter Aufrufstapel zu einem Problem, das von der Go-Community das „hot-split problem“ genannt wird.^[7] Wenn ein Programm in einer Schleife ständig einen neuen Block für den Aufrufstapel anlegt und sofort wieder freigibt, führt dies zu Einbrüchen in der Performance. Aus diesem Grund haben die Programmiersprachen Rust und Go, die beide segmentierte Aufrufstapel in früheren Versionen benutzt haben, diese mittlerweile durch alternative Lösungen ersetzt.^[8][9]

Stacktrace

Tritt in einem Programm ein Fehler auf, der nicht durch den Programmierer erwartet und behandelt wurde und die weitere Ausführung des Programms nicht ermöglicht, so stürzt das Programm ab. Dabei werden in der Regel Informationen gesammelt, die die Ursache des Absturzes eingrenzen und die Behebung des Fehlers vereinfachen sollen. Dazu gehört häufig ein sogenannter Stacktrace, der die Hierarchie des Aufrufstapels zum Zeitpunkt des Fehlers widerspiegelt. Dadurch lässt sich verfolgen, in welchem Unterprogramm der Fehler auftrat und wie das Programm an die Stelle gelangt ist (da ein Unterprogramm möglicherweise von vielen Stellen aus aufgerufen werden könnte). Im Falle einer endrekursiven Funktion fehlt aber ein beträchtlicher Teil des Stacktraces, was über einen Shadow Stack gelöst werden kann.

Sicherheitsbetrachtungen

Die Nähe von lokalen Variablen zur Rücksprungadresse kann eine Kompromittierung der Software durch Pufferüberläufe ermöglichen.

Gelingt es einer Schadsoftware, in dem gerade aufgerufenen Unterprogramm die auf dem Aufrufstapel hinterlegte Rücksprungadresse zu überschreiben, so kann sie beeinflussen, welcher Code nach dem Rücksprung ausgeführt wird. Ist dazu zuvor eigener Schadcode im Hauptspeicher abgelegt worden, so kann mit diesem Verfahren die Kontrolle an den Schadcode übergeben werden.

Befindet sich z. B. ein Puffer unter den lokalen Variablen und gelingt es der externen Schadsoftware, durch Ausnutzen von Programmierfehlern zu erreichen, dass dieser Puffer über sein definiertes Ende hinaus beschrieben wird, so wird der Ablageort der Rücksprungadresse erreichbar. Da der Aufrufstapel typischerweise von höheren zu niedrigeren Adressen (der Puffer aber von niedrigen zu höheren Adressen) beschrieben wird, sind durch Überschreiben des Puffers ältere Inhalte des Aufrufstapels veränderbar (siehe auch Pufferüberlauf).

Shadow Stack

Das Sicherheitsrisiko bezüglich des Überschreibens von Rücksprungadressen kann durch einen sogenannten shadow stack (englisch Schatten Stapel) mitigiert werden.^[10] Dabei werden die Rücksprungadressen auf einem zusätzlichen, vom eigentlichen Stapel getrennten Speicherbereich gesammelt und somit von Nutzdaten getrennt. Modifizierte Rücksprungadressen können somit erkannt und die Programmausführung rechtzeitig beendet werden. Dies erschwert typische stapelbasierte Angriffe, verhindert sie jedoch nicht gänzlich, da ein Angreifer unter Umständen auch Zugriff auf den Shadow-Stack erhalten kann. Des Weiteren werden Shadow-Stacks benutzt, um unvollständige Stacktraces während des Debuggings von Programmen mit Endrekursion zu ergänzen. Hierzu werden alle Unterprogrammaufrufe, auch solche, die eigentlich durch die Optimierung von Endrekursion nicht mehr stattfinden, in einem Shadow-Stack zusätzlich abgespeichert, um die Fehlerbehebung zu erleichtern.^[11]

Interpreter

Bei der Implementation eines Interpreters wird eine neue Laufzeitumgebung modelliert, die einen eigenen Aufrufstapel besitzen kann. Einige Implementationen gestalten Unterprogrammaufrufe über eine Prozedur call, die bei Rekursion selbst rekursiv aufgerufen wird, was zu einer Kopplung der beiden Aufrufstapel führt. Da die Größe des Aufrufstapels bei einem Maschinenprogramm oft beschränkt ist, wird auch die maximale Rekursionstiefe des vom Interpreter ausgeführten Unterprogramms beschränkt. Eine Lösung für dieses Problem besteht darin, call in die Hauptschleife des Interpreters einzubetten, was der Transformation der Rekursion in eine Iteration entspricht.

Alternativen

Registerstack

Abhängig von der Aufrufkonvention werden Parameter an Unterprogramme in Registern übergeben. Da Unterprogramme jedoch ihrerseits Register benötigen und weitere Unterprogramme mit anderen Parametern aufrufen können, müssen häufig Inhalte dieser Register auf dem Aufrufstapel abgelegt werden, um diese später zu rekonstruieren. Eine Register Stack Engine verhindert diese kostenintensiven Speicherzugriffe, indem es einen Stapel an Registern simuliert und diesen erst dann auf den Aufrufstapel auslagert, wenn er zu groß wird.^[12] Soll Registerinhalt auf dem Stack abgelegt werden und neuer Inhalt in das Register geschrieben werden, wird stattdessen das Register umbenannt und ein neues Register anstelle des ursprünglichen benutzt. Zur Wiederherstellung des Registerinhalts wird die Umbenennung rückgängig gemacht.

Activation Records

Alternativ ist es möglich, dass das Stack Frame (auch Activation Record genannt) auf einem Heap alloziert wird. Eine teilweise Heap-Allokation ist bei Closures notwendig, eine vollständige bei Koroutinen, die ihren Zustand zwischen zwei Aufrufen behalten. Aus diesem Grund kann der Zustand nicht auf einem Stapel verwaltet werden, da bei Pausierung des Programms dieser Zustand überschrieben würde.

Continuation-Passing Style

Bei fester Einbettung des Stack Frames in das Maschinenprogramm entfällt der Aufrufstapel, allerdings unterbindet dies zunächst die Verwendung von Rekursion. Beim Continuation-Passing Style entfällt sogar die Speicherung der Rücksprungadresse, weil ein Unterprogramm ausschließlich neue Unterprogramme aufruft und niemals zurückkehrt, wodurch Rekursion wieder zur Verfügung steht.

Geschichtliches

Bei McCarthy^[13] wird der Einsatz von Aufrufstapeln bei einer LISP-Implementierung ab 1958 berichtet.

Belege

1. ↑ Intel Corporation: Intel® 64 and IA-32 Architectures Software Developer’s Manual (§6.1). Intel Corporation, Mai 2019, abgerufen am 18. Juni 2019 (englisch). 
2. ↑ Intel Corporation: Intel® 64 and IA-32 Architectures Software Developer’s Manual (§3.4.1). Intel Corporation, Mai 2019, abgerufen am 18. Juni 2019 (englisch). 
3. ↑ __cdecl. In: C++ Language Reference. Microsoft, 10. September 2018, abgerufen am 18. Juni 2019 (englisch). 
4. ↑ Itanium C++ ABI. Abgerufen am 18. Juni 2019 (englisch). 
5. ↑ Harold Abelson, Gerald Jay Sussman, Julie Sussman: Structure and Interpretation of Computer Programs. 2. Auflage. Cambridge, Massachusetts 2. Februar 2016, S. 45 f. ([1] [PDF; abgerufen am 26. Juni 2019]). 
6. ↑ Segmented Stacks in LLVM. In: LLVM Compiler Infrastructure. LLVM Project, 26. Juni 2019, abgerufen am 26. Juni 2019 (englisch). 
7. ↑ Contiguous Stacks. In: Go Design Documents. Abgerufen am 26. Juni 2019 (englisch). 
8. ↑ Brian Anderson: Abandoning segmented stacks in Rust. In: mail.mozilla.org Mailing Lists. 4. November 2013, abgerufen am 26. Juni 2019 (englisch). 
9. ↑ Go 1.3 Release Notes. In: golang.org. 18. Juni 2014, abgerufen am 19. September 2020 (englisch). 
10. ↑ Saravanan Sinnadurai, Qin Zhao, Weng-Fai Wong: Transparent Runtime Shadow Stack: Protection against malicious return address modifications. Singapore 2006 (psu.edu [PDF; abgerufen am 26. Juni 2019]). 
11. ↑ ShadowChicken.h. In: Webkit Code Base. Abgerufen am 26. Juni 2019 (englisch). 
12. ↑ Intel® Itanium® Architecture Software Developer's Manual. In: intel.com. Intel Corporation, Mai 2010, abgerufen am 26. Juni 2019 (englisch). 
13. ↑ J. McCarthy: History of Lisp. In: R. L. Wexelblat: History of Programming Languages. Academic Press, New York 1981, S. 173–185.