调试不仅仅是费时的、繁琐的、昂贵的,而且也是极易出错的^[1-4].在各种调试活动中,软件故障定位(简称为故障定位)已被确定为最昂贵的活动之一^[5].能够快速地定位故障的根源,可以减少测试阶段所花费的时间.故障定位技术^[6-19]的发展为未来的程序修复铺平了道路.

常用的故障定位技术的基本思想可解释如下:首先定出最有可能的故障部分(例如程序语句和谓词),并对它们进行排序;然后,根据排列的顺序进行逐一检查,直到找到故障的部分为止.一种好的定位技术应当是把有故障的部分排到更靠前,这样,故障就能被更快地检查出来.理想情况下,有故障的部分排在第一位,不需要程序员的进一步分析,故障完全可以自动定位.

目前,主要的故障定位方法有:

· 基于频谱的故障的定位(spectrum-based fault localization)^[20].该方法通过抽象程序的轨迹,使得软件的组件与程序的故障关联起来.

· 相似程序谱的故障定位(nearest neighbor queries)^[13].该方法假设存在一个失败的程序谱和很多成功的程序谱,然后根据距离准则挑选出一个与失败运行最相似的成功运行的程序谱,进而比较两个程序谱的不同之处,以分离软件故障.虽然从复杂性的角度来看,统计方法非常有吸引力,但是不能推理解释多错误导致的失败.但实际上,大多数的程序是有多错误的.

· SOBER的故障定位方法^[21].该方法对谓词在成功执行和失败执行中的取值模式进行建模,然后基于统计学中假设检验的原理,量化每个谓词的故障相关性,按照谓词怀疑度(the suspicion degree)的大小审查源代码,发现故障的位置.然而,该方法需要足够多的测试用例.

· 基于模型的诊断(model-based diagnosis,简称MBD)^{[16, 17, 20, 22, 23-28]}.该方法通过逻辑推理和构建行为命题模式来推导软件故障.该推理方法的主要缺点是:(1) 模型生成通常是静态的分析,因为无法捕捉的动态数据依赖或者条件控制流;(2) 生成诊断候选集的代价是呈指数增长的,通常禁止使用超过几百行程序^[24].

然而,基于频谱的故障定位较为常用,可分为两类:基于语句和基于组件.基于语句的故障定位工作有文献^{[11, 20, 22, 23, 29, 30]},基于组件的故障定位工作有文献^{[16, 17]}.

基于语句的故障定位需要定位到代码行,就意味着需要大量的工作去掉与故障的代码行不相关的语句,其粒度过于精细.基于组件的故障定位组件范围很大(如服务器),程序员不能准确地定位具体的位置,其粒度又显得过于粗糙.为了解决这一问题,在前人工作的基础上,我们提出一种新的故障定位方法,即二次定位(double- times-locating,简称DTL).第1次函数定位,第2次语句定位.下面给出我们的方法框架图.图 1包含两个部分:第1部分叫做函数定位,我们把程序中的函数作为组件生成候选集,并根据算法计算出候选集的怀疑度进行排序,并将怀疑度较大的候选集放到故障定位的集合中,准备进行语句定位;第2部分叫做语句定位,我们把候选集中的函数所对应的语句作为组件,根据算法计算出语句的怀疑度进行排序,逐个检查怀疑度较大的语句,直到定位故障语句为止.

本文第1节描述函数定位的基本原理.第2节描述语句定位的基本原理.第3节用我们的方法对一个例子进行故障定位并分析.第4节给出实验结果及分析.第5节讨论和分析相关工作.第6节是全文的总结.

1 一次定位——函数定位

我们利用工具从程序中生成函数调用图,再从函数调用轨迹中建立程序谱,将软件的组件与程序的故障关联起来,再利用MBD的逻辑推理和构建行为命题模式来对函数进行初步定位.我们分别详细地介绍函数调用图的生成以及函数定位.

1.1 函数调用图

