軟件故障定位關(guān)鍵技術(shù)研究綜述

黃小紅+趙逢禹

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

關(guān)鍵詞：故障定位；程序調(diào)試；軟件測試；執(zhí)行跟蹤；可疑代碼

DOIDOI：10.11907/rjdk.171181

中圖分類號：TP301

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

0 引言

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

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

1 故障定位技術(shù)

1.1 故障定位常見技術(shù)

傳統(tǒng)的故障定位技術(shù)在簡單的小型程序中解決了軟件可靠性低的難題，提高了軟件質(zhì)量，但是隨著軟件的規(guī)?；c復(fù)雜化發(fā)展，近年來不斷出現(xiàn)新的故障定位技術(shù)，雖然沒有任何一種技術(shù)可以適用于所有故障定位場景，但是各種技術(shù)都各具優(yōu)勢。

1.1.1 基于覆蓋的故障定位技術(shù)

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

1.1.2 基于程序切片的故障定位技術(shù)

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

1.1.3 基于程序頻譜的故障定位技術(shù)

基于頻譜分析進行故障定位的方法簡單而言是根據(jù)測試用例集合運行完成后的記錄信息，使用風險評估方法對程序中的每一行語句計算故障可疑度?？衫玫挠涗浶畔⒅饕浅绦驁?zhí)行過程中的剖面信息與測試用例是否通過的信息[31]。

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

1.2 最新推廣的故障定位技術(shù)

1.2.1 基于數(shù)據(jù)挖掘的故障定位技術(shù)

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

1.2.2 基于模型檢測的故障定位技術(shù)

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

1.2.3 其它故障定位技術(shù)

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

2 主流程序集

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

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

3 未來研究方向展望

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

3.1 多故障定位

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

3.2 測試用例套件

常見的定位技術(shù)多用于測試用例的執(zhí)行狀態(tài)，如執(zhí)行成功狀態(tài)或者執(zhí)行失敗狀態(tài)來討論對應(yīng)計數(shù)所需尋找的信息，關(guān)注點幾乎都在測試用例的執(zhí)行結(jié)果上。因此，一個良好的測試用例套件對程序的有效定位具有重要意義。關(guān)于測試用例套件重要性的表現(xiàn)如下：

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

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

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

3.3 巧合正確性

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

4 結(jié)語

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

參考文獻：

[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] 王勇.軟件過程資產(chǎn)庫的研究與實現(xiàn)[J].計算機應(yīng)用與軟件，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].計算機工程與應(yīng)用，2015，51（20）：67-71.

[15] DUCASSé M，F(xiàn)ERRé 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] 黃燕勤.有關(guān)基于頻譜和聚類方法定位故障的實證研究[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，F(xiàn)rance，2010：165-174.endprint