能量高效的传感器网络空间范围聚集

Transcription

1 计算机学报 CHINESEJOURNALOFCOMPUTERS 软件多缺陷定位方法研究综述 李征 1) 1) 1) 2) 1) 吴永豪王海峰陈翔刘勇 1) ( 北京化工大学信息科学与技术学院, 北京 ) 2) ( 南通大学信息科学技术学院, 江苏南通 ) 摘要软件多缺陷定位 (MultipleFaultLocalization, 简称 MFL) 尝试在含有多个缺陷的软件程序中自动标识出这些缺陷所在 的位置 传统的缺陷定位研究一般假设被测软件内仅含有一个缺陷, 而实际情况下软件内往往包含多个缺陷, 因此 MFL 问 题更加贴近实际场景 当程序中存在多个缺陷时, 由于缺陷数量难以准确估计, 同时缺陷之间可能存在互相干扰, 因此对 MFL 问题的研究更具挑战性 已有研究表明传统单缺陷假设下的缺陷定位技术会随着程序中缺陷数目的增多而出现定位效 果下降的问题 因此, 需要对已有缺陷定位技术加以改进使其在 MFL 问题中具有更好的缺陷定位效果 本文以 MFL 研究 问题为核心, 对相关研究成果进行了系统的梳理 首先将已有的 MFL 技术细分为三类, 分别是基于缺陷干扰假设的多缺陷 定位方法, 基于缺陷独立假设的多缺陷定位方法和不基于任何假设的多缺陷定位方法 ; 然后依次总结了每一类方法的主要设 计思想和相关研究成果, 随后分析了 MFL 研究中经常使用的评测指标和评测对象 ; 最后, 本文从扩大评测对象的编程语言 范围 考虑更多的软件程序 寻找更多的工业应用场景等多个角度对 MFL 的未来研究方向进行了展望 关键词软件调试 ; 多缺陷定位 ; 缺陷干扰 ; 缺陷独立中图法分类号 TP311 ReviewofSoftwareMultipleFaultLocalizationApproaches LIZheng 1), WUYong-Hao 1), WANGHai-Feng 1), CHENXiang 2), LIUYong 1) 1) (CollegeofInformationScienceandTechnology, BeijingUniversityofChemicalTechnology, Beijing100029) 2) (SchoolofInformationScienceandTechnology, NantongUniversity, Nantong226019) Abstract With the development of the computer and electronic information industry, computer software's functions and scale have become increasingly complex and large, bringing unprecedented challenges to software debugging. When defects occur in the software, developers need to spend an incalculable workload to debug the software, and the first step in software debugging is to find the location of the defect, that is, the fault localization. There has been a drastic growth of research in Multiple Fault Localization (MFL) in the past few years. MFL attempts to automatically identify multiple fault locations in a software program with multiple defects. Traditional fault localization techniques generally assume that the software programs under test only contain one single fault, but in reality, the software often contains multiple defects, so the MFL problem is closer to the debugging scenarios. However, Compared with the fault localization of programs containing only a single defect, MFL research is much more difficult. When multiple defects in the program under test, it is difficult to estimate the accurate number of defects in this scenario, and the multiple faults may interfere with each other, which are the problems that will not be encountered in the process of single defect fault localization; hence the MFL problem is quite a challenging problem. Studies have shown that the fault localization accuracy of techniques designed for single-fault localization will be decreased when there are multiple faults in the software programs under test. Therefore, it is necessary to improve the fault localization performance in MFL problem. This survey takes the MFL research problem as the core and offers a systematic overview of existing research achievements. In this survey, we firstly classified these MFL techniques into three groups, which are Defect Interference Hypothesis 本课题得到国家自然科学基金 ( , , ) 南通市应用研究计划 (JC ) 资助. 李征, 博士, 教授, 计算机学会 (CCF) 会员 (E S), 博士生导师, 主要研究领域为软件测试 源代码分析和维护. lizheng@buct.edu.cn. 吴永豪, 博士研究生, 主要研究领域为 软件测试和错误定位. appmlk@outlook.com. 王海峰, 博士研究生, 主要研究方向为软件测试 错误定位和软件缺陷预测. h.f.wang@hotmail.com. 陈翔 ( 通讯作者 ), 博士, 副教授, 计算机学会 (CCF) 会员 (25917S), 主要研究领域为软件维护和软件测试. xchencs@ntu.edu.cn. 刘勇 ( 通讯作者 ), 博士, 计算机学会 (CCF) 会员 (48965M), 主要研究领域为源代码分析 变异测试和错误定位. lyong@mail.buct.edu.cn.

2 2 计算机学报 based MFL (INF-MFL), Defect Independence Hypothesis based MFL (IDP-MFL), and None Hypothesis based MFL (NOH-MFL). INF-MFL method only locates and repairs a single defect each time during debugging. When a single defect is repaired, all test cases are re-executed to collect coverage information and execution results until all defects are repaired. IDP-MFL method divides the MFL task into multiple single fault localization subtasks so that different developers can perform parallel debugging on different subtasks. NOH-MFL method attempts to locate multiple defects at the same time in a debugging process. Then, we summarized the design ideas and detailed research results of each MFL technique. Among them, the INF-MFL method is currently the most studied in MFL, and it is widely used because of its simple implementation. We further analyzed the evaluation metrics, Statistical hypothesis test method, and subject programs used in MFL research. Specifically, In MFL research, manual defects are often used to simulate real defect behavior. However, in recent years, researchers believe that this kind of defect will impact the validity of empirical research conclusions and cause the industry to question the practicability of fault localization technology. Therefore, more and more researchers use real procedures with real defects to conduct empirical research to ensure the validity of research conclusions. Finally, we discussed future research directions of MFL, which include: Further study the granularity of fault localization, optimize fault localization technology from the perspective of time cost, consider projects implemented in more other programming languages, consider more software features, combine MFL with defect prediction, and find more industrial application scenarios. Keywords SoftwareDebugging; MultipleFaultLocalization; DefectInterference; DefectIndependence 1 引言 软件调试是保障软件质量并使其正常运行的 重要手段 [1] 软件调试过程中, 确定程序内的缺 陷语句所在位置被称为软件缺陷定位 (SoftwareFaultLocalization), 是软件调试过程中最 为费时费力的一个步骤 [2] 自动化软件缺陷定位 方法旨在不需要或较少需要人为干预的前提下, 自动确定程序内缺陷所在位置, 以帮助开发人员 更快地修复缺陷 其中, 基于程序谱的缺陷定位 技术 (Spectrum-basedFaultLocalization, SBFL) 是一 种常用的自动化缺陷定位技术 [3], 程序谱是指测 试用例在执行期间产生的特征向量 因为失败测 试用例产生的特征向量不同于通过测试用例, 通 过比对特征向量之间的差异, 可以计算出代码中 各个语句包含缺陷的可能性 ( 即怀疑度 ), 怀疑度 值越高的语句则越有可能包含缺陷 在早期的自动化缺陷定位研究中, 绝大部分 研究工作假设被测程序仅含有一个缺陷 研究人 员针对单缺陷程序提出了大量的缺陷定位技术, 并且取得了不错的定位效果 [4,5,6,7] 但是, 单缺陷 假设并不符合实际的软件调试场景特征 在商业 项目或开源项目中, 通常会包含多个缺陷, 甚至部分缺陷之间还会存在相互干扰 [8,9] [10] Xue 等人 的研究工作表明, 一些缺陷定位方法虽然在单缺 陷程序上可以取得较好的定位效果, 但在多缺陷 程序上, 其定位效果会出现显著下降 因此本文 重点关注的软件多缺陷定位 (MultipleFaultLocalization, 简称 MFL) 问题, 比传统的软件单缺陷定位问题更具研究挑战性 其面临的主要挑战包括 :(1) 当被测程序内包括多个缺陷时, 难以精准地确定各个缺陷和与其关联的失败测试用例, 即无法判断单个失败测试用例是因为执行哪个缺陷所导致的 ;(2) 程序内含有的实际缺陷数难以精确估计 ;(3) 部分缺陷之间可能存在相互干扰的问题 例如, 单缺陷下存在某个测试用例执行失败, 但引入新的缺陷后, 该测试用例可能就会执行通过, 并导致无法精确定位到各个缺陷的实际位置 因此 MFL 逐渐成为软件自动缺陷定位领域的一个热点问题, 并引起研究人员的广泛关注 近些年来, 研究人员对 MFL 问题展开了深入的研究, 重点集中于分析缺陷之间的相互影响和提升多缺陷定位的效果和效率 为了对该综述主题进行系统的梳理, 我们在 IEEEXplore ACM ScienceDirect Wiley Springer 中国知网等国内外相关论文数据库中搜索与综述主题相关的论文, 查询的英文关键词包括 : programfaultlocalization 和 softwarebugdetect 等 ; 查询的中文关键词包括 : 缺陷定位 和 错误定位 等 但是在相关论文检索时, 我们没有直接使用 multiplefault 或 multiplebug 这样的关键词, 是因为我们发现在综述时有一些论文虽然探讨了 MFL 问题, 但在标题和摘要中并没有包含这些关键词, 因此使用这些关键字会遗漏一

3 发表论文数 李征等 : 软件多缺陷定位方法研究综述 3 些相关论文 在论文的搜索过程中, 我们发现与缺陷定位相关的研究工作数量较多 因此, 我们遵循以下原则来选择文献 : 1. 研究论文与综述主题相关, 排除与多缺陷研究无关的文献 ; 2. 只选择在同行评议期刊 / 会议上发表的研究论文 ; 3. 如果论文首先发表在会议上, 随后扩充版本发表在期刊上, 则仅选择发表在期 刊上的论文 ; 4. 仅考虑中文和英文的文献 接下来将论文的搜索过程总结如下, 我们首先下载了与上述关键词相关的所有论文, 然后借助手工分析方式逐一筛选出与 MFL 问题相关的论文 随后查阅这些论文对应的相关工作和研究人员已发表论文列表来进一步补充论文 最终确定了与该综述主题相关的论文共 87 篇 ( 截止到 2020 年 7 月 ) 表 1MFL 相关论文发表源统计结果 发表源全程 ( 简称 ) 发表源 类型 期刊 / 会议 级别 论文数 JournalofSystemsandSoftware (JSS) 期刊 CCFB 类 12 IEEETransactionsonSoftwareEngineering (TSE) 期刊 CCFA 类 5 InternationalSymposiumonSoftwareReliabilityEngineering (ISSRE) 会议 CCFB 类 5 InformationandSoftwareTechnology (IST) 期刊 CCFB 类 3 InternationalConferenceonAutomatedSoftwareEngineering (ASE) 会议 CCFA 类 3 SoftwareQualityJournal (SQJ) 期刊 CCFC 类 3 Software:PracticeandExperience (SPE) 期刊 CCFB 类 3 计算机学报 期刊 一级学报 2 计算机研究与发展 期刊 一级学报 2 FrontiersofComputerScience (FCS) 期刊 CCFC 类 2 InternationalConferenceonSoftwareMaintenanceandEvolution (ICSME) 会议 CCFB 类 2 InternationalConferenceonSoftwareQuality,ReliabilityandSecurity (QRS) 会议 CCFC 类 2 InternationalConferenceonSoftwareTesting,VerificationandValidation (ICST) 会议 CCFC 类 2 InternationalSymposiumonSoftwareTestingandAnalysis (ISSTA) 会议 CCFA 类 年份图 1MFL 相关论文年度统计结果图 1 统计了 MFL 领域每年发表的论文数量 从图中可以看出, 与 MFL 相关的研究工作呈大致上升的趋势, 在 2016 年至 2019 年, 这种上升趋势尤其明显 表 1 中对 MFL 相关论文的发表数量进行了统计, 并按照发表的论文总数从大到小进行排序 ( 表中仅列出了中国计算机学会推荐的英文期刊 / 会议和中文核心期刊, 且发表数量至少 2 篇 ) 不难看出, 与 MFL 相关的研究工作主要集中于软件工程领域的权威期刊和会议上, 例如 : 在 JSS 期刊上发表 12 篇, 在 TSE 期刊上发表 5 篇, 在 ISSRE 会议上发表 5 篇, 在 ASE 会议上发表 3 篇, 在 ISSTA 会议上发表 2 篇 软件自动缺陷定位是近些年来软件自动调试 领域的一个重要研究问题, 在 Wong 等人 [1] 2016 年发表在 IEEETransactionsonSoftwareEngineering 上的 综述中, 他们将已有的缺陷定位方法细分为八类 : 基于切片的方法 基于程序频谱的方法 基于统 计的方法 基于程序状态的方法 基于机器学习 的方法 基于数据挖掘的方法 基于模型的方法 和其他方法 国内研究人员针对该问题在 计算 机学报 和 软件学报 上也先后发表了三篇综 述论文 [11,12,13] 但与上述综述不同, 本文主要关 注的是软件自动缺陷定位领域中的一个子问题, 即多缺陷定位问题, 并系统地分析了多缺陷定位 问题在近 12 年 ( 即 2009 年至 2020 年 ) 内取得的重 [14] 要研究成果 虽然 Zakari 等人对多缺陷定位问

