基于信息流的关键软件缺陷定位技术

周东红，石 柱，王 瑞，李 沫

（中国航天系统科学与工程研究院，北京100048）

基于信息流的关键软件缺陷定位技术

周东红，石 柱，王 瑞，李 沫

（中国航天系统科学与工程研究院，北京100048）

针对软件因涉及多程序要素间相互作用而来的复杂缺陷，研究了基于信息流的关键软件缺陷定位技术，对现有的信息流进行了扩展，并对经典方法的可疑度度量公式进行了改进，而且将其融入了相关算法；并进行了与语句覆盖、分支覆盖和定义使用对覆盖等缺陷定位技术的对比试验，结果表明：此方法比基于语句覆盖、分支覆盖和定义使用对覆盖的方法更可靠、更精确，能高效率地定位软件中的缺陷。

软件测试；复杂缺陷；信息流覆盖；语句覆盖；分支覆盖；定义使用对覆盖

1　引言

由于软件的原因而导致的航空航天事故很多，其中由于软件中存在整数溢出的缺陷而导致的事故，就有欧洲Ariane5火箭在发射时爆炸和Comair航空公司机组调度软件崩溃等［1］。

据统计，在软件研发和后期维护的成本中，软件测试占到了50%～75%［2］。其中在测试中发现软件缺陷，对缺陷进行检测定位和修正的调试过程是最困难且成本最高的步骤之一。传统的测试工作一般由软件测试人员手动完成，耗时耗力。

本文研究了基于信息流覆盖的缺陷定位技术，并基于该技术设计了一个缺陷定位的原型工具，通过该工具能快速地找到软件的缺陷，有效提高缺陷定位的效率。

2　基于动态信息流覆盖的缺陷定位技术

本文中所使用的算法，是动态信息流分析的前向计算（forward computing）算法［3］，本章介绍了该算法的一些基本定义和扩展研究，并说明了如何基于该方法进行缺陷定位。

2.1 动态信息流

2.1.1 动态控制依赖

假设活动表示一个可执行语句（或基本块），则执行路径就是活动的一个序列。路径T上的第k个活动表示为T（k）或sk（s为对应的语句或基本块）。“判断活动”是指语句s是分支判断语句的活动sk。子路径T（k，m）表示的是一条从活动T（k）开始到活动T（m）结束的子序列［1］。动态控制依赖关系的形式化定义如下［3］：

定义1：假设sk和tm是执行路径T上的两个活动（k＜m且sk是判断活动），当且仅当子路径T（k，m）证明了t直接控制依赖于s（t DCD s）时［4］，活动tm直接动态控制依赖于活动sk，表示为tmDDynCDsk。活动tm直接动态控制依赖的判断活动如果存在，则它是唯一，表示为DDynCD（tm）。

其中DCD的含义为语句能通过它的控制分支决定是否执行语句。直观来看，DDynCD（tm）就是先于活动tm最后出现的判断活动。

2.1.2 动态数据依赖

建模活动之间的动态数据依赖时，需要将下面两个集合与每个活动联系起来［5］：在活动sk中定义（或赋值）的变量或对象集D（sk），和在sk中使用（或引用）的变量或对象集U（sk）。

定义2：假设sk和tm是执行路径T上的两个活动（k＜m）。当且仅当（D（sk）∩U（tm））-D（T（k+1，m-1））≠φ时，活动tm直接动态数据依赖于活动sk，表示为tmDDynDDsk［5］。活动tm直接动态数据依赖的活动集表示为DDynDD（tm）。

直观看来，tmDDynDDsk表示的是tm使用（或引用）了最后由sk进行定义（或赋值）的变量或对象。2.1.3 直接影响和影响

另外，本文还引用了其他三种活动间的动态依赖关系［6］：

1）函数使用了一个由return语句返回的值；

2）函数使用了一个由形式化参数传递的值；

3）函数的请求调用方法指令中存在控制依赖。

对于两个活动sk和tm（k＜m），当且仅当活动tm在上述的5类依赖关系中依赖于活动sk时，就认为sk直接影响tm［7］。直接影响tm的活动集表示为DInfluence（tm），简称为DInf（tm）。

“影响”关系则表示一个语句能影响到其他语句的执行，包含直接和间接影响［1］。

定义3：假设T为一条执行路径，sk和tm为T中的两个活动（k＜m）。当且仅当在T中存在着活动序列a1，a2，……，an，其中a1=sk，an= tm，并且对于i=1，……，n-1，都有aiDInfluenceai+1，则有sk“影响”tm，表示为skInfluence tm。影响tm的活动集表示为Influence（tm），简称为Inf（tm），计算公式如公式（1）：

