基于靜態(tài)分析的缺陷模式匹配研究

王建斌 劉 臻 胡昌振 單 純 鐘松延

1(中國(guó)航天科工集團(tuán)有限公司網(wǎng)絡(luò)信息總體部 北京 100048)

2(北京理工大學(xué)軟件學(xué)院軟件安全工程技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室 北京 100081)

(jb.wang2000@163.com)

如何保障軟件的可靠性和運(yùn)行的穩(wěn)定性,是軟件開(kāi)發(fā)一直以來(lái)難以避免的問(wèn)題.影響軟件可靠性和穩(wěn)定性的因素有許多,但主要的影響因素是軟件中存在的缺陷數(shù)量.通過(guò)檢測(cè)查找并及時(shí)修改軟件中存在的缺陷,可以在一定程度上對(duì)軟件的可靠性和穩(wěn)定性進(jìn)行控制.

現(xiàn)有的軟件缺陷檢測(cè)工具多采取靜態(tài)分析技術(shù),并通過(guò)軟件缺陷模式匹配的方法進(jìn)行缺陷檢測(cè).本文在研究軟件缺陷以及軟件缺陷靜態(tài)檢測(cè)技術(shù)的基礎(chǔ)上,提出了2種新的缺陷匹配方法;并通過(guò)實(shí)驗(yàn)驗(yàn)證了這2種方法在實(shí)際應(yīng)用過(guò)程中的可行性.

1 相關(guān)工作概述

1.1 靜態(tài)分析技術(shù)

現(xiàn)有的主流軟件缺陷檢測(cè)方式一般分為2種:動(dòng)態(tài)檢測(cè)和靜態(tài)檢測(cè).動(dòng)態(tài)檢測(cè)方法通常通過(guò)軟件運(yùn)行過(guò)程中軟件功能是否可以正常實(shí)現(xiàn),來(lái)判斷軟件是否存在缺陷或者漏洞.但測(cè)試用例往往很難將所有的邏輯流程窮盡,也就極有可能漏掉一些隱藏更深的缺陷.同時(shí),動(dòng)態(tài)檢測(cè)難以直觀地確定缺陷及其定位,這也為檢查和修改帶來(lái)了很大的困難.靜態(tài)檢測(cè)是指在不實(shí)際執(zhí)行程序的情況下,通過(guò)分析軟件源代碼或某種形式的目標(biāo)代碼,從而發(fā)現(xiàn)可能存在的缺陷以及漏洞的分析方法[1].由于靜態(tài)檢測(cè)不需要軟件運(yùn)行,因而靜態(tài)檢測(cè)更適合對(duì)軟件代碼中的編寫錯(cuò)誤或深層邏輯代碼進(jìn)行檢測(cè).

靜態(tài)分析是通過(guò)對(duì)代碼進(jìn)行自動(dòng)化掃描來(lái)發(fā)現(xiàn)可能的漏洞或缺陷.相對(duì)于動(dòng)態(tài)分析而言,其優(yōu)點(diǎn)在于[2-3]:由于有些靜態(tài)分析是直接對(duì)代碼進(jìn)行分析的,因此靜態(tài)分析工具可以對(duì)某一部分模塊進(jìn)行分析,也就無(wú)須等到整個(gè)項(xiàng)目完成才可以進(jìn)行檢測(cè),因而可以更早更有針對(duì)性地進(jìn)行檢測(cè);軟件執(zhí)行路徑的組合是非常復(fù)雜的,靜態(tài)檢測(cè)可以無(wú)視這種執(zhí)行路徑的復(fù)雜性,對(duì)難以執(zhí)行的路徑實(shí)施有效的檢測(cè);靜態(tài)分析的自動(dòng)化程度高,執(zhí)行速度快,相對(duì)效率更高,定位更準(zhǔn)確.

1.2 正則表達(dá)式及其意義

在計(jì)算機(jī)科學(xué)或形式語(yǔ)言理論中,正則表達(dá)式指的是一種用于定義搜索模式的序列.這種序列主要用于針對(duì)字符串進(jìn)行模式匹配或者字符串的匹配[4].在正則表達(dá)式中,每一個(gè)字符都可以被理解為一個(gè)具有特殊含義的“元字符”或者是一個(gè)僅僅代表其字面意義的標(biāo)準(zhǔn)字符.通過(guò)正則表達(dá)式中不同的字符組合,可以確定一種用于處理大量文字材料的模式.使用這種模式序列,可以直接自動(dòng)化地處理和分析普通文本文件或輸入的字符串中的特定文本形式.正則表達(dá)式處理器在處理正則表達(dá)式中,將正則表達(dá)式轉(zhuǎn)換為一個(gè)非確定的有限自動(dòng)機(jī),計(jì)算機(jī)會(huì)將這個(gè)有限自動(dòng)機(jī)作為匹配規(guī)則,來(lái)識(shí)別符合該有限自動(dòng)機(jī)表示的正則表達(dá)式代表的模式[5].

