基于模糊測(cè)試生成多樣化的數(shù)據(jù)庫(kù)隔離級(jí)別測(cè)試案例

盧皙鈺, 劉 維, 翁思揚(yáng), 李可強(qiáng), 張 蓉

（1. 華東師范大學(xué) 數(shù)據(jù)科學(xué)與工程學(xué)院, 上海 200062;2. 工業(yè)和信息化部電子第五研究所, 廣州 511300 ）

0 引 言

數(shù)據(jù)庫(kù)隔離級(jí)別[1-2]定義了事務(wù)與其他事務(wù)進(jìn)行資源或者數(shù)據(jù)更新的隔離程度, 避免由數(shù)據(jù)訪問(wèn)沖突造成的數(shù)據(jù)庫(kù)狀態(tài)的不一致和不正確. 隔離級(jí)別實(shí)現(xiàn)的正確性對(duì)于事務(wù)型業(yè)務(wù)的部署至關(guān)重要.在事務(wù)數(shù)據(jù)庫(kù)的開(kāi)發(fā)或部署階段, 為了評(píng)估數(shù)據(jù)庫(kù)系統(tǒng)在并發(fā)環(huán)境下隔離級(jí)別實(shí)現(xiàn)的正確性, 需要生成多樣化的隔離級(jí)別測(cè)試案例并提升測(cè)試覆蓋度. 通過(guò)生成多樣化的測(cè)試案例, 涵蓋不同的并發(fā)事務(wù)操作、并發(fā)事務(wù)執(zhí)行交互方式以及事務(wù)隔離級(jí)別組合, 開(kāi)發(fā)人員能夠驗(yàn)證數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)是否能夠正確地處理并發(fā)操作. 多樣化的測(cè)試案例模擬了真實(shí)世界中數(shù)據(jù)庫(kù)并發(fā)訪問(wèn)模式和使用情況,能夠更全面地覆蓋數(shù)據(jù)庫(kù)系統(tǒng)的代碼路徑. 因此, 開(kāi)發(fā)人員能夠從測(cè)試案例執(zhí)行中發(fā)現(xiàn)潛在的并發(fā)操作問(wèn)題, 例如臟讀或不可重復(fù)讀等異常情況, 并從中獲得開(kāi)發(fā)需改進(jìn)的方向.

數(shù)據(jù)庫(kù)系統(tǒng)的隔離級(jí)別實(shí)現(xiàn)涉及復(fù)雜的數(shù)據(jù)結(jié)構(gòu)、算法和并發(fā)控制機(jī)制[3-6]. 不同的隔離級(jí)別 (如讀未提交、讀已提交、可重復(fù)讀和串行化) 需要在數(shù)據(jù)庫(kù)內(nèi)部實(shí)現(xiàn)鎖定、版本控制和事務(wù)管理策略等功能. 現(xiàn)代數(shù)據(jù)庫(kù)種類的數(shù)量越來(lái)越多, 包括關(guān)系型數(shù)據(jù)庫(kù)、NoSQL (not only SQL)數(shù)據(jù)庫(kù)和分布式數(shù)據(jù)庫(kù)等. 然而, 大多數(shù)數(shù)據(jù)庫(kù)產(chǎn)品不可開(kāi)源, 現(xiàn)有的測(cè)試工具通常只能對(duì)數(shù)據(jù)庫(kù)進(jìn)行黑盒測(cè)試[7]. 因此, 針對(duì)復(fù)雜的數(shù)據(jù)庫(kù)隔離級(jí)別實(shí)現(xiàn), 現(xiàn)有的黑盒測(cè)試工具在提供全面探索數(shù)據(jù)庫(kù)隔離級(jí)別細(xì)節(jié)方面存在一定的局限性.

傳統(tǒng)的數(shù)據(jù)庫(kù)隔離級(jí)別測(cè)試方法存在局限性. 首先, 采用手工測(cè)試的工作量巨大, 難以實(shí)現(xiàn)全面的測(cè)試覆蓋. 手工構(gòu)造測(cè)試用例需要消耗大量時(shí)間, 并且可能會(huì)忽略一些潛在的事務(wù)并發(fā)執(zhí)行邊界情況和漏洞. 其次, 由于數(shù)據(jù)庫(kù)系統(tǒng)中的事務(wù)和并發(fā)訪問(wèn)模式非常復(fù)雜, 不同的并發(fā)事務(wù)和執(zhí)行順序?qū)⒃跀?shù)據(jù)庫(kù)中呈現(xiàn)不同的行為, 基于手動(dòng)構(gòu)造測(cè)試規(guī)則的測(cè)試方法所生成的測(cè)試案例通常難以模擬所有并發(fā)事務(wù)的交互行為, 無(wú)法涵蓋到所有可能的輸入和邊界情況, 具有一定的測(cè)試覆蓋度限制[8].

因此, 為了深入了解數(shù)據(jù)庫(kù)的內(nèi)部實(shí)現(xiàn)細(xì)節(jié)、高效全面地探索隔離級(jí)別測(cè)試空間, 需要一種能夠與數(shù)據(jù)庫(kù)內(nèi)部實(shí)現(xiàn)結(jié)合的測(cè)試方法. 模糊測(cè)試[9-14]是一種廣泛應(yīng)用于軟件安全領(lǐng)域的測(cè)試技術(shù), 旨在通過(guò)廣泛探索輸入空間、變異和生成測(cè)試案例來(lái)構(gòu)建多樣化的負(fù)載, 發(fā)現(xiàn)系統(tǒng)中潛在的漏洞和錯(cuò)誤行為. 模糊測(cè)試在解決數(shù)據(jù)庫(kù)隔離級(jí)別測(cè)試方面具有明顯的優(yōu)勢(shì), 它以全面且自動(dòng)化的方式進(jìn)行測(cè)試,并生成多樣性和針對(duì)性的測(cè)試案例. 通過(guò)分析數(shù)據(jù)庫(kù)隔離級(jí)別測(cè)試行為, 測(cè)試可以獲取在執(zhí)行過(guò)程中代碼覆蓋的增長(zhǎng)信息. 并且, 模糊測(cè)試能夠調(diào)整測(cè)試生成的輸入數(shù)據(jù), 從而有針對(duì)性地探測(cè)廣泛而復(fù)雜的隔離級(jí)別測(cè)試路徑. 具體來(lái)說(shuō), 模糊測(cè)試結(jié)合了靜態(tài)分析和動(dòng)態(tài)測(cè)試, 通過(guò)監(jiān)測(cè)和分析測(cè)試的覆蓋情況, 自動(dòng)變異現(xiàn)有的測(cè)試用例以生成新的測(cè)試案例可以探索尚未覆蓋到的代碼路徑, 并高效地深入探索數(shù)據(jù)庫(kù)隔離級(jí)別的測(cè)試空間.

然而, 在利用模糊測(cè)試對(duì)數(shù)據(jù)庫(kù)隔離級(jí)別進(jìn)行自動(dòng)化測(cè)試時(shí), 需要考慮到數(shù)據(jù)庫(kù)隔離級(jí)別涉及多個(gè)并發(fā)事務(wù)之間的交互. 隨著模糊測(cè)試的進(jìn)行, 事務(wù)數(shù)量、隔離級(jí)別種類和并發(fā)沖突組合的增多, 測(cè)試中需要覆蓋的復(fù)合案例將會(huì)呈指數(shù)級(jí)增長(zhǎng). 在這種情況下, 窮盡所有可能的測(cè)試案例幾乎是不可行的,故而, 如何高效地探索測(cè)試空間是數(shù)據(jù)庫(kù)隔離級(jí)別模糊測(cè)試中的一個(gè)挑戰(zhàn). 在數(shù)據(jù)庫(kù)領(lǐng)域也出現(xiàn)了一系列模糊測(cè)試工具[15-20], 如Squirrel、Ratel、SQLRight 等, 旨在生成多樣化的數(shù)據(jù)庫(kù)測(cè)試案例, 提高測(cè)試效率和測(cè)試覆蓋度. 然而, 這些數(shù)據(jù)庫(kù)模糊測(cè)試工具除了無(wú)法有效支持并發(fā)事務(wù)測(cè)試, 還存在著無(wú)法提供隔離級(jí)別測(cè)試指導(dǎo)的限制. 上述工具的測(cè)試案例變異方式主要生成具有復(fù)雜查詢結(jié)構(gòu)的查詢語(yǔ)句, 無(wú)法控制模擬并發(fā)事務(wù)的執(zhí)行交互行為, 這使得上述工具在數(shù)據(jù)庫(kù)隔離級(jí)別行為的全面評(píng)估中受到限制.

