Förderjahr 2022 / Stipendien Call #17 / ProjektID: 6428 / Projekt: Automated Diagnosis of Heisenbugs
Ein Hauptziel unseres Projekts ist es, eine Methode zu entwickeln, mit der man Ursachen von Heisenbugs finden kann. Dabei stützen wir unsere Arbeit auf Ansätze aus dem philosophischen Feld der Kausalität.
Kausalität in der Philosophie
In der Welt der Wissenschaft und Philosophie spielt das Konzept der Kausalität eine große Rolle, wenn es darum geht Zusammenhänge zwischen Ursache und Wirkung zu finden. Kausalität beschäftigt sich mit der Frage, welche Voraussetzungen erfüllt sein oder Ereignisse passieren müssen, damit ein bestimmtes Ergebnis eintritt. So kann man zum Beispiel nach ganz alltäglichen kausalen Zusammenhängen wie "Warum ist der Waldbrand ausgebrochen?" fragen. Basierend auf ähnlichen Prinzipien stellen wir in unserem konkreten Projekt die Frage:
"Welche Quellen von Nichtdeterminismus im System führen dazu dass der Heisenbug manchmal auftritt und manchmal nicht?".
Wie wir im Zuge unserer Arbeit festgestellt haben, gibt es in der Philosophie eine Vielzahl verschiedener Ansätze, wie man Kausalität definieren und feststellen kann. Tatsächlich beschäftigt die Frage nach einer passenden Definition von Kausalität Philosophen und Wissenschaftler seit mindestens einigen hundert Jahren und ist immer noch Gegenstand einer fortwährenden Debatte. Für unsere Zwecke hat sich herausgestellt, dass sich vor allem Kausalitätsargumente basierend auf Lewis' Counterfactuals eignen, bei denen mehrere unterschiedliche Szenarien verglichen werden.
Formale Definition von Kausalität
Auf dieser Grundlage haben wir eine formales Modell für die Kausalität von Heisenbugs entwickelt. Das formale Modell baut auf der formalen Definition von Heisenbugs auf, die besagt, dass ein Heisenbug vorliegt wenn zwei Ausführungen mit denselben Nutzereingaben zu unterschiedlichen (korrekten bzw. falschen) Ergebnissen führen.
Für die Kausalitätsanalyse erweitern wir nun das Modell, indem wir nichtdeterministische Mechanismen explizit als zusätzliche Inputs darstellen. So könnte man etwa im Beispiel des Getränkeautomaten die Uhrzeit als zusätzlichen Input modellieren.
Um die Ursachen für den Heisenbug zu finden, suchen wir zwei Ausführungen, die zwar zu unterschiedlichen Ergebnissen führen, aber in möglichst vielen Eingaben, die nichtdeterministische Mechanismen modellieren, übereinstimmen. Ursache für den Heisenbug sind dann all jene nichtdeterministischen Mechanismen, in denen sich die Ausführungen weiterhin unterscheiden. Anders ausgedrückt: Der Heisenbug würde nicht mehr auftreten, wenn diese Quellen von Nichtdeterminismus explizit kontrolliert würden.
Kausalitätsanalyse in der Praxis
Eine häufige Herausforderung in der Praxis besteht darin, dass nicht immer bekannt ist welche Quellen von Nichtdeterminismus eine Rolle spielen. Quellen, die nicht modelliert werden, können von keiner Analyse als Ursache identifiziert werden. Dies wirft die Frage auf, wie präzise kausale Analysen sein können, wenn nur ein Teil der Quellen berücksichtigt wird.
In unserer Arbeit haben wir gezeigt, dass die gefundenen Ursachen in solchen Fällen immer noch eine Teilmenge der tatsächlichen Ursachen sind. Dies ist eine wertvolle Eigenschaft unserer Analyse, da das sicherstellt, dass Analyseergebnisse in unvollständigen Modellen, zwar potentiel auch unvollständig, aber dennoch korrekt sind.
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.