軟件故障定位關鍵技術研究綜述

黃小紅+趙逢禹

摘 要：軟件故障定位旨在利用程序信息和測試信息定位出故障語句或給出出錯語句的可疑范圍，以輔助提高軟件質量。隨著軟件結構的復雜化與軟件規模的擴大化，程序運行狀態呈指數級增長，已經無法單獨依靠手動定位技術進行故障排查。因此，越來越多的輔助定位技術應運而生。為了探索這些技術的實用性，首先介紹了傳統的故障定位技術以及近年來最新推廣的故障定位技術，然后總結了常用的測試程序集，最后提出故障定位的關鍵問題并指出了未來值得關注的研究方向。

關鍵詞：故障定位；程序調試；軟件測試；執行跟蹤；可疑代碼

DOIDOI：10.11907/rjdk.171181

中圖分類號：TP301

文獻標識碼：A 文章編號：1672-7800（2017）007-0205-05

0 引言

軟件應用的日益廣泛已深入影響到人們的生活[1-3]，尤其在許多危及安全的行業，如醫藥、航空、核能行業等，而且這種趨勢隨著軟件的復雜化而更加明顯。與此同時，也衍生了令人堪憂的軟件故障，故障的產生不僅導致經濟損失，甚至可能造成生命威脅[4]。伴隨著軟件成本的增加，超過一半的修復成本被傳遞給消費者。因此，為了降低成本、提高軟件質量，必須加強軟件故障定位的研究。

軟件調試中一個很重要的因素就是找到產生程序故障的根源，失敗問題產生的根源可能離程序展示出的位置距離很遠，例如程序崩潰或產生故障輸出時無法直接定位具體故障源。因此，軟件故障定位和軟件故障修復應運而生。相對于軟件修復，故障定位更為重要，定位是修復的必要條件。由于軟件系統規模不斷擴大，使傳統的手工定位耗時耗力，而且受軟件開發人員的思維定位，以及編碼風格、約束規范限制，可能導致無法快速有效地找到故障位置。通過引入自動化故障定位技術，可使定位效率大大提高。目前，越來越多的研究者開始致力于軟件故障定位的研究且取得了可觀的成果，本文主要對2010年以來故障定位的相關成果進行研究，以期準確把握故障定位的發展方向。

1 故障定位技術

1.1 故障定位常見技術

傳統的故障定位技術在簡單的小型程序中解決了軟件可靠性低的難題，提高了軟件質量，但是隨著軟件的規模化與復雜化發展，近年來不斷出現新的故障定位技術，雖然沒有任何一種技術可以適用于所有故障定位場景，但是各種技術都各具優勢。

1.1.1 基于覆蓋的故障定位技術

故障定位研究實質上是解決如何把存在故障的程序語句排名推至首位。基于覆蓋的故障定位技術較為直觀，覆蓋分析法正是采用可疑度描述來降低定位復雜度，尤其適用于一些大規模的故障定位。Wong等[6]作了如下假設：元素可疑度與被成功測試用例覆蓋次數成反比，與被失敗測試用例覆蓋次數成正比。簡而言之，如果該元素被失敗測試用例覆蓋的多，而很少被成功測試用例覆蓋，該處引發故障的可能性則很大；Jones等[5]基于同樣的思想提出利用覆蓋信息和測試信息定位錯誤，并開發了可視化工具Tarantula；Xie等[7]提出了集合理論的分析框架，之后又通過蛻變技術將軟件測試分析技術集成到故障定位中[8]，反映了更加真實的場景。其不足之處是測試用例的數量、質量限制了覆蓋的全面性，而且如果用例數量過少，覆蓋不全面，或者用例質量差，大量測試用例重復覆蓋相同代碼，將產生大量冗余覆蓋，從而導致故障定位的精準度降低[9]。

1.1.2 基于程序切片的故障定位技術

