基于風險軌跡與復雜網(wǎng)絡的缺陷定位方法

王曙燕,韓 雪,孫家澤

(西安郵電大學 計算機學院,西安 710121)

0 概述

隨著軟件復雜性的增加,軟件缺陷幾乎不可避免。程序調試在軟件開發(fā)與維護過程中是一項成本昂貴且復雜耗時的工作[1]。研究表明,軟件發(fā)展維護過程中50% ～80%的成本用于軟件測試和調試[2]。因此,如何有效快速定位軟件缺陷是保證軟件高質量和可靠性的關鍵性工作。

當程序輸出偏離預期輸出時,通常說明程序中存在缺陷。傳統(tǒng)的軟件缺陷定位方法大多是在源碼中設置斷點,在失敗的輸入上重新執(zhí)行程序,并檢查程序狀態(tài)以了解失敗的原因,但該方法依賴于程序員的主觀判斷,效率不高。為實現(xiàn)軟件缺陷定位自動化,許多用于調試的自動缺陷定位技術被提出。文獻[3]提出將程序切片技術用于軟件調試中,常被用來減少錯誤的搜索范圍,但存在時間和空間復雜度過高的問題。文獻[4]提出基于覆蓋信息的錯誤定位技術,通過對成功和失敗測試用例執(zhí)行過程中的覆蓋信息進行分析,計算語句可疑度,例如Tarantula[5]、Jaccard[6]和Ochiai[7]等方法,但這些方法會受到偶然性成功測試用例的影響[8],使定位效率降低。文獻[9]提出程序譜的概念,程序譜記錄了程序運行過程的某方面信息,可用于跟蹤程序行為。文獻[10]通過對程序頻譜間差異和回歸缺陷的相關性進行研究,實驗結果表明有缺陷的程序在運行過程中表現(xiàn)出行為異常的概率較大。文獻[11]根據(jù)程序光譜間的相似性進行缺陷定位,但如果錯誤語句不在可疑集合中,則定位效率會明顯降低。文獻[12]收集時間頻譜信息用于輔助缺陷定位,通過對比成功和失敗測試用例執(zhí)行的時間譜并找出差異,然而差異處存在缺陷的概率較大。文獻[13]通過構建程序頻譜及其執(zhí)行結果之間的關系模型,提出基于條件概率的缺陷定位方法,總體定位效果顯著。但上述技術均是關注軟件局部特征而非全局特征,適用范圍相對較小。

為尋找通用的軟件缺陷定位方法,文獻[14]將復雜網(wǎng)絡理論引入軟件缺陷定位領域,提出基于中心度量的軟件缺陷定位方法,通過度中心性和結構洞兩個度量值計算程序語句的懷疑度。文獻[15]根據(jù)錯誤語句在通過測試執(zhí)行和測試執(zhí)行失敗過程中的距離對程序各語句進行懷疑度計算,提出基于復雜網(wǎng)絡理論的軟件缺陷定位方法,該方法可同時對程序中的單個錯誤和多個錯誤進行定位。

相對而言,基于語句粒度的缺陷定位分析研究較多,而基于函數(shù)這一粒度進行分析的缺陷定位研究較少。從實際情況看,程序中出現(xiàn)的多數(shù)缺陷是由函數(shù)內部的語句間邏輯錯誤引起,因此以函數(shù)為研究對象定位軟件缺陷更符合生產(chǎn)環(huán)境[16]。面向對象程序,文獻[17]指出如果某個方法僅出現(xiàn)在程序通過或失敗程序中,此方法可行性不高。文獻[18]通過挖掘控制流異常對缺陷進行定位,該方法可有效定位缺陷函數(shù)。文獻[19]將缺陷報告和源代碼方法體用向量表示,計算其余弦距離并排序,提出的MethodLocator技術可有效定位缺陷函數(shù)。針對以函數(shù)為分析粒度進行缺陷定位效率不高的問題,本文提出基于風險軌跡與復雜網(wǎng)絡的缺陷定位方法(Defect Location Based on Risk Trace and Complex Network,DRC),以期在滿足對大規(guī)模軟件缺陷定位需求的同時,提高軟件缺陷定位效率。

1 程序風險軌跡獲取