4 4 计算机学报 题也进行过系统综述, 但与该综述相比, 本文覆盖了更多的与多缺陷定位相关的研究论文, 累计新增论文 32 篇, 并且本文对每一类型的方法进行了机理分析以及更为细致的分析和评点 除此之外, 本文还额外统计整理了多缺陷定位研究中常用的性能评测指标 统计显著性分析方法和常用评测对象, 以方便研究人员进行合理的实验设计 本文的主要贡献可总结如下 : 1. 通过搜集分析在国内外权威期刊和会议上发表的相关文献, 系统地分析了 MFL 领域近 12 年来取得的研究成果, 提出 MFL 的研究框架并识别框架内的影响因素 ; 2. 将已有的 MFL 方法细分为三类 : 基于缺陷干扰假设的多缺陷定位方法, 基于缺陷独立假设的多缺陷定位方法以及不基于任何假设的多缺陷定位方法 详细分析了三种 MFL 方法的机理并举例说明其执行过程 针对每一类方法, 我们依次分析了研究人员的解决思路, 并对属于同一类的不同方法进行了系统的比较与分析 ; 3. 总结了 MFL 方法在实证研究中经常使用的评测指标和评测对象, 并对评测指标和评测对象的使用趋势进行了分析 上述分析有助于为后续研究工作更好地进行实证研究设计提供有价值的指导 本文剩余的内容安排如下 : 第 2 节给出 MFL 方法的整体研究框架, 对三种 MFL 方法的机理进行详细分析, 并举例说明其执行过程 ; 第 3 节对基于缺陷干扰假设的多缺陷定位方法进行详细分析 ; 第 4 节对基于缺陷独立假设的多缺陷定位方法进行详细分析 ; 第 5 节对不基于任何假设的多缺陷定位方法进行详细分析 ; 第 6 节和第 7 节分析并统计了研究人员在 MFL 问题上经常使用的性能评测指标和显著性分析方法 ; 第 8 节分析并统计了经常使用的评测对象 ; 最后总结全文, 并对 MFL 领域未来值得关注的研究方向进行深入探讨 2 研究框架 本文研究 MFL 方法的整体框架如图 2 所示, 首先将已有 MFL 方法根据调试模式的不同细分 为三类, 随后总结已有 MFL 研究中经常使用的程 序评测对象 性能评测指标和统计显著性分析方 法 基于缺陷独立假设的多缺陷定位 评测对象 Siemens test suite Unix programs Space Defects4J 多缺陷位方法 基于缺陷干扰假设的多缺陷定位 性能评估指标 Exam score Expense score Top-N Wasted effort 不基于任何假设的多缺陷定位 统计显著性分析 曼 - 惠特尼 U 检验 Wilcoxon 符号秩检验 Student T 检验 Quade 检验 图 2 多缺陷定位方法的整体研究框架 2.1 多缺陷定位方法分类 根据开发人员对多缺陷行为的不同假设, 我 们将已有的 MFL 方法分为三类 : 1. 基于缺陷干扰假设的多缺陷定位 (DefectInterferenceHypothesisbasedMFL, 简称 INF-MFL) 的调试方法, 这类方法在 调试中每次仅定位并修复单个缺陷, 当 修复完单个缺陷后, 会重新执行所有测 试用例来收集覆盖信息和执行结果, 直 至所有缺陷都被修复 ; 2. 基于缺陷独立假设的多缺陷定位 (DefectIndependenceHypothesisbasedMFL, 简称 IDP-MFL) 的调试方法, 这类方法 将 MFL 任务划分为多个单缺陷定位任务 ( 即子任务 ), 以方便不同开发人员可以在 不同的子任务上进行并行调试 ; 3. 不基于任何假设的多缺陷定位 (NoneHypothesisbasedMFL, 简称 NOH-MFL) 的调试方法, 这类方法在一次 调试中尝试同时定位多个缺陷所在位 置 我们对不同类型的方法在已有工作中所占的 比例进行了统计, 统计结果如表 2 所示 表 2MFL 研究方法类型占比 方法类型论文数所占比例 基于缺陷干扰假设的多缺 陷定位 (INF-MFL) 基于缺陷独立假设的多缺 陷定位 (IDP-MFL) % % 不基于任何假设的多缺陷 %

5 李征等 : 软件多缺陷定位方法研究综述 5 定位 (NOH-MFL) 其中有 65.52% 的研究工作采用的是 INF-MFL 调试方法,22.99% 的研究工作采用的是 IDP-MFL 调试方法,11.49% 的研究工作采用的是 NOH-MFL 调试方法 可以看出, 基于缺陷干扰 假设的多缺陷定位的 INF-MFL 方法是目前 MFL 研究领域内的主流方法, 基于缺陷独立假设的多 缺陷定位方法的 IDP-MFL 方法次之, 不基于任何 假设的多缺陷定位的 NOH-MFL 方法则相对较 少 本文随后在 2.1 节对三种 MFL 方法的机理进 行详细分析, 并在 2.2 节通过一个简单示例来分 析不同类型的多缺陷定位方法的主要思想, 之后 在第 3 节, 第 4 节和第 5 节分别整理和剖析了这 三种 MFL 方法的研究动机 研究进展与现状, 以 及潜在的问题与改进之处 2.2 多缺陷定位机理分析 多缺陷定位的难点主要体现在分析多个缺陷 如何交互以表现为新的缺陷行为, 针对新缺陷行 为的分析方式对设计软件调试策略至关重要 然 而基于不同的测试环境 被测程序或假设检验方 法, 研究人员会得出不同的分析结论 本文汇总 的三种软件调试策略本质上是针对不同的新缺陷 行为的分析模式而提出的 多缺陷行为 程序中的多个缺陷可能以多种方式相互影 响, 从而产生仅包含其中任意一个缺陷的单缺陷 程序都无法实现的新行为 新的缺陷行为存在有 多种类型, 且对传统的单缺陷定位技术产生难以 [15] 预料的负面影响,Digiuseppe 等人对缺陷相互 影响进行了深入研究, 并把多缺陷行为分为四种 类型 : (1) 缺陷协同 : 与单缺陷程序相比, 通过测 试用例检测的缺陷表现增多 ; (2) 缺陷混淆 : 与单缺陷程序相比, 通过测 试用例检测的缺陷表现减少 ; (3) 缺陷独立 : 与单缺陷程序相比, 通过测 试用例检测的缺陷表现无变化 ; 淆 (4) 混合类型 : 同时发生缺陷协同和缺陷混 因此, 研究人员针对上述多缺陷行为提出了 众多的多缺陷程序定位方法, 这些方法根据其对 多缺陷行为的假设可被分为 3 类 : 基于缺陷独立 假设的多缺陷定位方法 基于缺陷干扰假设的多 缺陷定位方法和不基于任何假设的多缺陷定位方 法 其中基于缺陷独立假设的多缺陷定位方法假 设多缺陷程序中各缺陷相互独立 ; 基于缺陷干扰 假设的多缺陷定位方法假设多缺陷程序中各缺陷 相互影响, 从而可能产生缺陷混淆或缺陷协同现 象 ; 不基于任何假设的多缺陷定位方法假设缺陷 独立和缺陷相互影响两种情况都有可能存在 下 文将详细介绍上述三种方法的缺陷定位依据以及 在其假设中的缺陷定位流程 基于缺陷独立假设的多缺陷定位方法 基于缺陷独立假设的多缺陷定位方法假定同 一程序中的不同缺陷相互独立, 即单个程序中的 缺陷之间不会发生交互, 从而不会产生新的缺陷 行为 T4 T 8 T 1 B 1 T 2 T 5 T 3 B 2 B 3 T 7 T 9 图 3 缺陷独立示例图 如图 3 所示的是一个缺陷相互独立的程序中 的测试用例 - 程序缺陷关系图,B 1 B 2 和 B 3 指的 是 3 个程序缺陷,T 1-9 表示 9 个测试用例 单个测 试用例位于某个缺陷的影响范围内, 表示该测试 用例被对应的缺陷影响而失败 例如图中的 T 1-4 被缺陷 B 1 影响而失败,T 5-7 被缺陷 B 2 影响而失败, T 8-9 被缺陷 B 3 影响而失败 在缺陷相互独立的假设中, 程序的每一个缺 陷行为都有其唯一对应的程序缺陷 [16] 因此, IDP-MFL 方法通常试图对失败的测试用例进行划 分成组, 且使每组中测试用例仅对应于单个导致 该测试用例失败的程序缺陷 [17] 以图中所示关系 图为例, 测试用例应该被划分为三组 :T 1-4 为一组 ( 对应缺陷 B 1 ) T 5-7 为一组 ( 对应缺陷 B 2 ) T 8-9 为一组 ( 对应缺陷 B 3 ) 最后软件测试人员使用 单组内的测试用例对其对应的程序缺陷进行定 位 综上所述,IDP-MFL 方法获得的同一组中的 失败测试用例均与同一个程序缺陷相关 但在实 T 6

6 6 计算机学报 践过程中, 多缺陷的真实行为并不一定完全符合 该多缺陷定位方法的假设, 即程序中不可避免地 会存在缺陷协同和缺陷混淆的情况 [18] 为此,Yan 等人进行了一个实证研究 [19], 他们的实验结果表 明缺陷独立假设在大多数情况下成立, 且超过 50% 的失败测试用例仅执行了程序中的单个缺 陷, 该结果为 IDP-MFL 方法的提出提供了支持 除此之外,IDP-MFL 方法还受到另一个因素 的挑战 即该方法通常采用基于相似度的聚类算 法进行测试用例划分, 而聚类算法不一定能够得 到完全正确的结果 因此可能存在测试用例划分 之后, 分组数量少于程序真实缺陷数量的情况 此时软件测试人员无法在单次迭代中通过每个分 组定位所有程序缺陷 为了解决这个问题, 研究 [20] 人员提出了迭代的方法进行 IDP-MFL 方法的 缺陷定位, 即重复进行测试用例执行 分组和缺 陷定位的过程, 直至不再出现失败的测试用例 基于缺陷干扰假设的多缺陷定位方法 尽管实证研究表明超过 50% 的失败测试用例 仅执行了程序中的单个缺陷 [19], 但是在多缺陷程 序中依然存在多种缺陷相互影响的情况, 因此 INF-MFL 方法不完全认同单个程序中的不同缺陷 相互独立的假设, 即不同缺陷之间可能会相互影 响, 从而产生缺陷协同或混淆的现象 当缺陷协同发生时, 程序出现了新的缺陷行 为, 即同一个失败测试用例有可能执行多个程序 缺陷 [21], 此时程序缺陷与测试用例无法一一对应 图 4 中展示的是一个发生了缺陷协同的测试用例 - 是使用 INF-MFL 方法对图 4 中的缺陷协同进行缺 陷定位的效果示意图, 图中 B 1 被定位并修复,T 1-3 变为通过测试用例, 从而解决缺陷协同问题 T1 T 2 B 1 T 7 B 2 T 6 T 5 T 3 定位 B 1 并修复 T1 T 4 T 7 T 6 T 2 F 1 B 2 图 5INF-MFL 方法解决缺陷协同 除此之外, 缺陷混淆对测试用例的影响更加 显著, 因为缺陷混淆的存在会使得测试用例检错 能力降低, 即测试用例能够在单缺陷程序中检测 到缺陷 ( 产生失败测试用例 ), 但是在多缺陷程序 中却无法检测到缺陷 [22] 在这基础上,Debroy 和 Wang 对缺陷的相互干扰进行了进一步详细的分 析 [21], 他们在实证研究中进一步提出了缺陷掩盖 现象 缺陷掩盖是一种缺陷混合类型相互影响的 极端情况, 发生缺陷掩盖时, 某个程序缺陷相关 的失败测试用例因缺陷混淆与该缺陷失去关联 ( 即不再执行该缺陷 ), 而这部分缺陷却同时与另 一个程序相关联, 即前者被后者完全掩盖, 此时 前一个缺陷无法被测试用例检测 图 6 中展示的 是一个发生了缺陷混淆的测试用例 - 程序缺陷关 系图, 从图中可以看出, 程序缺陷 B 1 部分掩盖了 缺陷 B 2, 且完全掩盖了缺陷 B 3 T 5 T 3 T4 程序缺陷关系图, 从图中可以看出, 程序缺陷 B 1 T 1 和 B 2 共同导致了测试用例 T 1-7 的失败, 此时 T 1-7 无法通过 INF-MFL 方法进行有效划分 T 8 T2 T 1 T 7 B 1 T 3 T 2 T 4 B 1 T 5 T 6 T 5 T 4 B 2 T 9 T 3 B 2 B 3 T 8 B 3 T 6 T 7 T 9 图 4 缺陷协同示例图使用 INF-MFL 方法对图 4 中的协同缺陷进行缺陷定位, 能够在每次迭代中定位并修复单个程序缺陷, 直至解决缺陷协同问题 如图 5 所示的 图 6 缺陷掩盖示例图此时 B 1 已主导了程序的缺陷行为, 即大部分测试用例均与 B 1 相关联, 因此这种情况下使用 INF-MFL 方法进行缺陷定位能够实现与单缺陷程序缺陷定位类似的调试环境, 从而获得良好的缺陷定位效果 当前已有研究表明, 缺陷掩盖的发生频率高于其他类型的多缺陷行为 [19,21], 因此当

7 李征等 : 软件多缺陷定位方法研究综述 7 多缺陷程序中缺陷相互影响的情况时,INF-MFL 方法依然能够有效地完成缺陷定位 不基于任何假设的多缺陷定位方法不基于任何假设的多缺陷定位方法创新性的规避了多缺陷行为差异的问题 具体来说, 该方法会同时给多个 ( 或单个 ) 程序实体 ( 变量 语句或实体 ) 计算怀疑度并排序, 从而实现把单个测试用例与多个 ( 或单个 ) 程序缺陷进行对应 因此该方法能够在缺陷协同和缺陷独立的情况下完成缺陷定位 关于 NOH-MFL 方法的一种可行的策略是抽取程序实体进行排列组合, 然后设计一个适应度函数对每个排列组合的选项进行排序 [23] 图 7 中 所示的是一个适应度分数的排名结果示例图, 其中 B 表示包含缺陷的程序实体,N 表示不包含缺陷的程序实体 理想情况下排名越高的程序实体组合越有可能包含更多的程序缺陷, 从而实现在单次迭代内定位出程序中的所有缺陷 排名第 1: B 1 B 2 B 3 排名第 2: B 1 B 2 排名第 3: B 2 B 3 排名第 4: B 1 N 1 排名第 5: N 1 N 2 图 7NOH-MFL 方法适应度分数排名示例图 t1 t2 t3 t4 t5 t6 Sus Sus (IDP-MFL) defjudge(year): 1st 2nd (INF-MFL) cluster cluster 1:flag = false :ifyear % 100 == 0: :ifyear % 400 == 0: :flag = false # 应该为 true :else: :flag = true # 应该为 false :elifyear % 4 == 0: :flag = true :print (flag) Fail/ Pass P P F F F F 表示该语句被对应的测试用例覆盖 P 表示该测试用例执行通过,F 表示该测试用例执行失败 图 8MFL 示例 2.3 多缺陷定位示例分析位到第一个缺陷语句需要检查 5 行语句 当修复完该缺陷语句后, 开发人员需要重新编译程序并图 8 给出了一个示例程序, 该节将基于这个执行测试用例以搜集覆盖信息和执行结果, 开发示例程序来简要分析三种 MFL 方法的主要执行人员将根据 Ochiai 公式重新计算每个语句的怀疑过程 该示例程序 P 用于判断输入的年份是否为度, 按照怀疑度取值形成语句有序列表, 并依次闰年, 其中包含两个缺陷, 分别是语句 4 和语句检查每个语句, 直至定位到第二个缺陷语句 6, 该程序的配套测试套件 (TestSuite) 共包含 6 个若使用 IDP-MFL 调试方法, 开发人员首先将测试用例 {t1,t2,t3,t4,t5,t6}, 图中给出了每所有失败测试用例按照其特征 ( 例如覆盖信息 ) 划个测试用例的输入取值 代码覆盖情况和执行结分到两个类簇 (Cluster), 随后分别基于两个类簇计果 需要说明的是, 我们在这个示例程序中, 以 Ochiai [24] 算出相应的怀疑度并形成不同的语句有序列表 公式为例来计算 INF-MFL 和 IDP-MFL 对于图 8 所示的示例程序, 不难看出, 第一个类调试方法对应的语句怀疑度 ( 即含有缺陷的可能簇主要针对缺陷语句 4, 第二个类簇主要针对缺性 ) 陷语句 6 最后, 可以为两个开发人员分别提供若使用 INF-MFL 调试方法, 开发人员首先根不同的语句有序列表, 以支持对两个缺陷语句的据 Ochiai 公式计算出每个语句的怀疑度, 并按照并行定位 怀疑度取值从大到小依次检查, 直至定位到第一若使用 NOH-MFL 方法, 其流程与 INF-MFL 个缺陷 对于图 8 所示的示例程序, 开发人员定

