Mit der automatischen Entdeckung von mehr als 100 Schwachstellen in vier großen Datenbanken an einem Tag gewann die Forschung der Zhejiang-Universität den besten Artikel bei SIGMOD 2023

Die 2023 ACM SIGMOD/PODS International Conference on Data Management (SIGMOD 2023) findet vom 18. bis 23. Juni Ortszeit in Seattle, USA, statt. Kürzlich gab die Konferenz die Liste der besten Beiträge bekannt, wobei „Predicate Pushdown for Data Science Pipelines“ von Microsoft Research und „Detecting Logic Bugs of Join Optimizations in DBMS“ von der Zhejiang University als Sieger hervorgingen. Dies ist das erste Mal seit ihrer Gründung im Jahr 1975, dass ein Forschungsteam aus Festlandchina den Preis für den besten Beitrag der Konferenz gewonnen hat. Unter anderem schlug eine Forschung der Universität Zhejiang eine neuartige Methode vor, die automatisch logische Schwachstellen in Datenbankverwaltungssystemen wie MySQL, MariaDB, TiDB und PolarDB erkennen kann.

In den letzten Jahrzehnten haben sich moderne Datenbankmanagementsysteme (DBMS) weiterentwickelt, um eine Vielzahl neuer Architekturen wie Cloud-Plattformen und HTAP zu unterstützen, die eine immer komplexere und anspruchsvollere Optimierung der Abfrageauswertung erfordern. Der Abfrageoptimierer gilt als eine der komplexesten und wichtigsten Komponenten in einem DBMS. Seine Funktion besteht darin, die eingegebene SQL-Abfrage zu analysieren und dann mithilfe des integrierten Kostenmodells einen effizienten Ausführungsplan zu generieren. Fehler bei der Implementierung des Abfrageoptimierers können zu Schwachstellen (Bugs) führen, einschließlich Absturzschwachstellen und Logiklücken. Absturzschwachstellen sind leicht zu erkennen, da ein Absturz dazu führt, dass das System sofort stoppt. Allerdings werden logische Schwachstellen leicht übersehen, da sie dazu führen können, dass das DBMS fehlerhafte Ergebnismengen zurückgibt, die schwer zu erkennen sind. Dieses Papier konzentriert sich auf die Erkennung dieser stillen Schwachstellen.

Es gibt einen neuen Ansatz zur Erkennung logischer Schwachstellen in DBMS, nämlich Pivoted Query Synthesis (PQS). Die Kernidee dieser Methode besteht darin, zufällig eine Pivot-Zeile (Pivot-Zeile) aus der Tabelle auszuwählen und dann eine Abfrage mit dieser Zeile als Ergebnis zu generieren. Wenn eine synthetisierte Abfrage diese Datenzeile nicht zurückgeben kann, wurde eine logische Schwachstelle erkannt. PQS wird hauptsächlich zur Unterstützung von Optionsabfragen in einer einzelnen Tabelle verwendet, und 90 % der gemeldeten Schwachstellen betreffen nur Abfragen einzelner Tabellen. Bei Abfragen mit mehreren Tabellen, die unterschiedliche Join-Algorithmen und Join-Strukturen verwenden (die fehleranfälliger sind als Abfragen mit einer Tabelle), besteht noch immer eine große Forschungslücke.

Die folgende Abbildung zeigt die logische Schwachstelle von zwei Join-Abfragen in MySQL. Beide Schwachstellen können mit den in diesem Artikel vorgeschlagenen neuen Tools erkannt werden.

Abbildung 1: Beispiel einer logischen Schwachstelle bei der Join-Optimierung in DBMS

Abbildung 1 (a) zeigt eine logische Schwachstelle bei der Hash-Join in MySQL 8.0.18. In diesem Beispiel gibt die erste Abfrage den richtigen Ergebnissatz zurück, da sie mithilfe eines Block-Nested-Loop-Joins ausgeführt wird. Die zweite Abfrage mit einem inneren Hash-Join ging jedoch schief und gab einen fälschlicherweise leeren Ergebnissatz zurück. Dies liegt daran, dass der zugrunde liegende Hash-Join-Algorithmus fälschlicherweise davon ausgeht, dass 0 nicht gleich –0 ist.

Die logische Schwachstelle in Abbildung 1 (b) entsteht durch die Semi-Join-Verarbeitung in MySQL 8.0.28. In der ersten Abfrage konvertiert der Nested-Loop-Inner-Join den Datentyp varchar in bigint, was zu der korrekten Ergebnismenge führt. Beim Ausführen der zweiten Abfrage mithilfe eines Hash-Semi-Joins wird der Datentyp varchar in double konvertiert, was zu einem Verlust an Datengenauigkeit und Fehlern bei äquivalenten Vergleichen führt.

