陳偉

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

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

陳偉

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

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

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

0 引言

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

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

1 文獻(xiàn)計(jì)量分析

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

1.1 檢索方案

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

1.2 結(jié)果分析

（1）年限分析

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

（2）期刊分布和載文比

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

（3）期刊類型分布

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

（4）作者分析

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

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

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

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

2.1 輕量級錯(cuò)誤定位方法

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

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

①基于語句或基本塊

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

②基于謂詞

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

③基于方法

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

（2）基于模型的錯(cuò)誤定位方法

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

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

②基于時(shí)間頻譜模型

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

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

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

④基于其他行為模型

Guoshun，Chen等人[11]認(rèn)為MAS（Multi-Agent System）具有較強(qiáng)的自主性和智能性，同時(shí)具有較強(qiáng)的社會能力，容易與軟件密集型裝備現(xiàn)有的軟件測試方案進(jìn)行集成。于是，他們提出了一種新的基于MAS的故障診斷框架，整個(gè)錯(cuò)誤診斷系統(tǒng)被分為四部分：System Management Agent(SMA)、Pre-Processing Agent(PPA)、Fault Localization Agent(FLA)和Failure Analysis Agent (FAA)。SMA層直接與用戶進(jìn)行交互，為用戶提供軟件錯(cuò)誤斬?cái)嘞到y(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，主要用來實(shí)現(xiàn)語句和分支覆蓋測試，并自動查詢覆蓋率是否滿足需求，程序是否為目標(biāo)程序。此框架已應(yīng)用與真正的軟件診斷當(dāng)中，并且證明了它的有效性。

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

2.2 重量級錯(cuò)誤定位方法

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

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

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

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

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

3 結(jié)語

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

2016-11-24

2017-03-10