一種故障傳播感知的程序故障定位方法

何加浪 孟 錦 張 琨 張 宏

(南京理工大學計算機科學與技術學院 南京 210094)

1 引言

隨著信息化的不斷深入，人們對計算機軟件的依賴不斷增強，對軟件質量的要求也越來越高；在某些關鍵領域要求軟件必須具有很高的可信性，否則很可能造成重大損失。由于軟件復雜性不斷增大，程序員花費在故障定位上的時間越來越多，這嚴重阻礙了故障的修復和軟件可信性的提升，因而軟件的快速故障定位問題就成了國內外研究的熱點。

目前的研究主要集中在基于覆蓋的故障定位(Coverage-Based Fault-Localization, CBFL)技術方面。CBFL的主要思路是利用軟件多次執行獲取成功執行的覆蓋路徑和失敗執行的覆蓋路徑，通過分析比較這兩種覆蓋路徑，計算出覆蓋路徑中各節點包含故障的可疑度，然后根據可疑度將節點進行排序輸出，程序員根據該有序序列依次檢查各節點，最終確定故障位置。Jones等人[1]提出的 Tarantula技術使用程序語句作為覆蓋節點，統計各語句在失敗測試用例中被覆蓋的相對次數與在成功測試用例中被覆蓋的相對次數，然后使用上述兩個相對次數的比值作為節點可疑度的計算值；之后，Wong等人[2]按成功和失敗的測試用例對故障的支持度不同對各測試用例進行區分，改進了文獻[1]的工作；但是基于語句的覆蓋對所有語句都要進行統計分析，計算量較大，因而文獻[3,4]使用軟件中不同位置的斷言作為節點，通過插樁技術構建覆蓋路徑，利用統計分析方法確定各斷言處的可疑度；Zhang等人[5]在此基礎上通過關鍵斷言狀態轉換技術確定故障位置，其主要思想是在失敗執行中強制改變某斷言狀態后若執行恢復正常，則認為該斷言屬于關鍵斷言，進而根據關鍵斷言確定節點可疑度。通過斷言覆蓋代替語句覆蓋，有效降低了計算量，但是由于斷言位置的確定并不能保證覆蓋到真正的故障位置，因而定全率[6]會受到很大影響。Santelices等人[7]綜合了前人的研究成果，分析比較了各種覆蓋類型的特點，指出對于不同的故障，各種覆蓋類型的故障定位技術各有優劣，因而提出了一種多類型覆蓋方法并通過實驗驗證了方法的有效性和優越性。

上述研究都是在覆蓋路徑節點相互獨立的基礎上進行的，沒有考慮故障在路徑中的傳播對可疑度的影響，因而文獻[8]考慮采用邊覆蓋代替節點覆蓋，根據邊可疑度計算節點可疑度，使節點可疑度具有捕捉故障在節點間傳播的能力；Zhao等人[9]在計算節點可疑度時考慮了節點的入邊和出邊，改進了文獻[8]方法；但此類方法存在的主要問題是所有處在故障傳播路徑當中的節點可疑度值都會偏高，因為計算是沿著故障傳播路徑進行的，有些中間節點只是參與了故障傳播，并不是故障的真正位置，因此不應參與相應計算。本文為了消除故障傳播對中間節點可疑度計算的影響，不再使用覆蓋路徑中的邊，而是直接生成具有表達故障傳播能力的虛邊(Virtual Edge, VE)來對節點可疑度進行修正，一方面解決了中間節點參與可疑度計算的問題；另一方面也降低了可疑度的計算復雜性。本文在第2節介紹了基本概念；第3節詳細描述了本文所提出的可疑度計算模型 VE-CBFL；第 4節是相關實驗和分析；最后在第5節給出結論。

2 基本概念

在程序故障定位中，目的是根據程序發生故障信息尋找程序故障位置，而故障一般是程序缺陷(bug)被觸發產生的，故障定位實際上是尋找與故障對應的缺陷所在位置，因而本文約定：在不引起混淆的情況下故障和缺陷不加區分地使用。

定義 1 基礎塊：不含有跳轉指令的順序執行的語句片段；程序中所有基礎塊組成的集合記為B={b1,b2,… ,bm}。

性質 1 在CBFL類方法中，基礎塊內的各語句的可疑度相同。這較容易理解：基礎塊內不含跳轉指令，在程序一次執行中基礎塊內的語句要么全被覆蓋，要么都不被覆蓋，因而像CBFL這類基于覆蓋信息的方法無法分辨出基礎塊內語句可疑度的差別。

圖1 示例程序的控制流圖

3 VE-CBFL描述

3.1 初始s(vi)計算

表1 s(vi)計算的算法

3.2 s(vi)的修正

