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

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

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

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

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

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

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

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

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

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

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

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

03隨機(jī)測(cè)試的優(yōu)缺點(diǎn)

3.1 優(yōu)點(diǎn)

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

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

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

3.2 缺點(diǎn)

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

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

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

在1988年的一個(gè)風(fēng)雨交加的夜晚，威斯康星大學(xué)的Barton Miller教授在自己的公寓中通過(guò)一條電話線連接他在學(xué)校中的計(jì)算機(jī)。暴風(fēng)雨引發(fā)了電話線中的信號(hào)錯(cuò)亂，以至于所連接的Unix終端不斷接收到糟糕的命令輸入，最終導(dǎo)致了系統(tǒng)崩潰。頻發(fā)的崩潰使這位講授操作系統(tǒng)課程的教授感到驚訝，因此他腦海中浮現(xiàn)了一個(gè)對(duì)Unix系統(tǒng)進(jìn)行魯棒性測(cè)試的念頭。于是他在給學(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é)生開(kāi)發(fā)一個(gè)模糊生成器（fuzz generator），這個(gè)生成器可以產(chǎn)生不可預(yù)測(cè)的輸入流，然后將這些雜亂的輸入給到Unix系統(tǒng)設(shè)施，然后試圖攻陷這些設(shè)施并找到和分析引發(fā)錯(cuò)誤的隨機(jī)輸入和原因。這就是模糊測(cè)試的誕生，教授在作業(yè)中使用的fuzz一詞也就被用來(lái)命名這一技術(shù)。

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

圖 1

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

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

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

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

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

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

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

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

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

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

圖 2

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

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

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

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

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

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

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

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

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

圖 3

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

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

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

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

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

圖 4

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

圖 5

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

05總結(jié)

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

審核編輯 黃昊宇