為了解決對(duì)數(shù)據(jù)庫(kù)隔離級(jí)別核心功能的自動(dòng)化、高覆蓋有效測(cè)試的問(wèn)題, 通過(guò)對(duì)PostgreSQL[21]隔離級(jí)別實(shí)現(xiàn)的代碼和資料進(jìn)行詳細(xì)研讀[22-24], 本文面向隔離級(jí)別設(shè)計(jì)高效的代碼搜索策略來(lái)引導(dǎo)多樣化的測(cè)試案例生成. 本文將數(shù)據(jù)庫(kù)隔離級(jí)別測(cè)試空間定義成兩個(gè)維度, 即并發(fā)事務(wù)組合空間和并發(fā)事務(wù)執(zhí)行交互模式空間. 通過(guò)在并發(fā)事務(wù)組合空間中搜索, 測(cè)試能夠涵蓋多樣化的并發(fā)測(cè)試案例, 并對(duì)不同的并發(fā)場(chǎng)景進(jìn)行測(cè)試. 通過(guò)搜索并發(fā)事務(wù)執(zhí)行交互空間, 可以深入測(cè)試事務(wù)管理模塊中的關(guān)鍵細(xì)節(jié), 如讀取可見(jiàn)性的判斷、鎖的管理和事務(wù)協(xié)調(diào), 這有助于深入研究數(shù)據(jù)一致性和隔離級(jí)別的有效性.

為全面探索這兩個(gè)測(cè)試空間, 本文在模糊測(cè)試中提出了結(jié)構(gòu)化的測(cè)試輸入結(jié)構(gòu), 包含并發(fā)事務(wù)組合結(jié)構(gòu)和并發(fā)事務(wù)執(zhí)行交互模式結(jié)構(gòu). 并發(fā)事務(wù)組合結(jié)構(gòu)表示操作組合, 并發(fā)事務(wù)執(zhí)行交互模式影響了并發(fā)執(zhí)行下隔離級(jí)別允許的操作行為. 根據(jù)兩個(gè)空間維度的變異滿足數(shù)據(jù)庫(kù)隔離級(jí)別測(cè)試的要求,針對(duì)這兩個(gè)維度測(cè)試空間的變異搜索, 本文采用了廣度和深度的搜索策略, 其中廣度搜索策略用于探索并發(fā)事務(wù)組合的空間, 通過(guò)變異和調(diào)整事務(wù)的組合方式, 覆蓋多樣的并發(fā)測(cè)試場(chǎng)景; 深度搜索策略則專注于探索事務(wù)交互方式的空間, 通過(guò)變異和調(diào)整事務(wù)的執(zhí)行順序、并發(fā)沖突方式以及事務(wù)執(zhí)行方式, 以深入挖掘事務(wù)之間的執(zhí)行交互方式. 最后, 通過(guò)記憶化變異軌跡記錄中的反饋信息, 測(cè)試可以自適應(yīng)地應(yīng)用這兩個(gè)搜索策略, 以全面地探索測(cè)試空間并指導(dǎo)測(cè)試方向, 確保測(cè)試用例的多樣性、針對(duì)性和有效性. 這種指導(dǎo)性的方法能夠幫助測(cè)試更有針對(duì)性地選擇測(cè)試方向, 重點(diǎn)關(guān)注引起更多數(shù)據(jù)庫(kù)行為的測(cè)試路徑, 從而提高測(cè)試的效率和效果.

具體來(lái)說(shuō), 論文貢獻(xiàn)點(diǎn)包括以下兩點(diǎn):

(1) 實(shí)現(xiàn)了針對(duì)數(shù)據(jù)庫(kù)隔離級(jí)別測(cè)試的模糊工具SilverBlade, 引入結(jié)構(gòu)化輸入模型, 準(zhǔn)確模擬并發(fā)事務(wù)執(zhí)行交互; 引入基于反饋指導(dǎo)的廣度和深度的搜索策略, 解決了數(shù)據(jù)庫(kù)隔離級(jí)別測(cè)試中測(cè)試空間探索不充分的難題.

(2) 在流行的數(shù)據(jù)庫(kù)系統(tǒng)PostgreSQL 上進(jìn)行了測(cè)試. 相較于其他工具, SilverBlade 的方法在提高隔離級(jí)別關(guān)鍵區(qū)域的測(cè)試覆蓋率方面表現(xiàn)出色. SilverBlade 能夠生成更廣泛的測(cè)試用例, 并覆蓋了更多關(guān)鍵測(cè)試路徑.

1 相關(guān)工作

本章將介紹相關(guān)數(shù)據(jù)庫(kù)的模糊測(cè)試工具. 針對(duì)數(shù)據(jù)庫(kù)的模糊測(cè)試可分為兩種, 分別是基于生成的模糊測(cè)試和基于變異的模糊測(cè)試. 基于生成的模糊測(cè)試工具近年在數(shù)據(jù)庫(kù)測(cè)試領(lǐng)域得到廣泛研究, 其中包括著名的工具, 如RAGS、SQLancer 和SQLsmith 等, 它們的主要目標(biāo)是發(fā)現(xiàn)數(shù)據(jù)庫(kù)中的邏輯錯(cuò)誤和崩潰問(wèn)題. 這些工具根據(jù)特定的測(cè)試案例生成規(guī)則生成隨機(jī)的SQL 查詢語(yǔ)句以測(cè)試數(shù)據(jù)庫(kù), 通過(guò)隨機(jī)選擇表、列、運(yùn)算符和條件的組合來(lái)模擬真實(shí)環(huán)境中的各種異常情況和錯(cuò)誤.

在數(shù)據(jù)庫(kù)測(cè)試領(lǐng)域, 眾多現(xiàn)有工作對(duì)基于變異的模糊測(cè)試工具進(jìn)行了深入的研究和探索, 并且已經(jīng)有許多現(xiàn)有的工具可供使用. 這些工具根據(jù)其變異規(guī)則修改測(cè)試案例中的SQL 查詢語(yǔ)句, 生成新的測(cè)試案例, 進(jìn)而探索數(shù)據(jù)庫(kù)系統(tǒng)的不同行為和潛在缺陷, 如Squirrel、Ratel 和SQLRight 等工具, 將測(cè)試案例利用抽象語(yǔ)法樹(shù)[25]進(jìn)行解析并根據(jù)語(yǔ)法規(guī)則對(duì)其執(zhí)行各種變異操作以生成多樣性的查詢語(yǔ)句.

然而, 這些相關(guān)工具在測(cè)試數(shù)據(jù)庫(kù)隔離級(jí)別方面存在一定的局限性, 首先, 它們通常不支持并發(fā)事務(wù)測(cè)試, 也無(wú)法控制并發(fā)事務(wù)執(zhí)行交互. 其次, 基于變異生成的工具大多只針對(duì)查詢語(yǔ)句進(jìn)行變異操作, 而沒(méi)有充分考慮并發(fā)環(huán)境下的因素. 這樣的問(wèn)題將導(dǎo)致測(cè)試無(wú)法模擬數(shù)據(jù)庫(kù)在并發(fā)環(huán)境下處理事務(wù)的行為. SilverBlade 能夠根據(jù)數(shù)據(jù)庫(kù)隔離級(jí)別的特性支持并發(fā)事務(wù)進(jìn)行測(cè)試, 并更好地模擬并發(fā)事務(wù)場(chǎng)景和復(fù)雜的沖突情況, 從而確保更全面地探索數(shù)據(jù)庫(kù)隔離級(jí)別的測(cè)試空間.