程序具有很強的邏輯性，在一個基礎塊發生的故障其真正位置也許位于另外的基礎塊，例如在程序某個位置釋放了一塊空間卻在另一個位置再次使用、沒有初始化的NULL指針等。在圖1示例中，故障的真正位置在b2，然而卻發生在b5處，這樣按照前一節計算的結果s(b5) = 0 .800是最可疑的基礎塊就不能準確反映事實情況。本文思路是從可疑度最大的節點max{s(vi)}出發，判斷與其直接前驅節點是否存在故障傳播趨勢，如果存在則遞歸處理該前驅節點直到到達某個節點vo不再存在這種傳播趨勢，然后以該節點為起點，以節點max{s(vi)}為終點建立一條虛邊來修正vo的可疑度。

圖2是對示例1進行處理的結果，最終生成虛邊ve2,5對s(b2)進行修正，具體算法如表2所示，該算法首先找出初始可疑度最大的節點vmax，對于此節點存在兩種可能：

圖2 虛邊的生成

4 實驗和分析

4.1 評價指標和實驗目的

序列不包含真正的故障位置，則該輸出序列就不是完備的。

表2 s(vi)修正算法

本文實驗的目的就是要在上述評價指標的基礎上驗證本文方法能有效而快速地定位故障位置，并且與其它方法進行比較，具體從以下3個方面考慮：

(1)分析本文方法在考慮故障傳播因素時對故障定位的影響；

(2)在定準率、定全率、有效值和時間開銷方面與同類方法相比，驗證本文方法的有效性和優越性；

(3)驗證本文在表1算法中提出的壓縮空間對定全率指標的影響較小的結論。

針對第(1)，(3)兩個方面本文選取 3個程序實例：圖1示例，CDBug和DDBug[10]作為第1組實驗；第2組實驗按照程序規模選擇8個實用程序作為程序對象，具體如表3所示。

4.2 實驗結果及分析

表4是第1組程序的實驗結果。表中給出了每種方法計算出來的s(vi)值，表中黑色粗體表示故障所在基礎塊，列中的黑色圓點代表執行測試用例覆蓋的相應基礎塊。

以示例1為例，從表4中可以看出，文獻[1]和文獻[7]方法計算出可疑度最高的節點均是b5，沒有考慮到故障的傳播，獲得的可疑度不夠準確；而文獻[9]方法計算出b2可疑度高于b5，但由于b4處在故障傳播路徑中，其可疑度受到了很大影響，甚至高出了b2；本文方法(VE-CBFL)在計算初始s(vi)值時s(b5)最大，根據表2描述的算法2修正后的s(b2)'值超過s(b5)'，與預期相符。在可疑空間壓縮方面，示例1欄中的b1,b5被壓縮掉，壓縮率為33.3%；特別注意到在CDBug和DDBug欄中，盡管計算初始s(vi)值時均壓縮掉b1，但在修正時由于檢測到了b1處在故障傳播路徑中的起始位置，因而對其進行了修正，從而降低可疑空間的壓縮對定全率μ的影響。

表3 故障軟件版本相關信息

上述實例分析較好地驗證了實驗目的的(1), (3)兩個方面；更進一步地，為了驗證本文方法的有效性和優越性，按程序規模選取8個實用程序作為實驗對象，分別從定準率、定全率、有效值和時間開銷方面與同類方法相比。

從ξ的定義可知，ξ值與nC,nL兩個參數有關，故障定位方法期望nC越小越好；而對于不同的方法，nL可能不同，為了對不同方法進行準確的比較，本文分別選取nL=max_nL及作為參數，實驗結果如圖3所示，圖中軟件id 是對上述8個程序按規模進行的編號。從圖 3(a)可以看出這 4種方法隨著軟件規模的擴大，定準率都有所下降，這符合一般的軟件越復雜越難找出隱藏故障的觀點；另一方面通過曲線的比較可以看出本文方法(VE-CBFL)在定準率指標上具有一定優勢；圖3(b)是按nL= m in_nL對不同方法輸出序列進行截斷，從該圖可以看出截斷后各方法ξ值具有整體降低的趨勢，這是由ξ的定義決定的，另外在6, 8處文獻[1]和文獻[7]方法由于這種截斷都導致輸出序列不再包含故障位置，從而使相應的ξ值等于零，造成定全率的下降。

圖3 ξ比較結果

表5 定全率μ值比較

定全率反映了不同方法輸出序列的完備性，一方面期望故障定位方法輸出序列盡可能短，另一方面要求該序列盡量完備，在實際應用中可以根據不同類型程序的特點進行折中處理，具體可參考文獻[11]設置保留度閾值的思想方法，本文不再贅述。

