鑒源論壇 · 觀模丨淺談隨機(jī)測試

作者 |黃杉華東師范大學(xué)軟件工程學(xué)院博士

蘇亭 華東師范大學(xué)軟件工程學(xué)院教授

首發(fā) |鑒源論壇 · 觀模

01 什么是隨機(jī)測試（Random Testing）

隨機(jī)測試是一種使用隨機(jī)、相互獨立的程序輸入來對計算機(jī)程序進(jìn)行測試的黑盒軟件測試（在完全忽略程序內(nèi)部實現(xiàn)細(xì)節(jié)的情況下進(jìn)行測試）技術(shù)。在處理完隨機(jī)且獨立的程序輸入后，程序輸出的結(jié)果將會和軟件規(guī)格說明（software specifications）中所描述的軟件行為進(jìn)行比對來判斷該測試是否通過。

隨機(jī)測試的核心思想接近于無限猴子定理[1]（The Infinite Monkey Theorem），所以隨機(jī)測試也被稱為Monkey Testing。無限猴子定理是來自émile Borel的一本出版于1909年的概率相關(guān)的書籍，其中描述了這樣一個場景：當(dāng)一只猴子在打字機(jī)鍵盤上不限時間地隨機(jī)敲擊，它可能輸出任何給定文章，例如莎士比亞的完整作品，并且這種可能性隨著時間的增長會不斷地接近100% 。換用測試的語言來描述則是測試程序通過不斷地生成測試輸入，其能完整測試整個程序并尋找到程序中異常的可能性會不斷增大。

02早期的隨機(jī)測試

最早對隨機(jī)測試技術(shù)的使用可以追溯到上個世紀(jì)五十年代，那時的數(shù)據(jù)還存儲在穿孔卡片（Punched Card）上。程序員會將扔進(jìn)垃圾桶中的卡片或者標(biāo)記有隨機(jī)數(shù)字的卡組作為計算機(jī)程序的輸入來進(jìn)行隨機(jī)測試。

當(dāng)隨機(jī)測試被廣泛認(rèn)定為測試程序的最差方式時，Duran和Ntafos兩人在1981年正式地對使用隨機(jī)測試技術(shù)對程序進(jìn)行測試的有效性進(jìn)行了調(diào)研，結(jié)果表明相對于系統(tǒng)化的測試技術(shù)，隨機(jī)測試是一個成本低收益高的替代品。

后來在1983年，蘋果公司的Steve Capps開發(fā)了一款名為“The Monkey”的隨機(jī)輸入生成工具用來對傳統(tǒng)的MacOS應(yīng)用進(jìn)行測試。他對工具的命名就是化用了無限猴子定理。

1991年，一款名叫 “crashme” 的工具發(fā)布。這款工具意在通過隨機(jī)執(zhí)行帶有隨機(jī)參數(shù)的系統(tǒng)調(diào)用來測試Unix以及類Unix操作系統(tǒng)的魯棒性。

03隨機(jī)測試的優(yōu)缺點

3.1 優(yōu)點

（1）容易實現(xiàn)和使用。隨機(jī)測試并不需要知曉程序細(xì)節(jié)，并且輸入也通過隨機(jī)生成。

（2）對程序不存在偏見。由于隨機(jī)測試的輸入都是隨機(jī)生成的，不存在人為因素影響，也就不會因為對程序某一部分信任而忽略掉潛在的漏洞。

（3）能快速查找漏洞。隨機(jī)測試的測試速度快，通過快速和大量的測試，能夠在短時間內(nèi)找到大量的候選漏洞（對漏洞的確認(rèn)還需要人工參與）。

3.2 缺點

（1）尋找漏洞的精度不高。由于隨機(jī)測試的完全隨機(jī)性，尋找到的漏洞很可能是一些無關(guān)緊要的錯誤。

（2）過于隨機(jī)導(dǎo)致對程序的代碼覆蓋率不高。大部分人認(rèn)為對程序的測試過于依賴隨機(jī)，不如通過人工白盒測試的方式來更精確地測試程序。