2 方 法

2.1 方法總覽

SilverBlade 整體工作流程如圖1 所示. 在進(jìn)行測(cè)試之前, 首先, 使用基于GCC (GNU compiler collection)的GCOV 工具對(duì)被測(cè)試數(shù)據(jù)庫(kù)進(jìn)行插樁, 以獲取動(dòng)態(tài)的覆蓋信息, 并為后續(xù)的測(cè)試提供指導(dǎo). 其次, 將初始案例作為測(cè)試用例結(jié)構(gòu)的種子, 并進(jìn)行初始化. 最后, 將其放入測(cè)試隊(duì)列中, 準(zhǔn)備開(kāi)始測(cè)試過(guò)程. 一個(gè)模糊測(cè)試循環(huán)的工作步驟如下: ① 從測(cè)試隊(duì)列中提取一個(gè)測(cè)試案例 (記為t), 在測(cè)試案例中, 并發(fā)事務(wù)組合包含n個(gè)事務(wù), 每個(gè)事務(wù)被標(biāo)記為T(mén)i( 1 ≤i≤n) . 在測(cè)試案例中, 并發(fā)事務(wù)執(zhí)行交互結(jié)構(gòu)中存在沖突模式, 涉及3 個(gè)單獨(dú)的事務(wù)模版, 分別是T1、T2和T3. 每個(gè)事務(wù)都包含兩個(gè)操作, 分別記為o1和o2. 在變異引擎中提取測(cè)試用例記憶化的變異軌跡 (ttrace), 并根據(jù)ttrace的變異信息指導(dǎo)引擎選擇變異策略對(duì)測(cè)試用例進(jìn)行變異. ② 將經(jīng)變異引擎處理后的測(cè)試用例傳入數(shù)據(jù)庫(kù)進(jìn)行測(cè)試. ③ 測(cè)試結(jié)果分析器將此時(shí)整體測(cè)試的覆蓋信息與未執(zhí)行之前的整體覆蓋信息進(jìn)行對(duì)比, 若其判定此次測(cè)試導(dǎo)致數(shù)據(jù)庫(kù)整體覆蓋度增長(zhǎng), 則定義測(cè)試案例t為具有新行為的測(cè)試案例. ④ 如果經(jīng)過(guò)測(cè)試的測(cè)試用例具有新行為, 則將本次變異的內(nèi)容和覆蓋度增長(zhǎng)數(shù)量添加到ttrace中, 以指導(dǎo)后續(xù)測(cè)試的變異. 在模糊循環(huán)的最后階段, 將具有新行為的測(cè)試用例記錄到測(cè)試案例隊(duì)列中, 供后續(xù)測(cè)試使用.

圖1 SilverBlade 工作流程Fig. 1 Workflow of SilverBlade

SilverBlade 在模糊測(cè)試中引入基于結(jié)構(gòu)化輸入, 以及支持深度和廣度搜索的變異引擎以在數(shù)據(jù)庫(kù)隔離級(jí)別的測(cè)試空間進(jìn)行針對(duì)性搜索.

2.2 結(jié)構(gòu)化的測(cè)試輸入結(jié)構(gòu)

本節(jié)給出結(jié)構(gòu)化輸入結(jié)構(gòu)中并發(fā)事務(wù)組合和并發(fā)事務(wù)執(zhí)行交互模式的定義.

2.2.1 并發(fā)事務(wù)組合

并發(fā)事務(wù)測(cè)試由包含多個(gè)事務(wù)的并發(fā)事務(wù)組合控制, 并發(fā)事務(wù)組合的定義如下.

定義1令Tc表示一個(gè)并發(fā)事務(wù)組合,Tc={T1,T2,··· ,Tm},Tc由多個(gè)單事務(wù)模版Ti={o1,o2,··· ,oni}組成, 其中單事務(wù)模版Ti包含若干需要順序執(zhí)行的數(shù)據(jù)庫(kù)操作序列oj(2 ≤j≤ni-1) .記ni為T(mén)i的操作個(gè)數(shù),Ti包含的操作中oj是數(shù)據(jù)庫(kù)的讀操作r或是寫(xiě)操作w,o1是開(kāi)始操作,oni是提交操作或回滾操作.

如圖2 所示, 測(cè)試案例 a 的并發(fā)事務(wù)組合包含了兩個(gè)單事務(wù)模版T1和T2, 此事務(wù)組合構(gòu)建了由這兩個(gè)事務(wù)組成的并發(fā)場(chǎng)景.

圖2 結(jié)構(gòu)化輸入結(jié)構(gòu)的一個(gè)實(shí)例Fig. 2 An example of a structured input structure

2.2.2 并發(fā)事務(wù)執(zhí)行交互模式

并發(fā)事務(wù)執(zhí)行交互模式包含操作沖突模式和運(yùn)行時(shí)參數(shù), 如圖1 所示. 其中沖突模式的定義如下.

定義2令S表示由并發(fā)事務(wù)組合Tc={T1,T2,··· ,Tm}中所有事務(wù)操作組成的序列組合. 令沖突模式 c 表示一個(gè)沖突模式, 其可用圖來(lái)表述. 其節(jié)點(diǎn)表示具體的操作o, 邊表示操作之間的依賴關(guān)系和沖突關(guān)系. 在給定的并發(fā)事務(wù)模版Tc中,oi ∈Ti,oj ∈Tj, 邊 (oi,oj) 規(guī)定oi必須在oj之前執(zhí)行且oi和oj之間存在讀–寫(xiě)、寫(xiě)–讀或?qū)懆C寫(xiě)沖突中的一種. 其中S由 c 決定.

一個(gè)在PostgreSQL 中測(cè)試的測(cè)試案例如圖2 所示, 圖中間的沖突模式表明其在并發(fā)事務(wù)組合下可能發(fā)生的一種沖突情況. 該模式包含了讀–寫(xiě) (read-write, RW) 和寫(xiě)–讀 (write-read, WR) 沖突, 其中均涉及數(shù)據(jù)X. 圖2 下方展示了左邊的并發(fā)事務(wù)組合在這種沖突模式下的事務(wù)執(zhí)行順序. 一個(gè)沖突模式圖代表一種并發(fā)沖突場(chǎng)景, 它表示了事務(wù)之間的交互關(guān)系, 并定義了事務(wù)的執(zhí)行順序和依賴關(guān)系,不同的并發(fā)沖突情況可能會(huì)在事務(wù)管理機(jī)制下表現(xiàn)出不同的行為.

并發(fā)事務(wù)執(zhí)行交互模式的另一部分中, 運(yùn)行時(shí)參數(shù)包含4 種類型的參數(shù): 訪問(wèn)數(shù)據(jù)參數(shù)、訪問(wèn)鎖定模式參數(shù)、訪問(wèn)方式參數(shù)和隔離級(jí)別參數(shù). 它們控制著操作的執(zhí)行方式并決定了事務(wù)的并發(fā)行為和執(zhí)行交互模式. 訪問(wèn)數(shù)據(jù)參數(shù)控制操作數(shù)據(jù)的分布和狀態(tài), 通過(guò)調(diào)整它可以模擬不同的數(shù)據(jù)訪問(wèn)場(chǎng)景.例如, 模擬高并發(fā)訪問(wèn)同一數(shù)據(jù)塊或訪問(wèn)分布式數(shù)據(jù). 訪問(wèn)鎖定模式參數(shù)定義了事務(wù)對(duì)共享資源的鎖定方式, 決定了鎖沖突和競(jìng)爭(zhēng)情況. 訪問(wèn)方式參數(shù)表示了使用的索引和檢索方式, 不同的索引和檢索方式會(huì)影響鎖定行為; 隔離級(jí)別參數(shù)決定了事務(wù)的隔離級(jí)別以確定事務(wù)的數(shù)據(jù)可見(jiàn)性和隔離程度, 隔離級(jí)別將會(huì)對(duì)并發(fā)沖突和數(shù)據(jù)一致性產(chǎn)生影響. 通過(guò)調(diào)整這些參數(shù), SilverBlade 可以模擬不同的事務(wù)執(zhí)行策略和測(cè)試并發(fā)控制機(jī)制的實(shí)現(xiàn)細(xì)節(jié).

