Plus de 100 vulnérabilités découvertes automatiquement dans quatre bases de données majeures en une journée, les recherches de l'Université du Zhejiang ont remporté le meilleur article du SIGMOD 2023

La Conférence internationale ACM SIGMOD/PODS 2023 sur la gestion des données (SIGMOD 2023) se tiendra à Seattle, aux États-Unis, du 18 au 23 juin, heure locale. Récemment, la conférence a annoncé la liste des meilleurs articles, avec les gagnants « Predicate Pushdown for Data Science Pipelines » de Microsoft Research et « Detecting Logic Bugs of Join Optimizations in DBMS » de l'Université du Zhejiang. C'est la première fois qu'une équipe de recherche de Chine continentale remporte le prix du meilleur article lors de la conférence depuis sa création en 1975. Parmi eux, des recherches de l'Université du Zhejiang ont proposé une nouvelle méthode capable de découvrir automatiquement les vulnérabilités logiques des systèmes de gestion de bases de données tels que MySQL, MariaDB, TiDB et PolarDB.

Au cours des dernières décennies, les systèmes de gestion de bases de données (SGBD) modernes ont continué d'évoluer pour prendre en charge une variété de Les nouvelles architectures, telles que les plateformes cloud et HTAP, nécessitent une optimisation de plus en plus sophistiquée de l'évaluation des requêtes. L'optimiseur de requêtes est considéré comme l'un des composants les plus complexes et les plus importants d'un SGBD. Sa fonction est d'analyser la requête SQL d'entrée, puis de générer un plan d'exécution efficace à l'aide du modèle de coût intégré. Les erreurs dans la mise en œuvre de l'optimiseur de requêtes peuvent entraîner des vulnérabilités (bugs), notamment des vulnérabilités de crash et des trous logiques. Les vulnérabilités en cas de crash sont faciles à détecter car un crash provoque l'arrêt immédiat du système. Cependant, les vulnérabilités logiques sont facilement négligées car elles peuvent amener le SGBD à renvoyer des ensembles de résultats incorrects, difficiles à détecter. Cet article se concentre sur la détection de ces vulnérabilités silencieuses.

Il existe une approche émergente dans la détection des vulnérabilités logiques dans les SGBD, à savoir la synthèse de requêtes pivotées (PQS). L'idée principale de cette méthode est de sélectionner aléatoirement une ligne pivot (ligne pivot) dans le tableau, puis de générer une requête avec cette ligne comme résultat. Si une requête synthétisée ne peut pas renvoyer cette ligne de données, une vulnérabilité logique a été détectée. PQS est principalement utilisé pour prendre en charge les requêtes d'options dans une seule table, et 90 % de ses vulnérabilités signalées impliquent uniquement des requêtes sur une seule table. Il existe encore un grand déficit de recherche sur les requêtes multi-tables qui utilisent différents algorithmes de jointure et structures de jointure (qui sont plus sujettes aux erreurs que les requêtes à table unique).

La figure suivante montre deux failles logiques dans la connexion des requêtes dans MySQL. Les deux vulnérabilités peuvent être détectées à l'aide des nouveaux outils proposés dans cet article.

Figure 1 : Exemple de vulnérabilité logique dans l'optimisation des jointures dans un SGBD #🎜 🎜 #

La figure 1 (a) montre une vulnérabilité logique dans la jointure de hachage dans MySQL 8.0.18. Dans cet exemple, la première requête renvoie le jeu de résultats correct car elle est exécutée à l’aide d’une jointure de boucle imbriquée par blocs. Cependant, la deuxième requête utilisant une jointure par hachage interne a mal tourné et a renvoyé un jeu de résultats incorrectement vide. En effet, l’algorithme de jointure par hachage sous-jacent suppose à tort que 0 n’est pas égal à −0.

