發(fā)布時(shí)間：2020-11-13 18:19

　　 在軟件開發(fā)過程中,軟件缺陷始終威脅著軟件的安全性以及可靠性,并且隨著軟件規(guī)模越發(fā)龐大、程序設(shè)計(jì)越發(fā)復(fù)雜,這一問題也將變得越發(fā)嚴(yán)重。而正因?yàn)槿绱?“測(cè)試”作為業(yè)界中的主要有效應(yīng)對(duì)手段,也就顯得尤為重要。其中,相比較于通過人工方式生成測(cè)試輸入,“程序測(cè)試輸入自動(dòng)生成”在成本方面有著無可比擬的優(yōu)越性,并且已經(jīng)被業(yè)界廣泛投入使用。目前,具備程序測(cè)試輸入自動(dòng)生成能力的測(cè)試技術(shù)種類繁多,包括隨機(jī)測(cè)試、蛻變測(cè)試等等。而在所有相關(guān)測(cè)試技術(shù)之中,又以“模糊測(cè)試(Fuzzing Testing)”以及“動(dòng)態(tài)符號(hào)執(zhí)行(Dynamic Symbolic Execution)”最為典型、高效,同時(shí)彼此之間風(fēng)格迥異。但是,如何生成高質(zhì)量的測(cè)試輸入子集以及如何快速獲取目標(biāo)測(cè)試輸入,從而最終高效達(dá)成程序測(cè)試目標(biāo),一直都是阻礙程序測(cè)試輸入自動(dòng)生成進(jìn)一步發(fā)展的主要難題。截至目前為止,在程序測(cè)試輸入自動(dòng)生成研究領(lǐng)域中,已經(jīng)涌現(xiàn)出了大量的相關(guān)技術(shù)綜述以及技術(shù)改進(jìn),所有這些相關(guān)工作都極大的促進(jìn)了程序測(cè)試輸入自動(dòng)生成的發(fā)展。然而可惜的是,直到今天,程序測(cè)試輸入自動(dòng)生成依然存在大量問題亟待解決。我們渴望能夠在本質(zhì)上有所突破,從而徹底解決相關(guān)問題。但是與此同時(shí),我們也逐漸意識(shí)到:如果想要達(dá)成這一目標(biāo),當(dāng)下這種在傳統(tǒng)理論框架下單純進(jìn)行技術(shù)改進(jìn),已經(jīng)是遠(yuǎn)遠(yuǎn)不夠了。所以,我們需要一個(gè)全新的、統(tǒng)一的視角,幫助我們理解現(xiàn)有相關(guān)工作的特點(diǎn)、優(yōu)勢(shì)、劣勢(shì),并且以此作為基礎(chǔ),便于我們提出新的程序測(cè)試輸入自動(dòng)生成技術(shù)。為此,我們開展了如下的主要研究工作:1.我們嘗試從搜索空間的角度來理解程序測(cè)試輸入自動(dòng)生成,并且以此作為基礎(chǔ),提出了一個(gè)基于“鄰居關(guān)系定義(Neighborhood Definition)”N、“鄰居選擇策略(Selection Strategy)”以及“初始測(cè)試輸入集合(Bootstrap Test Inputs)”H0的統(tǒng)一技術(shù)框架,記為N,S,H0。這樣一個(gè)統(tǒng)一技術(shù)框架可以包羅目前所有已知的相關(guān)技術(shù)(包括模糊測(cè)試、動(dòng)態(tài)符號(hào)執(zhí)行以及兩者技術(shù)融合),同時(shí)也為我們提供了一個(gè)全新的、統(tǒng)一的視角,可以重新省視目前所有相關(guān)工作的特點(diǎn)、優(yōu)勢(shì)、劣勢(shì)。2.基于這樣一個(gè)統(tǒng)一技術(shù)框架N,S,H0,我們從定性分析的角度出發(fā),通過開展一份迷你技術(shù)調(diào)研(調(diào)研了模糊測(cè)試、動(dòng)態(tài)符號(hào)執(zhí)行以及兩者技術(shù)融合的29份具有代表性的相關(guān)工作),梳理了相關(guān)工作的歷史發(fā)展脈絡(luò),與此同時(shí),基于N,S,H0,我們以一個(gè)全新的、統(tǒng)一的視角,分析、總結(jié)了所有這些相關(guān)工作的特點(diǎn)、優(yōu)勢(shì)、劣勢(shì),并且從中挖掘了具有潛力的未來研究方向。3.基于這樣一個(gè)統(tǒng)一技術(shù)框架N,S,H0,我們從定量分析的角度出發(fā),開展了一份實(shí)證研究。在實(shí)證研究中,我們使用GNU CoreUtils作為被測(cè)程序,使用AFLfast作為模糊測(cè)試工具的代表,使用KLEE作為動(dòng)態(tài)符號(hào)執(zhí)行工具的代表。分析了模糊測(cè)試以及動(dòng)態(tài)符號(hào)執(zhí)行在現(xiàn)實(shí)程序上的代碼覆蓋表現(xiàn)。同時(shí),基于所統(tǒng)計(jì)到的全部142處代碼覆蓋失敗案例,我們總結(jié)了“模糊測(cè)試/動(dòng)態(tài)符號(hào)執(zhí)行”的代碼覆蓋失敗原因,并且發(fā)現(xiàn):“模擬不充分”占比26%/49%,“算法局限性”占比64%/40%。借此,我們考察了這兩項(xiàng)技術(shù)間的局限性以及互補(bǔ)性,驗(yàn)證了迷你技術(shù)調(diào)研中的相關(guān)定性結(jié)論。4.基于定性分析以及定量分析,我們針對(duì)實(shí)證研究過程中所發(fā)現(xiàn)的AFL中搜索策略的饑餓問題,提出了動(dòng)態(tài)削減低效變異操作的策略,以及基于代碼覆蓋差異的局部深度優(yōu)先搜索算法。隨后,我們?cè)贏FL的基礎(chǔ)上進(jìn)行了相關(guān)改進(jìn),實(shí)現(xiàn)了全新的AFLSU。通過實(shí)驗(yàn),我們發(fā)現(xiàn):AFLSU有效的緩解了饑餓問題,并且在代碼覆蓋行數(shù)方面,相比較于AFL以及AFLfast,AFLSU分別最高提高了40.35%以及36.66%,平均提高了 17.27%以及12.86%。
【學(xué)位單位】：南京大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2019
【中圖分類】：TP311.53
【部分圖文】：

