一种面向失败测试用例稀少情况的软件错误定位方法

摘要

一种面向失败测试用例稀少情况的软件错误定位方法，包括五个步骤：一、对原始测试用例集中的成功测试用例进行拆分；二、成批复制失败测试用例，与拆分好的每份成功测试用例配对；三、依次输入类别均衡的子测试用例集，生成相应子排位表；该步骤又具体分为收集子测试用例集运行时程序谱的执行信息，计算语句可疑度和生成子排位表这三小步；四、集成多重排位结果，合成综合排位表；五、根据得到的综合排位表，依次返回源程序对应位置处进行检查，直到找出与错误相关的语句为止。该方法可以有效克服测试用例集类别不均衡现象对基于谱的软件错误定位方法所带来的不利影响，并且方法切实可行，能够有效提高基于谱的软件错误定位方法的定位精度。

说明书

所属技术领域

本发明涉及一种动态的软件错误定位方法，尤其涉及一种面向失败测试用 例稀少情况的软件错误定位方法，它是一种面向拥有大量成功测试用例和极少 数失败测试用例的使用情况，涉及对成功测试用例集进行拆分和对多重语句可 疑度进行集成操作的软件错误定位方法。该方法属于软件测试技术领域。

背景技术

软件已深入到我们日常生活中的每个角落，但与此同时，软件中的bug（错 误）也是无处不在。为查找软件中潜在的bug，许多自动化的错误定位技术被 相继提出。

基于谱的软件错误定位方法(Spectrum-based Fault Localization，简称SBFL。 该方法本质上是一种算法)通过比较程序语句在成功测试用例和失败测试用例 运行时执行信息的差异，来查找最有可能与程序缺陷有关的语句。该类算法所 基于的假设是：如果一条可执行语句只被失败测试用例覆盖而没有被成功测试 用例所覆盖，则该可执行语句被认为越与程序缺陷相关。

在现有的基于谱的软件错误定位方法中，最具有代表性的是Tarantula算法 （该名称是算法的发明人命名，现在暂无中文名称）。Tarantula算法是琼斯等人 在“一种利用可视化信息的缺陷定位方法”（详见2002年《第二十四届国际软件 工程会议》）一文中提出的，其选择的插桩方法是语句插桩，即对所有可执行语 句进行插桩，统计成功和失败测试用例对每条可执行语句的覆盖情况。其余几 种基于谱的软件错误定位方法与Tarantula算法所使用的插桩方式以及信息类型 都相同，只是彼此可疑度计算公式不同。纳什等人在“一种基于谱的软件诊断 模型”（详见2011年ACM出版社出版的《软件工程方法》杂志）一文中对现 有的33种基于谱的软件错误定位方法进行了总结。

由于基于谱的软件错误定位方法的定位效果会受使用的测试用例集质量的 影响，因此，如何有效利用测试用例集成为了软件错误定位领域里关注的热点。 测试用例集缩减技术被证明能够有效提高对测试用例的利用效率，但是，现有 研究主要集中于减少测试用例集的大小，却忽略了测试用例集的组成，例如测 试用例集中成功测试用例与失败测试用例的类别比例。测试用例集中的类别不 均衡现象是指一类测试用例的数量要远远多于另一类测试用例的数量。在现实 生活中，已发布的软件通常都是含有大量的成功测试用例，仅含有少量的失败 测试用例。例如，服务于2008年北京奥运会信息管理系统的基础中间件产品， 它的成功测试用例与失败测试用例的比例就高达8500：1。对于验证错误定位 方法定位效果的实验程序，这种由于失败测试用例稀少所导致的类别不均衡现 象更是广泛存在。

研究如何消除测试用例集类别不均衡现象对基于谱的软件错误定位方法所 产生的不利影响正是本发明所基于的考虑。

发明内容

本发明一种面向失败测试用例稀少情况的软件错误定位方法，其目的是： 克服基于谱的软件错误定位方法容易受到测试用例集类别不均衡现象影响的缺 点，提出一种拆分—集成操作，使得基于谱的软件错误定位方法在面对失败测 试用例稀少情况时仍能发挥很好的定位作用。