在程序執(zhí)行時動態(tài)輸入多個測試用例,獲取運行過程中的函數(shù)調用序列,根據(jù)測試用例在不同缺陷版本程序的執(zhí)行結果,為待測程序選擇目標序列和可疑序列,提取風險軌跡并檢測可疑函數(shù)候選集。

1.1 函數(shù)調用序列獲取

函數(shù)調用序列(Function Call Sequence,FCS)指程序在特定輸入下函數(shù)之間調用關系的全信息。本文主要分析函數(shù)調用序列的3個部分:函數(shù)間的調用關系,函數(shù)間調用次數(shù)及函數(shù)調用的時間順序。

定義1(函數(shù)調用關系) FC=a→b[calls="count"],其中,a與b均為函數(shù)名,a稱為主調函數(shù),b稱為被調函數(shù),a→b表示函數(shù)a調用函數(shù)b,calls="count"表示a函數(shù)調用b函數(shù)count次。

動態(tài)獲取函數(shù)調用序列,如圖1所示。利用C程序代碼追蹤工具Pvtrace[20],通過定制特殊的分析函數(shù),可獲取函數(shù)運行過程中的地址信息。然后將分析函數(shù)與待測程序一起編譯,就可獲取一個調用路徑可追蹤的新程序。將設計好的多個測試用例動態(tài)輸入調用路徑可追蹤的程序中,多次運行程序,得到函數(shù)運行時所對應的地址序列文件,利用可將指令地址轉換為函數(shù)名的工具Addr2line,把地址信息轉換為對應的函數(shù)名稱,Pvtrace可以通過分析函數(shù)執(zhí)行序列得到函數(shù)間的調用序列dot文件。

圖1 函數(shù)調用序列獲取流程

1.2 風險軌跡提取

若程序P在測試用例ti上執(zhí)行對應預期輸出結果為oi,實際輸出結果為pi,根據(jù)測試用例在程序上執(zhí)行是否通過可以定義目標序列和可疑序列。

定義2(目標序列) 如果pi=oi,則說明程序在測試用例ti上執(zhí)行通過,所對應的函數(shù)調用序列稱為目標序列Scorrect。

定義3(可疑序列) 如果pi≠oi,則說明程序在測試用例ti上執(zhí)行不通過,所對應的函數(shù)調用序列稱為可疑序列Sdoubt。

定義4(風險軌跡) 通過對比目標序列和可疑序列,提取可疑序列與目標序列不一致序列的集合稱為風險軌跡Trisk。

對于特定的輸入,程序函數(shù)調用序列是固定的。存在缺陷的程序在執(zhí)行測試用例時可能會導致函數(shù)調用序列發(fā)生異常,將目標序列和可疑序列進行對比找出程序風險軌跡,分析并提取可疑函數(shù)集,依次檢測并定位缺陷函數(shù)。通過運行正確的程序可獲取目標序列,也可能在大多情況下無法獲得一個正確的軟件版本,但卻可以得到含有不同缺陷版本的軟件。在回歸測試中,對比多個含缺陷版本的程序,同一個測試用例可能在一個版本中執(zhí)行失敗,在另一個版本中執(zhí)行成功,在程序執(zhí)行成功中的函數(shù)調用序列就是目標序列[21]。假設程序P在回歸測試中的版本是P1,P2,…,Pn。如果測試用例t在P1中運行失敗,在Pi(1

1.3 風險軌跡分析

本文主要分析函數(shù)間的調用關系、函數(shù)間調用次數(shù)及函數(shù)調用的時間順序3種函數(shù)調用信息。當可疑序列與目標序列調用關系或調用次數(shù)不一致時,異常位置的主調函數(shù)很可能存在缺陷。當可疑序列與目標序列調用時間順序不一致時,說明異常位置的上一調用序列有很大嫌疑,以致異常處函數(shù)調用時間順序異常。如果可疑序列與目標序列同時出現(xiàn)函數(shù)間的調用關系、調用次數(shù)及調用時間順序不一致時,則認為調用關系和調用次數(shù)異常對程序缺陷影響更大,可忽略調用時間順序異常,因為調用時間順序不一致可由多種因素造成,提取可疑函數(shù)候選集時,只考慮調用關系和調用次數(shù)異常。

在獲取待測程序目標序列和可疑序列后,利用Linux文本比對命令diff找出程序風險軌跡,diff命令會在可疑序列與目標序列不一致處打上標記,共有3種情況:1)不一致處標記為“|”,表示可疑序列與目標序列對應行調用信息(調用關系或次數(shù))有所不同,提取不一致位置的主調函數(shù)作為可疑函數(shù);2)不一致處標記為“<”或“>”,表示可疑序列與目標序列調用時間順序(調用序列個數(shù))不同,提取發(fā)生異常處上一位置的主調函數(shù)和被調函數(shù)作為可疑函數(shù);3)無標記,說明目標序列和可疑序列完全相同,不提取可疑函數(shù)。

