基于输入参数特征谱的软件缺陷定位方法

摘要

本发明涉及一种基于输入参数特征谱的软件缺陷定位方法，基于程序输入参数特征谱的软件缺陷定位方法。使用了程序输入参数特征谱和执行切片信息进行软件缺陷定位。对程序参数特征谱进行分析时，为了得到更加精确的结果，将每个参数域划分为多个子域进行统计分析。执行切片信息主要用来构建程序执行依赖图，这是对传统SBFL方法的有效补充。本方法与已有的缺陷定位方法相比，可以有效提高缺陷定位的准确性至少10%以上。此外，该方法给缺陷修复者提供可疑语句的同时，提供了导致该语句可疑的参数和可疑区间，这些信息非常有助于缺陷的快速修复。

说明书

技术领域

本发明属于软件工程技术领域中的软件缺陷定位技术，特别涉及一种基于输入参 数特征谱的软件缺陷定位方法。

背景技术

随着信息技术的飞速发展，计算机软件已经渗透到社会的各个领域，为了确保软 件质量，实施大量的软件测试是软件开发中重要的步骤。测试中常常需要对所发现的 软件缺陷进行定位，传统的软件缺陷定位通常都是设置断点、重新执行错误代码，检 查程序状态的变化，这样不断迭代缩小查错的范围，直至识别出可疑的程序实体。由 于该过程需要耗费大量的资源，因此软件缺陷定位被视为软件测试中最昂贵和最耗时 的工作之一，见文献J.A.Jones and M.J.Harrold.Empirical evaluation of the tarantula automatic  fault-localization technique.In20th IEEE/ACM International Conference on Automated Software Engineering, ASE2005,pp.273–282.。如何提高缺陷定位的效率和准确度成为一个重要的问题，研究人 员已经提出了多种自动化的错误定位技术以解决该问题。现有的自动化软件错误定位 方法可分为七类，见文献W.E.Wong and V.Debroy.A survey of software fault localization.Technical  report,The University of Texas at Dallas,2009.，其中基于切片和基于程序特征谱的方法是两种 最广泛应用的方法。

切片技术是最早提出的一种缺陷定位技术。假设给定一个程序P，一个可疑语句s 以及其中的一个变量v，切片就是影响s中的v值的语句集合，也就是切片会去除与v 值无关的部分，这样可以缩小可疑程序实体的搜索空间。切片技术可以分为静态切片、 动态切片以及执行切片。由于动态切片与具体的软件错误执行关系密切，大部分研究 人员主要关注动态切片，但收集动态切片需要更多的时间和相关文件。对于一个给定 测试用例，执行切片即是将执行测试用例时所经过的各种覆盖信息转化成另一种格式 的信息。由于执行切片信息的易获取性，文献H.Agrawal,J.R.Horgan,S.London,and W.E.Wong. Fault localization using execution slices and dataflow tests.Proceedings of the6th International Symposium on  Software Reliability Engineering,ISSRE1995,pages143–151，文万志,李必信,孙小兵,齐珊珊.基于条件执 行切片谱的多错误定位.计算机研究与发展,2013,50(5):1030–1043.的研究中都使用执行切片代替了 动态切片。然而，切片通常都比较大，其所包含的噪声信息可能会降低缺陷直接相关 的信息的重要度。文献文万志,李必信,孙小兵,齐珊珊.基于条件执行切片谱的多错误定位.计算机研究 与发展,2013,50(5):1030–1043.，W.Z.Wen.Software fault localization based on program slicing spectrum.In  201234th International Conference on Software Engineering,ICSE2012,pages1511–1514.中将切片技术与 其他缺陷定位技术相结合（如程序特征谱定位），取得了较好的定位效果。

