一种面向巧合一致性问题的统计学软件缺陷定位方法

技术领域

本发明涉及一种动态的软件缺陷定位方法，特别是涉及一种面向巧合一致 性问题的统计学软件缺陷定位方法，它是一种集成了概率分布判据和标准化 类间距离计算的统计学软件缺陷定位方法。该方法属于软件测试技术领域。

背景技术

统计学软件缺陷定位方法(该方法本质上是一种算法，下文中出于习惯用法， 一律用算法一词)通过比较程序运行成功和失败时程序单元执行谱的差异，来查 找最有可能与程序缺陷有关的程序单元。

在现有的统计学软件缺陷定位方法中，较有代表性的是Tarantula算法、CBI 算法、SOBER算法（这些名称是算法的发明人命名，现在暂无中文名称）。 Tarantula算法是哈罗德等人在“一种利用可视化信息的缺陷定位方法”（详见 2002年《第二十四届国际软件工程会议》）一文中提出的，其选择的插桩方法 是语句插桩，即对所有可执行语句进行插桩，统计成功与失败测试用例对每条 可执行语句的覆盖情况。该算法所基于的假设是如果一条可执行语句被所有失 败测试用例覆盖而没有被成功测试用例覆盖，则该可执行语句越可疑。然而， 程序中大多数语句都很少导致缺陷，针对所有可执行语句的缺陷定位不仅会造 成信息的冗余，而且还会使缺陷定位成本增大。针对这个问题，本.里布里特等 人在“一种可扩展的基于统计学的故障隔离方法”(详见2005年《美国计算机学 会<编程语言的设计和实现>会议》)一文中提出了CBI算法。该算法选择的插 桩方法是谓词插桩，对分支语句、返回语句以及数量对语句进行插桩，通过收 集和处理谓词在程序运行时的动态执行信息来实现缺陷定位。里布里特虽然解 决了Tarantula算法中的信息冗余问题，但并没有充分地收集谓词的执行信息（主 要表现在里布里特仅仅考虑了谓词是否在一次程序运行中被执行到，并没有考 虑该谓词在一次程序中被执行了几次）。信息不充分导致CBI算法的定位效果 还有待提高。为此，刘超等人在“基于统计学的程序纠错：一种基于假设检验的 方法”（详见2006年《电机及电子学工程师联合会软件工程汇刊》）一文中提出 了SOBER算法。该算法有效地解决了谓词执行信息收集不充分的问题，表现 为它不仅记录了谓词是否在一次程序运行中被执行到，而且记录了谓词在一次 程序运行中执行的次数，包括谓词判断为“真”和判断为“假”的次数。将这两种 统计信息也包括到谓词缺陷相关度的计算当中，并引入假设检验的方法来计算 谓词的可疑度。实验结果表明，SOBER算法的定位效果要优于CBI算法。然 而SOBER算法在应用时需要假设谓词执行谱分布是正态分布，张震宇等人在 “非参统计学缺陷定位”（详见2011年《系统与软件期刊》）一文中曾证明有些 程序的谓词执行谱并不符合正态分布，因此提出Wilcoxon算法和 Mann-Whitney算法。该算法利用统计学中非参数假设检验的方法来比较谓 词执行谱的差异，经大量实验证明，Wilcoxon算法和Mann-Whitney算法在 现有基于谓词的缺陷定位算法中定位效果最优。

尽管统计学软件缺陷定位方法可以取得很高的定位精度，但是，该类方法 的定位精度会受输入数据特性的影响。之前的研究发现，巧合一致性（巧合一 致性是指程序运行时缺陷语句被执行，但程序并没有表现出失效）问题的存在 会降低统计学缺陷定位方法的定位精度。因为巧合使程序运行成功的测试用例 的执行剖面与使程序运行失败的测试用例的执行剖面相近，如果将这部分测试 用例归入到成功的测试用例中，会对比较谓词成功与失败执行谱差异产生负面 影响。因此，现有技术主要集中于找到使程序巧合运行正确的测试用例，并且 将其移除。但是，这些方法首先受限于如何正确找到存在巧合一致性的测试用 例。其次，移除存在巧合一致性的测试用例，将会减少输入的测试数据，影响 算法中统计学方法的应用。

如何在允许巧合一致性存在的前提下，利用巧合一致性问题的相关特性来 进行缺陷定位正是本发明所基于的考虑。

