王 強,周金宇, 金超武

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

1 引言

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

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

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

2 開源軟件缺陷報告問題描述

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

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

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

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

Trp={trn|tn∈Tp}

Trf={trn|tn∈Tf}

(1)

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

表1 開源軟件部分缺陷報告

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

3 獲取程序風險軌跡

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

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

分析函數(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)用序列動態(tài)過程

3.2 提取風險軌跡

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

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

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

3)風險軌跡:將Scorrect和Sdoubt進行對比,選取目標不一致的序列,構(gòu)成集合為風險軌跡集Trisk。

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

3.3 風險軌跡分析

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

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

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

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

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

4.1 風險度傳播計算

(2)

式中,δ和ω均表示正則項。

為了使式(2)達到最小值,對其進行求導計算[13-15],如式(3)所示

ω(R-R0)=0

(3)

對δ和ω進行代換,得到

(4)

對式(2)進行收斂,得到:

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

(5)

式中,M表示單位矩陣。

計算每一輪的風險度傳播公式,如式(6)所示

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

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

(6)

4.2 標簽傳播及安全缺陷定位

(7)

(8)

式中,ζ表示正則項。

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

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

(9)

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

5 實驗分析

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

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

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

5.2 算法評價指標

為了驗證三種算法在缺陷定位方面的有效性,實驗中選取了前N排名(top N rank)、平均準確率(MAP)以及平均倒數(shù)排名(MRR)三個指標作為算法有效性的評價指標。

1)前N排名(top N rank)

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

2)平均準確率(MAP)

該指標指的是對開源軟件中缺陷部位實現(xiàn)定位后,得到準確率的平均值。對于軟件中單獨一個缺陷,通過式(10)計算其平均精度AvgP

(10)

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

(11)

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

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

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

(12)

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

5.3 三種算法有效性對比

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

圖2 三種算法前N排名平均準確率對比

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

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

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

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

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

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

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

6 結(jié)論

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