程序特征谱，也被称为程序光谱/程序行为特征，是程序执行特征的统计信息，例 如语句覆盖、定义使用对覆盖、控制覆盖等信息。基于程序特征谱的缺陷定位方法 (Spectrum-Based Fault Localization,SBFL)，通常假设失败的测试执行会表现出异常的 程序行为特征，所以成功执行和失败执行中的行为特征的差异可以用于指导缺陷定位。 Jones等人在文献J.A.Jones,M.J.Harrold,and J.Stasko.Visualization of test information to assist fault  localization.In24th International Conference on Software Engineering,ICSE2002,pages467–477.中作了大 量的实验，结果表明程序出现异常的行为特征未必意味着代码中存在故障，但是错误 的程序运行往往会表现出异常的行为特征。在SBFL中，可疑度计算公式是判定某程 序实体是否可疑的重要依据。目前已有超过三十种不同的SBFL中的可疑度计算公式， 例如Tarantula,Ochiai,Wong等，见文献：1、J.A.Jones,M.J.Harrold,and J.Stasko.Visualization  of test information to assist fault localization.In24th International Conference on Software Engineering, ICSE2002,pages467–477.，2、R.Abreu,P.Zoeteweij,and A.J.C.Van Gemund.An evaluation of similarity  coefficients for software fault localization.In12th Pacific Rim International Symposium on Dependable  Computing,PRDC2006,pages39–46,2006.3、W.E.Wong and Y.Qi.Effective program debugging based on  execution slices and inter-block data dependency.Journal of Systems and Software,79(7):891–903,2006。Xie 等人用理论证明和实验验证了这些可疑度计算公式，结果表明对于程序中仅有一个缺 陷的情况下，有五种方法效果比较好，并将它们分为两个等价组：ER1(Naish1,Naish2) 和ER5(Wong1,Russell&Rao,and Binary)，见文献X.Y.Xie,T.Y.Chen,F.C.Kuo,and B.W.Xu. A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization.Acm Transactions on  Software Engineering and Methodology,22(4):40,2013.：。Naish等人在文献L.Naish,H.J.Lee,and K. Ramamohanarao.A model for spectra-based software diagnosis.Acm Transactions on Software Engineering and  Methodology,20(3),2011中的实验中发现ER1组方法平均优于ER2组方法。不同的程序特 征谱包括可以用于定位不同类型的错误，也有研究[11,12]将多种不同特征谱进行不同 策略的组合后用于缺陷定位取得较好的定位效果，见文献1、R.Santelices,J.A.Jones,Y.Yu, and M.J.Harrold.Lightweight fault-localization using multiple coverage types.In200931st International  Conference on Software Engineering,ICSE2009,pages56–66.IEEE Computer Society.；2、K.Yu,M.Lin,Q. Gao,H.Zhang,and X.Zhang.Locating faults using multiple spectra-specific models.In26th Annual ACM  Symposium on Applied Computing,SAC2011,pages1404–1410.。

现有的基于程序特征谱的缺陷定位方法有效提高了定位的效率和准确度，然而我 们发现测试用例作为SBFL方法的重要输入信息之一，其所包含的数据中还蕴藏着很 多对软件缺陷定位有价值的知识。传统SBFL方法没有充分考虑程序本身固有的依赖 信息，从而使错误定位的精度受限。因此，将测试用例数据的特征谱分析结果与执行 切片信息进行结合，将会有效提高缺陷定位的准确性。

发明内容

要解决的技术问题

为了避免现有技术的不足之处，本发明提出一种基于输入参数特征谱的软件缺陷 定位方法，充分利用程序输入参数信息提高缺陷定位的准确性。

技术方案

一种基于输入参数特征谱的软件缺陷定位方法，其特征在于步骤如下：

步骤1：将每一个数值型参数的域进行区间离散化，将其划分为多个子域；所述 数值型参数包括每个值本身就是一个子域的离散型数值，以及连续性数值；

所述连续性数值的区间离散化，以下述公式计算出每个子域的步长Steplength以及 每个子域i的取值区间，得到若干个子域，