正則表達(dá)式在如今的軟件開(kāi)發(fā)中具有極大的意義,它可以為不同標(biāo)準(zhǔn)的系統(tǒng)提供一種特定的正規(guī)表達(dá)方式.使得不同的系統(tǒng)在文字處理方面可以有相同的標(biāo)準(zhǔn)為依據(jù)[6].

1.3 軟件缺陷

軟件缺陷其實(shí)是軟件開(kāi)發(fā)過(guò)程中導(dǎo)致錯(cuò)誤運(yùn)行結(jié)果或性能上不足的問(wèn)題代碼,且在軟件開(kāi)發(fā)過(guò)程中難以完全避免.通常情況下,軟件缺陷表現(xiàn)為人工編寫代碼的過(guò)程中產(chǎn)生的編譯錯(cuò)誤或者邏輯錯(cuò)誤.這些錯(cuò)誤通常比較隱蔽,在動(dòng)態(tài)檢測(cè)過(guò)程中并不容易檢測(cè)出來(lái),甚至可以一直潛伏,在某個(gè)特定的邏輯流程產(chǎn)生時(shí)才會(huì)出現(xiàn).這就為軟件的安全運(yùn)行留下的隱患,比較嚴(yán)重的缺陷甚至?xí)?duì)用戶造成極大的損失,包括經(jīng)濟(jì)資產(chǎn)的損失和非經(jīng)濟(jì)資產(chǎn)的損失[7-8].

1.4 軟件缺陷模式

軟件缺陷模式指由具有豐富的領(lǐng)域程序設(shè)計(jì)經(jīng)驗(yàn)的程序編碼人員、或具有豐富測(cè)試及缺陷修復(fù)經(jīng)驗(yàn)的測(cè)試人員總結(jié)出來(lái)的,可能經(jīng)常出現(xiàn)在程序中的特定規(guī)律,這些特定規(guī)律的出現(xiàn)往往意味著某種設(shè)計(jì)與實(shí)現(xiàn)錯(cuò)誤或是某種缺陷.一般說(shuō)來(lái),不同的編程語(yǔ)言會(huì)對(duì)應(yīng)不同的缺陷模式集.

缺陷模式的確定主要通過(guò)3個(gè)途徑[9]:軟件開(kāi)發(fā)和測(cè)試過(guò)程中積累的缺陷資源;各類文獻(xiàn)歸納的項(xiàng)目中實(shí)際積累的缺陷數(shù)據(jù);各領(lǐng)域內(nèi)的專家總結(jié)的缺陷數(shù)據(jù).

2 缺陷模式匹配方法

2.1 軟件缺陷檢測(cè)模型

利用靜態(tài)分析的方法構(gòu)建軟件缺陷檢測(cè)模型對(duì)軟件代碼中的缺陷進(jìn)行檢測(cè),一般需要3個(gè)步驟:首先獲取軟件各個(gè)文件中的代碼文本;其次對(duì)代碼文本進(jìn)行語(yǔ)法分析,構(gòu)建語(yǔ)法樹,根據(jù)預(yù)先規(guī)定的語(yǔ)法規(guī)則,對(duì)每一段有具體意義的代碼進(jìn)行切分;最后將得到的有具體意義的代碼片段與缺陷模式庫(kù)中已有的缺陷模式進(jìn)行匹配,逐一排查[10-11].

其中軟件缺陷檢測(cè)模型的主要技術(shù)點(diǎn)在于語(yǔ)法分析和缺陷模式匹配2個(gè)方面.一般而言,構(gòu)建語(yǔ)法樹的規(guī)則和方法大同小異,且并非是影響一個(gè)軟件缺陷檢測(cè)系統(tǒng)性能的核心.而缺陷模式和缺陷模式的匹配才是決定軟件缺陷測(cè)試系統(tǒng)性能的關(guān)鍵.

2.2 缺陷模式匹配存在的問(wèn)題