发明内容

本发明一种面向巧合一致性问题的统计学软件缺陷定位方法，其目的是： 克服现有方法易受巧合一致性问题影响的缺点，从巧合一致性问题本身的特性 出发，提供一种新的统计学软件缺陷定位方法。

本发明一种面向巧合一致性问题的统计学软件缺陷定位方法，其设计思想 是：将程序中的插桩谓词分为中立谓词（与程序缺陷无任何数据及控制关联关 系，并且相距缺陷较远的谓词）、导致缺陷的谓词（与程序缺陷有数据或控制关 联关系，并且位于数据或控制关联关系之前的谓词，也包括缺陷谓词本身）以 及受缺陷影响的谓词三类。在程序运行原理上，由于导致缺陷的谓词的成功与 失败执行谱会存在一定的交叠，而受缺陷影响的谓词的成功与失败执行谱没有 交叠，按照谓词成功与失败执行谱交叠程度的差异可以将导致缺陷的谓词排在 受缺陷影响的谓词的前面。继而借助标准化类间距离的计算对导致缺陷的谓词 的排序进行细化，从而将最可疑的导致缺陷的谓词排在相对靠前的位置优先进 行检查。具体是插桩程序中的桩函数返回谓词的动态执行信息(此处主要是指谓 词的评估偏差)。相应地，运行程序并收集该信息。最后，采用设计的统计学方 法进行结果分析。具体分析时，利用概率分布判据与标准化类间距离计算相结 合的方式来计算每个谓词的缺陷关联度。然后，根据缺陷关联度从高到低将谓 词排列，从而实现依据谓词排序进行缺陷定位的目的。

更具体地，本发明一种面向巧合一致性问题的统计学软件缺陷定位方法， 其步骤包括以下五步：

第一步对含有缺陷的程序进行插桩。程序插桩在软件测试中有广泛的应用， 插桩是为了获得特定程序节点在程序运行时的动态信息。本专利申请主要对 程序中的分支语句、返回语句以及数量对语句进行插桩，它通过插入布尔表 达式（简称谓词）来得以实现，桩函数要求在程序运行时输出谓词的动态执 行信息（在本专利申请中，谓词的动态执行信息主要是指谓词的评估偏差。 评估偏差的定义是：一次程序运行中谓词被判断为“真”的概率。可以用表达 式来表示，其中，e_T(p_j,r_i)和e_F(p_j,r_i)分别表示程序 第r_i次运行时谓词p_j被判断为“真”和判断为“假”的次数。需要注意的是， 若谓词在某次程序运行中没有被执行，则此时的评估偏差值设为0.5）。为便 于后文说明，使用p₁，p₂，…，p_m表示程序中的m个插桩谓词；

第二步加载程序的全部测试用例，运行插有桩函数的程序。通过对比原始版 本（不含有任何缺陷的程序）输出和缺陷版本（植入单个缺陷后的程序）输 出，区分使程序运行成功和运行失败的测试用例。其中，使用u表示程序运 行成功的次数，v表示程序运行失败的次数；

第三步收集每次程序运行时桩函数输出的谓词动态执行信息。在程序运行 成功时，谓词p_j(j∈[1,m])共得到u个评估偏差，程序运行失败时，谓词p_j共得到v个评估偏差；

第四步对收集到的所有谓词动态执行信息进行统计学分析，该步骤又分为四 小步：

(一)计算谓词p_j(j∈[1,m])成功与失败执行谱分布的交叠程度，用O_j表示。

对于谓词p_j在程序运行成功和失败时评估偏差值所分别构成的执行谱集 合，利用概率分布判据$O_j=-\ln \left[{\Sigma }_{y_j\in D_j}\sqrt{P\left(y_j\right|{\omega }_F)\times P\left(y_j\right|{\omega }_N)}\right]$来计算 谓词p_j成功与失败执行谱分布的交叠程度。其中，D_j表示谓词p_j所有评 估偏差值所构成的集合，y_j表示该集合中的一个取值，ω_N和ω_F分别代表 程序运行成功和运行失败；