$[\mathrm{Min}+i*\mathrm{Steplength}-\frac{\mathrm{Steplength}}{2},\mathrm{Min}+i*\mathrm{Steplength}+\frac{\mathrm{Steplength}}{2}]$

其中：Max和Min表示参数取值的最大值和最小值，|D|表示测试用例的个数，N 是常量，表示每个子域包含参数取值个数的期望值；

步骤2：以每个参数Pi在每个子域中的相关执行结果failed/passed统计信息作 为输入参数特征谱，根据可疑度计算公式得出可疑度最大的参数以及其所对应的可疑 度最大的子域区间：

所述可疑度计算公式：

${\mathrm{Density}}_j=\frac{{\mathrm{fail}}_j}{\mathrm{fail}}$

${\mathrm{Sensitivity}}_j=\frac{{\mathrm{fail}}_j/{\mathrm{total}}_j}{\mathrm{fail}/\mathrm{total}}$

Suspiciousness_j=Density_j×Sensitivity_j

Suspiciousness=Max(Suspiciousness_j)

其中：fail表示执行失败的测试用例个数，total表示所有的测试用例个数，j表示 该参数的第j个子域，fail_j表示第j个子域中执行失败的测试用例个数；Density表示 失败密度，Sensitivity表示失败敏感度，Suspiciousness表示可疑度；

步骤3：构建程序超级执行依赖图PSEDG；首先针对每个测试用例构建其程序依赖 图，然后将所有测试用例的程序依赖图进行叠加构成PSEDG；

步骤4：以第2步得到的可疑度最大的参数为图搜索的起点，在PSEDG中搜索可 疑实体集合SSPN；

步骤5：执行一种基础SBFL方法，得到一个按照可疑度降序排列的可疑实体列表；

步骤6：采用下式计算每个可疑实体e最终的可疑度susp^e_SPRank，进而给出一个最 终的降序排列的可疑实体列表；

${{\mathrm{susp}}^e}_{\mathrm{SPRank}}=\frac{1}{2}{{\mathrm{susp}}^e}_{\left(\mathrm{basic}\right)}+\frac{1}{2}\times \mathrm{flag}\times \mathrm{Max}\left({\mathrm{susp}}_{\left(\mathrm{basic}\right)}\right)$

其中：flag表示e是否更加可疑的标识符，当e∈SSPN时，flag为1；否则flag 为0；susp^e_(basic)为第5步中基础SBFL方法计算出的实体e的可疑度，Max(susp_(basic))表 示第5步计算得到所有实体上可疑度中的最大可疑度。

有益效果

本发明提出的一种基于输入参数特征谱的软件缺陷定位方法，——基于程序输入 参数特征谱的软件缺陷定位方法(Suspicious Parameter Rank,SPRank)。该方法使用了 程序输入参数特征谱和执行切片信息进行软件缺陷定位。对程序参数特征谱进行分析 时，为了得到更加精确的结果，将每个参数域划分为多个子域进行统计分析。执行切 片信息主要用来构建程序执行依赖图，这是对传统SBFL方法的有效补充。

本发明的有益效果是：从程序输入参数特征谱的角度，提供一种新的方法对数值 型软件缺陷进行定位，综合考虑了程序测试用例中的输入数据信息和测试用例的执行 切片信息。将该方法应用于软件缺陷定位领域的代表性数据集Siemens套件中TCAS 程序进行实验，实验结果表明，该方法与已有的缺陷定位方法相比，可以有效提高缺 陷定位的准确性至少10%以上。此外，该方法给缺陷修复者提供可疑语句的同时，提 供了导致该语句可疑的参数和可疑区间，这些信息非常有助于缺陷的快速修复。

附图说明

图1为SPRank方法整体流程示意图；

图2为示例程序mid.c的第1个参数的输入特征谱分析的结果示意图

图3为SPRank方法的第三步中，构造的PSEDG的示意图，图中顶点的圆圈中的 数字表示程序代码的行号；