本发明一种面向失败测试用例稀少情况的软件错误定位方法，其设计思想 是：首先，对成功测试用例进行拆分。将原始测试用例集中的成功测试用例分 成几个等份，确保每一份中成功测试用例的数量与原始测试用例集中失败测试 用例数量相同。其次，将失败测试用例成批复制，并与拆分后的每份成功测试 用例进行配对，构成新的类别均衡的子测试用例集。之后，依次输入每份类别 均衡的子测试用例集，收集测试用例运行时程序的动态执行谱，调用基于谱的 软件错误定位方法进行计算，生成相应的语句排位表。最后，对多重语句排位 结果进行集成，合成综合排位表，程序开发人员根据综合排位表来查找程序中 的缺陷。

更具体地，本发明一种面向失败测试用例稀少情况的软件错误定位方法， 其步骤包括以下五步：

第一步对原始测试用例集中的成功测试用例进行拆分。将原始测试用例集中 的成功测试用例P分成等份，第i份（1≤i≤m）成功测试用例用P_i表 示。其中，u表示原始测试用例集中成功测试用例P的数量，v表示原始测 试用例集中失败测试用例F的数量。P_i中包含v个成功测试用例，这v个成 功测试用例均是通过对原始测试用例集中的成功测试用例进行随机不放回 抽取而得到；

第二步成批复制失败测试用例，与拆分好的每份成功测试用例配对。经过此 步后，将得到m份新的类别均衡的子测试用例集S_i，其中，每份子测试用 例集包含v个成功测试用例和v个失败测试用例；

第三步依次输入类别均衡的子测试用例集，生成相应子排位表。该步骤又 分为三小步：

(一)收集子测试用例集运行时程序谱的执行信息。针对插桩后的待测程序， 输入第i个类别均衡的子测试用例集，统计语句s在该子测试用例集运 行时得到的这四个参数。其中，分别表示第i个类别均衡的子测试用例集中经 过语句s的成功测试用例数目，经过语句s的失败测试用例数目，没有 经过语句s的成功测试用例数目和没有经过语句s的失败测试用例数目；

(二)计算语句可疑度。针对上一步中得到的语句s的执行信息，使用基于 谱的软件错误定位方法进行计算，为语句s计算可疑度T_i(s)。不断循 环该步骤，直至计算出所有语句的可疑度；

(三)生成子排位表。按照可疑度值由大到小的顺序对所有语句进行排序， 生成子排位表L_i。其中，语句s在子排位表L_i中的排位用R_i(s)表示。

第四步集成多重排位结果，合成综合排位表。针对第三步中得到的语句s的 m个可疑度计算结果，利用公式来为语句s计 算总可疑度其中，式中符号说明如下：m表示将原始测试用例集中的 成功测试用例拆分成的份数；表示第i个类别均衡的子测试用例集中 经过语句s的失败测试用例数目；T_i(s)表示运行第i个类别均衡的子测试用 例集之后，使用基于谱的软件错误定位方法为语句s计算出的可疑度。不 断循环第四步，为所有语句计算出总可疑度。最后按照总可疑度值由大 到小的顺序对所有语句进行排序，生成综合排位表L，语句s在综合排位 表中的排位用表示；

第五步根据得到的综合排位表，依次返回源程序对应位置处进行检查，直到 找出与错误相关的语句为止。

本发明与现有方法相比较的优点在于：现有方法均没有对失败测试用例稀 少所导致的测试用例集类别不均衡现象加以考虑，而该现象又会对基于谱的软 件错误定位方法的定位精度造成负面影响。本发明方法是第一个被提出来用于 解决该问题的方法，并且方法切实可行，能够有效提高基于谱的软件错误定位 方法的定位精度。

附图说明

图1为示例程序代码和测试用例运行剖面

图2为本发明流程示意图

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

图4为各算法在Siemens程序包上整体定位结果提升对比

图5为各算法在space、flex和grep程序上整体定位效果提升对比

图6为各算法在单个独立程序上定位效果提升对比

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

图1左侧这段代码的主要功能是输出三个数中的中间值。其中，错误 位于第4行，以方框标出，斜线右侧为正确的代码。可以发现该错误为逻辑 错误，在编译器编译过程中可以编译通过而不会提示出错。随机输入3个整 数，构成一个测试用例，如t₁-t₈所示。分别输入这8个测试用例，测试用例 的运行剖面如图1右侧所示。其中，黑色实心点表示相应测试用例运行时经 过了该语句。t₁和t₂为运行失败的测试用例，用符号F进行标示，t₃-t₈为成 功测试用例。

