文萬(wàn)志　陳善利

摘要：程序錯(cuò)誤定位是程序調(diào)試中最復(fù)雜最耗時(shí)的任務(wù)之一。文中提出一種新穎的基于依賴分析的錯(cuò)誤定位方法，這種方法構(gòu)造可疑代碼的數(shù)據(jù)依賴和控制依賴，通過求精算法和擴(kuò)大算法實(shí)現(xiàn)程序錯(cuò)誤定位。文中通過實(shí)例驗(yàn)證了該方法的有效性。

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）20-0202-02

在軟件開發(fā)和維護(hù)過程中，不可避免的會(huì)引入一些未知的錯(cuò)誤。隨著軟件系統(tǒng)的不斷大型化和復(fù)雜化，軟件程序中的錯(cuò)誤定位越來越困難。傳統(tǒng)的手動(dòng)斷點(diǎn)法和插入語(yǔ)句法不再適應(yīng)當(dāng)前需求，自動(dòng)化、半自動(dòng)化的錯(cuò)誤定位方法已成為主要趨勢(shì)。

近些年，研究人員提出了各種各樣的錯(cuò)誤定位技術(shù)，如：基于程序切片的技術(shù)[2～3]、基于程序譜的技術(shù)[5～6]、基于概念格的技術(shù)[4]、基于調(diào)用圖的技術(shù)[1]等等。這其中，基于程序切片的技術(shù)有利于提取錯(cuò)誤依賴相關(guān)部分[2～3]，基于程序譜的技術(shù)簡(jiǎn)單高效[5～6]，因而，這兩種技術(shù)是當(dāng)前最流行的錯(cuò)誤定位技術(shù)。然而，基于程序切片的技術(shù)提取的依賴相關(guān)部分規(guī)模通常比較大，基于程序譜的技術(shù)缺乏依賴分析，存在一定的局限性。文中基于依賴分析，首先提取與錯(cuò)誤最相關(guān)部分，然后不斷擴(kuò)大搜索規(guī)模進(jìn)行錯(cuò)誤定位。

1 程序錯(cuò)誤定位算法

1.1 基本概念

程序依賴通常包括控制依賴和數(shù)據(jù)依賴，文中定義如下。

定義1 控制依賴. s1和s2為程序P中的兩條語(yǔ)句，令PATH（s2）為s2的必經(jīng)節(jié)點(diǎn)集合，XPATH（s1）為s1的后必經(jīng)節(jié)點(diǎn)集，若：（1）s1∈PATH（s2）；（2）s2?XPATH（s1）；（3）s1到s2可達(dá)路徑上不存在s3，使得s3∈PATH（s2），s2?XPATH（s3），則s2控制依賴s1，記作[s2→cds1]。

定義1中，PATH（s2）為s2的必經(jīng)節(jié)點(diǎn)集合，即程序P任何一次執(zhí)行到s2必然經(jīng)歷的節(jié)點(diǎn)。XPATH（s1）為s1的后必經(jīng)節(jié)點(diǎn)集，即程序P任何一次執(zhí)行到s1，繼續(xù)執(zhí)行，必然經(jīng)過的節(jié)點(diǎn)集。如果執(zhí)行s2必然先執(zhí)行s1，而執(zhí)行s1后未必執(zhí)行s2，且s1到s2可達(dá)路徑上再?zèng)]有滿足這種關(guān)系的節(jié)點(diǎn)，則s2控制依賴s1。

定義2. 數(shù)據(jù)依賴. s1和s2為程序P中的兩條語(yǔ)句，令DEF（s1）為在s1中定義的變量集合，USE（s2）為在s2中使用的變量集合，若：（1）s1到s2之間存在可達(dá)路徑；（2）存在變量v∈USE（s2）∩v∈DEF（s1）；（3）s3為s1到s2可達(dá)路徑上的任意節(jié)點(diǎn)，v?DEF（s3），則s2數(shù)據(jù)依賴s1，記作[s2→dds1]。

定義2中，如果s1到s2存在可達(dá)路徑，在s2中使用的變量在s1中定義，且此變量沒有被s1到s2路徑上其他節(jié)點(diǎn)再定義，則s2數(shù)據(jù)依賴s1。

定義3. 依賴關(guān)系。若語(yǔ)句集合α、β滿足α中存在語(yǔ)句s1控制依賴或數(shù)據(jù)依賴β中某條語(yǔ)句s2，即[s1→cds2]||[s1→dds2]，則α依賴β，記作αΘβ。

