王 強(qiáng),周金宇, 金超武

(1. 金陵科技學(xué)院信息化建設(shè)與管理中心,江蘇 南京 211169;2. 金陵科技學(xué)院機(jī)電學(xué)院,江蘇 南京 211169;3. 南京航空航天大學(xué)機(jī)電學(xué)院,江蘇 南京 210016)

1 引言

精準(zhǔn)的缺陷定位可以幫助工作人員及時(shí)發(fā)現(xiàn)和修復(fù)問題,在一定程度上降低系統(tǒng)維修的費(fèi)用。目前對(duì)于缺陷定位最常用的兩種算法是靜態(tài)和動(dòng)態(tài)缺陷定位法。靜態(tài)缺陷定位法僅分析軟件程序中缺陷報(bào)告和源代碼,即可對(duì)缺陷定位;動(dòng)態(tài)缺陷定位法則是監(jiān)控程序執(zhí)行過程中每一個(gè)軌跡,分析每一個(gè)軌跡的數(shù)據(jù)點(diǎn)和斷點(diǎn),找出潛在風(fēng)險(xiǎn)位置。

文獻(xiàn)[1]利用方法級(jí)別細(xì)粒度對(duì)軟件缺陷進(jìn)行靜態(tài)定位,將詞向量和TF-IDF算法結(jié)合在一起,將缺陷報(bào)告中的源代碼以向量的形式展現(xiàn)出來;再計(jì)算源代碼中方法體間的相似度,實(shí)現(xiàn)對(duì)向量的拓展;經(jīng)過拓展后,根據(jù)余弦距離對(duì)方法體和缺陷報(bào)告排序,確定缺陷可能存在的位置;文獻(xiàn)[2]憑借條件分類可執(zhí)行切片算法實(shí)現(xiàn)對(duì)軟件中缺陷的有效動(dòng)態(tài)定位,在CESS-MFL中選取不同的謂詞條件,并劃分為若干個(gè)不同的類別;利用相關(guān)執(zhí)行切片對(duì)每個(gè)類別建立相應(yīng)的特征集,再為每個(gè)特征集選取合適的分類執(zhí)行切片譜;計(jì)算每個(gè)切片譜的可疑度,得到可疑度報(bào)告,實(shí)現(xiàn)對(duì)軟件缺陷的定位。

但上述兩種方法面對(duì)不同類型開源軟件時(shí),缺陷定位結(jié)果誤差較大,為此,本文提出一種基于風(fēng)險(xiǎn)軌跡的開源軟件安全性缺陷定位方法。

2 開源軟件缺陷報(bào)告問題描述

將開源軟件的程序集[3]定義為P={s1,s2,…,sm},T={t1,t2,…,tn}表示測(cè)試用例集,tn表示程序中的第n個(gè)測(cè)試用例。測(cè)試用例由輸入項(xiàng)di和預(yù)期結(jié)果oi兩部分組成,即tn=(di,oi)(1≤i≤n)。在P中運(yùn)行一次tn得到的結(jié)果為oi′=P(di),當(dāng)oi′=oi時(shí),說明測(cè)試用例通過程序的驗(yàn)證,將該用例稱為通過的測(cè)試用例;當(dāng)oi′≠oi時(shí),說明測(cè)試用例沒有通過程序的驗(yàn)證,稱其為未通過的測(cè)試用例。P運(yùn)行一次tn,可用執(zhí)行軌跡trn來表示。當(dāng)P執(zhí)行完所有的tn后,得到執(zhí)行用例集T和執(zhí)行軌跡集Tr,兩個(gè)集合中的元素存在相互對(duì)應(yīng)的關(guān)系。

根據(jù)P的執(zhí)行結(jié)果,可以將T分為兩個(gè)無關(guān)聯(lián)的集合Tp和Tf,二者分別表示通過和未通過的執(zhí)行測(cè)試用例集合。同樣地,Tr也被分為集合Trp和Trf,分別表示測(cè)試用例通過和未通過執(zhí)行所構(gòu)成的執(zhí)行軌跡集。將上述四個(gè)集合用式(1)進(jìn)行描述

Tp={tn≥|P(di)=oi}

Tf={tn≥|P(di)≠oi}

Trp={trn|tn∈Tp}

Trf={trn|tn∈Tf}

(1)

