基于關(guān)聯(lián)規(guī)則的終端軟件缺陷檢測(cè)方法研究

呂華輝，劉欣，農(nóng)彩勤

（1.中國(guó)南方電網(wǎng)有限責(zé)任公司，廣東廣州 510000；2.南方電網(wǎng)數(shù)字電網(wǎng)研究院有限公司，廣東廣州 510663）

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，軟件的應(yīng)用范圍迅速擴(kuò)大。為了保證終端軟件在使用過(guò)程中的安全性與穩(wěn)定性，需要對(duì)終端軟件缺陷進(jìn)行檢測(cè)。傳統(tǒng)的軟件缺陷檢測(cè)方法主要應(yīng)用了靜態(tài)分析技術(shù)，通過(guò)這種檢測(cè)技術(shù)可實(shí)現(xiàn)對(duì)軟件代碼的分析與評(píng)估，同時(shí)不需要執(zhí)行運(yùn)行程序，能夠及時(shí)發(fā)現(xiàn)終端軟件中存在的缺陷，但隨著軟件應(yīng)用環(huán)境的日漸復(fù)雜與軟件數(shù)量的激增，傳統(tǒng)的軟件缺陷檢測(cè)方法在對(duì)終端軟件的缺陷進(jìn)行檢測(cè)時(shí)，出現(xiàn)了漏報(bào)與誤報(bào)情況[1-2]。

為此，國(guó)內(nèi)專家學(xué)者對(duì)此展開(kāi)相關(guān)研究。文獻(xiàn)[3]提出基于N-gram 模型的終端軟件缺陷檢測(cè)方法，該方法建立了終端軟件缺陷N-gram 模型，通過(guò)該模型提取終端軟件的缺陷數(shù)據(jù)，將終端軟件缺陷數(shù)據(jù)存儲(chǔ)到數(shù)據(jù)庫(kù)中，然后對(duì)模型進(jìn)行優(yōu)化，最后通過(guò)優(yōu)化后的終端軟件缺陷N-gram 模型實(shí)現(xiàn)了終端軟件缺陷的檢測(cè)，該方法容易實(shí)現(xiàn)，并且檢測(cè)誤報(bào)率較低，但檢測(cè)漏報(bào)率較高。

為了解決以上問(wèn)題，該文提出了基于關(guān)聯(lián)規(guī)則的終端軟件缺陷檢測(cè)方法。

1 終端軟件缺陷特征提取

在終端軟件中，二進(jìn)制軟件的尾指令較為復(fù)雜，無(wú)法直接進(jìn)行分析，需要對(duì)二進(jìn)制軟件賦予中間指令集，并增加代碼量，從二進(jìn)制軟件的路徑與匯編指令入手，提取軟件缺陷特征[4]。

二進(jìn)制軟件基本塊執(zhí)行順序根據(jù)軟件底層指令確定，軟件底層指令位于尾指令前面，由多個(gè)匯編指令構(gòu)成，基本塊在執(zhí)行第一行代碼時(shí)，不需要執(zhí)行二進(jìn)制程序，此時(shí)，基本塊可表示為返回指令集合設(shè)置為a={b1,b2,…,bm}，m為基本塊a的地址長(zhǎng)度，b1表示基本塊a的跳轉(zhuǎn)指令，bm表示基本塊a的匯編指令。

二進(jìn)制軟件的第一行代碼程序可表示為若干基本塊的集合A={a1,a2,…,ai}，i表示基本塊的控制信息[5-6]。

為了提取終端軟件特征信息，需要根據(jù)尾指令中的自定義函數(shù)將基本塊分為條件跳轉(zhuǎn)基本塊與返回基本塊，條件跳轉(zhuǎn)基本塊中的語(yǔ)句可通過(guò)jmp、je進(jìn)行判斷，如果歸為同一類別，則條件跳轉(zhuǎn)基本塊的代碼顯示為true，如果條件條狀基本塊中含有庫(kù)函數(shù)與自定義函數(shù)，不歸為同一類別，則代碼程序顯示為false。

