动态程序分析方法与工具-四川大学

软件学院2010级毕业论文动态程序分析方法与工具 陈伟动态程序分析方法与工具目录动态程序分析方法与工具11.前言21.1研究背景21.2基本概念31.3研究价值和意义41.4研究路线42.研究方法42.1 检索方案42.2 系统文献综述法62.3 文献计量法73. 文献计量分析93.1 年限分析93.2 期刊分布93.3 载文比分析103.4 期刊类型分布113.5 作者分析113.6 关键词分析134.动态程序分析144.1 动态程序分析方法144.2 动态程序分析工具264.3 动态程序分析在软件测试中的应用265.未来研究展望265.1 错误定位新理论和新技术的引入与集成265.2 程序算法检测新的发展形态275.3 软件运行平台的新发展276. 结束语27参考文献27摘要：关键字：程序分析、动态程序分析、文献计量方法1. 前言1.1 研究背景软件是一种十分特殊的人工制品：它是人类“智力活动”的产物，是对客观事物的虚拟反应，是知识的固化和凝练1。迄今为止，软件已有了50多年发展历史，但对于一个给定的软件，我们目前还不能完全了解它的特性。软件分析就是以软件特性为关注点的研究领域。经过这么多年的发展，目前软件生命周期中的许多活动（分析，设计，实现，测试，部署，维护等）都离不开分析技术。尽管软件分析的能力有限，但它仍然是软件领域十分有用的技术。下面将谈到两个概念，“验证”和“确认”。“验证”是要回答“软件制品是否与软件需求规约一致”的问题，而“确认”则是回答“软件的特性是否符合用户需求”。在英文中，“验证”是“Do the thing right”，而用“Do the right thing”来解释“确认”。验证就是所谓的软件分析技术，而确认则是软件测试技术。软件分析包括对文档（需求规约、设计文档、代码注释等）的分析、对运行程序的分析，等等。而程序分析中，根据“是否需要运行程序”为准则，可以将程序分析技术划分为静态分析技术和动态分析技术两大类，本文主要尝试对动态程序分析涉及的主要方法和工具进行总结和归类，并讨论动态程序分析技术在软件测试中的应用和发展。本文总共分为6部分，第一部分是前言，主要对研究背景、涉及到的一些基本概念、研究的价值和意义、研究路线等进行了说明。第二部分主要阐述了本文所涉及到的两种研究方法：文献计量方法和系统文献综述方法。第三部分是根据文献计量方法的策略，对检索到的文献进行具体的分析。第四部分是本文的核心内容，主要总结和归纳现有的动态程序分析技术方法和工具，并讨论了动态程序分析方法和工具在软件测试中的应用。第五部分结合本文所有信息对动态程序分析技术的发展趋势进行展望。最后一部分是结束语，归纳总结了本文的研究思想和路线。1.2 基本概念1) 软件分析软件分析是对软件进行人工或者自动分析，以验证、确认或发现软件性质（或规约、约束）的过程或活动。包括对文档（需求规约、设计文档、代码注释等）的分析、对运行程序的分析，等等。12) 程序分析程序分析是指对计算机程序行为进行自动分析的过程，主要包括静态分析和动态分析两种策略，它是以某种语言书写的程序为对象，对其内部的运作流程进行分析。3) 动态程序分析动态程序分析是通过运行具体程序并获取程序的输出或者内部状态等信息来验证或发现软件性质的过程。4) 静态程序分析静态程序分析是指在不运行软件前提下进行的分析过程。5) 软件测试：软件测试是一组活动，执行这组活动的目的是发现程序中可能存在的潜在错误，验证在指定条件下程序运行的情况，方法则是给出指定的输入和期望的结果，观察实际的运行结果和期望结果之间的差异，从而对软件的执行正确程度做出判断。（IEEE标准610.12-1990中，对软件测试是这样定义的：软件测试是在指定的条件下操作测试系统或组件，观察和记录结果，并对测试系统或组件的不同方面做出评估的过程。）6) 文献计量方法文献计量方法是一种以各种文献外部特征为研究对象的量化分析方法，主要用于科学文献的研究，能够揭示各门学科的发展水平。7) 系统文献综述方法系统文献综述(systematic literature review),简称系统综述,是主要在医学领域和社会学研究领域针对某一个研究性问题开展的基于文献的系统化综述方法,并于2004年引入软件工程领域.系统文献综述的过程包含3个主要的阶段: 制定综述方案、开展综述、形成综述报告。1.3 研究价值和意义为了保证软件开发的质量，业界在软件测试和软件分析阶段投入了大量的人力物力，而动态程序分析在软件分析中扮演着极其重要的角色。本文对动态程序方法和工具进行了分析与总结，并讨论了其在软件测试当中的应用，不仅丰富了自己在该领域中的知识，增长了见闻，同时有利于人们在分析软件特定的质量属性时，选取合适的技术和工具。1.4 研究路线首先提出该领域的几个需要最终回答的问题，然后确定关键字以及检索策略，接着对检索得到的论文进行筛选，然后对筛选过后剩下的论文进行数据提取和分析，最后形成报告。同时，我们借助EndNote文献管理工具对我们检索到的文献进行管理，方便我们阅读和使用。2. 研究方法2.1 检索方案2.1.1 研究问题通过该系统评价最终所要回答的问题,同时可能需要进一步明确所感兴趣的研究方法(intervention)和研究结果(outcome)等其他限定条件. 1) 现有程序分析的方法和工具有哪些？2) 动态程序分析的方法和工具有哪些？ 3) 动态程序分析方法在软件测试中的应用有哪些？ 4) 动态程序分析中有哪些未解决的问题？2.1.2 搜索策略根据所要研究的问题和关键词确定查询语句，并根据查询结果,确定是否需要进行二级查询(比如引入新的关键词或者添加新的论文集和期刊)。 确定关键词：Program Analysis , Software Analysis, Dynamic Program Analysis, Software Testing.逻辑表达式：(dynamic program analysis) AND (method OR tool)；(software analysis OR program analysis) AND (method OR tool) ；(software analysis OR program analysis) AND (software testing); dynamic program analysis;(software analysis) OR (program analysis);运用的搜索引擎为Google, Google Scholar, IEEE Xplore；另外在四川大学图书馆IEEE Digital Library，CNKI数据库，万方数据库，学位论文库、期刊EI和SCI、国际会议论文集中进行检索，检索年限为2004年（包括2004）至2013年。文献资料收集来源一般包括了图书，期刊，报纸以及网络资源。由于图书的出版周期较长并不能有效反应该学科领域的研究进展情况；网络资源丰富而且反应速度最快，但信息噪音最强；报纸资源的研究深度尚浅。因此，本文选择以国内外期刊，会议等作为文献资料的来源。通过检索，经过去重操作，得到相关论文1066篇。2.1.3 筛选方案1) 长文优于短文。对于短文或者Poster,通过DBLP查询作者是否有相关的工作发表在其他地方,若有,则引用相对比较完整的论文,若没有,则将相应的短文或者Poster排除掉；2) 学位论文只要博士论文；3) 期刊只搜EI和SCI论文；4) 国际会议最好是国外国际会议，或主要成员是外国学者；5) 若论文的目的是提出一种形式化验证技术,则将该论文包含进来；若论文的目的不是提出一种形式化验证技术,而是基于已有的一种形式化验证技术提出了新的软件形式化验证技术和方法，则也将该论文包含进来;6) 虽然论文中没有涉及到具体的形式化验证技术,但提出了关于形式化验证技术新的方法论,同样也将这类论文包含进来;7) 同时对于内容重复的文章:同一作者类似的文章发表在多个地方或者一篇综述很好地概括了一系列的相关研究,只选择了那些我们认为更具代表性的文章。通过几轮筛选，最终确定下来的文献有108篇。2.1.4 数据提取和分析 对于检索到的有关程序分析的论文，我们对入选的论文根据提出的问题进行分类、分析和总结。阅读过程中重点提取技术报告数据、专利、软件工具（网站、软件、描述性语言），应用案例、方法等。2.1.5 完成报告在上述工作的基础上完成最终的报告. 2.2 系统文献综述法系统文献综述(systematic literature review),简称系统综述,是主要在医学领域和社会学研究领域针对某一个研究性问题开展的基于文献的系统化综述方法,并于2004年引入软件工程领域.系统文献综述的过程包含3个主要的阶段: 制定综述方案主要进行综述需求分析,明确综述的目的,设计开展综述的规程,以指导后期的文献收集等工作; 开展综述根据综述方案预定的目标,按照综述步骤进行文献收集,主要工作包括确定主要的文献来源、确定收录标准、实现文献质量评价、开展数据抽取与综合; 形成综述报告对于综述进行总结. 图-系统文献综述法框架图如上图，系统文献综述法细致划分可划分为四部分：计划、选择、提取和结果，最后形成系统性的报告。2.3 文献计量法文献计量法是一种以各种文献外部特征为研究对象的量化分析方法，以文献的量为研究对象，以文献文本为基本特征。它是借助文献的各种特征数量，采用数学与统计学方法来描述、评价和预测科学技术的现状与发展趋势的图书情报学分支学科2。下面通过几个方面对它进行介绍：1) 性质上：文献计量分析法的特征在于其输出量必定是量化信息内容，是一种基于数学和统计学的定量分析方法。2) 方法论基础上：文献计量法是以数学和统计学方法论为基础，在其应用过程中再利用推理和比较的方法对文献的分布趋势进行预测。3) 研究对象上：文献计量法研究的对象主要是文献的外部形式特征，只适用于有实体形态的科学文献，比如具有著者、引文、词汇等文献特征的部分。4) 应用领域上：文献计量法是图书馆学、情报学的特殊研究方法，主要用于科学文献的研究，对各门学科都使用。在发展的几十年中，文献计量法的应用领域不断拓宽，其内容包括作者分布规律、文献分散增长规律、引文分析等。通过引文分析，了解学科发展动态；在学科核心期刊测定中的应用，通过统计分析确定核心期刊的范围；在图书情报系统管理领域等情报探索系统研究中也得到广泛应用。5) 研究的侧重点：它侧重于分析文献形式特征的“量”，它从定量的角度分析文献规律，知识间接反映内容的相关关系。研究步骤：确定研究范围，抽取样本，界定分析单元，对分析单元做量化统计，最后根据统计结果建立反映其趋势变化的规律性结论。图-文献计量法研究步骤3. 文献计量分析为了观察整个程序分析领域的研究情况，于是此文献计量分析的样本数据不仅包括了程序分析技术中的动态分析，同时也囊括了静态程序分析相关文献。3.1 年限分析对采集到的论文的年份，数量特征进行统计分析，可以在一定程度上根据文献的增长情况得到近10年间关于“程序分析技术”研究的总体研究水平和发展速度，如图1所示：图1 程序分析研究论文数量变化从图1中可以看出自2004年以来关于程序分析技术的研究文献数量大致呈现上升趋势，2004至2007关于此项研究的文献相对比较少，数量波动不是很大，2008年数量相比2007年产生了骤变，2009至2012文献数量维持着相对较高的水平，并且在2011年达到最高值，而2013数量相对减少。3.2 期刊分布论文的期刊分布和载文比可以在一定程度上反映出一段时期内该领域研究的成熟度。因此，对程序分析研究论文的期刊分布和载文比进行统计分析可知，自2004年以来，共有317种期刊刊载了相关的论文刊载程序分析研究论文的期刊数量呈现逐年增长的趋势，刊载种数的增加，说明研究涉及的领域越来越多，分布更加广泛。图2 程序分析研究论文期刊分布从图2可以看出，刊载程序分析研究论文的期刊种数从2004年到2010年逐年增加，2011有所下降，而2012年，急剧增加，2013年又回到平稳状态。3.3 载文比分析图3 程序分析研究论文载文比情况从载文比（该时段论文总数/该时段的期刊总数）来看，除了2011年载文比达到3.5以外，其他年度载文比斗小于3，特别在2012年，达到最低0.66，这表明程序分析研究论文还没有向一些特定的期刊集中，研究文献在期刊分布上还比较分散，该研究的发展还不够成熟。3.4 期刊类型分布对刊载论文的期刊类型分布进行分析，可以了解到软件分析研究的主要集中在哪些类型的期刊，从另外一个方面也能看到该研究领域发展到了哪一个程度。我们对搜集到的740篇论文进行期刊类型分布统计，如下图。图4 程序分析研究论文刊载期刊类型分布情况根据图4可以看出，程序分析研究论文主要集中在Conference Proceedings和Journal Article上，其次是在Generic和Thesis上，Conference Paper, Patent 和 Web Page上相对较少。3.5 作者分析作者分布情况可以体现在该领域研究的广度以及深度。作者数越多，说明该研究领域越广，某一个作者出现的频次越高，说明该作者在这个领域研究得比较深入。通过对搜集到的论文进行作者分布统计（包含第一作者，第二作者，第三作者），共有2074位作者参与该领域的研究，对出现频次比较高的作者进行统计，列出了前18位作者，如下表。表1 软件分析研究论文作者分布情况表（前23位）位次作者频次1肖庆42Amp33徐宝文24张路25Alzamil, Z.A26Wei, Hua27Bruda, S.D.28De Halleus, P.29Farn, Wang210Ganai, M.K.211Jianguo, Chen212Jie, Zhang213Kroening, D.214Li, J.J.215Ling Dong216Nail, R217Tillmann, N.218Zhiping, Shi219梅宏220Landwehr, J.221赵建华222ValeriyVyatkin223姜淑娟23.6 关键词分析词频分析法师利用能够揭示或表达文献核心内容的关键词或主题词在某一研究领域文献中出现的频次高低来确定该领域研究热点和发展动向的文献计量方法。为了更客观地对软件分析研究领域的研究热点进行分析，我们在搜集到的740篇论文中进行关键词统计分析。我们共获得6187个关键词，对这些关键词进行频度统计，按照频次高低排序所得的前31位高频词的统计结果如表2所示。表2 软件分析研究论文词频统计情况（前31位）位次关键词词频1Formal verification262Software testing Program testing1963Program testing1964Model checking1205Software engineering886Software877Formal specification718System testing689Computer science6710Software quality6411Program diagnostics6312Program verification6213Analytical models5214Computational modeling4915testing4916Application software4917Java4718Software systems4619Programming4520Program analysis4321Software reliability4022Educational institutions3823Automata3724Software tools3625Automatic testing3426Unified modeling language3427Safety3028Embedded systems3029Algorithm design and analysis3030Program debugging2931Performance analysis29统计结果显示，程序分析研究在形式化验证，软件测试，程序测试，模型检测，软件工程等方面研究比较突出。软件分析领域的研究主要集中在软件模型，软件测试，程序分析上。4. 动态程序分析4.1 动态程序分析方法4.1.1 错误定位为了保证软件开发的质量，工业界在软件测试阶段投入了大量的人力物力，其中最耗时代价最昂贵的任务之一就是调试过程，这是指对程序错误进行定位和修正的过程，而错误定位又是软件调试过程中最耗时和困难的一步。所以，错误定位过程中的任何改进都可以在一定程度上降低调试成本。经过多年的研究发展，在软件领域出现了很多检测程序缺陷的技术，本文主要讨论的是基于实际执行的动态定位技术。该技术通过对源程序、测试结果以及各种程序行为特征信息的计算分析，给出造成故障的软件缺陷在源代码中的可能位置，辅助开发人员进行程序错误的定位和修改。经过研究者们的探索，按照使用和操纵的程序执行信息的不同，目前的错误定位方法该技术可以分为3类：基于行为特征对比的方法，基于程序状态修改的方法和基于程序依赖关系的方法3。4.1.1.1 基于行为特征对比的方法程序行为特征同时也被称作程序光谱，是程序执行的统计信息。经过Reps，Harrold等人的实验研究，程序出现异常的行为特征不一定表示代码存在缺陷，但错误的程序运行往往会表现出异常的行为特征。基于行为特征对比的方法假设失败的测试执行会表现出异常的程序行为特征，那么成功执行和失败执行中的行为特征的差异就可以用于指导错误定位。其工作流程如下：首先，根据收集信息类型的需要，对源代码进行插桩并执行程序，收集执行信息。其次，判断每个测试用例的执行结果。接着，解析执行信息，得到执行行为特征。然后，根据给定的模型，建模程序实体的怀疑度（可能出错的程度）。最后，以程序实体排名的方式给出定位结果，将各个程序实体按照怀疑度大小从大到小排列，供开发人员查看3。目前，按照使用的行为特征信息的种类和策略，大致可以分为5类：基于语句或基本块，基于谓词，基于方法，基于定义使用对或信息流以及行为特征信息精炼的方法。1) 基于语句或基本块2003年，Renieres和Reiss提出NNQ（Nearest Neighbor Queries）方法，假设存在一个失败的执行和很多成功的执行，然后根据距离准则挑选出一个程序光谱和失败运行最相似的成功运行（即失败执行的最近邻居），进而比较它们光谱的不同之处以分离软件错误。与NNQ不同，Jones 和 Harrold 提出的Tarantula法，认为只要是主要被失败用例执行的程序实体就值得被怀疑，同时，它也能容忍出错的程序实体偶尔被成功用例执行。他们使用常用的信息来辅助错误定位，包括每个测试用例的执行结果，程序实体（语句，分支或函数等）被每个测试用例覆盖的信息以及程序的源代码。对于程序实体e，它的怀疑度计算公式为：其中，failed(e)和passed(e)分别表示失败用例和通过用例执行程序实体e的个数，|Tf|和|Tp|表示测试组件中所有失败用例和通过用例的个数。e的怀疑度取值范围从0到1，数值越大，出错的可能性越大。开发人员可以按照怀疑度从大到小的顺序审查源代码。不同于NNQ和Tarantula这些基于直观或启发式的计算方法，Wong等人提出了一个定义良好的统计方法Croaatab. 它利用覆盖信息和测试结果为每条可执行语句w构建一个交叉表，进而计算卡方统计量和列联相关系数M(w)。语句w的怀疑度定义如下：然后，Hao等人提出应该考虑测试用例的相似性，并消除相似的测试用例对于定位结果的影响，于是提出了一种名为SAFL（Similarity Aware Fault Localization）的方法。最后，Naish等人总结了30多种基于语句的定位方法，首先构造了一段名为ITE2（If-Then-Else-2）的程序，然后在这个程序中讨论各种情形。这个程序可以用于刻画错误定位中的两种重要场景：存在“噪声”和信号“微弱”。基于在ITE2代码模型上的分析，他们提出了两种Optimal metric, 语句s的怀疑度定义如下：Yingqi等人结合程序切片和贝叶斯方法来实现错误定位4。首先，我们根据切片的标准执行动态切片，然后根据贝叶斯理论计算后验概率。最后，我们把后验概率作为语句的怀疑程度按照从大到小的顺序进行排列。此方法被应用于6个开源项目，通过实验，此方法在一定程度上可以提高错误定位的精确度。统计错误定位技术通过执行大量的测试用例来预测程序错误的位置，相关研究表明，通过测试用例数量和失败测试用例数量之间失衡的程度可能会降低这种技术的有效性，然而，在实践中失败的测试用例往往小于通过的测试用例。于是Yichao等人提出了一种策略5，通过克隆失败测试用例适当的数量以达到通过测试用例的数量，最终产生平衡的测试组件。分析表明，通过开展克隆两个具有代表性错误定位技术的有效性可以在一定条件下得到改善。随着研究的发展，很多研究者开始探究多故障检测技术。Cheng，Gong等人提出了一种有效的机制用于检测多个故障6，当一个故障被检测到时，我们用它来解释我们观察到的故障，同时更新指标（在检测可疑序列时的一种准则），以判断在程序中是否存留其他故障。实验证明这个方法不仅提高了单故障定位器的效率，同时在很大程度上避免了放弃单故障检测器而开发多故障检测器时的无效的工作与努力。针对动态程序切片，Hofer等人提出了一种技术7，可以减少包含在动态切片中的语句数目，这种技术是基于约束的计算，并且允许从不太可能是错误的根本原因的切片中移除语句。实验结果表明，在有关切片中得到的片段的数量，平均降幅超过28%。由于测试覆盖信息不能识别那些程序实体，而这些实体的执行影响了输出，于是便削弱了实体之间的相关性。Yan，Lei等人为解决这个问题8，提出了一项新的统计故障定位技术。该统计方法是利用一组测试运行的程序切片来捕捉在输出结果中程序实体执行的影响，并且利用统计分析来衡量程序实体故障的可疑度。此外，他们还提出了一种近似后向动态切片的新切片方法，以此来平衡切片的尺寸和精度，并将此切片方法应用于统计方法。实验表明，在两个标准的基准测试下，我们的统计方法明显优于其他8个具有代表性的故障定位方法。2) 基于谓词Liblit和他的同事提出了CBI（Cooperative Bug Isolation）技术，用于定位已部署软件中的错误。基本思想是搜集用户在使用软件过程中产生的执行信息，进而通过分析这些数据将软件缺陷分离出来。然后，在搜集这些执行信息的同时，会对用户使用的软件性能有一定的影响，为了解决这个问题，Liblite等人通过在源代码上的变换，使用稀疏的随机抽样，较好地控制了客户端的性能并返回执行时的摘要信息。尽管CBI技术能够从广泛的系统中识别出一些错误，但它只考虑了那些在失败执行中取值为真的谓词，而对于一个总是取值为真的谓词，CMI技术就丧失了它的判断能力。Liu等人对谓词在成功执行和失败执行中的取值模式进行建模，然后基于统计学中假设检验的原理，量化每个谓词的错误相关性，建立了SOBER方法。一个谓词P的取值偏差在成功和失败执行中的差异越大，则谓词P出错的可能性越大。令Y表示谓词P的取值偏差在所有失败执行中的均值。SOBER使用如下公式计算P的怀疑度：其中，sp为谓词P在所有成功执行中谓词的取值偏差的方差，Z是Y的标准化随机变量。开发者可以根据谓词的怀疑度的大小审查源代码，发现错误的位置。然后，Zhang等人研究了短路求值和求值序列对于错误定位技术的影响。他提出了一种基于谓词的定位方法的改进策略：DES（Debugging through Evaluation Sequences）策略，将每个谓词排名最高的取值序列作为该谓词的排名，实验表明，DES可以提高基于谓词的错误定位技术的有效性而同时仅产生较小的额外性能开销。Zunwen，You等人提出了一项新的统计方法9，该方法是通过探测两个在执行过程中顺序连接的谓词的统计行为。如果谓词被视为一个图的顶点，那么这个图的边则表示程序在执行过程轨迹中两个顺序连接谓词的过渡。每个边的标签代表每个转变的频率。对于每条边，我们应用假设检验来评价在通过运行边缘评估偏倚和失败运行边缘评估偏倚之间的差异。边缘是根据从假设检验中得到的故障相关程度来排列的。实验证明，我们提出的基于谓词的故障定位技术优于其他适当运用统计的故障定位技术。3) 基于方法对于面向对象的语言，Dallmeier等人提出了基于方法调用序列的Ample技术，认为只出现在通过执行或失败执行中的方法调用子序列都应该被怀疑。与在通过或失败执行中出现的子序列相比，这些子序列被分配较大的怀疑度值，遗失或增添的子序列都值得怀疑，因为它们都可能引发程序故障。与Ample技术不同，Yilmaz等人提出使用时间光谱作为程序执行的抽象。时间光谱是指程序实体（方法，函数等）运行的时间特征信息，通常用于程序性能的评价和优化。他们提出一种叫做TWT（Time Will Tell）的方法，首先收集成功执行和失败执行的时间光谱，接着基于成功执行的时间光谱建立程序行为模型，然后使用这个模型来识别失败执行和成功执行的偏离程度。SFL（Spectrum-based Fault Localization）是一种轻量级的自动诊断技术，然而当它应用于面向对象程序时，它的诊断精确度由于可疑语句被分布到不同的类中而受到限制，于是，Jingxuan，Tu等人提出了一种方法，利用方法调用异常来提高SFL技术在面向对象程序中故障定位的有效性。其过程如下：首先，基于在通过和失败运行中方法调用序列的差异来计算每个类的可疑度；然后，利用每个类的可疑信息细化SFL可疑度序列，以提高面向对象软件故障定位的效率。实验表明，该方法能够提高SFL技术的有效性。4) 基于定义使用对、分支或信息流Santelices等人认为有些缺陷最好使用语句覆盖信息来定位，而有些最好使用分支或者定义使用对的覆盖信息。首先需要计算一个程序实体的怀疑度，然后对于分支或者定义使用对，根据3条规则，将每条语句的可疑度定义为和它关联的分支或定义使用对可疑度的最高值。然后采用max-SBD，avg-SBD和avg-BD 3种策略来获得一个语句的可疑度得分。即是说一个语句的可疑度得分可以是和它关联的3种程序实体怀疑度得最大值，平均值或只是定义为和它关联的分支和定义使用对怀疑度得平均值。实验表明，综合使用多种覆盖类型的信息，确实可以提高错误定位技术的有效性。与Santelices等人提出的使用单一模型建模程序实体不同，Yu等人进一步提出一个使用多个模型来捕捉不同类型的错误的方法LOUPE。假设对于任一类型的错误，存在一种适合模型，它能够较好识别出错误语句，由于错误类型事先未知，LOUPE方法建立了多个模型来捕捉语句的异常行为，并试图选出相应的适合模型。动态信息流分析师一种更加重量级的方法，它考虑5种类型的依赖关系：动态直接控制依赖，动态直接数据依赖和3种过程间的依赖关系。由于动态信息流分析能够识别运行时对象之间的信息流，所以也可以用来建模程序元素之间复杂的交互作用，于是Masri提出了一种基于动态信息流分析的错误定位方法。对于信息流f，怀疑度计算公式如下：然后，每条可执行语句被赋予流经它的怀疑度最大的信息流的值。并且，值得怀疑的信息流的源语句应该先于这条信息流上的其他语句被检查。5) 行为特征信息的精炼由于受到很多因素的影响，在实践中，基于行为特征对比的方法的有效性仍然会受到限制。Masri等人通过实验发现了这类方法有效性下降的四个场景：错误条件满足，但程序故障并未出现（作者成为巧合正确性）；错误语句被执行，但程序故障并未出现（作者称为弱巧合正确性）；程序故障和不止一个的不同类型的程序元素的组合有关；以及很多程序元素不在通过程序中出现，却出现在所有的失败执行中。前三个场景可能会影响错误定位技术的准确性，后一个会影响精确性。为了进一步提高定位技术的有效性，研究者提出了不同的精炼方法来减少各种因素的影响。针对弱巧合正确性，Wang等人受后向动态切片的启发，将与程序输出结果无关的实体的覆盖信息去除，以精炼程序输出特征。由于以上错误定位技术只关注与评估单个的程序实体的怀疑度，而忽略了被感染的程序状态在它们之间的传播，于是Zhang等人提出使用控制流边的信息来表示成功执行和失败执行，然后比较它们的差异来建模每个基本块对于程序故障的贡献程度。由于基于频谱定位技术中故障类型和数量，测试组件的质量比较敏感，Gopinath等人10提出了一种新的技术，该技术应用于基于光谱的协同规范分析，以更准确地定位故障。他们的观点是违反规范的不可满足性分析，可被用于计算包含可能故障语句的不可满足核心和生成有助于基于光谱的定位技术的测试用例。此方法是迭代的，并且可以通过反馈回路获取更加精确的故障定位。SAT-TAR是体现了我们这个技术针对Java程序的一个框架，并且包含了多故障检测技术。实验证明，此项技术比state of the art方法更加准确。4.1.1.2 基于程序状态修改的方法基于程序状态修改的方法通常是在程序执行时获得并修改程序的状态，然后观察修改后的测试结果，进而找出对测试结果有影响的关键谓词或语句。由于程序运行时的状态有多种可能性，所以这类方法经常需要采取一些简化策略来提高错误定位的效率。Delta Debugging方法是由Zeller提出的一种能自动缩小程序的成功运行过程和失败运行过程之间区别的技术。它采用分治思想，把软件配置（测试输入，源程序等）变动的集合进行划分，然后分别进行测试。然后递归地把导致失败配置的集合并入结果为通过配置的集合。这样逐渐减小两个集合之间的差异，最终确认成功配置和失败配置差别的一个最小集。2005年，此方法被应用到程序状态上，自动化找出导致程序失败的语句。改变分支的取值结果是改变运行时变量的值的一种特殊情形。Jeffrey等人提出了Value Replacement方法：首先尝试改变运行时变量的值以得到成功用例，进而将这种信息用于错误定位。然后将使用的值替换成另外一个，并观察是否会产生正确结果。Feng Li等人提出了一种新的基于状态的错误定位方法DelFal11。假设执行轨迹的可用性导致报告的程序执行失败，这种新方法依次选择设置跟踪点以便对程序执行状态高效自动的探索来帮助开发人员找到编程所观察到的执行失败。每个这样的集合跟踪点，在每个轨迹点的程序状态被象征性地改变。通过否定每种原子谓词，去观察同样的故障是否发生在从源代码中相应的程序点符号执行继续进行。这组跟踪点是备选集合中的最小程序状态集，这样一组跟踪点被称为最小调试边界集MDFS（Minimum Debugging Frontier Set）。根据符号执行的结果，下一个MDFS是根据向前或向后移动剩余程序轨迹而确定的。当故障代码被发现时，轨迹跟踪过程会被缩短并继续进行下去。MDFS方法需要被提供执行失败的位置，但所需的程序状态的规范是可选的。有了这样的规范，它可以实现更加精确的错误报告。实验证明此方法在合理的时间内可以有效的解释故障。4.1.1.3 基于程序依赖关系的方法基于程序依赖关系的方法侧重于使用程序的动态依赖关系给出值得怀疑的语句的集合。这个集合包含错误语句和调试上下文，由于这个集合通常会包含一些冗余的语句，所以需要使用一个技术来简化。Zhang等人从动态角度提出隐式依赖（implicit dependence ）的概念，它只会将已经观测到的发生在谓词和变量使用上的依赖关系加入切片中。进一步，他们使用一种需求驱动的策略来减小探测隐式依赖的开销。为了减小动态切片的规模，研究着提出了许多种简化策略。Gupta等人整合了Delta Debugging技术来识别一个最小的故障相关的输入，然后基于这个输入计算动态前向切片并以错误输出为准则产生的动态后向切片取交集，作为引发故障的砍片（chop）。Baah等人扩展了程序依赖图，通过测试用例的执行信息估计节点间的统计依赖，建立了程序依赖图PPDG（Probabilistic Program Dependence Graph）。它是基于概率图模型的框架，首先产生依赖图，然后得到标记了子节点和父节点之间条件概率的变换程序依赖图。与此同时，插桩源程序得到测试用例的执行信息，通过学习执行信息中的数据，最终得到PPDG。与PPDG不同，Feng和Gupta为每种指令类型建立了通用模型。给定一组程序的执行轨迹，并包括至少一个成功执行和至少一个失败执行，可以基于动态依赖图建立基于贝叶斯网络的错误流图（Error Flow Graph）和通用的概率模型。然后使用标准的推理算法从业节点沿着错误流后向追溯寻找错误可能性最大的可执行语句。一种常用的定位错误的方法是根据通过执行和失败执行来计算程序块的可疑度，但这种技术并没有完全考虑到程序块之间的以来关系，因此错误定位的能力受到了限制。Wanzhi，Wen等人经过研究12，打算利用程序切片技术和统计方法，该统计方法是从程序块之间提取它们之间依赖关系并且喜欢它们的执行历史。然后根据统计方法对可疑程序块进行排序，并建立一个程序切片谱。我们期望的是这个方法能够直接促进软件故障定位有效性和精确度的改进，从而减少软件开发和维护的成本。4.1.1.4 其他方法Wong等人提出了一种名为DStar（D*）的技术13，它可以自动提示进行错误定位的可疑位置而不需要任何程序结构或语义的先验信息。通过实验，DStar（D*）方法在24个程序错误定位中，与其他38种不同的错误定位技术相比，无论是单故障还是多故障，它都是最有效的。实验同时也表明，DStar（D*）方法随着指数*的有效性增加，逐渐达到一个平稳状态。Yan Lei等人提出了一种名为BSSFL（Backward-Slice-based Statistical Fault Localization）的错误定位方法14。该方法假定测试预言存在来确定测试用例的结果是否是失败或通过，但由于在现实中，测试预言并不总是存在，因此在这种情况下BSSFL是不可行的。在目前的研究中，变质测试已被广泛研究，以缓解测试预言问题，因此，我们利用变质测试进行BSSFL。在此过程中，我们用后向切片和违反或不违反变质测试组，而不是后向切片和失败或通过的单个测试用例。此方法不需要测试用例的执行结果，所以它可以扩展到没有测试预言存在的领域。实验表明，我们提出的方法在测试预言存在的情况下较现有的BSSFL技术效率更高。最近的研究表明，利用因果推断技术来减少混杂偏倚以提高统计错误定位（SFL）在程序语句水平的有效性，然而由于非常大的程序和测试组件，会造成一定的影响，为降低影响，Gang Shu等人提出并评估了一种新的方法级SFL技术MFL15，该技术基于因果推断，并采用了新的算法来选择协变量以调节混杂偏倚的使用。同时，试图确保这样的协变量满足能够识别观测数据的因果效应的条件可交换性和积极性。实验表明，我们的方法比知名的SFL方法更有效，并且，我们的混杂因素选择算法优于两种选择。近来，随着人工智能的快速发展，基于人工智能理论的故障诊断技术吸引了越来越多人的注意。Guoshun，Chen等人16认为MAS（Multi-Agent Sysytem）具有较强的自主性，智能性和社会能力，很适合用于诊断软件系统，并很容易与现软件密集型装备现有的软件测试方案进行集成。于是，他们提出了一种新的基于MAS的故障诊断框架，此框架已应用与真正的软件诊断当中，并且证明了它的有效性。（需要详细列出这个四层框架）Roychowdhury等人提出了一种新的方法17，该方法基于伯努利分歧来自动定位故障，所以，该方法是从信息论和机器学习中西吸取的概念，并将它应用于软件工程。经过初步的实验研究，表明此方法给故障定位技术带来了希望。Xiaomin，Wang等人18为了解决现有定位技术的限制性，提出了一种新的技术，建立一种新的行为模型，并提出相应的故障定位技术。实验表明，这项新技术优于其他SBFL故障定位技术，并且，我们发现，这项技术的有效性来自于分层行为模型的指导。虽然基于频谱的贝叶斯推理可以有效地根据通过/失败测试案例来排列候选故障位置，但是诊断质量高度依赖于地层测试组件的规模和多样性。由于在实践中测试组件通常不表现出必要的属性，据此，Gampos等人19提出了一种技术用新的能够优化诊断质量的测试案例来扩展现有的测试组件。我们运用概率理论概念中的熵来指导测试用例生成，使得在诊断排名中的不确定量达到最小化。我们的ENTBUG原型扩展了基于搜索的测试用例生成工具EVOSUITE使用熵在其潜在的遗传算法的实用度函数，我们将此技术应用到了7个真正的故障定位当中，实验结果表明，相对使用原始的测试组件，该方法在诊断排名的熵上平均下降了49%，从而导致在寻找真正故障时下降了91%的检查幅度。De Souza, H.A等人20提出了一项新的技术，该技术使用整合覆盖数据来指导故障定位过程。通过排序的方法调用可疑对，被调查的路线排序方法列表随之被创建。在每个方法中，单元覆盖被用于定位故障。实验对4个包含了2000到80000行代码中的55个BUG进行了分析，结果表明，通过使用路线图，故障定位过程的有效性得到了明显提高：固定基本块中的78%的故障被定为成功，比Tarantula技术高出40%。4.1.2 算法检测在众多的软件系统和应用中，许多被检测到的缺陷都是由于程序设计或低效的编码造成的。4.1.2.1 冗余计算（Redundant Computation）冗余计算在软件程序中是一种普遍发生的现象，在多数情况下，它是软件缺陷发生的根源，消除冗余计算不仅可以提高程序性能，而且还能识别软件程序中的潜在错误。冗余计算在多数情况下都是由于程序算法设计的不足所造成的，针对这个问题，Zakarya,A.Alzamil 21提出了一种动态方法来理解程序的动态行为。该方法能够识别执行程序语句中没有输出的计算，这些计算就被成为冗余计算。这种冗余计算能够指导开发者识别潜在的算法问题。在他的实验中，通过RCAT (Redundant Computation Analysis Tool )搜索工具检测C程序当中的冗余计算并且识别与冗余计算相关的潜在缺陷。表3-Initial Experiment Result表3所显示的就是作者实验的结果，通过实验结果，我们可以看出，此方法可以帮助开发者检测冗余计算，并且指导开发者提高程序的算法，开发更加健壮的程序软件。4.1.3 数据检测类4.1.3.1 浮点数精度问题（Floating-Point Accuracy Problems）在程序中使用浮点数，很容易造成舍入或灾难性取消等精度问题。然而这些现象引发的错误难以追查：程序不一定崩溃，程序结果不一定是显然错误的，但往往是有细微的错误存在，如果开发者进一步使用这些值，就可能会造成灾难性的错误。Florian等人针对浮点数问题，提出了一种支持程序员发现精度问题的动态程序分析方法22。他们使用二进制转换，将浮点数转换到更高的精度，此外，还是用轻量级切片方法来追踪错误评估。他们通过捕获到的比较典型的浮点数问题和分析SPECFP2006浮点数基准来评估我们的分析。在后者中，我们会通过工具来追寻一个灾难性的取消是如何导致精度完全失效进而引发的毫无意义的一个结果。在试验中，他们利用VDBIF（Valgrind Dynamic Binary Instrumentation Framework）框架来执行实验的分析并且将它运用到大规模的基准程序中。分析结果显示，我们的分析能够帮助开发者追踪和修正浮点数精度问题。图-Result of the SPECFP2006 benchmarks with the “test” data sets4.2 动态程序分析工具最近的研究表明，矛盾、重复或嘈杂的光谱可能影响SBFL指标排名的准确性，Danel等人23据此提出并开发了一种新的SBFL工具，该工具可以通过测试用例预处理过滤掉矛盾，重复或其他嘈杂的光谱。实验表明，该带有测试用例预处理的SBFL工具已经成功改善了SBFL指标在大多数研究中的性能。4.3 动态程序分析在软件测试中的应用5. 未来研究展望作为软件技术研究领域的核心内容之一，动态程序分析技术随着软件技术的发展而处于不断发展之中，并受到如下几个方面的推动：程序错误定位新理论和新技术的引入与集成、程序算法检测新的发展形态、软件运行平台的新发展等等。5.1 错误定位新理论和新技术的引入与集成1) 测试组件（test suite）的影响测试组件的组成会对错误定位技术的有效性产生影响。当前的错误定位技术通常假设测试用例集满足测试充分性准则，足以满足错误定位的需要2) 多个缺陷的定位3) 定位结果的理解4) 错误修复的建议5.2 程序算法检测新的发展形态5.3 软件运行平台的新发展6. 结束语本文从错误定位、算法检测、数据监测等方面对动态程序分析技术进行归纳总结，并对未来的研究趋势进行展望。动态程序分析在过去几十年间取得了很大的进步，研究者们贡献了巨大的力量，