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).