在劃分完成后，自定義基本庫(kù)中包含缺陷，需要提取自定義基本庫(kù)中的缺陷特征信息進(jìn)行分析?；緣K通過(guò)自定義返回指令可由基本塊an返回到基本塊aj，基本塊an與基本塊aj之間的缺陷路徑可由rn,j={an,aj,c|j∈An} 表示，其中，an為缺陷路徑中點(diǎn)，aj表示缺陷路徑終點(diǎn)，c表示缺陷路徑變量，An表示基本塊an的特征集合[7-8]。

在終端軟件中如果多次進(jìn)行循環(huán)與基本塊判斷，會(huì)導(dǎo)致終端軟件的缺陷路徑以指數(shù)形式增加，從而造成缺陷路徑爆炸，為降低缺陷路徑的增加速度，在提取缺陷路徑特征時(shí)，只提取終端軟件中相鄰基本塊的缺陷路徑，并以自定義調(diào)用方式記錄軟件程序的判斷與基本塊循環(huán)。為了使缺陷路徑迭代過(guò)程更優(yōu)，采用廣度優(yōu)先的方式使缺陷路徑循環(huán)。缺陷路徑特征提取過(guò)程如下。

首先，在二進(jìn)制程序中將匯編指令集轉(zhuǎn)換為跳轉(zhuǎn)指令集，并將底層指令集進(jìn)行返回操作，在返回過(guò)程中將其劃分為多個(gè)不同的基本塊，并根據(jù)基本塊第一行代碼的數(shù)量將其由高到低進(jìn)行排序，標(biāo)記為A={a1,a2,…,ai} 。通過(guò)反匯編技術(shù)[9-10]將基本塊作為節(jié)點(diǎn)，基本塊之間的返回作為特征變量，構(gòu)建控制流圖G={rn,j,A,Begin,Exit|n,j＜A|}，G表示二進(jìn)制程序中代碼的控制流信息。

然后，提取二進(jìn)制程序中代碼特征，將第一行代碼中的底層指令轉(zhuǎn)換為條件跳轉(zhuǎn)指令，并提取特征變量。通過(guò)基本塊中的缺陷路徑提取路徑復(fù)雜度，根據(jù)出入度的頻率對(duì)基本塊進(jìn)行調(diào)用，挖掘自定義基本庫(kù)函數(shù)的基本塊數(shù)據(jù)，對(duì)數(shù)據(jù)進(jìn)行靜態(tài)分析，提取自定義基本庫(kù)中的基本塊出入度[11]。

最后，采用廣度優(yōu)先方法對(duì)缺陷路徑進(jìn)行遍歷，根據(jù)基本塊的復(fù)雜度與出入度特征提取缺陷路徑特征，缺陷路徑特征包括代碼程序的匯編指令特征與底層指令特征，可以表示為：

其中，t表示基本塊的缺陷路徑特征維度。

2 基于關(guān)聯(lián)規(guī)則的缺陷檢測(cè)

根據(jù)以上缺陷特征提取結(jié)果，采用關(guān)聯(lián)規(guī)則方法檢測(cè)終端軟件的缺陷。在檢測(cè)過(guò)程中需要申請(qǐng)終端軟件的匹配權(quán)限，并將基本塊中的頻繁項(xiàng)進(jìn)行檢測(cè)，權(quán)限匹配程度與基本塊數(shù)量的比值能夠體現(xiàn)終端軟件缺陷的支持度，采用關(guān)聯(lián)規(guī)則算法計(jì)算終端軟件中基本塊的缺陷度，計(jì)算公式為：

其中，L表示終端軟件基本塊的缺陷度；d表示終端軟件中基本塊的數(shù)量；Nd表示基本塊與二進(jìn)制程序代碼的關(guān)聯(lián)度；Td表示終端軟件中基本塊經(jīng)過(guò)跳轉(zhuǎn)指令與相鄰基本塊的缺陷路徑[12]。

