【編者按】2023數(shù)據(jù)庫(kù)頂會(huì)SIGMOD在美國(guó)西雅圖頒出最佳論文。阿里云與浙江大學(xué)合作的《Detecting Logic Bugs of Join Optimizations in DBMS》獲得最佳論文，成為自1975年該會(huì)議至今49年以來(lái)，中國(guó)大陸研究團(tuán)隊(duì)首次斬獲該獎(jiǎng)項(xiàng)。

(相關(guān)資料圖)

這項(xiàng)工作聚焦數(shù)據(jù)庫(kù)邏輯測(cè)試，始于阿里云PolarDB云原生數(shù)據(jù)庫(kù)的內(nèi)核測(cè)試，通過開發(fā)創(chuàng)新的自動(dòng)化數(shù)據(jù)庫(kù)邏輯測(cè)試方案TQS，檢出不易察覺的邏輯漏洞予以修復(fù)。實(shí)驗(yàn)發(fā)現(xiàn)，TQS運(yùn)行僅24小時(shí)就檢測(cè)出4大商用數(shù)據(jù)庫(kù)管理系統(tǒng)的邏輯漏洞115個(gè)，予以修復(fù)后，大幅提升數(shù)據(jù)庫(kù)穩(wěn)定性。

該論文一作唐秀系浙江大學(xué)博士，這一工作是她在阿里云數(shù)據(jù)庫(kù)進(jìn)行研究型實(shí)習(xí)時(shí)的成果；阿里云數(shù)據(jù)庫(kù)負(fù)責(zé)人李飛飛也是作者之一，此前他曾以一作身份憑借《Wander Join: Online Aggregation via Random Walks》拿下2016年SIGMOD最佳論文。本次論文獲獎(jiǎng)，完成了中國(guó)大陸研究團(tuán)隊(duì)在數(shù)據(jù)庫(kù)頂會(huì)的歷史性突破，也成為了中國(guó)校企合作攻克科研難題的典范之一。

我們特別邀請(qǐng)到唐秀博士，為我們深入淺出地解讀這篇論文的關(guān)鍵成果。

作者 | 唐秀，浙江大學(xué)博士，2022 年阿里巴巴優(yōu)秀研究型實(shí)習(xí)生

背景與動(dòng)機(jī)

我國(guó)數(shù)據(jù)庫(kù)正處于高速發(fā)展期，并且隨著應(yīng)用復(fù)雜程度的增加，企業(yè)和用戶對(duì)于更強(qiáng)大、更安全的數(shù)據(jù)庫(kù)的需求也越來(lái)越迫切。因此，如何檢查數(shù)據(jù)庫(kù)漏洞和錯(cuò)誤，成為保障數(shù)據(jù)庫(kù)安全、提升數(shù)據(jù)庫(kù)穩(wěn)定性的關(guān)鍵之一。

在數(shù)據(jù)庫(kù)查詢執(zhí)行期間，主要有兩類錯(cuò)誤（bug）：一種常見的錯(cuò)誤是數(shù)據(jù)庫(kù)突然崩潰停止，這種錯(cuò)誤對(duì)于開發(fā)人員來(lái)說(shuō)相對(duì)容易檢測(cè)，因?yàn)閿?shù)據(jù)庫(kù)連接會(huì)突然中斷。然而，還存在一類隱藏的錯(cuò)誤，即邏輯漏洞。在這種情況下，數(shù)據(jù)庫(kù)正常運(yùn)行并返回結(jié)果，但實(shí)際上并非正確的結(jié)果。

圖說(shuō)：邏輯漏洞舉例

以上圖中的兩個(gè)邏輯漏洞為例，圖a展現(xiàn)了MySQL的一個(gè)哈希連接錯(cuò)誤，這種錯(cuò)誤發(fā)生在錯(cuò)誤地將零和負(fù)零視為不同值的情況下，導(dǎo)致最終返回一組空集合；b圖涉及數(shù)據(jù)類型轉(zhuǎn)換和數(shù)據(jù)精度損失導(dǎo)致的錯(cuò)誤半連接：在MySQL中，當(dāng)比較兩個(gè)值是否相等時(shí)，數(shù)據(jù)類型轉(zhuǎn)換和精度損失可能導(dǎo)致意外的結(jié)果，從而影響查詢結(jié)果集的構(gòu)建。

邏輯漏洞很難檢測(cè)，但其導(dǎo)致的后果確很嚴(yán)重，重則會(huì)導(dǎo)致“上萬(wàn)航班延誤癱瘓”級(jí)別的大規(guī)模宕機(jī)，因此也被視為“無(wú)聲的漏洞”。本論文便主要聚焦于此。

針對(duì)邏輯漏洞，目前已經(jīng)有一些檢測(cè)方法，例如部分查詢語(yǔ)義（PQS），但這些方法通常只支持針對(duì)單表選擇查詢的檢測(cè)，在涉及多表查詢以及不同的連接算法和連接結(jié)構(gòu)的情況下，仍存在大量的研究空白。

而最常用的差分測(cè)試，通過在不同數(shù)據(jù)庫(kù)中執(zhí)行相同操作，以驗(yàn)證其一致性，這種測(cè)試仍存在問題：假如兩個(gè)數(shù)據(jù)庫(kù)返回相同的結(jié)果，也有可能是基于同樣錯(cuò)誤的邏輯生成了一樣的結(jié)果， 也即如何驗(yàn)證查詢結(jié)果正確性的關(guān)鍵問題。