?第一章緒論??要不充分條件。為了方便闡述其中原理，我們還是先看一個(gè)如圖１－２所示的代??碼案例。??１?ｖｏｉｄ?ｆｕｎｃ（ｃｈａｒ＊?ｓ）?｛??２?ｉｎｔ?ｃｎｔ?＝?０；??３?ｆｏｒ?（ｉｎｔ?ｉ?＝?０；?ｉ?＜?１００；?ｉ＋＋）?｛??４?ｉｆ?（ｓ［ｉ］?＝＝?＇ｘ＇）?｛??５?ｃｎｔ＋＋；??６?｝??７?｝??８?ａｓｓｅｒｔ（ｃｎｔ?�。�?２５）；??９?ｉｆ?（ｃｎｔ?＝＝７５）?｛??ｉ〇?ｂｕｇ?（）；??１１?｝??１２?｝???圖１－２：闡述語句全覆蓋以及路徑全覆蓋的程序示例。??與圖１－１中的代碼案例一樣，在當(dāng)前這個(gè)例子中，函數(shù)／？ｎｃ的輸入是一個(gè)??長(zhǎng)度為１００的字符串，大小為１００個(gè)字節(jié)。在這其中：??？如果我們想要觸發(fā)位于第８行的程序中斷，需要滿足：在作為輸入的１００??個(gè)字節(jié)當(dāng)中，有且正好只有２５個(gè)單字符’ｘ’。此處，我們將這樣一個(gè)測(cè)試??輸入約束記為??魯如果我們想要觸發(fā)位于第１０行的錯(cuò)誤函數(shù)，需要滿足：在作為輸入的１００??個(gè)字節(jié)當(dāng)中，有且正好只有７５個(gè)單字符’Ｘ’。此處，我們將這樣一個(gè)測(cè)試??輸入約束記為辦。??這里可以發(fā)現(xiàn)：（：洲辦是相互矛盾的。??現(xiàn)在我們己經(jīng)知道全覆蓋從強(qiáng)到弱可以分為：“路徑全覆蓋（Ｆｕｌｌ?Ｐａｔｈ??Ｃｏｖｅｒａｇｅ）?”、“分支全覆蓋（Ｆｕｌｌ?Ｂｒａｎｃｈ?Ｅｄｇｅ?Ｃｏｖｅｒａｇｅ）?”、“語句全覆蓋??（Ｆｕｌｌ?Ｓｔａｔｅｍｅｎｔ?Ｃｏｖｅｒａｇｅ）?”。在圖１－２所示的代碼案例中，我們可以發(fā)現(xiàn)：??參當(dāng)我們達(dá)成語句全覆蓋的時(shí)候

Ｐｏｉｎｔ）?”的兩次執(zhí)行，針對(duì)所有后續(xù)將會(huì)被讀取的變量，如果這些變量當(dāng)前取??值己經(jīng)相同，那么兩者后續(xù)路徑必然相同，后續(xù)符號(hào)分析純屬冗余，可以進(jìn)行??剪枝（狀態(tài)剪枝原理如圖３－１所示）。除了?ＲＷｓｅｔ之外，在ＧＵＩＤＥＳＥ中，用??戶向被測(cè)程序中插入特殊注釋，而ＧＵＩＤＥＳＥ則據(jù)此遵循用戶意志，有目標(biāo)的??進(jìn)行狀態(tài)合并、路徑剪枝。ＭＵＬＴＩＳＥ通過利用狀態(tài)合并，引導(dǎo)探索方向前往目??標(biāo)執(zhí)行路徑。??不管如何，狀態(tài)合并的核心思想是：針對(duì)抵達(dá)同一程序執(zhí)行點(diǎn)的兩次執(zhí)??行，如果兩者變量狀態(tài)高度相似，那么兩者可以進(jìn)行合并（如果被判定為等??價(jià)），從而剔除冗余、指導(dǎo)搜索（狀態(tài)合并原理如圖３－２所示）。??