運(yùn)行在程序中的任意一個(gè)語句塊[4]都有可能存在缺陷,因此在軟件試運(yùn)行階段,開發(fā)人員和用戶會(huì)根據(jù)試用情況提交缺陷報(bào)告,對(duì)這些缺陷報(bào)告進(jìn)行分析,幫助后期更快地實(shí)現(xiàn)缺陷定位。本文從Eclipse3.1整理了部分缺陷報(bào)告,如表1所示。

表1 開源軟件部分缺陷報(bào)告

表1中,Bug id代表的是缺陷報(bào)告的名稱信息;Open date表示缺陷報(bào)告最終提交的日期;Fix date代表了缺陷報(bào)告最后一次修改的時(shí)間;Summary中描述了缺陷報(bào)告的大體內(nèi)容和展現(xiàn)形式;Description描述了缺陷報(bào)告中的具體內(nèi)容;Fixed files表示軟件缺陷定位模板[5]。通過分析Summary和Description二個(gè)部分,得到Fixed files,進(jìn)而確定軟件中缺陷所在的位置。

3 獲取程序風(fēng)險(xiǎn)軌跡

3.1 獲取函數(shù)調(diào)用序列

函數(shù)調(diào)用序列(FCS)指的是特定輸入環(huán)境下,程序調(diào)用函數(shù)關(guān)系的所有信息。本文主要對(duì)FCS中3個(gè)主要部分進(jìn)行分析:函數(shù)之間的調(diào)用關(guān)系、函數(shù)之間的調(diào)用次數(shù)以及函數(shù)之間的調(diào)用時(shí)間先后順序。

分析函數(shù)之間的調(diào)用關(guān)系,定義FC=a→b[calls="count"],其中,a、b分別表示主調(diào)函數(shù)和被調(diào)函數(shù)[6],a→b表示a調(diào)用b,calls="count"表示a調(diào)用bcount次。函數(shù)調(diào)用序列過程如圖1所示。

圖1 函數(shù)調(diào)用序列動(dòng)態(tài)過程

3.2 提取風(fēng)險(xiǎn)軌跡

在P上運(yùn)行T={t1,t2,…,tn},將預(yù)期輸出結(jié)果定義為on,實(shí)際輸出結(jié)果定義為pn,tn是否通過P的執(zhí)行作為判定目標(biāo)序列[7]和可疑序列的條件。

1)目標(biāo)序列:當(dāng)on=pn時(shí),說明P執(zhí)行tn通過,得到目標(biāo)序列Scorrect。

2)可疑序列:當(dāng)on≠pn時(shí),說明P執(zhí)行tn未通過,得到可疑序列Sdoubt。

3)風(fēng)險(xiǎn)軌跡:將Scorrect和Sdoubt進(jìn)行對(duì)比,選取目標(biāo)不一致的序列,構(gòu)成集合為風(fēng)險(xiǎn)軌跡集Trisk。

通過對(duì)比Scorrect和Sdoubt找出程序中的風(fēng)險(xiǎn)軌跡,提取其中的特征信息,即可構(gòu)建可疑函數(shù)集[8],再對(duì)其進(jìn)行檢測(cè),就可定位到軟件中缺陷的準(zhǔn)確位置。在后續(xù)進(jìn)行回歸測(cè)試時(shí),將多個(gè)包含缺陷的軟件來執(zhí)行同一個(gè)測(cè)試用例,如果出現(xiàn)一個(gè)軟件版本成功、其它軟件版本失敗的情況,以成功的軟件版本程序內(nèi)函數(shù)調(diào)用序列作為目標(biāo)序列。

3.3 風(fēng)險(xiǎn)軌跡分析

針對(duì)軟件中缺陷的風(fēng)險(xiǎn)軌跡,本文深入分析函數(shù)之間的調(diào)用關(guān)系、調(diào)用次數(shù)和調(diào)用時(shí)間順序三個(gè)方面。舉個(gè)例子,當(dāng)Scorrect、Sdoubt二者在調(diào)用關(guān)系上存在不同時(shí),則說明軟件模塊的主調(diào)函數(shù)極有可能出現(xiàn)了缺陷;當(dāng)Scorrect、Sdoubt二者之間的調(diào)用時(shí)間順序不相同時(shí),說明軟件模塊的調(diào)用序列可能出現(xiàn)了缺陷;當(dāng)Scorrect、Sdoubt在上述三種關(guān)系都出現(xiàn)了不同時(shí),不考慮調(diào)用時(shí)間順序的影響,直接對(duì)調(diào)用關(guān)系和調(diào)用次數(shù)進(jìn)行分析,軟件模塊也很大可能是由于二者不一致而導(dǎo)致缺陷的出現(xiàn)。