La vulnérabilité logique de la figure 1 (b) provient du traitement de semi-jointure dans MySQL 8.0.28. Dans la première requête, la jointure interne de la boucle imbriquée convertit le type de données varchar en bigint, ce qui donne le jeu de résultats correct. Lors de l'exécution de la deuxième requête à l'aide d'une semi-jointure de hachage, le type de données varchar sera converti en double, entraînant une perte de précision des données et des erreurs dans les comparaisons équivalentes.

Utiliser une méthode de synthèse de requêtes pour détecter les vulnérabilités logiques dans les requêtes de jointure multi-tables est bien plus difficile que les requêtes mono-tables. Cela implique deux défis : .

• Vérification des résultats : afin de vérifier l'exactitude des résultats de la requête, la méthode précédente utilisait une stratégie de tests différentiels. L'idée est d'utiliser différents plans d'exécution physique (la manière dont le système de base de données exécute réellement les instructions de requête) pour traiter les requêtes. Si ces plans renvoient des ensembles de résultats incohérents, un défaut logique peut avoir été détecté. Cependant, la méthode de test différentiel présente deux inconvénients. Premièrement, certaines vulnérabilités logiques peuvent affecter plusieurs plans d’exécution physique et les amener tous à produire le même résultat erroné. Deuxièmement, lorsque des ensembles de résultats incohérents sont observés, il devient coûteux de vérifier manuellement quel plan d'exécution a généré le résultat correct. Une solution possible à ce problème consiste à construire des résultats de vérité sur le terrain pour des requêtes de test arbitraires, mais les outils existants ne prennent pas en charge cette opération.
• Espace de recherche : pour un schéma de base de données donné, le nombre de requêtes de jointure pouvant être générées évolue ; exponentiellement avec le nombre de tables et de colonnes. Puisqu’il est impossible d’énumérer toutes les requêtes possibles à vérifier, un mécanisme efficace d’exploration de l’espace de requêtes est nécessaire pour nous permettre de détecter les vulnérabilités logiques aussi efficacement que possible.

En réponse aux problèmes ci-dessus, des chercheurs de l'Université du Zhejiang ont proposé une méthode appelée Transformed Query Synthesis (TQS). TQS est un nouvel outil universel et rentable pour la tâche de détection des vulnérabilités logiques dans l'optimisation des jointures dans les SGBD.

En réponse au premier défi ci-dessus, la solution proposée par les chercheurs est DSG, qui est Data-guided Schema and query Generation (Data-guided Schema and query Generation) . Étant donné un ensemble de données représenté sous la forme d'un tableau large, DSG peut diviser l'ensemble de données en plusieurs tableaux en fonction du paradigme détecté. Pour accélérer la découverte des vulnérabilités, DSG injecte également des données de bruit artificiel dans la base de données générée. Tout d’abord, convertissez le schéma de la base de données en un graphique, où les nœuds sont des tables/colonnes et les bords sont des relations entre les nœuds. DSG utilise des parcours aléatoires sur le graphique de modèles pour sélectionner les tables pour la requête, puis utilise ces tables pour générer des jointures. Pour une requête de jointure spécifique impliquant plusieurs tables, nous pouvons facilement trouver le résultat véridique à partir de la table large. De cette manière, DSG peut générer efficacement des collections (requête, résultat) pour la validation de la base de données.

En réponse au deuxième défi ci-dessus, la méthode conçue par les chercheurs est KQE, qui est l'exploration de l'espace de requête guidée par les connaissances (Exploration de l'espace de requête guidée par les connaissances). L'approche commence par étendre le graphe de modèles en un graphe plan-itératif, qui représente l'intégralité de l'espace de génération de requêtes. Chaque requête de jointure est ensuite représentée sous forme de sous-graphe. Pour évaluer le graphique de requête généré, KQE utilise un index de graphique basé sur l'intégration qui recherche dans l'espace déjà exploré des graphiques de requête structurellement similaires. Le générateur de requêtes à marche aléatoire est guidé en fonction du score de couverture pour explorer autant que possible l'espace de requête inconnu.

Pour montrer la polyvalence et l'efficacité de la méthode, les chercheurs ont évalué TQS sur quatre SGBD couramment utilisés : MySQL, MariaDB, TiDB et PolarDB. Après 24 heures d'exécution, TQS a réussi à trouver 115 vulnérabilités, dont 31 dans MySQL, 30 dans MariaDB, 31 dans TiDB et 23 dans PolarDB. En analysant les causes profondes, les types de ces vulnérabilités peuvent être résumés, parmi lesquels il existe 7 types de vulnérabilités dans MySQL, 5 types dans MariaDB, 5 types dans TiDB et 3 types dans PolarDB. Les chercheurs ont soumis les vulnérabilités découvertes aux communautés appropriées et ont reçu des commentaires positifs.

Le problème à résoudre et la solution proposée par l'Université du Zhejiang seront décrits sous forme mathématique ci-dessous.

Définition du problème

Il existe deux types de vulnérabilités de bases de données : les plantages et les vulnérabilités logiques. Les vulnérabilités aux crashs proviennent de l'exécution du système d'exploitation et du SGBD. Ils peuvent provoquer l'arrêt forcé du SGBD pour des raisons telles que des ressources insuffisantes telles que la mémoire ou l'accès à une adresse mémoire non valide. Par conséquent, les vulnérabilités en cas de crash sont facilement découvertes. Les vulnérabilités logiques sont beaucoup plus difficiles à trouver car la base de données fonctionnera toujours normalement, traitera les requêtes et retournera des résultats apparemment corrects (et la plupart du temps, elles le font, mais dans quelques cas, elles peuvent lire un ensemble de résultats incorrect). Ces vulnérabilités silencieuses sont comme des bombes invisibles et sont plus dangereuses car difficiles à détecter et peuvent affecter l'exactitude de l'application.

Cet article présente un optimiseur de requêtes pour détecter les vulnérabilités logiques pour les problèmes de requêtes de jointure multi-tables. Les chercheurs appellent ces vulnérabilités des bugs d’optimisation. En utilisant la notation donnée dans le tableau 1, le problème de détection de vulnérabilité d'optimisation de jointure peut être formellement défini comme :

Définition : Pour chaque requête qi dans la charge de travail de requête Q , provoquant le optimiseur de requêtes pour effectuer une jointure de qi à travers plusieurs plans réels et valider son ensemble de résultats en utilisant la vérité terrain . Si , une vulnérabilité d'optimisation de connexion a été découverte.

Tableau 1 : Tableau de description des symboles

Aperçu du projet

La figure 2 donne un aperçu architectural de TQS. Étant donné un ensemble de données de base et un SGBD cible, TQS recherche d'éventuelles vulnérabilités logiques dans le SGBD en générant des requêtes basées sur l'ensemble de données. TQS comporte deux composants clés : la génération de schémas et de requêtes guidée par les données (DSG) et l'exploration de l'espace de requête guidée par les connaissances (KQE). Figure 2 : Présentation de TQS DSG traite l'ensemble de données d'entrée comme une table large et, en plus des tuples d'origine, DSG synthétise délibérément certains tuples avec des valeurs sujettes aux erreurs (telles que des valeurs nulles ou des chaînes très longues). Pour les requêtes de jointure, DSG crée un nouveau schéma pour la table large en divisant la table large en plusieurs tables, garantissant ainsi que les tables sont conformes à un paradigme basé sur les dépendances fonctionnelles. DSG modélise le schéma de la base de données sous forme de graphique, puis génère des requêtes logiques/conceptuelles via des parcours aléatoires sur le graphique du schéma. Un DSG matérialisera une requête logique en un plan d'exécution physique et transformera la requête avec différents indices, permettant au SGBD d'exécuter plusieurs plans d'exécution physique différents pour rechercher des vulnérabilités. Pour une requête de jointure, le résultat de la vérité terrain est obtenu en mappant le graphique de jointure sur la table large.

Après avoir terminé la configuration du modèle et le fractionnement des données, KQE développe le diagramme de modèle en un diagramme d'itération de planification. Chaque requête est représentée sous forme de sous-graphe. KQE construit un index de graphe basé sur l'intégration pour les intégrations du graphe de requête dans l'historique (c'est-à-dire dans l'espace de requête déjà exploré). Intuitivement, le rôle de KQE est de garantir que le graphique de requête nouvellement généré est aussi éloigné que possible de ses voisins les plus proches dans l'historique, c'est-à-dire qu'il s'agit d'explorer de nouveaux graphiques de requête plutôt que de répéter les graphiques de requête existants. KQE le fait en notant le graphique de requête généré en fonction de la similarité structurelle (pour interroger les graphiques de l'historique) tout en utilisant une méthode de marche aléatoire adaptative pour générer des requêtes. .

L'algorithme 1 résume l'idée centrale de TQS, où les lignes 2, 10 et 12 sont DSG et les lignes 4, 8 et 9 sont KQE.

Étant donné un ensemble de données et un large tableau échantillonné à partir de #🎜 🎜# , DSG divise une seule table large en plusieurs tables. Ces tables forment un schéma de base de données conforme à 3NF ( ligne 2). Le modèle peut être considéré comme un graphique , où les tables et les colonnes sont des sommets et les arêtes représentent les relations entre les sommets. DSG utilise une marche aléatoire sur pour générer une expression de jointure de la requête (ligne 10). En fait, les requêtes de jointure peuvent être projetées sous forme de sous-graphes de . Le DSG peut facilement récupérer le résultat de la vérité terrain pour cette requête en mappant le sous-graphe sur la table large (ligne 12).

KQE Étendez le diagramme de modèle en un diagramme d'itération de planification (ligne 4). Pour éviter de tester des chemins similaires, KQE construira un index de graphique basé sur l'intégration pour indexer l'intégration de requête existante (ligne 9). KQE met à jour le poids de bord π du graphe d'itération de planification G en fonction de la similarité structurelle entre le graphe de requête actuel et le graphe de requête existant (ligne 8). KQE note le prochain chemin possible, qui guide le générateur de marche aléatoire, préférant ainsi explorer l'espace de requête inconnu.

Pour une requête

, TQS transforme la requête via le jeu d'invites pour exécuter plusieurs requêtes réelles différentes plans (ligne 11). Enfin, l'ensemble de résultats de la requête

est comparé à la valeur de vérité terrain (ligne 14) . S'ils sont incohérents, alors une vulnérabilité d'optimisation de jointure a été détectée (ligne 15).

Veuillez lire l'article original pour des descriptions plus détaillées de DSG et KQE.

Résultats expérimentaux

TQS a réussi à détecter certaines vulnérabilités logiques dans les systèmes de gestion de bases de données tels que MySQL, MariaDB, TiDB et PolarDB. Parmi elles, les vulnérabilités. de MySQL sont : Il existe 7 types, MariaDB a 5 types, TiDB a 5 types et PolarDB a 3 types, comme indiqué dans le tableau ci-dessous.

Par rapport à d'autres méthodes, la performance globale du TQS proposé par l'Université du Zhejiang est également assez impressionnante, dans de nombreux indicateurs Des résultats nettement meilleurs ont été obtenus et l'efficacité de chaque composant a également été testée au moyen d'expériences à variables contrôlées.

Mais les chercheurs ont également déclaré que TQS se concentre actuellement sur les requêtes d'équi-jointure. Néanmoins, les idées DSG et KQE peuvent également être étendues au cas des non-équijointures. La seule difficulté est de savoir comment générer et gérer les résultats de la vérité des requêtes : dans le cas de non-équijointures, la taille de ces résultats augmente de façon exponentielle. Cet aspect nécessite encore des recherches plus approfondies à l'avenir.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!