運(yùn)行時(shí)參數(shù)的實(shí)例如圖2 右邊所示, 訪問(wèn)數(shù)據(jù)參數(shù)設(shè)置了沖突操作中所訪問(wèn)的數(shù)據(jù)X,X是近期具有高訪問(wèn)頻率的數(shù)據(jù) (記為 h igh_heat ); 訪問(wèn)鎖定模式參數(shù)表明采用了默認(rèn)的鎖定方式; 訪問(wèn)方式參數(shù)表明啟用了默認(rèn)的索引方式 (記為 d efault ); 隔離級(jí)別參數(shù)將兩個(gè)事務(wù)的隔離級(jí)別都設(shè)置為可重復(fù)讀隔離級(jí)別 (記為 d efault ).

良好的輸入結(jié)構(gòu)對(duì)模糊測(cè)試至關(guān)重要, 因?yàn)槠溆绊懥四：郎y(cè)試的有效性和測(cè)試覆蓋度. 本節(jié)設(shè)計(jì)的測(cè)試輸入結(jié)構(gòu)為模糊測(cè)試提供了數(shù)據(jù)庫(kù)隔離級(jí)別的有效信息, 并指導(dǎo)模糊測(cè)試生成更有針對(duì)性的測(cè)試用例, 以全面地探索系統(tǒng)的多種行為. SilverBlade 的測(cè)試輸入結(jié)構(gòu)支持生成不同的并發(fā)事務(wù)組合和交互模式, 這種設(shè)計(jì)方式能夠更深入地測(cè)試事務(wù)管理機(jī)制中的關(guān)鍵細(xì)節(jié), 例如讀取可見(jiàn)性判斷、鎖管理和事務(wù)協(xié)調(diào). 因此, 合理的輸入結(jié)構(gòu)不僅提供了關(guān)鍵的信息和指導(dǎo), 使模糊測(cè)試更具針對(duì)性和有效性, 而且能夠全面評(píng)估數(shù)據(jù)庫(kù)隔離級(jí)別的行為.

2.3 基于反饋指導(dǎo)變異探索測(cè)試空間

本節(jié)將討論如何基于并發(fā)事務(wù)組合和并發(fā)事務(wù)執(zhí)行交互模式兩個(gè)結(jié)構(gòu)進(jìn)行變異, 并結(jié)合測(cè)試反饋信息來(lái)指導(dǎo)測(cè)試方向, 以全面搜索測(cè)試空間并產(chǎn)生新的測(cè)試行為. 通過(guò)對(duì)并發(fā)事務(wù)組合和交互模式的變異, 模糊測(cè)試能夠生成多樣化的測(cè)試用例, 從而覆蓋數(shù)據(jù)庫(kù)隔離級(jí)別下的各種可能執(zhí)行情況. 與現(xiàn)有基于變異生成的數(shù)據(jù)庫(kù)模糊測(cè)試工具不同, SilverBlade 的變異搜索方法能夠考慮事務(wù)的并發(fā)執(zhí)行, 主要包括以下兩個(gè)方面的內(nèi)容.

(1) 采用廣度和深度的搜索方法有效變異測(cè)試案例.

(2) 采用基于反饋指導(dǎo)的自適應(yīng)變異方法全面搜索測(cè)試空間.

2.3.1 基于廣度和深度搜索的變異

為了更加全面和有效地探索隔離級(jí)別測(cè)試空間, SilverBlade 采用了廣度搜索和深度搜索兩種針對(duì)性的搜索策略, 分別用于搜索并發(fā)事務(wù)組合測(cè)試空間和并發(fā)事務(wù)執(zhí)行交互模式測(cè)試空間. 通過(guò)這兩種策略的應(yīng)用, SilverBlade 能夠更全面地覆蓋可能的測(cè)試情況, 并且對(duì)隔離級(jí)別的測(cè)試空間進(jìn)行更加全面的探索. SilverBlade 采用基于廣度搜索的方式對(duì)測(cè)試案例并發(fā)事務(wù)組合執(zhí)行變異, 以生成多樣化的并發(fā)事務(wù)組合場(chǎng)景來(lái)探索事務(wù)組合測(cè)試空間. 具體的變異方式基于已有的測(cè)試案例中的并發(fā)事務(wù)組合, 采用隨機(jī)執(zhí)行刪除、替換其中包含的事務(wù)模版和添加新的事務(wù)模版的方法. 其中, 被替換和添加的單事務(wù)從測(cè)試隊(duì)列中隨機(jī)獲取. 圖3 中展示了一個(gè)變異的實(shí)例. 原始的并發(fā)事務(wù)結(jié)構(gòu)包含兩個(gè)單事務(wù)模版, 每個(gè)事務(wù)模版包含若干操作. 通過(guò)基于廣度搜索的變異, 原始并發(fā)事務(wù)組合中的T2被從測(cè)試隊(duì)列中提取的事務(wù)模版T23取代, 同時(shí)另一個(gè)從測(cè)試隊(duì)列中提取的事務(wù)模版T892被添加到了新的并發(fā)事務(wù)組合中.

圖3 基于廣度搜索變異的一個(gè)實(shí)例Fig. 3 An example of mutation based on breadth search

在基于廣度搜索的測(cè)試案例變異中, SilverBlade 重新組合一個(gè)測(cè)試案例的并發(fā)事務(wù)組合. 對(duì)于新增和修改的變異操作, SilverBlade 將隊(duì)列中現(xiàn)有的測(cè)試案例中的并發(fā)事務(wù)組合與當(dāng)前測(cè)試案例的并發(fā)事務(wù)組合進(jìn)行重新組合. 若初始化隊(duì)列中的測(cè)試案例均符合語(yǔ)法和語(yǔ)義的正確性, 在新增或修改并發(fā)事務(wù)組合時(shí), 變異所生成的新組合事務(wù)也能保持語(yǔ)法和語(yǔ)義的正確性. 通過(guò)這種方法,SilverBlade 能夠改變測(cè)試案例的并發(fā)事務(wù)組合, 確保測(cè)試案例的可執(zhí)行性并廣泛探索各種可能的測(cè)試情況.

除此之外, SilverBlade 采用深度搜索的方式對(duì)測(cè)試案例的并發(fā)事務(wù)執(zhí)行交互模式結(jié)構(gòu)進(jìn)行變異,以探索事務(wù)執(zhí)行交互模式的測(cè)試空間. 圖4 展示了一個(gè)原始測(cè)試案例變異后可能得到的新測(cè)試案例.深度搜索基于固定的并發(fā)事務(wù)組合, 通過(guò)變異沖突模式和運(yùn)行時(shí)參數(shù), 生成多樣的新事務(wù)執(zhí)行交互模式, 其中包含兩個(gè)核心的變異方式, 分別是沖突模式變異和運(yùn)行時(shí)參數(shù)變異.

