基于變異的軟件錯誤定位方法研究綜述

遲洋　蘇小紅　王甜甜

摘要：軟件調試橫跨整個軟件開發周期，而錯誤定位是軟件調試中最困難、最耗時的任務之一。針對軟件自動化調試的需求和應用背景，本文介紹了變異分析以及錯誤定位相關的國內外研究現狀，選擇了具有較高的錯誤定位精度的基于變異分析的軟件錯誤定位方法進行研究，并對已有的基于變異分析的軟件錯誤定位方法做出了分析和比較。最后，對未來的研究方向進行了展望。

關鍵詞： 軟件調試； 變異分析； 錯誤定位

中圖分類號： TP311

文獻標志碼： A

文章編號： 2095-2163（2017）05-0157-05

Abstract： Software debugging is across the entire software development cycle， and faultlocalization is one of the most difficult and timeconsuming task in software debugging. For automatic software debugging requirements and application background， this paper analyses the research status of mutation analysis and fault location in China and abroad； after that， chooses to study the mutaitonbased fault localization as it has higher fault location accuracy. Then the paper makes the detailed analyses and comparisons on previous researches of mutaitonbased fault localization. At last， the paper looks into the research priorities in future.

Keywords： software debugging； mutation analysis； fault localization[HK][HJ]

0 引言

錯誤定位是指有效識別導致程序測試執行失敗的缺陷或問題，以定位軟件中的錯誤代碼為目的，可通過在待測程序上運行合適的測試用例，分析并定位錯誤語句。這一過程通常需要人為理解待測程序的復雜的內部邏輯，以及辨識通過和失敗的測試之間的不同原因，因此錯誤定位技術是軟件調試中最具挑戰性與開拓性，且對操作人員要求達到高等技能水平的任務之一。由于人為進行錯誤定位開銷巨大[1]，自動化、高效可靠、且精準可達的錯誤定位方法研究工作則具有重大的理論意義和實用價值。

然而，雖然軟件測試是減少軟件錯誤、提高軟件質量的一種重要手段，但是因為程序中的某些語句或分支僅在一些極端情況或滿足特定條件時才能執行，同時某些影響程序的環境因素又往往是不可預見的，所以完備的測試幾乎是不可能的，也是不現實的。隨著軟件規模越來越大、邏輯越來越復雜，測試有時很難覆蓋程序中所有可能的執行分支，以致幾乎不可能在程序測試過程中發現所有的問題。另外，雖然目前已有很多自動化軟件測試工具，軟件調試卻大多采用設置斷點等人工分析的方法，人工定位錯誤不僅極其耗時，而要準確定位軟件中的錯誤則更是需要對其現存各種困難的長足突破。因此，如何有效檢測并快速準確地定位軟件錯誤，即已成為目前亟需解決的一個重要的科學問題。

[JP2]迄今為止，已有很多不同的軟件錯誤定位方法，例如基于語句覆蓋的方法、基于程序狀態的方法和基于程序依賴關系的方法等等。其中，基于語句覆蓋的錯誤定位方法[1]（Coverage-based Fault Location， CBFL）得到了廣泛的研究，該方法通過在待測程序上運行一個測試套件，程序譜，也就是研究項目實體（程序語句[2-4]或程序分支[5]）的覆蓋情況，以及記錄測試用例執行結果（成功，或失敗）。這種錯誤定位技術根據覆蓋情況可為每個實體計算可疑度作為其可能是一個錯誤的衡定依據。實體可疑度從高到低排序形成一個列表從而提供給開發人員用于定位錯誤實體。基于程序譜（語句覆蓋）的錯誤定位方法研究主要集中在設計新的可疑度計算公式[6-9]，進行公式最優化的理論分析和公式的層次結構的分析[10-12]等方面。然而，這里所指的程序譜，僅僅是待測程序控制流和測試用例執行結果的結合，由于高度依賴測試用例在程序語句上的覆蓋信息，對其準確性也存在著一定質疑[13]。隨著錯誤定位研究的不斷發展，提高錯誤定位的精度吸引了廣泛的關注。因此，如何在已有的錯誤定位方法的基礎上，尋找一種新的精確而穩定的錯誤定位方法輔助開發人員尋找軟件錯誤并對錯誤進行修復，不僅僅是一個值得研究的問題，同時更對于提高軟件質量、降低軟件維護的成本、縮減人為開銷、實現軟件的自動化調試與維護，具有至關重要的科學意義和使用價值。