有效值是評價故障定位方法對程序員調試程序是否有幫助的指標，本文以傳統的Ad hoc調試方法平均需要檢查的基礎塊數目的期望為基準進行比較，實驗結果如圖4所示。從圖中可以看出有效值η均大于零，這說明4種方法對程序員調試均有幫助，本文方法相對較好；但是考慮到程序員自身的調試經驗，當η比較小時對調試幫助效果已不是很明顯，從圖中曲線下降趨勢來看，本文方法對應曲線下降相對平穩，具有一定的優勢。

圖5是不同方法的時間開銷對比，從圖中可以看出隨著程序規模的擴大，各方法時間開銷都呈上升趨勢；在程序規模相對小的情況下，本文方法時間開銷相對較大；但隨著程序規模的變大，其他方法時間開銷迅速增加，而本文方法則相對緩慢；這主要是由于本文方法在計算節點可疑度時對空間進行了壓縮的原因；盡管對空間的壓縮需要消耗一定的時間，但是當程序規模很大時這種壓縮所帶來的優勢十分明顯。

5 結束語

軟件的快速故障定位是提高軟件可信性的前提條件，本文在分析了現有研究的基礎上，提出了基于故障傳播感知的故障定位方法，有效降低了由于故障的傳播性對故障定位準確性造成的影響，并給出了相關的評價指標；在此基礎上通過實驗將本文方法與前人的研究工作進行了比較，得出如下兩點結論：(1)通過對邊故障傳播趨勢的分析來修正節點可疑度是可行的，能有效提高故障定位的定準率等相關指標；(2)在計算節點可疑度前預先對可疑空間進行壓縮，可以有效減少時間開銷，并隨著軟件規模的不斷擴大效果尤為明顯，這為故障定位的快速性要求提供了保證。

本文的研究是對傳統的基于覆蓋的故障定位技術的延伸，在這方面除了需要考慮故障的傳播對故障定位準確性造成的影響之外，還有其他很多因素如代碼的缺失、多故障之間的交叉影響等需要考慮和進一步研究；另一方面如何根據具體需求和故障特點建立層次化多粒度的自適應故障定位模型也值得進一步深入研究。

圖4 有效值比較

圖5 時間開銷比較

[1] Jones J A and Harrold M J. Empirical evaluation of the tarantula automatic fault-localization technique[C]. Proc. of the 20th IEEE/ACM Conference on Automated Software Engineering, Long Beach, California, USA, December 2005:273-282.

[2] Wong W E, Debroy V, and Choi B. A family of code coverage-based heuristics for effective fault localization [J].Journal of Systems and Software, 2010, 83(2): 188-208.

[3] Liblit B, Naik M, Zheng A X,et al.. Scalable statistical bug isolation[C]. Proc. of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation,Chicago, Illinois, USA, June 2005: 15-26.

[4] Liu Chao, Fei Long, Yan Xi-feng,et al.. Statistical debugging:a hypothesis testing-based approach [J].IEEE Transactions on Software Engineering, 2006, 32(10): 831-848.

[5] Zhang Xiang-yu, Gupta N, and Gupta R. Locating faults through automated predicate switching[C]. Proc. of the 28th International Conference on Software Engineering, Shanghai,China, May 2006: 272-281.

[6] Renieris E. A research framework for software-fault localization tools[D]. [Ph.D. dissertation], Brown University,2005.

[7] Santelices R, Jones J A, Yu Y,et al.. Lightweight faultlocalization using multiple coverage types[C]. Proceedings of the 31st International Conference on Software Engineering,Vancouver, Canada, May 2009: 56-66.

[8] Zhang Zhen-yu, Chan W K, Tse T H,et al.. Capturing propagation of infected program states[C]. Proceedings of the the 7th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering (ESEC/FSE'09),Amsterdam, The Netherlands, August 2009: 43-52.

[9] Zhao Lei, Wang Li-na, Xiong Zuo-ting,et al.. Executionaware fault localization based on the control flow analysis[C].Proceedings of the First International Conference on Information Computing and Applications, Tangshan, China,October 2011: 158-165.

[10] Yu Kai, Ling Meng-xiang, Gao Qin,et al.. Locating faults using multiple spectra-specific models[C]. The 26th Symposium on Applied Computing, Taichung, March 2011:1404-1410.

[11] 柳永坡, 吳際, 金茂忠, 等. 基于貝葉斯統計推理的故障定位實驗研究[J]. 計算機研究與發展, 2010, 47(4): 707-715.Liu Yong-po, Wu Ji, Jin Mao-zhong,et al.. Experimentation study of BBN-based fault localization [J].Journal of Computer Research and Development, 2010, 47(4): 707-715.