問欣 方勇 賈鵬 范希明

摘 要： 數(shù)據(jù)庫管理系統(tǒng)（DBMS）被廣泛應(yīng)用于各個(gè)領(lǐng)域，并在其中發(fā)揮著不可替代的作用. 因此發(fā)現(xiàn)DBMS 中的bug，防止其被攻擊者利用至關(guān)重要. 為了檢測(cè)DBMS 中潛藏的bug，研究者提出了DBMS 模糊測(cè)試技術(shù). 使用這項(xiàng)技術(shù)，研究者成功在DBMS 中發(fā)現(xiàn)了大量bug. 然而現(xiàn)有的DBMS 模糊測(cè)試技術(shù)依然存在一定的局限性. 現(xiàn)有的技術(shù)在對(duì)SQL 語句的抽象語法樹（AST）進(jìn)行變異時(shí)，沒有根據(jù)不同節(jié)點(diǎn)和變異結(jié)果的重要性分配計(jì)算資源，而是采取了一種平均分配的策略，這降低了測(cè)試的效率. 為了解決這個(gè)問題，本文提出了一種使用基于語法信息的變異方法的自適應(yīng)變異策略. 這種變異策略能夠自動(dòng)計(jì)算不同節(jié)點(diǎn)和變異結(jié)果的重要性，并根據(jù)重要性為更重要的操作分配更多的計(jì)算資源. 基于語法信息的變異方法可以將變異操作與變異結(jié)果直接關(guān)聯(lián)，消除了變異操作和變異結(jié)果之間的偏差. 我們?cè)谝环N新的DBMS 模糊測(cè)試工具Pinecone 中實(shí)現(xiàn)了這種變異策略，并使用Pinecone 對(duì)兩款廣泛使用的DBMS 進(jìn)行測(cè)試. 實(shí)驗(yàn)證明，與Squirrel 相比，Pinecone 在MariaDB 和MySQL 中發(fā)現(xiàn)的路徑數(shù)分別提升了4. 52% 和19. 4%，位圖覆蓋率分別提升了15% 和13. 8%，發(fā)現(xiàn)的Bug 數(shù)量提升了26. 7% 和75%，這證明了本文提出的方法可以有效提升模糊測(cè)試的效率.

關(guān)鍵詞： DBMS 模糊測(cè)試； Squirrel； 語法信息； 自適應(yīng)變異策略

中圖分類號(hào)： TP391. 1 文獻(xiàn)標(biāo)志碼： A DOI： 10. 19907/j. 0490-6756. 2024. 032006

1 引言

數(shù)據(jù)庫管理系統(tǒng)（Database Management System，DBMS）是一種操縱和管理數(shù)據(jù)庫的大型軟件，被廣泛應(yīng)用于各種行業(yè). 然而，像其他復(fù)雜系統(tǒng)一樣，DBMS 內(nèi)往往存在許多未被發(fā)現(xiàn)的bug. 這些bug 可能會(huì)被攻擊者利用，從而造成嚴(yán)重的后果.

模糊測(cè)試是一種被廣泛使用的自動(dòng)化軟件測(cè)試技術(shù). 其基本過程是使用生成或變異的方法得到大量新測(cè)試用例，再將這些測(cè)試用例輸入程序，找出能使程序出現(xiàn)異常的測(cè)試用例，最后通過這些測(cè)試用例找到程序中存在的bug. AFL［1］是最著名的模糊測(cè)試工具，其中使用的很多方法和設(shè)計(jì)理念被后人沿用，有許多先進(jìn)的模糊測(cè)試工具是基于AFL 實(shí)現(xiàn)的，例如AFLGO［2］、AFLFast［3］、AFL++［4］等.

近年來，隨著模糊測(cè)試技術(shù)的發(fā)展，模糊測(cè)試開始被用于DBMS 的測(cè)試. 最早的DBMS 模糊測(cè)試技術(shù)是黑盒的，其中代表性的工具是SQLsmith［5］. 使用SQLsmith，研究者們?cè)诙鄠€(gè)DBMS中發(fā)現(xiàn)了100 多個(gè)bug［6］. 之后，出現(xiàn)了灰盒DBMS模糊測(cè)試技術(shù). 最著名的開源灰盒工具是Squirrel［7］，該工具基于AFL 實(shí)現(xiàn)，并在AFL 的基礎(chǔ)上增加了基于抽象語法樹（AST）的變異方法和語義引導(dǎo)的實(shí)例化方法，解決了AFL 難以產(chǎn)生語法正確且語義正確的SQL 語句的問題. 使用Squirrel，研究者在MariaDB、MySQL、SQLite 等著名DBMS 中發(fā)現(xiàn)了幾十個(gè)bug. 之后，研究者們提出了越來越多的灰盒DBMS 模糊測(cè)試工具，包括RATEL［8］、SQLRight［9］、Griffin［10］、DynSQL［11］等.但是這些工具沒有開源，因此Squirrel 仍是最著名的開源灰盒DBMS 模糊測(cè)試工具.