图4为SPRank方法的第四步中，在PSEDG中可疑实体的搜索算法图；

图5为示例程序mid.c的程序清单，以及SPRank法和Tarantula法的对比实验结 果；

图6为示例程序mid.c的5个测试用例，以及相关的执行覆盖信息。

具体实施方式

现结合实施例、附图对本发明作进一步描述：

对于某个给定的程序，假设该程序有N个输入参数，分别为P1,P2,…,Pn，每个参 数对应的输入域为D1,D2,…,Dn。假设构造了一个测试用例集T={T1,T2,…,Tm}对该程 序进行测试，每个测试用例的执行结果为Failed或者Passed。此处，将每个参数P在 每个子域中的相关执行结果统计信息称为输入参数特征谱。本发明SPRank方法所采 用的技术方案包括以下步骤：

1.对每一个数值型参数的域进行区间离散化。对于离散型数值，每个值本身就是 一个子域。对于连续性数值，采用等距法将每个参数的域划分为若干个子域。根据下 面的公式可以计算出每个子域的步长。其中，Max和Min表示参数取值的最大值和最 小值，|D|表示测试用例的个数，N是常量，可手动设置，表示每个子域包含参数取值 个数的期望。

根据下面的公式可以计算出第i个子域的取值区间。

$[\mathrm{Min}+i*\mathrm{Steplength}-\frac{\mathrm{Steplength}}{2},\mathrm{Min}+i*\mathrm{Steplength}+\frac{\mathrm{Steplength}}{2}]$

2.针对每个参数，统计该参数在每个子域中的输入参数特征谱信息，根据可疑度 计算公式得出各个参数的可疑度及其所对应的最可疑子域区间。对某个参数P_i，以下 公式中的j表示该参数的第j个子域。最终根据预定的可疑度阈值判定参数的可疑性。

Density_j＝fail_j/fail

${\mathrm{Sensitivity}}_j=\frac{{\mathrm{fail}}_j/{\mathrm{total}}_j}{\mathrm{fail}/\mathrm{total}}$

Suspiciousness_j=Density_j×Sensitivity_j

Suspiciousness=Max(Suspiciousness_j)

3.构建程序超级执行依赖图(Program Super Execution Dependency Graph, PSEDG)。该图是由测试用例执行后的执行覆盖信息构建而成，同时包括控制覆盖和数 据的定义使用对覆盖信息。PSEDG图是有一个有向图，其中图中的顶点为所有执行覆 盖信息中出现的程序实体，图中的边表示实体之间的依赖关系。

4.以第2步得到的可疑参数为入口点，在PSEDG中搜索可疑实体集合S_SPN。具 体的搜索算法如图3所示。

5.执行任意一种基础的SBFL方法，例如Tarantula，得到一个按照可疑度降序排 列的可疑实体列表。

6.针对第5步中得到的可疑实体列表中的每个实体，计算每个实体最终的可疑度， 进而给出一个最终的可疑实体列表。对某个程序实体e，已根据基础SBFL方法计算 得到的可疑度为susp^e_(basic)，在此基础上叠加第4步中搜索得到的可疑实体集合产生 的效应后，得到新的可疑度susp^e_(SPRank)。具体的计算公式如下：

${{\mathrm{susp}}^e}_{\mathrm{SPRank}}=\frac{1}{2}{{\mathrm{susp}}^e}_{\left(\mathrm{basic}\right)}+\frac{1}{2}\times \mathrm{flag}\times \mathrm{Max}\left({\mathrm{susp}}_{\left(\mathrm{basic}\right)}\right)$

当e∈S_SPN时，flag为1；否则flag为0。Max(susp_(basic))表示基础SBFL方法在所 有实体上的最大可疑度。

具体实施例如下：

针对给定的一个程序P和测试用例集T，本发明对该程序P进行缺陷定位的具体 过程如下：

