2023 年度的 ACM SIGMOD/PODS 國際數(shù)據(jù)管理大會(huì)（SIGMOD 2023）將于當(dāng)?shù)貢r(shí)間 6 月 18-23 日在美國西雅圖舉辦。近日，該會(huì)議公布了最佳論文名單，微軟研究院的《Predicate Pushdown for Data Science Pipelines》和浙江大學(xué)的《Detecting Logic Bugs of Join Optimizations in DBMS》獲獎(jiǎng)。自 1975 年該會(huì)議始辦以來，這是中國大陸研究團(tuán)隊(duì)首次獲得該會(huì)議的最佳論文獎(jiǎng)。其中浙大的研究提出了一種新穎的方法，可以自動(dòng)發(fā)現(xiàn) MySQL、MariaDB、TiDB 和 PolarDB 等數(shù)據(jù)庫管理系統(tǒng)的邏輯漏洞。

過去幾十年，現(xiàn)代數(shù)據(jù)庫管理系統(tǒng)（DBMS）不斷演進(jìn)，可以支持多種不同的新架構(gòu)，比如云平臺(tái)和 HTAP，這需要對(duì)查詢?cè)u(píng)估進(jìn)行越來越復(fù)雜精細(xì)的優(yōu)化。查詢優(yōu)化器（query optimizer）被認(rèn)為是 DBMS 中最復(fù)雜和最重要的組件之一，其功能是解析輸入的 SQL 查詢，然后在內(nèi)置成本模型的協(xié)助下生成高效的執(zhí)行方案。查詢優(yōu)化器實(shí)現(xiàn)中的錯(cuò)誤可能會(huì)導(dǎo)致出現(xiàn)漏洞（bug)，包括崩潰漏洞和邏輯漏洞。崩潰漏洞很容易檢測，因?yàn)楸罎?huì)導(dǎo)致系統(tǒng)立即停止。然而邏輯漏洞卻容易被忽視，因?yàn)檫壿嬄┒磿?huì)導(dǎo)致 DBMS 返回難以檢測的錯(cuò)誤結(jié)果集。這篇論文關(guān)注的重心是檢測這些無聲的漏洞。

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

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

圖 1：DBMS 中連接優(yōu)化的邏輯漏洞示例

圖 1 (a) 展示了 MySQL 8.0.18 中的哈希連接（hash join）的一個(gè)邏輯漏洞。在這個(gè)示例中，第一個(gè)查詢返回了正確的結(jié)果集，因?yàn)槠鋱?zhí)行過程中使用了塊嵌套循環(huán)連接（block nested loop join）。但是，第二個(gè)查詢使用內(nèi)部哈希連接（inner hash join）卻出了問題，返回的是一個(gè)不正確的空結(jié)果集。這是因?yàn)槠涞讓拥墓＿B接算法錯(cuò)誤地認(rèn)定 0 不等于 ?0。

圖 1 (b) 中的邏輯漏洞源自 MySQL 8.0.28 中的半連接（semi-join）處理過程。在第一個(gè)查詢中，嵌套循環(huán)內(nèi)部連接會(huì)將數(shù)據(jù)類型 varchar 轉(zhuǎn)換成 bigint，進(jìn)而得到正確的結(jié)果集。而當(dāng)使用哈希半連接執(zhí)行第二個(gè)查詢時(shí)，數(shù)據(jù)類型 varchar 會(huì)被轉(zhuǎn)換成 double，從而導(dǎo)致數(shù)據(jù)準(zhǔn)確度出現(xiàn)損失以及等值比較出錯(cuò)。

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

• 結(jié)果驗(yàn)證：為了驗(yàn)證查詢結(jié)果的正確性，之前的方法采用的是差分測試策略。其思路是使用不同的物理執(zhí)行計(jì)劃（physical plan，即數(shù)據(jù)庫系統(tǒng)實(shí)際執(zhí)行查詢語句的方式）來處理查詢。如果這些規(guī)劃返回的結(jié)果集不一致，那么就可能是檢測到了邏輯漏洞。但是，差分測試方法有兩個(gè)缺點(diǎn)。其一，某些邏輯漏洞可影響多個(gè)物理執(zhí)行計(jì)劃并讓它們?nèi)可赏瑯拥腻e(cuò)誤結(jié)果。其二，當(dāng)觀察到不一致的結(jié)果集時(shí)，需要人工檢查生成正確結(jié)果的是哪一個(gè)執(zhí)行計(jì)劃，從而導(dǎo)致成本開銷變得高昂。這個(gè)問題有一個(gè)可能的解決方案，即為任意測試查詢構(gòu)建真值（ground-truth）結(jié)果，但現(xiàn)有的工具并不支持這種操作；
• 搜索空間：對(duì)于給定的數(shù)據(jù)庫模式，可生成的連接查詢的數(shù)量隨表格和列的數(shù)量呈指數(shù)級(jí)變化。由于我們不可能為了驗(yàn)證而枚舉出所有可能的查詢，因此就需要一種有效的查詢空間探索機(jī)制，以便讓我們盡可能高效地檢測出邏輯漏洞。

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

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