8 8 计算机学报 方法相似, 但不同之处是, 开发人员在找到第一 个缺陷语句之后, 会继续检查语句来尝试找到第 二个缺陷语句 因此 NOH-MFL 方式会尝试将多 个缺陷语句都排在语句有序列表的前列, 使得开 发人员在单次迭代中能快速找到多个缺陷语句 以图 8 所示的 INF-MFL 方法怀疑度值为例, 当使 用 NOH-MFL 方法进行缺陷定位时, 开发人员定 位到第一个缺陷语句仍然需要检查 5 行语句 但 当修复完该缺陷语句后, 开发人员会按照怀疑度 值继续检查程序语句, 直至找到第二个程序缺陷 因此针对图 8 所示的示例程序, 采用 NOH-MFL 方法进行缺陷定位至多需要检查 7 行语句 3 基于缺陷干扰假设的多缺陷定位方 法 基于缺陷干扰假设的多缺陷定位的 INF-MFL 方法是目前多缺陷定位领域中研究最多的一类方 法, 具有实现简单的特点 从发表年份分析, 在 我们收集的 53 篇与 INF-MFL 方法相关的研究工 作中,2019 年发表的数量最多 ( 为 14 篇 ),2016 年和 2017 年次之 ( 分别为 11 篇和 8 篇 ) 需要注意 的是, 搜集的部分论文的方法并没有针对多缺陷 定位问题提出定制算法, 而仅考虑了含有多个缺 陷的评测对象 但这些实证研究对 MFL 问题的后 续研究仍有指导和参考价值, 因此该综述也考虑 了这些论文 由于 INF-MFL 方法一次只定位一个缺陷, 假 设一个程序包含两个缺陷, 那么使用 INF-MFL 方 法定位这些缺陷则总共需要执行两次调试 具体 来说, 在第一次调试过程中,INF-MFL 方法将尝 试定位其中一个缺陷, 随后开发者将其修复 ; 修 复完第一个缺陷后,INF-MFL 方法将对修复完第 一个缺陷后的程序重新执行测试用例并收集缺陷 定位所需要的信息, 并尝试定位第二个缺陷 不 难看出,INF-MFL 方法需要在每次缺陷定位结束 后, 由开发者对程序进行缺陷修复并重新执行测 试用例, 直到找到并修复被测程序包含的所有缺 陷 研究人员尝试将 INF-MFL 方法与多种经典的 缺陷定位技术结合使用, 如 : 基于程序频谱的方 法 (Spectrum-BasedFaultLocalization, 简称 SBFL) [7,21,25,26,27] 基于统计的方法和基于机器学习的方法 等 3.1 INF-MFL 方法的提出与改进 基于优化模型的方法 基于优化模型的方法通常将多缺陷定位问题 转换为优化模型的求解问题, 研究人员通过提取 程序中某种粒度 ( 粒度可以设置为程序组件 程序 类 函数 语句 变量等 ) 的特征, 并使用该特性 构造多种不同的优化问题模型, 从而在测试数据 中对相同粒度的程序缺陷进行识别 在近些年的研究中, 有研究人员将缺陷定位 抽象为一个数据挖掘问题, 并尝试使用约束规划 模型求解该问题 这种方法可以提取满足对最可 疑语句建模的一组约束的数个最佳匹配模式, 该 匹配结果可以为程序中的缺陷 ( 如失败的测试用 例 包含缺陷的程序语句 ), 或者为需要排除的无 关因素 ( 如通过的测试用例 正确的程序语句 ) 当匹配结果是以程序中的缺陷为目标, 则相 应算法需要以尽可能高的效率定位到程序中缺陷 的位置并报告给软件开发人员 例如,Dean 等人 [28] 利用线性规划模型, 将多缺陷定位问题转化为 查找最小覆盖所有失败测试用例的语句集合问 题, 他们从 Tarantula 公式的定义出发, 分析认为 被更多失败测试用例覆盖且被更少通过测试用例 覆盖的语句集合有更大的可能性成为缺陷语句, 并将这些语句集合作为目标, 构建约束条件并进 行求解 他们在包含 2 到 4 个缺陷的被测程序上 展开了实证研究, 结果表明这种方法在定位多个 缺陷时, 比 AMPLE [24] 和 Tarantula 等方法有更好 的缺陷定位效果 2011 年,Artho 基于 Zeller 等人 的工作 [29], 提出了针对多缺陷程序的缺陷定位方 法 IDD(IterativeDeltaDebugging) [30] 该方法首 先使用失败的测试用例执行程序的历史版本, 从 而找到使得这些测试用例通过的程序版本, 之后 通过提取当前版本和历史版本之间的差异进行缺 陷定位 当程序中存在多个缺陷, 且缺陷互相干 扰使得测试用例在引入某一缺陷之前的程序版本 中依然无法执行通过时, 该方法将会迭代式向更 为历史的版本进行追溯, 直至所有的程序缺陷都 [31] 能被定位 Birch 等人提出了一种基于符号执行 的多缺陷定位方法, 可自动定位到程序的可修复 片段 这种方法提升了测试用例的搜索速度, 减 少了模型中符号执行的开销 在多缺陷程序上的 实验结果表明, 使用该方法可以有效缩小可疑缺 陷位置的搜索范围, 具有较好的缺陷定位效果 [32] 2019 年,Ma 等人提出了一种向量表模型 VTM

9 李征等 : 软件多缺陷定位方法研究综述 9 (VectorTableModel), 用于系统分析和比较不同 的 SBFL 公式 基于该模型, 他们实现了一个统 一的系统调查框架, 以同时考虑单缺陷程序和多 缺陷程序 通过定义不同类型的缺陷并基于 VTM 研究缺陷类型的数学表达, 可以系统地分析和比 较不同缺陷定位技术的有效性 他们的实验结果 表明, 在单缺陷情况下, 怀疑度计算公式 Ochiai 的性能要优于 Dstar, 而在多缺陷情况下,Ochiai [33] 的稳定性要优于 Dstar Liu 等人提出了一种基 于 Simulink 模型的多缺陷定位方法 该方法可以 对测试用例进行聚类, 以帮助识别 Simulink 模型 中的多个缺陷, 然后根据每个类簇内的测试用例 计算怀疑度, 进而生成相应的语句怀疑度排序列 表, 最后根据他们提出的评估准则选出具有最佳 缺陷定位效果的排序列表用于缺陷定位 尽管这 种方法对失败测试用例进行聚类, 但其仍然属于 INF-MFL 方法, 即每次迭代仅定位单个缺陷并立 即进行修复 当匹配结果是以无关因素为目标, 则该技术 需要尽可能剔除缺陷定位过程中的无关或干扰因 素, 以提高开发人员定位缺陷的效率 例如 Wang [34] 等人发现, 对被测程序使用 SBFL 技术生成的 语句怀疑度表中, 存在一些排名较高的语句为正 确语句, 并导致缺陷定位精度不高 为了进一步 提高 SBFL 技术的有效性, 他们依据软件缺陷传 播模型 RIP(Reachability,Infection,Propagation) 来识别那些在怀疑度列表中排名较高的正确语 句, 并通过排除这些语句来提高缺陷语句的排名 他们基于 Siemens 数据集进行了实证研究, 实验 结果表明他们所提的方法可以有效提升 SBFL 技 术在多缺陷程序上的缺陷定位性能 尽管研究人员提出了多种基于优化模型的方 法, 但是该方法在处理大规模程序时, 因为方法 本身的算法复杂度较高, 因此会存在时间开销大 [35] 的问题 为了解决这个问题,Aribi 等人利用全 局约束和基于模式的怀疑度计算公式, 提出了一 种新的关联多缺陷上下文的约束规划模型, 来挖 掘怀疑度最高的数个语句, 可以有效缓解因缺陷 之间的复杂依赖关系所引起的问题 实验结果表 明, 与 Tarantula Ochiai 和 Jaccard 等传统缺陷定 位方法相比, 该方法在多缺陷定位时的性能有显 [36] 著提升 此外, 他们还提出了一种基于多标准 层次分析 (AnalyticHierarchyProcess, 简称 AHP) 的方法 AHP 方法将缺陷定位问题建模为多准则 决策问题 (Multi-CriteriaDecisionMakingProblem), 并利用加权线性公式将不同度量指标整合成单一 度量指标, 来作为程序语句怀疑度的排序依据 他们在包含 2 个和 4 个缺陷的程序上进行了实证 研究, 发现 AHP 方法比常见的 SBFL 方法 ( 如 Tarantula,Ochiai 等 ) 有着更高的缺陷定位精度 [37] 最近 Peng 等人提出的一种基于自动编码 的缺陷定位方法 ABFL(Auto-encoderBasedFaultLocalization) 该方 法包括四个步骤, 分别是编码器训练 特征提取 排名模型的训练和语句有序列表的生成 首先标 记所有程序语句以训练编码器, 训练完成的编码 器可以为每个语句编码成一个固定长度的特征表 示 然后, 将所有提取的特征表示输入到排序学 习 (LearningtoRank) 算法, 以训练排名模型 最后, ABFL 基于排名模型生成语句怀疑度序列表 在 Defects4J 数据集上的实验结果表明,ABFL 方法 在多缺陷上的定位效果要优于最新的 14 种 SBFL 方法 ( 例如 :DStar GP13 GP19 等 ) 基于程序切片的方法 基于程序切片的方法一般通过分析程序信 息, 缩小缺陷定位的语句搜索范围, 以提高缺陷 定位效果 近些年来, 研究人员提出了多种结合 程序切片分析的 MFL 方法, 改进了多缺陷定位精 度 程序切片可简单分为静态切片和动态切片两 类, 动态切片通过分析测试用例的覆盖信息和执 行结果等获得切片内容, 而静态切片仅通过分析 程序源代码获得切片内容 静态切片是软件工程中常用的程序分析方 法, 但是静态切片通常会返回范围较大的程序集 合, 难以精确定位到缺陷所在位置 为了解决上 [38] 述问题,Zhang 等人提出了一种基于静态程序 切片的方法 PRIOSLICE, 该方法建立程序中数据 依赖的概率模型, 为切片中的每一个语句计算范 围为 [0,1] 的权重, 用以表示该语句属于切片的可 能性, 最后依照权重对静态切片内的语句进行优 先级排序, 这种排序结果能提高静态切片的准确 度, 从而达到提高缺陷定位效果的目的 实验结 果表明 PRIOSLICE 方法比现有的静态切片方法 能更有效提升多缺陷定位效果 与静态切片相比, 动态切片执行过程更为复 杂且耗时, 但是其切片范围更小且更精准, 文万 [39] 志等人通过 codecover 工具收集测试用例的语 句或语句块覆盖信息, 提出了一种基于条件执行

10 10 计算机学报 切片谱 (ConditionedExecutionSlicingSpectrum) 的 多缺陷定位技术 该技术主要分为 4 步 :1. 计算 缺陷相关条件执行切片, 缩小缺陷搜索范围 ;2. 构造条件执行切片谱矩阵 ;3. 根据条件执行切片 谱, 计算缺陷相关条件执行切片内每个元素的怀 疑度 ;4. 根据怀疑度大小依次定位程序中的缺陷, 并生成怀疑度报告 在 3 个面向对象程序 (Tetris SimpleJavaApp 和 JHSA) 上的实验结果表明该技 术比基于程序谱的 Tarantula 技术 基于程序切片 的 Intersection 技术和 Union 技术等具有更高的多 缺陷定位精度 将 SBFL 技术与其他技术结合, 可以保留两 种技术的优势, 因此这通常被视为一种可行的改 [40] 进缺陷定位效果的方法 现有研究表明, 将 SBFL 与切片命中集计算 (SlicingHittingSetComputation) 技术相结合的 Sendys 方法具有较好的缺陷定位效果 更进一步, [41] Tu 等人从理论层面对 Ochiai 公式与切片命中集 计算结合的定位方法 Sendys 方法进行了分析, 并 提出 Sendys 方法的多个改进版本, 该方法具有严 格的理论支撑, 同时在多缺陷定位上具有更好的 [42] 定位效果 Parsa 等人从缺陷代码与失败测试用 例输出的依赖关系角度出发, 提出了一种结合 INF-MFL 调试方法和程序切片技术的方法 Stat-Slice 该方法能够查找到更多类型的缺陷, 如代码遗漏缺陷 头文件缺陷 ( 如头文件中包含缺 陷的宏命令 ) 等 在 grep 和 gzip 程序上的实验结 果表明,Stat-Slice 方法能有效减少缺陷定位的开 销, 并在定位两个缺陷和三个缺陷时有更好的定 位效果 基于怀疑度计算公式改进的方法 SBFL 和基于变异的缺陷定位 (Mutation-BasedFaultLocalization, MBFL) 技术因 其较好的缺陷定位效果, 近年来被研究人员广泛 运用 SBFL 和 MBFL 技术的核心是怀疑度值计 算公式, 然而传统的怀疑度计算公式 (Tarantula Ochiai Jaccard 等 ) 并未针对多缺陷问题进行优化 因此, 基于 SBFL 和 MBFL 怀疑度计算公式改进 的方法通常通过改进现有的怀疑度计算公式, 或 提出新的怀疑度计算公式, 从而提高缺陷定位效 果 针对上述问题, 一部分研究人员尝试通过加 权 组合等方法, 对传统的怀疑度计算公式进行 改进 例如,Abreu 等人在传统的测试用例覆盖 频谱信息 ( 仅记录程序语句是否被测试用例执行 ) 的基础上, 进一步考虑了程序语句的执行次数信 息 [43], 并提出了 Zoltar-C 方法 该方法同时考虑 到程序语句的执行覆盖频谱以及程序语句被执行 的次数, 并综合利用这些信息来改进贝叶斯方法, 最终计算出程序语句的出错概率 他们通过理论 分析验证了 Zoltar-C 方法能够提高多缺陷定位效 果 但实证研究的结果表明 Zoltar-C 方法在多缺 [44] 陷定位精度上提升效果有限 Lee 等人基于实 证研究发现覆盖多缺陷的测试用例所执行的语句 比仅覆盖单个缺陷的测试用例所执行的语句有更 高的怀疑度 因此, 他们提出一种加权的测试用 例分类方法来提升多缺陷定位精度 实验结果表 明, 这种加权方法能够有效提高多缺陷定位的精 [45] 度 Zhang 等人提出一种轻量的缺陷定位技术 PRFL, 该方法通过使用 PageRank 算法来增强现 有的 SBFL 技术 具体而言,PRFL 根据每个测试 用例的贡献程度, 使用 PageRank 算法对原始程序 的覆盖信息进行加权 然后使用传统的 SBFL 技 术重新计算语句的怀疑度值, 以实现更有效的缺 陷定位 在 Defects4J 程序集和 87 个 GitHub 项目 的多缺陷版本上的实验结果表明,PRFL 的缺陷定 位效果要显著优于传统的 SBFL 技术 (Tarantula [46] Ochiai 等 ) Zou 等人针对来自 Defects4J 评测程 序集的真实程序缺陷, 系统比较了不同缺陷定位 方法 ( 基于频谱的方法, 基于变异的方法, 基于切 片的方法等 ) 的多缺陷定位效果 在 Defects4J 上 的实验结果表明,SBFL 的独立定位效果是最好 的, 并优于 MBFL 同时他们提出一种组合定位 方法, 结果表明该组合方法要明显优于任何单独 的方法 除了改进已有的计算公式, 也有一部分研究 人员尝试通过构造更加丰富的程序特征信息 设 计出一些全新的怀疑度计算公式 例如,Wong [25] [47] 等人对 Kulczynski 相关系数进行研究, 在此 基础上提出了一种全新的语句怀疑度值的计算方 法 Dstar 实验结果表明, 与其他 38 种缺陷定位 公式相比,Dstar 在单缺陷程序和多缺陷程序上都 能有更好的缺陷定位效果 通过对比覆盖多缺陷 的失败测试用例与覆盖单缺陷的失败测试用例, Naish 等人 [48,49] 基于遗传编程 (GeneticProgramming), 提出一种新的怀疑度计算 方法, 即双曲度量 (HyperbolicMetric) 这种度量 方法考虑到程序多缺陷位置的不确定性, 通过机