[JP2]考慮到測試和錯誤定位，超過二十年的變異測試領域的研究和實驗表明，通過在程序上使用變異算子模擬人為錯誤，相比于傳統的測試選擇標準（如基于代碼覆蓋）可以有效檢測未知的、真實的錯誤，這種方法因此而被稱為基于變異分析的錯誤定位方法[14]（Mutation-based Fault Location， MBFL）。該方法通過變異體模擬人為錯誤，并通過其執行結果利用公式揭示出來以達到錯誤定位的目的，能夠更為準確地定位出程序的錯誤語句。這一方法也為錯誤定位領域提供了一個良好的開端方向，對錯誤定位領域的發展必將發揮預期理想的推動作用。

本文通過對已有文獻成果的研究和分析，總結了變異分析以及錯誤定位相關的國內外研究現狀，并對已有的基于變異分析的軟件錯誤定位方法做出了分析和比較。最后，對未來的研究方向進行了展望。endprint

[BT4]1軟件錯誤定位方法的研究

[HT5”SS][ST5”BZ]

[JP2]由于自動化錯誤定位技術具有重要的科學意義和研究價值，人們在錯誤定位領域開展了大量的研究。主要的方法包括，基于程序狀態修改的方法[15-16]、基于程序依賴分析的方法[17]、基于程序切片的方法[18]以及基于語句覆蓋的方法[1]等。在此，針對各類方法，將逐一給出實現原理概述如下。

首先，基于程序狀態修改的方法就是通過修改狀態識別程序錯誤，定位效果較好，但由于其復雜度較高，對于較大規模的程序定位效率并不理想，且對程序狀態進行修改，[JP3]容易導致無法預估的后果，如程序崩潰或陷入死循環等，錯誤定位的效果并不穩定，因而該方法在近幾年涌現的研究成果頗為少見。

其次，基于程序依賴分析的方法是使用程序實體間的依賴關系，給出可疑語句的集合并形成可供程序員理解的調試上下文。這類方法考慮了程序實體間的相互影響和依賴關系，在理論上更為全面、也更深入，定位效果堪稱良好。但該方法計算復雜度結果居高，且開銷巨大，同時調試信息通常又會過于繁瑣，包含冗余，增加了定位的難度。

接著，基于程序切片的方法通過將程序劃分簡化成程序切片，將定位的范圍縮小到切片級別，該方法定位較為準確，所需測試用例較少，但無法提供程序語句可疑程度的描述，且在大量的程序切片中觀察程序行為的開銷較大，時間和空間復雜度均會較高。

最后，基于語句覆蓋的方法主要是分析程序執行時每條語句的覆蓋信息，根據成功和失敗測試用例對程序語句的覆蓋情況利用公式計算可疑度，如Jones和Harrold[2，19]提出的Tarantula方法、Abreu[20]等提出的Ochiai方法以及Jaccard

基于語句覆蓋的錯誤定位方法依賴待測程序控制流和測試用例的覆蓋信息，易于實現且容易理解，往往能夠得到理想的結果。但該方法未考慮到程序控制流對程序的影響，對于謂詞類型的錯誤不能達到有效定位；同時，因其未能處理巧合正確性的測試用例，使得定位的有效性和穩定性必將會受到影響。[JP3]此外，由于過分依賴測試用例在程序語句上的覆蓋信息，所有在同一個基本塊中的語句會共享相同的覆蓋信息，相同的排名。這即會使得錯誤定位的精確度發生降低，程序員需要檢查的語句數量也隨之增多，因此其定位效果并不恒穩于理想狀態。

為了解決上述問題，人們提出了將變異分析與錯誤定位相結合的基于變異分析的錯誤定位方法。

2變異分析相關研究

變異分析產生于上世紀70年代[24]，是指對程序源代碼執行變異操作生成變異體，簡單實例如圖1所示，然后將測試用例在變異體上執行，獲得執行結果信息，最后結合程序結構進行分析。程序的變異可分為一階變異和高階變異，分別是指對程序設計一處和多處變異產生變異體。