雖然Squirrel 取得了很好的效果，但仍然存在一些不可忽視的問題. 例如，變異策略問題. 近年來，研究者們提出了很多改善模糊測(cè)試效率的方法. 其中一項(xiàng)重要的研究是自適應(yīng)變異策略［12-17］.然而，人們對(duì)DBMS 模糊測(cè)試領(lǐng)域自適應(yīng)變異策略的研究較少. Squirrel 在進(jìn)行變異時(shí)，每種變異節(jié)點(diǎn)和變異操作被選擇的機(jī)會(huì)是一樣的. 然而，在AST 中，每種變異節(jié)點(diǎn)的重要性是不一樣的，對(duì)于不同節(jié)點(diǎn)類型，不同變異結(jié)果的重要性也是不一樣的. 因此，不同變異節(jié)點(diǎn)和變異結(jié)果帶來的效果也是不同的. 如果選擇了不重要的變異節(jié)點(diǎn)和變異結(jié)果，則會(huì)導(dǎo)致計(jì)算資源的浪費(fèi)，從而降低模糊測(cè)試的效率. 本文提出了一種針對(duì)DBMS 模糊測(cè)試的自適應(yīng)變異策略. 該策略會(huì)根據(jù)代碼覆蓋率信息自動(dòng)判斷不同變異節(jié)點(diǎn)和變異結(jié)果的重要性，使計(jì)算資源傾向于更重要的節(jié)點(diǎn)類型和變異結(jié)果，提升測(cè)試的效率.

2 背景

2. 1 Squirrel 簡(jiǎn)介

Squirrel 是一種DBMS 模糊測(cè)試工具，主要用于檢測(cè)DBMS 中存在的內(nèi)存bug. Squirrel 是基于AFL 實(shí)現(xiàn)的，修改了AFL 中的變異方法，使得在變異時(shí)能夠確保SQL 語句語法正確. 同時(shí)，為了確保生成的SQL 語句是語義正確的，Squirrel 還添加了實(shí)例化模塊，該模塊會(huì)推斷SQL 語句中數(shù)據(jù)庫對(duì)象標(biāo)識(shí)符之間的依賴關(guān)系，并基于依賴關(guān)系為標(biāo)識(shí)符賦予正確的值.

Squirrel 的變異方法首先會(huì)將SQL 語句解析為AST，之后對(duì)AST 中每個(gè)節(jié)點(diǎn)進(jìn)行替換、插入和刪除等3 種變異操作（圖1）. 其中，替換操作會(huì)根據(jù)變異節(jié)點(diǎn)子節(jié)點(diǎn)的類型從語料庫中隨機(jī)選擇語料，替換變異節(jié)點(diǎn)的子樹；插入操作會(huì)根據(jù)變異節(jié)點(diǎn)的類型從語料庫中隨機(jī)選擇語料，將語料的子樹插入變異節(jié)點(diǎn)的空白子樹；刪除操作會(huì)隨機(jī)刪除變異節(jié)點(diǎn)的子樹. 最后，通過實(shí)例化就可以得到新的SQL 語句. 如果新語句使代碼覆蓋率增加，則將新語句的AST 加入語料庫中.

2. 2 Squirrel 變異策略的局限性

Squirrel 使用了一種最基本的變異策略，即無差別的對(duì)待每種變異節(jié)點(diǎn)和變異操作. 這種變異策略假定了AST 中每種變異節(jié)點(diǎn)和變異操作的重要性是一樣的. 但是，這種方法是存在明顯缺陷的，因?yàn)椴煌N類節(jié)點(diǎn)的重要性是不同的.