Die Verwendung der Abfragesynthesemethode zur Erkennung logischer Schwachstellen bei Mehrtabellen-Join-Abfragen ist weitaus schwieriger als bei Einzeltabellenabfragen. Dies bringt zwei Herausforderungen mit sich:

• Ergebnisüberprüfung: Um die Richtigkeit der Abfrageergebnisse zu überprüfen, verwendete die vorherige Methode eine Differenzteststrategie. Die Idee besteht darin, unterschiedliche physische Ausführungspläne (die Art und Weise, wie das Datenbanksystem Abfrageanweisungen tatsächlich ausführt) zur Verarbeitung von Abfragen zu verwenden. Wenn diese Pläne inkonsistente Ergebnismengen zurückgeben, wurde möglicherweise ein Logikfehler erkannt. Allerdings hat die differenzielle Prüfmethode zwei Nachteile. Erstens können bestimmte logische Schwachstellen mehrere physische Ausführungspläne beeinträchtigen und dazu führen, dass alle das gleiche fehlerhafte Ergebnis liefern. Zweitens wird es bei inkonsistenten Ergebnissätzen kostspielig, manuell zu überprüfen, welcher Ausführungsplan das richtige Ergebnis generiert hat. Eine mögliche Lösung für dieses Problem besteht darin, Ground-Truth-Ergebnisse für beliebige Testabfragen zu erstellen, aber vorhandene Tools unterstützen diesen Vorgang nicht.
• Suchraum: Für ein bestimmtes Datenbankschema kann die Anzahl der Join-Abfragen skaliert werden exponentiell mit der Anzahl der Tabellen und Spalten. Da es unmöglich ist, alle möglichen Abfragen zur Überprüfung aufzuzählen, ist ein effektiver Mechanismus zur Erkundung des Abfrageraums erforderlich, damit wir logische Schwachstellen so effizient wie möglich erkennen können.

Als Reaktion auf die oben genannten Probleme schlugen Forscher der Zhejiang-Universität eine Methode namens Transformed Query Synthesis (TQS) vor. TQS ist ein neues, universelles und kostengünstiges Tool zur Erkennung logischer Schwachstellen bei der Join-Optimierung in DBMS.

Als Reaktion auf die erste oben genannte Herausforderung ist die von Forschern vorgeschlagene Lösung DSG, also datengesteuerte Schema- und Abfragegenerierung (datengesteuerte Schema- und Abfragegenerierung) . Bei einem als breite Tabelle dargestellten Datensatz kann DSG den Datensatz basierend auf dem erkannten Paradigma in mehrere Tabellen aufteilen. Um die Entdeckung von Schwachstellen zu beschleunigen, fügt DSG auch einige künstliche Rauschdaten in die generierte Datenbank ein. Konvertieren Sie zunächst das Datenbankschema in ein Diagramm, in dem Knoten Tabellen/Spalten und Kanten Beziehungen zwischen Knoten sind. DSG verwendet Random Walks im Musterdiagramm, um Tabellen für die Abfrage auszuwählen, und verwendet diese Tabellen dann zum Generieren von Verknüpfungen. Für eine bestimmte Join-Abfrage mit mehreren Tabellen können wir das wahre Ergebnis leicht aus der breiten Tabelle ermitteln. Auf diese Weise kann DSG effektiv (Abfrage-, Ergebnis-)Sammlungen für die Datenbankvalidierung generieren.

Als Reaktion auf die zweite oben genannte Herausforderung ist die von den Forschern entwickelte Methode KQE, die wissensbasierte Query-Space-Exploration (wissensgesteuerte Query-Space-Exploration). Der Ansatz beginnt mit der Erweiterung des Musterdiagramms zu einem planiterativen Diagramm, das den gesamten Abfragegenerierungsraum darstellt. Jede Join-Abfrage wird dann als Untergraph dargestellt. Um das generierte Abfragediagramm zu bewerten, verwendet KQE einen einbettungsbasierten Diagrammindex, der den bereits erforschten Raum nach strukturell ähnlichen Abfragediagrammen durchsucht. Der Random-Walk-Abfragegenerator wird basierend auf dem Coverage-Score angeleitet, so viel wie möglich vom unbekannten Abfrageraum zu erkunden.