變異分析最早用于變異測試，變異測試概念由DeMillo等[24]在文章中首次提出，是一種通過修改程序源碼模擬程序錯誤檢驗測試用例有效性的軟件測試方法。該方法可以有效挖掘發現測試集的缺陷和不足，測試用例殺死變異體的數量就將反映測試用例對程序變異的敏感程度，敏感程度越高，測試用例質量越高。變異測試的例子如圖2所示。相關的方法還包括Nica等[25]的研究，在其研究中，變異體被用于產生測試用例，測試套件因此而會擴大，擴大后的測試套件即可用于執行基于模型的錯誤診斷。

而后，變異分析也被用于錯誤修正，Debroy和Wong [26]提出了使用變異體來自動修復程序錯誤。該方法的基本思路是，利用基于語句覆蓋的錯誤定位技術對程序錯誤進行定位，而后對擁有最高可疑度的錯誤語句引入變異，檢查一個錯誤

語句的變異體是否能夠使所有測試用例都成功，即變異體是[CM）]否能修復錯誤。假如所有測試均顯現了成功，變異體就可稱為是錯誤程序的一個可能的修復。

3已有的基于變異分析的錯誤定位方法

使用變異體幫助軟件錯誤定位過程的想法第一次在Papadakis和Le-Traon[27]的錯誤定位研究中提出，稱為基于變異分析的錯誤定位方法（Mutation-based Fault Location， MBFL），并開發出工具Metallaxis-FL。該方法主要依賴變異體間的相似性來探測未知錯誤。其總體思路是，對待測程序進行變異處理生成變異體，執行測試用例，將執行結果與源程序測試結果構建特征比較，獲得變異體可疑度，揭示與變異體在相同位置的程序語句的可疑度，判斷錯誤語句的可能位置。

基于變異分析的錯誤定位方法舉例如圖3所示，圖中“√”表示變異體被測試用例殺死，F-Cov項中“X”表示被失敗測試用例覆蓋，“P，F”表示成功和失敗測試用例，“#P，#F”分別表示殺死變異體的成功和失敗測試用例數量，“M-Sup，S-Sup”表示變異體和語句的可疑度，“Rank”為語句可疑度排名。待測程序的錯誤為（Line7： m=x -> m=y），Mutation列給出了各目標語句的不同變異體（一階變異后的完整程序），這些變異體依次執行6個測試用例得出是否被殺死的結果，統計每個變異體被失敗測試用例殺死的次數failed（e）、被成功測試用例殺死的次數passed（e）和總的失敗測試用例數量totfailed這3個數據帶入Ochiai公式計算每個變異體的可疑度，語句的變異體中可疑度最高的值作為語句的可疑度，并排序。此時，根據Ochiai公式，Line7的變異體可疑度是0.71，排名最高，與實際錯誤語句位置吻合。

Papadakis等[27]使用Siemens套件作為評測數據集，實驗結果表明，Metallaxis-FL能夠精確有效地進行錯誤定位，且明顯優于其他基于語句覆蓋的錯誤定位工具。使用該方法實現錯誤定位不會導致有多條語句出現相同的排名，而且Metallaxis-FL擁有捕獲數據流信息的能力，能區分屬于同一基本塊的程序語句，因此這一方法不依賴于程序結構。錯誤定位過程是在測試過程之后，使其能夠充分利用測試過程的信息。此外，等價變異體也不會對錯誤定位造成影響。使用這一方法計算程序語句可疑度比以往的基于覆蓋的錯誤定位方法更加精確，但缺點卻是變異體數量過多，執行開銷較大。endprint

另一方面，類似地，Zhang等[4]使用變異分析來鑒別程序員提交的一系列源代碼庫中的包含錯誤的代碼：該方法是基于同一個位置的變異可能會導致相似的行為并產生相似的結果這一思想。這一思想為MBFL的發展提供了方向，具有重大意義。但程序變異會產生大量的變異體，這將使得變異體的執行開銷巨大，錯誤定位效率低。

受程序自動修復技術的啟發，Seikhyeon[28]等提出了一種基于變異分析的錯誤定位技術（MUtation-baSEd fault localization technique， MUSE），由于測試用例具有探測錯誤的能力，因此變異分析對錯誤定位也可提供積極作用，MUSE通過變異體模擬不同的程序行為，并提出了揭示這些變異體之間不同的度量，根據這一度量計算語句包含錯誤的概率。此外，研究還設計了一種錯誤定位方法的評估策略LIL，通過LIL分數更好地評估錯誤定位方法的有效性。評測時，使用的實驗測試數據是Unix程序，包括flex、grep、gzip、sed、space，結果表明，MUSE的表現要勝過Op2、Tarantula、Ochiai等 CBFL度量[10]。雖然MUSE與MBFL一樣都是采用了變異算子來影響程序行為，但MBFL更多地主要是集中在通過測試套件執行變異體來展現類似的程序行為，因此MBFL與MUSE并不完全相同。由于變異算子具有顯著的多樣性，基于變異分析的方法如MUSE的缺點則是不能像CBFL那樣自然地產生理論分析[11]。