Doxygen是一种开源跨平台的,可以从一套归档源文件开始,生成HTML格式的在线类浏览器,或离线的LATEX,RTF参考手册.Graph Visualization Software(Graphviz)是一个由AT&T实验室启动的开源工具包,用于绘制DOT语言脚本描述的图形,它也提供了供其他软件使用的函数库.我们使用文档生成工具Doxygen和图像生成工具Graphviz生成函数调用图,记为G.

生成的函数调用图是有向无回路的拓扑结构,我们将函数之间的相互关系用拓扑结构进行描述.图 2是最常见的函数调用图.我们知道,函数之间常用的调用关系包括顺序、循环、选择方式.这里我们假设,如果函数是错误的,那么经过它的测试用例中必然是有错的.现在我们分析一下顺序调用和循环调用的情况,比如,函数F3调用函数F8时,假如函数F8有错,函数F3的测试用例中,如果经过函数F8的测试用例是有错的,我们就可以把函数F8放进函数的候选集中.选择调用的情况,比如,函数F1调用函数F4和函数F5时,如果只有函数F4有错,那么函数F1的错误测试用例的个数不小于函数F4的错误测试用例的个数,而且经过函数F4的测试用例是有错的.此时,我们就可以把函数F4放进函数的候选集中.我们把具体实现的算法放在第1节的算法1中实现.

1.2 程序谱

假定一个软件系统由M个组件C_j组成,其中j∈{1,...,M},并且存在多个故障,记为C.诊断报告D=〈…,d_k,…〉是一个由诊断候选集d_k构成的有序集合.程序谱是由参与了系统的特定动态行为的组件构成的集合,它统计了系统执行的N个测试用例的结果(成功/失败).我们的行为模型是通过一组涉及计算的组件构成,并且不需要详细地描述行为的具体信息.我们把程序成功/失败的信息输入到程序谱.通过实例化程序中每一个组件,形成矩阵A.在A中的元素a_ij表示组件C_j是否参与了第i个测试用例的执行:若是,则a_ij=1;若不是,则a_ij=0.测试用例的结果(成功/失败)用向量e表示.向量e中的元素e_i表示第i个测试用例的执行结果:若成功,则e_i=0;若失败,则e_i=1.因此,矩阵(A,e)就是我们需要的程序谱.

1.3 定位函数

基于模型的推理方法得到的诊断报告描述了对多个故障候选集d_k的排序,例如D={〈2,3〉,〈1〉},这意味着组件C₂和C₃有故障,或组件C₁有故障.正如上述描述的基于模型的推理方法,我们将这一方法应用在我们具体的程序模型中.在前人工作的基础上^{[17, 20, 23]},本文提出以函数作为组件建立程序模型.本文在逻辑命题方面将每个组件C_j定义为${{h}_{j}}\to (o{{k}_{in{{p}_{j}}}}\to o{{k}_{ou{{t}_{j}}}})$,其中,${{h}_{j}},o{{k}_{in{{p}_{j}}}},o{{k}_{in{{p}_{j}}}}$是布尔类型,分别代表组件的正确值、组件的输入变量和输出变量.这个模型表达了特定的行为:假如组件正确并且输入变量的值是正确的,那么其输出也是正确的.为了更清晰地说明这类特定行为,该模型没有指定故障的具体行为.即使组件是错误的和/或输入值不正确,还是可能导致正确的输出.因此,一个程序通过并不意味着经过的组件的正确性.在函数定位中,我们首先把程序中的函数作为组件生成候选集,在算法1中,把函数调用图G和程序谱(A,e)作为输入,由第4行~第22行生成函数候选集d_k;接下来,在函数定位过程中,计算出候选集的怀疑度进行排序.现在假定候选集是相互独立的,我们利用贝叶斯定理计算候选集D的条件概率:

$P({{d}_{k}}|e)=\frac{P(e|{{d}_{k}})P({{d}_{k}})}{P(e)}.$

其中,P(e)是一个标准化常数,由所有的d_k定义,不需要直接计算.$P({{d}_{k}})={{p}^{|{{d}_{k}}|}}\times {{(1-p)}^{M-|{{d}_{k}}|}}$,其中,M是组件的个数,|d_k|是候选集d_k包含的组件个数.在本文中,我们假定p=0.01,即程序本身大部分是正确的.