(二)计算谓词p_j执行谱分布的标准化类间距离，用A_j表示。对于谓词p_j在程序运行成功和失败时评估偏差值所分别构成的执行谱集合，首先， 利用公式来计算谓词p_j成功与失败执行谱分布之间的 距离，即类间距离。其中，表示程序运行成 功时谓词p_j所有评估偏差值的均值。表示程序 运行失败时谓词p_j所有评估偏差值的均值。然后，利用公式 $D_j=\frac{\sqrt{\frac{{\Sigma }_{i=1}^v\left[{(x(p_j,f_i)-m_j^F)}^2\right]}{v}}+\sqrt{\frac{{\Sigma }_{i=1}^u\left[{(x(p_j,n_i)-m_j^N)}^2\right]}{u}}}{2}$来计算谓词p_j成功与失败执行 谱分布内部分散的程度，即类内距离。最后，利用公式来求取

谓词p_j执行谱分布的标准化类间距离。需要注意的是，若D_j=0，而B_j≠0， 则设置A_j=+∞。若D_j＝B_j=0，则设置A_j=0；

(三)计算谓词p_j的缺陷关联度。借助上面两步中分别得到的结果，利用公 式来计算谓词p_j的缺陷关联度。

(四)对程序中的每个插桩谓词执行上述的（一）至（三）步，直至得到全 部谓词的缺陷关联度。并按照缺陷关联度的从高到低，对所有谓词排序。 需要注意的是，如果遇到谓词可疑度相同的情况，则按照谓词编号的 由小到大排序。此外，对于上一步中可能出现的O_j=A_j=0的特殊情况， 在排序操作中需要将该谓词排在所有谓词的后面，因为该谓词的成功与 失败执行谱完全相同，表现为最不可疑；

第五步根据得到的谓词排序表，对谓词依序进行查找，直到找到缺陷相关谓 词为止。

本发明与现有方法相比较的优点在于：本发明允许巧合一致性的存在，并 且利用巧合一致性问题的相关特性进行缺陷定位，从而提高了算法的定位精度。 而且方法简单，容易实现。

附图说明

图1为示例程序代码

图2为桩函数输出的部分信息示意图

图3为本发明流程示意图

图4为待测程序详细信息图

图5为所有待测程序上实验结果对比

图6为print_tokens及print_tokens2上实验结果对比

图7为replace上实验结果对比

图8为schedule及schedule2上实验结果对比

图9为tcas上实验结果对比

图10为tot_info上实验结果对比

图11为space上实验结果对比

图12为flex上实验结果对比

图13为grep上实验结果对比

对图中的符号和标号说明如下：

图1是从一大段程序中截得的小段程序代码，每一行是一句代码，最 前面一列是代码所在行数，中间一列是程序代码，其中，缺陷位于第5行。 最右面一列是对该段程序插桩的谓词以及相应的谓词编号。

图2中的每一行表示一个测试用例运行时待测程序中所有插桩谓词的 运行结果。其中，B表示插桩的语句是分支语句或数量对语句，B后面括号 中的第一个数即为该插桩谓词的评估偏差值。R表示插桩的语句是返回语句， R后面括号中最大的那个数即为该插桩谓词的评估偏差值。

图4中的第一列print_tokens、print_tokens2、schedule、schedule2、replace、 tot_info、tcas、space、flex及grep分别为待测程序的名称；#of selected versions 是每个待测程序所选取的缺陷版本数，每一个缺陷版本都只包含一个缺陷； #of LOC是每个程序的代码长度，单位为行；#of predicates是每个待测程 序中插桩的谓词数；#of runs是运行待测程序的测试用例数目。

图5~图13中的横坐标为检查的谓词数占全部谓词的百分比，即查找代 价，纵坐标为定位到的缺陷占总缺陷的百分比。图中J-B为本发明标记，CBI、 SOBER、Wilcoxon和Mann-Whitney分别为各算法名称。

具体实施方式

假定待测程序中含有若干个缺陷，通常测试之前这些缺陷是未知的。首 先对待测的程序进行插桩，设计桩点的输出信息为图2所述的信息。然后加 载测试用例，运行插桩后的程序，输出状态信息。利用这些状态信息计算得 到谓词的缺陷关联度，并将谓词按照缺陷关联度从高到低排列，最后根据得 到的谓词排序自上向下在程序中寻找缺陷。

为了检验本专利中所提方法的定位效率，考虑把Siemens程序包、space 程序包以及UNIX程序包中的flex和grep（这些程序包都是公认的典型测试 对象）作为实验对象，这些待测程序中的缺陷位置、缺陷数目和缺陷类型都 是已知的。图4显示了所有待测程序的详细信息。