同時(shí)，測(cè)試數(shù)據(jù)庫(kù)現(xiàn)在面臨的搜索空間是非常龐大的， 如何引導(dǎo)測(cè)試以盡可能消耗最小的資源窮盡全部測(cè)試，也是一個(gè)需要解決的問題。

研究思路與核心內(nèi)容

圍繞這兩個(gè)關(guān)鍵問題，我們引入了一個(gè)名為TQS（轉(zhuǎn)換查詢合成）的全新解決方案，以解決MySQL數(shù)據(jù)庫(kù)中可能出現(xiàn)的邏輯錯(cuò)誤。

圖說(shuō)：TQS架構(gòu)圖

TQS包括DSG和KQE兩部分，分別為數(shù)據(jù)驅(qū)動(dòng)的模式和查詢生成，與知識(shí)引導(dǎo)的查詢空間探索。

為解決真值生成問題，我們采用了以下方法：首先，根據(jù)給定的寬表，使用函數(shù)依賴（FD）將該表拆分為多個(gè)表。

圖說(shuō)：DSG是如何拆分寬表的

同時(shí)，為了進(jìn)行邊緣測(cè)試，我們還插入了一些噪聲數(shù)據(jù)作為邊緣情況的樣本（圖中彩色數(shù)據(jù)），并基于數(shù)據(jù)庫(kù)的模式圖模型，隨機(jī)游走生成一系列查詢。

圖說(shuō)：DSG構(gòu)建針對(duì)表連接的Bitmap 索引

在此基礎(chǔ)上，構(gòu)建RowID映射表，用于記錄在表拆分過程中，寬表中的行和拆分后表的行的對(duì)應(yīng)關(guān)系。根據(jù)表連接是表拆分的逆向過程的直覺，構(gòu)建基于構(gòu)建RowID映射的Bitmap索引，以便從寬表中檢索到連接查詢的理論真值。 這些真值生成后，便是檢測(cè)潛在邏輯錯(cuò)誤的參照樣本。

然而，對(duì)于給定的數(shù)據(jù)庫(kù)模式，可生成的連接查詢的數(shù)量會(huì)隨著表格和列的數(shù)量呈指數(shù)級(jí)增長(zhǎng)，顯然無(wú)法使用枚舉法一一驗(yàn)證。那么，要如何更高效地探索查詢未知空間呢？我們提出了TQS的第二部分設(shè)計(jì)——KQE。

圖說(shuō)：KQE原理圖

KQE首先將模式圖進(jìn)一步拓展為一個(gè)規(guī)劃迭代圖，來(lái)表示整個(gè)查詢生成空間。同時(shí)，在大量的歷史查詢圖中，KQE構(gòu)建了一個(gè)基于嵌入的圖索引，以確保新生成的查詢圖盡可能地遠(yuǎn)離其在歷史查詢中的近鄰，探索更多的未知空間。

總體來(lái)看，KQE可基于結(jié)構(gòu)相似性為生成的查詢圖評(píng)分，同時(shí)也通過自適應(yīng)隨機(jī)游走多樣化查詢生成， 從而極大降低了對(duì)于重復(fù)查詢的概率，節(jié)省了計(jì)算資源開支。

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

我們的研究在MySQL、MariaDB、TiDB 和 PolarDB 等4大常用DBMS上進(jìn)行了實(shí)驗(yàn)。

運(yùn)行了 24 小時(shí)后，TQS 成功找到了 115 個(gè)漏洞：MySQL 中 31 個(gè)、MariaDB 中 30 個(gè)、TiDB 中 31 個(gè)、PolarDB 中 23 個(gè)。通過最小化測(cè)試樣例，我們進(jìn)一步將它們分為20種類型。

圖說(shuō)：實(shí)驗(yàn)檢出漏洞分類詳表

我們已經(jīng)將檢測(cè)到的漏洞提交給相應(yīng)數(shù)據(jù)庫(kù)社區(qū)，并得到了他們積極的反饋。這些漏洞的危機(jī)程度被數(shù)據(jù)庫(kù)社區(qū)判定為首要危急或嚴(yán)重級(jí)別，一些漏洞已經(jīng)修復(fù)在了其數(shù)據(jù)庫(kù)最新版本中。

具體來(lái)說(shuō)，MySQL 8.0.28的錯(cuò)誤主要集中在Semi-join和Sub-query的執(zhí)行過程中，其中，幾個(gè)錯(cuò)誤被評(píng)定為首要危急，即最緊急的錯(cuò)誤，這些錯(cuò)誤已經(jīng)在MySQL 8.0.30版本中得到修復(fù)，并提供了相應(yīng)的修復(fù)說(shuō)明。而對(duì)于已使用SQLancer進(jìn)行全面測(cè)試的TiDB，TQS也測(cè)出了一些首要危急錯(cuò)誤，TiDB對(duì)其進(jìn)行了修復(fù)。另外，針對(duì)PolarDB，我們則直接提交錯(cuò)誤報(bào)告，相關(guān)錯(cuò)誤已經(jīng)被修復(fù)。

圖說(shuō)：TQS與原有方法的有效性對(duì)比

總的來(lái)說(shuō)，相比于其它方法，TQS在多項(xiàng)指標(biāo)上取得了更優(yōu)的效果，較原有方法實(shí)現(xiàn)高達(dá)100倍的性能提升，各組件的有效性也通過控制變量實(shí)驗(yàn)得到了檢驗(yàn)。

6月21日晚上8點(diǎn)整，本文一作唐秀將直播解讀論文，歡迎廣大讀者預(yù)約收看。

返回搜狐，查看更多

責(zé)任編輯：