1.针对待测程序P，执行测试用例集T中的所有有效测试用例，获取每个用例执 行经过的语句覆盖、控制覆盖和定义使用对覆盖信息。这些执行覆盖信息可以借助其 他的辅助工具获取，例如WET等。

2.采用等区间法或者单点值法将每个参数的域划分为若干个子域。例如对某个连 续数值型参数P_i，遍历所有的测试用例，得到该参数在整个域中的最大值、最小值、 值的个数（去除重复值），假设每个子域中的值的个数是常量，则可以计算出子域的个 数、步长以及每个子域的取值区间。实际实验中，取该常量为40。

例如图2所示的图为mid.c程序的第1个参数的子域划分图。该测试用例集中共 有500个有效测试用例，这些测试用例在第1个参数的取值中，最大值为74836，最 小值为-74836，假设期望每个子域包含40个数据，则可以将整个域划分为约为13个 区间，每个区间的步长约为12472.67。

3.计算每个参数的每个子域中缺陷密度和缺陷敏感度，进而计算该区域的可疑 度。取子域可疑度大于预订阈值的为该参数的可疑度，并且该子域区间为最可疑区间。 实验中取阈值为1.5。

例如对于图2中mid.c的第1个参数的第4个区间，缺陷密度：0.563，缺陷敏感 度：3.967，区间可疑度：0.563*3.967=2.233。同理，计算其他各个区域的可疑度。将 所有参数的可疑度都计算完毕后排序，若该值大于预订的阈值1.5，则认为该参数可疑， 即找出了可疑参数以及该参数的可疑区间。该例中，第4个区间可疑度最高，且区间 可疑度>1.5，则参数1为可疑参数，其区间可疑度即为其第4个区间的可疑度。其余 参数的区间可疑度均未达到阈值1.5，在该例中仅有参数1是可疑参数。

4.根据测试用例集T中每个测试用例的执行覆盖信息，构建执行依赖图PSEDG。

例如对于图5所示的一个简单例子程序mid.c，测试用例集T中有5个测试用例， 具体的测试用例以及执行后的相关的覆盖信息如图6所示，根据图6可以画出图3的 PSEDG图。

5.在上步构建的PSEDG中搜索可疑实体，具体搜索算法如图4所示。整体是广 度优先的搜索，具体是：以第3步中找到的可疑参数所在的行号为入口开始搜索，将 直接依赖于该可疑参数的结点作为初始集合和初始搜索结果集合。然后将直接或者间 接依赖于该初始集合中的元素的结点不断并入搜索结果集中，直到该搜索结果集合中 元素个数到达原PSEDG图元素个数的半数时，停止搜索。

6.执行一种基础的SBFL方法，例如Tarantula，按照下面的公式计算每个程序实 体e的可疑度，得到一个按照可疑度降序排列的可疑语句列表，其中可疑度大于一定 阈值的称为可疑语句。

$\mathrm{susp}\left(e\right)=\frac{\mathrm{failed}\left(e\right)/\mathrm{totalfailed}}{\mathrm{passed}\left(e\right)/\mathrm{totalpassed}+\mathrm{failed}\left(e\right)/\mathrm{totalfailed}}$

图5中列举了mid.c程序的Tarantula方法的可疑度计算值，图5的例子中，生成 了500条测试用例，三个参数的取值都在[-74836,74836]之间。最终的Tarantula方法 的可疑度计算都是根据这500个测试用例的语句覆盖信息进行的。

7.按照SPRank的可疑度计算公式，计算第6步中得到可疑程序语句列表中每条 语句的最终可疑度。

对于图5所示的mid.c程序，利用Tarantula方法计算每条语句的可疑度，进而计 算得到所有可疑度非零的语句的最大可疑度Max(susp_TA)是0.6202。图5的实验结果表 明，采用了SPRank方法得到的可疑语句排名中，真正出错语句的排名更高，这意味着 开发人员可以更早，更容易的找到程序代码中的错误。