當(dāng)對(duì)軟件模塊測(cè)試后,得到Scorrect和Sdoubt,憑借Linux文本比對(duì)促使diff找出軟件中缺陷的風(fēng)險(xiǎn)軌跡,diff通過找出Scorrect和Sdoubt二者之間的不一致序列,然后標(biāo)記,標(biāo)記的情況通常分為三種:①將Scorrect和Sdoubt之間不一致的序列標(biāo)記為“|”;②將Scorrect和Sdoubt之間不一致的序列標(biāo)記為“<”或“>”;③沒有標(biāo)記。

在軟件模塊調(diào)用序列中提取可疑函數(shù)fsuspect,并根據(jù)其位置的不同進(jìn)行排序,得到可疑函數(shù)候選集Tsuspect={fsuspect1,fsuspect2,…,fsuspectn|n≥1}。依次對(duì)候選集中的數(shù)據(jù)進(jìn)行檢測(cè),確定軟件的缺陷函數(shù)[9]。

4 開源軟件安全性缺陷定位

在綜合考慮了開源軟件中序列風(fēng)險(xiǎn)軌跡類型和調(diào)用關(guān)系,本文選取TPA方法作為實(shí)現(xiàn)方法。TPA方法分為風(fēng)險(xiǎn)度傳播和標(biāo)簽傳播兩部分,從歷史缺陷報(bào)告中獲取已經(jīng)成功修復(fù)的缺陷,構(gòu)成初始標(biāo)簽矩陣L0,再對(duì)標(biāo)簽矩陣構(gòu)建初始風(fēng)險(xiǎn)度向量R0,據(jù)此兩個(gè)條件,設(shè)計(jì)風(fēng)險(xiǎn)度傳播圖(SG-SC和CG),通過對(duì)圖中傳播模塊的風(fēng)險(xiǎn)度進(jìn)行分析,得到風(fēng)險(xiǎn)度向量R。最后確定缺陷報(bào)告標(biāo)簽L,對(duì)標(biāo)簽值進(jìn)行分析,即可實(shí)現(xiàn)開源軟件缺陷的準(zhǔn)確定位。

4.1 風(fēng)險(xiǎn)度傳播計(jì)算

(2)

式中,δ和ω均表示正則項(xiàng)。

為了使式(2)達(dá)到最小值,對(duì)其進(jìn)行求導(dǎo)計(jì)算[13-15],如式(3)所示

ω(R-R0)=0

(3)

對(duì)δ和ω進(jìn)行代換,得到

(4)

對(duì)式(2)進(jìn)行收斂,得到:

RT=(1-p-q)(M-pWSG-SC-qWCG)-1R0T

(5)

式中,M表示單位矩陣。

計(jì)算每一輪的風(fēng)險(xiǎn)度傳播公式,如式(6)所示

Ri+1=(pWSG-SC+qWCG)RiT+(1-p-q)R0

=(p+q)W′RiT+(1-p-q)R0

(6)

4.2 標(biāo)簽傳播及安全缺陷定位

(7)

(8)

式中,ζ表示正則項(xiàng)。

對(duì)式(8)做最小化處理,得到

Ln+1=(1-η)WVR-VRL+ηWR

(9)

通過上述計(jì)算,得到開源軟件標(biāo)簽分布情況,根據(jù)其在模塊中的位置對(duì)其進(jìn)行排列,當(dāng)標(biāo)簽值越大時(shí),該模塊中存在缺陷的概率就越大,以此實(shí)現(xiàn)缺陷的精準(zhǔn)定位。

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

5.1 實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證本文方法在開源軟件缺陷定位中的有效性,與引言中提到的細(xì)粒度和條件分類可執(zhí)行切片算法展開對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)在開源軟件Linux上實(shí)現(xiàn),系統(tǒng)內(nèi)存大小為8GB,CPU頻率為2.7GHz。實(shí)驗(yàn)中用到的數(shù)據(jù)集為Eclipse3.1、AspectJ1.5和SWT3.1,介紹如表2所示。

表2 數(shù)據(jù)集信息

5.2 算法評(píng)價(jià)指標(biāo)

