450 logische Fehler in populären Datenbanken aufgespürt

Wenn eine Adresse im Smartphone abgespeichert ist, gehen wir wie selbstverständlich davon aus, dass wir sie mit der richtigen Abfrage auch finden. Genauso wie mit den geeigneten Begriffen alle passenden Artikel im Webshop aufgelistet werden. Bloss: So selbstverständlich, wie wir meinen, ist das nicht. Ein logischer Fehler im Datenbank-Management-System (DBMS), in dem die gespeicherten Informationen verwaltet werden, kann falsche Antworten zurückliefern, ohne dass wir den Fehler überhaupt bemerken.

Überraschend viele Fehler in allen Systemen

Und genau derartige logische Fehler sind erstaunlich häufig. Oder besser gesagt, sie waren es bis vor kurzem. Forscher vom Advanced Software Technologies Lab der ETH Zürich haben jetzt nämlich ein Tool entwickelt, das automatisch logische Fehler in Datenbanksoftware aufspürt. Bereits konnten damit über 450 Programmierdefekte in weitverbreiteten Datenbanken gefunden und anschliessend behoben werden.

«Wir waren selbst überrascht, wie viele Fehler in gängigen Datenbank-Management-Systemen stecken», erläutert Manuel Rigger: «Mit unseren Methoden haben wir beispielsweise in der auf fast allen Smartphones und auch in vielen Web-Browsern laufenden SQLite-Datenbank über 150 Programmfehler entdeckt. Und das ist kein extremer Fall. Die Quote ist in allen Systemen, die wir bisher untersucht haben, ähnlich gross.»

Komplexe Programme und kaum erkennbare Bugs

Dass die ETH-Informatiker derart viele Bugs finden, hat zwei Hauptgründe. Zum einen sind heutige Datenbanken sehr komplex und können mehrere Millionen Zeilen Programm-Code umfassen. Da ist es praktisch unvermeidlich, dass Widersprüche entstehen und Programmierfehler passieren. Zum anderen sind logische Fehler nicht so einfach zu finden. Im Gegensatz zu Bugs, die das System abstürzen lassen, äussern sie sich nur selten offensichtlich. In der Regel ist ein Vergleich mit dem richtigen Ergebnis nötig, um sie zu bemerken. Genau das war bisher nur mit viel Aufwand möglich.

Das bis anhin einzige in der Praxis genutzte automatisierte Testverfahren ist bereits vor über 20 Jahren entworfen worden. Es beruht auf dem Vergleich von Abfragen mit unterschiedlichen Datenbanksystemen. Da jeder Hersteller spezifische Erweiterungen und Anpassungen am Abfrage-Standard SQL (Structured Query Language) vornimmt, ist das Formulieren von eindeutig vergleichbaren Fragen inzwischen aber auf einen kleinen Kernbereich der Systeme beschränkt. Die Abfragesprachen der Hersteller unterscheiden sich nämlich ähnlich wie die Dialekte einer menschlichen Sprache zum Teil erheblich.

Zwei Wochen Arbeit verloren

Persönlich vermutet Rigger zudem noch einen dritten Grund, wieso den Fehlern bisher nicht mit mehr Entschlossenheit nachgegangen wurde: Im Datenbankbereich konzentrieren sich derzeit die Aktivitäten darauf, die Systeme mit Methoden der künstlichen Intelligenz wie maschinellem Lernen noch leistungsfähiger zu machen. Daneben erscheint die Fehlersuche naturgemäss wenig attraktiv.

Rigger selbst hat seine Wurzeln im Software-Testing und in der Entwicklung von Compilern, mit denen verschiedene Programmier- und Maschinensprachen ineinander übersetzt werden können. Aufmerksam geworden auf die Fehler-Problematik im Datenbankbereich ist er durch eigene ärgerliche Erfahrungen, als wegen eines Fehlers im Datenbank-Management-System zwei Wochen Arbeit verloren gingen.

Drei Methoden für drei Fehlertypen

In der Folge hat sich der Testing-Spezialist gemeinsam mit dem Leiter des Advanced Software Technologies Lab, Zhendong Su, dem Problem angenommen. Ihre Lösung besteht in drei unterschiedlichen Methoden, mit denen sich zuverlässige Vergleichsabfragen finden lassen. Bei sogenannten «Query Partitioning» werden Abfragen automatisiert in mehrere Teile zerlegt und dann kontrolliert, ob das Ganze und die Summe der Teile das Gleiche ergeben.

Mit der zweiten Methode lassen sich gezielt Fehler aufspüren, die durch Optimierungs-Mechanismen in den Datenbanken hervorgerufen werden. Dabei werden die Abfragen für den Vergleich so abgewandelt, dass der Optimierungsmechanismus nicht mehr funktionieren kann.

Im Gegensatz zur den ersten zwei Methoden, die auch ohne detaillierte Kenntnisse der fraglichen Datenbank automatisiert durchgeführt werden können, verlangt die dritte ein spezifisches Datenbankwissen und auch eine individuelle Implementierung des Vergleichs. Bei der sogenannten «Pivoted Query Synthesis» wird eine ganze Reihe in der relationalen Datenbanktabelle zufällig ausgewählt. Danach muss eine Abfrage erstellt werden, welche die gewählte Reihe zum Ergebnis hat. So können logische Fehler wesentlich effizienter identifiziert werden, als wenn wie bisher einzelne Einträge von Hand analysiert werden müssen.

Tool ist bereits bei Herstellern im Einsatz

Mit ihren Methoden und dem Tool SQLancer, in welchem diese automatisiert wurden, haben die ETH-Informatiker offensichtlich schlafende Geister geweckt. Das Interesse der Datenbank-Hersteller ist ausgesprochen gross. Obwohl die drei Verfahren bisher nur informell als Preprints und über Social Media kommuniziert wurden und erst in diesen Tagen an einschlägigen Fachkonferenzen offiziell vorgestellt werden, haben bereits mehrere Hersteller angefangen, ihre Software damit zu testen. «Diverse Hersteller haben bereits zahlreiche Bugs in ihren Systemen gefunden und den SQLancer fest in ihr Testing eingebaut,» weiss Rigger aus vielen direkten Kontakten: «Einige haben auch Programmiercode zu unserem als Open Source veröffentlichten Projekt beigesteuert oder das Tool an ihre spezifischen Bedürfnisse angepasst und erweitert.»

Die «Pivoted Query Synthesis» wurde der Forscher-Community am 5. November an der Systeme-Software-Tagung externe Seite OSDI (Operating Systems Design and Implementation) vorgestellt. Die Optimierungsfehler-Methode wird am 13. November im Rahmen des 28^th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (externe Seite ESEC/FSE) präsentiert, und das «Query Partitioning» am 18. November an der Programmiersprachenkonferenz externe Seite OOPLSA (Object-Oriented Programming, Systems, Languages, and Applications).