11 李征等 : 软件多缺陷定位方法研究综述 11 器学习从训练数据中获取度量多缺陷的最优参 数 在 Siemens 和 Unix 数据集上的实验结果表明, 与 Ochiai Tarantula 和 GP13 等常用的怀疑度计算 方法相比, 他们提出的双曲度量方法在多缺陷程 序上有更好的定位效果 [50] 同时,Laghari 等人改进了传统的 SBFL 方 法, 提出了一种基于模式化频谱 (PatternedSpectrum) 的缺陷定位方法 与传统的 SBFL 方法主要使用测试用例的频谱信息不同, 基 于模式化频谱的缺陷定位方法通过记录程序中的 函数调用关系和次数来构造出一种新的程序频 谱 实验结果表明该方法比传统 SBFL 方法有更 好的多缺陷定位效果 [51] 除此之外,Li 等人提出一种迭代用户驱动 (IterativeUser-Driven) 的半自动缺陷定位方法 Swift 该方法基于函数粒度, 借助统计缺陷定位 方法来识别出可疑程序函数, 然后对这些函数的 正确性生成相应的查询, 最后结合开发人员的反 馈信息来改进缺陷定位结果 实证评估结果显示 Swift 在多缺陷程序调试上对开发者能产生一定 程度的帮助, 可以减少查找缺陷所需的时间开销 并提高调试效率 基于测试套件改进的方法 在缺陷定位的过程中, 除了人工检查被测程 序以外, 执行测试套件内的测试用例也会产生巨 大的时间开销, 因此提高测试用例的执行效率也 可以有效提高缺陷定位的效率 基于测试套件改 进的方法就是指通过改进测试套件内测试用例生 成 选择 执行顺序等过程, 或改进测试用例的 覆盖频谱信息, 从而提高多缺陷定位的效果和效 率 根据方法的不同, 基于测试套件改进的方法 可以分别对测试用例执行的三个阶段进行优化 ( 执行前 执行中和执行后 ) 在执行测试用例前, 开发人员可以对测试用例进行选取以及通过组合 测试的方法来减少测试用例生成的数量, 从而控 制测试用例的执行流程和效率 ; 在执行测试用例 中, 开发人员可以对测试用例的进行排序, 或者 调整测试用例的覆盖路径来提高执行效率 ; 在执 行测试用例后, 开发人员通过降低测试预言和偶 然正确用例对缺陷定位的负面影响来提高缺陷的 定位效果 测试用例的选取是指人为判断测试套件内各 个测试用例是否被保留, 通常开发人员会保留或 复制对缺陷定位有价值的测试用例, 并删除冗余 的测试用例, 从而实现提高缺陷定位效率且不降 低缺陷定位精度 例如, 为了优化测试套件内测 [52] 试用例之间的关系,Gong 等人将通过测试用例 的数量与失败测试用例的数量之比称为测试套件 的平衡率, 其中平衡率为 1 的测试套件被称为平 衡测试套件 他们证明了测试套件的平衡率越接 近 1, 则 SBFL 技术的缺陷定位效果越好 但在实 际的缺陷定位中, 失败测试用例的数量通常要低 于通过测试用例的数量 因此, 针对缺陷定位中 [53] 的测试用例不平衡问题,Zhang 等人调查针对 类不平衡问题 ( 即失败测试用例数量远小于通过 测试用例的数量 ), 研究简单复制失败测试用例, 从而扩充失败测试用例数量对 SBFL 方法定位精 度的影响 他们的研究表明对失败测试用例的复 制, 能有效提升多缺陷定位效果 除此之外, 与 常用的 SBFL 技术相比,MBFL 技术的时间开销 更大,MBFL 通过变异的方法植入人工缺陷来模 拟真实的程序缺陷, 并通过计算两者之间的相似 度来进行缺陷定位,MBFL 是一种精度较高的缺 陷定位技术 然而该技术需要对语句进行变异操 作产生大量的变异体, 同时对每个变异体执行所 有的测试用例, 其时间开销极大, 因此很少被工 [54] 业界采用 针对这个问题,Oliveira 等人通过对 变异体只执行失败测试用例而忽略通过测试用 例, 来减少变异执行开销 基于 Defects4J 上的实 验结果表明, 这种执行策略可以减少约 90% 的执 行开销, 且多缺陷定位精度降低并不显著 组合测试 (CombinatorialTesting) 通过关注部 分参数间的组合覆盖, 来减少需要生成的测试用 例, 使用部分测试用例对不同的程序模块进行调 试, 可以有效缩减需要执行的测试用例数量 [55] Ghandehari 等人利用组合测试思想提出了一种 缺陷定位方法 BEN 组合测试用例中不同模块有 不同的测试用例集合,BEN 方法首先确定可能执 行缺陷的测试用例组合, 然后根据执行缺陷语句 数量对测试用例集合进行排序, 最后从测试用例 集合的排序结果中选择排名靠前的测试用例集合 用于缺陷定位 该方法在单缺陷程序和多缺陷程 序上均进行了性能评估 与 Tarantula 和 Ochiai 方 法相比,BEN 能有效地定位到缺陷所在位置 除 此之外, 研究人员已证明组合测试可以有效地揭 示由影响系统行为的因素之间的相互作用所引起 的缺陷, 从而提出了最小失效原因架构 MFS (MinimalFailure-CausingSchema) 理论以隔离缺

12 12 计算机学报 陷原因 [56] 但是大多数旨在识别 MFS 的算法都集 中于处理被测程序中的单个缺陷, 因此这些方法 可能被多缺陷程序中的缺陷混淆情况所影响, 从 [57] 而无法观察到某些缺陷 为此,Niu 等人提出 了一种新的 MFS 模型, 该模型考虑了多缺陷的情 况, 会分别处理被测程序中的每个缺陷 具体而 言, 针对某一个程序缺陷, 该模型仅会关注在该 缺陷中通过或失败的测试用例 触发其他不同缺 陷的测试用例将被新生成的测试用例替换 因此, 该方法可以在不受缺陷混淆干扰的情况下正常工 作 在执行测试用例的过程中, 开发人员可以对 测试用例进行排序, 或者调整测试用例的覆盖路 径, 及组合测试中的模块组合, 从而提高后续工 作的效率 开发人员对测试套件内的测试用例进 行排序, 会优先执行对缺陷定位有价值的测试用 例, 并延后执行其余测试用例 例如, 为降低 [58] INF-MFL 调试成本,Fu 等人从测试用例角度, 基于程序元素怀疑度值的变化, 提出了一种测试 用例优先级排序方法 实验结果表明该方法可以 有效减少调试的成本 开发人员通过调整测试用 例的覆盖路径或者组合测试中的模块组合来提升 [59] 执行效率 例如,Perez 等人提出一种动态代码 覆盖的方法 DCC(DynamicCodeCoverage), 该方法 会动态改变测试套件对被测程序的覆盖频谱, 旨 在减少缺陷定位过程中的执行开销 DCC 方法首 先分析测试用例针对被测程序中系统组件 ( 子程 序 ) 的覆盖路径, 然后从文件粒度开始进行逐步细 化, 直至达到语句级别 实验结果表明, 相比 SBFL 方法,DCC 能够平均降低 27% 的多缺陷定位开销 [60] Yu 等人在 2015 年提出一种分类方法, 可以区 分失败测试用例与单缺陷有关还是与多缺陷有 关 他们的实验结果验证了上述分类方法的有效 性, 从测试用例角度为提升多缺陷定位效果提供 了新的研究思路 除此之外, 开发人员可以在程 序测试过程中, 根据程序的状态生成新的测试用 例, 从而实现更高精度的缺陷定位 例如,Yilmaz [61] 等人为了解决缺陷混淆问题, 提出了一种反馈 驱动的自适应组合交互测试过程 FDA-CIT ( FeedbackDrivenAdaptiveCombinatorialInteractio ntestingprocess) 在此过程的每次迭代中, 他们 首先执行测试用例并分析结果, 通过计算缺陷特 征模型 ( 即通过识别可能的缺陷相互作用 ) 来检 测潜在的缺陷混淆情况, 然后生成可避免该缺陷 混淆情况的新的测试用例, 从而减轻缺陷混淆对 缺陷定位产生的负面影响 基于两个大型开源软 件系统 (Apache 和 MySQL) 的实验结果表明, 他们提出的 FDA-CIT 方法能够有效减轻缺陷混淆 的影响, 从而提高缺陷定位精度 在测试用例执行结束之后, 开发人员需要根 据测试预言 (TestOracle) 判断测试用例的执行结 果, 测试预言通常是指某个测试用例的预期输出, 通过对比测试用例的实际输出和预期输出, 可以 判断测试用例是否执行通过 尽管大多数缺陷定 位技术仅使用少量测试用例也可以相对准确地定 位缺陷, 但是选择合适的测试用例并为其创建测 试预言费时费力 因为创建测试预言需要花费大 [62] 量的人工成本 为了解决上述挑战,Xia 等人 提出了一种多样性最大化加速的方法 DMS(DiversityMaximizationSpeedup) DMS 方法 试图仅优选少量高质量测试用例进行缺陷定位, 开发人员只需要人工给选出的少量测试用例创建 测试预言, 即可通过缺陷定位技术取得较好的缺 陷定位结果 其中可行的优选方法包括 : 选择执 行更多程序语句的测试用例 选择执行了当前已 选的测试用例未执行语句的测试用例 选择覆盖 路径相似度较低的测试用例 实验结果表明,DMS 方法能有效约减测试用例的数量, 加速多缺陷定 位过程, 并同时保证了缺陷定位的精度 而 Gao [63] 等人提出了一种基于汉明距离和 K-Means 聚类 的方法来预测测试用例的执行结果 该方法根据 未标记测试用例与失败测试用例之间的距离来判 断其标签 ( 通过或失败 ), 当未标记测试用例与失败 测试用例的汉明距离小于某一阈值或与失败测试 用例划分至同一类簇时, 则判定该未标记测试用 例为失败, 否则为通过 基于 Unix 程序集的实验 结果表明使用预测结果的定位效果与原始执行结 果的定位效果同样有效, 有些甚至定位性能更好 [64] Zhang 等人使用了 INF-MFL 调试方法, 提出了 一种测试用例分类方法, 以帮助在定位缺陷时使 用未标记的测试用例 他们提出一种基于测试分 类的方法来利用未标记的测试用例 该分类器称 为基于可疑概率 ( SuspiciousnessProbability-based) 的分类器, 它利用 SBFL 领域知识 (DomainKnowledge) 为每个未标记的测试用例分 配一个估计的标签 ( 通过或失败 ) 分类后, 新标记 的测试用例将被用于语句怀疑度值的计算 基于 多缺陷程序的实证研究表明, 该方法有助于提高