針對(duì)上述第二個(gè)挑戰(zhàn)，研究者設(shè)計(jì)的方法是 KQE，即知識(shí)引導(dǎo)的查詢空間探索（Knowledge-guided Query space Exploration）。該方法首先是將模式圖擴(kuò)展成一個(gè)規(guī)劃迭代圖（plan-iterative graph），其表示整個(gè)查詢生成空間。然后將每個(gè)連接查詢表示為一個(gè)子圖。為了給生成的查詢圖評(píng)分，KQE 采用了一種基于嵌入的圖索引，其可以在已經(jīng)探索過的空間中搜索是否有結(jié)構(gòu)相似的查詢圖。根據(jù)覆蓋度分?jǐn)?shù)引導(dǎo)隨機(jī)游走查詢生成器，以盡可能多地探索未知的查詢空間。

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

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

問題定義

數(shù)據(jù)庫的漏洞有兩種：崩潰和邏輯漏洞。崩潰漏洞來自于操作系統(tǒng)和 DBMS 的執(zhí)行過程。它們會(huì)導(dǎo)致 DBMS 被強(qiáng)行終止，原因包括內(nèi)存等資源不足或訪問了無效內(nèi)存地址等。因此，崩潰漏洞很容易被發(fā)現(xiàn)。相較而言，邏輯漏洞則更難以發(fā)現(xiàn)，因?yàn)閿?shù)據(jù)庫依然會(huì)正常運(yùn)行，處理查詢后也會(huì)返回看似正確的結(jié)果（并且大多數(shù)情況下它們確實(shí)會(huì)返回正確結(jié)果，但在少數(shù)情況下卻可能讀取錯(cuò)誤的結(jié)果集）。這些無聲漏洞就像是隱形炸彈，要更加危險(xiǎn)一些，因?yàn)樗鼈冸y以檢測到，還可能影響到應(yīng)用的正確性。

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

定義：對(duì)于查詢工作負(fù)載Q中的每個(gè)查詢qi，令查詢優(yōu)化器通過多個(gè)實(shí)際規(guī)劃執(zhí)行qi的連接，并使用基本真值驗(yàn)證其結(jié)果集。如果，則發(fā)現(xiàn)了一個(gè)連接優(yōu)化漏洞。

表 1：符號(hào)說明表

方案概述

圖 2 給出了 TQS 的架構(gòu)概況。給定一個(gè)基準(zhǔn)數(shù)據(jù)集和目標(biāo) DBMS，TQS 通過基于數(shù)據(jù)集生成查詢來搜索 DBMS 可能存在的邏輯漏洞。TQS 有兩大關(guān)鍵組件：數(shù)據(jù)引導(dǎo)的模式和查詢生成（DSG）和知識(shí)引導(dǎo)的查詢空間探索（KQE）

圖 2：TQS 概況

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

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

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

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

KQE 將模式圖擴(kuò)展為一個(gè)規(guī)劃迭代圖（第 4 行）。為避免測試相似的路徑，KQE 會(huì)構(gòu)建一個(gè)基于嵌入的圖索引

來索引已有查詢圖的嵌入（第 9 行）。KQE 根據(jù)當(dāng)前查詢圖與已有查詢圖的結(jié)構(gòu)相似性來更新規(guī)劃迭代圖 G 的邊權(quán)重 π （第 8 行）。KQE 為下一條可能路徑評(píng)分，其引導(dǎo)著隨機(jī)游走生成器，從而更傾向于探索未知的查詢空間。

對(duì)于一個(gè)查詢 ，TQS 通過提示集對(duì)該查詢進(jìn)行變換，以執(zhí)行多個(gè)不同的實(shí)際查詢規(guī)劃（第 11 行）。最后，將查詢

 的結(jié)果集與基本真值進(jìn)行比較（第 14 行）。如果它們不一致，那么就檢測到了連接優(yōu)化漏洞（第 15 行）。

有關(guān) DSG 和 KQE 的更多詳細(xì)描述請(qǐng)閱讀原論文。

實(shí)驗(yàn)結(jié)果

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

相比于其它方法，浙大提出的 TQS 的整體表現(xiàn)也相當(dāng)亮眼，在多項(xiàng)指標(biāo)上都取得了顯著更優(yōu)的成績，而各組件的有效性也通過控制變量實(shí)驗(yàn)得到了檢驗(yàn)。

但研究者也表示，TQS 目前關(guān)注的是等值連接查詢。盡管如此，DSG 和 KQE 思想也可擴(kuò)展到非等值連接的情況。唯一的難題是如何生成和管理查詢真值結(jié)果 —— 在非等值連接的情況下，這些結(jié)果的規(guī)模將指數(shù)級(jí)增長。這方面還有待未來進(jìn)一步研究。