(1) 變異沖突模式. 其變異方式如算法1 所示, 算法MutateConflictPattern (行1—7) 負(fù)責(zé)對(duì)沖突模式進(jìn)行變異以生成新的沖突模式, 并檢查和過(guò)濾冗余的新沖突模式以提升測(cè)試效率. 對(duì)于固定的并發(fā)事務(wù)組合 (記為c), 核心算法GenerateConflictPattern 負(fù)責(zé)生成c的新沖突模式, 并用沖突模式圖的方式記錄新的沖突模式 (記為g). 方法check (行4) 基于子圖同構(gòu)判定算法VF2[24-25]計(jì)算新生成的沖突模式g與c并發(fā)事務(wù)組合已生成的沖突模式集合 (記為s) 中每個(gè)圖的相似度, 以減少并發(fā)事務(wù)組合沖突模式的冗余. 在計(jì)算相似度時(shí), SilverBlade 考慮節(jié)點(diǎn)間操作的語(yǔ)義類型匹配和沖突邊的類型匹配以提高計(jì)算的準(zhǔn)確性. check 采取的方法是在計(jì)算新生成的沖突模式與已生成的并發(fā)事務(wù)歷史沖突模式集合s中的每個(gè)圖的相似度后, 確保若相似度高于預(yù)先設(shè)定的指定閾值, 則繼續(xù)進(jìn)行變異操作,直到相似度降至低于該閾值為止. 其中GenerateConflictPattern (行7—17) 是生成新的沖突模式的核心算法, 首先對(duì)事務(wù)組合的事務(wù)順序進(jìn)行隨機(jī)排序 (行8), 其次按照順序?qū)中排列連續(xù)的兩個(gè)事務(wù)c1(行12) 和c2(行13) 選取沖突對(duì). 其中, 方法random_choose_conflict 負(fù)責(zé)確定沖突操作, 其返回由c1和c2操作構(gòu)成的操作沖突對(duì)集合C. 其不僅保證選取沖突模式?jīng)_突邊的沖突操作不違反c1和c2事務(wù)內(nèi)操作執(zhí)行順序的規(guī)則, 且保證選取的沖突操作分別來(lái)自不同的事務(wù)和兩個(gè)操作都不為讀操作.最后, 將沖突對(duì)集合C中的每一個(gè)沖突對(duì)添加到新的沖突模式g中.

(2) 變異運(yùn)行時(shí)參數(shù). 分別變異4 種運(yùn)行時(shí)參數(shù)以生成新的組合參數(shù). 一個(gè)深度搜索變異的例子如圖4 所示, 在變異訪問(wèn)參數(shù)時(shí), 沖突操作訪問(wèn)了具有另一種特征的數(shù)據(jù)Y, 即不同訪問(wèn)熱度的數(shù)據(jù).在訪問(wèn)模式變異中, 增加新的索引 i ndex1以訪問(wèn)數(shù)據(jù). 同樣地, 在鎖定模式和隔離級(jí)別參數(shù)中也執(zhí)行了相應(yīng)的變異. 變異鎖定方式時(shí), 訪問(wèn)數(shù)據(jù)的鎖定模式由默認(rèn)方式變異為使用行鎖(row lock)的方式訪問(wèn)數(shù)據(jù). 在變異事務(wù)模版所使用的隔離級(jí)別時(shí), 將原來(lái)的可重復(fù)讀隔離級(jí)別(RR)變異為已提交讀隔離級(jí)別(RC). 為了確保并發(fā)事務(wù)組合能夠在新的運(yùn)行時(shí)參數(shù)下正常運(yùn)行, 變異的方式需要根據(jù)被測(cè)試數(shù)據(jù)庫(kù)所支持的選項(xiàng)進(jìn)行相應(yīng)的調(diào)整和變異. 通過(guò)對(duì)數(shù)據(jù)庫(kù)系統(tǒng)的配置、參數(shù)和功能進(jìn)行分析,SilverBlade 根據(jù)上述信息對(duì)測(cè)試案例進(jìn)行變異, 以確保變異后的運(yùn)行參數(shù)能在當(dāng)前被測(cè)數(shù)據(jù)庫(kù)中被正確運(yùn)行, 這樣能夠更好地探索數(shù)據(jù)庫(kù)隔離級(jí)別的潛在問(wèn)題, 并提高測(cè)試案例的可靠性和實(shí)用性.

算法1 MutateConflictPattern (t)p輸入: 事務(wù)組合 , 歷史沖突模式集合g輸出: 新的沖突模式s(p,s)1: Function MutateConflictPattern 2: While true do g(p) p 3: ← GenerateConflictPattern //根據(jù) 生成新的沖突模式g, s 4: If not check( ) then // VF2 檢查此沖突模式在此事務(wù)組合下是否冗余s,g g s 5: add( ) // 不冗余, 加入此事務(wù)組合的沖突模式集合 中g(shù) 6: Return // 成功生成不冗余的沖突模式(p)7: Function GenerateConflictPattern(p)8: Reshuffle // 為增加沖突操作組合的多樣性, 隨機(jī)生成并發(fā)事務(wù)組合的順序g(p)9: ← build_node ip1 ip1 p 10: For = 0 to length(p) – 1 do// 為 中單事務(wù)模版的序列號(hào)ip2 ip1 ip2 p 11: For = +1 to length(p) do // 為 中單事務(wù)模版的序列號(hào)p1 p ip1 p1 p ip1 12: ← .index( ) // 為 中第 個(gè)單事務(wù)模版p2 p ip2 p2 p ip2 13: ← .index( ) // 為 中第 個(gè)單事務(wù)模版(p1,p2) p1 p2 14: ← random_choose_conflict // 針對(duì) 和 隨機(jī)生成沖突C 15: For c in C do // 隨機(jī)生成沖突邊(g,(co1,co2)) (co1,co2) g 16: add // 增加新沖突 到新沖突模式 中g(shù) 17: Return

綜上所述, SilverBlade 在測(cè)試空間的兩個(gè)維度上采用了針對(duì)性的搜索策略. 該策略旨在廣泛地探索不同的并發(fā)事務(wù)組合, 從而覆蓋更多的并發(fā)場(chǎng)景, 并深入挖掘事務(wù)執(zhí)行交互的行為.

2.3.2 基于反饋指導(dǎo)的自適應(yīng)的搜索策略

為了有效地測(cè)試數(shù)據(jù)庫(kù)隔離級(jí)別的核心功能, SilverBlade 基于數(shù)據(jù)庫(kù)隔離級(jí)別實(shí)現(xiàn)的核心代碼覆蓋度增長(zhǎng)變化, 指導(dǎo)自動(dòng)化搜索變異. 為了有效解決適用于不同情況的搜索方式選擇問(wèn)題, 本文提出了一個(gè)自適應(yīng)搜索策略. 為了實(shí)現(xiàn)自適應(yīng)搜索策略, 首先, SilverBlade 定義核心代碼為涵蓋了與事務(wù)關(guān)鍵功能的實(shí)現(xiàn)代碼. 關(guān)鍵代碼的實(shí)現(xiàn)模塊包括事務(wù)管理、并發(fā)控制相關(guān)的鎖機(jī)制、多版本并發(fā)控制機(jī)制以及存儲(chǔ)模塊等文件夾的源文件. 這些核心代碼的功能協(xié)同工作, 確保了數(shù)據(jù)庫(kù)事務(wù)隔離級(jí)別的正確進(jìn)行. 其次, SilverBlade 提出了歷史搜索類型和核心代碼覆蓋平均增長(zhǎng)速率, 用于反饋測(cè)試案例的自適應(yīng)搜索. 最后, SilverBlade 使用測(cè)試案例變異軌跡來(lái)記錄測(cè)試案例的歷史變異信息, 并追蹤每次變異后測(cè)試案例執(zhí)行后核心代碼覆蓋的增長(zhǎng)情況, 以指導(dǎo)自適應(yīng)搜索過(guò)程.

