动态程序分析技术在错误定位中的应用

陈伟

（四川大学计算机学院，成都 610065）

动态程序分析技术在错误定位中的应用

陈伟

（四川大学计算机学院，成都 610065）

错误定位是软件调试过程中的一个关键问题。为了降低调试成本，辅助开发人员定位和修复程序错误，基于动态分析的错误定位技术通过选择测试用例，运行待测程序，跟踪并分析程序执行过程及结果，给出造成错误的程序缺陷在源代码中的可能位置。归纳总结基于动态分析的错误定位领域的相关成就，并且从故障性质研究、多方式结合和新技术引入研究三方面展望基于动态分析的错误定位技术的发展趋势，并进行总结。

程序分析；错误定位；软件调试；程序依赖关系

0 引言

在工业界，为了能确保软件的质量，他们在测试和维护中投入了不少的精力。在整个软件开发周期中，测试和维护所需要的成本比例非常之高，而在测试和维护过程中，调试是其最困难的一部分，而错误定位又是调试阶段中耗费最大的一步。所以，通过改进在定位过程中的任何一方面都可以在一定程度上降低调试的开销。根据定位过程“是否需要运行软件”为准则，错误定位技术可以分为基于动态的和基于静态的，基于动态分析的错误定位（Dynamic Analysis-Based Fault Localization，DABFL）是指开发者设计测试用例，并根据设计的测试用例去并运行程序，然后根据程序的执行轨迹和行为特征信息给出错误的可能位置。

本文同时采用文件计量法和文献综述法，根据提出的有关该领域的几个需要回答的问题，然后确定关键字以及检索策略进行文献检索，接着根据筛选原则对检索得到的论文进行筛选，然后对筛选过后剩下的论文进行数据提取和分析，最后形成报告。然后主要对基于动态分析的错误定位技术所涉及到的一些方法和模型进行归纳总结，并根据现有的研究情况，对未来动态程序分析技术在错误定位中的应用研究趋势进行展望。

1 文献计量分析

文献计量法总共分为五步：确定研究范围、抽取样本、界定分析单元、对分析单元做量化统计和建立反应其趋势变化的规律总结。

1.1 检索方案

首先确定三个研究问题：1）现有错误定位技术有哪些？2）动态程序分析技术在错误定位中的应用有哪些？3）基于动态程序分析的错误定位方法的研究趋势是什么？然后确定关键词：程序分析（Program Analysis）、动态程序分析（Dynamic Program Analysis）、错误（故障）定位（Fault Localization），接着在关键论文数据库中进行文献检索，检索年限为2004-2016年。然后对检索得到的论文根据一定的原则进行筛选和去重。最后得到有关错误定位的文献有200多篇，这200多篇作为文献计量统计的输入数据。而文献综述只选择其中的一部分重要参考文献进行综述。我们对得到的200多篇文献通过工具进行分析，得到了一些客观的分析结果。

1.2 结果分析

（1）年限分析

对采集到的论文的年份、数量特征进行统计分析，可以在一定程度上根据文献的增长情况得到近12年间关于“程序分析在错误定位中的应用”研究的总体研究水平和发展速度。通过分析可知，自2004年以来关于“程序分析在错误定位中的应用”的研究文献数量大致呈现上升趋势。2004至2008关于此项研究的文献相对比较少，数量波动也不是很大；2009年数量相比2008年，论文数量增加了一倍多，然后继续呈现一个上升的增长趋势，一直到2016。

（2）期刊分布和载文比

论文的期刊分布和载文比可以在一定程度上反映出一段时期内该领域研究的成熟度。因此，对“程序分析在错误定位中的应用”研究论文的期刊分布和载文比进行统计分析可知，自2004年以来，刊载程序分析研究论文的期刊数量大致呈现逐年增长的趋势，刊载种数的增加，说明研究涉及的领域越来越多，分布更加广泛。

（3）期刊类型分布

对刊载论文的期刊类型分布进行分析，可以了解到“程序分析在错误定位中的应用”研究的主要集中在哪些类型的期刊，从另外一个方面也能看到该研究领域发展到了哪一个程度。我们对搜集到的200多篇论文进行期刊类型分布统计，得知在期刊分布上还比较分散研究论文主要集中在Conference Paper和Journal Article上，占据总论文数量的69.88%。其次是在Conference Proceeding和Thesis，分别占据22.89%和7.23%。