13 李征等 : 软件多缺陷定位方法研究综述 13 缺陷定位的效果 需要注意的是, 在缺陷定位过程中, 存在一 类通过的测试用例, 这些通过的测试用例执行了 包含缺陷的语句, 但是执行结果与预期一致, 这 一类测试用例被称为偶然正确的测试用例 (CoincidentalCorrectTestCases), 当前大量研究表 明偶然正确测试用例对缺陷定位效果有负面影响 [65] 针对上述问题,Liu 等人 [66], 提出了一种加 权模糊分类的方法 FW-KNN(FuzzyWeightedK-NearestNeighbor), 来 识别并处理偶然正确的测试用例 该方法基于模 糊 KNN 分类算法, 其将失败的测试用例作为训练 数据, 通过的测试用例作为测试数据进行判断 与失败测试用例相似度较高的通过测试用例将会 被判定为偶然正确的测试用例 在单缺陷和多缺 陷程序的实验结果表明, 与传统的 Jaccard Ochiai 和 Dstar 等 SBFL 缺陷定位方法相比, 应用 FW-KNN 方法能有效提升缺陷定位效果 基于程序语义分析的方法 基于程序语义分析的方法通常通过分析程序 内部或程序与程序之间的相关性 ( 如变量相关性 谓词相关性 抽象语法树相关性 控制流图相关 性等 ) 进行缺陷定位 基于变量相关性的方法通常 会分析程序中变量之间的关系, 然后根据变量之 间的依赖关系计算语句怀疑度 考虑到程序中变 [67] 量的变化,Kim 等人提出一种基于变量的缺陷 定位方法 VFL(Variable-basedFaultLocalization), 用于解决 SBFL 方法在测试用例覆盖信息相近时 定位效果差的问题 VFL 通过识别程序中的可疑 变量, 来指导程序语句的排名 基于 Defects4J 程 序集的实验结果 VFL 的定位效果较好, 且具有轻 量级和可扩展的优点, 并可以与其他方法进行结 [26] 合以进一步提升缺陷定位效果 Wong 等人提出 一种基于交叉表的统计方法 CBT(Crosstab-BasedTechnique) 该方法首先对每 条执行语句构建交叉表, 然后使用统计方法来确 定对应语句的怀疑度 但实验结果表明 CBT 方法 在多缺陷定位上的效果提升并不明显, 同时他们 发现 CBT 方法的定位效果容易受到测试套件规模 [68] 的影响 Dandan 等人在分析程序控制流图 (ControlFlowGraph) 间的状态相关性信息的基础 上, 研究使用状态依赖概率模型来描述程序语句 之间的控制依赖关系, 随后提出一种基于通过和 失败测试用例状态依赖的缺陷定位方法 基于 Siemens 和 Unix 程序集中的多缺陷版本的结果表 明, 他们提出的方法与 SOBER [69] Tarantula 和 CP [70] 等缺陷定位方法相比, 在少量测试用例的场 景下, 能取得更好的缺陷定位效果 [71] Feyzi 等人基于信息理论分析和统计因果 推理, 提出了一种缺陷定位方法 Inforence 该方 法采用基于互信息的特征选择策略, 通过计算语 句间的依赖关系来确定导致程序失败的语句组 合 实验结果表明,Inforence 在多缺陷定位效果 上要优于 DStar 和 GP19 等缺陷定位方法 [72] Wang 等人提出了一种基于动态不变量 (DynamicInvariant) 差异的方法 FDDI 动态不变量 指的是变量之间的关系 具体来说, 程序在执行 过程中, 存在部分变量的值在变化过程中有一定 的相关性 因此研究人员认为, 相关性被破坏的 动态不变量可以为缺陷定位提供线索 当前已经 存在通过分析动态不变量来检测程序异常的技 术, 但是这些技术通常会产生较大的时间开销 为了解决上述问题,FDDI 方法首先选择怀疑度较 高的函数, 然后检测这些函数中存在的动态不变 量 随后,FDDI 方法会剔除存在于通过测试用例 和失败测试用例之间的动态不变量, 从而降低时 间复杂度 最后, 他们使用所有测试用例, 并基 于 INF-MFL 调试模式进行缺陷定位 实验结果表 明,FDDI 方法不仅能够提高缺陷定位效果, 而且 可以平均减少算法 87.2 % 以上的执行时间 基于程序谓词分析的缺陷定位方法也受到了 研究人员的关注 程序中的谓词 (Predicate) 是一种 返回值为布尔类型的函数, 通常用于控制 for if while 等语句块 研究人员提出的方法一般通过对 单个谓词的切换, 从而强制更改谓词实例的状态 ( 返回结果从 true 更改为 false, 或从 false 更改为 true), 然后通过检查谓词状态切换能够改变测试 用例的执行结果, 从而来确定缺陷是否包含于该 谓词中 但是, 切换一个谓词实例有其局限性, [73] 在 Wang 等人的实验中, 他们发现单个谓词切 换只能识别少数关键谓词 要克服这个局限性, 可能需要切换多个谓词实例 但是若考虑所有的 谓词实例组合, 则可能存在指数爆炸问题 因此, [73] Wang 等人提出一种基于分层的多谓词切换方 法 HMPS HMPS 方法仅在怀疑度较高的语句内 搜索可能包含缺陷的谓词 实验结果表明 HMPS 方法的多缺陷定位效果要优于部分已有的缺陷定 位方法 ( 例如 Barinel,Ochiai)

14 14 计算机学报 基于谓词的统计缺陷定位方法以谓词作为研 究对象, 度量谓词与程序缺陷间的关联程度, 关 联程度越高, 谓词的怀疑度值越高 但是, 高关 联度的谓词并不意味着它是程序执行失败的原 因 软件缺陷定位过程是寻找引发程序失效的原 因的过程, 可理解为针对程序执行失效这一现象, 来寻找引发缺陷的原因的因果推理过程 在因果 推理过程中, 在分析处理变量与输出变量之间的 因果关系时, 需要考虑其他变量的影响, 否则推 理过程会受到混杂偏倚效应 (ConfoundingEffect) 的影响, 并导致推理结果不准确 针对上述问题, [74] 王兴亚等人对谓词怀疑度度量过程中的混杂偏 倚效应的消除进行了研究, 在此基础上提出了 PBSFL(Predicate-basedStatisticalFaultLocalization) 方法 该方法包括 5 个步骤, 分别是程序静态切 片, 缺陷候选谓词筛选, 混杂偏倚元素识别, 监 控执行与动态约减, 回归分析及排序 具体来说 : 首先对源程序执行静态切片, 将影响输出变量的 语句集合作为可疑语句集合, 然后根据程序中变 量的类型对其进行缺陷候选谓词筛选, 生成可疑 谓词集合, 对其中的每一个元素通过程序依赖分 析构建因果图, 并推理识别混杂偏倚元素, 最后 通过监控记录可疑谓词取值结果 混杂偏倚元素 信息进行回归分析, 度量谓词导致失败的贡献来 进行排序, 生成谓词序列来帮助缺陷定位 基于 Siemens 程序集的多缺陷版本的实验结果表明 : PBSFL 可以有效提高传统缺陷定位方法 (Tarantula Ochiai Naish1 等 ) 的效果 [75] Liu 等人提出了一种称为多谓词切换的有 界调试 (BoundeddebuggingviaMultiplePredicateSwitching, 简称 BMPS) 方法, 该方法试图通过切换谓词状态 来使测试用例通过, 从而定位存在于谓词中的程 序缺陷 BMPS 专注于由控制流引起的程序缺陷 [76] 他们在后续的工作中认为这种类型缺陷仅占很 小的比例 因此, 他们进一步提出了一种将 BMPS 与基于语义的调试方法 (SemanticbasedDebuggingMethod) 相结合的方法来 定位更多类型的缺陷 基于语义的调试算法从失 败的测试用例的覆盖信息中生成一系列方程, 并 根据方程的解为开发人员提供包含缺陷代码的最 小程序段 通过迭代和交互的过程, 他们的方法 以 INF-MFL 调试方法定位程序中多个缺陷 基于 Siemens 程序集的实验结果表明 : 他们的方法的定 位效果要显著优于 BMPS 方法 除此之外, 基于程序语义分析的方法还能够 通过提取程序执行过程中的特征, 分析与缺陷相 关的语句或测试用例, 从而提高 SBFL 等缺陷定 位技术的效率 在软件测试过程中, 动态分析是 指根据程序的运行过程产生的信息对程序进行分 析,SBFL 就是一种动态分析方法 静态分析是指 根据程序非运行时获得的信息对程序进行分析, 其可行的实现方式包括提取抽象语法树 控制流 [77] 图等 Neelofar 等人同时考虑了动态分析方法 和静态分析方法, 提出一种结合动静态分析的加 权方法来辅助缺陷定位 其中静态分析方法根据 语句的怀疑度分配不同的权重后, 对这些语句进 行分类, 动态分析则将计算语句加权之后的分数 作为新的怀疑度, 并生成 INF-MFL 调试中使用的 语句有序列表 实验结果表明, 该方法能将单缺 陷程序和多缺陷程序上的定位效果分别提升 20% [78] 和 42% Xu 等人将未执行某个缺陷语句而失败 的测试用例称为噪声测试用例, 噪声测试用例的 存在会导致已有方法在定位该缺陷语句时效率降 低 因此, 他们提出一种可减少这类噪声测试用 例的方法框架 [79], 该框架通过分析代码块之间的 关系, 构建程序基本块之间的关系链, 来改进 Jaccard Anderberg 和 Dice 等怀疑度计算公式, 从而降低噪声测试用例的影响 实验结果表明, 他们提出的多缺陷定位方法与 SBFL 技术相比, [80] 其定位精度至少能提高 10% Li 等人将深度学 习 (DeepLearning) 引入到缺陷定位, 提出 DeepFL 定位方法 DeepFL 通过抽取多缺陷程序的四类特 征来构建怀疑度预测模型, 这四类特征分别为 : SBFL 技术计算的语句怀疑度,MBFL 技术计算的 语句怀疑度, 用于缺陷预测的程序复杂度指标, 基于信息检索的文本相似度信息 实验结果表明 : DeepFL 的多缺陷定位效果要明显优于最新的 TraPT 和 FLUCCS 缺陷定位技术 表 3INF-MFL 方法相关论文统计结果 分类论文数量 基于优化模型的方法 [28,30,31,32,33,34,35,36,37,81] 基于切片的方法 [38,39,41,42] 4 基于怀疑度计算公式 改进的方法 基于测试套件进行改 进的方法 [25,43,44,45,46,48,49,50,51] [53,54,55,57,58,59,60,61,62,63,64,66]

15 李征等 : 软件多缺陷定位方法研究综述 15 基于程序语义分析的 方法 [26,67,68,71,72,73,74,76,77,79,80,82] 最后我们针对已有的 INF-MFL 方法进行分 类统计, 最终统计结果如表 3 所示 从表中可以 看出, 大部分的研究工作都旨在提高单缺陷定位 的准确度 因为基于 INF-MFL 调试方法的多缺陷 定位技术在每次迭代中仅会定位单个缺陷, 这意 味着每次迭代都被视为单缺陷定位, 所以提高单 缺陷定位准确度就是提高每次迭代定位的准确 度, 从而提高基于多缺陷定位流程整体的效果 除此之外, 还有一些研究工作试图降低缺陷定位 的成本, 即减少缺陷定位算法执行过程中的时间 消耗 3.2 针对 INF-MFL 方法的实证研究 INF-MFL 调试方法是 MFL 领域中研究最多 的一类方法, 因此也有大量研究人员对该调试方 法展开实证研究 本节对基于 INF-MFL 调试方法 的 MFL 相关研究论文进行了概述, 其中部分论文 研究了多缺陷的存在对缺陷定位技术有效性的影 响 在多缺陷定位研究当中, 多缺陷的存在对现 有缺陷定位技术的影响方式备受研究人员关注 [9] 例如,Nicholas 等人进行了缺陷数量对 SBFL 技 术影响的实证研究 传统的多缺陷定位研究认为, 缺陷定位技术的有效性与缺陷数量成反比 为了 验证该推测, 他们对来自 Unix 程序集的三个程序 (Gzip Space Replace) 进行了研究, 这些程序的 大小各不相同, 涉及超过 13,000 个多缺陷版本 他们的研究结果表明 : 多缺陷的存在对 SBFL 技 术的影响不如预期的那样大, 对基于 INF-MFL 调 [83] 试方法的 SBFL 技术影响可忽略不计 Sun 等人 分析了部分缺陷定位公式 (SymmetricKlosgen [84] Ochiai Jaccard 等 ) 的共性, 以分析某些定位公式 比其他公式更有效的原因 基于多缺陷程序的实 验结果表明 : 相较于其他缺陷定位方法, SymmetricKlosgen relativeochiai relativef1 和 enhancedtarantula 更适用于多缺陷定位问题 Yan 等人从缺陷数量对 SBFL 定位效果的影响进行了 实证研究 [85], 研究结果表明 : 多缺陷的存在对缺 [3] 陷定位效果普遍存在负面影响 Xie 等人为了克 服传统实证研究经验化的局限性, 提出了针对怀 疑度计算公式的理论研究框架 该框架基于简单 的直觉来识别不同公式之间的关系, 直觉认为怀 疑度值高于缺陷语句的正确语句数量决定了缺陷 12 语句的排名 因此该框架将所有程序语句划分为 三个不相交的集合, 分别为怀疑度值高于 等于 和低于缺陷语句 通过比较不同怀疑度计算公式 产生的集合大小, 该框架可以比较得出不同怀疑 度公式的缺陷定位有效性 上述评估方法是基于 单缺陷程序情况提出, 因此 Xie 等人的理论研究 框架也适用于 INF-MFL 方法 SBFL 是单缺陷定位研究中的一种经典缺陷 定位方法 Lucia 等人比较了 40 种 SBFL 定位公 式的实际定位效果 [84], 他们采用 INF-MFL 调试方 法对定位效果进行评估, 发现没有一种 SBFL 公 式在单缺陷和多缺陷的情况下都能达到最好的定 [86] 位效果 Xia 等人在包含多缺陷版本的大规模 程序上调查研究 SBFL 方法是否能够有效辅助开 发人员实现缺陷的自动定位 研究结果表明 : SBFL 方法的差异性对程序调试的结果和效率有 着重要的影响, 同时 SBFL 方法能有效节约开发 人员的调试时间 传统的 SBFL 在对小规模程序进行缺陷定位 [87] 时通常能够取得较好的定位结果 Heiden 等人 认为传统的 SBFL 方法难以适用于真实的大规模 程序 因此, 他们使用包含多缺陷版本的 Defects4J 评测程序和 AspectJ 评测程序 ( 包含超过 500,000 行代码 ), 对传统的 SBFL 方法进行验证 他们的 实证研究结果表明 :SBFL 方法在定位 90% 的缺陷 时, 需要开发人员平均检查约 450 行代码 因此 他们认为, 需要考虑更多配套软件制品以提高 SBFL 的有效性, 例如通过考虑缺陷报告信息或代 码历史变更信息等, 来进一步提高缺陷定位效果 基于上述研究结果, 我们发现 : 多缺陷通常 会对传统缺陷定位技术的精度产生负面影响, 因 此一些研究人员试图进一步分析多缺陷产生负面 影响的原因, 从而希望后续研究, 可以提出更加 [88] 有效的多缺陷定位策略 Perez 等人认为即使程 序中存在多个缺陷, 但测试时也仅有一个缺陷会 影响程序的运行, 因此 INF-MFL 调试模式相较于 其他调试模式更加适用于多缺陷定位 为了验证 INF-MFL 调试方法是否适用于真实程序, 他们对 真实软件维护过程中的 INF-MFL 调试模式使用 情况进行了分析, 通过挖掘软件仓库, 查找缺陷 修复以及根据修复数量对缺陷进行分类, 以评估 INF-MFL 调试方式在实际软件调试过程中使用的 普遍性 结果表明, 在实际软件调试时, 在 82% 的情况下, 开发人员会使用 INF-MFL 调试方式,