近來，Gong P等[29]提出使用一種動態變異執行策略來降低MBFL的執行開銷，該方法首先變異程序語句生成有效變異體，然后在變異體上啟動實現測試用例時，為了降低在大量變異體上執行測試用例的開銷，采用了由變異體執行優化（Mutation Execution Optimization Strategy，MEO）和測試用例執行優化（Test Cases Execution Optimization Strategy，TEO）這2種優化構成的變異執行策略。MEO的思想是基于語句所有變異體中的最大可疑度值被分配為該語句的可疑度值，因此只需要得到最高可疑度，盡量減少會得到較低可疑度的執行即可。TEO的思想是可殺死語句s的一個變異體的測試用例可能也會殺死s的其他變異體。記錄測試用例t殺死變異體的情況history，優先執行能殺死更多變異體的測試用例，可以削減不必要的測試用例在變異體上的運轉流程。相關的實驗測試數據集為Siemens測試套件，結果表明，這一優化策略能有效降低開銷且不損失精度。

[BT4]4研究展望

從目前已有的研究來看，雖然基于變異分析的錯誤定位方法定位錯誤的精度較高，但由于在計算語句可疑度之前，要執行大量的測試用例和變異體，因此變異分析成本是相當巨大的。為此預計在今后的一段時間內，如何有效降低這一開銷是研究該錯誤定位方法的主要問題。降低變異分析成本可以通過以下3個方面得到控制與實現：

1）減少變異體數量。目前普遍使用的方法是變異體抽樣，通過隨機選擇的方法選擇變異體，這一方法簡便快捷，但可能會降低錯誤定位精度；還可以采用選擇變異，可通過啟發式學習程序錯誤版本建立模型針對程序結構特征選擇有效的變異體，或根據變異體的變異得分優選變異體；或者使用高階變異，產生出融合多處變異的變異體以減少變異體數量。

2）去除冗余測試用例。由于Siemens套件等測試數據集中包含大量的測試用例，這些測試用例可能不會全部為錯誤定位做出貢獻，因此分析針對不同的程序錯誤，選擇不同的測試用例，去除那些不容易揭露錯誤的測試用例以減少測試用例的數量。

3）減少執行開銷。設計算法優化執行以減少不必要的開銷，或是采用弱編譯的方法提高程序批量執行的速度以達到運行時間上的優化；或者使用變異體模式進行變異分析，使用程序圖式編碼將變異體劃分成一元程序，其編譯和運行速度將大大提高。

5結束語

本文綜述了近年來錯誤定位領域以及變異分析領域的主要研究方法，重點介紹了幾個基于變異分析的錯誤定位方法的優缺點以及目前面臨的主要問題，最后從3個方面展望了未來的研究重點。

參考文獻

WONG W E， DEBROY V. A Survey of Software Fault Localization[R]. Dallas： University of Texas， 2009.

[2] JONES J A， HARROLD M J. Empirical evaluation of the tarantula automatic faultlocalization technique[C]Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering. Long Beach， California： ACM， 2005： 273-282.

[3] ABREU R， ZOETEWEIJ P， GEMUND A J C V. An evaluation of similarity coefficients for software fault localization[C]Pacific Rim International Symposium on Dependable Computing. Melbourne， Victoria， Australia： IEEE， 2007：39-46.

[4] ZHANG L， ZHANG L， KHURSHID S. Injecting mechanical faults to localize developer faults for evolving software[J]. Acm Sigplan Notices， 2013， 48（10）：765-784.endprint

[5] MASRI W. Fault localization based on information flow coverage[J]. Software Testing Verification & Reliability， 2010， 20（2）：121-147.

[6] [JP3]DALLMEIER V， LINDIG C， ZELLER A. Lightweight bug localization[JP] with AMPLE[C] International Workshop on Automated Debugging， Aadebug 2005. Monterey， California， USA：ACM， 2005：99-104.

