基于風險軌跡與復雜網絡的缺陷定位方法

王曙燕,韓 雪,孫家澤

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

0 概述

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

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

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

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

1 程序風險軌跡獲取

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

1.1 函數調用序列獲取

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

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

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

圖1 函數調用序列獲取流程

1.2 風險軌跡提取

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

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

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

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

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

1.3 風險軌跡分析

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

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

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

2 DRC方法

2.1 復雜網絡圖構建

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

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

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

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

2.2 DRC方法實現流程

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

圖2 DRC方法流程

DRC方法實現步驟具體如下:

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

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

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

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

3 實例分析

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

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

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

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

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

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

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

表1 函數節點出度值及檢測優先級

4 實驗結果與分析

4.1 實驗設置

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

表2 評測程序信息

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

4.2 實驗結果

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

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

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

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

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

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

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

圖7 DRC方法的缺陷相關度

5 結束語

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