一天自動發現四大資料庫100+漏洞，浙大研究獲SIGMOD 2023最佳論文

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 給出的標記法，連線最佳化漏洞偵測問題可以形式化地定義為：

#定義：對於查詢工作負載Q中的每個查詢qi，令查詢最佳化器透過多個實際規劃執行qi的連接，並使用基本真值驗證其結果集。如果，則發現了一個連線最佳化漏洞。

表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 思想也可扩展到非等值连接的情况。唯一的难题是如何生成和管理查询真值结果 —— 在非等值连接的情况下，这些结果的规模将指数级增长。这方面还有待未来进一步研究。

以上是一天自動發現四大資料庫100+漏洞，浙大研究獲SIGMOD 2023最佳論文的詳細內容。更多資訊請關注PHP中文網其他相關文章！