因为每次执行是独立的,因此,

$P(e|{{d}_{k}})=\prod\limits_{i=1}^{N}{P({{e}_{i}}|{{d}_{k}})}$

其中,P(e_i|d_k)的定义如下:

$P({{e}_{i}}|{{d}_{k}})=\left\{ \begin{array}{*{35}{l}} 1,\text{ if }{{d}_{k}}\wedge {{e}_{i}}\text{ are inconsistent} \\ \text{0, if }{{d}_{k}}\text{ is unique to }{{e}_{i}} \\ \varepsilon ,\text{ otherwise} \\ \end{array} \right..$

关于e的定义有很多种,本文的定义为

$\varepsilon =\left\{ \begin{array}{*{35}{l}} \prod\limits_{j\varepsilon {{d}_{k}}\cap {{a}_{ij}}=1}{{{h}_{j}}},\text{ }{{e}_{i}}=0 \\ 1-\prod\limits_{j\varepsilon {{d}_{k}}\cap {{a}_{ij}}=1}{{{h}_{j}}},\text{ }{{e}_{i}}=1 \\ \end{array} \right..$

其中,h_j∈[0,1]表示组件j正常工作的概率.

我们可以得出P(e|d_k)关于h_j的表达式,通过最大似然估计法计算$H=\underset{H}{\mathop{\max }}\,(P(e|{{d}_{k}})),$其中,H={h_j∈[0,1]|

j∈d_k}.最后,将得到的P(e|d_k),P(d_k)带入公式,计算出P(d_k|e)进行排序,将排序较高的候选集进行语句定位.

算法 1中的描述包括两个主要部分:

· 第1部分,我们把程序中的函数作为组件生成的函数,调用图G和程序谱(A,e)作为输入,生成函数候选

集D=〈…,d_k,…〉:第1步,我们计算出$|L|=\{{{A}_{{{k}^{*}}}}|{{e}_{k}}=1\}$,并且把那些函数满足没有调用其他函数、相关系数最大且n(v_j)=|L|直接放入候选集d_k中,并且更新函数集R和函数调用图G;第2步,对于不满足上述条件的函数,存在函数n_cs(v_j)/n_cf(v_j)=0.我们重复第1步,直到R中没有满足条件的函数为止.

· 第2部分,我们通过计算第1部分生成的函数候选集D=〈…,d_k,…〉中每个d_k的P(d_k|e)值,生成有序的诊断报告D′.

下面我们对算法1的时间和空间复杂度进行计算.算法1第1部分的时间复杂度就是对每个函数(M)相似度的计算,即(A,e)的每一行,复杂度为O(N×M);第2部分诊断报告的时间复杂度为O(M×logM).所以算法1的时间复杂度为O(M×(N+logM)).算法1的空间复杂度就是我们的方法需要保存函数的候选集C,空间复杂度为O(2^|C|×M).

算法 1. 诊断算法(一次定位算法).

输入:矩阵(A,e),函数调用图G.

输出:诊断报告D.

1. g←e

2.$L\leftarrow \{{{A}_{{{k}^{*}}}}|{{e}_{k}}=1\}$

3. D←∅

4. G←TOPOLOGICAL-SORT(G)

5. R←SORT(H,A,e)

6. while j<G.length do

7. if P(v_j)=Max(P(R))∧n_cf(v_j)=|L| then

8. Push(D,j)

9. A←EXTRACT(A,j)

10. G←EXTRACT(G,v_j)

11. R←R\{j}

12. end if

13. end while

14. while R≠∅∧P(v_j)≠0

15. j′←Pop(R)

16. while n_cs(v_j)/n_cf(v_j)=0

17. Push(D,j′)

18. A←EXTRACT(A,j′)

19. G←EXTRACT(G,v_j′)

20. R←R\{j}

21. end while

22. end while

23. for all d_k∈D

24. R←SORT(A,e,d_k)

25. i←0

26. P(d_k)ⁱ←0

27. while |P(d_k)ⁱ-P(d_k)^i-1|<e

28. for all j∈d_k

29. h_j←h_j+g*∇R(h_j)

30. end for

31. P(d_k)ⁱ←FUNCTION(R,${{\forall }_{j\in {{d}_{k}}}}{{h}_{j}}$)

32. i←i+1

33. end while

34. end for

35. Return 诊断报告D′

2 二次定位——语句定位

我们利用Wong等人^[30]提出的一种能够自动引导开发人员定位程序故障的方法,即DStar.该方法通过跨越21个不同的项目进行评估,DStar显示比同时代的其他16种故障定位技术更有效(12 similarity coefficient-based,Tarantula,Ochiai,H3b and H3c techniques).DStar的优越性并不限于定位只包含一个故障的程序,可以延伸到多个故障的程序,此外,无需任何对程序结构或语义先验信息.本文语句定位采用了当前基于语句效率较高的方法DStar.根据经验^{[11, 20, 23]},我们知道:

1) 一个语句的怀疑度正比于它本身覆盖失败的测试用例的次数.那么,这个语句被失败的测试执行次数越多,越值得怀疑.

2) 一个语句的怀疑度反比于它本身覆盖成功的测试用例的次数.那么,这个语句被成功的测试执行次数越少,越值得怀疑.

