基于程序執(zhí)行軌跡與動態(tài)切片的錯誤定位研究

孫士明, 侯秀萍, 高 燦, 孫琳琳(. 長春工業(yè)大學(xué) 計算機科學(xué)與工程學(xué)院, 長春 300； . 蘇州大學(xué) 附屬第一醫(yī)院, 江蘇 蘇州 5006)

?

基于程序執(zhí)行軌跡與動態(tài)切片的錯誤定位研究

孫士明1, 侯秀萍1, 高 燦2, 孫琳琳1
(1. 長春工業(yè)大學(xué) 計算機科學(xué)與工程學(xué)院, 長春 130012； 2. 蘇州大學(xué) 附屬第一醫(yī)院, 江蘇 蘇州 215006)

為解決程序調(diào)試過程中的錯誤定位問題, 將程序執(zhí)行軌跡和動態(tài)切片技術(shù)應(yīng)用于錯誤定位。程序執(zhí)行軌跡中包含與錯誤無關(guān)語句, 影響錯誤定位的準(zhǔn)確度。在執(zhí)行軌跡的基礎(chǔ)上, 通過使用動態(tài)切片技術(shù)降低不相關(guān)語句在錯誤定位時的影響。建立基于程序執(zhí)行軌跡和動態(tài)切片的語句懷疑度計算模型, 使用該模型計算每條語句的懷疑度, 并根據(jù)懷疑度對每條語句進(jìn)行排序, 給出查錯的推薦方案。通過實驗對比其他算法, 證明了基于程序執(zhí)行軌跡與動態(tài)切片的錯誤定位方法是有效的。

執(zhí)行軌跡; 動態(tài)切片; 懷疑度

0 引 言

軟件生命周期中的任何一個階段的程序調(diào)試都需要程序員進(jìn)行大量的人機交互[1]。為保證軟件開發(fā)的質(zhì)量, 工業(yè)界在軟件測試階段投入了大量的人力物力。據(jù)統(tǒng)計, 軟件測試約占軟件開發(fā)和維護(hù)成本的50%～75%[2], 其中最耗時、 代價最昂貴的任務(wù)之一就是程序調(diào)試[3-6], 這是指對程序錯誤進(jìn)行定位和修正的過程, 而錯誤定位又是程序調(diào)試中最耗時和困難的任務(wù)。

在程序的調(diào)試過程中, 程序員準(zhǔn)確識別導(dǎo)致程序出錯的位置稱為錯誤定位[7]。錯誤定位的有效性取決于程序員對程序的理解程度, 以及邏輯判斷能力和調(diào)試經(jīng)驗。錯誤定位研究可以分為兩部分[8]： 使用某種技術(shù)識別可能含有錯誤的代碼和程序員通過檢查識別含有錯誤的代碼。筆者研究的是識別可能含有錯誤的代碼。

1 錯誤定位方案

在錯誤定位研究過程中, 有很多種方法可以定位錯誤。常見的方法是對源程序進(jìn)行相應(yīng)的程序理解或動態(tài)跟蹤出現(xiàn)錯誤的測試用例的執(zhí)行軌跡并獲取錯誤信息, 利用人工智能的方法或統(tǒng)計的方法計算每條語句的懷疑度[9], 然后定位錯誤可能發(fā)生的位置。筆者根據(jù)程序的執(zhí)行軌跡和動態(tài)切片信息進(jìn)行錯誤定位。由于面向?qū)ο蟪绦蚓哂谐橄蟆?封裝、 繼承和多態(tài)的特性, 對于部分具有多態(tài)特性的程序, 動態(tài)切片獲取工具不能獲取準(zhǔn)確的切片[10], 如果只使用動態(tài)切片技術(shù)進(jìn)行錯誤定位, 這將導(dǎo)致動態(tài)切片中可能不會包含錯誤語句, 使錯誤定位的精度降低。含有錯誤的語句一定會在執(zhí)行軌跡中, 但執(zhí)行軌跡中包含大量與錯誤發(fā)生無關(guān)語句, 利用動態(tài)切片技術(shù)降低執(zhí)行軌跡中無關(guān)語句的影響, 又不會遺漏執(zhí)行軌跡中的錯誤語句。筆者進(jìn)行錯誤定位的流程如圖1所示。

圖1 錯誤定位流程圖Fig.1 Flow chart of fault localization