為證明以上觀點(diǎn)，我們?cè)贛ySQL 和Maria DB上進(jìn)行了實(shí)驗(yàn)，來證明不同種類節(jié)點(diǎn)的重要性是不同的（如圖2）. 我們?cè)贛ariaDB 和MySQL 中進(jìn)行了12 h 測(cè)試，并記錄了每種類型節(jié)點(diǎn)變異后觸發(fā)新分支的概率. 圖2a 和2b 展示了MariaDB 中成功率最高和最低的10 種節(jié)點(diǎn). 其中，8 號(hào)類型節(jié)點(diǎn)在變異后，觸發(fā)新分支的概率高達(dá)14. 85%，而213號(hào)節(jié)點(diǎn)在變異后觸發(fā)新分支的概率僅有0. 6? .圖2a 和2c 展示了MariaDB 和MySQL 中成功率最高的10 種節(jié)點(diǎn)，可以看出，在這兩種DBMS 中，成功率最高的節(jié)點(diǎn)類型存在一定差異. 這說明在同一DBMS 中，不同類型節(jié)點(diǎn)在進(jìn)行變異后，觸發(fā)新分支的概率有很大差異. 在不同DBMS 中，不同類型節(jié)點(diǎn)觸發(fā)新分支的概率也不一致.

在同一類型節(jié)點(diǎn)中，不同變異結(jié)果的重要性也是不同的. 我們?cè)贛ariaDB 和MySQL 中進(jìn)行了12 h 測(cè)試，并記錄了每種節(jié)點(diǎn)類型下不同變異結(jié)果觸發(fā)新分支的概率（如圖3）. 我們選擇了具有多種變異結(jié)果且成功率最高的6 種節(jié)點(diǎn)，展示同一種節(jié)點(diǎn)類型中不同變異結(jié)果重要性的差異. 這里的變異結(jié)果是指AST 中，該類型節(jié)點(diǎn)的合法結(jié)構(gòu). 有一些節(jié)點(diǎn)具有多種合法結(jié)構(gòu)，這些結(jié)構(gòu)的重要性是不同的. 在對(duì)這種節(jié)點(diǎn)進(jìn)行變異時(shí)，某些結(jié)構(gòu)更容易觸發(fā)新分支. 圖3 中resulti代表一種類型的節(jié)點(diǎn)中第i 種變異結(jié)果. 不同節(jié)點(diǎn)間的resulti 代表不同結(jié)果. 為了更直觀的理解不同結(jié)果重要性的差異，我們對(duì)每種節(jié)點(diǎn)不同變異結(jié)果觸發(fā)新分支的概率進(jìn)行了歸一化處理. 可以看出，對(duì)于一種類型的節(jié)點(diǎn)，不同變異結(jié)果的重要性是不一樣的.例如，在39 號(hào)類型節(jié)點(diǎn)中，一共只有兩種變異結(jié)果，變異結(jié)果1 觸發(fā)新分支的概率要遠(yuǎn)高于結(jié)果2觸發(fā)新分支的概率. 這說明結(jié)果1 的重要性高于結(jié)果2，在對(duì)39 號(hào)類型節(jié)點(diǎn)進(jìn)行變異時(shí)，結(jié)果1 更容易觸發(fā)新分支.

除此之外，即使在對(duì)同一數(shù)據(jù)庫的不同測(cè)試中，變異節(jié)點(diǎn)和變異結(jié)果的重要性也是不同的. 如圖4 所示，我們?cè)贛ariaDB 中進(jìn)行了兩次12 h 測(cè)試. 可以看出，兩次實(shí)驗(yàn)中，不同節(jié)點(diǎn)類型的重要性和每種節(jié)點(diǎn)不同結(jié)果的重要性存在一定差異.事實(shí)上，兩次測(cè)試中，成功率最高的前30 個(gè)節(jié)點(diǎn)中有24 個(gè)是相同的，但是其排名和成功率存在一定差異. 對(duì)于同一類型的節(jié)點(diǎn)，每種結(jié)果的成功率也存在差異.

根據(jù)以上分析，我們可以得出結(jié)論，不同種類變異節(jié)點(diǎn)的重要性是不一樣的. 對(duì)于同一種節(jié)點(diǎn)，不同變異結(jié)果的重要性也是不一樣的. 在測(cè)試時(shí)，應(yīng)當(dāng)為更重要的節(jié)點(diǎn)和結(jié)果分配更多的計(jì)算資源. 而那些不重要的的節(jié)點(diǎn)和結(jié)果應(yīng)當(dāng)獲得更少的計(jì)算資源. 然而，Squirrel 的變異策略無法實(shí)現(xiàn)這一點(diǎn). 因此，需要一種更有效的變異策略.

