Netidee Blog Bild
Nichtdeterminismus
Warum verhalten sich Programme unvorhersehbar? (02.07.2023)
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.

 

 

Tags:

Heisenbugs Nichtdeterminismus Debugging

Sarah Sallinger

Profile picture for user 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.

Skills:

Programming
,
Formal Methods
,
Logic
CAPTCHA
Diese Frage dient der Überprüfung, ob Sie ein menschlicher Besucher sind und um automatisierten SPAM zu verhindern.
    Datenschutzinformation
    Der datenschutzrechtliche Verantwortliche (Internet Privatstiftung Austria - Internet Foundation Austria, Österreich) würde gerne mit folgenden Diensten Ihre personenbezogenen Daten verarbeiten. Zur Personalisierung können Technologien wie Cookies, LocalStorage usw. verwendet werden. Dies ist für die Nutzung der Website nicht notwendig, ermöglicht aber eine noch engere Interaktion mit Ihnen. Falls gewünscht, treffen Sie bitte eine Auswahl: