機器之心專欄

機器之心編輯部

本文中，浙大的研究者提出了一種名為 Transformed Query Synthesis（TQS）的方法。在運行了 24 小時后，TQS 成功找到了 115 個漏洞，包括 MySQL 中 31 個、MariaDB 中 30 個、TiDB 中 31 個、PolarDB 中 23 個。

(資料圖片)

2023 年度的 ACM SIGMOD/PODS 國際數據管理大會（SIGMOD 2023）將于當地時間 6 月 18-23 日在美國西雅圖舉辦。近日，該會議公布了最佳論文名單，微軟研究院的《Predicate Pushdown for Data Science Pipelines》和浙江大學的《Detecting Logic Bugs of Join Optimizations in DBMS》獲獎。自 1975 年該會議始辦以來，這是中國大陸研究團隊首次獲得該會議的最佳論文獎。其中浙大的研究提出了一種新穎的方法，可以自動發現 MySQL、MariaDB、TiDB 和 PolarDB 等數據庫管理系統的邏輯漏洞。

過去幾十年，現代數據庫管理系統（DBMS）不斷演進，可以支持多種不同的新架構，比如云平臺和 HTAP，這需要對查詢評估進行越來越復雜精細的優化。查詢優化器（query optimizer）被認為是 DBMS 中最復雜和最重要的組件之一，其功能是解析輸入的 SQL 查詢，然后在內置成本模型的協助下生成高效的執行方案。查詢優化器實現中的錯誤可能會導致出現漏洞（bug ) ，包括崩潰漏洞和邏輯漏洞。崩潰漏洞很容易檢測，因為崩潰會導致系統立即停止。然而邏輯漏洞卻容易被忽視，因為邏輯漏洞會導致 DBMS 返回難以檢測的錯誤結果集。這篇論文關注的重心是檢測這些無聲的漏洞。

在檢測 DBMS 中的邏輯漏洞方面有一種新興方法，即 Pivoted Query Synthesis（PQS）。該方法的核心思路是從表格中隨機選定一個樞軸數據行（pivot row），然后生成以該行作為結果的查詢。如果合成的任何查詢都不能返回該數據行，那么就檢測到了一個邏輯漏洞。PQS 主要用來支持單表中的選項查詢，其報告的漏洞中 90% 都是僅涉及單表查詢。對于使用不同連接算法和連接結構的多表查詢（比單表查詢更易出錯），還存在很大研究空白。

下圖展示了 MySQL 中連接查詢兩個的邏輯漏洞的。這兩個漏洞通過使用本文新提出的工具都能被檢測到。

圖 1：DBMS 中連接優化的邏輯漏洞示例

圖 1 ( a ) 展示了 MySQL 8.0.18 中的哈希連接（hash join）的一個邏輯漏洞。在這個示例中，第一個查詢返回了正確的結果集，因為其執行過程中使用了塊嵌套循環連接（block nested loop join）。但是，第二個查詢使用內部哈希連接（inner hash join）卻出了問題，返回的是一個不正確的空結果集。這是因為其底層的哈希連接算法錯誤地認定 0 不等于 0。

圖 1 ( b ) 中的邏輯漏洞源自 MySQL 8.0.28 中的半連接（semi-join）處理過程。在第一個查詢中，嵌套循環內部連接會將數據類型 varchar 轉換成 bigint，進而得到正確的結果集。而當使用哈希半連接執行第二個查詢時，數據類型 varchar 會被轉換成 double，從而導致數據準確度出現損失以及等值比較出錯。

為多表連接查詢的邏輯漏洞檢測問題采用查詢合成方法的難度遠遠超過單表查詢的情況，這涉及到的挑戰有兩個：

結果驗證：為了驗證查詢結果的正確性，之前的方法采用的是差分測試策略。其思路是使用不同的物理執行計劃（physical plan，即數據庫系統實際執行查詢語句的方式）來處理查詢。如果這些規劃返回的結果集不一致，那么就可能是檢測到了邏輯漏洞。但是，差分測試方法有兩個缺點。其一，某些邏輯漏洞可影響多個物理執行計劃并讓它們全部生成同樣的錯誤結果。其二，當觀察到不一致的結果集時，需要人工檢查生成正確結果的是哪一個執行計劃，從而導致成本開銷變得高昂。這個問題有一個可能的解決方案，即為任意測試查詢構建真值（ground-truth）結果，但現有的工具并不支持這種操作；