根據(jù)計(jì)算的基本塊缺陷度判斷終端軟件在缺陷檢測(cè)過(guò)程中是否存在缺陷家族，如果存在缺陷家族，需要計(jì)算軟件缺陷檢測(cè)的誤報(bào)率，選取檢測(cè)誤報(bào)閾值p，將終端軟件識(shí)別的基本塊數(shù)量進(jìn)行統(tǒng)計(jì)，并通過(guò)路徑頻繁項(xiàng)檢測(cè)基本塊的指令地址，采用關(guān)聯(lián)規(guī)則算法計(jì)算終端軟件缺陷檢測(cè)誤報(bào)率wFalsealarmrate為：

其中，M表示終端軟件被二進(jìn)制程序正確識(shí)別的數(shù)量；δ表示關(guān)聯(lián)規(guī)則算法中的支持系數(shù)；K表示終端軟件中被識(shí)別出來(lái)的缺陷家族。

根據(jù)數(shù)據(jù)計(jì)算結(jié)果以及提取出軟件缺陷特征信息，采用關(guān)聯(lián)規(guī)則算法對(duì)終端軟件缺陷進(jìn)行檢測(cè)的流程如圖1 所示。

圖1 終端軟件缺陷檢測(cè)流程

首先，建立終端軟件缺陷訓(xùn)練樣本庫(kù)，樣本庫(kù)中包含若干個(gè)軟件缺陷家族，缺陷家族中包含大量終端軟件缺陷特征數(shù)據(jù)。采用靜態(tài)檢測(cè)方法對(duì)缺陷家族中缺陷特征數(shù)據(jù)反編譯，獲得終端軟件中的缺陷文件，并從該文件中獲得終端軟件的缺陷申請(qǐng)列表[13-14]。

然后，采用關(guān)聯(lián)規(guī)則方法構(gòu)建缺陷檢測(cè)模型。在關(guān)聯(lián)規(guī)則方法中引入倒排理論，可以提升終端軟件缺陷檢測(cè)的速度，迅速生成缺陷路徑中的頻繁項(xiàng)，通過(guò)關(guān)聯(lián)規(guī)則方法融合匯編指令集與底層指令集，根據(jù)軟件缺陷支持度挖掘候選項(xiàng)集的缺陷數(shù)據(jù)集，采用靜態(tài)檢測(cè)工具為檢測(cè)出的缺陷數(shù)據(jù)集提供缺陷可能值，以便識(shí)別出終端軟件中非缺陷項(xiàng)，降低終端軟件缺陷檢測(cè)的誤報(bào)率與漏報(bào)率。通過(guò)檢測(cè)出的缺陷數(shù)據(jù)集建立缺陷檢測(cè)模型圖，如圖2 所示。

圖2 缺陷檢測(cè)模型

通過(guò)該模型對(duì)終端軟件二進(jìn)制程序代碼進(jìn)行檢測(cè)，輸出檢測(cè)結(jié)果，并利用一級(jí)處理程序輸出Tool-i結(jié)果并生成優(yōu)化結(jié)果，在優(yōu)化過(guò)程中，根據(jù)二級(jí)處理程序標(biāo)識(shí)出終端軟件缺陷項(xiàng)，分析并查找軟件缺陷項(xiàng)的描述項(xiàng)，作為誤報(bào)規(guī)則，根據(jù)輸出結(jié)果將缺陷重復(fù)項(xiàng)與重報(bào)項(xiàng)進(jìn)行人工確認(rèn)，并給予不同的確認(rèn)級(jí)別，當(dāng)可信度級(jí)別為1 時(shí)，表示標(biāo)識(shí)出來(lái)的重復(fù)缺陷項(xiàng)的優(yōu)先級(jí)別較高，此時(shí)需要對(duì)重復(fù)缺陷項(xiàng)進(jìn)行優(yōu)化檢測(cè)。

最后，進(jìn)行匹配檢測(cè)。與模型中重復(fù)缺陷項(xiàng)與描述項(xiàng)進(jìn)行匹配，如果匹配的程度大于檢測(cè)的程度，則終端軟件缺陷項(xiàng)被成功檢測(cè)出來(lái)，此時(shí)輸出檢測(cè)結(jié)果[15-16]。

3 實(shí)驗(yàn)分析