程序切片技術將程序抽象化，通過刪除不相關的部分將程序用切片表示，切片保留原始程序的行為規范。程序切片技術包括靜態切片技術和動態切片技術。靜態切片技術是對源程序采取靜態分析技術，利用語句之間的依賴關系將相關變量語句集合形成靜態切片。靜態切片技術最早由Weiser首次提出[10]，該技術主要將整個程序分為若干個切片，通過含有錯誤變量的程序切片來排除無關變量，從而縮減故障范圍。靜態切片的缺點是，片的大小可能會對給定的可執行語句帶來影響，如變量值隨著執行的改變導致切片發生變化，而且當程序規模較大時，算法時間開銷會很大。因此，Zhang等[11]提出了多種動態切片技術，包括后向動態切片（BWS）、前向動態切片（FWS）和雙向動態切片（BIS）。BWS通過執行語句輸出而捕捉故障變量的值；FWS通過計算成功用例的最小輸入觸發故障所在位置；BIS通過確定失敗執行用例的謂詞執行情況，生成正確的輸出，從而找到故障所在位置。

1.1.3 基于程序頻譜的故障定位技術

基于頻譜分析進行故障定位的方法簡單而言是根據測試用例集合運行完成后的記錄信息，使用風險評估方法對程序中的每一行語句計算故障可疑度。可利用的記錄信息主要是程序執行過程中的剖面信息與測試用例是否通過的信息[31]。

表1給出了常用的符號說明作參考。

1.2 最新推廣的故障定位技術

1.2.1 基于數據挖掘的故障定位技術

基于數據挖掘的故障定位技術試圖從大量程序運行信息數據中提取相關信息，產生一個可使用的數據模型，從而達到定位效果。Cellier等[15]提出了數據挖掘的關聯規則和概念分析以協助故障定位，該技術通過語句覆蓋率之間的關系和相應的執行失敗的測試用例之間的關聯關系，測量每個規則出現的頻率，通過已給閾值篩選出滿足關聯規則的語句執行數量，生成規則點陣，最后生成一個可疑度排名來定位故障；Zhang等[16]提出一種基于數據挖掘的故障定位技術，該技術基于馬爾可夫邏輯，結合一階邏輯與加權馬爾可夫隨機域進行感知器算法學習；王鵬等[14]提出基于圖挖掘的技術，通過收集程序的執行軌跡信息構造出程序調用圖，提取頻繁邊輔助定位故障。

1.2.2 基于模型檢測的故障定位技術

基于模型檢測的故障定位技術通過推導期望的程序行為模型，檢測失效執行對期望行為的違背情況，從而捕捉故障行為，主要需解決的關鍵問題是模型表達能力問題，以及模型對定位效果是否有顯著影響力，是否快速有效。Baah等[17]提出通過程序依賴圖模型研究程序的內部行為，促進了可能與故障有關語句的概率分析和推理。基于檢測的模型主要依賴模型檢查器來定位故障[18]。如果一個模型不滿足相應的程序規范（這意味著模型包含至少一個故障），模型檢查器可提供反例顯示違反規范詳情，反例并不直接指定哪些部分的模型與故障相關，但是它可以被視為一個可確定因果關系的失敗測試用例。宗芳芳等[20]提出二次定位策略技術，首先從程序中抽象出函數調用圖，用基于模型的方法對可能存在故障的函數進行可疑排序，最后利用DStar定位函數中故障的代碼行；Wotawa等[19]利用約束求解的技術將程序自動編譯成一組約束，實現模型檢測定位，優點是減少了可疑語句的搜索域范圍，缺點是不同程序往往具有不同的異常行為。因此，并沒有一個完整的模型可以滿足所有可能的故障模式以及故障類型之間的關聯。endprint

1.2.3 其它故障定位技術