Um die Vielseitigkeit und Wirksamkeit der Methode zu zeigen, bewerteten die Forscher TQS auf vier häufig verwendeten DBMS: MySQL, MariaDB, TiDB und PolarDB. Nach einer Laufzeit von 24 Stunden hat TQS 115 Schwachstellen erfolgreich gefunden, darunter 31 in MySQL, 30 in MariaDB, 31 in TiDB und 23 in PolarDB. Durch die Analyse der Grundursachen können die Typen dieser Schwachstellen zusammengefasst werden, darunter 7 Schwachstellentypen in MySQL, 5 Typen in MariaDB, 5 Typen in TiDB und 3 Typen in PolarDB. Die Forscher haben die entdeckten Schwachstellen an die entsprechenden Communities weitergeleitet und positives Feedback erhalten.

Im Folgenden werden das zu lösende Problem und die von der Zhejiang-Universität vorgeschlagene Lösung in mathematischer Form beschrieben.

Problemdefinition

Es gibt zwei Arten von Datenbankschwachstellen: Abstürze und logische Schwachstellen. Absturzschwachstellen entstehen durch die Ausführung des Betriebssystems und des DBMS. Sie können dazu führen, dass das DBMS aus Gründen wie unzureichenden Ressourcen wie Speicher oder Zugriff auf eine ungültige Speicheradresse zwangsweise beendet wird. Daher können Absturzschwachstellen leicht entdeckt werden. Logikschwachstellen sind viel schwieriger zu finden, da die Datenbank weiterhin normal läuft, Abfragen verarbeitet und scheinbar korrekte Ergebnisse zurückgibt (was in den meisten Fällen auch der Fall ist, aber in einigen Fällen kann es sein, dass sie einen falschen Ergebnissatz liest). Diese stillen Schwachstellen ähneln unsichtbaren Bomben und sind gefährlicher, da sie schwer zu erkennen sind und die Korrektheit der Anwendung beeinträchtigen können.

In diesem Artikel wird ein Abfrageoptimierer vorgestellt, mit dem logische Schwachstellen bei Problemen mit Multi-Table-Join-Abfragen erkannt werden können. Forscher nennen diese Schwachstellen „Join Optimization Bugs“. Unter Verwendung der in Tabelle 1 angegebenen Notation kann das Problem der Schwachstellenerkennung bei der Join-Optimierung formal wie folgt definiert werden:

Definition: Lassen Sie den Abfrageoptimierer für jede Abfrage qi in der Abfragearbeitslast Q qi durch die Verkettung mehrerer tatsächlicher Pläne ausführen und überprüfen Ergebnismenge unter Verwendung der Grundwahrheit . Wenn , wurde eine Sicherheitslücke bei der Verbindungsoptimierung entdeckt.

Tabelle 1: Symbolbeschreibungstabelle

Projektübersicht

Abbildung 2 gibt den Architekturüberblick von TQS. Ausgehend von einem Basisdatensatz und einem Ziel-DBMS sucht TQS nach möglichen logischen Schwachstellen im DBMS, indem es Abfragen basierend auf dem Datensatz generiert. TQS besteht aus zwei Schlüsselkomponenten: datengesteuerte Schema- und Abfragegenerierung (DSG) und wissensgesteuerte Abfrageraumexploration (KQE)

Abbildung 2: TQS-Übersicht

DSG Die Der Eingabedatensatz wird als breite Tabelle behandelt. Zusätzlich zu den ursprünglichen Tupeln synthetisiert DSG absichtlich auch einige Tupel mit fehleranfälligen Werten (z. B. Nullwerten oder sehr langen Zeichenfolgen). Für Join-Abfragen erstellt DSG ein neues Schema für die breite Tabelle, indem es die breite Tabelle in mehrere Tabellen aufteilt und so sicherstellt, dass die Tabellen einem auf funktionalen Abhängigkeiten basierenden Paradigma entsprechen. DSG modelliert das Datenbankschema als Diagramm und generiert dann logische/konzeptionelle Abfragen durch zufällige Spaziergänge auf dem Schemadiagramm. Ein DSG materialisiert eine logische Abfrage in einen physischen Ausführungsplan und wandelt die Abfrage mit unterschiedlichen Hinweisen um, sodass das DBMS mehrere verschiedene physische Ausführungspläne ausführen kann, um nach Schwachstellen zu suchen. Bei einer Join-Abfrage wird das Ground-Truth-Ergebnis durch Zurückabbilden des Join-Diagramms auf die breite Tabelle ermittelt.

