第 卷 第 期年 月计 算 机 学 报收 稿 日 期 在 线 出 版 日 期 本课题得到国家自然科学基金 和教育部博士点基金资 助苏 小 红女 年 生博 士教 授中国计算机学会 高 级 会 员主要研究领域为软件缺陷检测程 序 分 析信 息 融 合目标检测与跟踪等 王 甜 甜女 年 生博 士副 教 授主要研究方向为程序分析软 件 缺 陷 检 测等杨 劭 君男 年 生硕 士 研 究 生 主要研究方向为软件错误定位图 挖 掘 等马 培 军男 年 生博 士教 授主 要 研 究 领 域 为 信息 融 合软 件 工 程目标检测与跟踪等一种基于加权软件行为图挖掘的软件错误定位方法苏小红 王甜甜 杨劭君 马培军哈尔滨工业大学计算机科学与技术学院 哈 尔 滨摘 要 已有错误定位方法通常仅给出可疑语句排序而缺少必要的上下文信息 导致难于理解软件失效的产生原因为了解决该问题 定义了加权软件行为图来表示成功和失败的程序执行路径由于图中边的权重表示了路径的执 行 频 率因 此 与 方 法 相 比可以较好地分析与循环和递归等结构相关的软件错误 在 此 基 础 上 执 行 基 于分支限界搜索的加权软件行为图挖掘算法 识别成功和失败执行之间最有差异的子图来获得错误签名 不 但 可 以有效定位错误位置 还能输出缺陷语句相关的执行路径从而提供失效产生的上下文分 析 基 准 测 试 集 和程序的结果表明 在检查相同百分比的语句的情况下文 中 方 法 可 以 比 方 法 和 方 法 定 位 到 更多的 错 误特别是对于冗余代码 缺失代码和变量替换以及会直接改变执行路径类的错误 文中方法具有较高的定 位 精 度关 键 词 错 误 定 位软 件 行 为 图 图 挖 掘错 误 签 名分 支 限 界 搜 索中 图 法 分 类 号 号引 言随 着 计 算 机 行 业 的 不 断 发 展软 件 也 日 趋 庞 大和复杂软件失效发生的概率也随之增高这使得软件的质量越来越难以保证 在软件失效发生以后 调试软件定位导致错误产生的代码语句并且修复错误往往需要消耗大量的时间和人力而自动化错误定位技术可以显著减少其中的人力和时间消耗从而提高软件的质量目 前 已 存 在 很 多 不 同 的 软 件 错 误 定 位 方 法 例如基于程序状态修改的方法 基于程序行 为 特 征对 比 的 方 法 以 及 基 于 程 序 依 赖 关 系 的 方 法等这些错误定位方法的结果大多数都是一个语句的可疑值序列其中按照可疑值降序的顺序列出了不同语句的可疑值 以指导开发者对错误进行修改但是单独检查给出的可疑语句 通常并不足以令开发者判断该语句 是 否 是 正 确 的开发者往往需要更多的上下文信息 才能够理解错误是如何产生的 并修正程序因此 等人 提出了能 够 从 成 功 和 失 败 的程序执行 路 径 中 识 别 错 误 签 名 的 方 法错误签名是一个程 序 实 体 序 列当按顺序执行其中的程序实体时就很可能会导致错误产生 错误签名不但可以指示错误 的 所 在 还能够提供错误产生的上下文 等人 根据 程 序 执 行 路 径 构 造 软 件 行为图提出了利用图挖掘算法来识别错误签名的方法本 文 则 进 一 步 改 进 了 软 件 行 为 图 考 虑 了 语 句的执行频率对错 误 定 位 效 果 的 影 响 提 出 了 加 权 软件行为图以及适用于挖掘加权图的新函数得到了错 误 定 位 精 度 更 高 的 错 误 签 名 最 后 与方法 和 方法 进行了实验比 较 讨 论 了 不同错误类型对错误定位精度的影响本文第 节介绍目前的相关工作和本文的研究动机第 节介绍本文方法的总体思想 第 节介绍加权软件行为图的构造以及相应的图挖掘算法 第节通过实验分析本文的方法第 节 讨 论 本 文 方法的局限性和可改进之处 最后总结全文相关工作及研究动机目 前 的 软 件 错 误 定 位 方 法 大 致 可 以 分 为 程 序状 态 修 改 程 序 行 为 特 征 对 比 程 序 依 赖 关 系 分析 和错误签名方法等程序状态修改方法通常在程序执行时收集程序状态信息并对 程 序 状 态 进 行 修 改 然 后 观 察 修 改 后的执行结果是否发生变化据此找到与错误相关的关键 语 句 和 提 出 的方法采用分治的思想找到成功的测试输入和失败的测试输入间的 最 小 差 别 再跟踪成功和失败执行之间的状态差异 找到错误语 句 等 人 通 过在运行时强制修改谓词的取值结果使 得 失 败 的 执行变为成功的执行 并依此识别错误所在 这类方法的算法复杂度一 般 都 较 大 对小规模程序效果比较理想但处理复杂程序时效率会大大降低程 序 行 为 特 征 对 比 方 法 一 般 认 为 成 功 执 行 和失败执行的程序行为特征是不同的它 们 之 间 的 差异可以用于指导 错 误 定 位 这些方法通常统计语句和谓词被每个测试用例覆盖的信息来衡量每条语句出错的 可 能 和 提 出 的 基 于 语 句 覆盖的方法 认为错误语句应该在失败的执行中大量的出现 而在成功的执行中少量出现 之后研究人员提出了大量的覆盖分析方法文 献 对这些方法的等价性和精度进行了理论上的分析比较文献 提出了利用机器学习方法结合多种覆盖分析错误定位方法 期望取得更准确的定位结果 然而此类方法往往只考虑了语句或谓词的覆盖信息缺少对程序结构和执行信息的分析会 影 响 错 误 定位精度而且难以给出与错误相关的上下文信息 开发者仍然需要做许多工作才能够修复错误程 序 依 赖 关 系 分 析 方 法 侧 重 于 根 据 程 序 实 体间的控制依赖关系或数据依赖关系给 出 语 句 的 可疑值还能提供额外的上下文信息供开发者理解错误的产生 等人 分析了 程 序 的 控 制 依 赖 和 数据依赖产生程序 依 赖 图 再通过执行测试 计 算 节点间的条件概率 建立了概率程序依赖图 可以有效的应用于 错 误 定 位 和 错 误 理 解 苏 小 红 龚 丹 丹 等人 定义了联合依赖概率模型 在定位过程 中 分 析程序元素间的控 制 依 赖 数据依赖以及语句执行状态这类方法的结果仍可能包含大量信息 这些冗余信息会造成难以找到与错误相关的信息等人 提出了识别错误签名的 方法通过增量的分析失败的程序执行路径的公共序列将挖掘得到可疑语句序列作为错误签名 辅助开发人员定位和理解软件错误等人 对错误 签 名 方 法 进 行 了 改 进本文将其称为 方法首 先 利 用 程 序 执 行 路 径 构计 算 机 学 报 年造软 件 行 为 图 再 通 过 图 挖 掘 算 法 利 用 信息增益作为目标 函 数 从成功测试用例和失败测试用例的软件行 为 图 集 合 中 挖 掘 出 个 在 失 败的执行中出现很 频 繁 而在正确的执行中比较少见的最优局部软件 行 为 图 作 为 可 疑 语 句 序 列 该 方 法能够给出失效产生的上下文且避免了冗余信息 因此有助于定位和 理 解 软 件 错 误然而存在的一个不足之处是软件行为图中所有的控制流路径具有相同的重要程度而没有考虑语句执行频率与软件失效之间的关联例如错误的条件表达式或循环体内的某些缺陷语句可能导致循环执行路径和次数的改变进而导致软件失效对于这 种 情 况 如 果 采 用 方 法 进行分析那么执行了多次循环的测试用例和只执行次循环的测试用例可能 具 有 相 同 或 相 似 的 软 件 行为图如果这两个软件行为图分别对应于成功和失败测试用例的软 件 行 为 图 则图挖掘算法将因无法在这两个软件行为图中区分成功执行和失败执行的差异而失 效从而不能有效定位到软件错误 类 似地错误的递归也可能导致函数执行路径的改变由于循环和递归是 编 程 语 言 的 基 本 元 素 需 要 提 供 一种机制来表示程 序 执 行 路 径 的 转 移 概 率 使 之 可 以有效区分成功和失 败 执 行 路 径本 文 第 节 中 用 实例进行了详细分析综 上 所 述目 前 大 多 数 方 法 在 错 误 理 解 方 面 做的还不够完善要么只提供可疑语句的列表 缺少可以用于理解错误产生原因的有效上下文信息 要 么提供了过多的信 息 开发者难以从中找到与错误相关的信息都不利于开发者理解错误是如何产生的错误签名能够较好的平衡过多和过少的信息 但 仍需要考虑程序执行路径的统计学意义 而 不 仅 仅 是频繁图的挖掘本文的研究动机就是如何结合统计信息和图挖掘方法进一步提高错误签名的错误定位精度方法概述方法框架输入是待测程序 以及相 应 的 测 试 用 例 集 合根据程序 执行 测 试 用 例 的 实 际 输 出 结 果可 以 将测试用例分为两类 成功的测试用 例 的 实 际 输 出结果与预期输出结果相同 和失败 的 测 试 用 例 的实际输出结果与预期输出结果不同本文 方 法 主 要 包 含 个 步 骤获取程序执行路径构造加权软件行为图和挖掘错误签名 其流程如图 所示图 基于加权软件行为图挖掘的错误定位方法的基本流程软件测试和调试过程通常协作来检测和定位软件缺陷如果在测试过程中获得了测试用例的路径信息则可直接执行构造加权软件行为图和挖掘错误签名同大多数错误定位方法一样 本文假设测试用例集提供了充分的用以错误定位的测试覆盖信息能够保证测试覆盖率 错误定位方法的研究重点主要放在如何在这一前提条件下快速准确地定位错误所在的语句本文方法与 方法的差异方法将测试用例的执行路径表示为软件行为图不区分路径的执行频率因此对应的图挖掘算法仅是挖掘成功和失败测试用例集合执行路径中期 苏 小 红 等 一种基于加权软件行为图挖掘的软件错误定位方法的频繁子图方法是采用信息增益作为目标函数用算法挖掘出区分失败执行和正确执 行 差 异 的频繁子图而本文定义的加权软件行为图不但表示了程序软件执行路径还用边的权重表示了程序路径的执行频率表示了程序执行的统计信息 在本质上区别于软件行为图此外本文方法在基于图挖掘定位软件缺陷时需要考虑路径的权重 即路径执行的统计信息因 此采 用 了 不 同 于 的 目 标 函 数 和 图挖掘 算 法具 体 方 法 如 图 所 示用 得 分 作为目标函数用分支界限搜索方法挖掘错误签名并且提出了一系列用来提高挖掘效率和准确率的剪枝和去冗余等算法关键技术获取程序执行路径为 了 得 到 程 序 的 执 行 路 径需 要 对 待 测 程 序 的源代码进行插桩 插桩是在保证待测程序原有逻辑和功能不变的条 件 下 向程序源代码中插入探针语句用来在程序被执行时输出程序执行信息本 文 实 现 语 句 级 别 的 程 序 插 桩即 跟 踪 程 序 中语句的执行信息 每当执行到一条语句 就将被执行语句的行号作为执行路径输出首 先需 要 对 待 测 程 序 进 行 词 法 分 析 和 语 法 分析将源代码转换为等价的抽象语法树然后对抽象语法树进行分析 找到适合插入探针语句的位置 以保证额外的语句不会影响到现有的程序逻辑和功能例如对于 语 言 中 的 条 件 语 句 和 循 环 语 句 由于它们需要在每次执行条件判断时输出行号信息因此利用逗号表达式直接将探针语句插入到条件表达式中对于跳转语句由于它们会立即改变程序的执行路径因此必须在其之前插入探针语句接下来将插入探针的抽象语法树反向生成相应的程序代码即可得到插桩后的程序最后当执行插桩完毕的待测程序时 插入的探针语句也会被执行 从而输出程序的执行路径 如果探针语句将当前正在执行语句的行号输出 那 么 得到的程序执行路 径 中 每个节点就表示待测程序中的一条语句以图 所 示 的 程 序 为 例 它 是在数字数组中找到最大值首次出现的位置 函数中调 用 了 函 数为 了 避 免 冗 余 说明本文将 函数中的 和 的 读 取 用 了 伪代码 描 述 组 不 同 的 测 试 用 例 及 其 相 应 的 程 序 执行路径如表 所示当执行到 函数中的函数调用语 句 时程 序 的 执 行路径发生转移执 行 函 数 中 的 语 句执 行 完 后返 回 到 函 数 中 第行错 误应 该 使 用 号" "图 示 例 程 序表 程序的测试用例以及其执行路径序 号 测 试 用 例 分 类 程 序 执 行 路 径成 功失 败失 败构造加权软件行为图表 中 的 测 试 用 例 执 行 了 两 次 循 环 结 构 因此路 径 中 包 含 了 两 组 语 句 序 列 导 致 其执行路径长于测试用例 的执行路径实际程序中循环可能会执行 若 干 次 且如果循环结构中包含较多的执行语句则会导致过长的执行路径 特别是当程序中包含大量 循 环 结 构 的 时 候分析起来会非常困难需要消耗大 量 的 空 间 和 时 间而 且由 于 其 中包含的信息过多 很难从中提取关键信息 因此很有必要对程序执行路径进行进一步处理为了解决这一 问 题 等 人 提 出 了 软 件行为图软件行为图是一幅有向图图中的顶点对应于程序执行路径 中 包 含 的 语 句顶点间的边对应于程序语句执行时 的 顺 序 关 系软件行为图有效地压计 算 机 学 报 年缩了程序执行路 径 在保留了程序执行路径的特征信息的同时去除了很多冗余信息 可以有效减少数据 量节 省 时 间 和 空 间而 且 更 有 利 于 进 一 步 的处理例如表 语 句 在 测 试 用 例 中 被循环执行了 遍但是行为图中通过将其表示为控制流图的循环结构形式 使这些节点只出现一次 有效压缩了该路径 的 表 示 如 图 所 示同 理 如 果其他测试用例执行多次该 循 环 结 构节 点仍只需表示一次图 程序各个执行路径的软件行为图软件行为图可以认为是与特定执行相关的控制流图如果执行路径覆盖到了所有的语句和所有可能的语句执行顺 序 那么软件行为图就与控制流图是相同的如果执行路径仅覆盖到了部分语句或者未能包含全部可 能 的 语 句 执 行 顺 序 那 么 就 只 包 含控制流图的一部 分 当存在函数调用时控制流图可通过增加函数调用边和返回边来表示为过程间控制流图同样软件行为图也可以类似地表示函数调用关系但 是软 件 行 为 图 中 只 包 含 了 语 句 是 否 被 执 行以及语句执行顺 序 的 信 息 而没有考虑到语句执行频率对错误定位 结 果 的 影 响不能很好的处理循环和递归等 结 构 例 如对 于 表 成 功 测 试 用 例 和失败测试用例 的 执 行 路 径 是 不 同 的 但 是 却 具 有相同软件行为图表示 如 图 所 示如 果 比 较 测试用例 和 的软件行为图则因无法区分成功执行与失败执行之间的差异而无法有效定位缺陷语句基于以上分析本文提出了加权软件行为图定义 加 权 软 件 行 为 图 加 权 软 件 行 为 图是一个四元组 其 中 是 顶 点 集 合 包含程序执行路径中出现的 所 有 程 序 实 体是有 向 边 的 集 合 是 边 与 其 标 签 的 映 射 是 边与其权重的映射边 的 标 签可 能 是 调 用 转 移或返回之一如果 调用了 就被标记为调用如 果 从 返 回 到 了 则 将 标 记 为返回否则将 标记为转 移 表 示 紧 跟 在之后执行这 种标签表示了程序实体间的 种可能的控制流关系每条边还附加有一个权重 由于在待测程序的不同执行 中 同一条语句的执行次数可能会有很大区别因此直接将语句执行次数作为权重并不合适而是采用语句的执行概率作为权重若图中某条边 的起始顶点和结束顶点 分 别 为和 的出边以 为起始顶点 的 边 集 合其中每条边在执行路径中出现的次数分别为 则边 的权重计算公式为权重 表示了在此次执行中顶 点 被 执 行后顶点 会 被 执 行 的 概 率 对于同一个顶点的出边它们的权重和为 即有含有条件判定的语句可能有多条执行路径分支边 的 权 重 代 表 了 各 个 路 径 的 执 行 频 率如 图所 示对 于 测 试 用 例 的 路 径 其 语 句 有 两个分支 和 它们在循环中的执行次数分别为 和 因 此 边 的 权 重 为边 的权重为不同执行频率的路径意味着不同的执行上下文也可能 导 致 不 同 的 执 行 结 果成 功失 败 图成功测试用例 和图 失 败 测 试 用 例 的 加权行为图中的边的权重不同有效区分了成功测试用例和失败测试用例的软件 行 为 图 尤其是对与缺陷语句相关的执行路径做出了很好的区分有 了 程 序 执 行 路 径 只 要 不 断 的 将 执 行 路 径 中出现的边添加到有向图中 就可以得到软件行为图按照式 计 算 边 的 权 重 就得到了加权软件行为图其算法如算法 所示使 用 表 示 加 权 软 件行为图 的顶 点 集使 用 表 示 加 权 软 件 行 为期 苏 小 红 等 一种基于加权软件行为图挖掘的软件错误定位方法图 程序各个执行路径的加权软件行为图图 的边集算法 构造加权软件行为图输 入待测程序的执行路径输 出相应的加权软件行为图执行路径中的每条语句不 为中 的 每 个 顶 点以 为起始顶点的每条边的 权 重 为识别错误签名使 用 不 同 的 测 试 用 例 多 次 执 行 待 测 程 序 可 以得到一个加权 软 件 行 为 图 的 集 合 根 据 执 行 的 测试用例是成功的还是失 败 的 可 以 将 划 分 为 两 个子集一个包含与成功的测试用例对应的加权软件行为图记 为 另一个包含与失败的测试用例对应的加权软件行为图 记为在理想情况下有在理想情 况 下 即为需要分析的可能包含缺陷语句的子图 然 而现 实 情 况 下 失 败 测 试 用 例和成功用例常常执行一些公共的程序语句既 可 能包含正确也可能包含缺陷语句 因 此 与的交集 不 一 定 为 空 例 如 图 例 子 中 子 图子图 子 图 包含了图 中所有 语 句 节 点 加权软件行为图的挖掘目标是在 中找到一个最优的子图 使得 可以指出错误所在并提供与错误相关的上下文信息而这个最优的子图 就被称为错误 签 名 例 如 图 例子中的最优子图即错误签名为通 常 认 为错 误 语 句 应 该 被 失 败 测 试 用 例 大 量的执行而被成功测试用例少量的执行 即错误语句在 和 中的出现频率应当有显著的区别 那么可以设计一个目标函数 来 评 价 子 图 对成功的执行和失败的执行间差异的辨别能力 该 问题就 转 化 为 在 中寻 找 一 个 最 优 子 图 使 得最大的优化问题本文采用 得分作为 目 标 函 数 的 判据 得分以 最 大 化 类 间 离 散 度 和 最 小 化 类 内离散 度 为 目 标 准 则 在 中出现频率普遍较高而在 中出现频率普遍较低的子图 会 具 有更高的 得分它也 可 以 更 好 的 指 出 成 功 和 失败的执行间的差异令 表 示 次 不 同 的 执 行 对 应 的加权软件 行 为 图 对于特定的子图 其 边 集使 用 表 示 边 在 中 出 现 的 频率其定义为计 算 机 学 报 年其中 表示在图 中与 边 具 有 相 同 起 始 顶 点和结束顶点的边的权重使用 和 表 示 边 在 和 中 出 现频率的均值使用 和 表 示 边 在 和 中出现频率的方差运用 准则得到边 的 得分为最后将 中 所 有 边 的 得 分 求 平 均 数得到目标函数 的计算公式为剪枝策略由于 中可能包 含 指 数 级 别 的 子 图因 此 直 接进行搜索会消耗 大 量 的 时 间需要对搜索过程运用剪枝策略对于 某 一 子 图 它 在 和 中 出 现 的 频率 一 定 不 小 于 其 超 图 的 出 现 次 数即 的 超 图 在中出现的次数大于等于零 且 小 于 等 于 在中 出 现 的 次 数 在 中 出 现 的 次 数 大 于 等 于零且小于 等 于 在 中 出 现 的 次 数 因 此 的超图的得分具有 一 个 上 限 值可以通过判断该上限来进行剪枝边 的 得分上限为的超图的目标函数值上限为子图的选择和去冗余在 加 权 软 件 行 为 图 中 并 不 是 所 有 子 图 都 可 能是错误签名首先错误签名应当是有一定实际意义的子图能够表示错误的 上 下 文 即如果按照子图给出的顺序执行程序就很可能导致错误产生 包含复杂分支的子图如图 所示反而会让开发者难以理解其表示的意义不利于 理 解 错 误 产 生 的 原 因因 此可 以作为错误签名的子图 应当具有执行顺序 需要在选择子图时予以保证图 不利于理解错误产生原因的子图其次方法的调用与方法的返回是一一对应的即 如果方法 调用了方法 那么一定会从方法 中返回到 如果方 法 也 调 用 了 方 法 那 么 也 一 定会从 中返 回 到 将该执行过程转换为软件行为图结果如图 所示这里有效的子图只有和 而子图 和 都是无效的子图不可能在实际运行中出现在选择子图的时候必须将无效的 子 图 去 除 否则可能会影响错误定位的结果过滤子图的算法如算法 所示使用堆栈来检查调用边是否与返回边一一对应 例 如 对 于 有效的方法调用返回序列 而言首先调 用边 入栈调用边 入栈接下来分析返回边 此时栈 顶 是 与 对 应为 有 效路 径栈顶 出栈 变为栈顶此时分析与栈顶对应 出栈判 定 路 径 有 效 如 果 当 前分析的返回边 与栈顶对应则栈顶出 栈否 则 说 明所分析的路径为无效路径 于是在清空堆栈后返回图 被两个方法调用的软件行为图算法 过滤无效子图输 入需要检测是否有效的子图输 出子图是有效的还是无效的中 的 每 条 边为 调 用 边为 返 回 边与 不 对 应无 效期 苏 小 红 等 一种基于加权软件行为图挖掘的软件错误定位方法有 效最后在挖掘得到的多个错误签名之间可能具有包含关系因此定义下列规则 来合并相互包含的错误签名减少冗余对于两个存在包含关系的错误签名 和 无论 还是若 则删去这样存在包含关系的错误签名中 只会保留得分更高的错误签名 可以有效地减少冗余信息基于分支限界搜索的加权软件行为图挖掘本文采用如算法 所示的分支限界搜索算法来挖掘错误签名在错误定位中仅仅报告唯一的最佳错误签名往往并不足以提供足够的信息 按照可疑度降序给出多个 不 同 的 错 误 签 名更有助于开发者理解错误因此算法 会返回 个错误签名算法 挖掘 错误签名输 入加权软件行为图集合 结 果 数输 出 错 误 签 名中只包含一条边的子图从 中 选 择未检查过且有效用 式 和 计 算 和移 除 中 的 冗 余 结 果包含的错误签名数量大于移 除 中得分最小的错误签名扩 展 的最后一个节点并将其加入为了选择具有执行顺序的子图 算 法 每 次 只会扩展子图的最 后 一 个 节 点而不是在任意位置进行扩展该策略在提高了执行效率的同时也保证了子图能够具有执行顺序最后得到 的 错 误 签 名 就 可 以 作 为 错误定位的依据错误签名中包含的节点对应于可能导致错误发生的语句 可以用于进行错误理解错误签名实例以 中的 程序版本 为例展示 本 文 方 法 挖 掘 得 到 的 错 误 签 名 该 程 序 的函 数 中 存 在 如 图 所 示 的 缺 失 代 码错误第 行代码 中 包 含 一 个 缺 失 代 码 错 误 语 句的条件中缺失了一个条件 导致在某些情况下 本应执行第 行 语句块内的代码 但实际执行的却是第 行的 循环从而产生错误图 程 序 版 本 的代码片段及其得到的错误签名本文定位方法得到的错误签名如图 所 示错误签名中的 每 个 数 字 都 与 图 所 示 代 码 片 段的语句行号对应 该错误签名表示错误语句就在第和 这 行代码之中而且如果按照语句的顺序执行代码 就 很 可 能 会 导 致 错 误 开发者就可以根据错误签名给出的执行顺序 去 理 解为什么 会 产 生 错 误 找 到 并 修 正 真 正 引 起 错 误 的语句注 意 到 产 生 错 误 的 原 因 是 因 为 没 有 满 足 条 件因该条件缺失导致改变了程序的执行路径 即本应执行语句 却执行了语句 而此 时必 有 因 缺 失的条件 未 被 满 足 所 以 有这样 循环的条件一 定 为 假 因此会跳过循环体直接执行语句 最后 执 行 语 句 因 此实 际 产 生 错 误的执行路径是 与图 所示的错误签名是相同的这 个 例 子 说 明 错 误 签 名 与 实 际 产 生 错 误 的 执行路径是相同的 因此错误签名相当于指出了错误的执行路径有了这样的错误上下文信息 我们就可计 算 机 学 报 年以通过分析为什 么 会 执 行 这 个 错 误 的 路 径 原 因 一定是分支的判断 条 件 限 制 不 够 严 格 从 而 发 现 真 正产生错误的语句是语句 显 然 这 比 单 纯 地 给 出 最可疑的语句是语句 更有助于开发者理解错误产生的原因也更有利于开发者修正错误实 验采 用 语言实现了 语言词法语法分析工具程序插桩工具和本文方法方法实验建立本 文 方 法 采 用 被 广 泛 应 用 于 评 价 软 件 错 误 定位方法 有 效 性 的 和 程 序 集下 载 于 作 为 测 试 数 据测 试 集 全 部 采 用 语 言 编 写 程 序 规 模 较小并且由人工注入错误 每个程序都包含了数千个测试用例 是 系 统 下 的 一 个 真 实 的 语言程序其规模较大而且其中包含的错误都是生产过程中真实产生的 但测试用例数量较少 表 描述了 测试集和 的 程 序 信 息 包 括 程 序 名称错误版本数代码行数测试用例数及其描述表 实 验 数 据程 序错 误版 本 数代 码行 数测 试用 例 数描 述＿＿＿表中 列 出 了 个 错 误 版 本 但 由 于其中一些版本没 有 错 误 测 试 用 例或者错误位于头文件中或者运行时产生了段错误 因此只采用了其中 的 个错误版本再加上 程序的 个错误版本本文实验最终使用 个错误版本进行实验实 验 的 运 行 环 境 是内存评价指标实验选择 与 方 法 和 方 法进行比较 是一种实现比较简单的基于覆盖的错误定位方法 它的错误定位效果较好 常被用来作为错误定 位 方 法 的 比 较 对 象 则 是 一 种基于图挖掘的错误定位方法由于 方法会产生语句的可疑值列表因此采用文献 使用的错误定位方法精度评价指标 如果开发者从可疑值最高的语句开始按照可疑值降序 的 顺 序 检 查直到找到了错误所在的语句为止那么 就表示了在找到错误之前需要检查的代码百分比它的计算方法如式 所示其中 表示在找到错误之前需要检查的语句行数 表示可执行语句的行数由于本文方 法 和 方 法 产 生 的 是错误签名因此按照前 个 可 疑 值 降 序 的 顺 序 检 查每个错误签名将找到错误语句前需要检查的语句百分比作为代码检 查 率 的 计 算 类 似 于 是 按 照 定 位结果可疑度排序从高到低检查的代码行数占程序中可执行语句行数的百分比 两者的区别是在计算代码检查率时可能定位到也可能没有定位到缺陷语句而 是在定位到缺陷语句的情况下计算的实验结果总体分析图 展 示 了 测 试 集 上 本 文 方 法 与方法和 方法的总体错误定位精度折线图横轴表示需要检查的语句百分比 纵轴表示检查相应百分比 的 语 句 时 能够找到错误的错误版本百分 比横 轴 是 从 开 始 的表 示 只 检 查 的语句可以找到错误的错误版本百分比 可 以 看 到在检查相同百分 比 的 语 句 时本文方法总是可以比方法 和 方法定位到更多的错误而且至多只需要检查 的 代 码本文方法就可以定位到所有的错误图 测试集错误定位精度比较图 是 测试集中单个程序的错误定位结果可以很明显 的 看 到 对于不同的程序 错 误 定位的精度有较大的差异期 苏 小 红 等 一种基于加权软件行为图挖掘的软件错误定位方法图 单个程序的错误定位精度比较对于 ＿ ＿ 和 程序所有错误定位方法的效果都较好而本文方法效果最好对 于 程 序错误定位效果也比较好但 是 方 法 表 现 较 差 对 于 和＿ 程 序仍然是本文方法的错误定位精度最高但明显无法与前 个程序的错误定位精度相比计 算 机 学 报 年而对于 程 序则 是 方法的错误定位的精度要更高些 本文方法的错误定位精度略高于方法图 则是 程序的错误定位精度比较 可以看到 种方法 的 错 误 定 位 精 度 都 较 高而 且 仍 然是本 文 方 法 效 果 最 好 其 次 是 方 法最 后 是方法图 程序错误定位精度比较为了找到不同程序上的错误定位精度差异较大的原因我们在下面的实验中进一步按照不同的错误类型分别对错误定位结果进行分析针对不同错误的结果分析实验使用的 个 错 误 版 本 按 照 错 误 类 型 进行分类总计包含 个 冗 余 代 码 错 误 添 加 了 多 余的代码 个 缺 失 代 码 错 误 删 除 了 部 分 代 码个运算符变 异 错 误 运 算 符 发 生 了 改 变 个常量变异错误常量值发生了变 化 个 变 量 替 换使用的变量发 生 了 改 变 和 个 其 他 错 误 采 用 箱式图显示每种错 误 类 型 的 错 误 定 位 结 果 箱 式 图 描述了数据的统计 结 果 它由数据样本的五个重要数据统计点组成最大值最小值四分之一位数四分之三位数和中位数这里 以 方法作为比较的基准 将方法与本文方法 的 之 差 作 为 纵 轴记为 如式 所示本 文 方 法若 大于 零表 示 本 文 方 法 检 查 更少的代码就能定位到错误 定位精度优 于方法若 小于零则表示本文方法需要检查更多的语句才能定位到错误 定 位 精 度 比方法要差从图 可 以 看 到对 于 冗 余 代 码 缺 失 代 码 和变量替换错误本文方法大多都只需要检查更少的语句就能够定位 到 错 误 而少部分精度变差的 也小于 而对于运算符变异常量变异和其他错误本文方法 则 有 优 有 劣 约 有 的 错 误 定 位 精度变差了但变差幅度大于 的只占图 不同错误类型的 分 布再 考 虑 另 一 种 错 误 分 类 方 式部分错误可能会直接导致程序的 执 行 路 径 发 生 改 变例 如 语 句 中的条件发生了错 误 会直接令程序执行路径发生变化而另一些错误则不会直接导致程序执行路径发生改变例如变量赋值中发生了错误程序执行路径并未立刻发生变化 只有之后再用到该变量时 程序执行路径才可能发生变化按照这一方 式 来 分 类 实 验 使 用 的 个 错 误版 本包含 个会直接导致程序执行路径发生改变的错误 个不会直接导致程 序 执 行 路 径 改 变 的 错误同样使 用 箱 式 图 显 示 两 类 错 误 的 定 位 结 果如图 所 示可 以 发 现对于会直接改变程序执行路径的错误本 文 方 法 基 本 都 是 优 于 方 法的而对于不会直接导致程序执行路径发生变化的错误本文方 法 同 样 是 有 优 有 劣约 有 的 错 误定位精度变差了 而变差幅度大于 的约占图 是否直接改变执行路径的错误的 分 布综 合 分 析 以 上 两 个 实 验 可 以 发 现 本 文 方 法 对不同的错误类型 定位精度有比较明显的不同 对于冗余代码缺失代码和变量替换错误 以及会直接改变执行路径的错误的定位精度明显更高 如 果 将 这期 苏 小 红 等 一种基于加权软件行为图挖掘的软件错误定位方法些错误类型记为优势错误 将剩余的错误类型 不会直接改变执行路 径 的 运 算 符 变 异常量变异和其他错误记为劣势错误那么优势错误有 个劣势错误有 个优 势 错 误 和 劣 势 错 误 的对比结果如图 所示可以看到对于优势错误本文方法的 定 位 精 度 大 多 都 优 于 方 法而对于劣 势 错 误 本 文 的 定 位 精 度 则 普 遍 要 略 差 于方法图 所示的优势错误和劣势错误的 错 误 定 位 精 度 比 较 也 证 明 了 这 一 点 而 且图 优势错误和劣势错误的 分 布图 优势错误和劣势错误的错误定位精度比较方法也具有相同 趋 势 并且无论是对优势错误还是劣势错误本文方法 都 比 方 法 的 错 误 定 位 精度高性能分析表 给出了 种方法定位分析每个错误版本的平均时间 是基于语句覆盖的分析因此具有较高的时间效率 本 文 方 法 和 方 法 均 涉 及到图的分析两者时间开销相近表 时 间 分 析程 序定位每个版本的平均时间本 文 方 法＿＿＿讨 论本文方法的不足根据 本 文 方 法 与 方 法 对 比 实 验 的 结果可以得到以下结论 本文的错误定位方法对冗余代码缺失代码和变量替换错误以及会直接改变执行路径的错误的定位精度明显提高而 对 不 会 直 接改变执行路径的 运 算 符 变 异常量变异错误的定位精度的提高则不明显分 析 产 生 这 种 情 况 的 原 因是 由 于 本 文 方 法 会在成功的执行和失败的执行之间找到加权软件行为图差异最大的子 图 即当程序的执行路径出现明显差异时本文方法 比 较 有 效 反 之因本文方法的特点不能 被 有 效 利 用 而 使 得 其 错 误 定 位 的 优 势 不明显文献 的 研 究 表 明 一条语句的错误可能会影响到程序状态 而随着程序的继续执行 被影响的程序状态可能会被进一步传播 也就是说程序的执行路径发生变化 的 位 置 并不一定是真正导致错误的语句而可能是其他语句的错误通过程序状态不断传播直到导致程序的执行路径发生改变也 就 是 说本 文 方 法 对 于 在 错 误 语 句 附 近 就 能够观察到程序执行路径发生改变的错误 一 般 都 能具有比较好的定 位 精 度 而对于会将错误传播出去很远才发生执行路径变化的错误往往只能定位到执行路径发生变 化 的 位 置 虽然该位置与实际的错计 算 机 学 报 年误语句也具有一 定 的 相 关 性但因其并不是真正产生错误的语句从而导致错误定位的精度下降可改进之处针对 节中本文方法的适应性问题可 以 尝试捕获更多的程序状态 如谓词的真假等信息 而不仅仅是程序的执行路径 在进行图挖掘时 可以综合考虑更多的信息或融合其他的错误定位算法 来 提高对劣势错误的定位精度对 于 错 误 传 播 对 错 误 定 位 精 度 的 影 响 单 独 的应用图挖掘算法 可 能 难 以 解 决 这 一 问 题 因 此 可 以尝试分析程序的 控 制 依 赖 或 数 据 依 赖 并 依 此 对 错误的传播进行分 析 进而可能减少错误传播带来的影响讨 论本文提出了一种新的基于加权软件行为图挖掘的错误定 位 方 法 与 方 法 和 方 法相比本文方法具有更高的错误定位精度而且更适合于定位冗余代码 缺失代码和变量替换错误 以及会直接改变执行路径的错误本文的主要贡献是提出 了 加 权 软 件 行 为 图 的 概 念 和 构 造 方法并将其用于错 误 定 位 与软件行为图相比 加 权软件行为图使用语句执行概率作为边的权重 有 效地利用了路径执 行 的 统 计 信 息因此可以更好地分析与循环和递归等结构相关的软件错误提出一种 基 于 分 支 限 界 搜 索 的 加 权 软 件 行为图挖掘算法识别成功和失败执行之间最有差异的子图来获得错 误 签 名 不但可以有效定位错误位置还能输出缺陷语句相关的执行路径从而提供失效产生的上下文 有助于错误理解从理论和 实 验 两 个 方 面 分 析 了 基 于 加 权 软件行为图挖掘的 错 误 定 位 方 法 的 适 应 性 通 过 对 错误进行分类讨论了本文方法对不同错误类型的错误定位精度的影响参 考 文 献苏 小 红 龚 丹 丹 王 甜 甜 马 培 军 结合用例约简与联合依赖概率建模的错误定位 软 件 学 报虞 凯 林 梦 香 自动化软件错误定位技术研究进展 计 算 机学 报期 苏 小 红 等 一种基于加权软件行为图挖掘的软件错误定位方法计 算 机 学 报 年