除了上面討論的技術之外，近年來還出現了很多其它的軟件故障定位技術。Souza等[21]提出使用覆蓋率數據集成技術來定位故障，通過創建可疑語句排名列表的技術進行定位。以信息檢索技術為切入點的研究也取得了很多新的研究成果[22-23，25]。這些研究使用基于源代碼的搜索得到故障相關報告的降序等級排列，可以幫助開發人員檢查被標注的文件是否包含故障。算法調試也是一個創新性的故障定位技術，Silva[25]提出將復雜計算分解為一系列子計算幫助故障定位。公式故障定位技術[26-29]則依賴于對編碼失敗的程序公式執行軌跡跟蹤，該技術使用特定工具或算法公式幫助程序員捕捉導致失敗的相關語句。

2 主流程序集

表2總結了當前在故障定位研究中常用的程序集，分別從各程序集的名稱、代碼行數、簡述以及語言類型作簡要展示，程序集多來源于SIR[32]和SourceForge[33]。

表2展示了故障定位中常用的程序集，設計各個方面的程序測試，其中的Siemens程序集是最常用的程序集，該程序集由7個程序組成，程序結構多樣化，通用性較強，但是每個子程序僅有不到600行代碼（不包括空白行），而且是針對C語言程序定位的，因此后續出現了grep、flex等數萬行代碼的程序集，而且新增了Java和C++語言，極大地方便了各種語言下的定位應用。

3 未來研究方向展望

現有的故障定位技術已取得了不少研究成果，但是還有很多結果有待完善，如多故障定位技術[35-36]、測試用例套件質量[37-38]以及巧合正確性帶來的影響[39]。

3.1 多故障定位

對于故障數量及其相關性有幾個常見假設，這些假設往往基于某種技術效果顯而易見，但是換一種定位技術或者換一種實驗程序集則不奏效，常見假設如下：①假設程序只有一個故障。實際應用中程序通常包含多個故障，因此需質疑基于單個故障場景的定位效果，并盡量研究多故障并存下的故障定位效果；②假設即使程序中有多個故障，這些故障也都獨立執行。這一假設也在近年的研究中被質疑，因為同一個程序的不同故障很有可能相互作用，相長作用的結果往往會觸發新故障，相消作用的結果則往往掩蓋掉已有的故障；③假設調試一輪即能找到一個故障。通常程序經過一次調試后被程序員修復了一個故障，然而再次運行修改之后的程序不能保證不會對其它故障造成影響，因此被改動之后的程序往往不能當作測試用例集中的一員再次運行，而是要重新啟動其它測試用例。

3.2 測試用例套件

常見的定位技術多用于測試用例的執行狀態，如執行成功狀態或者執行失敗狀態來討論對應計數所需尋找的信息，關注點幾乎都在測試用例的執行結果上。因此，一個良好的測試用例套件對程序的有效定位具有重要意義。關于測試用例套件重要性的表現如下：

（1） 測試用例套件會影響故障定位技術的有效性。實驗證明，現階段采用的同時關注多條測試用例取得的定位效果往往要高于僅關注導致程序出現故障的一條失敗測試用例和多條成功測試用例的效果，因為在多條測試用例的對比下，可以提供更加詳細的故障線索。因此，如何生成一個自動化的測試用例套件仍然需要進一步探討。

（2） 不能實現高覆蓋的測試用例套件對目標程序的故障定位結果可能造成不利影響。為了減少這類影響，可用禁忌搜索技術自動生成一個測試用例套件，以達到最大的分支覆蓋或者對原始測試用例集約簡后，確保原有故障定位的準確性并保持較高約簡比。

（3） 對給定的被測程序使用全套測試用例未必有效。如果合理減少測試用例數量，選擇測試用例子集或者給其分配一定的優先級，可能定位效率更高。分配測試用例優先級的技術是給予導致執行失敗的測試用例優先執行，因為這樣可以提供更多信息，減少搜索域。

3.3 巧合正確性