首先運行測試用例, 在運行測試用例時記錄程序的執(zhí)行軌跡和生成測試報告。分析測試報告內(nèi)容, 報告中是否含有運行失敗的測試用例, 如果沒有, 則測試結(jié)束; 如果有, 將錯誤信息和參數(shù)信息傳遞給動態(tài)切片獲取程序, 計算每個參數(shù)信息對應(yīng)的動態(tài)切片。最后利用懷疑度計算模型估計每條語句含有錯誤的可能性, 給出推薦方案, 確定錯誤發(fā)生的位置。

2 懷疑度計算模型

2.1 相關(guān)定義

錯誤定位的過程就是計算每條語句含有錯誤可能性大小的過程, 也稱作懷疑度計算。為計算懷疑度, 做如下定義。

定義1 失敗切片數(shù)mi： 由運行失敗的測試用例對應(yīng)的參數(shù)計算得出的動態(tài)切片中覆蓋到語句Si的動態(tài)切片數(shù)。

定義2 正確切片數(shù)ni： 由運行成功的測試用例對應(yīng)的參數(shù)計算得出的動態(tài)切片中覆蓋到語句Si的動態(tài)切片數(shù)。

定義3 失敗路徑數(shù)pi： 動態(tài)測試中, 測試用例運行失敗且路徑中覆蓋到語句Si的測試用例數(shù)。

定義4 正確路徑數(shù)qi： 動態(tài)測試中, 測試用例運行成功且路徑中覆蓋到語句Si的測試用例數(shù)。

定義5x： 運行失敗的測試用例總數(shù)。

定義6y： 運行成功的測試用例總數(shù)。

定義7 影響因子αi：αi是經(jīng)過動態(tài)切片后, 通過執(zhí)行Si并且運行失敗的測試用例數(shù)與總的運行失敗測試用例數(shù)的比值進(jìn)行計算, 即αi=mi/x。

定義8 影響因子βi： 是經(jīng)過動態(tài)切片后, 通過執(zhí)行Si并且運行成功的測試用例數(shù)與總的運行成功測試用例數(shù)的比值進(jìn)行計算, 即βi=ni/y。

2.2 懷疑度模型

運行成功或失敗的測試用例對判斷語句中含有錯誤均有貢獻(xiàn)[11]。對每條語句Si, 當(dāng)測試用例運行失敗且運行Si時, 則認(rèn)為語句Si含有錯誤的可能性增加; 當(dāng)測試用例運行成功且運行Si時, 則認(rèn)為語句Si含有錯誤的可能性降低。運行成功的測試用例和運行失敗的測試用例的數(shù)量不同, 運行成功的測試用例多時, 會導(dǎo)致所有的語句含有錯誤的可能性降低。所以， 不僅考慮運行成功或失敗且經(jīng)過Si的數(shù)量, 還要考慮其在總的運行成功或失敗的測試用例中所占的比例。在獲取的路徑中含有導(dǎo)致錯誤產(chǎn)生無關(guān)的語句, 為減少這些語句, 對產(chǎn)生錯誤語句中的變量做動態(tài)程序切片。通過程序切片降低不相關(guān)的語句含有錯誤的可能性。

懷疑度SSuspicious(Si), 語句Si不同時,Si中含有錯誤的可能性大小也不一樣,把這種含有錯誤的可能性定義為懷疑度, 懷疑度的計算公式如下

3 Trace & Slicing錯誤定位算法

筆者進(jìn)行錯誤定位的思想是, 先分析動態(tài)測試報告, 檢查是否有運行失敗的測試用例, 如果有運行失敗的測試用例, 根據(jù)運行過程中的錯誤信息獲取程序的動態(tài)切片， 再根據(jù)動態(tài)切片信息和執(zhí)行軌跡信息計算每條語句的懷疑度, 進(jìn)行錯誤定位。算法所使用的類之間關(guān)系的設(shè)計如圖2所示。

圖2 類關(guān)系圖Fig.2 Class diagram

在圖2中TestCase為測試用例類, 其中name為測試用例名, param為測試用例的參數(shù)信息, 該參數(shù)也作為獲取動態(tài)切片的參數(shù)。Slicing_Info為動態(tài)切片信息, 每個測試用例的參數(shù)對應(yīng)一條切片信息。Trace_Info為執(zhí)行軌跡信息, 每個測試用例對應(yīng)一項執(zhí)行軌跡信息, 該信息保存在測試報告中。Statement存儲每條語句動態(tài)切片和執(zhí)行軌跡的覆蓋信息。Suspicious_Degree為懷疑度, 其中suspicious(Statement)方法計算懷疑度, 具體計算過程根據(jù)式(1)進(jìn)行, 每條語句對應(yīng)一個懷疑度值, 根據(jù)懷疑度值的大小判斷含有錯誤可能性的大小。