3) 一个语句的怀疑度反比于它本身未覆盖失败的测试用例的次数.那么,测试失败的情况下不涉及这个特定的语句,则该语句怀疑度小.

其中,情形1)是最健全的,并应该有一个更高的权重.我们重视失败的测试覆盖语句,而不是成功的测试用例覆盖的语句和失败的测试用例未覆盖的语句.Wong等人的实验结果表明,D³找到第1个故障的效果显著地高于Tarantula,D²,Mountford,Ochiai.因此,本文用到的DStar的公式:

$P(s)=\frac{{{[{{N}_{cf}}(s)]}^{3}}}{{{N}_{uf}}(s)+{{N}_{cs}}(s)}.$

符号含义如下:

· N_cf(s):通过第s行的结果为fail的用例总数.

· N_uf(s):不通过第s行的结果为fail的用例总数.

· N_cs(s):通过第s行的结果为pass的用例总数.

算法2中的描述包括3个主要部分:第1部分将一次定位的函数所在的行用数组B进行存储;第2部分利用DStar方法将B数组的所有行求出怀疑度;第3部分将怀疑度进行排序,从而定位错误的语句行.

算法2. 二次定位算法.

输入:诊断报告D.

输出:语句怀疑度排序.

1. For all d_k∈D do

2. B←Pop(R)

3. end for

4. For all b_j∈B do

5. P(b_j)←DStar(b_j)

6. end for

7. Return SORT(P(b_j),B)

算法 2的时间复杂度是对候选集C中函数所在的语句$\mathop{\sum }^{}{{C}_{j}}$的怀疑度进行排序$O\left( \mathop{\sum }^{}{{C}_{j}}\cdot N \right).$因此,算法1和算法2的时间复杂度总和为$O\left( N\cdot \left( M+\mathop{\sum }^{}{{C}_{j}} \right)+M\cdot \log M \right).$.统计技术(Tarantula方法^[11]、Ochiai方法^[23]和DStar方法^[30])每个语句$\mathop{\sum }^{}{{M}_{j}}$的相似度计算的复杂度为$O\left( N\cdot \mathop{\sum }^{}{{M}_{j}} \right),$诊断报告的复杂度$O\left( \mathop{\sum }^{}{{M}_{j}}\cdot \log \mathop{\sum }^{}{{M}_{j}} \right).$因此,统计技术时间复杂度总和为$O\left( N\cdot \mathop{\sum }^{}{{M}_{j}}+\mathop{\sum }^{}{{M}_{j}}\cdot \log \mathop{\sum }^{}{{M}_{j}} \right).$由时间复杂度可知,程序的语句行与函数行的数量级差别越大,我们的方法定位的速度就越快.因此,我们的方法在时间复杂度上更优于统计技术.