04隨機(jī)測試進(jìn)階—模糊測試（Fuzzing）

在1988年的一個風(fēng)雨交加的夜晚，威斯康星大學(xué)的Barton Miller教授在自己的公寓中通過一條電話線連接他在學(xué)校中的計算機(jī)。暴風(fēng)雨引發(fā)了電話線中的信號錯亂，以至于所連接的Unix終端不斷接收到糟糕的命令輸入，最終導(dǎo)致了系統(tǒng)崩潰。頻發(fā)的崩潰使這位講授操作系統(tǒng)課程的教授感到驚訝，因此他腦海中浮現(xiàn)了一個對Unix系統(tǒng)進(jìn)行魯棒性測試的念頭。于是他在給學(xué)生的課程作業(yè)中寫道：

The goal of this project is to evaluate the robustness of various UNIX utility programs, given an unpredictable input stream. This project has two parts. First, you will build a fuzz generator... Second, you will take the fuzz generator and use it to attack as many UNIX utilities as possible, with the goal of trying to break them... [2]

教授在作業(yè)中要求學(xué)生開發(fā)一個模糊生成器（fuzz generator），這個生成器可以產(chǎn)生不可預(yù)測的輸入流，然后將這些雜亂的輸入給到Unix系統(tǒng)設(shè)施，然后試圖攻陷這些設(shè)施并找到和分析引發(fā)錯誤的隨機(jī)輸入和原因。這就是模糊測試的誕生，教授在作業(yè)中使用的fuzz一詞也就被用來命名這一技術(shù)。

從上文可以看到模糊測試在誕生之初和隨機(jī)測試十分相似，都是通過隨機(jī)的輸入來對計算機(jī)程序進(jìn)行功能行為測試。下面的Python代碼片段給出了一個最簡單的模糊器（fuzzer）例子。這個模糊測試器接收三個參數(shù)：最大長度（max_length）、字符的ASCII碼起始值（char_start）以及字符的ASCII碼從起始到結(jié)束的范圍（char_range）。該模糊器將生成一個長度為max_length的包含ASCII碼在[char_start, char_start + char_range)范圍內(nèi)的字符串。

圖 1

所以最原始的模糊測試和隨機(jī)測試擁有相同的優(yōu)缺點。其中最顯著的問題就是由于其完全的隨機(jī)性，尋找到的程序錯誤過于刁鉆?？赡苷业降某绦蝈e誤只是因為錯誤的輸入導(dǎo)致而和程序本身實現(xiàn)無關(guān)，或者程序使用人員根本就不會使用像模糊測試器生成的輸入，所以不會在軟件設(shè)計的考慮范疇之內(nèi)，甚至模糊測試根本就沒有測試到程序的主要功能。

無論如何模糊測試還是有其可取之處的（尤其是測試速度快、易于實現(xiàn)），所以后來的研究者們不斷想方設(shè)法地，尤其是針對如何更好地生成測試輸入方面去提高模糊測試的精度（找到的錯誤確實是和軟件規(guī)范說明或預(yù)期設(shè)想行為不符）和深度（能更多地去測試程序的主要功能）來完善模糊測試的實用性。實現(xiàn)這些目標(biāo)的主要方法就是通過一些靜態(tài)（基于覆蓋率、基于變異）或動態(tài)（基于搜索、基于語法）的方式給模糊器提供額外的輔助信息來幫助模糊器更高效地生成、更有效地測試輸入，而不再是完全隨機(jī)，這也促使模糊測試從黑盒測試向灰盒測試進(jìn)行轉(zhuǎn)變。下文會進(jìn)行具體介紹。

現(xiàn)在的模糊測試技術(shù)可以有幾種劃分方式（不限于此）：

·一種模糊測試技術(shù)可以是基于生成（generation-based）的或者基于變異（mutation-based），取決于它是在沒有任何參考的情況下生成隨機(jī)輸入，還是在現(xiàn)有輸入的基礎(chǔ)上進(jìn)行修改，也就是所謂的變異；