图2展示了本发明方法的使用流程。主要包括拆分成功测试用例和集 成多重语句排位结果两个操作，图中SBFL表示一种基于谱的软件错误定位 方法，排位表表示对待测程序中所有可执行语句按照计算出的可疑度值大小 进行从高到低的排序。

图3列举了用于验证本专利所提方法定位效果的实验程序的详细信息。 其中，代码行数表示待测程序的代码规模；版本数表示待测程序中植入的不 同类型错误的数量（每个版本中都只植入了一个错误）；类别比例表示待测 程序自带的测试用例集中成功测试用例数目与失败测试用例数目的比值。例 如，Siemens程序包中的tcas程序，它的代码行数是141行，包含41个错 误版本，类别比例为159.31：1。

图4给出了各算法在Siemens程序包上整体定位效果提升对比实验的 实验结果。图中数据是在对图3所示的Siemens程序包全部141个错误版本 进行实验后统计得到的。从左手侧起，第一列表示代码的检查代价；第二列 是对同一行中从第三列起至最后一列的数据求平均值；在第三列至最后一列 中，正数表示相应的基于谱的软件错误定位方法在采取拆分-集成操作后相 比没有采取该操作之前定位精度获得提升，反之，负数表示定位精度降低， 零表示定位精度没有发生改变。例如，对于Jaccard算法，当检查5%的代码 量时，采取拆分-集成操作后，算法定位精度提升了9.38%。

图5给出了各算法在space、flex和grep程序上整体定位效果提升对比 实验的实验结果。图中数据是在对图3所示的space、flex和grep程序总共 76个错误版本进行实验后统计得到的，具体数据解释与图4类似。

图6给出了各算法在单个独立程序上定位效果提升对比实验的实验结 果。图中数据是在对图3所示的10个独立程序分别进行实验后统计得到的， 具体数据解释与图4类似。

具体实施方式

假定待测程序中含有若干个缺陷，通常测试之前这些缺陷是未知的。首 先对原始测试用例集中的成功测试用例进行拆分，并与失败测试用例配对， 构成新的类别均衡的子测试用例集。然后依次加载子测试用例集，运行插桩 后的程序，记录程序的执行信息。基于谱的软件错误定位方法将利用这些执 行信息计算语句的可疑度，并将所有可执行语句按照可疑度值从高到低排列， 生成子排位表。最后，根据前面得到的多重计算结果，调用集成公式，为每 个可执行语句计算总可疑度，合成综合排位表，程序人员最终根据该排位表 来查找错误代码。

为了检验本专利中所提方法的定位效率，考虑把Siemens程序包、space 程序、UNIX程序包中的flex和grep程序（这些程序都是公认的典型测试对 象。其中，后三个为实际应用程序）作为实验对象，这些待测程序中的错误 位置、错误数量和错误类型都是事先已知的。图3显示了所有待测程序的详 细信息。

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

第一步对原始测试用例集中的成功测试用例进行拆分。现共有8个测试用 例，它们分别是t₁（1,0,2）、t₂（2,1,2）、t₃（0,1,1）、t₄（0,1,2）、t₅（1,1,1）、 t₆（1,1,2）、t₇（1,1,0）和t₈（2,2,3）。其中，t₁和t₂为失败测试用例，t₃-t₈为成功测试用例。可以将成功测试用例拆分成份，例如P₁（t₃,t₄）， P₂（t₅,t₆），P₃（t₇,t₈）；

第二步成批复制失败测试用例，与拆分好的每份成功测试用例配对。将失 败测试用例t₁和t₂整体复制3份，并将其与拆分好的成功测试用例配对， 构成3个新的类别均衡的子测试用例集，即S₁（t₁,t₂,t₃,t₄）、S₂（t₁,t₂,t₅,t₆） 和S₃（t₁,t₂,t₇,t₈）；

第三步依次输入类别均衡的子测试用例集，生成相应子排位表。该步骤又 分为三小步：

(一)收集子测试用例集运行时程序谱的执行信息。当输入子测试用例集 S₁时，针对程序中的所有可执行语句s₁-s₁₃，分别统计a_ef，a_nf，a_ep和a_np这四个参数，记录的数据如下所示：

  a_efa_nfa_epa_nps₁2 0 2 0 s₂2 0 2 0 s₃2 0 2 0 s₄2 0 1 1 s₅1 1 1 1 s₆1 1 0 2 s₇1 1 0 2 s₈0 2 1 1 s₉0 2 1 1 s₁₀0 2 0 2 s₁₁0 2 1 1 s₁₂0 2 0 2 s₁₃2 0 2 0