搜索空間：對于給定的數據庫模式，可生成的連接查詢的數量隨表格和列的數量呈指數級變化。由于我們不可能為了驗證而枚舉出所有可能的查詢，因此就需要一種有效的查詢空間探索機制，以便讓我們盡可能高效地檢測出邏輯漏洞。

針對以上難題，浙大的研究者提出了一種名為 Transformed Query Synthesis（TQS）的方法。在檢測 DBMS 中連接優化的邏輯漏洞任務上，TQS 是一種普適且成本高效的全新工具。

針對上述第一個挑戰，研究者提出的應對方法是 DSG，即數據驅動的模式和查詢生成（Data-guided Schema and query Generation）。給定表示為一個寬表數據集，DSG 可基于檢測到的范式將該數據集拆分為多個表格。為了加快發現漏洞的速度，DSG 還會向生成的數據庫中注入一些人工噪聲數據。首先，將該數據庫模式轉換成一個圖（graph），其中節點是表 / 列，邊是節點之間的關系。DSG 會在模式圖上使用隨機游走來為查詢選擇表格，然后再使用這些表格來生成連接（join）。對于涉及多表的特定連接查詢，我們可以輕松從寬表格中找到其真值結果。這樣一來，DSG 就能有效地為數據庫驗證生成 ( 查詢，結果 ) 集合 了。

針對上述第二個挑戰，研究者設計的方法是 KQE，即知識引導的查詢空間探索（Knowledge-guided Query space Exploration）。該方法首先是將模式圖擴展成一個規劃迭代圖（plan-iterative graph），其表示整個查詢生成空間。然后將每個連接查詢表示為一個子圖。為了給生成的查詢圖評分，KQE 采用了一種基于嵌入的圖索引，其可以在已經探索過的空間中搜索是否有結構相似的查詢圖。根據覆蓋度分數引導隨機游走查詢生成器，以盡可能多地探索未知的查詢空間。

為了展現該方法的通用性和有效性，研究者在四個常用 DBMS 上對 TQS 進行了評估：MySQL、MariaDB、TiDB 和 PolarDB。運行了 24 小時后，TQS 成功找到了 115 個漏洞，包括 MySQL 中 31 個、MariaDB 中 30 個、TiDB 中 31 個、PolarDB 中 23 個。通過分析根本原因，可歸納出這些漏洞的類型，其中 MySQL 中的漏洞有 7 種、MariaDB 有 5 種、TiDB 有 5 種、PolarDB 有 3 種。研究者已經將發現的漏洞提交給相應的社區并且收到了積極的反饋。

下面將通過數學形式描述所要解決的問題以及浙大提出的解決方案。

問題定義

數據庫的漏洞有兩種：崩潰和邏輯漏洞。崩潰漏洞來自于操作系統和 DBMS 的執行過程。它們會導致 DBMS 被強行終止，原因包括內存等資源不足或訪問了無效內存地址等。因此，崩潰漏洞很容易被發現。相較而言，邏輯漏洞則更難以發現，因為數據庫依然會正常運行，處理查詢后也會返回看似正確的結果（并且大多數情況下它們確實會返回正確結果，但在少數情況下卻可能讀取錯誤的結果集）。這些無聲漏洞就像是隱形炸彈，要更加危險一些，因為它們難以檢測到，還可能影響到應用的正確性。

這篇論文為多表連接查詢問題引入了查詢優化器來檢測邏輯漏洞。研究者將這些漏洞稱為連接優化漏洞（join optimization bugs）。使用表 1 給出的標記法，連接優化漏洞檢測問題可以形式化地定義為：

定義：對于查詢工作負載中的每個查詢，令查詢優化器通過多個實際規劃執行 的連接，并使用基本真值 驗證其結果集。如果，則發現了一個連接優化漏洞。

表 1：符號說明表

方案概述