為了驗(yàn)證三種算法在缺陷定位方面的有效性,實(shí)驗(yàn)中選取了前N排名(top N rank)、平均準(zhǔn)確率(MAP)以及平均倒數(shù)排名(MRR)三個(gè)指標(biāo)作為算法有效性的評(píng)價(jià)指標(biāo)。

1)前N排名(top N rank)

該指標(biāo)表示缺陷報(bào)告中缺陷的定位方法,在返回結(jié)果的前N(N=1,5,10)位中所占的數(shù)量比例。在使用該項(xiàng)指標(biāo)評(píng)判缺陷定位效果時(shí),對(duì)于給定的缺陷報(bào)告,如果在前N個(gè)結(jié)果中含有1個(gè)缺陷定位的方法體,那么就認(rèn)為算法成功定位到缺陷。top N rank的值越大,說明算法的缺陷定位方法越精準(zhǔn)。

2)平均準(zhǔn)確率(MAP)

該指標(biāo)指的是對(duì)開源軟件中缺陷部位實(shí)現(xiàn)定位后,得到準(zhǔn)確率的平均值。對(duì)于軟件中單獨(dú)一個(gè)缺陷,通過式(10)計(jì)算其平均精度AvgP

(10)

式中,Y表示算法對(duì)軟件中的缺陷進(jìn)行定位后,構(gòu)成的源代碼方法體集合,|Y|表示共獲得的源代碼方法體總數(shù),rankk表示第k個(gè)正確定位的源代碼方法體在總數(shù)中的排名。MAP公式為

(11)

式中,Q表示開源軟件的缺陷報(bào)告集,|Q|表示Q中含有缺陷報(bào)告的個(gè)數(shù),AvgPj表示第j個(gè)缺陷報(bào)告的平均精度值。

3)平均倒數(shù)排名(MRR)

該指標(biāo)指的是正確定位缺陷的方法體位置倒數(shù)平均值。當(dāng)MRR的值越大時(shí),說明算法的定位精度就越高。計(jì)算過程如式(12)所示

(12)

式中,ranki表示算法定位到的缺陷與第i個(gè)缺陷報(bào)告中的方法體最靠前排名的位置。

5.3 三種算法有效性對(duì)比

首先,對(duì)于前N排名指標(biāo),對(duì)比本文方法與細(xì)粒度和條件分類可執(zhí)行切片算法的有效性。選取TOP1、TOP5和TOP10的平均準(zhǔn)確率,實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 三種算法前N排名平均準(zhǔn)確率對(duì)比

從圖2中可以看出,三種算法中本文方法的平均準(zhǔn)確率最高,在TOP10準(zhǔn)確率達(dá)到了100%,而其它兩種方法最高準(zhǔn)確率僅為70%。由此說明本文方法在缺陷定位方面具有較高的準(zhǔn)確率。

接下來利用平均倒數(shù)排名指標(biāo)對(duì)三種算法的有效性展開分析,實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 三種算法平均倒數(shù)排名對(duì)比

從圖3中可以看出,不論在哪個(gè)排名中,利用本文方法得到的缺陷定位MRR值都是最高的,而其它兩種方法的MRR值相對(duì)較低。說明通過本文方法定位到的軟件缺陷,與實(shí)際位置擬合程度最高。

最后針對(duì)不同的數(shù)據(jù)集,利用三種算法進(jìn)行缺陷定位的對(duì)比,實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 不同算法在三個(gè)數(shù)據(jù)集上缺陷定位對(duì)比

通過觀察圖4可以看出,無論在哪個(gè)數(shù)據(jù)集上,利用本文方法對(duì)軟件缺陷定位的概率值始終都是最高的,說明本文方法可以得到更精準(zhǔn)的缺陷位置,實(shí)現(xiàn)精準(zhǔn)定位

6 結(jié)論

由于開源軟件各個(gè)模塊之間存在著復(fù)雜的關(guān)系,傳統(tǒng)方法在對(duì)其進(jìn)行缺陷定位時(shí),常常出現(xiàn)較大的誤差。因此,本文利用風(fēng)險(xiǎn)軌跡,提出一種安全性缺陷定位方法。在綜合考慮了軟件模塊間的相似度和風(fēng)險(xiǎn)度之后,構(gòu)建風(fēng)險(xiǎn)度傳播模塊,根據(jù)風(fēng)險(xiǎn)度向量值確定缺陷報(bào)告標(biāo)簽,通過對(duì)比標(biāo)簽值,實(shí)現(xiàn)軟件缺陷的精準(zhǔn)定位。