同理，当运行子测试用例集S₂和S₃时，记录的数据分别为：

  a_efa_nfa_epa_nps₁2 0 2 0 s₂2 0 2 0 s₃2 0 2 0 s₄2 0 1 1 s₅1 1 1 1 s₆1 1 0 2 s₇1 1 0 2 s₈0 2 1 1 s₉0 2 1 1 s₁₀0 2 0 2 s₁₁0 2 1 1 s₁₂0 2 0 2 s₁₃2 0 2 0

和

  a_efa_nfa_epa_nps₁2 0 2 0 s₂2 0 2 0 s₃2 0 2 0 s₄2 0 1 1 s₅1 1 1 1 s₆1 1 0 2 s₇1 1 0 2

s₈0 2 1 1 s₉0 2 1 1 s₁₀0 2 0 2 s₁₁0 2 1 1 s₁₂0 2 1 1 s₁₃2 0 2 0

(二)计算语句可疑度。针对上一步中得到的子测试用例集S₁-S₃运行时程 序谱的执行信息，选择33种基于谱的软件错误定位方法中任何一种进 行计算，本次操作只以典型的Tarantula算法为例加以演示。根据公式 可得语句s₁-s₁₃的可疑度分别为：

注：在计算过程中，一旦遇到无法计算出数值且a_ef＝0（失败测试用例 运行时没有覆盖到相应语句）的情况时，按照基于谱的软件错误定位 方法所基于的假设，认为该语句不可疑。因此在算法设计中，通常将 该可疑度赋值为相应算法可疑度计算范围的下限值，这里以N/A加以 表示。

(三)生成子排位表。根据计算出的语句可疑度，可以得到子排位表L₁= L₂=<{s₆,s₇},s₄,{s₁,s₂,s₃,s₅,s₁₃},{s₈,s₉，s₁₁},{s₁₀,s₁₂}>， L₃=<{s₆,s₇},s₄,{s₁,s₂,s₃,s₅,s₁₃},{s₈,s₉，s₁₁,s₁₂},s₁₀>，语句s₄在各子排位表 中的排位R₁(s₄)=R₂(s₄)=R₃(s₄)=3；

第四步集成多重排位结果，合成综合排位表。针对第三步中得到的3种计算 结果，利用公式来计算总可疑度。可得 $\bar{T}\left(s_1\right)=\bar{T}\left(s_2\right)=\bar{T}\left(s_3\right)=1,$$\bar{T}\left(s_4\right)=1.4,$$\bar{T}\left(s_5\right)=0.5,$$\bar{T}\left(s_6\right)=\bar{T}\left(s_7\right)=1,$$\bar{T}\left(s_8\right)=\bar{T}\left(s_9\right)=0,$$\bar{T}\left(s_{10}\right)=N/A,$$\bar{T}\left(s_{11}\right)=0,$$\bar{T}\left(s_{12}\right)=N/A,$$\bar{T}\left(s_{13}\right)=1.$综合排位表为 L=<s₄,{s₁,s₂,s₃,s₆,s₇,s₁₃},s₅,{s₈,s₉,s₁₁},{s₁₀,s₁₂}>，语句s₄在综合排位表中的排位 $\bar{R}\left(s_4\right)=1.$

第五步根据得到的综合排位表，依次返回源程序对应位置处进行检查，直到 找出与错误相关的语句为止。在本例中，当检查综合排位表中排在第一位的 语句s₄时，就可以辅助程序开发人员迅速找到存在错误的代码。

对图3所列举的待测程序运用本专利方法进行错误定位，并选取 Tarantula算法（典型算法）、Jaccard算法、Ochiai算法（这两种算法被证 明能取得较好的定位效果）、Ochiai2算法（作为Ochiai算法的对比算法）、 Wong3算法（唯一有参数的算法）、Wong2算法（Wong3算法的对比算法）、 Euclid算法、Hammann算法（与Wong2算法计公式相似，作为Wong2的对 比算法）、Zoltar算法和Harmonic算法（这两种算法计算公式最复杂）作 为实验对象。此外，引入Expense作为算法定位效果的评价标准。其中，