現(xiàn)有的靜態(tài)分析工具所使用的缺陷模式以及匹配方法還存在不足.在研究中發(fā)現(xiàn),現(xiàn)有的靜態(tài)分析工具還不能很好地對(duì)自增自減語(yǔ)句可能存在的溢出缺陷作出良好的反應(yīng),或者時(shí)常會(huì)出現(xiàn)將正確的自增自減運(yùn)算作為溢出缺陷進(jìn)行報(bào)錯(cuò)處理的現(xiàn)象.經(jīng)過(guò)研究發(fā)現(xiàn),造成這一問(wèn)題的原因是在語(yǔ)法分析過(guò)程中,不能對(duì)自增自減語(yǔ)句構(gòu)建有效合理的語(yǔ)法樹,因而導(dǎo)致語(yǔ)義理解產(chǎn)生偏差.同時(shí),在C語(yǔ)言語(yǔ)句中,難以對(duì)判斷語(yǔ)句和輸入輸出語(yǔ)句中數(shù)據(jù)類型前后不符的缺陷進(jìn)行檢測(cè).例如scanf(“%d”,&a)語(yǔ)句中,要求a的數(shù)據(jù)類型與前面的%d(整型數(shù)據(jù))一致.如果a的數(shù)據(jù)類型不是整型,此處應(yīng)當(dāng)是一個(gè)比較嚴(yán)重的數(shù)據(jù)類型錯(cuò)誤,但傳統(tǒng)的檢測(cè)工具一般不會(huì)對(duì)這一錯(cuò)誤進(jìn)行檢查[12].

因此基于以上2個(gè)待解決的問(wèn)題,本文提出了代碼替換方法以及一種新的正則表達(dá)式語(yǔ)句來(lái)實(shí)現(xiàn)對(duì)這2種缺陷的有效檢測(cè).

2.3 代碼替換方法

代碼替換方法的核心思想是,將在語(yǔ)法分析階段難以解讀的代碼替換成效果相同且可以被解析的代碼.

在語(yǔ)法分析階段,通常會(huì)引入抽象語(yǔ)法樹對(duì)代碼進(jìn)行解析,因而形似i++的自增自減運(yùn)算,由于僅包含一個(gè)實(shí)體對(duì)象以及2個(gè)相鄰的運(yùn)算符,所以很難被構(gòu)造成1棵符合規(guī)則的抽象語(yǔ)法樹,也就無(wú)法對(duì)其進(jìn)行有效的檢測(cè)[13].

因此,通過(guò)代碼替換方法,將形似i++的自增自減運(yùn)算替換成具有相同效果的運(yùn)算公式,便可以構(gòu)造1棵對(duì)應(yīng)具有相同效果的抽象語(yǔ)法樹,也就可以相應(yīng)地對(duì)其進(jìn)行溢出缺陷的檢測(cè).

C語(yǔ)言中自增自減運(yùn)算通常包括:

替換代碼為:

2.4 正則表達(dá)式匹配語(yǔ)句

該正則表達(dá)式匹配語(yǔ)句主要是為了實(shí)現(xiàn)對(duì)判斷語(yǔ)句和輸入輸出語(yǔ)句中數(shù)據(jù)類型前后不符的缺陷的檢測(cè).這類缺陷在程序編譯過(guò)程中是不會(huì)報(bào)錯(cuò)的,但是會(huì)對(duì)程序的運(yùn)行造成極大的影響.

增加類似如下缺陷模式正則表達(dá)式語(yǔ)句:

其中,“%var%”,“%num%”,“%any%”以及“%str%”都是變量.由于數(shù)據(jù)類型組合多且復(fù)雜,因此這里并沒(méi)有列舉所有的語(yǔ)句.

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)描述

該實(shí)驗(yàn)以C語(yǔ)言為語(yǔ)言基礎(chǔ),并采用故障注入方法,以開(kāi)源軟件為載體,植入CWE數(shù)據(jù)庫(kù)中涉及的,隱含不同類型缺陷的20個(gè)代碼段,進(jìn)行對(duì)比檢測(cè).以Cppcheck為對(duì)照比較14],進(jìn)行對(duì)照實(shí)驗(yàn).本實(shí)驗(yàn)采用查出缺陷的準(zhǔn)確率、誤報(bào)率以及漏報(bào)率作為比較的標(biāo)準(zhǔn),對(duì)于相同的C語(yǔ)言程序源代碼,準(zhǔn)確率越高檢測(cè)的誤報(bào)率和漏報(bào)率越低,則認(rèn)為檢查的效果越好.

準(zhǔn)確率的計(jì)算公式如下:

其中,Ra是準(zhǔn)確率,Na是檢測(cè)出的缺陷數(shù),Nd是程序中的缺陷總數(shù).

漏報(bào)率Rm和誤報(bào)率Rf計(jì)算公式如下:

式(2)中的Nm是漏報(bào)的缺陷數(shù)量,式(4)中的Nf是誤報(bào)為缺陷的數(shù)量.式(3)意為漏報(bào)率還可以表示為1減去準(zhǔn)確率.

