一种基于依赖分析的程序错误定位算法

文万志　陈善利

摘要：程序错误定位是程序调试中最复杂最耗时的任务之一。文中提出一种新颖的基于依赖分析的错误定位方法，这种方法构造可疑代码的数据依赖和控制依赖，通过求精算法和扩大算法实现程序错误定位。文中通过实例验证了该方法的有效性。

关键词：程序调试；错误定位；依赖分析

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）20-0202-02

在软件开发和维护过程中，不可避免的会引入一些未知的错误。随着软件系统的不断大型化和复杂化，软件程序中的错误定位越来越困难。传统的手动断点法和插入语句法不再适应当前需求，自动化、半自动化的错误定位方法已成为主要趋势。

近些年，研究人员提出了各种各样的错误定位技术，如：基于程序切片的技术[2～3]、基于程序谱的技术[5～6]、基于概念格的技术[4]、基于调用图的技术[1]等等。这其中，基于程序切片的技术有利于提取错误依赖相关部分[2～3]，基于程序谱的技术简单高效[5～6]，因而，这两种技术是当前最流行的错误定位技术。然而，基于程序切片的技术提取的依赖相关部分规模通常比较大，基于程序谱的技术缺乏依赖分析，存在一定的局限性。文中基于依赖分析，首先提取与错误最相关部分，然后不断扩大搜索规模进行错误定位。

1 程序错误定位算法

1.1 基本概念

程序依赖通常包括控制依赖和数据依赖，文中定义如下。

定义1 控制依赖. s1和s2为程序P中的两条语句，令PATH（s2）为s2的必经节点集合，XPATH（s1）为s1的后必经节点集，若：（1）s1∈PATH（s2）；（2）s2?XPATH（s1）；（3）s1到s2可达路径上不存在s3，使得s3∈PATH（s2），s2?XPATH（s3），则s2控制依赖s1，记作[s2→cds1]。

定义1中，PATH（s2）为s2的必经节点集合，即程序P任何一次执行到s2必然经历的节点。XPATH（s1）为s1的后必经节点集，即程序P任何一次执行到s1，继续执行，必然经过的节点集。如果执行s2必然先执行s1，而执行s1后未必执行s2，且s1到s2可达路径上再没有满足这种关系的节点，则s2控制依赖s1。

定义2. 数据依赖. s1和s2为程序P中的两条语句，令DEF（s1）为在s1中定义的变量集合，USE（s2）为在s2中使用的变量集合，若：（1）s1到s2之间存在可达路径；（2）存在变量v∈USE（s2）∩v∈DEF（s1）；（3）s3为s1到s2可达路径上的任意节点，v?DEF（s3），则s2数据依赖s1，记作[s2→dds1]。

定义2中，如果s1到s2存在可达路径，在s2中使用的变量在s1中定义，且此变量没有被s1到s2路径上其他节点再定义，则s2数据依赖s1。

定义3. 依赖关系。若语句集合α、β满足α中存在语句s1控制依赖或数据依赖β中某条语句s2，即[s1→cds2]||[s1→dds2]，则α依赖β，记作αΘβ。

定义4. 交集削片.令程序P的测试执行集合T=TF∪TP，其中，TF={t1，t2，…，tm}为失效测试集合，TP={tm+1，t2，…，tn}，则交集削片[Inter_ChopPba=i=1mti-j=abtj]，其中m

定义4中，tk （1<=k<=n）为测试执行语句集合，交集削片为所有失效测试及部分成功测试的差集。

1.2 程序错误定位算法

一般情况，程序错误数较少时，程序中错误最可能存在于交集[i=1mti]中，利用交集削片可进一步缩小集合大小。假设程序错误出现在[i=1mti]中，对于较大型程序，此集合可能仍然较大，通过迭代调整交集削片参数a，b可进一步精化错误定位过程，求精算法如下：

算法1.求精算法

输入：程序P

失效测试集合TF，TF={t1，t2，…，tm}

成功测试集合TP，TF={tm+1，t2，…，tn}

输出：错误语句编号

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中，当错误不在ζ（m-n-1）中时，即不在交集[i=1mti]中时，求精算法返回0。此时需要检测额外的代码进行错误的最终定位。测试的失效由于执行了错误语句或者遗漏了语句。对于遗漏语句，这里依然可以当作错误执行了遗漏后的语句，返回遗漏语句之后的语句即可。选取失效测试t及失效观测节点s0，令Ψ=t-ζ（m-n-1）。如果错误不在ζ（m-n-1）中，则错误必在Ψ中。为了进一步确定错误的位置，根据Ψ的依赖语句依次扩大定位语句，扩大算法见算法2。

算法2.扩大算法

输入：程序P

失效测试t及失效观测节点s0

语句集合Ψ

输出：错误语句编号

σ（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）中包含了失效观测节点s0的的依赖相关节点，σ（2）包含了与σ（1）依赖相关的节点，依次类推，根据直接依赖间接依赖依次定位出错误。算法中while循环在依赖节点不再增加时通过控制语句退出，这在理论上是成立的，然而，事实上，错误节点必和失效观测节点相关的，即失效观测节点依赖于错误节点，因此while在循环过程中，if条件一定有成立的时候，总是能返回错误语句。当错误数较多时，求精算法精度较弱。算法2根据依赖关系能去除无关部分较快的定位出错误。

2实例分析

本节我们通过一个简单的程序片段来说明上述算法的有效性。程序片段如图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 简单例子

图1中，错误语句为语句10，正确的语句为”n=2*b+2*d”。不失一般性，选取t1，t2，t3，t4四个测试用例覆盖程序片段中所有分支。令输入（a，b，c，d）分别为（-3，3，7，11），（3，9，11，17），（-5，-6，10，7），（3，-10，8，13），则t1，t2，t3，t4的测试覆盖信息及执行结果如下：

表1 测试信息

根据求精算法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}，这样根据算法可以高效的定位出错误的最终位置。然而当错误数较多时，求精算法并不能保证一次性能定位出错误，这时利用扩大算法能高效定位出错误。如在上例中，除了现存的语句10错误外，语句4也为错误语句。则在表1中，t1，t2，t3均为失效语句。a=4，b=4，根据求精算法可得ζ（0） =?，ζ（1） ={1，2，11，12}。此例中，存在失效输出，为失效观测节点，根据观测节点11，σ（1）={4，6}，定位出错误语句4，根据观测节点12，σ（1）={8，10}定位错误语句10。

3结论

文中提出了一种基于依赖分析的程序错误定位算法，并通过实例说明了这种算法的有效性。在程序规模较大时，求精算法和扩大算法能较大的缩小错误搜索的规模，同时能给出搜索域中的错误检测顺序，从而可高效的定位出程序中的错误。

参考文献：

[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.