AuDeRace

Automatische Erkennung von Wettlaufsituationen

Große Softwareprojekte, an denen hunderte Entwickler arbeiten, sind schwer zu überblicken und enthalten viele Fehler. Zum Testen solcher Software haben sich automatisierte Tests bewährt, die Teilbereiche der Software (Unit-Tests) oder die komplette Software (Systemtest) testen und Fehler reproduzierbar erkennen können. Dieses Vorgehen funktioniert gut bei sequentiellen Programmen, die ein deterministisches Verhalten aufweisen. Moderne Software enthält jedoch vermehrt Parallelität. Durch diese Nebenläufigkeit treten etliche neue, teils schwer zu lokalisierende, Fehler auf, die nicht mehr durch herkömmliche Testverfahren sicher detektiert werden können. Dazu gehören vor allem Verklemmungen und gleichzeitige Zugriffe auf die selbe Speicherstelle. Ob ein solcher Fehler auftritt, hängt von dem konkreten Ausführungsplan der Aktivitätsfäden ab. Dieser unterscheidet sich jedoch bei jeder Ausführung und ist auch stark von dem darunterliegenden System abhängig. Somit treten entsprechende Fehler normalerweise nicht bei jedem Testlauf auf, je nach Testsystem sogar niemals. Aus diesem Grund sind die herkömmlichen Testverfahren nicht mehr ausreichend für moderne, nebenläufige Software.
In dem Projekt AuDeRace werden Verfahren entwickelt, die Nebenläufigkeitsfehler reproduzierbar, effizient und mit möglichst geringen Aufwand für Entwickler erkennen können. Unter anderem wird eine Technik entwickelt, die es ermöglicht, Tests um einen Ablaufplan zu erweitern, durch den die Ausführung weiterhin deterministisch bleibt. Ein weiteres generelles Problem an Tests bleibt dabei aber bestehen: Der Entwickler muss sich zunächst Testfälle überlegen und diese anschließend implementieren. Insbesondere im Kontext von Parallelität ist es aber extrem schwer, sich das Verhalten von Programmen vorzustellen und problematische Stellen zu identifizieren. Deshalb sollen kritische Stellen automatisiert erkannt werden, bevor überhaupt entsprechende Tests geschrieben wurde. Es existieren bereits Ansätze, potentiell kritische Stellen zu detektieren, allerdings werden dabei entweder sehr viele fälschliche Warnungen generiert oder die Analyse ist immens zeitintensiv. Ziel dieses Projektes ist es, durch eine geeignete Kombination aus statischer und dynamischer Analyse, die Anzahl an falschen Erkennungen zu reduzieren, bzw. langsame Analysen zu beschleunigen, sodass die Verfahren nicht nur in kleinen Testbeispielen funktionieren, sondern auch komplexe Softwareprojekte effizient analysieren können.

Im Jahr 2016 wurden bestehende Ansätze und Programme auf ihre Tauglichkeit untersucht. Dabei wurde ein vielversprechendes Verfahren ausgemacht, das mithilfe von Model Checking und vorgegebenen Bedingungen Ablaufpläne konstruiert, die ungewolltes Verhalten erzeugen. Allerdings zeigten die Ergebnisse ein deutliches Problem hinsichtlich eines produktiven Einsatzes, da in sinnvoller Zeit nur sehr kleine Programme analysiert werden konnten. Daher beschäftigte sich das Projekt damit, die Programme um möglichst viele Anweisungen zu kürzen, die nichts mit den gesuchten Wettlaufsituationen zu tun haben. Dadurch sollen spätere Analysen beschleunigt werden.

Im Jahr 2017 wurden die Untersuchungen zur automatischen Reduktion von Programmen weitergeführt.  Außerdem wurde erforscht, ob sich die existierende Technik des Mutationstestens auch auf nebenläufige Programme erweitern lässt. Die Ergebnisse zeigen, dass es durchaus möglich ist, Tests für eine parallele Software qualitativ zu bewerten. Allerdings muss teilweise auf Heuristiken zurückgegriffen werden, um auch größere Projekte in vertretbarer Zeit bewerten zu können.

Im Jahr 2018 lag der Fokus auf einer deterministischen Ausführung von Testfällen. Es wurde ein Konzept erarbeitet, um reproduzierbare Ergebnisse bei der Ausführung zu erzielen: Ein zusätzlicher Ablaufplan spezifiziert das Ablaufverhalten der verschiedenen Aktivitäten. Eine Instrumentierung von vorher markierten Positionen im Code und anderen relevanten Bytecode-Instruktionen soll hier während der Ausführung entsprechend die Kontrolle an eine Verwaltungsaktivität abgeben, die den Ablauf steuert. Damit die Markierungen (Angabe von Positionen im Quellcode) auch nach Änderungen am Quellcode gültig bleiben, sollen diese automatisch auf eine neue Version angepasst werden können. Eine Merge-Technik ähnlich derer zu Versionsverwaltungssystemen soll hier eingesetzt werden.

Das Projekt stellte bis 2019 einen Beitrag des Lehrstuhls Informatik 2 zum IZ ESI (Embedded Systems Initiative, http://www.esi.fau.de/ ) dar. In diesem Rahmen wurden verschiedene Ansätze zur Verbesserung der Qualität nebenläufiger Software untersucht. Zusammenfassend wurde festgestellt, dass verschiedenartige Verfahren notwendig und realisierbar sind, allerdings meistens die hohen Laufzeiten ein großes Problem darstellen.

Über das ESI Projekt hinaus wurde die Verwendung von Mutationstests durch die Entwicklung eines Werkzeugs zur Äquivalenzerkennung und Testfallgenerierung verbessert. Eine entsprechende Publikation wurde eingereich und angenommen.
Im Jahr 2020 evaluierten wir Ansätze und Techniken zur Erkennung von externen Wettlaufsituationen. Während bei klassischen Wettlaufsituationen mehrere Aktivitätsfäden eines Programms nicht richtig miteinander arbeiten, treten externe Wettlaufsituationen bei der Interaktion der Software mit anderen, unabhängigen und unbekannten Komponenten auf. Das können andere gleichzeitig laufende Programme sein, das Betriebssystem oder sogar Code eines böswilligen Angreifers, der gezielt mit der analysierten Software interferiert.
Im Jahr 2021 wurde ein Verfahren entwickelt, um statisch Wettlaufsituationen bei der Verwendung von externen Ressourcen zu erkennen. Ein häufiges Muster ist, dass Programme die Eigenschaften von Dateien abrufen und später auf Grund der vorherigen Überprüfungen auf die Dateien erneut zugreifen. Ändert sich der Zustand der Datei in der Zwischenzeit, kann eine Vielzahl von Problemen auftreten (time-of-check to time-of-use). Neben unerwartetem Verhalten können jedoch auch Angreifer durch geeignetes Anpassen der Datei, gezielt Fehlverhalten auslösen oder das System kompromittieren. Mit dem entworfenen Verfahren sollen solche Problemstellen in einer Software automatisch erkannt werden.

Publikationen