作者簡(jiǎn)介

高祥，北京航空航天大學(xué)軟件學(xué)院副教授。研究領(lǐng)域：程序分析、軟件自動(dòng)修復(fù)、軟件安全。 ? ?

高效快速地修復(fù)軟件漏洞是增強(qiáng)軟件安全性的關(guān)鍵。然而，據(jù)統(tǒng)計(jì)，一個(gè)漏洞從發(fā)現(xiàn)到修復(fù)平均需要 60 天，這會(huì)讓軟件系統(tǒng)長(zhǎng)期暴露在風(fēng)險(xiǎn)中。自動(dòng)程序修復(fù)是輔助開(kāi)發(fā)人員修復(fù)程序缺陷的技術(shù)。現(xiàn)有的修復(fù)方法通常以通過(guò)給定的測(cè)試用例作為修復(fù)目標(biāo)。但是，測(cè)試用例驅(qū)動(dòng)的修復(fù)技術(shù)易于產(chǎn)生“過(guò)擬合”的補(bǔ)丁，即修復(fù)后的程序在給定的測(cè)試用例上表現(xiàn)正確，但是在測(cè)試用例之外的輸入上仍然有錯(cuò)誤。我將介紹如何使用程序分析技術(shù)緩解漏洞修復(fù)的過(guò)擬合問(wèn)題。主要采用測(cè)試用例生成和形式化方法來(lái)增強(qiáng)程序規(guī)約，進(jìn)而提升自動(dòng)化生成補(bǔ)丁的質(zhì)量。

以下為正文。

我們每個(gè)月都會(huì)發(fā)現(xiàn)很多的安全漏洞，然而安全漏洞的修復(fù)速度卻非常慢。據(jù)統(tǒng)計(jì)，一個(gè)安全漏洞從被發(fā)現(xiàn)到被修復(fù)，大概要花費(fèi) 70 天的時(shí)間，即便是針對(duì)一些特別嚴(yán)重的安全漏洞，也需要花費(fèi)大概 50 天的時(shí)間來(lái)修復(fù)。

這種緩慢的修復(fù)速度會(huì)讓軟件長(zhǎng)期暴露在安全的隱患中，我們的工作就是希望能夠自動(dòng)化地生成程序漏洞的補(bǔ)丁，從而幫助開(kāi)發(fā)人員盡快修復(fù)程序中缺陷。

對(duì)于人工修復(fù)來(lái)說(shuō)，程序的修復(fù)往往需要定位異常、分析、修復(fù)這樣的過(guò)程。

人工程序修復(fù)

對(duì)于自動(dòng)修復(fù)來(lái)說(shuō)，我們希望把這個(gè)過(guò)程自動(dòng)化。即給定一個(gè)程序的正確性規(guī)約 Specification，以及一個(gè)帶缺陷的程序，通過(guò)程序的自動(dòng)修復(fù)系統(tǒng)來(lái)生成正確的程序。

自動(dòng)化程序修復(fù)

# 程序修復(fù)方法

## 基于搜索的方法

現(xiàn)有的最簡(jiǎn)單的程序修復(fù)方式之一是基于搜索的方法。

Search-based approach

首先定義程序的轉(zhuǎn)換規(guī)則，給定一個(gè)有錯(cuò)誤的程序。利用給定的轉(zhuǎn)換規(guī)則，生成候選補(bǔ)丁的搜索空間。給定一組程序的正確性規(guī)約（假設(shè)是以 Test case 的形式給定）。程序修復(fù)的目標(biāo)是使得修復(fù)后的程序能夠通過(guò)所有的 Test case。

修復(fù)的過(guò)程是在搜索空間中通過(guò)某種搜索算法找到一個(gè)補(bǔ)丁，能夠通過(guò)所有的 Test case。

## 過(guò)擬合問(wèn)題

基于搜索的方法最大的局限在于過(guò)擬合 Overfitting 問(wèn)題。

Overfitting

給定一組 Test case，這組 Test case 表示的程序的正確性規(guī)約可能是不完善的，修復(fù)后的程序可能在給定的 Test case 上表現(xiàn)是正確的，但它沒(méi)有辦法泛化到其他的 Test case 上。