16 16 计算机学报 这表明基于 INF-MFL 调试方式的研究具有很高 [19] 的实用价值 Yan 等人基于 4 个真实工业软件 系统, 展开了多缺陷定位方法的实证研究, 研究 结果表明, 多缺陷程序的异常行为主要来源于程 序缺陷之间的相互作用 Zhang 等人研究了程序 频谱的分布特征对缺陷定位的影响 [89], 重点探讨 了不同类型的语句与程序频谱之间的关系 其中, 他们引入了三种概念以描述不同类型的语句 : 与 缺陷无关, 与缺陷有关和与缺陷排除有关 其中 与缺陷排除有关指的是执行该类型语句会使得测 试用例失败率降低 基于多缺陷程序的实验结果 表明 : 不同类型的语句具有不同的测试用例覆盖 路径特征, 但是多缺陷的存在会削弱每种类型语 句的原始特征 4 基于缺陷独立假设的多缺陷定位方 法 基于缺陷干扰假设的多缺陷定位的 INF-MFL 方法需要开发人员多次迭代并逐个定位并修复缺 陷, 而基于缺陷独立假设的多缺陷定位方法的 IDP-MFL 方法则将多缺陷定位任务划分为多个单 缺陷定位子任务, 以便允许多个开发人员在不同 的子任务上展开并行调试 当被测程序内含有多 个缺陷的时候, 使用并行调试方法可以简化调试 过程, 并缩减软件的交付时间 IDP-MFL 一般会 对失败测试用例进行聚类分析, 并将每个类簇内 的失败测试用例与所有的通过测试用例进行组 合, 以创建针对单个缺陷的测试套件 构建出的 不同测试套件最终被分配给不同的开发人员以进 行并行调试 4.1IDP-MFL 方法的提出与改进 [17] 针对多缺陷定位问题,Jones 等人首次提出 了并行调试的思想, 即对失败的测试用例进行聚 类分析, 并将每个类簇内的失败测试用例与所有 的通过测试用例进行组合, 以生成针对单个缺陷 的测试套件 随后, 将这些针对缺陷的类簇提供 给开发人员以进行并行调试, 他们的工作假设每 个类簇都能够快速定位出被测程序内的某个缺 [8] 陷 然而 Wolfgang 等人通过研究发现 : 上述假 设并不一定成立, 因此他们认为 Jones 等人提出的 [17] 方法存在不足 例如, 如果某一个开发人员完 成调试任务后, 其他开发人员仍在进行调试, 那 么这个开发人员的修复动作可能会影响到其他人 员的调试工作, 从而降低其他开发人员的缺陷定 位效率 同时, 他们发现不同聚类算法对缺陷分离的效果影响很大 随后,Steimann 和 Frenkel [90] 提出了基于整数线性规划 (IntegerLinearProgramming) 的程序频谱分割方法, 他们试图将多缺陷定位问题分解为规模较小且可 独立解决的子问题 因此, 他们采用整数线性规 划算法将程序频谱分割成多个独立的程序频谱分 区, 每个分区内都包含部分测试用例的频谱信息, 且可以由单个开发人进行缺陷定位 结果表明, 与未划分程序频谱的缺陷定位方法相比, 他们提 出的方法能够在每一个分区内获得更高的缺陷定 位精度 使用聚类算法对多缺陷进行分离 (BugIsolation) 是 IDP-MFL 方法中常用的策略之 一, 研究人员从这个角度入手开展了多项研究 聚类的效果直接关系到后续的缺陷定位精度, 如 果聚类结果不准确 ( 即类簇数量不等于程序中的 缺陷数量 ), 则开发人员可能会花费更多的时间进 行 IDP-MFL, 甚至通过多次迭代才能完全修复程 序中的所有缺陷 考虑到聚类效果对定位精度的显著影响, 研 究人员从多个角度提出聚类策略, 试图得到精度 [91] 较高的聚类结果 Wang 等人提出了一种基于加 权特征的聚类选择策略 WAS(WeightedAttribute-basedStrategy) 传统的 SBFL 技术使用的程序谱信息仅通过 1 或 0 来表示对应的语句被某一测试用例 执行 或 未 执行, 而 WAS 策略则对不同类型的程序实体 ( 例 如语句 语句块 函数等 ) 计算怀疑度, 并使用该 怀疑度对测试用例覆盖信息进行加权, 即使用怀 疑度对程序谱中的 1 或 0 进行加权, 并根 据加权后覆盖信息的相似度对测试用例进行聚 类 基于多缺陷程序上的实验结果表明, 使用 WAS 策略在缺陷定位中的聚类效果要优于其他 聚类算法 Wei 和 Han [92] 提出了一种基于参数组 合的方法来帮助开发人员快速定位多个缺陷 该 方法使用二分法对失败测试用例进行聚类, 进而 生成针对单个缺陷的测试套件 实验结果证明, 该方法的多缺陷定位效果要优于使用 Tarantula 怀 疑度计算公式的 INF-MFL 方法, 且优于其他几种 [93] 主流的缺陷定位技术 Parsa 等人基于程序层次 聚类角度, 提出了 Hierarchy-Debug 方法

17 李征等 : 软件多缺陷定位方法研究综述 17 Hierarchy-Debug 方法旨在分析程序谓词之间的影 响, 从而将分层聚类算法应用于聚类谓词, 从而 实现定位多个包含缺陷的谓词语句 实验结果表 明, 该方法可以帮助开发人员查找与缺陷相关的 谓词 [94] 曹鹤玲等人提出了一种基于 Chameleon 聚 类分析的多缺陷定位方法 该方法首先选择每一 个失败测试用例和所有通过测试用例的覆盖路径 来计算怀疑度值, 并选择怀疑度值较高的数个语 句作为该失败测试用例的特征向量 然后使用 Chameleon 聚类算法通过上述特征向量对失败测 试用例进行聚类 最后将每个类簇内的失败测试 用例和所有通过测试用例的覆盖路径计算得到多 个怀疑度排序列表 他们的方法假设每个类簇均 对应程序中一个缺陷, 因此他们采用并行调试模 式, 来同时定位程序中的多个缺陷 基于 SIR 程 [17] 序集上的实验结果表明 : 其方法比 Jones 等人 提出的 INF-MFL 方法在效率有所提升, 且调试迭 代次数下降 为了进一步提高聚类的精度, 部分研究人员 对传统的聚类算法进行了改进, 其中的一种常用 策略是提出更为精确的测试用例距离度量方法 例如,Gao 和 Wong 等人提出了一种并行定位多 个缺陷语句的方法 MSeer [20], 该方法基于一种改 进的 k-medoids 算法对失败测试用例进行聚类, 然 后使用聚类后的测试套件进行缺陷定位 实验结 果表明 :MSeer 比 INF-MFL 方法和 Jones 等人的 方法在缺陷定位效率和效果上均表现得更好 Zakari 等人 [95] 使用了基于边缘间距 (edge-betweenness) 的距离公式来度量程序语句 ( 即节点 ) 执行的距离, 并提出一种网络社区聚类算 法 该算法将失败测试用例划分至多个类簇中, 其中每个类簇仅针对单个缺陷 实验结果表明, 网络社区聚类算法可以有效地将不同的缺陷分离 至以缺陷为中心的不同类簇中 但是,Zakari 等 [96] 人认为现有的聚类算法无法有效地将失败的测 试与其引起的缺陷进行有效划分, 这对缺陷定位 存在负面影响 随后, 他们考虑到类簇中连接越 密集的程序语句越有可能包含相同的缺陷, 在原 始网络社区聚类 (DivisiveNetworkCommunityClustering) 结果中通 过删除相似度较低的关联, 以进一步精简类簇 实验结果表明 : 与 MSeer 和原始方法相比, 他们 提出的改进方法具有更好的多缺陷定位效果 [97] 王兴亚等人认为与特定缺陷无关的失败测 试用例是 SBFL 方法缺陷定位有效性降低的主要 原因 因此, 他们提出了一种基于模糊 C 均值聚 类 (FuzzyC-MeansClustering) 的多缺陷定位方法 FCMFL 该方法首先通过模糊 C 均值聚类分析失 败测试用例与不同缺陷间的隶属关系, 得到与每 个缺陷关联的失败测试用例, 然后根据隶属度作 为权重计算每条语句的怀疑度, 最终每个类簇将 生成一个语句检查序列, 以指导开发人员进行程 序调试 基于 6 个 Siemens 程序和 6 个 SIR 库中 的程序的实验结果表明 : 与 Tarantula Ochiai Naish 和 Wong 等方法相比,FCMFL 方法可以降 低多缺陷对 SBFL 方法的负面影响, 从而提高 SBFL 方法的缺陷定位精度 除了聚类方法, 研究人员还从其他不同角度 [98] 实现 IDP-MFL 例如,Jeffrey 等人提出一种基 于值替换 (ValueReplacement) 的缺陷定位方法 该 方法在 INF-MFL 过程中可以反复更改执行程序 的状态, 通过搜索程序运行中可能导致出现异常 的赋值语句来定位缺陷语句 但是反复更改程序 状态在多缺陷程序中会带来更多的时间开销 [99] [99] 因此, 他们将并行调试引入到值替换方法中, 以减少定位多个缺陷所需的总时间消耗 实验结 果表明, 并行调试下的值替换方法在定位单个版 本中的所有缺陷仅需数分钟, 因此可以有效减少 缺陷定位的时间开销 Sun 等人提出了一种基于 迭代的方法 IPSETFUL, 用于选择更有效的测试 用例 [100] IPSETFUL 方法首先依据执行结果生成 程序谱概念格 (ConceptLatticeofProgramSpectrum, 简称 CLPS), 并将程序语句划分为危险 敏感和 安全三个级别, 随后开发人员检查危险级别的语 句以判断是否含有缺陷 然后,IPSETFUL 选择 部分测试用例覆盖危险和敏感的语句, 在下一次 迭代中生成新的 CLPS, 直到所有测试通过则迭代 终止 实验结果表明 :IPSETFUL 方法的定位效 果要优于一些传统 SBFL 方法 ( 例如 Jaccard, Ochiai,Tarantula) 表 4IDP-MFL 方法相关论文统计结果 分类论文数量 缺陷分离 [8,20,90,91,92,93,94,95,96,97] 10 其他方法 [98,99,100] 3 本节对已有的 IDP-MFL 相关论文进行了分 类统计, 最终统计结果如表 4 所示 从表 4 可以 看出, 为了实现并行调试任务, 研究人员提出了

18 18 计算机学报 多种方法将单个多缺陷定位任务划分为多个子任 务, 其中基于聚类的划分方法被最广泛使用 基 于聚类的多缺陷定位方法会将执行失败的测试用 例划分至多个类簇中, 每一个类簇内的失败测试 用例均由同一个缺陷导致, 因此多个开发人员可 以并行地使用多个类簇, 分别定位到程序中的每 一个缺陷 基于聚类的多缺陷定位方法的结果准 确度与聚类的精度有较强的相关性, 因此这部分 研究工作都试图提出更高聚类精度的聚类方法, 使得多缺陷定位效果更好 4.2 针对 IDP-MFL 方法的实证研究 除了提出并行调试场景下多缺陷定位的新方 法, 研究人员还针对 IDP-MFL 方法的有效性展开 了实证研究 为了从 IDP-MFL 角度上验证多缺陷对缺陷 [101] 定位是否存在负面影响,Li 等人对多缺陷划分 进行了实证研究 考察不同精度的聚类结果对多 缺陷分离后的缺陷定位效果的影响 实证结果表 明, 缺陷定位的效果与聚类算法的聚类效果密不 可分, 聚类算法的聚类效果越差, 其定位效果也 越差 因此划分的准确度对于后续步骤来说至关 [102] 重要 Huang 等人对缺陷定位中的缺陷分离进 行了实证研究, 他们分析了 6 种缺陷定位方法 (Naish2 Jaccard Tarantula Wong2 Wong1 和 Rogot1) 和两种聚类方法 ( 即 K-means 聚类和层次 聚类 ) 对缺陷分离效果的影响 结果表明,Wong1 能实现最好的缺陷定位效果,K-means 聚类算法 [103] 缺陷分离上要优于层次聚类算法 Zakari 等人 通过调查研究, 他们发现 : 使用基于失败测试用 例的覆盖相似性与距离度量进行划分的聚类算法 并不合适 他们调查了并行调试方法的有效性, 实验中通过 K-means 聚类算法和三个基于相似性 的距离度量公式来评估缺陷定位的效果 同时, 他们比较了最新的并行调试方法 MSeer 和 INF-MFL 调试方法的缺陷定位效果 实验结果表 明 : 基于失败测试用例执行路径相似度的聚类算 法并不适用于缺陷分离, 同时使用该聚类算法会 降低多缺陷定位的效果 为了分析部分情况下聚类算法效果较差的原 [21] 因,DiGiuseppe 等人对多缺陷程序内部的缺陷 相互影响情况进行了研究, 因为他们认为当程序 内含有多个缺陷时, 可能部分缺陷之间会存在相 互影响, 进而对多缺陷定位效果产生一定的负面 [15] 影响 针对上述问题,DiGiuseppe 等人将缺陷 间的干扰现象分为四类 ( 详见 2.2 节 ), 在他们的 研究中, 缺陷混淆是最普遍存在的一种现象, 应 该受到更多的关注与研究 [10] 随后,Xue 等人发现, 在面向对象的程序 设计语言中也存在缺陷干扰现象, 但这种现象对 缺陷定位性能的影响可以忽略不计 DiGiuseppe [104] 等人从缺陷数量 缺陷类型和缺陷定位方法等 方面展开了大规模实证研究 他们的实验结果表 明, 缺陷数量对缺陷定位有效性影响显著 同时, 他们发现缺陷类型与缺陷定位干扰之间不存在相 关性 该研究结果对软件开发的实践人员和研究 人员具有一定的指导意义 除此之外,Yan 等人 研究了缺陷数量对基于频谱的缺陷定位方法的影 响 [105] 他们基于 14 个大规模开源程序进行了评 估, 实验结果表明, 尽管多缺陷确实会对缺陷定 位效果产生负面影响, 但是不同的缺陷定位技术 的负面影响程度并不相同 5 不基于任何假设的多缺陷定位方法 不基于任何假设的多缺陷定位的 NOH-MFL 方法与 INF-MFL 方法和 IDP-MFL 方法不同, 这 一类方法通过单次迭代来定位多个缺陷语句, 且 不把多缺陷定位任务进行拆分 NOH-MFL 方法 缩减了其他 INF-MFL 方法需要多次编译被测项 目和执行测试 ; 用例所产生的时间开销, 且避免 了聚类算法产生的额外开销, 和聚类过程可能产 生的聚类结果不准确的问题 现有的 NOH-MFL [106,107] 方法通常使用人为限制或机器学习的方法 来设置缺陷语句搜索上限, 以减少人工调试成本 和提高缺陷定位效果为研究目标 本文在调研时 发现, 相比前两类方法,NOH-MFL 方法较少受 到研究人员的关注, 在最近 12 年中仅有 10 篇相 关论文发表 这些论文根据研究思路的不同主要 分为两类 :(1) 多个缺陷语句排列在同一个语句有 序列表中 ;(2) 借助机器学习算法实现多缺陷语句 的一次定位 第一类方法与传统缺陷定位流程相似, 不同 的是研究人员通过改进怀疑度计算方法, 尝试将 程序内的多个缺陷语句都排在有序列表的前列, 从而让开发人员可以快速定位到多个缺陷语句 Abreu 等人 [108] 结合了 SBFL 方法和 MBD(Model-BasedDiagnosis) 方法提出了一种缺 陷定位方法 BARINEL 该方法基于测试用例的程