3.1 算法描述

算法Trace & Slicing具體描述如下。

輸入： 測試用例集, 源程序

輸出： 查錯方案

initial TestCase, Path_Info and flag;//Path_Info數(shù)組存儲每個測試用例的路徑信息, flag標(biāo)注是否有運行失敗的用例for(inti=0;i

if(Path_Info[i].result==False){

computing dynamic slicing;∥如果有運行失敗的測試用例, 則計算對應(yīng)的動態(tài)切片

initial Statement;∥初始化每條語句的狀態(tài)

flag=true;

break;

}

flag=false;

}

if(flag){∥如果有運行失敗的測試用例, 則計算每條語句的懷疑度, 進(jìn)行錯誤定位

for(intj=0;j

Statement[j].suspicious_degree=Suspicious(Statement[j]);∥計算每條語句的懷疑度

}

sorting Statement by suspicious_degree and recommending scheme of finding fault/*根據(jù)懷疑度對語句排序并給出推薦方案*/

}

3.2 實例分析

圖3所示的程序為計算輸入的3個數(shù)的中間數(shù), 其中在第7行中正確的語句應(yīng)該是m=x, 由于誤寫成m=y, 導(dǎo)致程序存在錯誤。下面將用此例介紹如何定位錯誤發(fā)生的位置。

圖3 MiddleNum源碼圖Fig.3 Source code of MiddleNum

對圖3中的程序編寫了8個測試用例(見表1), 這8個測試用例分別選取不同的參數(shù)。T1是一組隨機數(shù),T2選取兩個相等的參數(shù),T3～T8選取3個不同大小的數(shù), 對其進(jìn)行排列組合作為測試用例的輸入?yún)?shù)。表2中的數(shù)據(jù)是根據(jù)定義2.1中的定義進(jìn)行計算的,懷疑度根據(jù)式(1)計算得出, 其計算結(jié)果如表2所示。

表1 測試用例表

表2 MiddleNum懷疑度表

(續(xù)表2)

根據(jù)懷疑度排列語句可得出如下序列

S7->S1->S2->S3->S4->S5->S8->S9->S11->S13->S14->S15->S10->S6->S12

由上面的序列可得出語句S7含有錯誤的可能性最大, 程序員查找差錯時可首先檢查語句S7是否含有錯誤。

4 對比分析

為評估所提出算法的有效性, 本節(jié)將對比Trace & Slicing算法與Tarantula[9]算法的有效性(見圖4～圖6)。Tarantula算法通過程序的執(zhí)行軌跡信息計算語句含有錯誤的可能性, 只考慮了運行成功與運行失敗的測試用例的執(zhí)行軌跡是否覆蓋了該語句, 沒有考慮不相關(guān)語句的影響。該實驗數(shù)據(jù)來自http://sir.unl.edu, 其中有XML-Security, JDepend, CheckStyle測試程序。

圖4 XML-Security錯誤定位速率Fig.4 Rate of fault localizationof XML-security

圖5 JDepend錯誤定位速率Fig.5 Rate of fault localizationof JDepend

圖6 CheckStyle錯誤定位速率Fig.6 Rate of fault localizationof CheckStyle

實驗對比了經(jīng)過錯誤定位算法計算后, 前5行推薦語句發(fā)現(xiàn)錯誤的百分比。通過圖4～圖6可以看出, Trace & Slicing算法經(jīng)過動態(tài)切片降低不相關(guān)語句的影響后, 含有錯誤語句的排列被前置。在被測試的3組數(shù)據(jù)中, Trace & Slicing比Tarantula發(fā)現(xiàn)錯誤的比例高, 并且Trace & Slicing算法能在前3行定位到約80%的錯誤。

5 結(jié) 語

測試用例的運行信息可用于錯誤定位, 并且導(dǎo)致錯誤產(chǎn)生的語句包含在用例的執(zhí)行軌跡中。執(zhí)行軌跡中含有大量與錯誤產(chǎn)生無關(guān)的語句, 檢查這些無關(guān)的語句是否含有錯誤會浪費程序員的時間。通過動態(tài)切片技術(shù)降低無關(guān)語句的影響, 使可能對錯誤產(chǎn)生有影響的語句排列提前, 有助于程序員提前發(fā)現(xiàn)錯誤。通過實驗結(jié)果證明, 筆者提出的算法提高了錯誤定位的效率。