2.1.4 动态信息流分析

动态信息流分析是确定在活动sk中影响了其他变量或对象的所有变量或对象的集合［1］。

定义：设T为一条程序执行路径，sk和tm为T中的两个活动（k＜m），设x和y是两个变量：活动sk定义了变量x并且活动tm使用了变量y。当且仅当skInfluence tm时，存在着从活动sk中的变量x到活动tm中的变量y的信息流，该信息流表示为（sk，x，tm，y）［9］。目标为tm内的y变量的信息流中包含的变量和对象集合如式（2）：

式中，U（tm）是活动tm中使用了的变量或对象的集合，U（Inf（tm））则是影响tm的活动中使用了的变量或对象的集合。

信息流实例的表示方法为四元组（sk，x，tm，y），其中sk表示最后定义或使用了源对象x的活动，tm表示最后定义或使用了目标对象y的活动。

2.1.5 信息流及其长度

信息流的长度，定义为它包含的动态数据依赖链和控制依赖链的长度［10］。我们规定信息流长度的计算规则如下：如果tm使用了对象x，则长度为1；否则，长度就是最短依赖链的长度，而且信息通过该依赖链从对象x流入到对象y。这样，通过综合考虑信息流及其长度就能区分两个有着完全相同的源和目标但长度不同的信息流了。很明显，通过这些信息还是不能区分两个有完全相同的源、目标和长度的信息流。

2.2 对动态信息流的扩展

动态信息流分析能够识别程序运行时程序对象之间的信息流，但是现有的研究中，没有考虑分支和定义使用对，在源和目标处的依赖关系是条件语句、返回语句和方法请求时，不能捕获该信息流。因此，需要对动态信息流技术进行扩展，使其包含定义使用对和分支，从而可捕获上述的依赖关系。标准的信息流格式为（sk，x，tm，y）［9］，其中sk表示最后定义了源对象x的活动，tm表示最后定义了目标对象y的活动。而通过引入分支和定义使用对，如果源或目标为返回语句或条件判决语句时，就用‘-'号作为对象名。如表1中就有扩展的信息流（7，-，8，ch），这里第7条源代码为条件判断语句，所以其对象名应为‘-'。

2.3 语句可疑度度量标准

信息流f可疑度的计算可采用式（3）［10］：

式中，%P（f）运行过程包含信息流f的成功测试用例个数与总的成功用例数的比值；%F（f）运行过程包含信息流f的失败测试用例个数与总的失败用例数的比值。

但是，仅仅根据这个公式进行可疑度排序是不够的。例如给定两个信息流f1和f2，其中%F（f1）=0.1，%F（f2）=1.0，%P（f1）=%P（f2）=0。如果使用公式（3），会得到SF1（f1）= SF1（f2）=1.0。但是根据%F（f1）=0.1和% F（f2）=1.0，可以判断出f2的可疑度高于f1。为解决这个问题，本文引入了第二个度量值SF2=%F（f）。使用这个度量值，就能判断出f2的可疑度高于f1。

综合考虑度量值SF1和SF2，基于信息流的缺陷覆盖技术就可以使用式（4）所示的度量准则：

较高的SF（f）值意味着较高的可疑度排列。当两个信息流的SF值相同时，规定较短的信息流可疑度较高。而程序语句的可疑度值就是包含该语句的全部信息流中SF值最大的信息流的可疑度值。最后根据程序语句的可疑度值降序排列所有程序语句。

3　算法实现

本章用图1的案例演示如何实现该算法。该程序中出错的程序语句为S6，正常情况下，power［0］的值应该为128，但是程序中会是-128。这样当输入的8位二进制数的最左边一位为1时，结果就会出错。

3.1 动态依赖关系实现算法

计算直接动态控制依赖关系（DDynCD）的算法如图2所示，它计算动态信息流，能同时应用于结构化的和非结构化的程序中。该算法中用到的数据结构是栈CDSTACK（m），该栈存储影响范围还没有完全退出的判定活动。当执行到了栈顶元素的ipd（s）时，程序就认为退出了判定活动Sk的动态领域，此时从栈CDSTACK（m）中弹出活动Sk。

图1　示例程序代码Fig.1 Code of the typical example program

表1　示例程序的信息流覆盖信息Table 1 Information flow coverage information of the example program

算法主要分为四步：

1）如果被访问的路径结点为判断结点时，将该结点入栈CDSTACK（m）；