3 方法概述

現(xiàn)有的變異策略無法根據(jù)變異節(jié)點(diǎn)和變異結(jié)果的重要性分配計(jì)算資源，這會(huì)導(dǎo)致測(cè)試效率降低. 為了解決這個(gè)問題，本文提出了一種使用基于語法信息的變異方法的自適應(yīng)變異方法. 首先，本文提出了一種基于語義的變異方法. 這種變異方法兼容了Squirrel 使用3 種變異方法，同時(shí)能夠在變異操作和變異結(jié)果之間建立直接的對(duì)應(yīng)關(guān)系.之后，基于這種變異方法，本文提出了一種自適應(yīng)變異策略. 這種策略能夠在測(cè)試中動(dòng)態(tài)調(diào)整每個(gè)節(jié)點(diǎn)和每種變異操作被選擇的機(jī)會(huì)，為那些更重要的節(jié)點(diǎn)和操作分配更多的計(jì)算資源.

3. 1 基于語法信息的變異

在第2 節(jié)中，本文展示了不同的變異結(jié)果具有不同的重要性. 然而，Squirrel 使用的3 種變異操作與變異結(jié)果之間不存在對(duì)應(yīng)關(guān)系. 在Squirrel 中，替換操作的變異結(jié)果由變異前的AST 結(jié)構(gòu)決定；插入操作的變異結(jié)果由變異前的AST 結(jié)構(gòu)和選擇的語料決定；刪除操作的變異結(jié)果是確定的，但是該操作很容易產(chǎn)生錯(cuò)誤的變異結(jié)果. 由于Squirrel的變異操作與變異結(jié)果之間缺乏聯(lián)系，因此即使調(diào)整這3 種變異操作被選擇的機(jī)會(huì)，也不能有效地增加測(cè)試的效率.

為解決這個(gè)問題，本文提出一種基于語法信息的變異方法. 由于解析SQL 時(shí)需要使用SQL 的語法信息，因此語法信息與AST 之間存在一定的對(duì)應(yīng)關(guān)系（如圖5）. SQL 是由上下文無關(guān)文法定義的語言，圖5 左側(cè)是其語法信息的一部分；右側(cè)是這部分語法信息對(duì)應(yīng)的AST. 可以看到，AST 中的節(jié)點(diǎn)對(duì)應(yīng)了語法信息中的符號(hào)，一個(gè)節(jié)點(diǎn)的合法結(jié)構(gòu)由語法信息中該非終結(jié)符的生成式?jīng)Q定.圖5 中c_tab 非終結(jié)符一共有2 條生成式，那么c_tab 節(jié)點(diǎn)的合法結(jié)構(gòu)也只有兩種. 也就是說，若變異后AST 語法是正確的，那么只可能是這兩種結(jié)果中的一個(gè). 其他變異結(jié)果，如第3 種情況，由于不存在這種生成式，因此該結(jié)果是錯(cuò)誤的. 因此，使用語法信息指導(dǎo)變異既可確保語法正確，又可在變異操作和變異結(jié)果之間建立直接的對(duì)應(yīng)關(guān)系.

在開始測(cè)試前，會(huì)先從文件中提取語法信息，經(jīng)過處理后用于指導(dǎo)變異. 具體處理方法如圖6所示. 首先是從文件中提取語法信息. 這里的文件一般指bison 文件，由于bison 文件中除了語法信息外，還有其他代碼，所以在處理時(shí)需要剔除多余代碼. 獲取到語法信息包括所有非終結(jié)符及其對(duì)應(yīng)的生成式. 之后，對(duì)語法信息進(jìn)行格式轉(zhuǎn)換. 轉(zhuǎn)換后的語法信息中，每條生成式具有特定格式. 這樣做是為了統(tǒng)一生成式的格式，使得AST 中不同種類的節(jié)點(diǎn)具有同樣的結(jié)構(gòu). 為了方便起見，這里使用了與Squirrel 中AST 一致的結(jié)構(gòu). 最后對(duì)語法信息中的終結(jié)符和非終結(jié)符進(jìn)行編碼，轉(zhuǎn)換為數(shù)字形式.

