陳偉

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

動態(tài)程序分析技術(shù)在錯誤定位中的應用

陳偉

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

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

程序分析；錯誤定位；軟件調(diào)試；程序依賴關(guān)系

0 引言

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

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

1 文獻計量分析

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

1.1 檢索方案

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

1.2 結(jié)果分析

（1）年限分析

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

（2）期刊分布和載文比

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

（3）期刊類型分布

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

（4）作者分析

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

（5）關(guān)鍵詞分析

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

2 基于動態(tài)分析的錯誤定位方法

2.1 輕量級錯誤定位方法

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

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

①基于語句或基本塊

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

②基于謂詞

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

③基于方法

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

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

①基于統(tǒng)計模型

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

②基于時間頻譜模型

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

③基于程序狀態(tài)模型

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

④基于其他行為模型

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

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

2.2 重量級錯誤定位方法

重量級錯誤定位方法需要分析程序?qū)嶓w之間的依賴關(guān)系，包括數(shù)據(jù)依賴、控制依賴以及其他依賴關(guān)系，于此同時，相對輕量級錯誤定位方法，它需要耗費更高的時間和空間代價。

（1）基于依賴關(guān)系的錯誤定位方法

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

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

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

3 結(jié)語

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

[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]寧國秀,牟永敏,申閆春,張志華.基于函數(shù)調(diào)用路徑的數(shù)據(jù)流分析錯誤定位.計算機仿真,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]王克朝,李兵,王甜甜,陳京浩.基于插樁技術(shù)的程序譜構(gòu)建方法.科學技術(shù)與工程,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]文萬志，程實.并發(fā)序列切片.科技創(chuàng)新與應用,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-），男，重慶人，碩士研究生，研究方向為嵌入式測試與開發(fā)

2016-11-24

2017-03-10