·一種模糊測試技術(shù)可以是愚笨的（dumb）或者聰明的（smart），取決于它是否對測試輸入的結(jié)構(gòu)敏感；

·一種測試技術(shù)可以是白盒、灰盒或者黑盒（基本上不再使用），取決于它是否對程序結(jié)構(gòu)信息或者程序運(yùn)行信息敏感。

目前最流行的模糊測試工具主要有AFL以及AFL的擴(kuò)展系列，如AFLFast、AFL++、AFLGo等。

4.1基于覆蓋率的模糊測試（Coverage-Based Fuzzing）

對于如何提高模糊測試精度和深度的探索，其中一種是利用了代碼覆蓋率[3]（code coverage）這一概念。代碼覆蓋率包括函數(shù)覆蓋率（function coverage）、語句覆蓋率（statement coverage）、邊覆蓋率（edge coverage）以及條件覆蓋（condition coverage）率等多種覆蓋準(zhǔn)則，這些覆蓋率都在一定程度上反映了測試用例對于程序代碼的測試程度，即代碼覆蓋率越高，測試用例對代碼的測試程度越高。近期的一項工作[4]也觀察到模糊測試技術(shù)的代碼覆蓋率和能找到程序中的錯誤具有強(qiáng)相關(guān)性。

下面的Python代碼片段將給出簡單的例子。當(dāng)輸入inp為一個正數(shù)的時候，程序執(zhí)行過程中將會執(zhí)行第 2 行和第 3 行的代碼語句，則語句覆蓋率為 2 / 6 = 33.3%。另外對于條件覆蓋率來說，整個函數(shù)中函數(shù)有三個 if 條件語句，每一個 if 條件語句都有真假兩種情況，則根據(jù)組合原理該函數(shù)共有 6 個條件分支。在上述情況下，程序執(zhí)行過程中只有第一個 if 條件語句為真的分支被執(zhí)行，則條件覆蓋為 1 / 6 = 16.7%。對于輸入 inp 為零和負(fù)數(shù)的情況，語句覆蓋為 3 / 6 = 50% 和 4 / 6 = 66.7%，條件覆蓋率為 2 / 6 = 33.3% 和 3 / 6 = 50%。

圖 2

在模糊測試中對于覆蓋率的利用，主要是在測試用例的生成過程中。模糊器首先生成一定個數(shù)的隨機(jī)輸入，這些輸入被稱為種子（seed）。接著模糊器將這些種子輸入程序，回收程序執(zhí)行的結(jié)果和預(yù)先選定的覆蓋率指標(biāo)。接下來模糊器會根據(jù)覆蓋率高低，將覆蓋率低的種子丟棄，將覆蓋率高的種子保留并對這些種子進(jìn)行操作生成一批新種子再作為輸入運(yùn)行程序。重復(fù)上述過程到覆蓋率不能夠更進(jìn)一步提高時，終止測試。

4.2 基于變異的模糊測試（Mutation-Based Fuzzing）

由于最初的模糊器完全靠隨機(jī)生成程序輸入，模糊測試很難生成出符合程序要求的合法輸入，以至于很難測試到程序的核心功能，同時這也是代碼覆蓋率極低的一個原因。于是基于變異的模糊測試被提出來解決這個問題。

變異的核心思想是對現(xiàn)有的種子（種子可以合法也可以不合法，但大多數(shù)情況下會使用合法的種子，這樣通過變異得到的種子后代質(zhì)量較高）以及通過變異得到種子后代進(jìn)行操作來生成測試輸入。具體的變異操作需要測試人員執(zhí)行制定。假如針對一個計算機(jī)程序的一個合法的程序輸入為“3+0”，那么在指定變異操作為隨機(jī)增加、刪除和替換字符串中的某一個字符這三種操作時，經(jīng)過變異之后的輸入就有多種可能，如“3 + - 0”、“3 +”、“3 / 0”。將這些通過變異得到的種子后代扔入程序中運(yùn)行，這就是基于變異的模糊測試。