下面是一個(gè)簡(jiǎn)單的例子，給定一個(gè)錯(cuò)誤的測(cè)試用例，當(dāng)輸入是 1 的時(shí)候，期待的返回值是 1，但是在這個(gè)程序里面返回值是 0。那么如何用自動(dòng)化的方式來(lái)生成一個(gè)正確的補(bǔ)丁？首先按照給定的轉(zhuǎn)換規(guī)則，對(duì)潛在的有錯(cuò)誤的語(yǔ)句做轉(zhuǎn)換，比如 x - 1 > 0 → x - 2 > 0，x - 1 > 0 → x - 1 >= 0 等。

Overfitting

通過(guò)這種方式生成的程序，可能可以通過(guò)給定的 Test case，但它不一定能夠泛化到其他的 Test case 上。

# 如何緩解程序過(guò)擬合問(wèn)題 #

下面介紹如何緩解在修復(fù)安全漏洞時(shí)的過(guò)擬合問(wèn)題。主要是通過(guò)增強(qiáng)程序的正確性規(guī)約，并進(jìn)一步通過(guò)程序分析方法來(lái)推斷開(kāi)發(fā)人員或用戶的意圖。我們用到的方法包括測(cè)試用例生成、基于邏輯推理的方法等。

研究如何緩解程序過(guò)擬合問(wèn)題

今天我會(huì)介紹三個(gè)近期的工作。

# 生成測(cè)試用例

第一個(gè)工作是通過(guò)生成更多的測(cè)試樣例來(lái)緩解程序的過(guò)擬合問(wèn)題。

既然過(guò)擬合的補(bǔ)丁無(wú)法泛化到其他的測(cè)試用例 test case 上，那么我們是否可以通過(guò)自動(dòng)算法來(lái)生成更多的測(cè)試用例，再使用修復(fù)系統(tǒng)生成修復(fù)后的程序呢？

已有的用例生成工具主要以提升程序覆蓋率為目的，這類工具并不了解補(bǔ)丁的語(yǔ)義。因此目前的用例生成技術(shù)，在我們的場(chǎng)景下其表現(xiàn)效果不是特別好。

Test Generation to Alleviate Overfitting

下圖中，假設(shè)最大的圈表示所有的補(bǔ)丁空間 search space，在補(bǔ)丁空間中有一些 plausible patches，這些 patches 能夠通過(guò)給定的測(cè)試用例，但它們不一定是正確的。在 plausible patches 里，可能只有一小部分是 correct patches。

Distinguish crashing and crash-free patches (practical)

我們的主要想法是通過(guò)測(cè)試用例生成，來(lái)區(qū)分出 plausible patches 里正確的和不正確的補(bǔ)丁。

在介紹具體的技術(shù)之前，我們先補(bǔ)充一下灰盒測(cè)試的背景。灰盒模糊測(cè)試 Grey-Box Fuzzing 以一組種子 seed (即測(cè)試用例) 作為輸入，測(cè)試引擎會(huì)基于給定的種子不斷修改來(lái)生成新的測(cè)試用例，并在程序上運(yùn)行這些新的測(cè)試用例，同時(shí)判斷新的測(cè)試用例是不是 isInteresting 的。在傳統(tǒng)的場(chǎng)景下，灰盒測(cè)試會(huì)判斷新測(cè)試用例是否提升了代碼的覆蓋率，如果有提升，就將其加入到 Input Queue 里，進(jìn)行進(jìn)一步的變異。但這種判斷方法對(duì)于補(bǔ)丁的語(yǔ)義是沒(méi)有任何理解的。

Grey-Box Fuzzing

為了解決這個(gè)問(wèn)題，我們希望在用例判斷的過(guò)程中加入補(bǔ)丁的語(yǔ)義信息。例如，生成新測(cè)試用例時(shí)，先判斷測(cè)試用例有沒(méi)有發(fā)現(xiàn)候選補(bǔ)丁行為的差異，如果新測(cè)試用例發(fā)現(xiàn)了補(bǔ)丁之間行為的差異，則把該用例加到 Input Queue 里進(jìn)行變異。這樣做的最終目標(biāo)是通過(guò)不斷發(fā)現(xiàn)補(bǔ)丁之間行為的差異，從而區(qū)分出哪些補(bǔ)丁是正確的，哪些補(bǔ)丁是錯(cuò)誤的。

