摘要 针对程序切片方法不提供语句的可疑程度描述，而覆盖分析方法不能充分分析程序元素间的相互影响等问题，提出上下文统计分析的软件故障定位方法。首先，将源程序转换为抽象语法树和程序依赖图；接下来，插桩程序，收集运行时信息；然后，根据失效点，执行按需的反向动态切片，确定失效产生的上下文；最后，对于反向动态切片中的节点，统计计算可疑度，输出带可疑度排序的动态程序切片。该方法不但描述了失效产生的上下文，还计算上下文中各个语句的可疑度。实验结果表明，所提方法与单一的覆盖分析方法相比，平均Expense降低了1.3%，与单一的切片方法相比，平均Expense降低了5.6 %，所提方法可以有效辅助开发人员定位与修正软件缺陷。
关键词 软件调试；故障定位；动态切片；覆盖分析；失效上下文
中图分类号 TP311.5
文献标志码 A
0引言
软件的自动化调试在当今越来越复杂的软件设计和开发的过程中日渐显露了其不可替代的重要性。如果软件开发人员能够将代码调试和排错这一个工作交由计算机程序来自动地完成，势必会大大地减少软件开发人员工作量，从而提高软件开发的工作效率。
软件故障定位[1]是软件的自动化调试中一个重要环节。由计算机分析程序源代码或用测试用例执行程序的运行时信息，检测程序中的异常情况，并将其独立出来作为需要进一步调试的可疑代码，从而将与软件失效无关的代码自动过滤掉，缩小缺陷代码的搜索范围。本文提出失效上下文统计分析的软件故障定位方法，辅助开发人员更快地定位和理解软件缺陷。
1相关研究
软件故障定位方法可划分为
覆盖分析（coverage analysis[2-5]、程序切片（program slicing[6-7]、依赖分析（dependence analysis[8]、模型检验（model based[9]、变异分析（mutation based[10]等。其中，覆盖分析方法因具有计算复杂度低、实现简单等优点得到了广泛的研究。程序切片作为一种最早提出的应用于软件调试的技术也发表了为数众多的论文。
覆盖分析方法对比失效执行和成功执行的程序元素（如语句、谓词、分支、基本块的覆盖信息，定位可疑代码。主要思想是如果某个程序元素被较多的失效执行覆盖，却很少被成功执行覆盖，则该程序元素很可能含有缺陷。这种方法通常包含如下步骤
首先，执行测试用例，收集测试用例执行过程中的覆盖信息（即哪些程序元素被执行，以及测试用例的执行结果（成功/失效。然后，统计分析失效执行和成功执行的程序元素覆盖信息，采用预先定义的度量公式，计算各个语句的可疑度，并将语句按照可疑程度由高到低排序，可疑度越高、排序越靠前则越可能是缺陷语句。各种覆盖分析方法一般都遵从上述步骤，主要区别在于采用的度量公式不同。Naish等[4]用模型和实验评价了36种采用不同度量公式的覆盖分析方法证明尽管有些方法度量公式不同，但是在可疑语句排序目的上是等价的。 覆盖分析方法的优点是提供语句的可疑程度描述，并且计算复杂度低，适于分析大规模程序。存在的主要问题是通常只能揭示统计关联，而不能充分分析程序元素间的相互影响，开发者很难通过单独检查给出的可疑语句来理解与修正软件缺陷。
程序切片是一种对程序的结构进行分析的技术，主要包括静态切片和动态切片。静态切片方法通过静态分析源程序，根据依赖信息识别可能影响程序中某个位置的变量值的语句集合。动态切片方法仅对当前输入生成的程序执行路径进行分析，识别实际影响给定程序执行点的变量值的语句集合。动态切片方法还可以分为反向动态切片和前向动态切片。在某个程序点的变量的反向动态切片包括影响该变量值的所有执行语句。在某个程序点的变量的前向动态切片，则包括被该变量值影响的所有执行语句。由于动态切片将可疑语句集合的判断范围缩小至给定输入相关的执行，这就在一定程度上弥补了静态切片冗余和计算量大的缺点。动态程序切片方法的优点是关注对特定程序点变量产生了影响的语句，描述了失效产生的上下文，开发人员可以通过程序切片的结果更有针对性地对程序进行分析排查，缺点是不提供语句的可疑程度描述，并且切片规模仍然可能很大，导致在切片中观察程序行为的代价较大。
第3期
王克朝等：失效上下文统计分析的软件故障定位方法
计算机应用 第35卷
2失效上下文统计分析框架
基于以上分析，本文提出失效上下文统计分析的故障定位方法并开发故障定位工具，使之既可充分分析失效产生的上下文，又可以计算语句可疑度，指导定位缺陷语句。
失效上下文统计分析框架如图1所示。
图片
图1失效上下文统计分析的软件故障定位框架
输入源程序和测试用例集合。根据程序执行测试用例的实际输出结果与预期输出结果是否一致，可以将测试用例分为成功和失效两类。
输出带可疑度排序的动态程序切片，将其用于辅助程序开发人员定位软件缺陷及理解软件失效产生的上下文。
1首先解析源程序，将其转换为中间表示形式，创建抽象语法树和分析静态控制依赖和数据依赖。
2在抽象语法树的基础上插桩程序，然后用测试用例执行程序，收集并存储用于后续故障定位中的运行时信息。
3对于失效测试用例，根据失效点执行按需的反向动态切片，分析静态控制依赖和数据依赖信息及动态执行信息，确定失效产生的上下文，即哪些指令的执行会影响失效点及其控制依赖和数据关系，生成失效执行的动态反向切片。 []
4对于失效执行的动态反向切片中的节点，统计分析成功测试用例集对其的覆盖信息，进而用统计公式（Tarantula等计算各个节点的可疑度，并按可疑度由高到低的顺序排序。最后输出带可疑度排序的动态程序切片，不但描述失效产生的控制流和数据流，还给出上下文中各个语句的可疑度排序。
3关键技术
3.1程序的中间表示
抽象语法树是一棵多叉树，是源代码的抽象语法结构的树状表现形式，每个树节点表示源代码中的一种抽象结构。
创建抽象语法树的过程如下：首先执行词法分析，根据预先用正则表达式定义的模式字符串，使用自动机识别源程序中的字符，生成Token
串，其中每一个Token都与源代码中的一个基本单元对应，如关键字、标识符、注释和运算符等。然后执行语法分析，利用LALR（Look Ahead Left Right derivation语法分析表，尝试将Token串与规则进行匹配，如果匹配成功，就会按照规则的相关定义，将Token串归约为节点，并最终形成抽象语法树。
由于抽象语法树的节点与语言的抽象结构是一一对应的，因此便于对程序进行分析，此外对于任意一棵抽象语法树，都可以反向生成相应的源代码，因此本文基于抽象语法树执行插桩，进行静态控制依赖和数据依赖分析[11]，用于后续的程序切片过程中。
定义1控制依赖。如果语句s2的执行是由语句s1表示的谓词在执行时确定的，那么s2控制依赖于s1。
定义2数据依赖。如果有一条从语句s1到语句s2的路径，且存在一个在s2中定义并在s1中使用的变量，且该变量在从s1到s2的路径上其他任何地方没有被重新定义，则称s2数据依赖于s1。
3.2程序插桩
程序插桩（Program Instrumentation技术是在保证原程序的逻辑和功能不变的基础上，向源代码中插入一些探针语句，用来在程序执行时捕获程序的运行时数据。
本文对待测试程序的插桩，是在抽象语法树的基础上完成的。遍历抽象语法树，识别需要插入探针语句的位置和需要跟踪保存的信息。根据探针语句插入的位置不同，跟踪不同的执行信息，包括：
1跟踪基本块退出点，在每个基本块结束点插入指令，当基本块结束执行时在执行信息文件中创建一条记录，用于确定执行了哪些分支和语句。
2跟踪加载/存储的值的内存地址，用以后续分析变量的定值和引用，反向查找影响加载变量值的语句，确定动态数据依赖。
3记录函数调用和返回信息，用于匹配函数调用的形参和实参、主调函数和被调函数的返回值。
最后将插入探针语句的抽象语法树反向生成程序代码，即得到插桩后的程序。编译并用测试用例执行插桩后的程序，便可生成并保存以上执行信息。
3.3失效执行的动态反向切片
动态反向切片的相关定义如表1所示。失效执行的动态反向切片跟踪程序的执行，然后查找执行过程中直接或者间接影响失效点的语句集合。
基本思想是：跟踪失效执行，对于触发失效的程序执行点，解析失效执行信息，反向推导在执行中可以通过数据流或者控制流影响该失效点的语句，构成反向切片。为了降低计算复杂度，采用按需的方式计算失效点的反向切片，不创建完整的动态依赖图，仅根据需要查询计算失效点控制流和数据流相关的动态反向切片的路径。
动态数据依赖的计算方法：对于每条静态单赋值语句，直接根据静态数据依赖信息分析反向查找影响该语句的节点；对于其他加载的值，分析内存执行信息查找对应的存储语句，即所存储的值被加载的变量使用；对于函数调用返回值和形参，利用函数调用-返回执行信息进行查找和映射。
表格（有表名
表1动态反向切片的相关定义
定义名称定义内容
执行实例程序P包含多个程序语句，对于输入I，每条语句在P的执行过程中可以执行多次。语句s的第i次执行，记为sith，称为语句s的第i次执行实例
失效点在失效执行中，如果执行实例sith是第一个没有满足期望的执行实例，则sith执行实例称为失效点。
对于崩溃型失效，失效点是第一次观测到崩溃的程序点；对于非崩溃型失效，失效点是第一次输出与期望输出不一致的程序点
动态数据依赖语句n的执行实例nith数据依赖于语句m的执行实例mjth，记为nith→mjth，当且仅当存在变量α，mjth定值了α，然后α 的值被nith使用
动态控制依赖语句n的执行实例nith控制依赖于语句m的执行实例mjth，记为nith→mjth，当且仅当mjth是谓词语句，并且nith执行与否由节点mjth中的谓词决定
动态依赖图一个程序在输入I时执行的动态依赖图DDG（N，E，I由节点集合N和有向边的集合E构成，其中节点ni∈N对应于输入I时，语句n的第i次执行的实例，边nith→mjth是语句n的执行实例nith对语句m的执行实例mjth的动态数据依赖或动态控制依赖
动态切片给定输入I的动态依赖图DDG（N，E，I，nith∈N的动态切片DS（nith是DDG（N，E，I的子图，该子图包含了nith以及nith可达的所有其他节点和边
DS（nith=（{nith}，{ee=nith→mjth∈E}∪（∪nith→mjthDS（mjth
动态控制依赖的计算方法：当把动态执行的基本块中的语句加入到反向切片时，首先采用静态控制依赖分析确定哪些语句会控制该基本块的执行，将其加入候选集合中。然后在候选集合中，分析基本块的执行信息，准确查找最近执行的语句，将其加入反向切片中。
3.4带可疑度排序的动态程序切片
统计动态反向切片中语句可疑度的算法如下。
程序前
输入：失效测试用例的动态反向切片DS
输出：带可疑度排序的动态程序切片RDS
1 SC = StatementCoverage（DS；
//用例覆盖信息统计DS语句的成功测试
2 SuspiciousMetric（SC，DS
//计算DS各语句的可疑度
3 RDS←Rank（DS
// 根据可疑度给DS中语句排序
4 输出RDS
程序后
首先根据动态执行信息，对动态反向切片中的各个节点，统计成功测试用例集合的语句覆盖信息，即每个节点被成功测试用例覆盖的次数。
接下来，利用统计分析度量公式结算各个节点的可疑度。采用了三种代表性的度量公式——Tarantula、Wong、Optimal，计算公式分别见式（1、（2、（3：
Tarantula=（aefaef+anf/（aefaef+anf+aepaep+anp（1
Wong=aef-aep（2
Optimal=-1，anf>0
anp，其他 （3
其中：aef是语句被测试用例集合中失效测试用例执行的次数，anf 是语句没有被测试用例集合中失效测试用例执行的次数，aep是语句被测试用例集合中成功测试用例执行的次数，anp是语句没有被测试用例集合中成功测试用例执行的次数。
然后，按照可疑度由高到低对各个节点进行排序。
最后，输出带可疑度排序的动态程序切片，给出了程序执行的控制依赖和数据依赖上下文描述，并统计分析了具体节点的可疑度。
4示例程序和应用分析
使用图2中的示例程序m
id[5，10]说明本文方法。程序mid的功能为
输入3个整数，然后输出这3个整数的中间值。
本文在mid的基础上给出了一个含有缺陷的示例程序P1（图2左侧部分，包含一个赋值缺陷，将语句s9“m=x”修改为“m=y”。
测试用例集T={t1，t2，t3，t4，t5，t6}（图2右侧部分第2、3行测试用例的成功/失效状态p表示测试用例执行成功，f表示执行失效。对于P1而言，成功测试用例集Tp={t1，t2，t3，t4，t5}，失效测试用例集Tf={t6}。
图2右侧表格中的数字表示测试用例集T执行程序P1的语句覆盖信息，即如果执行测试用例tk时，语句si被执行，则si和tk对应的单元格数值为1；否则为空白。
当用t6测试示例程序P1，发现在语句s15处输出错误的m值，因而将s15确定为失效点，对其执行动态反向切片的节点集合为
Backward（t6，m@s15={s15，s9，s8，s6，s5，s1}。
最后创建带可疑度排序的动态程序切片如图3所示。根据可疑度（采用Tarantula公式，查找最可疑语句s9，并通过反向跟踪控制依赖和数据依赖，可以清楚地分析和理解缺陷语句s9的上下文。
图片
图3带可疑度排序的动态反向切片
基于本文方法，开发了辅助调试工具。界面如图4所示，既可应用于工业软件还可以应用于学生程序的辅助调试。
调试辅助工具被应用于分析在软件错误定位实验中广泛应用的Siemens基准测试组如表3所示。用式（4Expense度量错误定位技术的精度，即调试人员找到缺陷语句需要查看程序代码的工作量大小，它是缺陷语句在定位结果中的可疑度排序rank（sbug和程序语句集合S的可执行代码行数∑sexecutable∈Ssexecutable的比值。Expense值越小则说明定位的精度越高，即调试人员只需查找较少代码就能找到缺陷位置。
Expense=rank（sbug∑sexecutable∈Ssexecutable×100%（4
图片
图4软件调试辅助工具界面
表格（有表名
表3Siemens基准测试组
程序错误版本数测试用例总数描述
print_tokens74130词法分析
print_tokens2104115词法分析
replace325542模式替换
schedule92650优先级调度
schedule2102710优先级调度
tcas411608高度间隔
tot_info231052信息测量
采用了Tarantula度量公式计算语句可疑度，实验结果表明，本文方法与单一的覆盖分析方法相比，平均Expense降低了1.3%，这是因为本文方法只统计程序切片中语句的可疑度，删除了其他与失效不相关的语句。此外，本文方法还可以输出失效产生的控制依赖和数据依赖上下文，更有利于理解失效的产生原因。 []
本文方法与单一的切片方法相比，平均Expense降低了5.6%，这是因为本文方法在切片的基础上，进一步进行了语句可疑度统计排序，将缺陷语句排在了靠前的位置，因此可以优先检查缺陷语句。
综上所述，本文方法比单一的切片方法和覆盖分析方法更便于开发人员定位和理解软件缺陷。
5结语
本文提出了失效上下文统计分析的软件故障定位方法，并开发了软件调试辅助工具。克服了已有切片方法不提供语句的可疑程度描述，而覆盖分析方法不能充分分析程序元素间的相互影响等问题，便于开发人员更快地定位和理解软件缺陷。
后续工作将进一步改进故障定位算法，例如考虑多错误情况、将测试用例优选与定位结合[12]提高故障定位的有效性等。