Nach Abschluss der Mustereinrichtung und Datenaufteilung erweitert KQE das Musterdiagramm zu einem Planungsiterationsdiagramm. Jede Abfrage wird als Untergraph dargestellt. KQE erstellt einen einbettungsbasierten Diagrammindex für die Einbettungen des Abfragediagramms im Verlauf (d. h. innerhalb des bereits untersuchten Abfrageraums). Intuitiv besteht die Rolle von KQE darin, sicherzustellen, dass der neu generierte Abfragegraph so weit wie möglich von seinen nächsten Nachbarn im Verlauf entfernt ist, d. h. es geht darum, neue Abfragegraphen zu erkunden, anstatt vorhandene Abfragegraphen zu wiederholen. KQE erreicht dies, indem es das generierte Abfragediagramm auf der Grundlage struktureller Ähnlichkeit bewertet (zu Abfragediagrammen im Verlauf) und gleichzeitig eine adaptive Random-Walk-Methode zum Generieren von Abfragen verwendet. .

Algorithmus 1 fasst die Kernidee von TQS zusammen, wobei die Zeilen 2, 10 und 12 DSG und die Zeilen 4, 8 und 9 KQE sind.

Anhand eines Datensatzes und einer breiten Tabelle aus teilt DSG eine einzelne breite Tabelle in mehrere Tabellen auf, die ein 3NF-kompatibles Datenbankschema bilden (Zeile 2). Ein Muster kann als Diagramm betrachtet werden, wobei Tabellen und Spalten Eckpunkte sind und Kanten Beziehungen zwischen Eckpunkten darstellen. DSG verwendet einen Random Walk on , um einen Join-Ausdruck der Abfrage zu generieren (Zeile 10). Tatsächlich können Join-Abfragen als Untergraphen von projiziert werden. Durch die Zuordnung des Untergraphen zurück zur breiten Tabelle kann DSG das Ground-Truth-Ergebnis für diese Abfrage leicht abrufen (Zeile 12).

KQE erweitert das Musterdiagramm zu einem Planungsiterationsdiagramm (Zeile 4). Um das Testen ähnlicher Pfade zu vermeiden, erstellt KQE einen einbettungsbasierten Diagrammindex

, um die Einbettungen des vorhandenen Abfragediagramms zu indizieren (Zeile 9). KQE aktualisiert das Kantengewicht π des Planungsiterationsgraphen G basierend auf der strukturellen Ähnlichkeit zwischen dem aktuellen Abfragegraphen und dem vorhandenen Abfragegraphen (Zeile 8). KQE bewertet den nächstmöglichen Pfad, der den Random-Walk-Generator leitet, und erforscht dabei bevorzugt den unbekannten Abfrageraum.

Für eine Abfrage transformiert TQS die Abfrage über den Hinweissatz , um mehrere verschiedene tatsächliche Abfragepläne auszuführen (Zeile 11). Abschließend wird die Ergebnismenge der Abfrage

mit der Grundwahrheit verglichen (Zeile 14). Wenn sie inkonsistent sind, wurde eine Schwachstelle bei der Join-Optimierung entdeckt (Zeile 15).

Für detailliertere Beschreibungen von DSG und KQE lesen Sie bitte das Originalpapier.

Experimentelle Ergebnisse

TQS hat erfolgreich einige logische Schwachstellen in Datenbankverwaltungssystemen wie MySQL, MariaDB, TiDB und PolarDB gefunden. Darunter sind die Schwachstellen von MySQL sind: Es gibt 7 Typen, MariaDB hat 5 Typen, TiDB hat 5 Typen und PolarDB hat 3 Typen, wie in der Tabelle unten gezeigt.

Im Vergleich zu anderen Methoden ist die Gesamtleistung des von der Universität Zhejiang vorgeschlagenen TQS in vielerlei Hinsicht ebenfalls recht beeindruckend Es wurden deutlich bessere Ergebnisse erzielt und die Wirksamkeit jeder Komponente wurde auch durch kontrollierte Variablenexperimente überprüft.

Aber Forscher sagten auch, dass sich TQS derzeit auf Equi-Join-Abfragen konzentriert. Dennoch können die DSG- und KQE-Ideen auch auf den Fall von Non-Equijoins ausgeweitet werden. Die einzige Schwierigkeit besteht darin, die Ergebnisse der Abfragewahrheit zu generieren und zu verwalten. Bei Non-Equijoins nimmt die Größe dieser Ergebnisse exponentiell zu. Dieser Aspekt bedarf in Zukunft noch weiterer Forschung.

Das obige ist der detaillierte Inhalt vonMit der automatischen Entdeckung von mehr als 100 Schwachstellen in vier großen Datenbanken an einem Tag gewann die Forschung der Zhejiang-Universität den besten Artikel bei SIGMOD 2023. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!