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

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

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

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

(jb.wang2000@163.com)

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

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

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

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

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

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

1.2 正則表達式及其意義

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

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

1.3 軟件缺陷

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

1.4 軟件缺陷模式

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

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

2 缺陷模式匹配方法

2.1 軟件缺陷檢測模型

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

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

2.2 缺陷模式匹配存在的問題

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

因此基于以上2個待解決的問題,本文提出了代碼替換方法以及一種新的正則表達式語句來實現(xiàn)對這2種缺陷的有效檢測.

2.3 代碼替換方法

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

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

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

C語言中自增自減運算通常包括:

替換代碼為:

2.4 正則表達式匹配語句

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

增加類似如下缺陷模式正則表達式語句:

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

3 實驗結(jié)果與分析

3.1 實驗描述

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

準確率的計算公式如下:

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

漏報率Rm和誤報率Rf計算公式如下:

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

3.2 實驗結(jié)果

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

表1 Cppcheck運行結(jié)果

表2 待驗證程序運行結(jié)果

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

4 結(jié) 語

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

[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]周丹丹,李先國.基于靜態(tài)檢測工具的軟件缺陷檢測模型研究[J].計算機與現(xiàn)代化,2012,11:55-58

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

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

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

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

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

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

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

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

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

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

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