Crash-avoiding Program Repair

## 舉個(gè)例子

下面介紹一個(gè)緩存溢出和數(shù)據(jù)泄露的例子。

如下代碼示例中，給定一個(gè)測(cè)試用例 s="foo", t="", n=4，運(yùn)行會(huì)觸發(fā)緩沖區(qū)溢出錯(cuò)誤。

?

?

//?copy?the?first?n?characters?of?s?to?t
char*?strncpy(char*?s,?char*?t,?int?n)?{
????for?(int?i=0;?i

	?

	?

	我們假設(shè)通過(guò)轉(zhuǎn)換規(guī)則生成了一系列候選補(bǔ)丁。

	?

				ID
			

				Patch
		

				p1
			

				i < n - 1
		

				p2
			

				i < 3
		

				p3
			

				i < n && i < strlen(s)
		

				p4
			

				i > n
		

				......
			

				......
		

	?

	我們將補(bǔ)丁空間劃分為 Plausible partition 和 Incorrect patch (Plausible partition 即能夠通過(guò)給定測(cè)試用例的補(bǔ)丁，Incorrect patch 指仍然會(huì)觸發(fā)異常的補(bǔ)丁)。其中，Plausible partition 又可以劃分為 Crashing partition 和 Crash-free patch (Crashing partition 指雖然能夠通過(guò)給定的測(cè)試用例，但在一些其他的測(cè)試用例上仍然會(huì)觸發(fā)異常的補(bǔ)丁；Crash-free patch 是指正確的補(bǔ)丁)。

	

	為了對(duì) Plausible partition 進(jìn)行進(jìn)一步的劃分，可以通過(guò)測(cè)試用例生成的方法，對(duì)原有的測(cè)試用例進(jìn)行修改和變異。

	?

				ID
			

				Patch
		

				p1
			

				i < n - 1
		

				p2
			

				i < 3
		

				p3
			

				i < n && i < strlen(s)
		

	?

	若新生成的測(cè)試用例能夠發(fā)現(xiàn)補(bǔ)丁之間行為的差異，那么就認(rèn)為基于此測(cè)試用例的進(jìn)一步變異，有更高的概率繼續(xù)發(fā)現(xiàn)補(bǔ)丁之間行為的差異。通過(guò)不斷生成測(cè)試用例，不斷劃分補(bǔ)丁分區(qū)，最終找到正確的補(bǔ)丁。

	

	## 實(shí)現(xiàn)方法

	下面介紹具體的實(shí)現(xiàn)方法。

	

	我們定義了 ，用以表示一個(gè)新生成的測(cè)試用例是否能夠發(fā)現(xiàn)補(bǔ)丁之間行為的差異：

	

	

	Separability 有兩個(gè)作用，一是判斷一個(gè)新生成的測(cè)試用例是否是 isInteresting 的 (即 non-zero separability)，若是，那么就進(jìn)行進(jìn)一步的變異。

	

	第二是使用 Separability 來(lái)定義種子的能量值 Energy。能量值 Energy 指對(duì)一個(gè)種子進(jìn)行變異的次數(shù)。假設(shè)我們通過(guò)變異某個(gè)種子生成了 4 個(gè)新的測(cè)試用例，則其能量值為 4。擁有更高 separability 的種子會(huì)被分配更高的能量值。

	

	不同時(shí)間和不同 separability 下能量值不同。

	

	## 工具與實(shí)驗(yàn)：Fix2Fit

	基于上述方法，我們實(shí)現(xiàn)了一個(gè)開(kāi)源工具 Fix2Fit，并與 AFL、AFLGo 進(jìn)行了對(duì)比。可以看到，F(xiàn)ix2Fit 相比 AFL 和 AFLGo 過(guò)濾掉了更多錯(cuò)誤的補(bǔ)丁。

	

	Percentage of plausible patches that are ruled out

	更多 Fix2Fit 信息：

	Github 地址：https://github.com/gaoxiang9430/Fix2Fit

	相關(guān)論文：Crash-avoiding Program Repair Xiang Gao, Sergey Mechtaev, Abhik Roychoudhury. ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) 2019.

	## 思考：如何進(jìn)一步排除補(bǔ)丁

	上述方法可以過(guò)濾掉 Crashing Patch，但實(shí)際上還有一些沒(méi)有引發(fā)安全隱患 (crash-free patch) 但依然是錯(cuò)誤的補(bǔ)丁。怎樣去區(qū)分這部分補(bǔ)丁 (下圖中紅色部分) 和正確補(bǔ)丁呢？這需要開(kāi)發(fā)者參與進(jìn)來(lái)。

	

	我們假設(shè)通過(guò)一個(gè)測(cè)試用例，發(fā)現(xiàn)了兩個(gè)補(bǔ)丁的差異行為，那么在程序確定的前提下，其中只有一個(gè)補(bǔ)丁會(huì)是正確的，那么此時(shí)我們就需要人的反饋來(lái)過(guò)濾掉不正確的補(bǔ)丁。需要強(qiáng)調(diào)的是，我們的研究工作不是為了取代人，而是為了幫助開(kāi)發(fā)者生成一些推薦，使開(kāi)發(fā)者能夠更高效地修復(fù)問(wèn)題。

	如下所示，我們的實(shí)驗(yàn)中，如果有 5-10 次的人的參與反饋，那么我們可以從眾多的 plausible patches 中篩選到 10 個(gè)左右。

	

	Number of plausible patches that can be ruled out if a few tests are empowered with more human oracles

	# 程序狀態(tài)變異

	我們發(fā)現(xiàn)，如果從程序的入口處 entry point 開(kāi)始對(duì)程序輸入進(jìn)行變異，會(huì)浪費(fèi)掉大量的資源，要到達(dá) patch location 是一件非常困難的事情。為了解決這個(gè)問(wèn)題，我們提出，是否可以在補(bǔ)丁的位置直接進(jìn)行變異呢？我們叫這種在 patch location 進(jìn)行變異的方法為 State-level (Snapshot) Fuzzing，即對(duì)程序的狀態(tài)進(jìn)行變異。

	

	Snapshot Fuzzing for repair

	具體的方法是：

	第一步，生成一些程序入口處的 Test Input ，針對(duì)每一個(gè)程序輸入，收集它在 patch location 的程序狀態(tài) ；

	第二步，根據(jù)程序狀態(tài) 推斷程序補(bǔ)丁 ；

	第三步，通過(guò) Snapshot Fuzzing，對(duì)程序狀態(tài)進(jìn)行修改，生成一個(gè)新的狀態(tài) ，去測(cè)試推斷的補(bǔ)丁是否正確，同時(shí)也把新的狀態(tài)加入到狀態(tài)集合中 ；

	返回第二步或者直接結(jié)束。

	Snapshot Fuzzing 和傳統(tǒng) Test Generation 最大的區(qū)別在于，Snapshot Fuzzing 不是從程序的入口處對(duì)程序的輸入狀態(tài)進(jìn)行變異，而是在 patch location 直接變異。這是一個(gè)不斷循環(huán)的過(guò)程，最終的目標(biāo)就是不斷生成新的程序狀態(tài)，同時(shí)不斷優(yōu)化程序的補(bǔ)丁。

	## 實(shí)現(xiàn)方法

	Patch Inference

	那么，如何根據(jù)生成的程序狀態(tài)推斷一個(gè)補(bǔ)丁呢？這里用到了程序合成技術(shù)。

	在程序狀態(tài) S 中，存在正樣本和負(fù)樣本。正樣本是指不能觸發(fā)安全事件的程序狀態(tài)，負(fù)樣本是指能夠觸發(fā)安全事件的程序狀態(tài)。最終的目標(biāo)是推斷出一個(gè)程序補(bǔ)丁，使其在正樣本上原有的程序執(zhí)行保持不變，在負(fù)樣本上，需要對(duì)程序的狀態(tài)進(jìn)行修改，從而把漏洞狀態(tài)給關(guān)閉掉。

	

	Patch Generation

	生成程序補(bǔ)丁有兩種方式。一種是加入到原有的 if/for/while 中，另一種是插入一個(gè) if-guard 關(guān)閉錯(cuò)誤的程序狀態(tài)。

	

	## 思考：Infeasible States

	這里存在一個(gè)問(wèn)題，雖然我們用直接修改的方式在程序中間生成了一個(gè)程序狀態(tài)，但是這個(gè)程序狀態(tài)在真實(shí)的場(chǎng)景中不一定存在，即不一定是合法的。

	針對(duì)這個(gè)問(wèn)題我們也做了分析。如下圖所示，通過(guò) Snapshot Fuzzing 生成的程序狀態(tài)，可能是 infeasible state，但即使生成了 infeasible state，對(duì)于 disable vulnerable state 是沒(méi)有什么影響的。這主要因?yàn)椋摼€表示的橢圓有可能也 disable 了一些 infeasible state，但它對(duì)于最終的目標(biāo)是沒(méi)有任何影響的。

	

	Snapshot mutation can generate infeasible states

	## 工具與實(shí)驗(yàn)：VulnFix

	在本個(gè)實(shí)驗(yàn)中，我們使用了 AsiaCCS'21 的數(shù)據(jù)集，其中包含 39 個(gè)真實(shí)世界的安全漏洞。我們?cè)O(shè)置了 30 分鐘的超時(shí)機(jī)制。實(shí)驗(yàn)結(jié)果表明，VulnFix 可以成功修復(fù)其中的 19 個(gè) 漏洞，在已有的工具基礎(chǔ)上有了明顯的提升。

	

	VulnFix generated more correct patches than CPR and SenX.

	# 語(yǔ)義分析與推理

	前面介紹的兩個(gè)工作，主要是基于 Fuzzing 的方式來(lái)緩解過(guò)擬合問(wèn)題。雖然能夠在一定程度上緩解，但仍然沒(méi)有辦法保證生成的補(bǔ)丁能夠修復(fù)所有錯(cuò)誤的 Test case。

	為了解決這個(gè)問(wèn)題，我們提出了一種 基于語(yǔ)義分析與推理方式修復(fù) 的方案。當(dāng)一個(gè)安全漏洞被發(fā)現(xiàn)時(shí)，通常會(huì)有一個(gè)能夠觸發(fā)安全漏洞的 Exploit (Failing Test)，如果僅以修復(fù) Exploit 作為目標(biāo)，很容易產(chǎn)生過(guò)擬合問(wèn)題。

	除了 Exploit 之外，可能還存在很多其他能觸發(fā)缺陷的程序輸入。那么，能否通過(guò)一種抽象的方式，將具體的 Exploit 抽象成一種針對(duì)所有 Failing Input 的表示？在這個(gè)場(chǎng)景下，我們使用抽象的條件約束 constraints 來(lái)表示一個(gè)缺陷，這樣修復(fù)的目標(biāo)就不再是使其通過(guò)測(cè)試用例，而是使其滿足給定的條件約束。

	

	

	## 實(shí)現(xiàn)方法

	生成條件約束

	我們定義了一些模板，用以生成條件約束。比如，

	buffer overflow：access(buffer) < base(buffer) + size(buffer)

	Integer overflow/underflow (a op b)：MIN ≤ a op b ≤ MAX (over Z)

	下面是一個(gè)的 buffer overflow 的例子。假設(shè) rows 聲明的長(zhǎng)度是 256，訪問(wèn)時(shí)的 nrows 也是 256。根據(jù)約束 access(buffer) < base(buffer) + size(buffer) 可知，nrows 必須小于 rows，此時(shí) buffer overflow 就會(huì)被觸發(fā)。

	

	怎樣提取出程序狀態(tài)？

	通過(guò)插樁和運(yùn)行時(shí)抽象的方法來(lái)提取抽象的條件約束。

	在分配內(nèi)存的時(shí)候會(huì)同時(shí)記錄元數(shù)據(jù)，包括 buffer 的大小、長(zhǎng)度等，在運(yùn)行時(shí)參照元數(shù)據(jù)生成抽象的條件約束。

	

	Concrete State Abstraction

	約束傳遞

	條件約束是在 bug location 生成的，稱之為 CFC。如果滿足 CFC，缺陷就會(huì)被修復(fù)。但問(wèn)題在于，條件約束的生成是在 bug location，而修復(fù)的過(guò)程是在 fix location，這時(shí)候就需要向后的 CFC 的傳遞。

	

	Constraints Propagation

	計(jì)算一個(gè)在 fix location 針對(duì)于 CFC 的最弱前提條件 CFC'，如果 CFC' 在 fix location 滿足，那么 CFC 在 bug location 也滿足。具體的計(jì)算過(guò)程我就不展開(kāi)講了，我們用了一個(gè)向前的符號(hào)執(zhí)行來(lái)計(jì)算最弱的前提條件。

	將固定位置的實(shí)時(shí)變量設(shè)置為符號(hào)變量

	在固定位置和崩潰位置之間進(jìn)行符號(hào)執(zhí)行

	

	用一個(gè)例子簡(jiǎn)單介紹一下，假設(shè) fix location 在程序的第 2 行，bug location 在程序的第 6 行，CFC 在第 6 行要滿足約束 y>5。這時(shí)候要從第 2 行進(jìn)行程序的符號(hào)執(zhí)行，發(fā)現(xiàn)兩條程序執(zhí)行路徑，我們可以計(jì)算出第 6 行 CFC -> (y>5) 在第 2 行的最弱前提條件 CFC' -> (x>4 ? i>0) ? (x>6 ? i≤0)。

	

	Patch Synthesis

	最后一步就是需要在 fix location 生成一個(gè)補(bǔ)丁。生成補(bǔ)丁之后，CFC' 一定是被滿足的。這里其實(shí)是一個(gè)程序合成的問(wèn)題，需要合成一個(gè)表達(dá)式，應(yīng)用了表達(dá)式之后，CFC' 一定是滿足的。具體的技術(shù)細(xì)節(jié)不展開(kāi)了。

	

	## 工具與實(shí)驗(yàn)：ExtractFix

	關(guān)于實(shí)驗(yàn)，我們實(shí)現(xiàn)了工具 ExtractFix。在 30 個(gè)現(xiàn)實(shí)的 CVE 中，我們的工具能夠生成 24 個(gè)補(bǔ)丁，其中有 16 個(gè)和開(kāi)發(fā)人員生成的補(bǔ)丁是一樣的。

	

	Experiments with Existing CVEs

	更多 ExtractFix 信息：

	網(wǎng)站：https://extractfix.github.io/

	論文：Beyond Tests: Program Vulnerability Repair via Crash Constraint Extraction. Xiang Gao, Bo Wang, Gregory J. Duck, Ruyi Ji, Yingfei Xiong, Abhik Roychoudhury. Transactions on Software Engineering and Methodology (TOSEM), 2020.

	# 總結(jié) #

	總結(jié)一下，今天主要介紹了三個(gè)緩解安全漏洞修復(fù)時(shí)過(guò)擬合問(wèn)題的方法。包括 Test case Generation、Snapshot Fuzzing、以及語(yǔ)義分析與推理。

	

	還是需要強(qiáng)調(diào)一下，由于程序 oracle (期待的程序行為) 的缺失，這些方法并沒(méi)有徹底地解決過(guò)擬合的問(wèn)題。因此我們只是提出了一些方法去緩解，最終的目標(biāo)也是幫助開(kāi)發(fā)人員更高效的修復(fù)程序缺陷。

	以上。

	# 相關(guān)論文 #

	Crash-avoiding Program Repair Xiang Gao, Sergey Mechtaev, Abhik Roychoudhury.?ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) 2019.

	Beyond Tests: Program Vulnerability Repair via Crash Constraint Extraction. Xiang Gao, Bo Wang, Gregory J. Duck, Ruyi Ji, Yingfei Xiong, Abhik Roychoudhury.?Transactions on Software Engineering and Methodology (TOSEM), 2020.

	編輯：黃飛