算法1 描述了這種變異方法. 算法以選擇進(jìn)行變異的AST 節(jié)點(diǎn)和選擇的生成式信息作為輸入，輸出新AST 的根節(jié)點(diǎn). 第3 行的checkNode 函數(shù)會(huì)檢查root 節(jié)點(diǎn)左右子節(jié)點(diǎn)的情況. 如果root節(jié)點(diǎn)左右子節(jié)點(diǎn)都存在，那么變異時(shí)有概率保留root 中原有的子節(jié)點(diǎn). 第4～13 行對(duì)節(jié)點(diǎn)進(jìn)行變異. 如果選擇變異，則根據(jù)生成式信息中記錄的節(jié)點(diǎn)類型，在corpos 中隨機(jī)選擇對(duì)應(yīng)類型的節(jié)點(diǎn)索引. 之后對(duì)該節(jié)點(diǎn)對(duì)應(yīng)的AST 進(jìn)行深拷貝. 否則對(duì)root 的左右子樹進(jìn)行深拷貝. 第14 行是對(duì)當(dāng)前節(jié)點(diǎn)的終結(jié)符部分進(jìn)行修改，由于終結(jié)符以數(shù)字形式存在，因此可以直接賦值. Mutate 函數(shù)生成的新AST 是完整AST 中被修改的部分. 將這些新AST 連接到完整AST 的操作由其他函數(shù)完成，這部分與本文的方法無關(guān)，因此省略.

該方法完全取代了Squirrel 中使用的替換、插入和刪除等3 種變異操作，并且在變異操作和變異結(jié)果之間建立直接的對(duì)應(yīng)關(guān)系. 這樣一來，就可以通過調(diào)整每種變異操作被選擇的機(jī)會(huì)來調(diào)整每種變異結(jié)果出現(xiàn)的機(jī)會(huì)，從而為更重要的變異結(jié)果分配更多計(jì)算資源.

3. 2 自適應(yīng)變異策略

經(jīng)實(shí)驗(yàn)證明，不同節(jié)點(diǎn)類型和變異結(jié)果的重要性是不同的. 變異策略應(yīng)根據(jù)不同節(jié)點(diǎn)類型和變異操作的重要程度，動(dòng)態(tài)調(diào)整每種節(jié)點(diǎn)類型和變異操作被選擇的機(jī)會(huì)，為更重要的節(jié)點(diǎn)類型和變異操作分配更多計(jì)算資源. 因此，本文提出了一種新的變異策略. 該變異策略將變異節(jié)點(diǎn)和變異操作的選擇問題表示為一個(gè)多臂老虎機(jī)問題，假設(shè)有k 臺(tái)老虎機(jī)，每臺(tái)老虎機(jī)都對(duì)應(yīng)一個(gè)獎(jiǎng)勵(lì)概率分布，其目標(biāo)是在不知道獎(jiǎng)勵(lì)概率分布的情況下操作T 次老虎機(jī)后，能夠取得累計(jì)最大獎(jiǎng)勵(lì).

在本文提出的方法中，使用每種變異節(jié)點(diǎn)和變異操作被選擇后成功觸發(fā)新分支的次數(shù)和被選擇的總次數(shù)的比值作為獎(jiǎng)勵(lì). 因?yàn)樵贏ST 中，不同種類節(jié)點(diǎn)出現(xiàn)的次數(shù)不同，有些類型的節(jié)點(diǎn)出現(xiàn)次數(shù)較多. 因此，以比值作為獎(jiǎng)勵(lì)更能反映不同變異節(jié)點(diǎn)和變異操作的重要性.

由于節(jié)點(diǎn)種類眾多，而每種節(jié)點(diǎn)可能會(huì)有多種操作，同時(shí)考慮節(jié)點(diǎn)類型和變異操作會(huì)導(dǎo)致老虎機(jī)數(shù)量過多. DBMS 模糊測(cè)試的運(yùn)行速度普遍較慢，過多的老虎機(jī)會(huì)導(dǎo)致在有限的時(shí)間內(nèi)探索不足. 因此，本文分別考慮變異節(jié)點(diǎn)和變異操作的選擇. 在求解多臂老虎機(jī)問題時(shí)，本文使用ε-貪心算法，這是一種在處理多臂老虎機(jī)問題時(shí)常用的算法. 這種算法在每次選擇老虎機(jī)時(shí)，以ε 的概率隨機(jī)選擇老虎機(jī)，以1-ε 的概率選擇期望獎(jiǎng)勵(lì)最大的老虎機(jī). 其中，ε 會(huì)隨時(shí)間逐步減少. 在使用時(shí)，本文對(duì)該算法進(jìn)行了一定的修改，使其更適用于實(shí)際情況.