將提取的可疑函數(shù)fsuspect按其在調用序列的執(zhí)行次序排列,作為可疑函數(shù)候選集Tsuspect={fsuspect1,fsuspect2,…,fsuspectn|n≥1},然后依次檢測,定位缺陷函數(shù)。

2 DRC方法

2.1 復雜網(wǎng)絡圖構建

由于復雜網(wǎng)絡在解決復雜問題方面的魯棒性和自適應性,因此在過去的幾十年中受到來自不同領域研究工作者的極大興趣與廣泛關注。最重要的是,復雜網(wǎng)絡具有很強的數(shù)學背景,使得復雜網(wǎng)絡成為理解系統(tǒng)復雜性的重要工具。復雜網(wǎng)絡的研究成果為探索大規(guī)模軟件系統(tǒng)提供有力支撐,利用網(wǎng)絡的觀點看待軟件系統(tǒng)得到了眾多研究者的認同。復雜網(wǎng)絡為缺陷定位提供了新思路[22],在不深究程序內部細節(jié)的情況下,從整體和全局的角度探究與軟件缺陷相關的信息量。本文將函數(shù)作為分析對象研究缺陷定位,隨著粒度變大,網(wǎng)絡結構越來越簡單,從而能忽略一些局部的細節(jié)問題,獲得更通用的研究結果。

在函數(shù)動態(tài)調用關系圖中位于葉節(jié)點的函數(shù)不會調用其他函數(shù),導致函數(shù)調用序列發(fā)生異常的可能性很小,基于風險軌跡的分析忽略此類缺陷。在檢測完畢分析風險軌跡提取的可疑函數(shù)集后未發(fā)現(xiàn)缺陷函數(shù)或目標序列與可疑序列并無異常時,將待測程序的函數(shù)調用序列中函數(shù)名作為節(jié)點,函數(shù)間調用關系作為邊為程序建復雜網(wǎng)絡圖,求其節(jié)點出度值(Out Degree,OD)。OD值代表該節(jié)點調用其他節(jié)點的個數(shù)(即該函數(shù)調用其他函數(shù)的個數(shù)),在函數(shù)動態(tài)調用關系圖中處于葉節(jié)點的函數(shù)出度值為0。出度值計算方式如下:

其中,對于節(jié)點Ni,復雜網(wǎng)絡記錄了該節(jié)點指出的鄰接節(jié)點Nj,j為節(jié)點Ni所指出的所有鄰接節(jié)點序號,n為復雜網(wǎng)絡中的節(jié)點總數(shù),OD(i)為節(jié)點Ni的出度值,oij為節(jié)點Ni是否指向節(jié)點Nj,如果節(jié)點Ni指向節(jié)點Nj,則oij= 1,否則oij= 0。

將OD值從小到大排列,若出現(xiàn)多個OD值相同的節(jié)點,則按其在輸入數(shù)據(jù)文件中的執(zhí)行次序排列,在排序后的缺陷函數(shù)候選列表中去除分析風險軌跡時已檢測過的函數(shù),生成缺陷函數(shù)候選集Tfault,在Tfault中依次檢測并定位缺陷函數(shù)。

2.2 DRC方法實現(xiàn)流程

DRC方法實現(xiàn)流程如圖2所示,其主要模塊為:1)獲取風險軌跡模塊,在執(zhí)行程序時動態(tài)輸入測試用例集,獲取運行過程中的函數(shù)調用序列,為待測程序找出目標序列和可疑序列,對比找出風險軌跡;2)分析風險軌跡模塊,主要對風險軌跡的異常信息進行分析,提取可疑函數(shù)集;3)定位缺陷函數(shù)模塊,檢測可疑函數(shù)集并直接定位缺陷函數(shù),或者針對風險軌跡模塊定位不足的問題,融合復雜網(wǎng)絡相關度量進行二次定位,最終定位缺陷函數(shù)。