[7] JONES J A， HARROLD M J， STASKO J T. Visualization for fault localization[C] Proceedings of Icse Workshop on Software Visualization. Toronto， Ont.， Canada：IEEE， 2001：71-75.

[8] WONG W E， QI Y， ZHAO L， et al. Effective fault localization using code coverage[C] International Computer Software & Applications Conference. Beijing， China： IEEE， 2007：449-456.

[9] [JP3]YOO S. Evolving human competitive spectrabased fault localisation[JP] techniques[C] International Conference on Search Based Software Engineering. Riva Del Garda， Italy： Springer-Verlag， 2012：244-258.

[10]NAISH L， HUA J L， RAMAMOHANARAO K. A model for spectrabased software diagnosis[J]. Acm Transactions on Software Engineering & Methodology，2011， 20（3）：563-574.

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

[12]XIE X， KUO F C， CHEN T Y，et al. Provably Optimal and HumanCompetitive Results in SBSE for Spectrum Based Fault Localisation[M] RUHE G， ZHANG Yuanyuan. Search Based Software Engineering. Berlin/Heidelberg： SpringerVerlag， 2013：224-238.

[13]PARNIN C， ORSO A. Are automated debugging techniques actually helping programmers？[C] International Symposium on Software Testing and Analysis. London： ACM， 2011：199-209.

[14]ANDREWS J H， BRIAND L C， LABICHE Y， et al. Using mutation analysis for assessing and comparing testing coverage criteria[J]. IEEE Transactions on Software Engineering， 2006， 32（8）：608-624.

[15]CLEVE H， ZELLER A. Locating causes of program failures[C]Proceedings of the 27th international conference on Software engineering. St. Louis， MO， USA： ACM， 2005： 342-451.

[16]CHANG C H， PAIGE R. From regular expressions to DFA's using compressed NFA's[M]APOSTOLICO A， CROCHEMORE M， GALIL Z， et al. Combinational Pattern Matching. Berlin/Heidelberg： Springer-Verlag， 1992：90-110.

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

[18]STERLING C D， OLSSON R A. Automated bug isolation via program chipping[C] International Symposium on Automated AnalysisDriven Debugging. California： ACM Press， 2005：1061-1086.

[19]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. Orlando： IEEE Computer Society， 2002：467-477.

[20]ABREU R， ZOETEWEIJ P， GEMUND A J C V. On the accuracy of spectrumbased fault localization[C] Testing： Academic and Industrial Conference Practice and Research TechniquesMutation 2007. Windsor： TAICPARTMutation， 2007：89-98.

[21]REPS T， BALL T， DAS M， et al. The use of program profiling for software maintenance with applications to the year 2000 problem[M] JAZAYERI M， SCHAUER H. Software EngineeringESEC/FSE′97. Berlin/Heidelberg：Springer， 1997：432-449.

[22]SANTELICES R， JONES J， YU Y， et al. Lightweight faultlocalization using multiple coverage types[C] International Conference on Software Engineering. Auckland： IEEE/ACM， 2009：56-66.

[23]YOO S， HARMAN M， CLARK D. Fault localization prioritization： Comparing informationtheoretic and coveragebased approaches[J]. Acm Transactions on Software Engineering & Methodology， 2013， 22（3）：96.

[24]DEMILLO R A， LIPTON R J， SAYWARD F G. Hints on test data selection： help for the practicing programmer[J]. Computer， 1978， 11（4）：34-41.

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

[26]DEBROY V， WONG W E. Using mutation to automatically suggest fixes for faulty programs[C] International Conference on Software Testing， Verification and Validation. Paris， France： ICST， 2010：65-74.

[27]PAPADAKIS M， TRAON Y L. Metallaxis-FL： mutationbased fault localization[J]. Software Testing Verification & Reliability， 2015， 25（5/7）：605-628.

[28]MOON S， KIM Y， KIM M， et al. Ask the mutants： mutating faulty programs for fault localization[C] IEEE International Conference on Software Testing， Verification， and Validation. Cleveland： IEEE Computer Society， 2014：153-162.

[29]GONG P， ZHAO R， LI Z. Faster mutationbased fault localization with a novel mutation execution strategy[C] IEEE Eighth International Conference on Software Testing， Verification and Validation Workshops. Graz： IEEE， 2015：1-10.

[30]MASRI W. Fault localization based on information flow coverage[J]. Software Testing Verification & Reliability， 2010， 20（2）：121-147.endprint