變異操作可以被設(shè)計為更加復(fù)雜精細(xì)的過程，例如結(jié)合其他種子質(zhì)量評估指標(biāo)進(jìn)行變異或者進(jìn)行某種針對性變異操作。上一小節(jié)末尾描述的將變異操作和覆蓋率指標(biāo)進(jìn)行結(jié)合來反復(fù)對程序進(jìn)行測試，這樣可以很好地利用這兩種方法的優(yōu)勢，從而增強(qiáng)模糊測試的有效性。著名的模糊測試工具AFL就是基于這樣的思路開發(fā)的。

4.3基于搜索的模糊測試（Search-Based Fuzzing）

基于搜索的模糊測試主要依賴于搜索算法。搜索算法也被稱為啟發(fā)式算法（heuristic algorithm），其核心思想是通過某些程序信息來啟發(fā)和引導(dǎo)算法執(zhí)行。這些算法的靈感大多是來自自然界的現(xiàn)象，如模擬退火算法和本小節(jié)會介紹的遺傳算法。而它們之所以被稱為搜索算法，是因為執(zhí)行這些算法可以在較大的搜索空間中比隨機(jī)算法或遍歷算法更高效。同樣以上一小節(jié)的計算機(jī)程序輸入為例，模糊器對該程序進(jìn)行模糊測試本質(zhì)上就是在不斷地探索其輸入空間，該輸入空間中包含了任意長度的合法或不合法的表示四則運(yùn)算表達(dá)式的字符串。想要通過測試來挖掘出程序中隱藏的缺陷，就是在輸入空間中搜索到特定的輸入使得該程序在運(yùn)行時出現(xiàn)異常行為；想要滿足更廣的程序覆蓋率，就是在輸入空間中搜索到特定的輸入使得讓該程序運(yùn)行時執(zhí)行更多的程序語句。

因此搜索算法也就自然而然地與模糊測試結(jié)合在了一起，來使模糊器生成更優(yōu)質(zhì)的程序測試輸入。下面將對基于結(jié)合代碼覆蓋率的遺傳算法的模糊測試進(jìn)行簡單的介紹。

我們構(gòu)建一個簡單函數(shù) fun2，該函數(shù)將判斷特定字符是否存在于輸入字符串中，然后對應(yīng)分支返回一個整型數(shù)字。

圖 3

在這個例子中我們給定模糊器的初始種子，為“axxx”，“xxxb”、“xxxc”和“xxxd”。我們首先將這些種子作為輸入來運(yùn)行這個函數(shù)，得到每個種子的語句覆蓋數(shù)量，分別是 3 、2 、2、2 。輸入“axxx”是可以讓程序執(zhí)行第 2、3 和 8 行語句，而后三個輸入只能執(zhí)行第 2 和 8 行語句。第一輪測試已經(jīng)結(jié)束，這時我們根據(jù)種子的語句覆蓋數(shù)量來生成下一次測試輸入集合，具體過程為從種子中選取語句覆蓋數(shù)量最多的兩個作為親代來進(jìn)行交叉變異（模擬自然界的遺傳現(xiàn)象）。由于后三個種子的數(shù)據(jù)覆蓋數(shù)量都為 2 ，則在選擇時會隨機(jī)選取。假設(shè)“axxx”和“xxxb”得到了選擇，則繼續(xù)對這兩個種子進(jìn)行交叉變異，此處交叉變異定義為交換兩個種子的右半部分子串，即得到的子代為“axxb”和“xxxx”。重復(fù)這樣的選擇并交叉變異的過程直到子代數(shù)量等于初始種子數(shù)量。假定經(jīng)過上述過程我們最后得到了“axxb”、“xxxx”、“axxc”和“xxxx”這四個子代，然后就繼續(xù)重復(fù)整個執(zhí)行過程，也就是將這些子代輸入程序繼續(xù)運(yùn)行遺傳算法來生成更加優(yōu)質(zhì)的測試輸入，最終提高代碼覆蓋率和異常檢測能力。