＇＇＇??？參。??圖３－１：在搜索空間中，狀態(tài)剪枝原理示意。??圖中所有節(jié)點(diǎn)代表測(cè)試輸入，在這其中，黑色節(jié)點(diǎn)代表的是目標(biāo)測(cè)試輸入，帶義號(hào)的節(jié)點(diǎn)??代表的是那些冗余或者尤價(jià)值的測(cè)試輸入。狀態(tài)剪枝通過提前剔除這些冗余或者無價(jià)值的??測(cè)試輸入，從而提高鄰居選擇策略效果。??最后，讓我們先回到動(dòng)態(tài)符號(hào)執(zhí)行所面臨的挑戰(zhàn)。我們現(xiàn)在己經(jīng)知道，由??于路徑約束內(nèi)部存在依賴關(guān)系，后綴約束總是在控制流程上依賴前綴約束。隨??意取反某個(gè)分支約束，極有可能導(dǎo)致被取反分支約束同前綴約束之間產(chǎn)生矛??盾。最終導(dǎo)致，很多時(shí)候，我們很難沿著當(dāng)前執(zhí)行路徑，通過直接取反目標(biāo)分??支約束，進(jìn)入目標(biāo)分支。另外一邊，由于計(jì)算資源有限，但是現(xiàn)實(shí)程序中的執(zhí)??行路徑總量幾乎無限
【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 山磊;;程序測(cè)試的心理研究[J];甘肅科技縱橫;2006年06期

2 李淑寧;數(shù)據(jù)流分析在程序測(cè)試中的應(yīng)用[J];小型微型計(jì)算機(jī)系統(tǒng);1988年04期

3 黃琳;;符號(hào)蹤跡測(cè)試工具——STTT[J];計(jì)算機(jī)研究與發(fā)展;1989年03期

4 李友仁;劉少英;;COBOL程序測(cè)試環(huán)境CPTS-1的設(shè)計(jì)與實(shí)現(xiàn)[J];西安交通大學(xué)學(xué)報(bào);1989年01期

5 劉劍;;重視程序測(cè)試 提高軟件質(zhì)量[J];金融電子化;1999年03期

6 陳鋼;王能斌;;程序測(cè)試與一個(gè)程序測(cè)試工具[J];南京工學(xué)院學(xué)報(bào);1983年02期

7 劉遠(yuǎn)信;程序測(cè)試[J];南昌大學(xué)學(xué)報(bào)(理科版);1996年04期

8 趙千川;王達(dá);薛文軒;;PLC程序測(cè)試與驗(yàn)證的研究進(jìn)展[J];清華大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年11期

9 黃采倫;RS-485 通訊接口及程序測(cè)試方法[J];電子儀器儀表用戶;1998年02期

10 郭聲;淺談AXE—10的程序測(cè)試系統(tǒng)[J];江蘇通信技術(shù);1994年01期

相關(guān)碩士學(xué)位論文 前10條

1 曹陽;程序測(cè)試輸入的自動(dòng)生成技術(shù)框架及其優(yōu)化實(shí)現(xiàn)[D];南京大學(xué);2019年

2 王雅楠;基于微信的智慧校園應(yīng)用[D];西安電子科技大學(xué);2018年

3 胡琰琳;程序正義中的“聲音”[D];浙江工商大學(xué);2018年

4 徐文飛;選礦過程自動(dòng)化邏輯控制程序測(cè)試平臺(tái)的設(shè)計(jì)與開發(fā)[D];東北大學(xué);2015年

5 張超群;選礦過程電氣設(shè)備邏輯控制程序測(cè)試平臺(tái)的設(shè)計(jì)與開發(fā)[D];東北大學(xué);2014年

6 楊曉光;泵和閥門類設(shè)備邏輯控制程序測(cè)試平臺(tái)的研發(fā)[D];東北大學(xué);2011年

7 王文軍;Java ME程序測(cè)試平臺(tái)的若干關(guān)鍵技術(shù)研究[D];大連海事大學(xué);2008年

8 李杜;字符識(shí)別技術(shù)研究及其在機(jī)器視覺測(cè)控中的應(yīng)用[D];江南大學(xué);2011年

9 張新杰;程序切片技術(shù)研究及切片方案設(shè)計(jì)[D];電子科技大學(xué);2017年

10 王大偉;回歸測(cè)試中基于需求優(yōu)先級(jí)的用例選擇算法研究[D];浙江工業(yè)大學(xué);2012年

本文編號(hào)：2882479