巧合正確性即在各種程序狀態下，本來執行結果失敗的測試用例由于特殊原因導致執行結果仍然是正確的。這種現象發生的原因很多，例如給定一個存在故障的語句，對語句變量分配不正確的值，測試執行過程中，該值可能會影響程序的輸出導致失敗。然而在測試不斷執行的過程中，該變量的值可能因為被覆蓋而未影響到程序輸出，或者根本沒有觸發到故障所在的位置，因此在實際操作中要考慮巧合正確性的存在，以減少定位誤差。

4 結語

隨著軟件結構復雜化與軟件規模的擴大化，軟件故障定位需要更多的時間投資和資源投資，定位程序故障不再是簡單的機械過程，而是朝著自動化、智能化的方向發展。在以往的實踐中，對軟件的調試工作往往由具有豐富經驗的程序員手動調試，如果判斷失誤，則采用回退技術返回起點再次調試，這種機械枯燥的操作使程序員急切需要一種能快速有效定位的技術。當務之急是將定位技術融入到實際應用中，結合新興技術的發展趨勢以及程序員的經驗和應用能力，根據特定場景應用相應的定位技術。本文梳理了當前的最新定位研究成果，分析了常見的以及最新流行的定位技術和當前的主流程序集，最后針對當前出現的主要問題，提出了若干值得研究的方向。

參考文獻：

[1] SCHOOOP G，LAMINA J.On the effectiveness of the tarantula fault localization technique for different fault classes[J].IEEE International Symposium on High-assurance Systems Engineering，2011，69（5）：317-324.

[2] 王勇.軟件過程資產庫的研究與實現[J].計算機應用與軟件，2016（7）：106-108.

[3] ZHOU X，WANG H，ZHAO J.A fault-localization approach based on the coincidental correctness probability[C].IEEE International Conference on Software Quality，Reliability and Security，2015.endprint

[4] WRIGHT C S，ZIA T A.A quantitative analysis into the economics of correcting software bugs[C].Computational Intelligence in Security for Information Systems，International Conference，Held at Iwann 2011，Torremolinos-Málaga，Spain，2011：198-205.

[5] JONES J A，HARROLD M J，STASKO J.Visualization of test information to assist fault localization[C].Proceedings of the 24th International Conference on Software Engineering，IEEE Computer Society，2002：467-477.

[6] WONG W E，DEBROY V，GAO R，et al.The DStar method for effective software fault localization[J].IEEE Transactions on Reliability，2014，63（1）：290-308.

[7] XIE X，CHEN T Y，KUO F C，et al.A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization[J].Acm Transactions on Software Engineering & Methodology，2013，22（4）：402-418.

[8] KAVITHA P.An integrated method for program proving，testing and debugging[J].Middle East Journal of Scientific Research，2014，20（12）：2310-2315.

[9] JIANG B，CHAN W K，TSEe T H.On practical adequate test suites for integrated test case prioritization and fault localization[C].International Conference on Quality Software.IEEE Computer Society，2011：21-30.

[10] WEISER M D.Program slices： formal，psychological，and practical investigations of an automatic program abstraction method[M].University of Michigan，1979.

[11] ZHANG X，NEELAM G，RAJIV G.Locating faulty code by multiple points slicing[J].Software Practice & Experience，2007，37（9）：935-961.

[12] KOREL B.PELAS-program error-locating assistant system[J].IEEE Transactions on Software Engineering，1988，14（9）：1253-1260.

[13] KOREL B，LASKI J.STAD-a system for testing and debugging： user perspective[C].The Workshop on Software Testing，1988：13-20.

[14] 楊書新，徐麗萍，王鵬.基于圖挖掘和決策樹的軟件故障定位研究[J].計算機工程與應用，2015，51（20）：67-71.

[15] DUCASSé M，FERRé S，RIDOUX O，et al.Multiple fault localization with data mining[J].Seke，2011.