圖 2 給出了 TQS 的架構概況。給定一個基準數據集和目標 DBMS，TQS 通過基于數據集生成查詢來搜索 DBMS 可能存在的邏輯漏洞。TQS 有兩大關鍵組件：數據引導的模式和查詢生成（DSG）和知識引導的查詢空間探索（KQE）

圖 2：TQS 概況

DSG 將輸入數據集視為一個寬表，并且除了原始元組外，DSG 還會刻意合成一些有易錯值（比如空值或非常長的字符串）的元組。針對連接查詢，DSG 會為該寬表創建一個新模式，其方法是將該寬表分成多個表，確保這些表符合基于功能依賴性的范式。DSG 會將該數據庫模式建模成一個圖，然后在該模式圖上通過隨機游走來生成邏輯 / 概念查詢。DSG 會將邏輯查詢具體化為物理執行計劃，并通過不同的提示對該查詢進行變換，使 DBMS 能夠執行多個不同的物理執行計劃，以搜索漏洞。對于一個連接查詢，其基本真值結果是通過將連接圖映射回寬表而得到。

在完成模式設置和數據拆分之后，KQE 將該模式圖擴展為一個規劃迭代圖。每個查詢都表示為一個子圖。KQE 為歷史中的查詢圖（即在已探索過的查詢空間中）的嵌入構建一個基于嵌入的圖索引。直觀地說，KQE 的作用是確保新生成的查詢圖盡可能地遠離其在歷史中的最近鄰，即這是為了探索新的查詢圖，而不是重復已有的查詢圖。為此，KQE 通過基于結構相似性（與歷史中的查詢圖）為生成的查詢圖評分，同時使用自適應隨機游走方法來生成查詢。。

算法 1 總結了 TQS 的核心思想，其中第 2、10、12 行是 DSG，第 4、8、9 行是 KQE。

給定一個數據集和從 采樣得到的寬表，DSG 將單個寬表 拆分成多表，這些表格組成符合 3NF 的數據庫模式（第 2 行）。模式可以被視為一個圖，其中表格和列是頂點，邊代表的是頂點之間的關系。DSG 在 上使用隨機游走來生成查詢的連接表達（第 10 行）。事實上，連接查詢可以被投射為 的子圖。通過將子圖映射回寬表格，DSG 可輕松地檢索到該查詢的基本真值結果（第 12 行）。

KQE 將模式圖擴展為一個規劃迭代圖（第 4 行）。為避免測試相似的路徑，KQE 會構建一個基于嵌入的圖索引來索引已有查詢圖的嵌入（第 9 行）。KQE 根據當前查詢圖與已有查詢圖的結構相似性來更新規劃迭代圖 G 的邊權重 π （第 8 行）。KQE 為下一條可能路徑評分，其引導著隨機游走生成器，從而更傾向于探索未知的查詢空間。

對于一個查詢 ，TQS 通過提示集對該查詢進行變換，以執行多個不同的實際查詢規劃（第 11 行）。最后，將查詢 的結果集與基本真值 進行比較（第 14 行）。如果它們不一致，那么就檢測到了連接優化漏洞（第 15 行）。

有關 DSG 和 KQE 的更多詳細描述請閱讀原論文。

實驗結果

TQS 成功找到了 MySQL、MariaDB、TiDB 和 PolarDB 等數據庫管理系統的一些邏輯漏洞，它們分為 20 種類型，其中 MySQL 的漏洞有 7 種、MariaDB 的有 5 種、TiDB 的有 5 種、PolarDB 的有 3 種，如下表所示。

相比于其它方法，浙大提出的 TQS 的整體表現也相當亮眼，在多項指標上都取得了顯著更優的成績，而各組件的有效性也通過控制變量實驗得到了檢驗。但研究者也表示，TQS 目前關注的是等值連接查詢。盡管如此，DSG 和 KQE 思想也可擴展到非等值連接的情況。唯一的難題是如何生成和管理查詢真值結果 —— 在非等值連接的情況下，這些結果的規模將指數級增長。這方面還有待未來進一步研究。

THE END

轉載請聯系本公眾號獲得授權

投稿或尋求報道：content@jiqizhixin.com