2）如果被访问的结点是栈顶元素的直接后控制结点，则将该栈顶元素出栈CDSTACK（m）；

3）如果栈不为空，则当前结点直接动态控制依赖于栈CDSTACK（m）的栈顶元素；如果栈为空，则当前结点直接动态控制依赖的顶点为空；

4）如果当前访问结点的直接后控制结点与栈顶元素的直接后控制结点相同，则将栈顶的判断结点出栈CDSTACK（m）（目的是为了限制栈的大小）。

按上述算法，可以得到图1中的程序在执行路径T=＜S1，S2，S3，S4，S5，S6，S5，S6，S5，S6，S5，……＞的DDynCD关系，如表2所示，它与直接使用DDynCD关系的定义得到的结果相同。

3.2 动态依赖关系实现算法

动态信息流分析和动态切片算法如图3所示。算法在执行程序时对每个活动tm频繁地使用公式（2），计算完成后存储计算结果以便随后使用。因为该算法是前向算法，当输入活动为活动tm时，算法计算时所有需要使用的值应该都已经计算得到并且可用。

在动态信息流分析算法中，并集操作对算法性能有着很大的影响。假设程序中语句的数量为m、活动对象的数量为n、用于实现并集的集合元运算（如添加、包含等）需要单位时间成本。则在最坏的情况下，计算活动tm的动态信息流的时间复杂度为O（n2）（包含计算该活动之前所需要的时间）；此时，信息流从每个对象流入到其他所有的对象、并且所有的活动对象都对tm有直接影响。此时并集操作涉及n个子集，每个子集有n个对象。另外，最坏的情况下，计算活动tm的动态切片［6］的时间复杂度为O（n*m）（包含计算该活动之前所需要的时间），此时，所有n个活动对象的每一个切片都包含m个程序语句、并且所有的活动对象都对tm有直接影响。此时并集操作涉及n个子集，每个子集有m个对象。

图2　计算直接动态控制依赖的算法Fig.2 DDynCD algorithm

表2　控制流图1中执行路径T对应的DDynCD关系表Table 2 Relationship of trace T in CFG of Fig.1 with DDynCD

图3　动态信息流分析和动态切片算法Fig.3 InfoFlow algorithm and DynSlice algorithm

对图1所示的程序设计了6个测试用例，其输入分别为T1=00000000、T2=00001111、T3= 01010101、T4=01101101、T5=11111111、T6= 10101010，其中前4个执行通过，T5和T6执行失败。通过使用图3的算法对其分析，可得如表1所示的信息流覆盖信息。表1中，信息流InF1=（6，powers［0］，10，decimal），InF2=（6，powers［0］，11，decimal），InF3=（6，powers［6］，10，decimal），InF4=（6，powers［6］，11，decimal），InF5=（6，powers［5］，10，decimal），InF6=（6，powers［5］，11，decimal），InF7=（8，ch，9，-），InF8=（10，decimal，11，-），InF9=（7，-，8，ch），InF10=（2，decimal，10，decimal），R*为可疑度值高于或等于出错语句可疑度值的语句数。

4　试验评价

4.1 试验概述

本文选择SIR的西门子测试套件的TCAS软件作为被测对象，TCAS（Traffic Alert and Collision Avoidance System，交通警戒和避撞系统）是一套被航空公司采用的飞机碰撞检测和回避系统。

4.2 试验数据

对试验中使用的软件进行了修改，注入了5个缺陷，注入情况如表3所示。

表3　TCAS软件中注入的缺陷Table 3 The seeded defects in TCAS program

表4　TCAS软件的测试结果Table 4 The test results of TCAS program

4.3 试验结果

为了说明方法的有效性，将结果与标准的语句覆盖技术［11］、分支覆盖技术和定义使用对覆盖技术［12］得到的结果进行对比。使用中共设计了172个测试用例。

测试结果如表4所示，其中S*max为用相关方法计算所有语句的可疑度值中的最大值，S*为用相关方法计算得到的出错语句可疑度值，R*为可疑度值高于或等于出错语句可疑度值的语句数，RS-*为用对应的方法排查软件缺陷时需要人工核查的程序语句数。

从表4中的F2可以看到：

1）172个测试用例中，有36个运行失败。

2）出错语句的SS和SB值均为0.93，与最大值1.0都有些差距，这意味着一些正常的语句会比出错语句更可疑。另外，出错语句的SDU值为空，因为这里没有定义使用对。但是该语句的SF和SFmax均为1.0。这证明了信息流覆盖比其他的技术要更可靠。