19 李征等 : 软件多缺陷定位方法研究综述 19 序频谱对被测程序进行建模, 随后基于 Ochiai 公 式计算每个程序模块含有缺陷的概率 作为其组 成部分的 MBD 方法主要针对多缺陷定位问题提 出,MBD 方法首先依据频谱信息构建程序语句组 合, 然后采用贝叶斯推理 (BayesianReasoning) 计算 不同程序语句组合的出错概率, 最终排在前列的 程序语句组合被认为是多缺陷语句 BARINEL 方 法充分利用了程序频谱所包含的信息, 并考虑到 多条语句对程序输出的影响 基于 Siemens 数据 集上的实验结果表明 :BARINEL 方法在多缺陷定 位性能上要优于 SBFL 方法 (Ochiai 和 Tarantula) [109,110] 和仅使用贝叶斯推理的方法 Abreu 等人还 提出一种基于逻辑推理的缺陷定位方法 Zoltar-M 该方法将程序语句视为组件, 采用贝叶 斯方法分别计算出组件对输出失败和输出通过的 概率, 然后对程序候选语句计算出错概率, 最后 按照出错概率的大小进行降序排列 实验结果表 明 :Zoltar-M 方法在多缺陷定位效果上要优于 Ochiai 和 Tarantula 等传统缺陷定位方法 Lamraoui 和 Nakajima [111] 采用全流敏感追踪 公式 (FullFlow-SensitiveTraceFormula) 对程序进行 编码, 可以更为有效地识别出程序缺陷位置 他 们的方法结合基于满意度的公式验证技术和基于 模型的诊断理论, 因此能够定位程序中多个缺陷 然而, 他们的方法仅在 Siemens 评测程序中一个 相对较小的程序 ( 即 Tcas) 上进行了验证 此外, 对于包含多个缺陷的大规模程序来说, 他们的方 法在缺陷定位时仅考虑了通过测试用例, 而未考 虑失败测试用例 而失败测试用例在已有的 MFL [10,15,104] [107] 研究中则被经常使用 Zakari 等人基于 复杂网络理论, 提出了一种缺陷定位方法 FLCN FLCN 方法采用度中心性 (DegreeCentrality) 与结 构洞 (StructuralHole) 来查找缺陷相关语句 FLCN 方法能够在一次调试迭代中同时定位多个缺陷 实验结果表明 :FLCN 方法要优于现有的缺陷定 位方法 ( 例如 Tarantula,Ochiai 等 ) 第二类方法主要借助基于搜索的方法, 该方 法将程序中的各个实体视为对象, 然后通过学习 [5] 算法找到多个缺陷语句的位置 Wong 等人结合 神经网络算法, 提出了一种基于径向基函数的多 缺陷定位方法 该方法把测试用例的覆盖路径视 为特征向量, 并把测试用例的执行结果 ( 即成功 / 失败 ) 作为神经网络的输出数据 然后为每一个程 序语句构造虚拟覆盖路径作为训练数据 其中每 个虚拟覆盖路径都只会覆盖一个语句, 则神经网 络的输出就是该语句的怀疑度值 例如, 为包含 5 行语句的程序中的第 3 行语句构造虚拟覆盖路 径, 则路径为 将该虚拟路径作为特征 向量输入神经网络, 输出数值即为第 3 行语句的 怀疑度值 实验结果表明, 该方法的多缺陷定位 效果要优于使用 Crosstab 或 Tarantula 等公式的基 [112] 准方法 何加浪等人认为 INF-MFL 和 IDP-MFL 方法的效果都不够理想, 其原因是由于 缺陷之间的复杂关系使多缺陷定位问题变得十分 复杂 因此, 通过深入分析缺陷间的征兆相关信 息, 计算出输入对各个缺陷的支持度分量, 构造 合适的神经网络模型来学习输入与缺陷位置的关 系 神经网络训练完成后, 针对每个语句构造一 个虚拟测试作为已训练出的神经网络的输入, 神 经网络的输出结果即为该语句的怀疑度值 该方 法的网络模型第一层选用概率神经网络 (ProbabilisticNeuralNetwork, 简称 PNN), 用于判 断输入对各缺陷的支持度, 第二层选用径向基函 数网, 利用 RBF 的逼近能力, 计算每个语句为缺 陷语句的概率, 然后生成有序列表, 并最终完成 多缺陷定位 实验结果表明 : 他们的方法效果优于现有的 RBF-FL [5] 和 PARA-FL [17] 方法 王赞等 [23] 人提出一种基于遗传算法的多缺陷定位方法 GAMFal GAMFal 方法包括三个步骤 : 首先对多 缺陷定位问题进行建模, 利用遗传算法搜索最优 种群, 确定缺陷分布的染色体编码方式和选定合 适的适应度函数 ; 随后使用遗传算法在解空间中 搜索具有最高适应度值的候选缺陷分布, 在满足 终止条件后返回最优解种群 ; 最后依据最优解种 群对程序实体排序, 最终开发人员可以依次检查 程序实体并确定多个缺陷的具体位置 基于 Siemens 程序集中的 7 个程序和 Unix 程序集中的 3 个程序 (gzip grep 和 sed) 作为评测对象,GAMFal 方法在整体定位效率方面优于其他经典的缺陷定 位方法 (Tarantula ImprovedTarantula 及 Ochiai), 且需要更少的人工交互 除此之外,GAMFal 的 [106] 执行时间也在可接受的范围之内 Zheng 等人 提出了一种基于遗传算法的 FSMFL 方法 FSMFL 方法将所有语句按照是否含有缺陷编码成染色 体, 例如, 表示一个 10 行代码的 程序中第二行和第五行代码包含缺陷 使用操作 算子 ( 例如选择 交叉 变异 ) 进化种群, 直到个体 的适应度函数达到预定的阈值, 最终个体内为 1

20 20 计算机学报 的语句即为缺陷语句 实验结果表明,FSMFL 在 多缺陷定位的效果和精度上, 比较传统的 SBFL 方法 (Tarantula,Ochiai,DStar 等 ) 都具有更好的定 [113] 位效果 Wang 等人提出了一种通过分析缺陷 传播环境来确定缺陷的方法, 缺陷传播环境是指 测试用例执行缺陷语句之后的程序异常状态, 其 通常体现于变量的异常值或异常的谓词判断结 果 他们的方法通过识别缺陷程序和示例程序之 间的执行状态和结构语义上的差异来定位可疑语 句 通过对值序列和结构语义进行交互分析, 可 以减少代码变化和缺陷传播的影响 实验结果表 明, 该方法可以有效地定位可疑语句, 并在有足 够的示例程序的情况下可以为缺陷修复提供帮 助 表 5NOH-MFL 方法相关论文统计结果 分类论文数量 多个缺陷在单个怀疑度 排序列表内排名靠前 机器学习算法一次性识 别程序中的多个缺陷 [107,108,109,110,1 11] [5,23,106,112,113] 5 本节对 NOH-MFL 相关方法进行了分类统 计, 统计结果如表 5 所示 从表 5 中可以看出, NOH-MFL 定位方法主要分为两种策略 所有缺 陷语句在单个怀疑度排序列表内排名靠前的位 5 置 这一策略旨在把所有的缺陷语句排名至怀疑度排序列表的靠前位置, 因此开发人员在根据怀疑度排序列表依次检查语句时, 能在较短的时间内找到多个缺陷语句 通过搜索算法一次性识别程序中的所有缺陷 是一个理想化的策略, 旨在使用如遗传算法等元启发式搜索算法, 或神经网络等机器学习算法, 一次性识别并修复程序中的缺陷语句 6 性能评测指标分析 这一节我们对 MFL 研究中经常使用的评测指标进行了分类, 并统计了不同指标的累计使用频率, 结果如表 6 所示, 表中仅列出了使用频率超过 1 次的性能评测指标 从表中可以看出, ExamScore 指标的使用次数最多, 累计使用次数达到了 20 次 其次分别是 ExpenseScore 指标和 Wastedeffort 指标, 分别为 19 次和 12 次 根据不同的代码审查策略, 本文将表 6 中的性能评测指标分为两类, 即基于代价的评测指标和基于精度的评测指标 不同的评测指标适用于不同的调试模式, 接下来将依次介绍这些评测指标并举例说明 表 6 性能评测指标使用次数统计结果 指标类别 指标名称 累计使用次数 EXAMscore 20 Expensescore 19 基于代价的评测指标 Wastedeffort 12 Average/Cumulativenumberofstatementsexamined 11 T-score 5 Efficiency 3 基于精度的评测指标 Top-N 8 Proportionofbugslocalized 基于代价的评测指标基于代价的评测指标, 通过统计开发人员定位出程序中真实缺陷位置所需的时间成本来评估缺陷定位技术有效性 常见的基于代价的评测指标有 :EXAMscore 及其相关指标 检查语句总和及均值 EXAMscore 及其相关指标 EXAMscore 是缺陷定位研究中最常使用的评 测指标之一 [37,95,96,105,114], 这是一种基于语句怀疑度排序的评价指标, 研究人员将程序实体按怀疑度取值从高到低进行排序, 并依次审查, 直到找到缺陷语句 EXAMscore 指标衡量开发人员发现第一个缺陷语句所需要检查代码的百分比 [67], 其计算公式为 : EXAM score = rankof the faultyentity numberof theexecutableentities (1)

21 李征等 : 软件多缺陷定位方法研究综述 21 在公式 1 中, 分子是缺陷语句在怀疑度排序列表中所处的位置 ( 即 Rank 值 ), 分母是被执行的程序语句总数 当存在多条语句的怀疑度取值相等的时候, 那么 rank 值将无法确定 目前有三种方式可以计算其对应的 rank 值 假设存在缺陷语句 ef, 怀疑度取值高于 ef 的正确语句数量为 A, 怀疑度取值与 ep 相同的正确语句数量为 B, 则 : 1. 最好情况 : 在检查所有怀疑度值与缺陷语句 ef 相同的语句时, 开发人员第一个检查的就是语句 ef, 即开发人员能够以最快的速度定位真实缺陷语句的位置 此时 rank 值的计算公式为 : rank e f = A + 1 (2) 2. 最坏情况 : 与 最好情况 " 相反, 在检查所有怀疑度值与缺陷语句 ef 相同的语句时, 开发人员最后一个检查的才是 ef, 即开发人员需要耗费最多的时间定位缺陷语句 此时 rank 值的计算公式为 : rank e f = A + B (3) 3. 平均情况 : 介于最好情况与最坏情况之间, 即开发人员会检查一部分怀疑度值与缺陷语句 ef 相同的正确语句, 但是不及 最坏情况 那么多 此时 rank 值的计算公式为 : IDP-MFL 调试方法提出了 T-EXAM 评测 指标 T-EXAM 通过计算所有子任务中 定位首个缺陷语句的 EXAMscore 值的总 和来评估多缺陷定位方法的效率 ; [106] 2. Zheng 等人在他们的研究工作中针对 NOH-MFL 调试方法提出了 EXAM F 和 EXAM L 评测指标 EXAM F 和 EXAM L 分别表示单次迭代中定位第一个缺陷和 最后一个缺陷所需要检查的程序语句占 总程序语句的百分比 检查语句总和及均值 EXAMscore 及其相关指标针对是单个缺陷版 本内的缺陷定位时间成本 除此之外, 研究人员 还提出了针对多个缺陷版本的评测指标 : 检查语 句总和 (Cumulativenumberofstatementsexamined, CNSE) 和检查语句均值 (Averagenumberofstatementsexamined, ANSE) [66] CNSE 评测指标是指对于给定的被测程 序,n 表示缺陷版本的数量, M 和 N 表示两种不同 的缺陷定位技术 M(i) 和 N(i) 指的是通过 M 和 N 进行缺陷定位后, 在第 i 个缺陷版本定位所有缺 陷语句所需检查语句数量的总和 由此可知, 如 n n 果 i=1 M i < i=1 N i, 则 M 比 N 更有效 越低的 CNSE 值意味着更好的缺陷定位技术 ANSE 评测 rank e f = A+1 +(A+B) 2 (4) [20] 指标与 CNSE 评测指标相似, 如果 n i=1 M i n < 包括 EXAMscore 在内的基于检查语句百分 比的评估方法是缺陷定位领域最常用的评估方 法 在本文统计的 MFL 相关论文中, ExpenseScore Wastedeffort T-score 和 Efficiency 的计算公式与 EXAMscore 的计算公式 ( 式 1) 完全 相同, 所评估的内容也完全一致 对于单缺陷程序定位,EXAMscore 值越小表 明开发人员只需要检查较少的语句就能找到真正 的缺陷语句, 则相应的缺陷定位方法有更好的缺 陷定位效果 但是 EXAMscore 指标仅能评估单个 缺陷的定位时间成本, 不能完整统计 IDP-MFL 和 NOH-MFL 过程产生的总体时间成本, 因此传统 的 EXAMscore 更适用于基于缺陷干扰假设的多 缺陷定位技术的评测 为了使 EXAMscore 能够评测更多类型的缺 陷定位方法, 研究人员对原有的 EXAMscore 评测 指标进行了拓展 例如 : [20] 1. Gao 等人在他们的研究工作中针对 n i=1 N i n, 则 M 比 N 更有效 因为 CNSE 和 ANSE 指标统计了每个缺陷版本的所有缺陷语句的定位 时间成本, 所以这两个指标适用于单缺陷和多缺 陷定位问题, 且同时适用于三种不同多缺陷调试 模式 6.2 基于精度的评测指标 基于精度的评测指标, 通过统计经过缺陷定 位技术处理之后达到某一定位精度要求的程序版 本数量, 从而评估缺陷定位技术有效性 TOP-N TOP-N 评测指标同时适用于单缺陷和多缺陷 定位问题 在软件单缺陷定位问题中,Top-N 是 指开发人员在检查排名表前 N 个程序实体 ( 如程 序语句 函数或文件 ) 内, 就能发现缺陷的程序版 本数量 该指标在部分文献中也称为 acc@n Top-N 值越高表示开发人员在检查相同数量的语 句行, 对应的缺陷定位技术能检测到缺陷版本数