定義4. 交集削片.令程序P的測(cè)試執(zhí)行集合T=TF∪TP，其中，TF={t1，t2，…，tm}為失效測(cè)試集合，TP={tm+1，t2，…，tn}，則交集削片[Inter_ChopPba=i=1mti-j=abtj]，其中m

定義4中，tk （1<=k<=n）為測(cè)試執(zhí)行語(yǔ)句集合，交集削片為所有失效測(cè)試及部分成功測(cè)試的差集。

1.2 程序錯(cuò)誤定位算法

一般情況，程序錯(cuò)誤數(shù)較少時(shí)，程序中錯(cuò)誤最可能存在于交集[i=1mti]中，利用交集削片可進(jìn)一步縮小集合大小。假設(shè)程序錯(cuò)誤出現(xiàn)在[i=1mti]中，對(duì)于較大型程序，此集合可能仍然較大，通過迭代調(diào)整交集削片參數(shù)a，b可進(jìn)一步精化錯(cuò)誤定位過程，求精算法如下：

算法1.求精算法

輸入：程序P

失效測(cè)試集合TF，TF={t1，t2，…，tm}

成功測(cè)試集合TP，TF={tm+1，t2，…，tn}

輸出：錯(cuò)誤語(yǔ)句編號(hào)

a=m+1，b=n， k=0；

for each k in 0 to n-m-1 do

create ζ（k）=[Inter_ChopPba+k]；

if ζ（k） include the fault statement s then

return s；

end if

end for

return 0；

算法1中，當(dāng)錯(cuò)誤不在ζ（m-n-1）中時(shí)，即不在交集[i=1mti]中時(shí)，求精算法返回0。此時(shí)需要檢測(cè)額外的代碼進(jìn)行錯(cuò)誤的最終定位。測(cè)試的失效由于執(zhí)行了錯(cuò)誤語(yǔ)句或者遺漏了語(yǔ)句。對(duì)于遺漏語(yǔ)句，這里依然可以當(dāng)作錯(cuò)誤執(zhí)行了遺漏后的語(yǔ)句，返回遺漏語(yǔ)句之后的語(yǔ)句即可。選取失效測(cè)試t及失效觀測(cè)節(jié)點(diǎn)s0，令Ψ=t-ζ（m-n-1）。如果錯(cuò)誤不在ζ（m-n-1）中，則錯(cuò)誤必在Ψ中。為了進(jìn)一步確定錯(cuò)誤的位置，根據(jù)Ψ的依賴語(yǔ)句依次擴(kuò)大定位語(yǔ)句，擴(kuò)大算法見算法2。

算法2.擴(kuò)大算法

輸入：程序P

失效測(cè)試t及失效觀測(cè)節(jié)點(diǎn)s0

語(yǔ)句集合Ψ

輸出：錯(cuò)誤語(yǔ)句編號(hào)

σ（0）= {s0}；

k=1；

σ（k）= σ（k-1）∪{s1|s1∈Ψ∧σ（k-1）Θ{s1}}；

while σ（k）≠σ（k-1） do

if σ（k）- σ（k-1） includes the fault statement s then

return s；

end if

k=k+1；

σ（k）=σ（k-1）∪{s1|s1∈Ψ∧σ（k-1）Θ{s1}}

end while

算法2中，σ（1）中包含了失效觀測(cè)節(jié)點(diǎn)s0的的依賴相關(guān)節(jié)點(diǎn)，σ（2）包含了與σ（1）依賴相關(guān)的節(jié)點(diǎn)，依次類推，根據(jù)直接依賴間接依賴依次定位出錯(cuò)誤。算法中while循環(huán)在依賴節(jié)點(diǎn)不再增加時(shí)通過控制語(yǔ)句退出，這在理論上是成立的，然而，事實(shí)上，錯(cuò)誤節(jié)點(diǎn)必和失效觀測(cè)節(jié)點(diǎn)相關(guān)的，即失效觀測(cè)節(jié)點(diǎn)依賴于錯(cuò)誤節(jié)點(diǎn)，因此while在循環(huán)過程中，if條件一定有成立的時(shí)候，總是能返回錯(cuò)誤語(yǔ)句。當(dāng)錯(cuò)誤數(shù)較多時(shí)，求精算法精度較弱。算法2根據(jù)依賴關(guān)系能去除無關(guān)部分較快的定位出錯(cuò)誤。