算法2 描述了本文的變異節(jié)點(diǎn)選擇算法. 6～13 行的循環(huán)遍歷AST. 對(duì)于AST 中每個(gè)節(jié)點(diǎn)，將其根據(jù)節(jié)點(diǎn)類型記錄到topRewards 對(duì)象中. 該對(duì)象還維護(hù)一個(gè)列表，里面記錄了AST 中獎(jiǎng)勵(lì)值最高的10 種節(jié)點(diǎn)類型，每次加入新節(jié)點(diǎn)時(shí)對(duì)該列表進(jìn)行更新. 之后，在14～21 行，進(jìn)入位置選擇階段. 對(duì)于AST 中每個(gè)節(jié)點(diǎn)，以ε 的概率選擇當(dāng)前節(jié)點(diǎn)進(jìn)行. 在這里，算法使用1/T 作為ε 的值，T 為測(cè)試進(jìn)行的時(shí)間（單位：h，向上取整）. 以1-ε 的概率使用getRandomTopNode 方法從當(dāng)前獎(jiǎng)勵(lì)最高的10 個(gè)節(jié)點(diǎn)類型中，隨機(jī)選擇一種節(jié)點(diǎn)類型，再隨機(jī)選擇一個(gè)該類型的節(jié)點(diǎn)進(jìn)行變異. 將AST 子樹連接到完整AST 的操作由其他函數(shù)完成.

選擇了要進(jìn)行變異的節(jié)點(diǎn)后，基于節(jié)點(diǎn)的上下文信息選擇要進(jìn)行的變異操作. 在這里，算法考慮了節(jié)點(diǎn)的上下文信息. 這是因?yàn)槲挥诓煌舷挛沫h(huán)境下的節(jié)點(diǎn)可能代表不同的語義. 例如SELECT 語句單獨(dú)存在時(shí)表示查詢語句，但是在FROM 子句中表示子查詢. 因此需要對(duì)每種上下文環(huán)境單獨(dú)考慮. 另一個(gè)原因是每個(gè)節(jié)點(diǎn)可選的變異操作數(shù)量較少. 即使考慮了上下文信息，也不會(huì)出現(xiàn)探索不足的問題.

算法使用的上下文信息可以使用一個(gè)五元組（stmt，inSubquery，clause，pType，pInfo）描述. 其中，stmt 表示該節(jié)點(diǎn)所在的語句類型. 例如用于區(qū)分SELECT 語句和UPDATE 語句中的FROM 子句. inSubquery 用于標(biāo)記該節(jié)點(diǎn)是否處于子查詢中. clause 表示該節(jié)點(diǎn)處于什么子句中. 主要用來區(qū)分不同子句中的表達(dá)式. pType 表示該節(jié)點(diǎn)父節(jié)點(diǎn)的節(jié)點(diǎn)類型. pInfo 表示該節(jié)點(diǎn)父節(jié)點(diǎn)對(duì)應(yīng)的生成式信息.

算法3 描述了本文的變異操作選擇算法. 第3行使用getContext 函數(shù)獲取root 節(jié)點(diǎn)的上下文信息. 在第4 行，根據(jù)該節(jié)點(diǎn)的類型和節(jié)點(diǎn)上下文信息獲取該類型節(jié)點(diǎn)的生成式信息. 5～10 行的循環(huán)選擇變異操作對(duì)root 進(jìn)行變異. 變異的次數(shù)由使用的能量調(diào)度策略決定. 為了與Squirrel 對(duì)比，將N 設(shè)置為2. 每次變異有ε 的概率隨機(jī)選擇一條生成式信息進(jìn)行變異，有1-ε 的概率選擇獎(jiǎng)勵(lì)最高的生成式信息進(jìn)行變異. 這里的ε 與變異節(jié)點(diǎn)選擇部分的ε 相同.

4 實(shí)驗(yàn)及分析