3）测试人员按排列顺序核查到出错语句时，使用语句覆盖技术需要多检查63条程序语句，使用分支覆盖技术时是31条，使用信息流覆盖技术时则为8条。使用定义使用对技术时更是需要检查所有的程序语句。这一结果证明了信息流覆盖技术要更加精确。

试验结果表明，信息流覆盖技术比语句覆盖技术更可靠、更精确。在所有数据中，它的可靠性都高于其他三种技术，虽然个别缺陷上它的精确性不如分支覆盖或定义使用对覆盖技术，但是从平均数上看，它的精确性优于其他三种技术。

5　结论

本文研究了基于信息流覆盖的缺陷定位技术，并基于该技术设计了一个缺陷定位的原型工具，通过该工具能快速地找到软件的缺陷，提高缺陷定位的效率。通过试验证明了该方法比语句覆盖、分支覆盖和定义使用对覆盖更有效。试验结果表明，在一些案例中信息流覆盖的性能要优于分支覆盖和定义使用对覆盖技术，而且在所有的数据中其性能都要优于语句覆盖技术；在可靠性方面，它在所有的数据中都要优于其他三种技术。

（References）

［1］Masri W，Podgurski A.Algorithms and tool support for dynamic information flow analysis［J］.Information and Software Technology，2009，51（2）：386-404.

［2］Hailpern B，Santhanam P.Software debugging，testing，and verification［J］.IBM Systems Journal，2002，41（1）：4-12.

［3］Shchekotykhin K，Friedrich G，Fleiss P，et al.Interactive ontology debugging：Two query strategies for efficient fault localization［J］.Web Semantics：Science，Services and Agents on the World Wide Web，2012（12）：88-103.

［4］Sahoo S K，Criswell J，Geigle C，et al.Using likely invariants for automated software fault localization［J］.ACM SIGARCH Computer Architecture News，2013，41（1）：139-152.

［5］Weiser M.Program slicing［C］//Proceedings of the 5th international conference on Software engineering.IEEE Press，1981：439-449.

［6］Korel B，Laski J.Dynamic program slicing［J］.Information Processing Letters，1988，29（3）：155-163.

［7］虞凯，林梦香.自动化软件错误定位技术研究进展［J］.计算机学报，2011，34（8）：1411-1422.YU Kai，LIN Mengxiang.Advances in automatic fault localization techniques［J］.Chinese Journal of Computers，2011，34（8）：1411-1422.（in Chinese）

［8］Masri W.Fault localization based on information flow coverage［J］.Software Testing，Verification and Reliability，2010，20（2）：121-147.

［9］Masri W，Podgurski A，Leon D.detecting and debugging insecure information flows［C］//Piscataway，NJ：IEEE Press.2004.198-209.

［10］Masri W，Podgurski A，Leon D.An empirical study of test case filtering techniques based on exercising information flows［J］.IEEE Transactions on Software Engineering，2007，33（7）：454-477.

［11］惠战伟，黄松，嵇孟雨.基于程序特征谱整数溢出错误定位技术研究［J］.计算机学报，2012，35（10）：2204-2214.HUI Zhanwei，HUANG Song，JI Mengyu.Research on spectra-based integer bug localization［J］.Chinese Journal of Computers，2012，35（10）：2204-2214.（in Chinese）

［12］Yu K，Lin M，Gao Q，et al.Locating faults using multiple spectra-specific models［C］//Proceedings of the 2011 ACM Symposium on Applied Computing.ACM，2011：1404-1410.

The Critical Defect Localization Technique Based on Information Flow in Software

ZHOU Donghong，SHI Zhu，WANG Rui，LI Mo
（China Academy of Aerospace Systems Science and Engineering，Beijing 100048，China）

The complex defects imposed by the interactions among many program elements in the software are difficult to exclude.To solve this problem，the critical software fault localization techniques based on information flow coverage were studied.The present information flow was extended and the suspicious metric formula of the classical methods was improved and incorporated into the related algorithm.Then comparative tests were conducted with the defect localization techniques including the statements coverage，branches coverage and define-use pair coverage methods.The experiment results showed that this method could efficiently locate the software defects and was more precise and reliable than the other methods.

software test；complex defect；information flow coverage；statement coverage；branch coverage；define-use pair coverage

TP311

A

1674-5825（2016）05-0635-06

2015-06-30；

2016-06-29

周东红（1981-），男，硕士，工程师，研究方向为软件工程软件缺陷定位。E-mail：19781970@qq.com