圖2 DRC方法流程

DRC方法實現(xiàn)步驟具體如下:

步驟1獲取函數(shù)調用序列。將待測程序Pf和其他任一含缺陷版本的程序P′f分別與分析函數(shù)一起編譯,獲取兩個調用路徑可追蹤的新程序,將設計好的測試用例集動態(tài)輸入路徑可追蹤的程序中,記錄測試結果通過或失敗。

步驟2獲取目標序列和可疑序列。在測試用例集中找出測試用例t,使得t在Pf上運行不通過,在P′f上運行通過。將t在Pf執(zhí)行過程中的函數(shù)調用序列稱為可疑序列,在P′f執(zhí)行過程中的函數(shù)調用序列稱為目標序列。

步驟3分析風險軌跡。利用Linux文本比對命令diff找出程序風險軌跡,根據(jù)diff命令在不一致處的標記類型提取可疑函數(shù)集,并依次檢測定位缺陷函數(shù)。如果可疑序列和目標序列一致,則轉到步驟4。

步驟4定位缺陷函數(shù)。如果步驟3執(zhí)行完未定位到缺陷函數(shù),將待測程序的函數(shù)調用序列作為輸入數(shù)據(jù)文件,以函數(shù)名作為節(jié)點、函數(shù)間調用關系作為邊為程序建立復雜網(wǎng)絡圖,求其節(jié)點OD值并排序,去除上一步已檢測過的函數(shù)生成缺陷函數(shù)候選集,最終定位缺陷函數(shù)。

3 實例分析

下文以西門子數(shù)據(jù)集的replace(字符串匹配替換程序)測試集中6個缺陷版本程序(v1和v2、v7和v8、v20和v21)為例,具體說明DRC方法的實現(xiàn)過程。

將以上版本程序分別與分析函數(shù)進行編譯,獲取對應調用路徑可追蹤的程序,將測試集提供的測試用例動態(tài)傳入路徑可追蹤的程序并記錄測試結果(通過或失敗),可獲得多組函數(shù)調用序列。為方便統(tǒng)計本文實驗在相鄰缺陷版本程序中找到待測程序目標序列,例如,若要檢測v1版本中的缺陷函數(shù),則要在v2版本找到目標序列。目標序列和可疑序列所對應的測試用例不唯一,只需找出一個測試用例即可。在v1和v2、v7和v8、v20和v21中,在測試用例集中找到符合條件的第一個測試用例分別為t205、t29和t290。

若要檢測v1的缺陷函數(shù),首先將測試用例t205傳入v1和相鄰版本v2中,分別獲取可疑序列和目標序列,然后用diff進行分析比對,找出風險軌跡。如圖3所示,[label="xcalls"]表示函數(shù)間調用x次。分析風險軌跡,根據(jù)異常標記,忽略序列調用時間順序異常,提取可疑函數(shù)集Tsuspect={dodash,subline,amatch,patsize},按可疑函數(shù)候選集中次序依次檢測,檢測第1次就定位出缺陷函數(shù),即定位成功。

圖3 diff標記的v1和v2調用序列結果

若要檢測v7的缺陷函數(shù),首先將測試用例t29傳入v7和相鄰版本v8中,分別獲取可疑序列和目標序列。然后用diff進行分析比對,找出風險軌跡。如圖4所示,分析風險軌跡,根據(jù)異常標記,忽略main函數(shù)異常,提取可疑函數(shù)集Tsuspect={makepat,int_set_2,dodash,addstr},按可疑函數(shù)候選集的次序依次檢測,檢測第2次就定位出缺陷函數(shù),即定位成功。

圖4 diff標記的v7和v8調用序列結果

若要檢測v20的缺陷函數(shù),則首先將測試用例t290傳入v20和相鄰版本v21中,分別獲取可疑序列和目標序列。然后用diff進行分析比對,發(fā)現(xiàn)目標序列與可疑序列完全一樣,此時,將處理后的可疑序列文件作為數(shù)據(jù)輸入文件,在Cytoscape平臺上建立復雜網(wǎng)絡圖,求其函數(shù)節(jié)點OD值。表1是程序中各函數(shù)節(jié)點的出度值及缺陷函數(shù)檢測次序(其中“—”表示main函數(shù)無需檢測),按檢測優(yōu)先級次序檢測,檢測第2次就定位到缺陷函數(shù)。

