Computerfehler einfach wegrechnen
In einem vom Wissenschaftsfonds FWF finanzierten Projekt werden schnelle mathematische Analysemethoden entwickelt, um die Sicherheit von Computerprogrammen und Hardware zu erhöhen.
Computermethoden für Software-Tests gibt es schon lange, jedoch wuchs die Komplexität der Programme in den vergangenen Jahren stetig, während die Leistungsfähigkeit der Testmethoden hinterherhinkte, insbesondere was ihre Geschwindigkeit angeht. Der Computerwissenschafter Krishnendu Chatterjee beschäftigte sich in einem vom Wissenschaftsfonds FWF finanzierten Projekt mit der Analyse von Computersystemen mittels mathematischer Methoden, die Softwaretests signifikant beschleunigen sollen.
Anwendung der Graphentheorie
Für die mathematische Analyse von Computersystemen wird die sogenannte “Graphentheorie” genutzt. Ihr Gegenstand sind Objekte, die man sich als Netzwerke aus miteinander verbundenen Punkten oder Knoten vorstellen kann. Computersysteme lassen sich mathematisch als Graphen darstellen : Ein Knoten steht für einen bestimmten Zustand, in dem sich das System befindet, eine Kante steht für einen Übergang zwischen zwei Zuständen.
Dieser Rahmen ist besonders geeignet für die Prüfung von Computersystemen. Gemeinsam mit Projektpartnerin Monika Henzinger von der Universität Wien untersuchte er, wie die Methoden der Graphen-Algorithmen adaptiert und erweitert werden müssen, um wirklich bessere Algorithmen für die Probleme zu bekommen, die in komplexen Computersystemen von heute entstehen können.
Geschwindigkeitsschranken durchbrochen
Es gelang, mehrere seit den Neunzigerjahren bestehende Schranken für die Geschwindigkeit bestimmter Verifikationsalgorithmen zu durchbrechen, etwa im Bereich sogenannter “Markov Decision Processes”. Das sind Modelle, die mehrere Auswahlmöglichkeiten und ein Zufallselement beinhalten. “Ein Beispiel ist die Entwicklung von Robotern”, erklärt Chatterjee. “Ein Roboter interagiert mit einer Umgebung, in der es Unsicherheit gibt, und er hat Auswahlmöglichkeiten, kann etwa nach links oder rechts gehen.”
Für viele Anwendungen ist die Beantwortung der Frage zentral, welche Ereignisse in so einem Modell mit absoluter Sicherheit eintreten. “Der bisher effizienteste Algorithmus dafür war aus 1995 und hatte quadratische Komplexität”, sagt Chatterjee. Damit ist gemeint, dass etwa ein doppelt so großes System die vierfache Laufzeit benötigt. “In unserem Projekt konnten wir diese Grenze mit Graph-algorithmischen Techniken überwinden.” In einem Folgeprojekt will Chatterjee nun unter anderem untersuchen, wie sich die neuen Erkenntnisse in der Praxis umsetzen lassen.