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

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

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

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

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

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

背景與動機

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

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

圖說：邏輯漏洞舉例

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

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

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

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

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

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

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

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

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

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

圖說：DSG是如何拆分寬表的

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

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

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

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

圖說：KQE原理圖

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

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

實驗結(jié)果分析

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

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

圖說：實驗檢出漏洞分類詳表

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

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

圖說：TQS與原有方法的有效性對比

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

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

返回搜狐，查看更多

責(zé)任編輯：