Förderjahr 2022 / Stipendien Call #17 / ProjektID: 6428 / Projekt: Automated Diagnosis of Heisenbugs
Heisenbugs sind Computerfehler, die nur gelegentlich auftreten. Diese Unvorhersehbarkeit ist nicht nur für Systemnutzer:innen frustrierend, sondern stellt auch die verantwortlichen Entwickler:innen vor große Herausforderungen.
Ein wichtiges Ziel meines Projekts ist es, Methoden zu entwickeln, die die Ursachen von Heisenbugs aufdecken, also aufzeigen, warum sich ein bestimmtes Programm nicht immer gleich verhält. Dazu muss im ersten Schritt festgestellt werden, an welchen Stellen das Programm unterschiedliche, also nichtdeterministische Entscheidungen treffen kann.
Um diesen Schritt zu unterstützen, habe ich im Zuge meiner Projektarbeit verschiedene Ursachen für nichtdeterministische Entscheidungen gesammelt und eine Taxonomie erstellt. Im Folgenden möchte ich einen Auszug der gesammelten Ursachen präsentieren:
Hardwarefehler
Herstellungsfehler, Alterung und Umweltbedingungen verursachen gelegentlich intermittierende Fehler, wie z. B. Bitflips im Speicher.
Weak Memory Models
Auf Multiprozessor-Plattformen können mikro-architektonische Funktionen (z. B. Caches) die Weitergabe von Schreibvorgängen an den geteilten Speicher verzögern, was zu unterschiedlichen Reihenfolgen führt, in denen nebenläufige Speicherzugriffe über die Kerne hinweg beobachtet werden.
Byte-Reihenfolge
Verschiedene Prozessorarchitekturen speichern Bytes in entgegengesetzter Reihenfolge, wobei das höchstwertige Byte zuerst (Big Endian) oder das kleinstwertige Byte zuerst (Little Endian) gespeichert wird, was zu abweichenden Ergebnissen für Programme führt, die auf einzelne Bytes zugreifen.
Wort- und Registergröße
Die Größe von Registern und Speicherzellen variiert je nach Architektur, was zu einem unterschiedlichen Überlaufverhalten führen kann, z. B. bei 32- gegenüber 64-Bit-Integern.
Scheduling
Unterschiedliche Abläufe der Thread- oder Prozessausführung führen zu abweichenden Ergebnissen, z.B. im Kontext von Race Conditions oder Atomizitätsverletzungen.
Ordnung von Netzwerkpaketen
Netzwerkpakete können in einer anderen Reihenfolge empfangen werden als sie gesendet wurden, z. B. aufgrund von unterschiedlichen Routen oder Parallelverarbeitung in Netzwerkgeräten.
Undefiniertes Verhalten in Programmiersprachen
Programmierkonstrukte, deren Verhalten im Sprachstandard nicht spezifiziert ist, können je nach Compiler und Optimierungsstufe eine unterschiedliche Semantik haben, z.B. im Falle von nicht initialisiertem Speicher.
Pseudo-Zufallszahlen
Pseudo-Zufallszahlengeneratoren können bei jeder Ausführung unterschiedliche Folgen von Zufallszahlen erzeugen, es sei denn, es wird ein Seed gesetzt.
Zeitabhängigkeit
Zeit kann ein impliziter Parameter sein, der die Anwendungslogik verändert, siehe z.B. Fehler, die nur in Schaltjahren auftreten oder dieser kuriose Fehler, der nur mittwochs auftritt.
Taxonomie
Im nächsten Schritt habe ich eine Taxonomie der verschiedenen Ursachen erstellt. So ist es zum Beispiel auffällig, dass manche Ursachen auf Nichtdeterminismus beruhen, bei denen innerhalb des System bestimmte Situationen nicht immer gleich behandelt werden (z.B. beim Scheduling), während andere Ursachen daher kommen, dass eigentlich zwei verschiedene Varianten eines Systems verwendet werden (z.B. Architekturen mit unterschiedlichen Registergrößen). Weiters spielen bei vielen Ursachen Nebenläufigkeit und Zeitabhängigkeit eine Rolle.
Bessere Einsichten in verschiedene Ursachen, bilden einen Grundstein für die Entwicklung automatischer Analysen für die Ursachensuche, was mein nächster Milestone ist.
Sarah Sallinger
I am a PhD student in the Rigorous Systems Engineering group at TU Wien. I am driven by the desire to better understand the inner workings of complex computer systems and I want to develop tools that help in this process. My research interests broadly span the fields of computer aided verification, program analysis and automated bug detection and diagnosis.