22 22 计算机学报 量越多, 相应的缺陷定位技术就有着更好的定位 精度 针对多缺陷定位问题,Top-N 为前 N 个实 体内成功检测到真实缺陷的数量, 同理,Top-N 值越高表明相应的技术能定位到更多的缺陷 [115] 据 Kochhar 等人的研究统计, 大多数开发 人员在进行缺陷定位时仅会检查怀疑度排序列表 中靠前的一些程序实体 其中,9.43% 的开发人员 只检查第一个程序实体, 而 73.58% 的开发人员会 检查前 5 个程序实体, 接近 98% 的开发人员认为 检查前 10 个程序实体是较为合理的 因此 TOP-1, TOP-5 和 TOP-10 这三个指标具有重要的意义 定位缺陷比率 定位缺陷比率 (Proportionofbugslocalized) 评 测指标首先会设定数个比率, 并假定开发人员在 缺陷定位的过程中只愿意检查给定比率的代码, 然后针对每个比率计算能够被定位的程序缺陷的 数量 因此, 在相同比率下, 能够定位到更多程 序缺陷的缺陷定位技术效率更高 [83] Sun 等人在他们的研究中分析了部分缺陷 定位公式能够取得更好缺陷定位效率的原因 他 们的实验结果表明,Tarantula 和 Ochiai 公式在仅 检查 10% 的程序元素时可以定位 39% 和 45% 的缺 陷 Klosgen 和 AddedValue 公式相比可以定位更 多的缺陷, 分别为 47% 和 48% 7 统计显著性分析 统计假设检验 (Statisticalhypothesistest) 是用 来判断样本与样本, 样本与总体的差异是由抽样 引起还是本质差别造成的统计推断方法 其基本 原理是先对总体的特征作出某种假设, 然后通过 抽样研究的统计推理, 对此假设应该被拒绝还是 接受作出推断 假设检验可分为正态分布检验 正态总体均值分布检验 非参数检验三类 考虑 到缺陷定位领域的怀疑度无法满足参数检验要求 的假定, 因此研究人员大量采用的非参数检验, 例如曼 - 惠特尼 U 检验 (Mann-WhitneyUtest), Wilcoxon 符号秩检验 (Wilcoxonsigned-ranktest), 其使用次数统计结果如表 7 所示 表 7 显著性分析方法使用次数统计结果 指标 累计使用次数 Wilcoxon 符号秩检验 6 曼 - 惠特尼 U 检验 2 studentt 检验 1 Quade 检 1 Wilcoxon 符号秩检验 (WilcoxonSignedRankTest) 是由 Wilcoxon 于 1945 年提出, 是缺陷领域中研究人员最常使用的指标 [80,95,103] Wilcoxon 符号秩检验是一种非参数假设 检验方法, 不受样本总体分布的影响, 但严格要 求进行检验的两组样本数量一致 通常研究人员 在比较不同缺陷定位技术的定位效果, 都是在相 同的数据集下进行实验, 因此最终得到的定位结 果都是匹配的, 符合 Wilcoxon 符号秩检验的条件 [95] 例如,Zakari 等人使用 Wilcoxon 检验基准方法 在多缺陷程序中定位的缺陷数量是否大于比提出 的方法定位的缺陷数量, 实验显示提出的方法能 有效定位更多的缺陷 实验中常采用置信水平为 95% 的 Wilcoxon 符号秩检验进行显著性分析 [20,25,48,63,88,95,103,106], 即假设检验水准为 0.05 该种 检验方法适用于 INF-MFL, IDP-MFL 和 NOH-MFL 三类缺陷定位方法, 是检验不同缺陷 定位方法效果是否存在显著性差异的首选指标 曼 - 惠特尼 U 检验 (Mann-WhitneyUtest) 是由是 由 Mann 和 Whitney 于 1947 年提出, 是一种非参 数的假设检验方法, 适用于检验两组数据是否来 自同一样本总体 其假设基础是, 若两组样本存 在差异, 则其中心位置将不同, 因此这种检验方 法不要求两组数据必须严格匹配 在缺陷定位领 域, 曼 - 惠特尼 U 检验常用于检验不同缺陷定位技 术的定位效果是否存在显著性差异 例如, [104] DiGiuseppe 等人使用曼 - 惠特尼 U 检验来检验 不同因素对多缺陷定位的效果是否存在显著性差 异 由于曼 - 惠特尼 U 检验可适用于两组样本数量 不同的情况, 因此建议研究人员在实际实验中对 非匹配样本数据检验时可采用该种假设检验方法 Studentt 检验 (Student'sttest), 简称 t 检验, 最 早是由 William 于 1908 年发表于 Biometrika [116] t 检验主要用于样本含量较小, 总体标准差未知的 正态分布 t 检验通过 t 分布理论来推论差异发生 的概率, 从而比较两组样本的均值是否存在显著 [104] 性差异 例如,DiGiuseppe 等人在他们的研究 中同样使用了 studentt 检验, 他们使用 t 检验评估 缺陷数量对缺陷定位花费的影响是否显著 最终 结果表明他们不能拒绝原假设, 即缺陷数量对缺 陷定位花费影响显著 但是 t 检验的使用前提是 总体样本需要服从正态分布, 因此在使用该假设 检验方法前需要先检验定位结果是否服从正态分

23 李征等 : 软件多缺陷定位方法研究综述 23 布 然而很难保证定位结果能够满足该要求, 因累计使用次数和初次使用时间, 以及程序规模分此不建议研究人员使用 t- 假设检验方法 类等信息 从表 8 中可以看出, 被采用次数最多 Quade 检验一种非参数的假设检验方法, 是的评测对象是 C 语言的 Siemens 程序集 Unix 程 Wilcoxon 符号秩和检验的多重采样扩充, 由序集以及 Space 程序, 其次是 Java 语言的 DanaQuade 提出 [117],Quade 检验适用于检验多组 Defects4J 程序集 NanoXML 程序和 Ant 程序, 数据是否来自同一样本总体 例如 Wolfgang 等人除此之外还有 Linux 编译程序 Make 和其他开源程使用 Quade 检验, 研究不同程序划分算法对缺陷序 划分效果的影响 他们提出假设 : 实验中采用的 8.1 常用评测对象介绍五个划分算法产生的数据结果是有关联的 最终如表 8 所示, 研究人员广泛使用的评测程序实验结果表明该假设被拒绝, 即不同程序划分算主要分为 C 语言程序和 Java 语言程序这两类 论法对缺陷划分的效果影响有差异 这种假设检验文将各个评测程序进一步细分为大 中 小三种方法适用于 IDP-MFL 方法不同程序划分算法的规模, 其中代码行数小于 1000 行的程序被称为小比较 规模程序, 行数在 1000 行至 行之间的程序 8 评测对象分析 在多缺陷定位的研究工作中, 研究人员一般使用开源软件作为评测对象进行实证研究 我们对论文中使用的评测对象进行了系统整理, 统计了累计使用次数, 结果如表 8 所示 需要说明的是在表中我们仅列出了使用频率最高的 10 个评测对象, 因此该表并未包含使用次数较少的评测对象 表 8 列出了评测程序的名称 编程语言 被称为中等规模程序, 行数超过 行的程序被称为大规模程序 除了 Defects4J 以外的所有评测程序都来自于软件代码仓库 SIR(Software-artifactInfrastructureRepository) [118], SIR 提供了丰富的软件源代码 配套的测试用例 人工植入或真实的软件缺陷, 以及多种辅助脚本工具方便研究人员使用 这些有利条件使得 SIR 成为了研究人员使用最广泛的评测程序来源之一 表 8 评测对象使用次数统计结果 评测对象 编程语言 累计使用次数 首次使用时间 程序规模 Siemenstestsuite [119] C 小规模 Unixprograms [118] C gzip 为中等规模, 其余为大规模 Defects4J [120] Java 大规模 Space [121] C 中等规模 NanoXML [122] Java 中等规模 Ant [123] Java 大规模 Make [124] C 大规模 XML-Security [125] Java 大规模 Jmeter [126] Java 大规模 Jtopas [127] Java 中等规模 在 SIR 库中,Siemens 测试套件是使用时间最早, 使用次数最多的小规模被测程序, 累计有 40 项研究使用了该程序集 Siemens 测试套件是由西门子公司研究部的 Ostrand 及其同事搜集而成, 用于研究控制流和数据流覆盖标准的缺陷检测能力,Ostrand 将其共享给 SIR 库 Siemens 测试套件中包含 7 个程序, 其中 tcas 是飞机防撞系统, schedule2 和 schedule 是优先级调度程序,tot_info 是在输入数据给定的情况下计算统计信息, print_tokens 和 printtokens2 是词法分析器, 而 replace 执行模式匹配和替换程序 Siemens 测试套件因其规模小 运行速度快等特点被大量缺陷定位相关研究所采用 [66,101], 但是 Siemens 测试套件包含的这 7 个程序的代码长度均未超过 600 行, 其代码规模远小于真实生产环境中的大规模程序 为了使实验结论更具普遍性和实际指导意义, 研究人员随后进一步在 SIR 库中添加了中大规模程序, 其中常用的包括 Unix 程

24 24 计算机学报 序集 ( 包含程序 grep gzip sed 和 flex) 和 Space 程序 在 Unix 程序集中,flex grep gzip 和 make 均为来自 Gnu 站点的 Unix 实用程序 其中,flex 是一个词法解析程序, 包含 11,000 多行代码 ; Grep 是一个文本搜索工具, 能使用特定模式匹配搜索文本, 该程序中包含 13,000 多行代码 ;Gzip 是一个 GNU 自由软件的文件压缩程序, 包含 6,000 多行代码 相比 Siemens 程序集,Unix 程序集的代码规模更大, 可以模拟真实生产环境中的中大型程序, 因此 Unix 程序集也被众多研究人员采用 [9,63,68,74,75,97,108,111] 但是 Unix 程序集中的缺陷大都采用人工植入的方式来产生, 因此即使其规模接近生产环境中的程序, 其缺陷类型依然与生产环境中的缺陷存在差异 为了进一步提高研究工作的可信度, 研究人员随后在 SIR 库中添加了来自真实生产环境的大型缺陷程序 Space Space 程序是一个针对数组定义语言 (ArrayDefinitionLanguage, 简称 ADL) 的解释器, 包含 9,000 多行代码 该程序读取含有多个 ADL 语句的文件, 并检查文件内容是否符合 ADL 语法和特定的一致性规则 Space 程序的每一个缺陷均来自真实的生产过程, 能在一定程度上代表真实生产环境中的缺陷程序 上述评测对象均基于 C 编程语言实现, 随着近些年来面向对象语言程序的日益流行以及 Java 语言程序占比的逐步升高, 研究人员逐渐在实证研究中考虑基于 Java 语言实现的评测对象 其中以 Defects4J NanoXML 和 Ant 为主 Defects4J 程序集是一个开源软件缺陷存储库, 可以帮助软件相关从业人员和研究人员评估缺陷定位效果 ; NanoXML 是一个轻量级 XML 解析程序, 包含 8,000 多行代码 ;Ant 是 Apache 项目提供的基于 Java 的开源构建工具, 类似于 Unix 的 Make 程序 在上述 Java 评测对象中,Defects4J 最初是由 Martinez 等人开发 [128], 现在已广泛用于缺陷自动定位和修复方法的评估 [129,130] Defects4J 经过了同行评审和结构化调整, 被认为是当下具有良好组织的最大真实 Java 缺陷公开数据库 [131], 因此近年来 Defects4J 程序集成为了缺陷定位领域的主流评测对象 Defects4J 属于大规模 Java 程序, 截至 2020 年 7 月最新版本的 Defects4J 中共包含 17 个中大规模 Java 程序, 共 835 个真实的缺陷版本 但是 Defects4J 的版本仍在不断迭代, 且规模不断 扩大, 因此表 8 中只列出了 Defects4J 更新之前最 常用的 6 个程序 从表 8 中可以看出, 目前的多缺陷定位研究 采用的评测对象基本上都是集中于强类型编程语 言 ( 例如 C++ 和 Java 等 ) 但当前的智能软件系 统需要使用机器学习算法, 其中大部分借助弱类 型编程语言 ( 例如 Python 等 ) 实现 针对这类系 统, 我们在后续工作中需要深入分析 例如, 多 缺陷的干扰是否更为严重, 以及现有的多缺陷定 位方法是否能够在这类智能软件系统中取得好的 定位效果 8.2 缺陷植入分析趋势分析 缺陷植入是指通过代码变异或人工修改等方 式在正确的程序中植入缺陷, 并且该过程仅适用 于人工植入缺陷类型的评测程序 在来自 SIR 库的评测程序中 ( 如 Siemens 程序 集 Unix 程序集等 ), 许多程序仅提供了植入单个 缺陷的版本, 因此这样的评测程序不适用于多缺 陷定位研究 为了解决上述问题, 研究人员通过 自行制作多缺陷版本的方式构造被测程序 [8,20,60,99,100,102,108,111] 研究人员把多个来自不同单 缺陷版本的缺陷语句植入到同一个评测程序中, 在此过程中, 如果同一行代码在不同版本中具有 不同的缺陷, 则在植入过程中, 一行代码内仅可 以包含其中一个缺陷, 因为当前的缺陷定位方法 不能在单行语句中识别不同类型的缺陷 此外, 由于基于频谱的缺陷定位需要至少一个失败的测 试用例, 因此在植入的过程中通常会排除没有失 败测试用例的缺陷版本 最后, 由于只有可执行 语句才能影响程序的执行或产生覆盖率信息, 因 此还会排除位于头文件 变量定义或声明的缺陷 图 9 缺陷植入方式统计 图 9 给出了不同缺陷植入方式的增长趋势 图 图中横轴表示论文的发表年份, 纵轴表示对 应年份中的不同缺陷类型评测对象的数量统计 其中 植入缺陷 是指该论文只使用了包含人工植