本文基于Squirrel 實(shí)現(xiàn)了一個(gè)灰盒DBMS 模糊測(cè)試工具Pinecone，并與Squirrel 進(jìn)行了對(duì)比.實(shí)驗(yàn)選取了MySQL 和MariaDB 作為目標(biāo)，這兩個(gè)DBMS 在現(xiàn)實(shí)世界中得到了廣泛運(yùn)用. 實(shí)驗(yàn)在一臺(tái)使用了 Ubuntu 20. 04操作系統(tǒng)、Inte（l R） Xeon（R） CPU E3-1231 v3 @ 3. 40 GHz 3. 39 GHz 處理器和32 GB 內(nèi)存的計(jì)算機(jī)上進(jìn)行. 實(shí)驗(yàn)中，bitmap被設(shè)置為256 KB，并使用AFL 自帶的afl-clangfast和afl-clang-fast++ 對(duì)MySQL 和MariaDB 進(jìn)行插樁，插樁比例為5%. 實(shí)驗(yàn)中使用DBMS 的最新版本. 其中，MariaDB 的版本是11. 3. 0，MySQL的版本是8. 0. 34. 在實(shí)驗(yàn)中，每次同時(shí)進(jìn)行兩個(gè)測(cè)試，運(yùn)行12 h，并重復(fù)3 次，結(jié)果取平均值.

4. 1 路徑數(shù)和位圖覆蓋率對(duì)比

如圖7 所示，在路徑數(shù)和位圖覆蓋率方面，Pinecone 都取得了優(yōu)勢(shì). 其中，在MariaDB 中，Pinecone 發(fā)現(xiàn)的路徑數(shù)僅比Squirrel 多4. 52%. 但是在位圖覆蓋率方面，Pinecone 比Squirrel 高出15%. 在MySQL 中，Pinecone 發(fā)現(xiàn)的路徑數(shù)比Squirrel 多19. 4%，位圖覆蓋率高出13. 8%. 實(shí)驗(yàn)結(jié)果說明，與Squirrel 相比，Pinecone 能夠在相同時(shí)間內(nèi)探索更多分支.

4. 2 發(fā)現(xiàn)bug 的數(shù)量

圖8 展示了兩種工具在測(cè)試中發(fā)現(xiàn)的bug 數(shù)量. 我們對(duì)發(fā)現(xiàn)的bug 進(jìn)行了手動(dòng)檢查，以去除重復(fù)的bug. 我們同時(shí)使用了ASan［18］和GDB［19］去除重復(fù)bug. 對(duì)于會(huì)引發(fā)崩潰的bug，我們利用崩潰時(shí)的堆棧信息判斷是否是重復(fù)bug. 對(duì)于沒有引發(fā)崩潰，但是引發(fā)ASan 報(bào)錯(cuò)的bug，我們利用出現(xiàn)錯(cuò)誤的代碼行位置判斷是否是重復(fù)bug. 實(shí)驗(yàn)結(jié)果顯示，在MariaDB 中，Pinecone 發(fā)現(xiàn)的bug 數(shù)量比Squirrel 多26. 7%；在MySQL 中，Pinecone 發(fā)現(xiàn)的bug 數(shù)量比Squirrel 多75%. 這說明在發(fā)現(xiàn)bug 的能力方面，Pinecone 要優(yōu)于Squirrel.

5 結(jié)論

本文使用實(shí)驗(yàn)統(tǒng)計(jì)數(shù)據(jù)證明了目前DBMS 模糊測(cè)試工具變異策略中存在的局限性，并且提出了一種自適應(yīng)變異策略來解決這個(gè)問題. 這種變異策略能夠自動(dòng)計(jì)算不同變異節(jié)點(diǎn)和變異操作的重要性，并根據(jù)重要性調(diào)整不同變異節(jié)點(diǎn)和變異操作被選擇的概率，從而為更重要的變異節(jié)點(diǎn)和變異操作分配更多計(jì)算資源. 本文在一種新的DBMS 模糊測(cè)試工具Pinecone 中實(shí)現(xiàn)了這種變異策略，并使用Pinecone 對(duì)MySQL 和MariaDB 這兩款廣泛使用的DBMS 進(jìn)行測(cè)試. 實(shí)驗(yàn)表明，與當(dāng)前先進(jìn)的DBMS 模糊測(cè)試工具Squirrel 相比，Pinecone能夠發(fā)現(xiàn)更多執(zhí)行路徑和程序bug. 這表明本文提出的自適應(yīng)變異策略能夠有效提升DBMS 模糊測(cè)試的效率.

參考文獻(xiàn)：

［1］ Zalewski. American fuzzy lop ［EB/OL］.［2023-12-

04］. https：//github. com/google/AFL.

［2］ B?hme M，Pham V T，Nguyen M D， et al. Directed

greybox fuzzing ［C］//Proceedings of the 2017 ACM