（4）作者分析

作者分布情况可以体现在该领域研究的广度以及深度。作者数越多，说明该研究领域越广，某一个作者出现的频次越高，说明该作者在这个领域研究得比较深入。通过对搜集到的论文进行作者分布统计（包含第一作者，第二作者，第三作者），共有600多名作者参与该领域的研究，对出现频次比较高的作者进行统计，发现Zhang,Zhenyu、Wong,W.Eric、徐宝文名列前三。

（5）关键词分析

我们对搜集到的200多篇论文中的关键词进行统计分析，共获得956个关键词，对这些关键词进行频度统计，按照频次高低排序所得的前3位高频词的统计结果是Fault Localization、Program Debugging和Debugging。统计结果显示，错误定位也叫做故障定位、错误诊断或缺陷定位，主要应用在程序调试程序测试中。从关键词的频度可以看出，动态程序分析技术（这里指自动化调试）主要技术是统计分析（Statistical Analysis）和程序切片分析（Program Slicing）。

2 基于动态分析的错误定位方法

2.1 轻量级错误定位方法

在轻量级错误定位方法中，我们只关注覆盖信息，程序实体之间的依赖关系一般不涉及，然后使用统计方法或数据挖掘的方法进行信息的处理。根据故障定位方式等信息，轻量级错误定位方法可以分为基于执行覆盖（Coverage-Based Fault Localization，CBFL）和基于模型(Model-Based Fault Localization，MBFL）两大类。

（1）基于执行覆盖的错误定位方法

①基于语句或基本块

Renieres和Reiss[1]提出了一种程序光谱对比的错误定位方法，在程序测试过程中，首先假设其存在很多个成功的执行和一个失败的执行，然后根据距离准则来选择一个和失败运行最相似的成功运行的程序光谱，最后根据光谱差异性来分离程序缺陷。Jones和Harrold等人[2]认为，如果一个程序实体被大部分的失败用例执行过，那么就应该被考察，于是提出了Tarantula错误定位方法，于此同时，他们开发了一个工具原型，通过故障可疑度来定位错误。

②基于谓词

Liblit等人[3]提出了CBI（Cooperative Bug Isolation）错误定位技术，也被称为Liblit05，是一种基于谓词覆盖的互操作分离故障技术。该技术通过利用谓词的真假取值，然后对比与其后某个错误的出现存在的关联性，于此同时，利用插桩技术来获取谓词的覆盖信息。然后，Zhang等人[4]把短路求值和求值序列考虑在内，通过分析他们之间的关系，提出了一种基于谓词的错误定位方法的DES（Debugging through Evaluation Sequences）改进策略，有效地提高了错误定位的效率。

③基于方法

Dallmeier等人[5]认为在失败执行中，如果某一个类调用了成功执行中不同的方法，那么是不是应该更值得被考察和怀疑，据此他们提出了一种基于方法调用序列的技术，被称为Ample技术。宁国秀等人[6]针对C源程序提出一种基于函数调用路径的数据流分析技术,主要分析程序中的数据流信息,他们结合程序切片，根据函数调用路径，进一步分析数据流的变化，从而定位错误。

（2）基于模型的错误定位方法

①基于统计模型

Liu等人[7]基于参数统计中的分布函数，提出了基于统计模型SOBER的故障定位方法。该方法需要获取谓词在成功失败执行中的取值模式，然后根据该取值模式进行建模，最后根据假设检验原理，进一步具体分析，以此量化谓词在取值上的偏差，并将此偏差结果作为谓词的怀疑度。Yu等人[8]进一步提出了一种错误的定位方法，被称为LOUPE。它可以同时利用到多个模型，根据每个模型适用的情况，来定位不同类型的错误。因为错误类型最开始是不知道的，所以LOUPE方法通过建立了多个模型来获取程序语句的不正常行为和状态信息，然后从上一步获取的信息中选出适合的模型来定位错误。

②基于时间频谱模型

Yilmaz等人[9]利用时间光谱作为程序执行特征的抽象，同时运用了高斯混合模型，对成功执行的时间频谱进行聚类分析，进而对每个类进行高斯分布建模，通过利用时间频谱信息，查找程序函数中隐藏的错误，该方法被称为TWT（Time Will Tell）方法。

③基于程序状态模型

徐宝文等人[10]考虑了值向量，他们认为，待测系统和测试用例可以用值向量来表示，然后对其测试结果和附加测试用例的测试结果进行对比分析，进而寻找错误的可能位置。Delta Debugging方法是由Zeller提出的，该方法能够自动减小程序成功和失败运行过程之间的区别。它采用分治的思想和递归思想，逐渐减小两个集合之间的差异，最终确认成功和失败配置差异的一个最小集。

④基于其他行为模型

Guoshun，Chen等人[11]认为MAS（Multi-Agent System）具有较强的自主性和智能性，同时具有较强的社会能力，容易与软件密集型装备现有的软件测试方案进行集成。于是，他们提出了一种新的基于MAS的故障诊断框架，整个错误诊断系统被分为四部分：System Management Agent(SMA)、Pre-Processing Agent(PPA)、Fault Localization Agent(FLA)和Failure Analysis Agent (FAA)。SMA层直接与用户进行交互，为用户提供软件错误斩断系统的接口，并且与Sevice Agent之间相互合作。PPA层包括了Lexical Analyzer Agent和Syntax Analyzer Agent，它主要的功能就是生成语法树（Syntax tree）。FLA层包括Syntax Tree Analyzer Agent（STAA）和Automatic Instrumentation Agent（AIA）。STAA自动分析源代码的仪器精确度，AIA自动接收STAA的结果，然后插入探测函数，并记录执行信息。FAA层包括了Coverage Analyzer Agent和Query Agent，主要用来实现语句和分支覆盖测试，并自动查询覆盖率是否满足需求，程序是否为目标程序。此框架已应用与真正的软件诊断当中，并且证明了它的有效性。

王克朝等人[12]通过利用插桩，构建了一种程序谱构建模型,通过该模型，可以明显提高源代码的处理效率,该模型中的有穷自动机能够准确识别插桩点，有效提高错误定位的速度。通过实验验证，该技术可以在一定程度上提高错误定位的效率。

2.2 重量级错误定位方法

重量级错误定位方法需要分析程序实体之间的依赖关系，包括数据依赖、控制依赖以及其他依赖关系，于此同时，相对轻量级错误定位方法，它需要耗费更高的时间和空间代价。

（1）基于依赖关系的错误定位方法

Baah等人考虑了程序依赖图，他们在程序依赖图上，通过增加结点和边的概率信息，建立了概率程序依赖图PPDG（Probabilistic Program Dependence Graph），用来反映程序元素之间的的行为。Feng和Gupta等人[13]基于动态依赖图建立基于贝叶斯网络的错误流图EFG （Error Flow Graph）和通用的概率模型。然后基于标准的推理算法从叶节点沿着错误流后向追溯寻找错误可能性最大的可执行语句。

（2）基于程序切片的错误定位方法

早前是由Weiser提出了一种被称为程序切片的概念，它是用来描述影响程序某个执行点上特定变量的语句的集合。Zhang等人[14]提出了一种动态切片错误定位方法，定义切片准则，计算数据切片、全切片和相关切片，进而有效分离出错误相关语句，以此来达到定位错误的目的。另外，通过比较三种单点切片(后向切片、前向切片、双向切片)的不同，他们还提出了一种基于多点切片的错误定位方法。文万志等人[15]为了解决并发程序中数据共享错误定位问题，他们使用关系构造静态并发序列切片和动态并发序列切片，来提高在程序数据共享错误定位上的准确率。

3 结语

软件错误定位方法研究是软件调试过程中的一个热点问题。本文首先对该领域的文献进行了文献计量分析，然后从轻量级和重量级两个角度归纳总结了现有的基于动态分析的错误定位方法，阐述了具有代表性的错误定位技术。我们发现，不涉及程序实体依赖关系，使用统计学方法对程序语句、分支、函数或类等的怀疑度进行计算并排序，进而定位错误的研究成果最多，而需要分析程序实体之间依赖关系的错误定位方法相对较少。研究者多数借助抽象和简化来研究错误定位，从而忽略了故障固有的一些特性。同时采用多种方式相结合的技术也会提高错误定位的效率，例如动态分析和静态分析相结合，不同方法相结合。于此同时，开发者们也开始利用数据挖掘、人工智能、机器学习和神经网络等新技术来进行错误定位，在未来，这些新技术是一个发展趋势，值得深一步的研究。

[1]M.Renieres，S.P.Reiss.Fault Localization with Nearest Neighbor Queries.in Automated Software Engineering,2003.Proceedings. 18th IEEE International Conference on,2003,pp.30-39.

[2]J.A.Jones,M.J.Harrold,J.Stasko.Visualization of Test Information to Assist Fault Localization.in Software Engineering,2002.ICSE 2002.Proceedings of the 24rd International Conference on,2002,pp.467-477.

[3]B.Liblit,M.Naik,A.X.Zheng,A.Aiken,M.I.Jordan.Scalable Statistical Bug Isolation.in ACM SIGPLAN Notices,2005：15-26.

[4]Z.Zhang,B.Jiang,W.Chan,T.Tse,X.Wang.Fault Localization Through Evaluation Sequences.Journal of Systems and Software,vol. 83,pp.174-187,2010.

[5]V.Dallmeier,C.Lindig,A.Zeller.Lightweight Defect Localization for Java.in ECOOP 2005-Object-Oriented Programming,ed: Springer,2005,pp.528-550.

[6]宁国秀,牟永敏,申闫春,张志华.基于函数调用路径的数据流分析错误定位.计算机仿真,2016.

[7]C.Liu,L.Fei,X.Yan,J.Han,S.P.Midkiff.Statistical Debugging:A Hypothesis Testing-Based Approach.Software Engineering, IEEE Transactions on,vol.32,pp.831-848,2006.

[8]K.Yu,M.Lin,Q.Gao,H.Zhang,X.Zhang.Locating Faults Using Multiple Spectra-Specific Models.in Proceedings of the 2011 ACM Symposium on Applied Computing,2011,pp.1404-1410.

[9]C.Yilmaz,A.Paradkar,C.Williams.Time Will Tell:Fault Localization Using Time Spectra.in Proceedings of the 30th International Conference on Software Engineering,2008：81-90.

[10]X.Baowen,N.Changhai,S.Liang,C.Huo-Wang.A Software Failure Debugging Method Based on Combinatorial Design Approach for Testing.Chinese Journal of Computers,vol.29,pp.132-138,2006.

[11]C.Guoshun,M.Sasa,X.Mingfei.A Kind of Software Fault Diagnosing Framework Based on Multi-Agent.in Quality,Reliability, Risk,Maintenance,and Safety Engineering(ICQR2MSE),2012 International Conference on,2012,pp.760-762.

[12]王克朝,李兵,王甜甜,陈京浩.基于插桩技术的程序谱构建方法.科学技术与工程,2014.

[13]M.Feng，R.Gupta.Learning Universal Probabilistic Models for Fault Localization.in Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering,2010：81-88.

[14]X.Zhang,H.He,N.Gupta,R.Gupta.Experimental Evaluation of Using Dynamic Slices for Fault Location.in Proceedings of the Sixth International Symposium on Automated Analysis-Driven Debugging,2005,pp.33-42.

[15]文万志，程实.并发序列切片.科技创新与应用,2015.

Application of Dynamic Program Analysis Techniques in the Fault Localization

CHEN Wei
（College of Computer Science，Sichuan University，Chengdu 610065）

Fault localization is a key research topic in the software debugging.In order to reduce the cost of debugging and assist the developers to locate and repair program faults,dynamic analysis-based fault localization techniques identify possible locations of faults by selecting test case,running programs and analyzing the program’s running process and results.Summarizes the achievements in the field of dynamic analysis-based fault localization,summarizes this technique and discusses its development trend from the view of fault properties,multiple methods combination and new technique.

Program Analysis;Fault Localization;Software Debugging;Program Dependency

1007-1423（2017）05-0034-05

10.3969/j.issn.1007-1423.2017.05.009

陈伟（1991-），男，重庆人，硕士研究生，研究方向为嵌入式测试与开发

2016-11-24

2017-03-10