自適應(yīng)搜索策略的核心方法如算法2 所示. 根據(jù)測(cè)試案例的歷史變異信息, SilverBlade 自適應(yīng)選擇搜索方式(記為m)對(duì)測(cè)試案例進(jìn)行變異, 變異方式包括深度搜索h和廣度搜索e. 針對(duì)一個(gè)測(cè)試案例的變異軌跡 (記為ttrace), 使用GetLastSearchType 檢查ttrace最后一次的搜索方式 (行2). 若最后一次的搜索方式是廣度搜索, 則返回此次深度搜索h, 以確定在此輪變異中是否采用深度搜索來(lái)對(duì)測(cè)試案例進(jìn)行變異 (行3); 否則, 算法需要根據(jù)測(cè)試案例變異軌跡進(jìn)行下一步判斷以確定變異方式(行4—16). 當(dāng)根據(jù)歷史覆蓋信息選擇變異方式時(shí), 首先, 從ttrace中獲取最后一次深度搜索、之前連續(xù)深度搜索的記錄和最后幾個(gè)連續(xù)的深度搜索的次數(shù)d. 然后, 根據(jù)最后的每一次深度搜索變異得到新覆蓋數(shù)據(jù)計(jì)算這幾次測(cè)試的核心代碼覆蓋平均增長(zhǎng)速率a(行6). 最后, 根據(jù)d和a的值判斷此輪變異使用何種變異搜索方式. 首先考慮當(dāng)搜索次數(shù)d小于閾值T時(shí), 算法有50%的概率繼續(xù)進(jìn)行深度搜索(行9), 否則隨機(jī)選擇搜索方式以提高搜索的隨機(jī)性 (行11). 反之, 當(dāng)d大于閾值T時(shí), 算法考慮根據(jù)a判斷選擇的變異類型 (行12—16). 這種情況下, 當(dāng)a小于閾值?時(shí), 意味著此測(cè)試案例在先前的深度搜索中表現(xiàn)不佳, 此時(shí)可以確定此輪搜索選擇廣度搜索對(duì)并發(fā)事務(wù)組合進(jìn)行變異, 此時(shí)變異產(chǎn)生新的并發(fā)事務(wù)組合可增加搜索的多樣性 (行13—14). 反之, 若a大于閾值?, 此輪將繼續(xù)進(jìn)行深度搜索(行15—16). 通過(guò)根據(jù)記憶化的變異軌跡信息和新覆蓋發(fā)現(xiàn)速率的自適應(yīng)調(diào)整, 搜索能夠集中在搜索空間中更有價(jià)值的區(qū)域, 從而使得搜索更加有效和有針對(duì)性.

(ttrace)算法2 GetSearchTypeByTrace(ttrace)輸入: 測(cè)試案例的變異軌跡輸出: 此次變異搜索模式m(ttrace)1: Function GetSearchTypeByTrace(ttrace) e 2: If GetLastSearchType == then//==表示表達(dá)判斷等于m h 3: ←trace 4: Else //檢查 最近時(shí)間中連續(xù)的深度搜索記錄(ttrace)5: ← GetDepthSearchTimes //檢查trace 最近時(shí)間中最后的深度搜索的次數(shù)d(ttrace,d)6: ← GetDepthSearchGrowthRate // 檢查trace 最后連續(xù)的深度搜索平均新覆蓋增長(zhǎng)率a 7: If d < T 8: If random_pick (0,1) == 0 then m ←e 9: // 繼續(xù)深度搜索10: Else

3 實(shí)驗(yàn)評(píng)估

本章旨在通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證SilverBlade 生成的測(cè)試案例對(duì)數(shù)據(jù)庫(kù)隔離級(jí)別的測(cè)試效果, 并解答以下兩個(gè)問(wèn)題.

問(wèn)題1: 相比于對(duì)比工具, SilverBlade 是否能夠生成多樣性的測(cè)試案例, 以有效覆蓋數(shù)據(jù)庫(kù)隔離級(jí)別核心實(shí)現(xiàn)代碼？

問(wèn)題2: SilverBlade 的結(jié)構(gòu)化測(cè)試輸入結(jié)構(gòu)以及基于深度和廣度搜索的變異方式能否提升數(shù)據(jù)庫(kù)隔離級(jí)別核心實(shí)現(xiàn)代碼的覆蓋率？

3.1 實(shí)驗(yàn)準(zhǔn)備

(1) 核心代碼定義. 根據(jù)PostgreSQL (8.0.31) 數(shù)據(jù)庫(kù)源代碼和文檔資料進(jìn)行分析, 將涵蓋了數(shù)據(jù)庫(kù)隔離級(jí)別實(shí)現(xiàn)的模塊代碼定義為實(shí)驗(yàn)的隔離級(jí)別測(cè)試核心代碼. 在PostgreSQL (版本14.4) 中,SilverBlade 定義的核心區(qū)域包括事務(wù)管理 (transam)、并發(fā)控制相關(guān)的鎖機(jī)制 (lmgr)、多版本并發(fā)控制機(jī)制 (snapmgr 和heap) 以及存儲(chǔ) (buffer 和heap) 模塊等文件夾的源文件.

(2) 測(cè)試設(shè)置. 在代碼覆蓋指標(biāo)設(shè)置上, SilverBlade 在實(shí)驗(yàn)中選擇隔離級(jí)別核心代碼的分支覆蓋度作為主要指標(biāo), 對(duì)隔離級(jí)別測(cè)試的覆蓋范圍和效果進(jìn)行評(píng)估. 在比較兩個(gè)實(shí)驗(yàn)的核心代碼分支覆蓋度時(shí), 較高的分支覆蓋度表明測(cè)試用例能夠觸發(fā)更多不同的代碼路徑, 同時(shí)也意味著實(shí)驗(yàn)涵蓋了更多與隔離級(jí)別相關(guān)的邏輯. 在測(cè)試初始種子設(shè)置上, 實(shí)驗(yàn)中初始種子測(cè)試案例的并發(fā)事務(wù)組合中事務(wù)均由Leopard 生成的事務(wù)隨機(jī)抽取而成, 生成的事務(wù)涵蓋了讀取和寫(xiě)入操作. 首先, 保證生成事務(wù)內(nèi)操作符合語(yǔ)法與語(yǔ)義正確. 其次, 保證生成操作均有效. 初始種子測(cè)試案例中沖突模式與運(yùn)行時(shí)參數(shù)均根據(jù)上述并發(fā)事務(wù)組合生成, 且分別通過(guò)本文所述生成方式保證初始種子的正確性.

(3) 實(shí)驗(yàn)平臺(tái). 實(shí)驗(yàn)將在一臺(tái)配置了6 個(gè)Intel(R) Core(TM) i5-8500 處理器的64 位Ubuntu 22.04 操作系統(tǒng)的機(jī)器上進(jìn)行. 每個(gè)處理器的時(shí)鐘頻率為3.00 GHz, 并且該機(jī)器擁有總計(jì)16 GB 的內(nèi)存. 本文將選擇在這個(gè)平臺(tái)上使用PostgreSQL (版本14.4) 來(lái)執(zhí)行所有實(shí)驗(yàn), 測(cè)試所用插樁工具基于GCC 的GCOV (11.3.0 版本) 實(shí)現(xiàn), 其中測(cè)試反饋的分支覆蓋信息為GCOV 所提供的信息.

(4) 對(duì)比工具. 實(shí)驗(yàn)選用BenchBase (使用TPC-C 和Smallbank 的并發(fā)事務(wù)負(fù)載) 作為對(duì)比工具.BenchBase 是支持并發(fā)事務(wù)測(cè)試的負(fù)載生成工具, 并提供了TPC-C 和Smallbank 的事務(wù)負(fù)載, 能夠生成并發(fā)的事務(wù)負(fù)載. 實(shí)驗(yàn)使用BenchBase 生成的并發(fā)事務(wù)負(fù)載在數(shù)據(jù)庫(kù)支持的隔離級(jí)別下進(jìn)行測(cè)試,從而對(duì)比和評(píng)估BenchBase 與SilverBlade 在測(cè)試隔離級(jí)別核心代碼區(qū)域表現(xiàn)的差異.

3.2 實(shí)驗(yàn)內(nèi)容

