動態程序分析技術在錯誤定位中的應用

陳偉

（四川大學計算機學院，成都 610065）

動態程序分析技術在錯誤定位中的應用

陳偉

（四川大學計算機學院，成都 610065）

錯誤定位是軟件調試過程中的一個關鍵問題。為了降低調試成本，輔助開發人員定位和修復程序錯誤，基于動態分析的錯誤定位技術通過選擇測試用例，運行待測程序，跟蹤并分析程序執行過程及結果，給出造成錯誤的程序缺陷在源代碼中的可能位置。歸納總結基于動態分析的錯誤定位領域的相關成就，并且從故障性質研究、多方式結合和新技術引入研究三方面展望基于動態分析的錯誤定位技術的發展趨勢，并進行總結。

程序分析；錯誤定位；軟件調試；程序依賴關系

0 引言

在工業界，為了能確保軟件的質量，他們在測試和維護中投入了不少的精力。在整個軟件開發周期中，測試和維護所需要的成本比例非常之高，而在測試和維護過程中，調試是其最困難的一部分，而錯誤定位又是調試階段中耗費最大的一步。所以，通過改進在定位過程中的任何一方面都可以在一定程度上降低調試的開銷。根據定位過程“是否需要運行軟件”為準則，錯誤定位技術可以分為基于動態的和基于靜態的，基于動態分析的錯誤定位（Dynamic Analysis-Based Fault Localization，DABFL）是指開發者設計測試用例，并根據設計的測試用例去并運行程序，然后根據程序的執行軌跡和行為特征信息給出錯誤的可能位置。

本文同時采用文件計量法和文獻綜述法，根據提出的有關該領域的幾個需要回答的問題，然后確定關鍵字以及檢索策略進行文獻檢索，接著根據篩選原則對檢索得到的論文進行篩選，然后對篩選過后剩下的論文進行數據提取和分析，最后形成報告。然后主要對基于動態分析的錯誤定位技術所涉及到的一些方法和模型進行歸納總結，并根據現有的研究情況，對未來動態程序分析技術在錯誤定位中的應用研究趨勢進行展望。

1 文獻計量分析

文獻計量法總共分為五步：確定研究范圍、抽取樣本、界定分析單元、對分析單元做量化統計和建立反應其趨勢變化的規律總結。

1.1 檢索方案

首先確定三個研究問題：1）現有錯誤定位技術有哪些？2）動態程序分析技術在錯誤定位中的應用有哪些？3）基于動態程序分析的錯誤定位方法的研究趨勢是什么？然后確定關鍵詞：程序分析（Program Analysis）、動態程序分析（Dynamic Program Analysis）、錯誤（故障）定位（Fault Localization），接著在關鍵論文數據庫中進行文獻檢索，檢索年限為2004-2016年。然后對檢索得到的論文根據一定的原則進行篩選和去重。最后得到有關錯誤定位的文獻有200多篇，這200多篇作為文獻計量統計的輸入數據。而文獻綜述只選擇其中的一部分重要參考文獻進行綜述。我們對得到的200多篇文獻通過工具進行分析，得到了一些客觀的分析結果。

1.2 結果分析

（1）年限分析

對采集到的論文的年份、數量特征進行統計分析，可以在一定程度上根據文獻的增長情況得到近12年間關于“程序分析在錯誤定位中的應用”研究的總體研究水平和發展速度。通過分析可知，自2004年以來關于“程序分析在錯誤定位中的應用”的研究文獻數量大致呈現上升趨勢。2004至2008關于此項研究的文獻相對比較少，數量波動也不是很大；2009年數量相比2008年，論文數量增加了一倍多，然后繼續呈現一個上升的增長趨勢，一直到2016。

（2）期刊分布和載文比

論文的期刊分布和載文比可以在一定程度上反映出一段時期內該領域研究的成熟度。因此，對“程序分析在錯誤定位中的應用”研究論文的期刊分布和載文比進行統計分析可知，自2004年以來，刊載程序分析研究論文的期刊數量大致呈現逐年增長的趨勢，刊載種數的增加，說明研究涉及的領域越來越多，分布更加廣泛。

（3）期刊類型分布

對刊載論文的期刊類型分布進行分析，可以了解到“程序分析在錯誤定位中的應用”研究的主要集中在哪些類型的期刊，從另外一個方面也能看到該研究領域發展到了哪一個程度。我們對搜集到的200多篇論文進行期刊類型分布統計，得知在期刊分布上還比較分散研究論文主要集中在Conference Paper和Journal Article上，占據總論文數量的69.88%。其次是在Conference Proceeding和Thesis，分別占據22.89%和7.23%。