对于空间复杂度,统计方法需要对所有的语句$\mathop{\sum }^{}{{M}_{j}}$相似度计算进行保存(N_cf,N_uf,N_cs,N_us).因此,空间复杂度为$O\left( \mathop{\sum }^{}{{M}_{j}} \right).$我们的方法需要的空间复杂度为O(2^|C|×M).从数量级别表明,我们的方法的空间复杂度呈指数增长,这就需要我们更准确地定位函数的候选集,那么空间复杂度就会更小.

3 一个例子

现在我们通过一个小例子来描述我们的方法.表 1中有4个测试用例(x=-5,1,3,0),其中,黑点表示这一行被对应的测试用例运行时所覆盖,空格则表示这一行在测试用例运行时未覆盖.现在给出4个测试用例的测试结果.两个故障语句如下:正确程序f2(n){…,n%i==0,…},f5(n){…,i<n+1,…},故障程序f2(n){…,n%i!=0,…},f5(n){…,i<n,…}.通过图 3描述的小例子的函数调用图,我们知道f1~f5之间不存在函数之间的调用.

根据我们的算法1得到表 2函数与测试用例关系表.

计算出函数的候选集d₁=〈1,4〉,d₂=〈2,5〉;然后最大化$H=\underset{H}{\mathop{\max }}\,(P(e|{{d}_{k}}))$,得到h₁=h₄=0.5,h₂=h₅=0;最后,由贝叶斯定理计算:

$\begin{array}{*{35}{l}} P\left( {{d}_{1}}|e \right)={{h}_{1}}x{{h}_{4}}x\left( 1-{{h}_{1}} \right)x\left( 1-{{h}_{4}} \right), \\ P\left( {{d}_{2}}|e \right)=\left( 1-{{h}_{2}} \right)x\left( 1-{{h}_{5}} \right). \\ \end{array}$

P(d₁|e)=0.9412,P(d₂|e)=0.0588,因此,函数定位的函数是f2和f5.我们利用算法2,首先将一次定位的函数f2和f5中所有代码行对应的行号b_j=20~23,31~35用数组B进行存储;然后,利用DStar方法求出P(b_j=23)=0,P(b_j≠23)=0.70710678;最后,我们成功地找到第1个错误行.最好的情况是检查1行,最坏的情况是检查8行.为了与实验统一,我们平均检查的行数是4.5,小例子可执行的总代码行为27,那么成功地找到错误行需要检查总代码行的比值为P(Our_Method)=4.5/27=0.167.我们计算得到Tarantula,Ochiai,DStar方法成功地找到错误行需要检查总代码行的比值分别为:P(Tarantula)=5.5/27=0.204,P(Ochiai)=6.5/27=0.241,P(DStar)=6.5/27=0.241.

4 实验分析 4.1 实验建立