表1 函數(shù)節(jié)點出度值及檢測優(yōu)先級

4 實驗結果與分析

4.1 實驗設置

為驗證本文方法的有效性,選用西門子套件的4個子測試集作為評測程序,基本信息如表2所示。

表2 評測程序信息

實驗程序均采用shell腳本和Python語言編寫,計算機配置為Intel(R) Core(TM) i7-8550U CPU@1.80 GHz,內存為8 GB,使用的GCC版本為5.4.0。測試執(zhí)行結果與程序集提供無缺陷程序的輸出進行比較,若一致則通過,否則為失敗。

4.2 實驗結果

為驗證本文方法的有效性,選擇同樣基于函數(shù)粒度級別的缺陷定位方法Combine和Upper與本文DRC方法進行比較。表3是在replace數(shù)據(jù)集上這3種方法的定位結果,replace數(shù)據(jù)集有30個缺陷版本的程序,由于其中1個缺陷在宏定義上,因此忽略此缺陷版本。

表3 Combine、Upper與DRC方法缺陷定位結果比較

由表3可以看出,本文方法不執(zhí)行所有測試用例,平均需執(zhí)行700個測試用例。由表4可知,定位到的缺陷函數(shù)平均檢測數(shù)少于Combine和Upper方法,且穩(wěn)定性好,定位效果優(yōu)于Combine與Upper方法。

表4 Combine、Upper與DRC方法缺陷定位性能比較

由圖5可以看出,相較于Combine和Upper方法,本文DRC方法定位效率明顯提高,僅需檢測20%的函數(shù)即可定位出90%的缺陷函數(shù),而Combine、Upper方法檢測同樣數(shù)量的函數(shù)可定位出的缺陷函數(shù)分別是69%和79%,與這兩種方法相比,缺陷定位代價分別降低了22.2%和12.5%。圖6展示了本文DRC方法在4個不同量級程序上的缺陷定位效果,結果表明,程序規(guī)模越大,該方法對缺陷的定位越有效,定位效果隨程序規(guī)模的擴大而提高,更適用于大規(guī)模程序。圖7為本文DRC方法在4種不同量級的程序上,通過分析風險軌跡和建立復雜網(wǎng)絡圖定位到的缺陷函數(shù)比例。其中,分析風險軌跡平均可以定位58%的缺陷,建立復雜網(wǎng)絡圖平均可以定位42%的缺陷。由此表明,程序缺陷在大多情況下會導致函數(shù)調用序列發(fā)生異常。

圖5 Combine、Upper和DRC方法的缺陷定位效率比較

圖6 DRC方法在不同量級程序下的缺陷定位效率

圖7 DRC方法的缺陷相關度

5 結束語

目前,基于函數(shù)粒度的缺陷定位方法大多是先統(tǒng)計程序中函數(shù)調用過程中的全信息,再結合概率論或數(shù)據(jù)挖掘的方法定位缺陷。這些方法消耗時間資源與所需測試用例數(shù)量均較多,并且將獲取的信息應用于概率論或數(shù)據(jù)挖掘中的方法較為復雜,在大型軟件中效率不高且可操作性不強。本文以函數(shù)為分析粒度進行研究,通過分析程序風險軌跡,提出對不同類型的異常序列進行可疑函數(shù)抽取的策略,并針對基于風險軌跡定位會忽略葉函數(shù)節(jié)點的缺陷,結合復雜網(wǎng)絡相關度量,定位此類缺陷。根據(jù)軟件風險軌跡異常信息給出不同異常類型的優(yōu)先級,通過對西門子測試集多個程序進行測試,并與同樣以函數(shù)為分析粒度的Combine和Upper缺陷定位方法進行對比,實驗結果表明,本文方法在節(jié)省時間資源消耗的情況下,提高了缺陷定位效率,且在大型軟件上可操作性更強。由于本文實驗程序中僅含單個錯誤,因此后續(xù)將在含多個錯誤的程序上驗證DRC方法的有效性,并且復雜網(wǎng)絡中的其他度量(如緊密度中心性、介數(shù)中心性等)在軟件缺陷定位領域的應用也將是下一步研究的重點。