（4）作者分析

作者分布情況可以體現在該領域研究的廣度以及深度。作者數越多，說明該研究領域越廣，某一個作者出現的頻次越高，說明該作者在這個領域研究得比較深入。通過對搜集到的論文進行作者分布統計（包含第一作者，第二作者，第三作者），共有600多名作者參與該領域的研究，對出現頻次比較高的作者進行統計，發現Zhang,Zhenyu、Wong,W.Eric、徐寶文名列前三。

（5）關鍵詞分析

我們對搜集到的200多篇論文中的關鍵詞進行統計分析，共獲得956個關鍵詞，對這些關鍵詞進行頻度統計，按照頻次高低排序所得的前3位高頻詞的統計結果是Fault Localization、Program Debugging和Debugging。統計結果顯示，錯誤定位也叫做故障定位、錯誤診斷或缺陷定位，主要應用在程序調試程序測試中。從關鍵詞的頻度可以看出，動態程序分析技術（這里指自動化調試）主要技術是統計分析（Statistical Analysis）和程序切片分析（Program Slicing）。

2 基于動態分析的錯誤定位方法

2.1 輕量級錯誤定位方法

在輕量級錯誤定位方法中，我們只關注覆蓋信息，程序實體之間的依賴關系一般不涉及，然后使用統計方法或數據挖掘的方法進行信息的處理。根據故障定位方式等信息，輕量級錯誤定位方法可以分為基于執行覆蓋（Coverage-Based Fault Localization，CBFL）和基于模型(Model-Based Fault Localization，MBFL）兩大類。

（1）基于執行覆蓋的錯誤定位方法

①基于語句或基本塊

Renieres和Reiss[1]提出了一種程序光譜對比的錯誤定位方法，在程序測試過程中，首先假設其存在很多個成功的執行和一個失敗的執行，然后根據距離準則來選擇一個和失敗運行最相似的成功運行的程序光譜，最后根據光譜差異性來分離程序缺陷。Jones和Harrold等人[2]認為，如果一個程序實體被大部分的失敗用例執行過，那么就應該被考察，于是提出了Tarantula錯誤定位方法，于此同時，他們開發了一個工具原型，通過故障可疑度來定位錯誤。

②基于謂詞

Liblit等人[3]提出了CBI（Cooperative Bug Isolation）錯誤定位技術，也被稱為Liblit05，是一種基于謂詞覆蓋的互操作分離故障技術。該技術通過利用謂詞的真假取值，然后對比與其后某個錯誤的出現存在的關聯性，于此同時，利用插樁技術來獲取謂詞的覆蓋信息。然后，Zhang等人[4]把短路求值和求值序列考慮在內，通過分析他們之間的關系，提出了一種基于謂詞的錯誤定位方法的DES（Debugging through Evaluation Sequences）改進策略，有效地提高了錯誤定位的效率。

③基于方法

Dallmeier等人[5]認為在失敗執行中，如果某一個類調用了成功執行中不同的方法，那么是不是應該更值得被考察和懷疑，據此他們提出了一種基于方法調用序列的技術，被稱為Ample技術。寧國秀等人[6]針對C源程序提出一種基于函數調用路徑的數據流分析技術,主要分析程序中的數據流信息,他們結合程序切片，根據函數調用路徑，進一步分析數據流的變化，從而定位錯誤。

（2）基于模型的錯誤定位方法

①基于統計模型

Liu等人[7]基于參數統計中的分布函數，提出了基于統計模型SOBER的故障定位方法。該方法需要獲取謂詞在成功失敗執行中的取值模式，然后根據該取值模式進行建模，最后根據假設檢驗原理，進一步具體分析，以此量化謂詞在取值上的偏差，并將此偏差結果作為謂詞的懷疑度。Yu等人[8]進一步提出了一種錯誤的定位方法，被稱為LOUPE。它可以同時利用到多個模型，根據每個模型適用的情況，來定位不同類型的錯誤。因為錯誤類型最開始是不知道的，所以LOUPE方法通過建立了多個模型來獲取程序語句的不正常行為和狀態信息，然后從上一步獲取的信息中選出適合的模型來定位錯誤。

②基于時間頻譜模型

Yilmaz等人[9]利用時間光譜作為程序執行特征的抽象，同時運用了高斯混合模型，對成功執行的時間頻譜進行聚類分析，進而對每個類進行高斯分布建模，通過利用時間頻譜信息，查找程序函數中隱藏的錯誤，該方法被稱為TWT（Time Will Tell）方法。

③基于程序狀態模型

徐寶文等人[10]考慮了值向量，他們認為，待測系統和測試用例可以用值向量來表示，然后對其測試結果和附加測試用例的測試結果進行對比分析，進而尋找錯誤的可能位置。Delta Debugging方法是由Zeller提出的，該方法能夠自動減小程序成功和失敗運行過程之間的區別。它采用分治的思想和遞歸思想，逐漸減小兩個集合之間的差異，最終確認成功和失敗配置差異的一個最小集。

④基于其他行為模型

Guoshun，Chen等人[11]認為MAS（Multi-Agent System）具有較強的自主性和智能性，同時具有較強的社會能力，容易與軟件密集型裝備現有的軟件測試方案進行集成。于是，他們提出了一種新的基于MAS的故障診斷框架，整個錯誤診斷系統被分為四部分：System Management Agent(SMA)、Pre-Processing Agent(PPA)、Fault Localization Agent(FLA)和Failure Analysis Agent (FAA)。SMA層直接與用戶進行交互，為用戶提供軟件錯誤斬斷系統的接口，并且與Sevice Agent之間相互合作。PPA層包括了Lexical Analyzer Agent和Syntax Analyzer Agent，它主要的功能就是生成語法樹（Syntax tree）。FLA層包括Syntax Tree Analyzer Agent（STAA）和Automatic Instrumentation Agent（AIA）。STAA自動分析源代碼的儀器精確度，AIA自動接收STAA的結果，然后插入探測函數，并記錄執行信息。FAA層包括了Coverage Analyzer Agent和Query Agent，主要用來實現語句和分支覆蓋測試，并自動查詢覆蓋率是否滿足需求，程序是否為目標程序。此框架已應用與真正的軟件診斷當中，并且證明了它的有效性。

王克朝等人[12]通過利用插樁，構建了一種程序譜構建模型,通過該模型，可以明顯提高源代碼的處理效率,該模型中的有窮自動機能夠準確識別插樁點，有效提高錯誤定位的速度。通過實驗驗證，該技術可以在一定程度上提高錯誤定位的效率。

2.2 重量級錯誤定位方法

重量級錯誤定位方法需要分析程序實體之間的依賴關系，包括數據依賴、控制依賴以及其他依賴關系，于此同時，相對輕量級錯誤定位方法，它需要耗費更高的時間和空間代價。

（1）基于依賴關系的錯誤定位方法

Baah等人考慮了程序依賴圖，他們在程序依賴圖上，通過增加結點和邊的概率信息，建立了概率程序依賴圖PPDG（Probabilistic Program Dependence Graph），用來反映程序元素之間的的行為。Feng和Gupta等人[13]基于動態依賴圖建立基于貝葉斯網絡的錯誤流圖EFG （Error Flow Graph）和通用的概率模型。然后基于標準的推理算法從葉節點沿著錯誤流后向追溯尋找錯誤可能性最大的可執行語句。

（2）基于程序切片的錯誤定位方法

早前是由Weiser提出了一種被稱為程序切片的概念，它是用來描述影響程序某個執行點上特定變量的語句的集合。Zhang等人[14]提出了一種動態切片錯誤定位方法，定義切片準則，計算數據切片、全切片和相關切片，進而有效分離出錯誤相關語句，以此來達到定位錯誤的目的。另外，通過比較三種單點切片(后向切片、前向切片、雙向切片)的不同，他們還提出了一種基于多點切片的錯誤定位方法。文萬志等人[15]為了解決并發程序中數據共享錯誤定位問題，他們使用關系構造靜態并發序列切片和動態并發序列切片，來提高在程序數據共享錯誤定位上的準確率。

3 結語

軟件錯誤定位方法研究是軟件調試過程中的一個熱點問題。本文首先對該領域的文獻進行了文獻計量分析，然后從輕量級和重量級兩個角度歸納總結了現有的基于動態分析的錯誤定位方法，闡述了具有代表性的錯誤定位技術。我們發現，不涉及程序實體依賴關系，使用統計學方法對程序語句、分支、函數或類等的懷疑度進行計算并排序，進而定位錯誤的研究成果最多，而需要分析程序實體之間依賴關系的錯誤定位方法相對較少。研究者多數借助抽象和簡化來研究錯誤定位，從而忽略了故障固有的一些特性。同時采用多種方式相結合的技術也會提高錯誤定位的效率，例如動態分析和靜態分析相結合，不同方法相結合。于此同時，開發者們也開始利用數據挖掘、人工智能、機器學習和神經網絡等新技術來進行錯誤定位，在未來，這些新技術是一個發展趨勢，值得深一步的研究。

[1]M.Renieres，S.P.Reiss.Fault Localization with Nearest Neighbor Queries.in Automated Software Engineering,2003.Proceedings. 18th IEEE International Conference on,2003,pp.30-39.

[2]J.A.Jones,M.J.Harrold,J.Stasko.Visualization of Test Information to Assist Fault Localization.in Software Engineering,2002.ICSE 2002.Proceedings of the 24rd International Conference on,2002,pp.467-477.

[3]B.Liblit,M.Naik,A.X.Zheng,A.Aiken,M.I.Jordan.Scalable Statistical Bug Isolation.in ACM SIGPLAN Notices,2005：15-26.

[4]Z.Zhang,B.Jiang,W.Chan,T.Tse,X.Wang.Fault Localization Through Evaluation Sequences.Journal of Systems and Software,vol. 83,pp.174-187,2010.

[5]V.Dallmeier,C.Lindig,A.Zeller.Lightweight Defect Localization for Java.in ECOOP 2005-Object-Oriented Programming,ed: Springer,2005,pp.528-550.

[6]寧國秀,牟永敏,申閆春,張志華.基于函數調用路徑的數據流分析錯誤定位.計算機仿真,2016.

[7]C.Liu,L.Fei,X.Yan,J.Han,S.P.Midkiff.Statistical Debugging:A Hypothesis Testing-Based Approach.Software Engineering, IEEE Transactions on,vol.32,pp.831-848,2006.

[8]K.Yu,M.Lin,Q.Gao,H.Zhang,X.Zhang.Locating Faults Using Multiple Spectra-Specific Models.in Proceedings of the 2011 ACM Symposium on Applied Computing,2011,pp.1404-1410.

[9]C.Yilmaz,A.Paradkar,C.Williams.Time Will Tell:Fault Localization Using Time Spectra.in Proceedings of the 30th International Conference on Software Engineering,2008：81-90.

[10]X.Baowen,N.Changhai,S.Liang,C.Huo-Wang.A Software Failure Debugging Method Based on Combinatorial Design Approach for Testing.Chinese Journal of Computers,vol.29,pp.132-138,2006.

[11]C.Guoshun,M.Sasa,X.Mingfei.A Kind of Software Fault Diagnosing Framework Based on Multi-Agent.in Quality,Reliability, Risk,Maintenance,and Safety Engineering(ICQR2MSE),2012 International Conference on,2012,pp.760-762.

[12]王克朝,李兵,王甜甜,陳京浩.基于插樁技術的程序譜構建方法.科學技術與工程,2014.

[13]M.Feng，R.Gupta.Learning Universal Probabilistic Models for Fault Localization.in Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering,2010：81-88.

[14]X.Zhang,H.He,N.Gupta,R.Gupta.Experimental Evaluation of Using Dynamic Slices for Fault Location.in Proceedings of the Sixth International Symposium on Automated Analysis-Driven Debugging,2005,pp.33-42.

[15]文萬志，程實.并發序列切片.科技創新與應用,2015.

Application of Dynamic Program Analysis Techniques in the Fault Localization

CHEN Wei
（College of Computer Science，Sichuan University，Chengdu 610065）

Fault localization is a key research topic in the software debugging.In order to reduce the cost of debugging and assist the developers to locate and repair program faults,dynamic analysis-based fault localization techniques identify possible locations of faults by selecting test case,running programs and analyzing the program’s running process and results.Summarizes the achievements in the field of dynamic analysis-based fault localization,summarizes this technique and discusses its development trend from the view of fault properties,multiple methods combination and new technique.

Program Analysis;Fault Localization;Software Debugging;Program Dependency

1007-1423（2017）05-0034-05

10.3969/j.issn.1007-1423.2017.05.009

陳偉（1991-），男，重慶人，碩士研究生，研究方向為嵌入式測試與開發

2016-11-24

2017-03-10