[16] ZHANG S，ZHANG C.Software bug localization with markov logic[C].Companion Proceedings of the 36th International Conference on Software Engineering.ACM，2014：424-427.

[17] BAAH G K，PODURSKI A，HARROLD M J.The probabilistic program dependence graph and its application to fault diagnosis[J].IEEE Transactions on Software Engineering，2009，36（4）：528-545.

[18] GRIESMAYER A，STABER S，BLOEM R.Fault localization using a model checker[J].Software Testing Verification & Reliability，2010，20（2）：149-173.

[19] NICA M，NICA S，WOTAWA F.On the use of mutations and testing for debugging[J].Software Practice & Experience，2013（43）：1121-1142.endprint

[20] 宗芳芳，黃鴻云，丁佐華.基于二次定位策略的軟件故障定位[J].軟件學報，2016（8）：1993-2007.

[21] DE SOUZA H A，LORDELLO CHAIM M.Adding context to fault localization with integration coverage[C].Ieee/acm，International Conference on Automated Software Engineering，2013：628-633.

[22] RAO S，KAK A.Retrieval from software libraries for bug localization： a comparative study of generic and composite text models[C].International Working Conference on Mining Software Repositories，MSR.2011：43-52.

[23] SAHA R K，LEASE M，KHURSHID S，et al.Improving bug localization using structured information retrieval[C].Ieee/acm，International Conference on Automated Software Engineering.2013：345-355.

[24] ZHOU J，ZHANG H，LO D.Where should the bugs be fixed？ more accurate information retrieval-based bug localization based on bug reports[C].International Conference on Software Engineering，2012：14-24.

[25] SILVA J.A survey on algorithmic debugging strategies[J].Advances in Engineering Software，2011，42（11）：976-991.

[26] CHRIST J，ERMIS E，SCHF M，et al.Flow-sensitive fault localization[M].Verification，Model Checking，and Abstract Interpretation.Springer Berlin Heidelberg，2013：189-208.

[27] ERMIS E，SCHF M，WIES T.Error invariants[M].FM 2012： Formal Methods.Springer Berlin Heidelberg，2012：187-201.

[28] 施小燕.基于條件概率公式的故障定位問題研究[D].南京：南京大學，2013.

[29] JOSE M，MAJUMDAR R.Cause clue clauses： error localization using maximum satisfiability[J].Acm Sigplan Notices，2011，46（6）：437-446.

[30] RENIERES M，REISS S P.Fault localization with nearest neighbor queries[C].IEEE International Conference on Automated Software Engineering，2003：30-39.

[31] 黃燕勤.有關基于頻譜和聚類方法定位故障的實證研究[D].南京：南京大學，2015.

[32] Software-artifact infrastructure repository[EB/OL]http：//sir.unl.edu/portal/index.html.

[33] Sourceforge[EB/OL]http：//sourceforge.net.

[34] LUCIA，THUNG F，LO D，et al.Are faults localizable[C].IEEE Working Conference on Mining Software Repositories，2012：74-77.

[35] DIGIUSEPPE N，JONES J A.On the influence of multiple faults on coverage-based fault localization[C].International Symposium on Software Testing and Analysis.ACM，2011：556-559.

[36] ARTZI S，DOLBY J，TIP F，et al.Practical fault localization for dynamic web applications[C].ACM/IEEE，International Conference on Software Engineering.IEEE，2010：265-274.

[37] JIANG B，CHAN W K，TSE T H.On practical adequate test suites for integrated test case prioritization and fault localization[C].International Conference on Quality Software.IEEE Computer Society，2011：21-30.

[38] ZHANG Z，CHAN W K，TSE T H.Fault localization based only on failed runs[J].Computer，2012，45（6）：64-71.

[39] MASRI W，ASSI R A.Cleansing test suites from coincidental correctness to enhance fault-localization[C].International Conference on Software Testing，Verification and Validation，ICST 2010，Paris，France，2010：165-174.endprint