[1]JONES J A, BOWRING F J, HARROLD M J. Debugging in Parallel [C]∥Proceedings of the 2007 International Symposium on Software Testing and Analysis (ISSTA 07). New York, NY, USA: ACM, 2007: 16-26.

[2]HAILPERN B, SANTHANAM P. Software Debugging, Testing, and Verification [J]. IBM Systems Journal, 2002, 41(1): 4-12.

[3]JONES J A. Semi-Automatic Fault Localization [D]. Atlanta, USA： Computing Department, Georgia Institute of Technology, 2008.

[4]SANTELICES R, JONES J A, YU Y, et al. Lightweight Fault-Localization Using Multiple Coverage Types [C]∥Software Engineering, 2009, ICSE 2009, IEEE 31st International Conference on. Vancouver, Canada: IEEE, 2009: 56-66.

[5]虞凱, 林夢香. 自動化軟件錯誤定位技術(shù)研究進(jìn)展 [J]. 計算機學(xué)報, 2011, 34(8): 1411-1422. YU Kai, LIN Mengxiang. Advances in Automatic Fault Localization Techniques [J]. Chinese Journal of Computers, 2011, 34(8): 1411-1422.

[6]張云乾, 鄭征, 季曉慧, 等. 基于馬爾科夫模型的軟件錯誤定位方法 [J]. 計算機學(xué)報, 2013, 36(2): 445-456. ZHANG Yunqian, ZHENG Zheng, JI Xiaohui, et al. Markov Model-Based Effectiveness Predicting for Software Fault Localization [J]. Chinese Journal of Computers, 2013, 36(2): 445-456.

[7]WONG W E, DEBROY V. Software Fault Localization [J]. IEEE Transactions on Reliability, 2010, 59(3): 473-475.

[8]WONG W E, DEBROY V, CHOI B. A Family of Code Coverage-Based Heuristics for Effective Fault Localization [J]. Journal of Systems and Software, 2010, 83(2): 188-208.

[9]XIE X, WONG W E, CHEN T Y. Metamorphic Slice: An Application in Spectrum-Based Fault Localization [J]. Information and Software Technology, 2013, 55(5): 866-879.

[10]SAHOO S K, CRISWELL J, GEIGLE C, et al. Using Likely Invariants for Automated Software Fault Localization [C]∥Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems. New York, NY, USA: ACM, 2013: 139-152.

[11]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, FL, USA: ACM, 2002: 467-477.

(責(zé)任編輯： 劉俏亮)

Research on Fault Localization Based on Execution Trace and Dynamic Slicing

SUN Shiming1, HOU Xiuping1, GAO Can2, SUN Linlin1
(1. School of Computer Science and Engineering, Changchun University of Technology, Changchun 130012, China;
2. The First Affiliated Hospital, Soochow University, Suzhou 215006, China)

The problem of faulty localization during program debugging is studied, and execution trace and dynamic slicing are applied to faulty localization. Irrelevant statements of fault localization are included in execution trace, accuracy of fault localization is affected by these statements. The influence of irrelevant statements is reduced by dynamic slicing technology based on execution trace. The model of suspicious degrees computing based on execution trace and dynamic slicing had been established, and suspicious degree of each statements could be computed by this model. After sorting these statements by their suspicious degrees, recommendation of fault localization would be reached. The experimental results are compared with other algorithms’, and the method of faulty localization based on execution trace and dynamic slicing is proved effective.

execution trace; dynamic slicing; suspicious degrees

1671-5896(2014)05-0528-06

2014-01-14

國家科技部863高技術(shù)基金資助項目(2011AA040602)

孫士明(1986— ), 男, 山東萊蕪人, 長春工業(yè)大學(xué)碩士研究生, 主要從事軟件工程研究, (Tel)86-13756116537(E-mail)sunshiming0634@qq.com；

侯秀萍(1964— ), 女, 長春人, 長春工業(yè)大學(xué)教授, 碩士生導(dǎo)師, 主要從事軟件工程研究, (Tel)86-18643194774(E-mail)houxiuping@mail.ccut.edu.cn。

TP311

： A