法律状态公告日
法律状态信息
法律状态
2016-08-03
授权
授权
2013-08-07
实质审查的生效 IPC(主分类):G06F11/36 申请日:20130326
实质审查的生效
2013-07-10
公开
公开
技术领域
本发明涉及计算机程序分析领域。
背景技术
随着计算机软件被广泛应用于经济、军事、商业等各个领域中,其可靠性问题日益得 到人们的广泛重视。然而随着软件系统越来越复杂,软件经常不像人们预期的那样运行, 换句话说,软件不总是可靠地运行,对计算机应用系统带来不利影响,甚至造成巨大的经 济损失和灾难性的后果。因此,保证软件的高质量、高可靠性已成为系统开发和维护工作 的一个不可或缺的重要方面。
导致软件不可靠的一个主要原因是程序源代码中的错误。程序设计是一项复杂的活 动,很难推导程序中所有可能的执行路径,以及预见可能影响程序或被程序影响的环境因 素。即使程序看起来正确执行,仍然可能存在极少情况下或特定条件满足时的错误。因此 软件错误是目前亟需解决的一个问题。
软件测试和调试是软件开发过程中的重要阶段,它们协同工作可以有效识别并消除软 件错误:测试用于暴露软件错误,调试用于消除这些软件错误。然而软件调试过程中消除 软件错误的速度往往跟不上软件测试过程中发现软件错误的速度。目前已有很多自动化软 件测试工具,然而,软件调试却大多采用人工分析的方法,这是一项很困难并且耗时的任 务,因为:(1)首先要定位软件中的错误。在某些情况下,当开发人员在程序执行过程中 发现软件错误时,可能已经离错误点很远了,需要花费大量的时间和精力来查找引起错误 产生的程序代码。(2)其次要理解软件错误。定位软件错误仅仅是软件调试第一步,接下 来必须通过适当地修改程序源代码来消除语句中的错误。在有些情况下,如何适当地修改 语句不是很明显,需要开发人员人工分析调试环境来理解为什么某个语句是错误的,然后, 寻找一种方法来修改代码中的错误,并且避免在修改过程中引入新的错误。
如果能实现软件自动化调试,即由计算机自动找到程序代码中的错误位置、分析错误 原因、进而自动纠正错误,则可以更有效地确保软件可靠性。软件错误自动定位通过计算 机来分析程序源代码或运行过程中产生的运行时状态,计算并分析程序中的异常情况,并 将其独立出来作为可疑代码。将与软件错误无关的代码自动过滤掉,仅保留需要进一步调 试的相关代码,可以缩小错误代码搜索的范围,来辅助开发人员更快地识别错误语句,有 效提高调试的效率。因此,本发明目旨在针对软件可靠性实际应用背景和需求,研究软件 错误自动定位,为软件调试和软件错误修正奠定理论基础,提高软件质量、确保软件高可 靠性、提高软件的可理解和可维护性。
发明内容
本发明是要解决传统的软件错误定位方法定位精度低的问题,而提供了基于联合依赖 概率建模的软件错误定位方法。
基于联合依赖概率建模的软件错误定位方法包括以下步骤:
步骤1:分别执行正确测试用例和错误测试用例,并分别对正确测试用例和错误测试 用例建立联合依赖概率模型;
步骤2:在步骤1的基础上,根据联合依赖概率模型,计算每个节点的可疑度;
步骤3:将错误定位信息按可疑度进行降序排列,可疑度高的节点认定为更有可能出 错的节点,即完成了对基于联合依赖概率建模的软件的错误进行定位。
发明效果:
本发明的基本思想是:节点的联合依赖可以很好的表示在不同执行状态下节点与其父 节点之间的数据依赖关系,有助于进行错误定位。如果某个节点的联合依赖关系在错误测 试用例执行过程中出现的频率较高,而在正确测试用例执行过程中出现的频率较低或没有 出现,则该节点的联合依赖关系很可能是错误的。根据这一思想计算各语句的联合依赖关 系的可疑度,进而有效定位软件错误。
本发明的基于联合依赖概率建模的软件错误定位方法,能够有效定位与数据依赖相关 的软件错误。与错误定位方法SBI、SOBER、Tarantula相比,定位精度可提高15%以上, 适用于大规模程序代码的错误定位技术领域。
附图说明
图1是本发明的方法的流程示意图;
图2是具体实施方式一建立联合依赖概率模型示意图;
图3是具体实施方式一程序控制流图和数据依赖图实例示意图;
图4是具体实施方式一程序控制依赖路径和数据依赖路径实例示意图。
具体实施方式
具体实施方式一:结合图1~图4说明本实施方式:本实施方式的基于联合依赖概率 建模的软件错误定位方法包括以下步骤:
步骤1:分别执行正确测试用例和错误测试用例,并分别对正确测试用例和错误测试 用例建立联合依赖概率模型;
步骤2:在步骤1的基础上,根据联合依赖概率模型,计算每个节点的可疑度;
步骤3:将错误定位信息按可疑度进行降序排列,可疑度高的节点认定为更有可能出 错的节点,即完成了对基于联合依赖概率建模的软件的错误进行定位。
本实施方式中,图3左侧上部分为程序void distance(),左侧下部分为此程序所对应 的数据依赖图,右侧为此程序所对应的控制流图;
图4左侧为运行的测试用例,中间部分为执行测试用例时所获得的控制依赖路径,右 侧部分为执行测试用例时所获得的数据依赖路径;例如,对于控制依赖路径中的5(true), 表示节点5被执行,且被执行时的状态为true;对于数据依赖路径中的5(true,[d1(i),d2(n)]), 表示节点5被执行时,执行状态为true,数据依赖于节点1和节点2,且数据依赖变量分 别为i和n;
本实施方式步骤E中例如n(5(true,[d1(i),d2(n)]))表示在数据依赖路径中 5(true,[d1(i),d2(n)])出现的次数,n(5(true))表示节点5的状态为true出现的总次数。
本实施方式效果:
本实施方式的基本思想是:节点的联合依赖可以很好的表示在不同执行状态下节点与 其父节点之间的数据依赖关系,有助于进行错误定位。如果某个节点的联合依赖关系在错 误测试用例执行过程中出现的频率较高,而在正确测试用例执行过程中出现的频率较低或 没有出现,则该节点的联合依赖关系很可能是错误的。根据这一思想计算各语句的联合依 赖关系的可疑度,进而有效定位软件错误。
本实施方式的基于联合依赖概率建模的软件错误定位方法,能够有效定位与数据依赖 相关的软件错误。与错误定位方法SBI、SOBER、Tarantula相比,定位精度可提高15% 以上,适用于大规模程序代码的错误定位技术领域。
具体实施方式二:本实施方式与具体实施方式一不同的是:所述建立联合依赖概率模 型的方法具体为:
A、首先为程序建立控制流图,然后记录语句间的控制依赖关系;
B、再为程序建立数据依赖图,然后分别记录语句间的数据依赖关系;
C、然后通过运行测试用例,插装捕获节点的控制依赖路径和数据依赖路径;
D、根据控制流图和节点的控制依赖路径,计算每个节点的状态依赖概率;
其中,所述每个节点被执行的概率记为P(node),对于分支节点在被执行概率的基础 上记录状态为true和false的概率,记为P(node(true))和P(node(false));
所述每个节点,根据下式计算节点node被执行的概率P(node):
其中,P(para(node))为节点node的父节点被执行的概率,n(node)为控制依赖路径中, 节点node被执行的次数,n(para(node))为控制依赖路径中节点node的父节点被执行的次 数;
所述分支节点,在被执行概率的基础上计算节点状态为true和false的概率,即 P(node(true))和P(node(false)):
P(node)=P(node(true))+P(node(false)) (2)
其中,所述
其中,n(node(true))和n(node(false))分别为控制依赖路径中节点node的执行状态为 true和false的次数;
E、根据数据依赖图和节点的数据依赖路径,计算每个节点的条件依赖概率P(data dependency|state dependency):
n(node(state dependency,data dependency))为数据依赖路径中节点node的状态为state、 数据依赖为data dependency出现的次数,n(node(state dependency))为数据依赖路径中节点 node的状态为state出现的总次数;
F、根据每个节点的状态依赖概率和条件依赖概率,计算节点的联合依赖概率:
根据下式计算节点的联合依赖概率:
联合依赖概率=状态依赖概率×条件依赖概率 (4)
G、建立联合依赖概率模型
定理:(联合依赖概率模型):程序代码P的联合依赖概率模型是一个三元组(D,S,R), 其中:
(1)D=(N,E)是P的数据依赖图,N为节点集合,E为数据依赖边集合,表示程序的数 据依赖关系;
(2)S是节点到状态的映射;
(3)R是节点的联合依赖概率。
其它步骤及参数与具体实施方式一相同。
具体实施方式三:本实施方式与具体实施方式二不同的是:所述计算每个节点被执行 状态的可疑度的方法,具体为:
计算每个节点的联合依赖关系的可疑度suspicious_score:
其中,Ppassed(joint dependency)为执行正确测试用例时,节点node的联合依赖概率; Pfailed(joint dependency)为执行错误测试用例时,节点node的联合依赖概率。
其它步骤及参数与具体实施方式二相同。
具体实施方式四:本实施方式与具体实施方式三不同的是:所述节点对应于程序中的 每条语句。其它步骤及参数与具体实施方式三相同。
具体实施方式五:本实施方式与具体实施方式四不同的是:所述分支节点为对应于程 序中的选择和循环语句。其它步骤及参数与具体实施方式四相同。
机译: 用于模拟物理实体与影响因素的测量数据之间的非线性依赖性的方法和系统,该方法和系统由使用带有嵌入式概率网络的对象的局部/全局建模方法控制
机译: 用于模拟物理实体与影响因素的测量数据之间的非线性依赖性的方法和系统,该方法和系统由使用带有嵌入式概率网络的对象的局部/全局建模方法控制
机译: 对象定位方法,涉及基于对象在这些位置排列的概率来计算输入图像中限制框的概率值,并选择概率最高的框作为对象的位置