2實(shí)例分析

本節(jié)我們通過一個(gè)簡(jiǎn)單的程序片段來說明上述算法的有效性。程序片段如圖1所示。

……

1 float a，b，c，d，m，n；

2 cin>>a>>b>>c>>d；

3 if（a<0）

4 m=4*c；

5 else

6 m=2*a+2*c；

7 if（b<0）

8 n=2*3.14*d*d；

9 else

10 n=2*b+d；

11 cout<<”m=”<

12 cout<<”n=”<

……

圖1 簡(jiǎn)單例子

圖1中，錯(cuò)誤語(yǔ)句為語(yǔ)句10，正確的語(yǔ)句為”n=2*b+2*d”。不失一般性，選取t1，t2，t3，t4四個(gè)測(cè)試用例覆蓋程序片段中所有分支。令輸入（a，b，c，d）分別為（-3，3，7，11），（3，9，11，17），（-5，-6，10，7），（3，-10，8，13），則t1，t2，t3，t4的測(cè)試覆蓋信息及執(zhí)行結(jié)果如下：

表1 測(cè)試信息

根據(jù)求精算法1，a=3，b=4，ζ（0）=[Inter_ChopPba+0]=[Inter_ChopP43+0]=[i=12ti-j=34tj]=（{1，2，3，4，9，10，11，12}∩{1，2，5，6，9，10，11，12}）-（{1，2，3，4，7，8，11，12}∪{1，2，5，6，7，8，11，12}）={1，2，9，10，11，12}-{1，2，3，4，5，6，7，8，11，12}={9，10}，這樣根據(jù)算法可以高效的定位出錯(cuò)誤的最終位置。然而當(dāng)錯(cuò)誤數(shù)較多時(shí)，求精算法并不能保證一次性能定位出錯(cuò)誤，這時(shí)利用擴(kuò)大算法能高效定位出錯(cuò)誤。如在上例中，除了現(xiàn)存的語(yǔ)句10錯(cuò)誤外，語(yǔ)句4也為錯(cuò)誤語(yǔ)句。則在表1中，t1，t2，t3均為失效語(yǔ)句。a=4，b=4，根據(jù)求精算法可得ζ（0） =?，ζ（1） ={1，2，11，12}。此例中，存在失效輸出，為失效觀測(cè)節(jié)點(diǎn)，根據(jù)觀測(cè)節(jié)點(diǎn)11，σ（1）={4，6}，定位出錯(cuò)誤語(yǔ)句4，根據(jù)觀測(cè)節(jié)點(diǎn)12，σ（1）={8，10}定位錯(cuò)誤語(yǔ)句10。

3結(jié)論

文中提出了一種基于依賴分析的程序錯(cuò)誤定位算法，并通過實(shí)例說明了這種算法的有效性。在程序規(guī)模較大時(shí)，求精算法和擴(kuò)大算法能較大的縮小錯(cuò)誤搜索的規(guī)模，同時(shí)能給出搜索域中的錯(cuò)誤檢測(cè)順序，從而可高效的定位出程序中的錯(cuò)誤。

參考文獻(xiàn)：

[1] Eichinger F， Pankratius V， Groe P. Localizing defects in multithreaded programs by mining dynamic call graphs[C]. Proceedings of the 5th International Academic and Industrial Conference-Practice and Research Techniques， 2010：56-71.

[2] Lei Y， Mao XG， Chen TY. Backward-slice-based statistical fault localization without test oracles[C]. Proceedings of the International Conference on Quality Software，2013：212–221.

[3] Ju X， Jiang S， Chen X， Wang X， Zhang Y， Cao H. Hsfal： effective fault localization using hybrid spectrum of full slices and execution slices[J]. Journal of Systems and Software， 2014， 90（4）： 3-17.

[4] Sun X， Li B， Wen W. CLPS-MFL： using concept lattice of program spectrum for effective multi-fault localization[C].Proceedings of the 13th International Conference on Quality Software， 2013：204-207.

[5] Xue J， Monperrus M. Test Case Purification for Improving Fault Localization[C].Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering， 2014：52-63.

[6] Xue X， Namin AS. How significant is the effect of fault interactions on coverage-based fault localizations[C].Proceedings of 2013 ACM/IEEE International Symposium on Empirical Software Engineering and Measurement， 2013：113-122.