Wie die Lösung klassischer Wahrscheinlichkeitsprobleme Informatikern helfen kann, Fehler zu finden
Bei automatisierten Softwaretests setzen Informatiker automatische Tools wie sogenannte Fuzzer ein, um Sicherheitslücken zu erkennen. Aber wie lange sollten die Fuzzer die Software testen, um sicherzustellen, dass sie fehlerfrei ist? Wissenschaftler am MPI-SP haben eine mathematische Berechnung auf der Grundlage von Wahrscheinlichkeiten entwickelt.
Ein Fuzzer ist ein automatischer Testgenerator: Er generiert künstliche Ausführungen der gegebenen Software, um potenzielle Schwachstellen für Angriffe zu erkennen. Der Fuzzer liefert zufällige, unerwartete Daten, um zu sehen, wie das Computerprogramm reagiert. Diese Technik ist zwar aufgrund ihrer Automatisierung deutlich schneller als andere Methoden, aber das Nichtauffinden von Fehlern nach wiederholten Tests bietet keine vollständige Garantie dafür, dass kein Fehler vorhanden ist. „Bei der empirischen Programmanalyse fragen wir uns oft, wie wahrscheinlich es ist, ein Programmverhalten zu beobachten, das noch nie zuvor beobachtet wurde. Unser Ansatz ermöglicht es uns, das Unbeobachtete zu quantifizieren.“ sagt Marcel Böhme, Fakultätsmitglied am MPI-SP.
Um die Wahrscheinlichkeit zu quantifizieren, dass ein neues, noch nie dagewesenes Verhalten eines Computerprogramms auftritt, greifen die Wissenschaftler am MPI-SP auf ein grundlegendes Wahrscheinlichkeitsproblem zurück: In einer Urne befindet sich eine große Anzahl von Kugeln in vielen verschiedenen Farben (die Verteilung der Farben ist nicht bekannt). Man zieht aus der Urne jeweils eine Kugel. Wie hoch nun ist die Wahrscheinlichkeit, dass man bei der N-ten Entnahme eine Kugel einer Farbe entnimmt, die man noch nie zuvor entnommen hat? In den Worten der Informatik: Wie hoch ist die Wahrscheinlichkeit, dass der Fuzzer beim N-ten Test ein neues, noch nie dagewesenes Verhalten beobachten kann?
„Der zentrale Beitrag unserer Arbeit besteht darin, genau zu quantifizieren, wie weit wir bei der Schätzung der Wahrscheinlichkeit von unbekannten Ereignissen auf der Grundlage beobachteter Daten gehen können“, erklärt Seongmin Lee, Postdoc am MPI-SP. Der Good-Turing-Schätzer ist zwar eine bekannte Lösung für dieses Problem, geht jedoch von einem bestimmten Wahrscheinlichkeitsmodell aus, das nicht zum typischen Verhaltensraum von Software passt. Das MPI-SP-Team hat einen neuen Schätzer entwickelt, der unter dem Multinomialmodell deutlich weniger verzerrt ist und besser widerspiegelt, wie Softwaretests das Programmverhalten untersuchen. „Unsere Theorie bietet eine Möglichkeit, Schätzer zu entwerfen, die auf eine bestimmte Verteilung zugeschnitten sind, aber dennoch in einem allgemeinen, verteilungsfreien Rahmen verankert sind“, sagt Lee.
Die Wissenschaftler veröffentlichten ihren Schätzer auf der Thirteenth International Conference on Learning Representations in Singapur. Die Arbeit wurde als „Spotlight“ für die Veranstaltung anerkannt.