從上述例子中可以看到在子代中的“axxb”不僅將原本“axxx”的語句覆蓋數(shù)量從 3 提升到了 4，并且能更深入地探索整個函數(shù)中的條件分支。但可以看到對于上述例子中假設(shè)得到子代整個算法已經(jīng)無法再有進(jìn)步了，因為這些子代不論怎么交叉變異也無法得到一個包含abc三個字母的字符串。在實際工業(yè)生產(chǎn)環(huán)境中算法本身會更加復(fù)雜，測試種子會經(jīng)過精心生成和挑選，同時納入更多指標(biāo)進(jìn)行算法引導(dǎo)，對交叉變異的過程也不會只是簡單地字符串交換。

4.4 通過文法進(jìn)行模糊測試（Fuzzing with Grammars）

當(dāng)程序的輸入具有一定規(guī)范和結(jié)構(gòu)的（比如數(shù)據(jù)庫或者API的輸入），人們開始嘗試通過文法（Grammar）來幫助模糊器生成合法規(guī)范的測試輸入，屬于前面提到的基于生成（Generation-based）的模糊測試技術(shù)。

下面展示了一個簡單的文法，該文法描述的是含有小數(shù)或整數(shù)的加減乘除的四則運(yùn)算表達(dá)式，如 (1 + 2) * (3.4 / 5.6 - 789) 。使用該文法，從 非終止符（non-terminal）開始展開，最終就可以得到一個可用于測試計算程序的合法的四則運(yùn)算表達(dá)式。

圖 4

對于表達(dá)式 (1 + 2) * 3 的部分推導(dǎo)過程如下，過程中遵循最左推導(dǎo)。推導(dǎo)中剩下的部分讀者可以自行嘗試完成。

圖 5

通過這樣來產(chǎn)生測試輸入相比于純隨機(jī)的方式不僅產(chǎn)生的種子質(zhì)量高，并且符合程序輸入規(guī)范，能夠節(jié)省無效測試用例的時間開銷從而提高測試效率。

05總結(jié)

隨機(jī)測試為軟件測試提供了一個在黑盒情況下快速和大量地測試程序的全新思路，其進(jìn)階版模糊測試更是在經(jīng)過包括上述基于覆蓋率、基于變異、基于搜索以及文法輔助在內(nèi)的多種方法的增強(qiáng)之后，成為了當(dāng)前工業(yè)環(huán)境下軟件測試的主流選擇，被廣泛應(yīng)用于人工智能測試、自動駕駛系統(tǒng)測試、數(shù)據(jù)庫系統(tǒng)測試、API測試等各種測試場景。雖然克服了隨機(jī)測試和模糊測試誕生之初的缺陷和問題，當(dāng)下的模糊測試仍然有待提高進(jìn)步，例如對模糊測試過程中對觸發(fā)的程序錯誤的類型進(jìn)行識別、整理和分類，以及對引發(fā)錯誤的根源誘因的分析等。學(xué)界和工業(yè)界也對傳統(tǒng)靜態(tài)分析工具如符號執(zhí)行技術(shù)和模糊測試技術(shù)相結(jié)合的道路在不斷地探索。

參考資料：

[1]“Infinite Monkey Theorem.” In Wikipedia, September 1, 2022.

[2] Bart Miller. 1988. [3] “Code Coverage.” In Wikipedia, July 7, 2022.

[4] Marcel B?hme, László Szekeres, and Jonathan Metzman. 2022. On the reliability of coverage-based fuzzer benchmarking. In Proceedings of the 44th International Conference on Software Engineering (ICSE '22). Association for Computing Machinery, New York, NY, USA, 1621–1633.

[5] “The Fuzzing Book.” Accessed November 5, 2022.

審核編輯 黃昊宇