Implementing a reversible debugger for Python

Abstract

Programmierer beginnen mit der Fehlersuche, weil sie ein falsches Verhalten des Programmes feststellen. Das Ziel der Fehlersuche ist festzustellen wo im Programm der Defekt ist, also der Teil des Programmes, welcher für das falsche Verhalten verantwortlich ist. Der Defekt wird jedoch ausgeführt bevor ein falsches Verhalten sichtbar ist. Daher wäre es sinnvoll in einem Debugger das Programm am Ort, wo der Fehler sichtbar ist, zu beginnen und von dort weg das Programm schrittweise rückwärts auszuführen bis man zum Defekt gelangt.<br />Dieses rückwärts Ausführen wird jedoch von vielen gängigen Debuggern nicht unterstützt.<br />Es gibt zwei grundsätzliche Strategien um einen rückwärtsausführenden Debugger zu implementieren, das heißt einen Debugger der das Vorwärts- und Rückwärtsausführen unterstützt. Die erste Variante ist die des Log-basierenden Debuggers. Ein Log-basierender Debugger speichert den Programm State nach jeder ausgeführten Instruktion. Nachdem das Programm fertig ausgeführt worden ist kann der Anwender das Programm anhand des Logdatei erneut abspielen und den State zu jedem beliebigen Zeitpunkt im Programm abspielen. Die zweite Variante ist die Snapshot & Replay Strategie. Hierbei erlaubt der Debugger interaktive Steuerung des Programmes. Beim Vorwärtsausführen werden hierbei regelmäßig Snapshots vom State gemacht. Um das Programm rückwärts auszuführen wird ein vorheriger Snapshot aktiviert und das Programm solange erneut ausgeführt bis die gewünschte Position erreicht ist.<br />In dieser Diplomarbeit möchte ich zeigen, dass es möglich ist einen rückwärtsausführenden Debugger zu schreiben, welcher regelmäßig Snapshots macht und diese nutzt um Rückwärtsausführen zu ermöglichen. Es gibt einige Probleme die beim Rückwärtsausführen auftreten. Zum Beispiel gibt es nichtdeterministische Instruktionen, welche der Interpreter jedes Mal anders ausführt, beispielsweise eine Funktion, die die Systemzeit zurück gibt. Ein weiteres Problem sind Instruktionen mit Seiteneffekten.<br />Diese ändern einen Teil States vom Programm, welcher nicht mittels Snapshots gespeichert wird, wie zum Beispiel eine Funktion die auf die Festplatte schreibt. Daher möchte ich in dieser Arbeit Methoden vorstellen, die mit diesen Problemen umgehen können. Außerdem habe ich zum Nachweis der Machbarkeit einen Rückwärtsausführenden Debuggers für die Programmiersprache Python entwickelt, welcher die meisten Probleme der Rückwärtsausführung löst. Um die Rückwärtsausführung von Programmen mit nichtdeterministischen Instruktionen zu ermöglichen, habe ich das neue Konzept der Zeitlinien eingeführt. Mit Zeitlinien kann der Benutzer entscheiden, welchen Ausführungspfad er wählen möchte, wenn er auf nichtdeterministische Instruktionen trifft. Außerdem habe ich das Konzept des zustandsorientierten Ressourcen Managements entwickelt, damit der Debugger auch den externen Zustand verwalten kann. Der Benutzer kann somit auch die der aktuellen Position entsprechende Umgebung des Programmes ansehen, wenn er das Programm rückwärts ausführt.<br />

The programmer usually initiates a debugging process because of a failure and his goal is to find the defect. The defect is always executed before the failure occurs, so it is natural to start at the failure and move backwards in a program to find the defect. However this procedure is usually not supported by actual debuggers.<br />There are two different methods of implementing a reversible debugger, i.e., a debugger which can run the program forwards and backwards. The first one is the logging-based approach, which records the state of the program after every instruction and allows inspection after the program has finished running.<br />The second one is the replay-based approach, where the debugger runs the debuggee interactively. For this purpose it makes periodic snapshots.<br />The debugger runs the debuggee backwards by restoring a previous snapshot and then running the program forward until it reaches the desired position. In this thesis, I show that it is possible to implement a reversible debugger by continuous snapshotting of the program state.<br />There are indeed some challenges with using such a feature. For example, there are non-deterministic instructions, which execute differently each instance the interpreter executes them, e.g., a function, which returns the system time. Another example of this is when instructions change some external state like a file on the hard drive, which the debugger does not save when it makes a snapshot. Another problem is that some instructions do something different each time the debugger executes them.<br />Therefore I present some methods of treating these problems.<br />Accompanying this thesis, I have developed a proof-of-concept implementation of a reversible debugger called epdb for the Python programming language, which solves most of the problems of reversible debugging.<br />In order to support reversible debugging of programs which have non-deterministic instructions in it, I introduce the new concept of timelines. With timelines, the user can decide which execution path he wants to take. I also introduce stateful resource management to support the management of the external state. This allows the user to investigate the environment corresponding to the actual position inside the program, when he executes the program backwards.<br />