為了回答問(wèn)題1, 首先選擇BenchBase 作為SilverBlade 的對(duì)比測(cè)試工具, 其中使用的負(fù)載包括TPC-C 和Smallbank, 以對(duì)比SilverBlade 與BenchBase 在生成多樣性測(cè)試案例方面的能力, 并評(píng)估它們?cè)诟采w數(shù)據(jù)庫(kù)隔離級(jí)別核心實(shí)現(xiàn)代碼方面的效果. TPC-C 和Smallbank 負(fù)載均支持讀寫(xiě)操作,TPC-C 和Smallbank 是兩個(gè)常用的負(fù)載模型, 它們都支持事務(wù)并發(fā), 其事務(wù)包含若干讀寫(xiě)操作.BenchBase 支持生成的并發(fā)事務(wù)測(cè)試案例, 并能夠模擬真實(shí)世界的并發(fā)數(shù)據(jù)庫(kù)操作, 同時(shí)也能對(duì)數(shù)據(jù)庫(kù)多樣化的事務(wù)行為和交互方式進(jìn)行測(cè)試. 為了確保BenchBase 作為對(duì)比實(shí)驗(yàn)的可行性和有效性, 實(shí)驗(yàn)保證其能夠有效生成并發(fā)事務(wù)負(fù)載. 因此, 將實(shí)驗(yàn)中BenchBase 的terminal 參數(shù)設(shè)置為4, 并遵循兩種負(fù)載測(cè)試配置中的默認(rèn)值來(lái)設(shè)定其他參數(shù).

兩個(gè)對(duì)比組的實(shí)驗(yàn)持續(xù)了4.5 h. 兩個(gè)工具對(duì)數(shù)據(jù)庫(kù)代碼的測(cè)試覆蓋度如圖5 所示. 圖5 中核心代碼區(qū)分支覆蓋表明SilverBlade 的覆蓋度相較BenchBase 的TPC-C 和Smallbank 兩個(gè)測(cè)試更高, 且SilverBlade 分支覆蓋增長(zhǎng)速率比BenchBase 兩個(gè)對(duì)比測(cè)試更高. 相比BenchBase 生成的兩種并發(fā)事務(wù)負(fù)載, SilverBlade 有效提升了數(shù)據(jù)庫(kù)隔離級(jí)別核心代碼的覆蓋度.

圖5 SilverBlade 與BenchBase 測(cè)試結(jié)果對(duì)比Fig. 5 Comparison of SilverBlade and BenchBase test results

數(shù)據(jù)顯示, 在總的核心代碼分支覆蓋中, SilverBlade 的實(shí)驗(yàn)覆蓋了更多內(nèi)部實(shí)現(xiàn)代碼, 比BenchBase 的TPC-C 和Smallbank 并發(fā)事務(wù)負(fù)載測(cè)試的結(jié)果分別提升了48.5%和60.6%. 為了進(jìn)一步分析試驗(yàn)結(jié)果, 詳細(xì)分析了測(cè)試數(shù)據(jù)庫(kù)的覆蓋度文件, 對(duì)對(duì)比實(shí)驗(yàn)的測(cè)試效果進(jìn)行深入分析, 結(jié)果如表1 所示. 其中access/transam 負(fù)責(zé)事務(wù)管理, 包含事務(wù)管理器的核心部分, 具體負(fù)責(zé)處理數(shù)據(jù)庫(kù)中的事務(wù)操作、并發(fā)控制; access/heap 負(fù)責(zé)數(shù)據(jù)訪問(wèn)及存儲(chǔ)管理模塊, 其中包含數(shù)據(jù)庫(kù)隔離級(jí)別的多版本并發(fā)處理實(shí)現(xiàn)關(guān)鍵內(nèi)容; storage/lmgr 負(fù)責(zé)數(shù)據(jù)庫(kù)鎖管理, 包括并發(fā)事務(wù)獲取鎖、釋放鎖、死鎖管理以及鎖實(shí)現(xiàn)等與實(shí)務(wù)隔離級(jí)別相關(guān)的關(guān)鍵內(nèi)容. 表1 中的數(shù)據(jù)表明SilverBlade 在測(cè)試中覆蓋更多關(guān)鍵區(qū)域之中的代碼分支, 這表明SilverBlade 能夠生成更多樣化的測(cè)試案例.

表1 SilverBlade 與BenchBase 3 個(gè)核心代碼分區(qū)覆蓋結(jié)果Tab. 1 The coverage results of the three core code partitions of SilverBlade and BenchBase

SilverBlade 支持根據(jù)覆蓋信息不斷變異測(cè)試案例, 以推進(jìn)測(cè)試探索數(shù)據(jù)庫(kù)隔離級(jí)別測(cè)試空間. 為了進(jìn)一步分析這一特性, 詳細(xì)分析了測(cè)試數(shù)據(jù)庫(kù)的覆蓋度文件, 對(duì)兩個(gè)工具的測(cè)試效果進(jìn)行深入分析.相比于沒(méi)有反饋機(jī)制的BenchBase 工具, 在測(cè)試中, SilverBlade 不僅表現(xiàn)出更多的核心代碼分支被觸發(fā)和覆蓋, 而且表現(xiàn)出了更大的隔離級(jí)別相關(guān)代碼增長(zhǎng)速度 (表1). 將實(shí)驗(yàn)開(kāi)始到第10 分鐘和實(shí)驗(yàn)開(kāi)始到第4.5 小時(shí)的覆蓋度增長(zhǎng)進(jìn)行對(duì)比, 結(jié)果如表2. 結(jié)果顯示在此時(shí)間區(qū)間, SilverBlade 經(jīng)過(guò)核心代碼覆蓋指導(dǎo)變異測(cè)試進(jìn)行的核心代碼區(qū)的分支覆蓋增長(zhǎng)了851 個(gè), 而B(niǎo)enchBase 的TPC-C 和Smallbank分別僅增長(zhǎng)193 個(gè)和547 個(gè).

表2 SilverBlade 與BenchBase 核心代碼覆蓋增長(zhǎng)結(jié)果Tab. 2 The core code coverage growth results of SilverBlade and BenchBase

綜上分析表明, SilverBlade 在關(guān)鍵區(qū)域的覆蓋度更高且覆蓋增長(zhǎng)率更高, 這表明SilverBlade 能夠有效生成多樣性的測(cè)試案例, 更全面地探索隔離級(jí)別相關(guān)邏輯, 從而獲得了更高的代碼覆蓋度. 對(duì)比實(shí)驗(yàn)表明SilverBlade 在生成多樣性測(cè)試案例方面的優(yōu)勢(shì), 并展示其在數(shù)據(jù)庫(kù)隔離級(jí)別核心實(shí)現(xiàn)代碼覆蓋度方面的表現(xiàn). 通過(guò)深入覆蓋核心實(shí)現(xiàn)代碼, SilverBlade 能探索更多數(shù)據(jù)庫(kù)隔離級(jí)別測(cè)試空間路徑, 可為數(shù)據(jù)庫(kù)測(cè)試人員提供更好的測(cè)試案例.

為了回答問(wèn)題2, 本文驗(yàn)證SilverBlade 的設(shè)計(jì)在模糊測(cè)試中的效果, 進(jìn)行了對(duì)比實(shí)驗(yàn). 將原始實(shí)驗(yàn)記為SB, 將對(duì)比實(shí)驗(yàn)記為SB-, 其涉及停用結(jié)構(gòu)化輸入結(jié)構(gòu)隊(duì)列、基于廣度和深度的搜索變異引擎功能. 兩組對(duì)比實(shí)驗(yàn)初始種子是由Leopard 生成的語(yǔ)法和語(yǔ)義正確的事務(wù), 與SB 不同的是, SB- 將其發(fā)送給被測(cè)試的PostgreSQL 以模擬數(shù)據(jù)庫(kù)并發(fā)執(zhí)行, 同時(shí)SB- 不會(huì)對(duì)測(cè)試案例進(jìn)行變異來(lái)更新測(cè)試隊(duì)列以推進(jìn)測(cè)試進(jìn)行.