选取图1所示的一段程序来验证本发明方法。运用本发明的流程如图3 所示，其具体实施步骤如下：

第一步对该段程序进行插桩。共插入7个桩点，桩函数的位置及编号如 图1所示，设置桩函数输出的信息格式如图2所示；

第二步加载6个测试用例，它们分别是T1：(2,1,3)、T2：(2,1,2)、T3：(1,1,3)、 T4：(1,2,3)、T5：(2,3,1)、T6：(1,2,0)，运行插桩后的程序。其中，前四 个测试用例使程序运行成功，后两个测试用例使程序运行失败。T3和T4 是存在巧合一致性的测试用例；

第三步分别收集每次程序运行时桩函数输出的谓词动态执行信息。例如， 程序运行成功时，谓词P₄共得到4个评估偏差值，分别为0.5，0.5，0， 0。程序运行失败时，谓词P₄共得到2个评估偏差值，分别为0，0；

第四步对收集到的所有谓词动态执行信息进行统计学分析，该步骤又可分 为四小步：

(一)计算谓词P₄成功与失败执行谱的交叠程度，用O₄表示。经统计， p(0.5|ω_N)=0.5,p(0.5|ω_F)=0，p(0|ω_N)=0.5，p(0|ω_F)=1。带入公式$-\ln \left[{\Sigma }_{y_j\in D_j}\sqrt{P\left(y_j\right|{\omega }_F)\times P\left(y_j\right|{\omega }_N)}\right],$可得O₄=0.347；

(二)计算谓词P₄执行谱分布的标准化类间距离，用A₄表示。经计算，B₄=0.25。同时，D₄=0.125。带入公式可得A₄=2；

(三)将上述两步计算出的O₄和A₄结果带入公式求出P₄的 缺陷关联度S₄=0.318；

(四)对于该段程序中的每个谓词，重复（一）至（三）步，求出程序 中每个谓词的缺陷关联度。

(五)将所有7个谓词依据缺陷关联度从高到低排序，所得谓词排序为 P₂，P₃，P₄，P₅，P₆，P₇，P₁。

第五步利用此排序对谓词依次进行查找。已知谓词P₄是缺陷谓词，则在 此排序中查找到第3个谓词即可定位到缺陷。

对全部171个待测程序运用上述方法进行缺陷定位，并选取CBI算法、 SOBER算法、Wilcoxon算法和Mann-Whitney算法作为比较算法（选取CBI 算法和SOBER算法是因为这两种算法是典型算法，选取Wilcoxon算法和 Mann-Whitney算法是因为这两种算法目前被证明能取得较好的定位效果）。 此外，引入P-score作为算法定位效果的评价标准。其中，L表示程序中插桩谓词的总数目，表示缺陷相关谓词，表 示缺陷相关谓词在谓词排序列表中的排位（例如，对于上面具体实施中所举 的例子，），P-score越小表示定位效率越高。

从图5中可以看到，对于全部171个待测程序，本发明方法（图中以J-B 标记，以下各图类似）在横轴所有统计节点处都表现出优于其他算法的定位 效果。例如，当检查10%的谓词时，本发明方法可以定位到47.95%的缺陷 （47.95%×171≈82，接近全部缺陷总数的一半），相比之下，CBI算法、 SOBER算法、Wilcoxon算法和Mann-Whitney算法则分别定位到21.64%、 12.28%、32.75%以及18.71%的缺陷，可见本发明在整体定位效果方面要明 显优于CBI算法、SOBER算法、Wilcoxon算法和Mann-Whitney算法。

图6~图13为各单独程序上分别应用本发明方法与CBI算法、SOBER 算法、Wilcoxon算法以及Mann-Whitney算法进行缺陷定位的实验结果对比。 从图6~图13中可发现，除了在图8和图11某些统计节点上本发明的定位 效果还有待提高外，对于各单独程序，本发明方法仍能表现出最优的定位效 果。

从以上实验数据中得出如下结论：

（1）本发明提出利用巧合一致性的相关特性来进行缺陷定位，在允 许巧合一致性存在的前提下，该方法能有效避免巧合一致性对算法 定位精度造成的影响；

（2）本发明在定位大多数程序缺陷时的定位效率都要高于CBI算法、 SOBER算法、Wilcoxon算法以及Mann-Whitney算法。