3.2 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)設(shè)置了4種類型共20個(gè)的缺陷,包括空指針異常、內(nèi)存泄露、類型溢出和數(shù)組越界各5個(gè).先記錄Cppcheck對(duì)這20個(gè)缺陷的檢測(cè)結(jié)果,如表1所示;再在Cppcheck所使用的缺陷庫(kù)的基礎(chǔ)上,加入本文涉及的2種新方法,組成待驗(yàn)證程序,并對(duì)其進(jìn)行檢測(cè),結(jié)果如表2所示.

表1 Cppcheck運(yùn)行結(jié)果

表2 待驗(yàn)證程序運(yùn)行結(jié)果

從對(duì)比結(jié)果可以看出,加入了本文提出的代碼替換以及正則表達(dá)式的檢測(cè)工具,對(duì)類型溢出缺陷和數(shù)組越界缺陷的檢測(cè)有更加出色的表現(xiàn),漏報(bào)率降低為0%,準(zhǔn)確度得到明顯提高.但是仍然存在一定的誤報(bào)現(xiàn)象,數(shù)組越界出現(xiàn)了20%的誤報(bào)率,在今后工作中仍需要對(duì)此進(jìn)行優(yōu)化和改進(jìn).

4 結(jié) 語(yǔ)

本文在現(xiàn)有的靜態(tài)檢測(cè)技術(shù)的基礎(chǔ)上,針對(duì)缺陷模式匹配方法和現(xiàn)有靜態(tài)檢測(cè)工具使用的缺陷模式庫(kù)所表現(xiàn)出的不足,提出了2種優(yōu)化改進(jìn)的缺陷模式匹配方法.極大地提高了缺陷檢測(cè)的準(zhǔn)確率,降低了漏報(bào)率.雖然本文是在C語(yǔ)言的環(huán)境基礎(chǔ)上進(jìn)行討論與實(shí)驗(yàn)的,但根據(jù)本文談到的設(shè)計(jì)思想,可以擴(kuò)展到其他編程語(yǔ)言的缺陷檢測(cè)中去.

[1]Wichmann B A,Canning A A,Marsh D W R,et al.Industrial perspective on static analysis[J].Software Engineering Journal,1995,10(2):69-75

[2]Silva V D,Kroening D,Weissenbacher G.A survey of automated techniques for formal software verification[J].IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems,2008,27(7):1165-1178

[3]周丹丹,李先國(guó).基于靜態(tài)檢測(cè)工具的軟件缺陷檢測(cè)模型研究[J].計(jì)算機(jī)與現(xiàn)代化,2012,11:55-58

[4]彭坤楊.基于TCAM的高速可擴(kuò)展的正則表達(dá)式匹配技術(shù)[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),2013

[5]熊忠陽(yáng),藺顯強(qiáng),張玉芳,等.結(jié)合網(wǎng)頁(yè)結(jié)構(gòu)與文本特征的正文提取方法[J].計(jì)算機(jī)工程,2013,39(12):200-203,210

[6]楊朝紅,宮云戰(zhàn),肖慶,等.基于軟件缺陷模型的測(cè)試系統(tǒng)[J].北京郵電大學(xué)學(xué)報(bào),2008,31(5):1-4

[7]王斌,吳太文,胡培培.軟件缺陷分類與分析研究[J].計(jì)算機(jī)科學(xué),2013,40(9):16-24

[8]尹相樂(lè),馬力,關(guān)聽(tīng).軟件缺陷分類的研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,19(29):4910-4913

[9]曾福萍,靳慧亮,陸民燕.軟件缺陷模式的研究[J].計(jì)算機(jī)科學(xué),2011,38(2):127-130

[10]葉亮.基于安全規(guī)則的源代碼分析方法研究[D].武漢:華中科技大學(xué),2013

[11]王雅文.基于缺陷模式的軟件測(cè)試技術(shù)研究[D].北京:北京郵電大學(xué),2009

[12]侯蘇寧.基于抽象解釋的數(shù)值程序分析技術(shù)研究[D].長(zhǎng)沙:國(guó)防科技大學(xué),2009

[13]崔舒寧,吳寧,葉丹.建立抽象語(yǔ)法樹模型評(píng)測(cè)C++代碼[J].計(jì)算機(jī)應(yīng)用,2015,35(S1):183-185

[14]張仕金,尚趙偉.基于區(qū)間集的Cppcheck數(shù)組邊界缺陷檢測(cè)[J].計(jì)算機(jī)應(yīng)用,2013,33(11):3257-3261