本文使用了经典的Siemens数据集进行实验,以证明我们方法的有效性,见表 3.第1列是实验对象的名称,第2列是每个实验对象的错误版本个数,第3列是每个实验对象主体的行数,第4列是测试用例的数量,第5列是实验对象的版本说明.其中,Siemens数据集可以从SIR(http://sir.unl.edu/content/sir.html)网站上免费获得.为了证明该方法的有效性,我们选择与一些经典的基于频谱的故障定位方法进行比较.

4.2 经典的基于频谱的故障定位方法介绍

我们现在总结一下基于频谱的故障定位方法.Jones等人提出了一种基于代码覆盖的错误定位方法^{[11, 31]},这种方法首先在程序运行时,在成功次数和失败次数的基础上计算语句怀疑度;其次,根据怀疑度的高低对语句进行排序;然后,调试人员根据排序表依次检查,直到他们找到错误为止.随后,一些研究人员在Tarantula公式的基础上,对怀疑度公式进行了改进.Abreu提出了Ochiai错误定位^[23],定义语句的怀疑度.而Ochiai是来自于分子生物学中的相似系数.在一个程序中,Kulczynski系数可以定位单个错误或多个错误.在此基础上,Wong等人提出了DStar(D)^[30].Abreu等人提出的Barinel^[20]以语句为粒度,应用模型诊断的方法及贝叶斯推理的方法进行错误定位.为了证明我们方法的有效性,本文使用Tarantula方法、Ochiai方法、DStar方法和Barinel方法与我们提出的方法进行了比较,现在我们分别给出Tarantula方法、Ochiai方法、DStar方法的定义.

· Tarantula:

$s(j)=\frac{\frac{{{N}_{cf}}(j)}{{{N}_{cf}}(j)+{{N}_{uf}}(j)}}{\frac{{{N}_{cs}}(j)}{{{N}_{cs}}(j)+{{N}_{us}}(j)}+\frac{{{N}_{cf}}(j)}{{{N}_{cf}}(j)+{{N}_{uf}}(j)}}.$

· Ochiai:

$s(j)=\frac{{{N}_{cf}}(j)}{sqrt(({{N}_{cf}}(j)+{{N}_{uf}}(j))\times ({{N}_{cf}}(j)+{{N}_{cs}}(j)))}.$

· DStar:

$s(j)=\frac{{{[{{N}_{cf}}(j)]}^{3}}}{{{N}_{uf}}(j)+{{N}_{cs}}(j)}.$

符号的含义:

· N_cf(j):通过第j行的结果为fail的用例总数.

· N_uf(j):不通过第j行的结果为fail的用例总数.

· N_cs(j):通过第j行的结果为pass的用例总数.

· N_us(j):不通过第j行的结果为pass的用例总数.

4.3 实验结果

我们通过对Siemens数据集的实验,得到一次定位的函数集以及在二次定位中发生故障时需要检查代码行占总行数的比值,作为故障定位的有效性值^[1].在表 4中,

· 一次定位的“无”代表故障没有出现在函数中.

· 二次定位的“0”代表 5种情况:第1种是故障出现在头文件中;第2种是故障的原因是缺少代码;第3种是没有故障的测试用例;第4种是故障出现在函数声明上;第5种是故障的代码行是程序未编译.

为了更清晰地表示故障定位的有效性值,我们给出一次定位函数集有效值的曲线图.在图 4中,我们把每个版本定位出的故障的函数占该版本总函数的百分比作为一次定位的有效值,并计算不同区间内能够检查出的故障函数集.X轴表示检测的函数的百分比;Y轴上给出定位故障函数的百分比;图上的节点表示在检查不同的函数区间能够定位出故障的百分比.在一次定位实验中,我们的方法检查60%的函数就可以定位大约86%的故障函数.

接下来,我们定位的函数以及定位出该故障函数占该版本总函数的比值.在表 5中,

· 一次定位的“无”代表故障没有出现在函数中.

· 占总函数的比值为“0代表两种情况:第1种是故障没有出现在函数中;第2种是该函数没有故障的测试用例,无法定位故障.

为了证明我们方法的有效性,我们单独统计每一种方法的平均有效性值.在下面的实验中,我们把发生故障时需要检查代码的行数占总行数的百分比作为故障定位的有效值,并计算不同的故障定位方法的有效值.在图 5中,X轴表示检测的代码的百分比;Y轴上给出定位故障的百分比;图上的节点表示在某个检查代码的百分比下,能够定位出故障的百分比.在平均情况下,我们的方法检查10%的代码行就可以定位大约57%的故障版本数.在相同的有效值下,Ochiai和DStar能够定位42%的故障版本数,Tarantula能够定位39%的故障版本数,Barinel能够定位47%的故障版本数.在统计学中,为了直观地比较二次定位的优越性,现在定义发生故障时需要检查代码的行数占总行数的百分比作为随机变量X,记录实验观察到X发生的概率,计算得到E(Tarantula)= 0.302,E(Ochiai)=0.296,E(DStar)=0.302,E(Barinel)=0.275,E(Our_Method)=0.22.也就是说,我们的方法在定位发生故障时需要检查代码的行数占总行数的百分比的数学期望比其他4种方法要小.

5 相关工作

本文中已经讨论过错误定位研究方法,现在对所附文献中所用方法进一步详细描述.

· 基于程序依赖关系的方法

Weiser在文献^[9]中提出了程序切片方法,用于描述影响程序某个执行点上特定变量的语句集合.后来的研究者通过考虑不同的依赖关系来解决故障定位中的遇到的各种问题.Baah等人在文献^[10]中扩展了程序依赖图,通过测试用例的执行信息估计节点间的统计依赖,建立了概率程序依赖图PPDG(probabilistic program dependence graph).它基于概率图模型的框架,首先产生程序依赖图,然后得到标记了子节点和父节点之间条件概率的变换程序依赖图.同时,插桩源程序得到测试用例的执行信息.通过学习执行信息中的数据,最终得到PPDG.在用于故障定位时,首先使用PPDG分析一次失败执行的信息,然后对PPDG上的节点按照怀疑度进行排序.一个节点的条件概率值被认为是其怀疑度,基于其父节点的值计算得到,条件概率值越低,怀疑度就越高.然而,插桩源代码的开销限制了PPDG在大型软件系统和部署软件的应用.

· 基于语句

Renieris等人在文献^[13]中提出了使用相似的程序谱(nearest neighbor queries)来进行故障定位的技术.该方法假设存在一个失败的程序谱和很多成功的程序谱,然后根据距离准则挑选出一个与失败运行最相似的成功运行的程序谱,进而比较两个程序谱的不同之处,以分离软件故障.如果故障在失败程序谱的集合中,那么直接可以定位故障;如果故障不在失败程序谱的集合中,则通过构建程序依赖图,并逐个检查图中的节点,直到定位出故障.由于失败和成功的程序谱的数量较多,该方法还没有为其建立一个完善的过滤系统.

· 基于谓词

Liu等人在文献^[21]中提出了SOBER方法.该方法对谓词在成功执行和失败执行中的取值模式进行建模,然后基于统计学中假设检验的原理,量化每个谓词的故障相关性,按照谓词怀疑度的大小审查源代码,发现故障的位置.然而,该方法需要足够多的测试用例,并且其鲁棒性尚不可知.

还有一些研究人员把模型诊断和频谱相结合,提高了故障定位中的排名,如文献^{[20, 22]}基于语句的故障定位和文献^{[16, 17]}基于组件(架构)的故障定位.然而,基于语句的故障定位需要定位到代码行,这就意味着需要大量的工作去掉与故障的代码行不相关的语句,其粒度过于精细.而基于组件的故障定位组件范围很大(如服务器),程序员不能准确地定位具体的位置,其粒度又显得过于粗糙.

6 结 论

本文提出了基于二次定位策略的故障定位方法.该方法从代码层向上抽象到函数层,首先使用工具生成函数调用图,将函数之间的相互关系用拓扑结构进行描述;再从函数调用轨迹中建立程序谱,将软件的组件与程序的故障关联起来;然后利用MBD的逻辑推理和构建行为命题模式来推导函数候选集并计算它们的概率,并根据概率进行怀疑度的排序;最后,利用DStar将函数候选集的语句进行故障定位.值得注意的是,我们的方法对以下5种情况是不能诊断出故障的:第1种是故障出现在头文件中;第2种是故障的原因是缺少代码;第3种是没有故障的测试用例;第4种是故障出现在函数的声明上;第5种是故障的代码行是程序未编译.我们知道,C语言所有程序都含有一个主函数,而主函数是程序处理的起点,在上述情况之外不存在跨函数的情形.因此,我们的方法是可行的.我们的方法在时间复杂度上优于统计技术.基于二次定位策略的故障定位方法,程序的语句行的数量级与函数行的数量级差别越大,我们的方法定位的速度就越快,详细分析见本文第2节.

虽然经研究表明,我们的方法有较好的定位效果,然而,我们还需要克服一些缺点并开展进一步的工作:首先,我们假设测试用例大部分是正确的,对程序本身的正确性要求较高,这无疑增加了局限性;其次,如果单个测试用例覆盖所有的函数,那么我们是无法正确诊断出具体的故障函数的,也就是说,我们的故障定位方法对测试用例有很强的依赖性;最后,Siemens程序包是序列化程序,我们需要对并发程序进行实验,有可能会面临更多的问题.