圖6 展示了這兩種方法在實(shí)驗(yàn)運(yùn)行4.5 h 后的實(shí)驗(yàn)結(jié)果, 結(jié)果顯示, 實(shí)驗(yàn)SB 相對(duì)于實(shí)驗(yàn)SB- 在核心代碼整體分支覆蓋方面有顯著提升, 覆蓋度增加了39%. 進(jìn)一步分析測(cè)試結(jié)果, 將一部分?jǐn)?shù)據(jù)庫(kù)隔離級(jí)別關(guān)鍵源文件的覆蓋數(shù)據(jù)進(jìn)行統(tǒng)計(jì), 如圖7 所示. 在支持隔離級(jí)別的多版本并發(fā)控制機(jī)制(圖7(a)和圖7(d))、事務(wù)管理 (圖7(b)) 和鎖實(shí)現(xiàn)的代碼區(qū)域 (圖7(c))方面中, 數(shù)據(jù)顯示SB 相對(duì)于SB- 具有更高的覆蓋率, 并且隨著時(shí)間的增長(zhǎng), 測(cè)試覆蓋率呈上升趨勢(shì). 這表明了, SB 相對(duì)于SB- 在生成多樣化的測(cè)試案例覆蓋數(shù)據(jù)庫(kù)隔離級(jí)別核心代碼中具有明顯優(yōu)勢(shì).

圖6 SB 與SB- 核心代碼區(qū)覆蓋結(jié)果對(duì)比Fig. 6 Comparison of core code area coverage results between SB and SB-

圖7 SB 和SB- 核心代碼覆蓋差異對(duì)比例子Fig. 7 Example of SB and SB- core code coverage comparison

數(shù)據(jù)顯示, 實(shí)驗(yàn)SB 相較于實(shí)驗(yàn)SB- 在覆蓋隔離級(jí)別核心區(qū)域上更有優(yōu)勢(shì), 這歸因于其支持結(jié)構(gòu)化輸入的測(cè)試隊(duì)列以及基于廣度和深度搜索的變異引擎. 首先, 實(shí)驗(yàn)SB 采用了結(jié)構(gòu)化輸入結(jié)構(gòu)的測(cè)試案例, 與實(shí)驗(yàn)SB- 的隨機(jī)并發(fā)事務(wù)測(cè)試相比, 它能更準(zhǔn)確地模擬具體的并發(fā)沖突模式, 并滿足隔離級(jí)別的要求. 這使得實(shí)驗(yàn)SB 能夠測(cè)試數(shù)據(jù)庫(kù)在并發(fā)環(huán)境下的真實(shí)行為, 對(duì)更多的數(shù)據(jù)沖突和隔離級(jí)別實(shí)現(xiàn)的關(guān)鍵細(xì)節(jié)進(jìn)行測(cè)試. 相比之下, 實(shí)驗(yàn)SB- 僅將初始種子的事務(wù)隨機(jī)發(fā)送給數(shù)據(jù)庫(kù)并發(fā)執(zhí)行,

無(wú)法保證是否存在沖突以及是否能夠涵蓋數(shù)據(jù)庫(kù)隔離級(jí)別實(shí)現(xiàn)的關(guān)鍵細(xì)節(jié), 所以其覆蓋隔離級(jí)別核心代碼的效率更低. 其次, 實(shí)驗(yàn)SB 啟用了變異引擎對(duì)測(cè)試案例進(jìn)行并發(fā)事務(wù)組合和執(zhí)行方式的變異.通過(guò)分析測(cè)試覆蓋度反饋, 實(shí)驗(yàn)SB 能夠判斷具有新行為的測(cè)試案例, 并實(shí)時(shí)更新測(cè)試隊(duì)列. 于是, 在后續(xù)的測(cè)試中, 這些具有新行為案例可以繼續(xù)被選擇進(jìn)行變異和測(cè)試, 這樣的機(jī)制可以推動(dòng)測(cè)試的進(jìn)一步進(jìn)行. 相比之下, 實(shí)驗(yàn)SB- 不支持自適應(yīng)變異的能力, 可能導(dǎo)致其測(cè)試案例的重復(fù)或缺乏多樣性,從而限制了隔離級(jí)別核心代碼測(cè)試覆蓋度的提升速率.

綜上所述, 以上測(cè)試結(jié)果表明, SilverBlade 能夠?qū)?shù)據(jù)庫(kù)隔離級(jí)別核心代碼模塊進(jìn)行有效測(cè)試,并在與對(duì)比工具進(jìn)行對(duì)比實(shí)驗(yàn)時(shí), 測(cè)試結(jié)果數(shù)據(jù)顯示SilverBlade 在隔離級(jí)別關(guān)鍵區(qū)域的測(cè)試覆蓋率方面表現(xiàn)更佳. 實(shí)驗(yàn)表明SilverBlade 能夠生成多樣性的測(cè)試案例以更廣泛地覆蓋數(shù)據(jù)庫(kù)隔離級(jí)別核心實(shí)現(xiàn)代碼 (問(wèn)題1). 同時(shí), 實(shí)驗(yàn)也說(shuō)明, 通過(guò)采用結(jié)構(gòu)化測(cè)試輸入結(jié)構(gòu)、基于深度和廣度搜索的搜索策略, SilverBlade 在并發(fā)事務(wù)組合和并發(fā)事務(wù)執(zhí)行交互的測(cè)試空間中進(jìn)行更高效和全面的搜索. 這種方法有效地提升了隔離級(jí)別核心代碼區(qū)的測(cè)試覆蓋度 (問(wèn)題2).

4 結(jié)論與展望

綜上所述, 本文研究了數(shù)據(jù)庫(kù)隔離級(jí)別內(nèi)容模糊測(cè)試, 并實(shí)現(xiàn)了工具SilverBlade. 首先, 通過(guò)結(jié)構(gòu)化測(cè)試結(jié)構(gòu)的設(shè)計(jì), SilverBlade 生成多樣化的并發(fā)測(cè)試案例, 并模擬這些案例的事務(wù)執(zhí)行交互, 從而提高了數(shù)據(jù)庫(kù)隔離級(jí)別測(cè)試的覆蓋度.

本文所提出的工具SilverBlade 支持深度和廣度搜索的變異方式, 這樣的方法使得測(cè)試能夠更全面地搜索數(shù)據(jù)庫(kù)隔離級(jí)別的測(cè)試空間. 廣度搜索變異方式引入多樣性的事務(wù)組合, 深度搜索變異方式增加了事務(wù)執(zhí)行交互的多樣性, 以更好地模擬具有讀取和寫(xiě)入操作序列的并發(fā)事務(wù)執(zhí)行. 通過(guò)二者結(jié)合, 可以促進(jìn)測(cè)試生成多樣的事務(wù)并發(fā)場(chǎng)景, 從而對(duì)數(shù)據(jù)庫(kù)隔離級(jí)別核心代碼進(jìn)行全面的測(cè)試.

實(shí)驗(yàn)結(jié)果表明, 與傳統(tǒng)對(duì)比工具相比, 本文設(shè)計(jì)的原型系統(tǒng)SilverBlade 在測(cè)試數(shù)據(jù)庫(kù)隔離級(jí)別時(shí)具有更好的測(cè)試能力. 通過(guò)提高測(cè)試覆蓋度, SilverBlade 能夠更全面地探索數(shù)據(jù)庫(kù)隔離級(jí)別測(cè)試空間,這更有助于開(kāi)發(fā)人員發(fā)現(xiàn)并糾正在傳統(tǒng)測(cè)試方法中可能被忽視的潛在隔離級(jí)別問(wèn)題. 本文所提出的模糊測(cè)試方法通過(guò)提高測(cè)試覆蓋度, 為數(shù)據(jù)庫(kù)隔離級(jí)別的評(píng)估和改進(jìn)提供了新的視角.

未來(lái)的研究方向計(jì)劃進(jìn)一步擴(kuò)展和優(yōu)化SilverBlade 模糊測(cè)試方法, 以進(jìn)一步提高SilverBlade 測(cè)試能力. 可以探索更多的測(cè)試案例生成技術(shù), 如基于更新穎模型的生成方法或符號(hào)執(zhí)行技術(shù), 以生成更多的有代表性的測(cè)試案例. 此外, 可以考慮利用人工智能技術(shù)與動(dòng)靜態(tài)分析的方法相結(jié)合, 以提高對(duì)數(shù)據(jù)庫(kù)隔離級(jí)別智能化的全面檢測(cè)能力.