SIGSAC Conference on Computer and Communications

Security. Dallas Texas USA： Association for

Computing Machinery， 2017：2329.

［3］ B?hme M，Pham V T，Roychoudhury A. Coveragebased

greybox fuzzing as markov chain ［C］//Proceedings

of the 2016 ACM SIGSAC Conference on

Computer and Communications Security. Vienna

Austria： Association for Computing Machinery，

2016：1032.

［4］ Fioraldi A，Maier D，Ei?feldt H， et al. AFL++ ：

Combining incremental steps of fuzzing research［ C］//

Proceedings of the 14th USENIX Workshop on Offensive

Technologies （WOOT20）. Boston，MA：

USENIX Association， 2020.

［5］ Seltenreich A，Tang B，Mullender S. SQLSmith［ EB/

OL］.［2023-12-04］. https：//github. com/anse1/sqlsmith.

［6］ Seltenreich A，Tang B，Mullender S. SQLSmith bug

hunting ［EB/OL］. ［2023-12-04］. https：//github.

com/anse1/sqlsmith/wiki#score-list.

［7］ Zhong R，Chen Y，Hu H， et al. Squirrel：Testing database

management systems with language validity

and coverage feedback ［C］//Proceedings of the 2020

ACM SIGSAC Conference on Computer and Com ‐

munications Security. Virtual Event USA：Association

for Computing Machinery， 2020： 955.

［8］ Wang M，Wu Z，Xu X， et al. Industry practice of

coverage-guided enterprise-level DBMS fuzzing［ C］//

Proceedings of the 43rd International Conference on

Software Engineering：Software Engineering in Practice

（ICSE-SEIP）. Virtual Event，Spain：IEEE Press，

2021： 328.

［9］ Liang Y，Liu S，Hu H. Detecting logical bugs of

DBMS with coverage-based guidance ［C］//Proceedings

of the 31st USENIX Security Symposium

（USENIX Security 22）. Boston， MA：USENIX Association，

2022： 4309.

［10］ Fu J，Liang J，Wu Z， et al. Griffin：Grammar-free

DBMS fuzzing［C］//Proceedings of the Conference

on Automated Software Engineering （ASE22）.

MI， Rochester，USA：Association for Computing

Machinery， 2022： 1.

［11］ Jiang Z M，Bai J J，Su Z. DynSQL：Stateful fuzzing

for database management systems with complex and

valid SQL query generation ［C］//Proceedings of

USENIX Security Symposium（ USENIX Security）.

Anaheim， CA： USENIX Association， 2023： 4949.

［12］ Lyu C， Ji S， Zhang C， et al. MOPT：Optimized mutation

scheduling for fuzzers ［C］//Proceedings of the

28th USENIX Security Symposium（ USENIX Security

19）. Santa Clara，CA：USENIX Association，

2019： 1949.

［13］ Karamcheti S，Mann G，Rosenberg D. Adaptive greybox

fuzz-testing with thompson sampling ［C］//Proceedings

of the 11th ACM Workshop on Artificial Intelligence

and Security. Toronto， Canada：Association

for Computing Machinery， 2018： 37.

［14］ Wang X，Hu C，Ma R， et al. CMFuzz：Contextaware

adaptive mutation for fuzzers ［J］. Empirical

Software Engineering， 2021， 26： 1.

［15］ Lemieux C， Sen K. Fairfuzz：A targeted mutation

strategy for increasing greybox fuzz testing coverage

［ C］//Proceedings of the 33rd ACM/IEEE International

Conference on Automated Software Engineering.

Montpellier， France：Association for Computing

Machinery， 2018： 475.

［16］ Cha S K，Woo M，Brumley D. Program-adaptive mutational

fuzzing ［C］//Proceedings of the 2015 IEEE

Symposium on Security and Privacy. San Jose，CA，

USA： IEEE， 2015： 725.

［17］ Yue T，Tang Y，Yu B， et al. Learnafl：Greybox fuzzing

with knowledge enhancement ［J］. IEEE Access，

2019， 7： 117029.

［18］ Google. AddressSanitizer ［EB/OL］. ［2023-12-04］.

https：//github. com/google/sanitizers/wiki/Address‐

Sanitizer.

［19］ Foundation F S. GDB：The GNU project debugger

［EB/OL］. ［2023-12-04］. http：//www. sourceware.

org/gdb/.

（責(zé)任編輯： 伍少梅）