為驗(yàn)證該文提出的基于關(guān)聯(lián)規(guī)則的終端軟件缺陷檢測(cè)方法的有效性，選用該文提出的方法與傳統(tǒng)的基于N-gram 模型的終端軟件缺陷檢測(cè)方法和基于數(shù)據(jù)挖掘的終端軟件缺陷檢測(cè)方法進(jìn)行實(shí)驗(yàn)。設(shè)置實(shí)驗(yàn)參數(shù)如表1 所示。

表1 實(shí)驗(yàn)參數(shù)

根據(jù)上述參數(shù)，選用該文提出的檢測(cè)方法和傳統(tǒng)方法進(jìn)行檢測(cè)，為了確保實(shí)驗(yàn)結(jié)果的權(quán)威性，分別對(duì)已知缺陷軟件和未知缺陷軟件進(jìn)行檢測(cè)，分析缺陷終端檢測(cè)結(jié)果的命中率，非缺陷終端軟件的誤報(bào)率。命中率計(jì)算公式為：

其中，wHitrate為檢測(cè)的命中率，T表示缺陷軟件被準(zhǔn)確識(shí)別的數(shù)目，F(xiàn)表示存在缺陷的終端軟件被錯(cuò)誤識(shí)別成非缺陷軟件的數(shù)量。命中率實(shí)驗(yàn)結(jié)果如圖3 所示。

圖3 命中率實(shí)驗(yàn)結(jié)果

根據(jù)圖3 可知，隨著檢測(cè)樣本數(shù)量的增加，檢測(cè)命中率呈現(xiàn)下降趨勢(shì)，這種趨勢(shì)在檢測(cè)軟件未知缺陷上尤為明顯。對(duì)于軟件已知缺陷，數(shù)據(jù)挖掘檢測(cè)方法的檢測(cè)命中率最高，當(dāng)檢測(cè)樣本數(shù)量為70 個(gè)時(shí)，命中率仍然在80%以上，該文提出的檢測(cè)方法檢測(cè)命中率為70%，而基于N-gram 檢測(cè)方法的檢測(cè)命中率則降低到40%。對(duì)于軟件未知缺陷，該文提出的檢測(cè)方法檢測(cè)命中率要遠(yuǎn)遠(yuǎn)高于傳統(tǒng)檢測(cè)方法，當(dāng)檢測(cè)數(shù)量為70 個(gè)時(shí)，該文檢測(cè)方法命中率高達(dá)90%，基于N-gram 檢測(cè)方法的檢測(cè)命中率則降低到40%，數(shù)據(jù)挖掘檢測(cè)方法的檢測(cè)命中率降低到15%。

根據(jù)式（3）計(jì)算缺陷檢測(cè)的誤報(bào)率，得到的誤報(bào)率實(shí)驗(yàn)結(jié)果如圖4 所示。

根據(jù)圖4 可知，對(duì)于軟件未知缺陷，三種方法的誤報(bào)率均比軟件已知缺陷的誤報(bào)率要高，但是傳統(tǒng)誤報(bào)率最高，已經(jīng)超過(guò)用戶要求，而該文提出的檢測(cè)方法誤報(bào)率始終低于5%，驗(yàn)證了該文提出的檢測(cè)方法實(shí)用性更強(qiáng)，更適合應(yīng)用于實(shí)際工作中。

圖4 誤報(bào)率實(shí)驗(yàn)結(jié)果

4 結(jié)束語(yǔ)

隨著軟件數(shù)量的增加及應(yīng)用環(huán)境的復(fù)雜，軟件缺陷逐漸暴露。為滿足終端軟件缺陷檢測(cè)的需求，并解決傳統(tǒng)軟件缺陷檢測(cè)方法出現(xiàn)的問(wèn)題，提出基于關(guān)聯(lián)規(guī)則的終端軟件缺陷檢測(cè)方法，實(shí)現(xiàn)對(duì)終端軟件的缺陷檢測(cè)，該文檢測(cè)方法可有效檢測(cè)出終端軟件的缺陷，使終端軟件的運(yùn)行更穩(wěn)定。