技術研究 | SQUIRREL——對于DBMS的模糊測試技術介紹

數據庫 管理系統（DataBase Management System）與其他的大型復雜系統一樣，存在著許多漏洞。 其 中的內存錯誤漏洞往往可能導致遠程代碼執行、數據泄露、拒絕服務攻擊等。 由于數據庫管理系統的重要性，這些攻擊的影響往往十分重大。 本文將基于Squirrel [1] 這篇文章，來介紹對于DBMS的模糊測試技術。 簡單來說，對于DBMS的模糊測試的目標是找到一些SQL語句，將其輸入到DBMS后會觸發DBMS的異常行為（一般是崩潰）。

DBMS在接收到一條SQL查詢語句的時候，會依次進行詞法分析、語法分析（上圖中的parse）、語義檢查（validation）、語句優化和執行（optimization & execution）等流程。在詞法分析階段，DBMS會識別SQL語句中的關鍵字、標識符等記號（token），然后在語法分析階段則會識別這些記號的關聯信息。如果這些關聯信息不符合語法規則，DBMS將立即終止本次查詢并向客戶端返回錯誤信息。例如上圖，假設在AFL中的一次位翻轉（bitflip）變異，將一個查詢語句中的“SELECT”變異為“RELECT”。在新的語句進行詞法分析的時候，“RELECT”將不會被識別為關鍵字（或是一個別的什么關鍵字）。在接下來的語法分析中，由于這個“RELECT...FROM...WHERE”的記號組合不在DBMS的語法規則中，因此通不過語法分析階段。在語義檢查階段，DBMS將驗證語句的語義正確性，例如進行查詢的表名、列名是否存在等。在上圖中，假設在語句中變異出一個不存在的表t3，則將通不過語義檢查。在語義正確的情況下，DBMS將構建多個查詢計劃并且選擇最有效的一個來對當前的查詢語句進行優化。最后DBMS會在數據庫中執行選定的查詢計劃并將結果發送給客戶端。因此，如果變異出來的SQL查詢通不過語法分析和語義檢查階段，則輸入進去的SQL語句將不會執行DBMS的優化和執行處的代碼，對于程序的狀態空間提升就極其有限。

目前主要有兩種對于DBMS的模糊測試方法，基于生成（model-based generation）的方法與基于變異（random mutation）的方法。SQLSmith [2] 是目前使用較廣的基于生成的DBMS模糊測試工具。它基于抽象語法樹（Abstract Syntax Tree）來生成語法正確的查詢語句。與其他的黑盒模糊測試工具一樣，因為沒有反饋信息，SQLSmith會依次遍歷SQL語句的輸入空間。由于許多的SQL語句在DBMS中是由一套代碼流程來處理，因此在探索程序狀態空間上，這種方法是十分低效的。此外，這種方法也較難產生符合語義正確的輸入。而基于變異的方法在近年來飛速發展，以AFL為代表的工具以代碼覆蓋率作為反饋，可以有效的探索程序的狀態空間。但是AFL的變異策略對于結構化的輸入效果并不好，很難變異出合法的SQL語句。文章中的實驗顯示，AFL在24小時變異生成的兩千萬條SQL查詢語句中，只有30%通過了語法檢查，并且最終只有4%是語義正確的。

Squirrel的工作就是將上述的兩種方法的優勢進行結合，即將基于AST的變異方法引入到具有反饋驅動的AFL中，并且提出了基于依賴圖的查詢實例化（instantiation）方法，盡可能的使變異出來的語句通過語義檢查。總的來看，Squirrel的每次執行都從一個空的數據庫開始，一次輸入一組SQL語句（通常會包含創建表、插入數據、查詢等語句）。在變異前，Squirrel會剝離這些SQL語句中語義信息（例如列名、表名、整型數值）。變異后，Squirrel會經過一個被稱為“實例化”的階段，再來填充這些新的SQL語句中的語義信息。最后，輸入到DBMS中執行，并監控執行結果，執行完畢后會清空數據庫。

對于每組輸入的SQL語句，Squirrel會首先將其轉換為AST，然后將AST轉換為文中所謂的中間表示（Intermediate Representation）。但本質上來說，這個IR就是二叉樹形式的AST。其中每個IR是這個二叉樹上的一個節點，保存著這個節點的左子節點和右子節點，以及該節點的類型。由于AST中的節點可能有超過兩個子節點，因此轉化為二叉樹后，需要創建一些“虛空節點”來進行連接，這些虛空節點的類型即為Unknown。

在變異階段，所有AFL自帶的變異策略均被舍棄。Squirrel重新定義了三種變異操作，分別是插入、替換和刪除。變異的對象是IR，每次變異輸入的這組SQL語句中的一個IR。對于這個IR的左子節點和右子節點，分別有幾率將其替換成一個同類型的節點或是刪除（如果非空的話），或是插入一個同類型的節點（如果為空的話）。這些插入或替換進去的新的節點來自于一個被稱為IR library的素材庫。在剛開始進入模糊測試的準備階段，Squirrel會讀取一些預定義的素材SQL語句，并將其轉換成IR存到這個素材庫中。

整體看下來，這個IR其實并不是類似于LLVM或是編譯原理里面的那種 “中間表示”，本質上就是二叉樹形式的AST。但由于文章這么叫了，這里也繼續沿用這個IR的稱謂。至于為什么不直接對于AST進行操作，而是對于IR來進行變異。我個人認為可能是二叉樹操作起來更簡單一些，例如遍歷二叉樹就比遍歷一顆不知道每個節點有幾個子節點的樹要來的方便一些。并且變異操作也可以寫的比較簡單直觀，因為只需要對于確定的兩個子節點進行變異即可。

在變異過后，對于每組新的SQL語句，需要進行實例化，填充其中的語義信息。Squirrel提出了一種基于依賴圖的實例化算法。以上圖左邊的這組SQL語句為例，這里一共有兩類依賴，一種是表名與表名之間的依賴，即某個表名是由另一個表名決定的；另一種是列名與表名之間的依賴，即某個列名是由一個表名決定的。例如x14這個表名就依賴于x12或x13，而表名x12和x13又依賴于x1、x4或x7。由于依賴圖中的某個節點可能有多個依賴的目標，Squirrel會隨機為這個節點指定一個目標進行依賴，例如上圖右邊。在確定所有的依賴關系以后，我們就可以為那些不依賴于其他節點的節點（一般處在依賴圖的末端）分配一個新的值，然后根據依賴關系依次填充值即可。當然這里面會充斥著一些細枝末節和奇技淫巧，例如依賴關系是在構建AST的時候根據一些人為規則指定的，依賴圖在實現中并不是跨SQL語句的等等，這些內容本文就不展開講解了。

實現上，Squirrel使用了Flex和Bison實現了詞法分析和語法分析的部分（將SQL語句轉化為AST），插樁反饋用的是AFL的基本框架，并在AFL中添加了基于AST的變異方法。多說一句，Squirrel看起來是有很多代碼，但實際上核心的變異和實例化算法可能也就500到1000行左右的代碼，每個數據庫的文法定義也就是大概是3000行左右的Bison代碼。如果對于其基礎實現感興趣的同學可以放心閱讀。

實驗方面，Squirrel對于幾個時下流行的數據庫用多個模糊測試工具進行了測試。可以看到，在語法正確和語義正確的百分比上，Squirrel相較其他的工具都有絕對的優勢。在SQLite、MySQL和 MariaDB中分別找到了51個、7個和5個漏洞。由于AFL插樁中的碰撞問題的限制，以及Squirrel對于SQLite的文法支撐較好等原因，Squirrel僅在代碼量較少的SQLite上挖掘出了較多的漏洞。未來如果希望使用Squirrel在PG、MYSQL等數據庫中挖掘更多漏洞的話，需要解決一下碰撞問題，以及在文法上要支持這些數據庫的語法“方言”。

[1] Zhong,R., Chen, Y., Hu, H., Zhang, H., Lee, W., & Wu, D. (2020). SQUIRREL:Testing Database Management Systems with Language Validity and CoverageFeedback. In CCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference onComputer and Communications Security (pp. 955-970). (Proceedings of the ACMConference on Computer and Communications Security). Association for ComputingMachinery. https://doi.org/10.1145/3372297.3417260

[2]SQLSmith. https://github.com/anse1/sqlsmith, 2016.