基于信息检索的缺陷定位:问题、进展与挑战∗

郭肇强 , 周慧聪 , 刘释然 , 李言辉 , 陈 林 , 周毓明 , 徐宝文

1(计算机软件新技术国家重点实验室(南京大学),江苏 南京 210023)2(南京大学 计算机科学与技术系,江苏 南京 210023)

软件缺陷(software bug)是伴随软件产品整个生命周期的产物.特别对于大型软件,由于其复杂的结构和众多的开发者,缺陷不可避免地在开发过程中被引入.软件缺陷的存在,极大地降低了软件质量并且增加了软件的维护成本,严重的缺陷可能会给企业造成经济损失甚至对人的生命安全造成威胁.为了提升软件的质量,软件产品要在不断更新换代或者版本更迭中对已经发现的缺陷进行清除.从历史数据来看,对缺陷的清除工作消耗了接近一半的软件开发和维护成本[1].因此,在学术界有大量的研究者致力于缺陷相关(包括但不限于缺陷预测[2,3]、缺陷定位[4,5]和缺陷修复[6]等)的研究.其中,非常重要并且耗费时间和精力的一个任务是对缺陷进行定位,即找出产生该缺陷的软件实体(例如源文件).

当软件中的缺陷被发现时,根据缺陷产生时的软件状况,用户或者软件系统会记录缺陷相关的信息,并且生成一份半结构化的缺陷报告上传到缺陷追踪系统上[7].软件维护人员对缺陷的修复工作始于阅读缺陷报告,在理解缺陷的基础上,他们从代码库中查找与缺陷报告描述内容相关的代码实体进行审查,直至找出产生该缺陷的位置.值得注意的是:一个在实际开发项目通常包含成百上千甚至更多的源文件,手工从其中找出与缺陷相关的那极小部分代码是十分困难的.为此,开发人员急需借助于缺陷自动定位工具来辅助他们查找产生缺陷位置.

为了帮助开发人员快速找到产生缺陷的位置,研究者们提出了多种自动化的缺陷定位(bug localization,简称BL)解决方法.现有的解决方法可以根据是否需要执行测试用例划分为动态缺陷定位方法和静态缺陷定位方法.其中,动态缺陷定位方法要运行被测程序来收集程序执行的动态信息(包括执行路径和结果等),根据这些信息来定位缺陷语句在代码中的可疑位置.这类方法的主流思路被称为基于程序频谱的缺陷定位[4].由于直接运行目标程序,这类方法通常可以在较细的粒度上对缺陷进行定位,但是需要消耗执行程序的时间和资源成本.因此,这类方法有助于对代码进行调试.而静态缺陷定位方法不需要直接运行被测程序,这类方法主要分析代码和缺陷报告中的静态信息(包括文本、代码实体等),然后计算每个代码实体(源文件)和报告中的静态信息的相似度分值,最后根据得分将可疑的代码实体推荐给开发者.静态方法的优势在于使用简单,成本低廉(不需要运行代码).同时,它的不足是定位粒度较粗糙,通常在文件或者方法级别对缺陷进行定位.可以看出,这类方法适用于帮助开发者快速找到缺陷报告所描述的问题的相关位置.

近年来,静态缺陷定位研究工作的一类主流方法是基于信息检索的缺陷定位(information retrieval based bug localization,简称IRBL).该领域目前的研究重点在于改良IRBL 方法和完善IRBL 的评价体系两方面.截止2020 年3 月,已有20 多种(仍在增长)不同IRBL 方法和多种不同的评价指标被提出.从现有研究结果来看,IRBL方法在实验评估中已经取得了较高的性能.然而,由于现实中不同项目代码的结构和风格存在差异性,并且收到的缺陷报告内容质量参差不齐,目前的IRBL 方法仍然存在局限性,在现实的实践应用中仍然面临一些挑战.

(1) 方法所用的特征由人工设计,对目标项目依赖高,在其他项目上迁移性能较差;

(2) 目前,这些方法仅在实验评估中取得较好性能分数,但是由于各自实验设置的差异性,开发者无法准确判断哪一种方法最具有实用性.因此,这些方法在生产实践中的表现结果未知;

(3) 现有方法仅仅给开发者推荐出与缺陷有关的代码文件列表,没有包含任何有助于定位的提示信息.

值得注意的是,目前学术界已有多份综述性的工作[4,8-12]对缺陷定位领域的技术研究进行总结.这些工作对多种特定类型的缺陷定位技术进行了整理和归纳,包括基于程序频谱的缺陷定位技术[4]、基于程序变异的缺陷定位技术[12]等.但是据我们所知,还没有一项工作对IRBL 这种特定类型的缺陷定位方向进行总结(截止2020 年3 月).由于对IRBL 研究的论文体量已经较为庞大并且是一类热门的研究方向,为了弥补这一空白,同时方便后续相关研究工作的进行,本文首次对近10 年来IRBL 的研究历史进行回顾,对现有的成果进行分类介绍和总结,并在此基础上指出该领域面临的挑战.

本文在第1 节概述主要的研究问题.第2 节说明本综述的文献检索方式和文献汇总信息.然后,分别在第3节和第4 节从模型改良和模型评估两个方面介绍近年的研究进展.在第5 节分类别地介绍缺陷定位领域的其他研究方法.在第6 节分析IRBL 领域的研究所面临的挑战.最后,在第7 节总结本文的内容.

1 研究问题

1.1 IRBL概要介绍

信息检索技术早期被用来在代码中进行概念/特征定位(不同文献中的术语略有差别:concept location[13-15],feature location[16-18]或者concern localization[19-22])任务,其目的是从代码库中找出与特定功能相关的代码.后来演变为使用信息检索技术对缺陷进行定位(IRBL),并成为目前主流的静态缺陷定位研究方法.具体来说,程序中的特征是指能够被开发者感知或者看见的功能,其中,那些想要被抛弃并且被移除的“功能”便可以看作是一种特殊的特征(即缺陷).特征定位是指从项目中找出具有指定特征的那部分源代码.因此,对于要在程序中抛弃并移除的“功能”的定位,便逐步变成现有的基于信息检索的缺陷定位.

IRBL 方法关注的对象是缺陷报告和软件源码.从技术角度看,IRBL 方法将缺陷定位任务看作是进行信息检索(IR)的过程.Rao 等人[23]在2011 年总结了信息检索领域的IR 术语与软件工程领域在缺陷定位时所用术语的对照关系如表1 所示.据此,IRBL 任务执行过程可以描述如下:IRBL 模型将缺陷报告看作查询(query),将报告中的文本进行分词处理组成查询语句.同时,将项目源码看作文档库(documents),对每份源文件进行预处理,构造出一个语料库.当收到缺陷报告时,从报告中构建查询语句并在文档库中检索(retrieval),根据查询语句与每个文档的相似度通过索引(index)将所有文档降序排列后反馈给开发者.在结果列表中,包含缺陷的文件(buggy files)尽可能排列在靠前的位置.开发者按照列表顺序对代码进行审查,可以在花费较少的工作量的情况下找到有缺陷的源文件,从而加速缺陷定位的进程.

Table 1 Parallels between IR terminology and the more traditional SE terminology表1 IR 术语与传统软件工程术语的对照关系

IRBL 方法能够获得众多研究者和软件开发者的关注主要得益于这类方法在应用时具有以下两点优势.

(1) 外部依赖少[24-27].相比于动态定位,技术静态技术不需要执行测试用例来触发缺陷,并且不需要工作在可运行的目标软件系统中,只需要从源代码和缺陷报告中收集信息即可进行定位.因此,它们具备使用简单的特点,从而可以应用于软件开发或维护过程的任何阶段;

(2) 计算成本低[24,27].IRBL 方法对源码文档的排序的主要依据是缺陷报告与文档之间的文本相似度,这部分分值的计算对现在的机器来说是十分简单,通常可以快速给出排序结果.因而这类方法具备反馈迅速的特点,所以在应用时的用户体验良好.而动态方法通常需要执行目标程序,实际响应时间和计算成本取决于目标程序的复杂程度.

1.2 IRBL方法流程

本小节对IRBL 方法的流程进行细致描述.综合该领域的多个优秀的研究工作[24,25,28-32],IRBL 方法的流程主要包含建立语料库、构建索引、抽取特征、构建查询以及检索排序这5 个基本步骤,如图1 所示.

(1) 建立语料库.对代码库中的每个源代码文件的文本进行分词,同时对分好的词汇进行预处理,主要包括去除关键词(例如“int”“public”等)、去除停用词(例如“a”“the”等)、词根还原(例如,“delegating”还原为“delegate”)、拆分复合词(例如,“TypeDeclaration”分为“type”和“declaration”)等.处理完成之后,每个源文件对应一组词汇,所有源文件构成了整个项目的语料库;

(2) 构建索引.为语料库中的所有源代码文件构建索引,模型可以在后续步骤中根据索引信息找到指定文件,并对这些文件根据相似度得分进行排序;

(3) 抽取特征.从目标项目中抽取有利于缺陷定位的特征信息(例如版本历史信息、堆栈信息等).这些特征信息会在第(5)步中集成到检索模型用于优化排序结果;

(4) 构建查询.IRBL 方法将缺陷报告当作一条查询语句.使用步骤(1)中的方法对缺陷报告中的标题和描述进行数据预处理,可以获得该缺陷报告对应的一组词汇;

(5) 检索和排序.使用一种IR 模型(例如VSM[28],LSI[33],SUM[23],LDA[34]等)进行建模,并利用步骤(3)中的特征优化模型,对建立好索引的语料库计算查询语句和每个源代码文件之间的相似程度(例如文本相似度),然后按照相似度得分高低对这些源代码文件进行降序排序.

经过上述5 个步骤,IRBL 模型会对每份缺陷报告输出一份排序列表.需要说明的是:除非代码版本更迭导致源文件内容更新,否则步骤(1)和步骤(2)通常只需要执行一次,而步骤(3)～步骤(5)在每次收到新的缺陷报告后都需要执行.

1.3 IRBL研究内容

目前,IRBL 领域的研究重点是模型改良和模型评估,以下分别从两方面列出IRBL 研究面临的主要挑战并和对应的研究内容.具体内容将在第3 节和第4 节详细介绍.

1.3.1 模型改良(见第3 节)

IR 模型最初是为检索非结构化的自然语言文本设计的,因此适合处理纯自然语言文本的应用.对于缺陷定位应用来说,不论是软件库中的代码文件还是软件平台收到的缺陷报告,其中都包含着丰富的结构信息.当IR模型被直接应用到具有特定结构化信息的软件代码库检索时,会遇到来自以下两方面挑战.

(1) 有用特征使用不完全.对源代码来说,有大量可以使用的附加特征(如提交历史[32]、代码结构[24,25,30,31]等)可以辅助定位缺陷.对缺陷报告来说,其中包含了标题(title)和描述(description)两部分内容,每部分中包含的词汇的权重是有差别的[35];

(2) 无用信息过滤不充分.源代码中的关键字是一种干扰词汇[24,28],例如关键字“public”,“class”和“int”等等.这类词汇对于文本语义没有任何帮助,并且几乎会出现在所有的代码文件中.代码中的部分注释组成另一类干扰词汇,例如,代码文件的许可证注释(license comments)通常和文档语义无关.这类词汇会影响检索模型的效果.

上述挑战使得IRRL 模型的定位性能低下.为了解决上述挑战,IRBL 领域研究的一个重点在于模型改良.即不断对模型进行修改以提高其定位准确性.可行的探索方向是挑选较好的IR 模型;从各个角度分析代码和缺陷报告的特征信息并将其集成到IR 模型中.现有研究人员已经挖掘出包括版本历史、代码结构、堆栈踪迹等多种重要的特征信息(见图1 中点划线标明的特征工程路径);提升缺陷报告的质量;使用深度学习技术自动提取特征等.

1.3.2 模型评估(见第4 节)

IRBL 方法的输出结果是一个排序列表,因此在对这类方法进行性能评估时,使用的是常用的3 个排序指标Top@K,MRR,MAP.这些指标在评估纯排序结果时是客观公平和有效的,然而在实际使用过程中是否有效,不仅仅取决于排序结果,还与待排序的对象有关.在评估模型时主要有以下3 个方面挑战.

(1) 评估指标不全面.单纯的排序指标并不能得到全面的评价结果.例如:对于缺陷定位来说,开发人员要花费工作量在排序结果中依次审查代码文件[36,37];

(2) 测试项目不充足.要取得可靠的评估结果,必须要在大量的项目上对模型进行评估.仅在个别项目上的评价结果,在更多项目上测试其泛化性能;

(3) 实验过程不统一.为了对比不同方法的性能,需要在统一的实验配置下进行实验.然而在不同研究者的实验设置中存在的差异,使得研究者很难得到真实客观的对比结果.

上述挑战使得IRBL 模型的良好表现只停留在实验阶段而无法在现实项目中被广泛应用.为了解决上述挑战,该领域的另一个研究重点是更加科学全面地评估IRBL 模型,即使用更加合理的评估指标[36]、更加丰富的数据集[26,38,39]和统一的实验设置对模型进行评估.

2 文献检索

2.1 文献筛选与检索

IRBL 方法一直是缺陷定位领域的热点研究问题.近年来,大量的研究工作集中在该领域,并不断地对定位方法和评价体系进行改善.为了对该问题进行系统的分析、总结和比较,本文的参考文献力图覆盖近10 年来与IRBL 相关的主要研究工作,同时包含缺陷定位领域的其他相关技术的主要文献.具体来说,本文使用以下的步骤来进行相关文献的检索和筛选.

(1) 检索目标:谷歌学术搜索引擎(Google scholar)、DBLP Computer Science Bibliography、ACM Digital Library、IEEE Xplore Digital Library 以及Springer Link Online Library 等论文数据库.检索内容主要包括软件工程-系统软件-程序设计语言方向的国际一流会议(ESEC/FSE,ICSE,ASE 等)和一流期刊(TSE,EMSE,IST 等)以及其他重要的会议和期刊如MSR,SIGIR,WCRE 等录用的文章;

(2) 检索关键词:包括“bug localization”“locating bugs”“information retrieval”和“fault localization”等以及相近的主题关键词如“text retrieval”;

(3) 检索起止时间:2000 年～2019 年之间的文献.需要说明的是:2010 年以前关于IRBL 的相关研究相对较少,所以重点关注2010 年及其之后的文献;

(4) 文献审查:首先对检索出来的文献进行人工筛选,去除不符合研究主题的文献;然后检查选中论文中的参考文献列表以防遗漏掉未检索到的文献;最后,在第2.2 节中对所选文献进行汇总.

2.2 历史文献的汇总

经过文献的检索与筛选,本文收集了基于信息检索的缺陷定位领域中近10 年来的学术论文共82 篇.这些研究论文将会按照种类分别在第3 节和第4 节进行详细介绍.对于其他种类的缺陷定位相关技术,我们在第5节中对其进行分类和介绍.

表2 列出了基于信息检索技术的相关文献的详细列表.可以看出:在CCF 划分的软件工程领域A 类会议上有15 篇,期刊上有6 篇.这表明IRBL 研究是软件工程领域一个比较活跃的研究方向.图2 展示了10 年来IRBL领域的研究论文发表的数量分布情况.从图中可以看出,该领域的逐年论文发表数量呈现出一个波动上升的趋势.这说明对IRBL 这个领域正越来越受到研究者的重视.在2019 年,相关论文数量有所下降但仍然保持着较高的活跃度.

Table 2 List of related literature on IR-based bug localization researches表2 基于信息检索的缺陷定位研究的相关文献列表

3 IRBL 模型的改良

对IRBL 模型的改良研究在不同研究阶段有不同的侧重点.图3 展示了基于信息检索的缺陷定位方法从2010 年以来的模型改良趋势和侧重点.同时,我们在表3 中列出了现有的代表性的IRBL 模型汇总比较信息.根据对现有研究的汇总,我们得出IRBL 领域的研究侧重点主要包含以下4 个方面.

(1) 更换检索模型.早在2010 年及以前,由于IR 技术刚刚被应用到缺陷定位领域,研究者的研究重点是尝试使用不同的IR 模型对缺陷定位任务进行建模来找出该领域比较合适的IR 模型(例如VSM,LDA,SUM,LSI 等);

(2) 使用特征分析.约从2011 年开始,研究者们发现,单纯使用IR 模型定位缺陷的性能低下很难满足实际的应用需求.研究者们发现:除了文本相似度之外,软件中的其他特征也可以帮助定位缺陷.所以,这一阶段的研究者们主要集中在挖掘软件项目中与缺陷有关的特有特征(例如项目版本历史、缺陷堆栈等),并结合使用这些特征和IR 模型来提升缺陷定位在测试项目上的性能;

(3) 进行查询重构.作为查询语句的缺陷报告是由不同的人员提交的,所以质量参差不齐.这些低质量的查询导致很多IRBL 模型表现较差,因而在2013 年后出现一些研究者着重于对查询进行重构,以改善现有IRBL 模型的查询准确性;

(4) 应用深度学习.随着深度学习技术的发展,从2017 年起,不少研究者开始尝试使用深度学习模型(如卷积神经网络CNN)对特征进行自动提取,然后结合信息检索技术对缺陷进行定位.

Table 3 Summary of representative IR-based bug localization models表3 基于信息检索的缺陷定位代表性模型汇总

Table 3 Summary of representative IR-based bug localization models (Continued)表3 基于信息检索的缺陷定位代表性模型汇总(续)

3.1 更换检索模型

在信息检索领域有很多模型,其中最常见的包括向量空间模型(vector space model,简称VSM)[106]、潜在语义索引模型(latent semantic index,简称LSI)[107]、隐狄利克雷分布模型(latent Dirichlet allocation,简称LDA)[108]等等.经过多年研究,IRBL 领域的方法中所用的检索模型已经涵盖了上述所有以及其他更多的IR 模型.

3.1.1 VSM 模型

VSM 是将自然语言文档库转化为一个字词-文件矩阵的向量模型.矩阵的每一行代表一个单词在不同文件中的权重值(可以通过TF.IDF[109]来表示),每一列代表一个文档所对应的特征向量.在字词矩阵的基础上,我们可以很容易地通过向量距离计算来衡量不同文档之间的相似性.因此,在IRBL 领域现有的方法中,VSM 和它的变体是使用最广泛的IR 模型.

在现有的研究中,大约有超过半数的IRBL 方法[25,28,30-32,35,47,50,63,68,74,79,80,90,92]都使用VSM 模型来进行建模.以下是该模型的相关应用.

2009 年,Gay 等人[110]提出一个使用相关反馈(relevance feedback)机制的方法来提升概念定位的结果.在他们的方法中,最先明确使用VSM 模型来进行检索.2012 年,Zhou 等人[28]指出,传统VSM 模型更倾向于将长度较短的文档排在前面,而已有研究表明,长度较大的文档包含缺陷的可能更高.基于这点认识,他们对VSM 模型进行改进,提出了rVSM 模型,其中,将文档长度作为一个权重参数.后续有多个研究工作(Wong 等人[30]、Rahman等人[103]、Youm[74]等)均是在rVSM 模型之上构建新的IRBL 方法.2014 年,Wang 等人[50]设计了基于搜索的引擎VSMcomposite,该引擎使用遗传算法(GA)将各种不同的VSM 变体(即,向量元素的计算方式不同)模型进行组合,得到新的近似最优组合模型来进行缺陷定位.

3.1.2 LSI 模型

LSI 是一种实用的主题模型[107,111],它是在传统的VSM 模型基础上进行改良后得到的.LSI 利用奇异值分解(singular value decomposition,简称SVD)将词汇和文本映射到一个新的空间来表示文档矩阵之间的潜在语义关系.它的优势是可以解决词语中出现的同义词和多义词对结果的影响,这些词汇是无法被VSM 模型识别处理的.然而,它的缺点是需要进行高阶矩阵运算来计算查询字段和每篇文档的相似度,所以运行速度慢于VSM 模型.其次,在使用SVD 时需要假设数据的分布是正态分布,然而类似词频的统计数据往往不能符合这个条件.经过对文献的整理,我们发现:在IRBL 领域LSI 是最早被用来进行特征/缺陷定位的IR 模型,并且只活跃在研究早期(2010 年以前).近年来,几乎已经没有方法使用LSI 作为IR 模型来进行缺陷定位.以下是该模型的相关应用.

2004 年,Marcus 等人[13]最先将LSI 模型应用到概念定位领域中.2006 年,Poshyvanyk 等人[16]将特征定位视为一个决策问题,他们使用LSI 模型和基于场景的事件概率排序两种技术来强化定位结果.随后,他们在2007 年又在LSI 模型基础上提出了PROMESIR 模型[18]进行特征定位.同年,Liu 等人[17]将LSI 模型和代码执行踪迹以及代码中的注释和标识符信息相结合来提升定位性能.考虑到现有技术没有使用到软件仓库的动态特性,Rao等人[87]在2015 年提出了一个可以随着数据演化增量更新LSA 模型参数的定位框架.

3.1.3 LDA 模型

LDA 是一种生成式的统计主题模型,同时也是一种典型的词袋模型.它将一篇文档看成是词语之间没有先后顺序和上下文关联的一组词语集合,文档中的这些词语属于多个主题,并且每个词语都由其中一个主题生成.LDA 模型在模块化和可扩展方面强于LSI 模型.与此同时,它在基于主题模型的信息检索应用上十分有效.在IRBL 领域里,LDA 模型也是在早期研究中就被应用到IRBL 领域中,并且在近年来仍有部分研究关注于改良LDA 模型.以下是该模型的相关应用.

2008 年,Lukins 等人[27]就明确提出使用LDA 模型检索源代码进行缺陷定位.在2010 年,他们再次使用LDA模型来构建IRBL 方法[3].他们得出结论,基于LDA 的缺陷定位方法的定位准确度与目标项目尺寸或者源代码的稳定性没有显著关联.因此,LDA 有广泛的应用前景.在2011 年时,Nguyen 等人[49]提出了基于LDA 主题模型的新方法BugScout,使得缺陷定位效果有明显提升.2018 年,Wang 等人[98]在他们的方法STMLocator 中使用了LDA 模型,并且利用代码库的历史信息来进行有监督的学习,进一步发掘了LDA 模型的性能.

3.1.4 其他IR 模型

除了上述3 种主流的IR 模型之外,还有其他一些模型也被某些研究者用来进行缺陷定位.

2010 年,通过聚集和挖掘被相同位置共同引用的历史缺陷报告,Chen 等人[85,112]提出一个有效的使用协同位置收缩(co-location shrinkage,简称CS)技术的支持向量机模型(CS-SVM)来检索潜在的缺陷位置.2011 年,Rao等人[23]使用平滑一元模型(smoothed unigram model,简称SUM)进行缺陷定位工作.在他们的实验结果中,SUM的缺陷定位性能比VSM,LSI 和LDA 都要优秀.2012 年,Sisman 等人[60]使用DFR 偏离随机性(divergence from randomness,简称DFR)模型进行缺陷定位.该模型会根据文档特征概率与纯非判别随机分布的差异,来评估文档对查询的恰当性.

除了手动构建IR 模型,还有一些研究使用了现成的信息检索工具.例如,Saha 等人[24]在他们的方法BLUiR中使用了Indri[113],Kilinc 等人[90]和Rahman 等人[35]则使用Apache Luence 作为他们方法的检索模型.

3.2 使用特征分析

直接应用IR 模型进行检索很难得到令人满意的结果,因此需要进一步进行特征分析来改良IRBL 模型.代码库和缺陷报告都不是由纯自然语言组成的文本,它们具有一些领域相关的结构化信息和特征.对这些特征进行挖掘,可以在一定程度上提升检索结果的准确性.综合现有文献的研究,我们发现对,代码库和缺陷报告提取的特征主要包括版本历史、相似报告、代码结构、堆栈踪迹以及其他一些不常用的特征.本小节从提取特征的角度来介绍现有研究如何通过对特征进行细致地挖掘来提升定位模型的性能.

3.2.1 版本历史

软件项目在演化过程中会通过版本更迭来实现对项目的更新和完善(例如修复缺陷、添加新功能等),每一次变更都会向代码库中添加丰富的历史信息(例如日志信息、文件变动信息等).与此同时,多数缺陷正是在代码变动的过程中因为开发人员主观疏忽或者是客观设计不合理而被引入到项目中,所以分析版本这些历史信息有利于为缺陷定位或者预测任务带来一些提示性的帮助.在现有的IRBL 方法中,很多方法已经将版本历史信息作为一个重要的特征组件来提升方法的性能.版本历史特征的应用示例过程如图4 所示.

2010 年,Chen 等人[85,112]利用历史缺陷报告和历史被修复的模块信息为新收到的缺陷寻找可能的位置,其中特别利用了缺陷报告之间的共位置关系.在他们的方法中,如果两个缺陷报告的修复模块相同,那么认为这两个缺陷报告有共位置关系.

2012 年,Sisman 等人[60]挖掘版本历史时应用到以下两点先验知识:(1) 在短期内被多次提交的修改很可能会包含缺陷;(2) 历史上包含缺陷的文件在之后版本中可能仍然有缺陷.其中,先验知识(1)也被应用在Rahman等人[103]的方法中.相比前两个方法,Wang 等人[31]和Youm 等人[74]考虑到新发现的缺陷通常是由最新的提交引入而非远古提交,因此在他们的方法中,只考虑近期的版本历史而完全丢弃距提交的新缺陷报告超过k天的版本历史信息.

2013 年,Tantithamthavorn 等人[29]挖掘代码文件之间的共同变更历史信息调整现有方法BugLocator[28]的结果.挖掘步骤如下:首先找出先前所有被修复的文件,并根据其所属的变更构建一个共同变更矩阵,矩阵中的元素代表两个文件之间的共同变更一致性;然后,对BugLocator 生成的列表从共同变更矩阵寻找一致性较高的文件提升它们的排名.相比之下,共同变更历史信息可以对原方法的结果产生显著提升.

2016 年,Wen 等人[32]在产生缺陷之前版本历史中,把每个变更块(change hunk,包括变更行的内容、变更日志等)索引为一个文档,并从这个文档构建自然语言和代码实体两个语料库.此外,提取每个源文件的缺陷修复历史后计算一个加强得分,并将其用作指示源文件包含缺陷可疑度的另一个特征.他们的定位模型不仅可以在文件级别定位缺陷,同时首次提出在变更级别定位缺陷,即定位引入缺陷的变更.这可以帮助开发人员更容易找出产生缺陷的原因.

3.2.2 相似报告

相似缺陷报告是另一类重要的辅助特征.一个直观的理解是:若两个缺陷报告在描述上具有较高的相似度,那么这两个报告所对应的缺陷文件有很大概率有重叠的部分甚至完全一致.在这个基础上,可以先收集已经定位到产生缺陷位置(例如源文件)的相似缺陷报告,适当增加这些位置的可疑度分值,可以在一定程度上提升IRBL 结果的性能.相似报告特征的应用示例过程如图5 所示.

2012 年,Zhou 等人[28]在他们的方法BugLocator 中使用到了相似缺陷报告特征.对于新收到缺陷报告,他们首先在rVSM 模型的基础上计算出该缺陷与每个源文件的文本相似度分值;然后计算该报告与历史上已经解决的缺陷报告之间的相似度;接着,对历史上有缺陷的文件根据其对应的历史缺陷报告进行加权,得到这部分文件的历史特征分数;最后结合两部分的分数,将所有文件倒序排列作为最终的推荐结果.

Zhou 等人使用相似缺陷报告特征的方法在后续多个研究工作中被应用.Saha 等人[24]在BLUiR 变体中、Wong[30]等人在BRTracer 变体中、Wang 等人在AmaLgam[31]和改良版AmaLgam+[80]中都以同样的方式使用到了相似缺陷报告信息.2017 年,Youm 等人[74]在 BugLocator 的基础上用到了历史缺陷报告中的评论信息(comment)来强化定位方法.

3.2.3 堆栈踪迹

堆栈踪迹是缺陷产生时代码执行的异常信息.这些信息是高度结构化的,其中包含了异常的类型(例如空指针异常和地址超界等)和出错代码所执行的路径信息(例如代码行、类名、方法名).因为缺陷所在的位置很可能在于这个出错路径上,所以堆栈信息对于开发人员手动进行缺陷定位是十分重要的.而在研究定位工具时,也可以通过提取堆栈中的信息(例如出错的类名)进一步强化工具的定位准确度.

堆栈踪迹特征的应用示例过程如图6 所示.

2014 年,Moreno 等人[25]考虑将堆栈踪迹信息应用到他们的方法Lobster 中.他们使用缺陷报告中的堆栈踪迹和软件源码中的程序依赖图来寻找在结构上相似的代码元素.具体说:对于给定的堆栈踪迹和代码元素,他们之间的结构相似性被定义为堆栈踪迹中元素和代码中元素的最小距离.同年,Wong 等人[30]使用正则表达式从缺陷报告的堆栈中提取所有的文件名以及对应的方法.在得到一组可疑的文件集合后,将上述文件对应方法中直接使用到的类所对应的文件也加入到可疑文件集合,最后通过提高对这些文件在结果中的排名来改善定位结果.2017 年,Youm 等人[74]在他们的方法BLIA 中集成了Wong 等人对堆栈踪迹的处理方法.

2016 年,Wang 等人[80]在他们的改良方法AmaLgam+使用了堆栈踪迹特征.他们提出一个直观假设:若某个类的引用距离堆栈顶部越近(出错位置),那么这个引用所在的文件越可能包含该缺陷.因此,他们设计了一个堆栈分数来度量堆栈中出现的每个文件的可疑程度.对每缺陷报告中的堆栈,他们首先按序提取出所有文件名并进行去重处理,然后使用每个文件排名的倒数作为该文件与缺陷报告在堆栈上的可疑程度.

2018 年,Rahman 等人[35]利用堆栈踪迹来重新查询.他们从堆栈踪迹中提取代码实体(类名和方法名).根据执行顺序构造出权重图,并在图上面应用PageRank 算法计算出每个代码实体的权重来重新构造查询语句.

3.2.4 代码结构

项目中的源代码是一种结构化文本,它的内容是由各种不同的代码实体(例如类名、方法名等)组成.直接将它们看作自然语言文本处理会丢失其中的结构化信息,会导致定位结果准确率低下.合理利用这些结构特征,可以帮助进一步提升自动工具的准确性.代码结构特征的应用示例过程如图7 所示.

2013 年,Saha 等人[24]在设计模型时首先考虑到代码结构特征.对于代码库来说,他们使用Eclipse JDT 解析源代码的AST 树,并提取其中的4 种代码实体(类名、方法名、变量名和注释)信息;对于缺陷报告,他们分别使用标题和描述构建两种查询.上述代码实体和查询共有8 种不同的组合方式,他们分别计算每种组合的分数,然后将所有组合的分数相加作为某个源文件的最终分数.最后,他们依据该分数向开发者推荐有缺陷的文件.

2016 年,Kilinc 等人[90]提出了BugCatcher 方法,该方法首先使用基础的检索方法对源代码进行检索获得一个排序结果;然后,从代码中提取类名、方法名和注释分别建立索引,并且根据这3 类信息对首次结果进行重排;最后使用一种用到重新索引的缩小范围技术计算最终结果.同年,Wen 等人[32]提出了Locus 方法.该方法对自然语言和代码实体分别构建语料库和查询语句,将两个查询结果组合起来输出变更块(change hunk)的排序,并在此基础上选出可以的文件或者变更.

2018 年,Dilshener 等人[79]提出一种不需要历史信息,仅使用结构和堆栈信息的缺陷定位方法.同年,Swe 等人[99]将代码结构细分为类名、方法名和变量名分别处理来避免代码文件过大对结果带来的影响.Rath 等人[97]研究了缺陷报告中的结构信息对IRBL 方法的影响.他们的结果表明:堆栈踪迹会倾向于降低缺陷定位的性能,并且需要额外的处理.

3.2.5 其他特征

除了上述4 种被大量使用的特征之外,还有一些现有研究[30,74,79,80,103]挖掘了源代码和缺陷报告中的其他隐藏的对缺陷定位有利特征.这些工作也在一定的场景下改进了IRBL 方法,并提升了它们的定位性能.

2014 年,Wong 等人[30]考虑到缺陷通常发生在源文件中的小部分代码里,而某些源文件的尺寸很大,会严重降低VSM 模型的准确性,因此,他们将每个的源文件按照某一阈值(例如100 行代码)分为若干大小相等片段,并在此基础上计算每个片段与缺陷报告的相似性.然后,用得分最高的片段代表该文件.分段操作消除了文件大小对定位模型的影响.该特征在2017 年也被Youm 等人[74]应用在他们的方法BLIA 中.

在某些缺陷报告中会记录代码库里出现的源文件名或者方法名等代码实体信息,这些信息往往与缺陷关联密切.因此,Rahman 等人[103](在2015 年)和Dilshener[79](在2018 年)在他们的定位方法中提高了这些出现在缺陷报告中的代码实体所对应的源文件(或者源方法)所在的最终排序列表中的优先级来获取更加可靠的结果.

2016 年,Wang 等人[80]提出了使用缺陷报告中的报告者信息来提升定位性能的方法AmaLgam+.他们的直观理解是,一个报告者很可能去报告与相同/相似的代码组件有关的缺陷.因此,当受到新的缺陷报告时,查看该报告者之前提交的缺陷报告和对应的包含缺陷的文件对于新缺陷的定位有帮助.

3.3 进行查询重构

在一定程度上来说,由于大量研究已经对代码库和缺陷报告中的相关特征进行了比较充分的挖掘,很难再提取新的特征来改良IRBL 方法.研究者从改善查询的角度提出了查询重构(query reformulation,简称QR)的策略来提升性能.这类策略的一个优势是独立于IRBL 方法本身,可以作为一个预处理步骤集成到现有的IRBL 方法中,因此它的可移植性较好.查询重构的应用场景如图8 所示.开发者首先使用自动方法构建初始查询并获取一个结果列表.当他们在排名靠前的代码中没有找到缺陷时,就请求进行查询重构重新获取推荐结果.

需要重构的对象是用来构建查询语句的缺陷报告,因此,对缺陷报告的组成部分及特征有全面的理解十分重要.在实际使用过程中,开发者也是需要根据初始查询的反馈结果来决定是否需要使用查询重构策略.因此,对缺陷报告的分析是进行查询重构的前序工作.根据研究的前后承接关系,我们将这部分相关内容分为缺陷报告分析和查询重构策略两个部分来介绍.

3.3.1 缺陷报告分析

2008 年,Bettenburg 等人[70,114]对现实项目中(例如Apache)的开发者和用户进行一项调研.他们发现,用户提交的报告内容与开发者希望收到的信息之间不匹配.开发者想要得到的信息是复现步骤、错误堆栈和测试用例等,然而用户很难提供这些信息.为了解决这个问题,他们提出一个原型工具CUEZILLA 来测量缺陷报告的质量,并且能够向用户推荐填写缺陷的信息来提升报告质量.

2014 年,Kochhar 等人[48]总结了会影响缺陷定位有效性的潜在偏好:

1) 被错误分类的缺陷报告.被标记为缺陷的问题报告并非总是由缺陷引起,也包含了文档更新、代码重构等;

2) 已经可定位的缺陷报告.缺陷报告中可能已经指出了有缺陷的程序文件,没有必要对这些报告使用缺陷定位工具;

3) 不正确的真实值.在修复缺陷的更新提交中被修改的文件中,可能并非所有文件都与这个缺陷有关.

他们的实验结果表明,偏好(2)对IRBL 有效性有显著影响,因此应当在后续研究中被纠正.

2018 年,Mills 等人[53]对缺陷报告进行调研,他们发现,缺陷报告中的大多数词汇的确可以用来构建有效查询语句,从而使得在没有辅助查询扩展的情况下,可以成功进行缺陷定位.在此基础上,他们设计了一种遗传算法(GA)来分析带有和不带有定位提示(localization hint,例如方法名)的缺陷报告文本,以获得一个接近最优的查询,该查询提高了缺陷报告在IRBL 应用中的潜力.然而在同年,Lawrie 等人[52]研究了缺陷报告在IRBL 中的价值.他们指出:GA 算法存在作弊(cheats)问题,因为GA 算法根据查询的性能评估值来产生优质的查询.然而在现实场景中,一个查询的性能评估值是未知的,因此不具备实用性.

2019 年,Rath 等人[84]着重分析了缺陷报告中结构化信息对IRBL 方法的影响.他们发现,缺陷报告中的堆栈踪迹信息更倾向于对缺陷定位结果产生负面影响,因此对包含这类信息的报告需要特别处理.与此同时,相比于只包含自然语言的缺陷报告,那些包含源代码信息的缺陷报告不仅可以提升BL 算法的性能,而且有助于开发人员更快找到缺陷位置.

3.3.2 查询重构策略

2013 年,Sisman[61]首先将查询重构策略应用到缺陷定位领域中.在不需要用户提供额外的输入信息的情况下,他们的QR 框架的工作原理是先进行一次初始查询得到相关的软件制品(artifact,例如文件)排名列表,然后从排名靠前的制品中抽取附加的词汇来扩充查询语句.

2017 年,Chaparro 等人在文献[40,46]中将缺陷报告的内容详细地划分为 OB(observed behavior),EB(expected behavior),S2R(step to reproduce)这3 个部分,他们使用启发式的规则识别和检测这3 部分内容,并发现多数缺陷报告中缺少EB 和S2R 这两部分内容.接着,他们在文献[51]中进行对比实验,发现使用OB 替代整个报告的内容来构造查询语句,是一种简单有效的方法来重构低质量的缺陷报告.在此基础上,Chaparro 等人[73]在2019 年了扩大了实验对象和数据集,发现使用OB 和报告标题的组合内容替代整份缺陷报告来定位能够达到更好的效果.

2018 年,Rahman 等人[35,42]提出使用一种上下文感知的查询重构方法BLZZARD.他们的重构方法对缺陷报告中的两类重要信息——堆栈踪迹和程序元素(例如类名、方法名等)分别构造踪迹图和文本图模型,对这两部分中的词汇进行建模.在构造好的图模型基础上,使用PageRank 算法对图中的词汇进行加权,并根据权重来选取加入查询语句的词汇.

2019 年,Kim等人[102]提出目前最新的自动查询重构方法.他们的方法包含3个组件:1) 缺陷报告扩展;2) 候选词提取;3) 查询扩展.首先,他们使用缺陷报告中的附件信息(attachment)扩展缺陷报告;然后,在提取候选词时,通过将情感词汇加入到停用词表来将它们移除,并且使用伪相关反馈的方式从源码中检索文件并移除噪音文件;最后,他们对检索到文件中的词汇加权,并选择权重较高的部分来扩展查询语句.

3.4 应用深度学习

随着深度学习技术的发展,近年来,研究者们将深度学习技术引入缺陷定位领域.相较于基于信息检索的缺陷定位只考虑了缺陷报告和源代码文本上的特征,基于深度学习的缺陷定位方法可以提取缺陷报告和源代码文件更深层和更高维的抽象特征.这类方法可以减少人为设计特征的工作量,同时也提高了缺陷定位的准确率.

2017 年,Lam 等人[55]将深度神经网络(DNN)与信息检索技术中的rVSM 相结合进行缺陷定位.首先,他们使用rVSM 收集缺陷报告和源代码文件之间文本相似性的特征;然后,他们用DNN 来学习缺陷报告中的术语,并将它们与源代码中潜在不同的代码字段关联起来.实验证明:深度神经网络和信息检索技术可以很好地相互补充,能够实现比单个模型更高的缺陷定位精度.

2018 年,Xiao 等人[64]提出一个深度学习方法,在字符级别解释缺陷报告,并使用语言模型来进行分析.该方法类似于机器翻译,首先将缺陷报告和源代码文件用字符表示,然后将结果传入到CNN 模型中进行卷积操作,最后把CNN 的结果应用在基于RNN 的编码器-解码器中进行缺陷定位.

同年,Xiao 等人[96]使用卷积神经网络和级联森林对语义信息和结构特征建模.首先,采用具有多个过滤器的卷积神经网络和具有多粒度扫描的随机森林集合,从缺陷报告和源文件中提取词向量的语义和结构特征;随后从级联森林进一步提取更深层次的特征,并观察缺陷报告与源代码文件之间的相关关系.

2019 年,Xiao 等人[77]提出使用词嵌入和强化的卷积神经网络来提升缺陷定位性能.他们使用词嵌入来表示缺陷报告和源文件中保留语义信息的单词,并使用不同的CNN 模型来提取它们的特征.Polisetty 等人[101]研究了基于深度学习的缺陷定位模型是否能够满足参与人员的需求,他们的结果表明:虽然深度学习模型比经典的机器学习模型表现得更好,但它们只能部分满足研究者实验中设定的采用标准.Huo 等人[69]提出了一种跨项目缺陷定位的深度迁移学习方法.使用他们所提出TRANP-CNN 方法,可以从源项目中提取出可转移的语义特征,充分利用目标项目中的标记数据进行有效的跨项目缺陷定位.

3.5 小 结

本节从更换检索模型、使用特征分析、进行查询重构和应用深度学习这4 个方面详细介绍了在改良IRBL模型近年的研究进展.下面简述主要发现:

(1) 相比于其他IR 模型,VSM 作为一种简单的IR 模型,能够在IRBL 的研究中获得较好的性能.因此,目前超过半数的IRBL 方法都使用VSM 或者VSM 的变体作为他们方法中IR 模型;

(2) 从代码库和缺陷报告中挖掘出的特征里,对提升缺陷定位方法性能十分有效的是版本历史、相似报告、代码结构和堆栈踪迹这4 种特征,并在大量研究中被以不同的方式集成到他们的IRBL 方法中;

(3) 查询重构是一种独立于具体定位方法的优化策略,因此,它可以作为一个预处理步骤集成在任何现有的IRBL 方法中,具有很好的可移植性;

(4) 将深度学习模型应用到基于信息检索的缺陷定位中,可以自动地从代码和缺陷报告中提取特征.最新的研究显示了深度学习模型在缺陷定位应用中十分有效.

4 IRBL 模型的评估

本节介绍IRBL 模型评估方向的研究进展,根据对现有文献的分类,主要从模型比较、评价指标和实验数据这3 个部分展开介绍.

4.1 模型比较

研究者在提出新的IRBL 方法时,会设计实验来验证新方法的有效性.然而通常的情况是,不同研究者在设计实验时不能够完全确保实验的一致性(即:与基准方法使用的实验设置是否一致,是否正确复现了基准方法)与合理性(即实验设置是否存在问题).这些因素可能会使得实验结果不能准确显示新方法的真实性能,从而误导后续的研究工作.

为了获得比较真实客观的实验结果,一些研究工作致力于设置公平的实验对已有定位方法或者IR 模型的效果进行比较和评估的实证研究,我们简称为模型比较研究.这类研究的好处在于以下3 个方面[89]:(1) 对研究者,帮助他们理解现有模型的优缺点和真实效果,并在此基础上研究更有效的定位方法;(2) 对缺陷定位编程人员,帮助他们理解如何更好地使用现有方法来达到理想的定位结果;(3) 对缺陷报告者来说,帮助他们在提交缺陷报告时填写对定位缺陷最有用的信息来加强缺陷定位的成功.

4.1.1 对不同参数性能的比较

2011 年,Thomas 等人[66]在超过8 000 个缺陷报告上实证调查了分类器参数(总共3 172 种参数设置)和不同分类器组合对缺陷定位的影响.他们主要得出两个结论:(1) 分类器的参数设置对性能有显著的影响;(2) 使用不同分类器组合的结果优于使用任意单独的分类器.

2018 年,Tantithamthavorn 等人[76]研究了IR 分类器的配置参数对方法级别缺陷定位的性能和工作量的影响.他们的主要结论如下:(1) 即使在分类结果的排序性能相似的情况下,不同的参数对分类结果的工作量有十分显著的影响;(2) 在方法级别表现较好的参数设置可以应用到文件级别,反之亦然.他们最后强调,在评估方法时应当考虑审查结果所花费工作量.

4.1.2 对不同模型性能的比较

2011 年,Wang 等人[19]在一个大型的Linux 内核数据集上比较了10 种不同IR 技术的关注点定位(concern localization)方法.他们的结果显示:(1) 简单的IR 模型(如VSM 和SUM)比复杂的模型(如LDA)定位效果要好;(2) 相同的IR 技术在不同系统上处理不同应用时的表现有差异;(3) 基于IR 的关注点定位技术在大型软件系统中和小型软件系统中一样有效;(4) 现有的IR 技术在处理软件语料库时,效果差于处理自然语言的语料库.

2015 年Alduailij 等人[89]使用统计推断比较3 种文本模型(VSM,LSI,LDA)在方法级别缺陷定位时的性能.他们得出结论是,VSM 是比较好的模型.接着,他们研究了额外参数对VSM 性能的影响,包括方法长度、查询长度、方法的文档注释以及缺陷报告中提及的产品名称和组件名称.他们发现,VSM 与大多数被测的参数正相关.

2018 年,Shi 等人[94]对混合缺陷定位方法(hybrid bug localization,即同时使用IR 相似度和附加特征的方法)进行研究.他们比较了8 种不同的LtR 技术在使用4 种归一化方法时的性能表现.他们发现,LtR 的表现好于最新的BLUiR[24]和AmaLgam 方法[31].

4.1.3 对不同实验方案的比较

一些研究者指出:在进行模型比较的实验验证过程中存在不合理的设置,这些不合理的设置会影响实验结果的准确性.2018 年,Kim 等人[41]发现,现有研究的实验数据集中包含一些non-buggy 文件(例如测试文件).他们指出:将这些文件包含在数据集中会影响现有技术的可靠性,所以在以后实验方案中应当被去掉.根据他们在排除测试文件的数据集上的实验结果,被多数研究者作为基准方法的BLUiR[24]的实际定位效果并没有原文实验中表现得那么好.Kim 等人[41]指出的不合理的实验方案在得到认同,例如,Lee 等人[39]在他们的实证研究中排除了数据集中的测试文件.

4.2 评价指标

评价指标是度量方法有效性的重要依据.针对不同模型的输出结果,研究者使用多种类型的指标对结果进行评价.本节从排序性能、分类性能和工作量这3 个角度介绍IRBL 领域的评价指标.

4.2.1 评估排序性能的指标

目前,大多数IRBL 领域的研究都将缺陷定位视为一个排序任务,对于给定的缺陷报告,定位方法会输出一个根据其包含缺陷可能性从大到小排序的文件列表.因此,大量研究使用排序指标来评价IRBL 方法的性能.表4对排序性能评估指标的计算方法和使用情况进行了汇总.这些指标的具体含义如下.

(1) Top@K.表示对缺陷定位方法生成的推荐列表中前k个文件进行审查时缺陷定位方法定位成功的概率.特别地,给定一个待定位的缺陷报告,如果缺陷定位方法生成的推荐列表的前k个源代码文件中至少有一个与给定的缺陷报告相关,则认为定位成功;

(2)MRR(mean reciprocal rank).测量的是缺陷定位方法定位到的首个与缺陷报告相关的源代码文件在排序列表中的位置;

(3)MAP(mean average precision).测量的是缺陷定位方法定位到的所有与缺陷报告相关的源代码文件在排序列表中的位置;

(4)E(effectiveness).表示在找到一个与缺陷报告相关的文件之前最少需要被开发者审查的源文件数目.

前 3 个指标的值越大,说明包含缺陷的文件在结果列表的位置越靠前,即方法的排序性能越好;而Effectiveness 的值越小,方法的性能越好.从表4 可以看出:其中,Top@K,MRR和MAP是应用最多的3 种指标,分别在40,38 和46 篇文献中被用来评估IRBL 方法.

Table 4 Summary of evaluation metrics for IRBL models in terms of ranking performance表4 评价IRBL 模型的排序性能指标汇总

4.2.2 评估分类性能的指标

在信息检索领域,另一类重要的指标是用来评价一种方法的分类性能.然而,由于IRBL 的输出结果是一个序列,分类指标不能被直接用于对这些方法进行评价.现有部分研究[60-62,86]的做法是,设置一个排名阈值将该序列分成两种类型,即:在排名之前的文件包含缺陷,反之不包含缺陷.

从二分类的角度来看,IRBL 方法的定位结果总共可以划分为以下4 种可能情况.

· 对于一个被定位为包含该缺陷的文件,它的确包含该缺陷,这种结果属于TP(true positive);

· 对于一个被定位为包含该缺陷的文件,它并不包含该缺陷,这种结果属于FP(false positive);

· 对于一个被定位为没有该缺陷的文件,它的确包含该缺陷,这种结果属于FN(false negative);

· 对于一个被定位为没有该缺陷的文件,它并不包含该缺陷,这种结果属于TN(true negative).

现有的二分类评价指标是基于上述4 种情况的统计技术来计算的.表5 对这些分类性能评估指标的计算方法和使用情况进行了汇总.这些指标的具体含义如下.

(1) Precision(精度):在预测为有缺陷的文件中,有多少比例的文件真正与该缺陷相关;

(2) Recall(召回率):在所有与缺陷相关的文件中,有多少比例的文件被定位为与该缺陷相关;

(3)F1-score(调和平均值):精度和召回率的调和平均值,可以更加客观地评价分类结果;

(4) Accuracy(准确率)[85]:在所有分类结果中,正确分类的文件(包括正确分为与缺陷相关和正确分为与缺陷无关的文件)占所有文件的比例;

(5) MCC(Matthews correlation coefficient,马修斯相关系数)[82]:表示的是真实类别和预测类别的二元分类之间的相关系数.

这些指标的计算与设定的排名阈值有关,即:在排名阈值之前的文件被定为包含某缺陷,反之不包含该缺陷.因为在没有阈值的情况下,任何结果是没有意义的.例如,召回率都为1.0 而精度都为k/K(K是项目中所有文件的数目,k是其中包含缺陷的文件数目).在这些指标中使用最多的是精度和召回率,它们都在11 篇文献中被使用过.

Table 5 Summary of evaluation metrics for IRBL models in terms of classification performance表5 评价IRBL 模型的分类性能指标汇总

4.2.3 评估工作量的指标

在缺陷定位领域,研究人员发现,上述性能评价指标不能完全满足IRBL 方法在实际应用中的评估需求.由于开发人员需要花费有限的工作量(时间和资源)来对IRBL 方法推荐的结果进行人工审查.在此期间,能够以较小工作量的找到缺陷所在位置才能够说明一个方法的实际有效性.因此,研究者们从工作量感知(effort aware)的角度来对结果进行评价.

表6 中对工作量性能评估指标的计算方法和使用情况进行了汇总,其中大部分评估指标是Zhao 等人[36,37]在2015 年首先提出的,他们使用代码行数来衡量一个文件在审查时所需花费的工作量.其具体含义如下.

(1) Effort@K:由Top@K派生而来,衡量了缺陷定位方法推荐对列表中前K个源代码文件进行审查时,开发人员找到与缺陷报告相关的源代码文件平均需要花费多少工作量;

(2) MAE(mean average effort):由MAP 派生而来,表示从推荐列表中找出所有与缺陷报告相关的源代码文件时平均所需花费的工作量;

(3) MFE(mean first effort):由MRR 派生而来,表示从源代码文件推荐列表中找到第一个与缺陷报告相关的源代码文件平均所需要的工作量.它的值越小,表示在工作量感知下方法的性能越好.

Table 6 Summary of evaluation metrics for IRBL models in terms of effort-aware performance表6 评价IRBL 模型的工作量性能指标汇总

4.3 实验数据

经过十几年的发展,目前IRBL 领域已有较多研究者收集并且公开了它们的实验数据集,这对于继续在缺陷定位领域进行研究十分有利.表7 列出了IRBL 领域的公开可用数据集的汇总信息,包括数据集提供者、所使用的项目数和提供的缺陷报告数目等.

Table 7 Summary of experiments datasets for IR-based bug localization models表7 基于信息检索的缺陷定位模型的数据集汇总

目前,IRBL 领域的数据集的收集和使用过程中仍存在一些问题需要得到重视.

(1) 项目语言偏向于Java.目前,绝大多数研究者提供的数据集中的实验项目是由Java 开发的,其他语言开发的数据集相对较少并且没有被大量引用.例如,Saha 等人[26]收集的C 语言项目和对Garnier 等人[38]收集的C#语言项目都仅在各自的研究中被使用.Java语言项目受到关注,这得益于Java语言的流行和相关项目的良好维护.现有研究可以在一定程度上说明目前的方法在对Java 项目进行缺陷定位时是有效的.然而,不同的语言在进行开发时有各自的特点,仅仅在一种语言的项目上实验的结果不能直接应用到其他语言开发的项目之上.其有效性还需要进一步的实验证实;

(2) 数据集质量各异.尽管数据集的收集过程都是按照Dallmeier 等人[115]提供的过程进行收集,但是具体操作过程会有一些差异,从而导致不同研究者收集的数据集存在一定到偏差,在这些数据上进行实验得到的结果可能会对分析带来误差.因此,为了得到客观公正的结果,需要花费更多的工作来审查数据集的质量来确保其准确性;

(3) 实验验证不充分.虽然已有较多的数据集,但是从统计信息来看,大多数研究者还是集中于使用个别数据集(例如Zhou 等人[28]和Ye 等人[47])来验证他们的方法.一方面说明现有的多个数据集还未受到研究者的重视,其数据集的可靠性有待于进一步被验证;另一方面表明,现有IRBL 方法仅在个别数据集上获得好的性能,其泛化能力仍有待更多实验数据的证实.

4.4 小 结

本节从模型比较、评价指标和实验数据这3 个方面详细介绍了在近年来对IRBL 方法进行评估的研究进展.下面简述主要的发现:

(1) 在实际定位中要选择合适的IRBL 方法,同时应当注意到,参数配置对结果的有效性的影响比较大.因此在应用具体IRBL 方法时,应当选择适当的参数;

(2) 现有研究主要是评价IRBL 方法的排序性能和分类性能,多数研究并没有从工作量感知的角度来评价他们的方法,导致现有的研究方法很难满足实际应用的需求;

(3) 目前,已有不同研究者提供的规模较大的数据集供后人使用,但是仍存在一些问题,例如数据集偏向于Java 编写的项目.此外,目前大多数研究仍只在少数数据集上测试它们的方法,无法确保其具有良好的泛化性能.

5 缺陷定位的相关研究工作

缺陷定位是一个涉及层面十分广阔的领域,除了可以使用信息检索技术实现软件缺陷定位,还可以通过其他多种途径定位软件中的缺陷,例如基于程序频谱的缺陷定位、基于程序变异的缺陷定位、基于多模态的缺陷定位等.本节中,对其他类型缺陷定位的相关工作进行简要介绍.

5.1 基于程序频谱的缺陷定位

基于程序频谱的缺陷定位(spectrum-based fault localization,简称SFL)是一类重要的动态定位技术,该类方法在进定位缺陷时需要执行大量的测试用例,然后通过对测试用例的程序频谱应用评估度量来定位错误语句.与基于信息检索的方法相类似的,该方法根据度量公式计算程序组件的分数,并对它们进行排序.基于程序频谱的定位效果依赖于程序频谱的构造方式和度量指标.以下是部分相关研究工作.

2009 年,Rui 等人[116]对早期的用于分析程序频谱的特定相似系数的性能进行了评估.实验结果表明,用于分析程序谱的特定相似系数的优越性能在很大程度上与实验的设计无关.此外,对于低质量的缺陷观察和有限数量的测试用例,基于程序频谱的缺陷定位已经获得了近乎最佳的准确性.实验也证明了基于程序频谱的缺陷定位可以有效地应用于嵌入式软件开发的环境中.

2010 年,Lee 等人[117]提出了一种利用频率加权函数进行缺陷定位的方法.该方法考虑了每个测试用例执行的程序语句的频率执行计数来进一步提高缺陷定位的性能.

2015 年,Naish 等人[88]发现,现有的遗传规划方法由于评估度量的巨大搜索空间变得缓慢而不可靠.因此,他们提出了一个“hyperbolic”度量的限定类,其中包含少量的数值参数,由此,遗传规划算法可以在大量的程序频谱上可靠地发现有效度量,从而使程序组件排序更准确.

2019 年,Ribeiro 等人[118]使用数据流频谱评估了10 个基于程序频谱方法的排名指标的有效性和效率.该实验证明:使用数据流频谱进行分析,比使用控制流频谱分析效果更好,最高有50%的缺陷位于排序列表的前15位.同年,Ma 等人[119]提出了一个统一的系统研究框架来评估和比较单缺陷和多缺陷情况下的基于程序频谱的缺陷定位方法.该框架实现了一个通用向量模型来深入理解各种基于程序频谱的缺陷定位方法.

5.2 基于变异分析的缺陷定位

基于程序变异的缺陷定位(mutation-based fault localization,简称MFL)是一种使用变异算子模拟人为错误来检测未知错误的定位方法[12,120-124],根据变异体与被测程序的执行结果,利用公式来推算代码语句的出错可能性.通常来说,这类方法在语句级别生成变异体,从而能够比较准确地定位出程序中有缺陷的语句.同时,由于需对大量程序变异体执行测试用例集,其执行开销较大.以下是部分相关研究工作.

2015 年,Papadakis 等人[125]首次提出了基于变异分析的缺陷定位的概念.他们提出的方法利用各个变异体间的相似性来检测缺陷:首先,使用变异算子为待测程序生成变异体;然后,对原程序和变异体执行测试用例并获取执行结果;接着,对执行结果构建特征计算变异体包含缺陷的风险分数;最后,根据相同位置的变异体与原程序语句风险分数来预测可能包含缺陷语句的位置.

同年,为了能够很好地处理真实世界中多语言程序的缺陷定位问题,Hong 等人[120]提出了一种基于变异的缺陷定位技术.该技术以目标程序的多语言源代码和一组测试用例作为输入,生成一个按照包含缺陷风险值排序的语句列表.为了计算每个语句的风险值,该技术首先通过系统地改变每个语句来生成原程序的不同变体;接着,根据语句发生特定变异后,测试结果变化情况来计算风险值.值得注意的是:为了提高对多语言程序缺陷定位的准确性,他们提出了适用于多语言程序的变异算子.

由于MFL 技术的计算开销较大,Liu 等人[121,122]在2017 年提出了两种变异约简策略来降低MFL 技术的计算成本.

· 一种是面向语句的变异约简策略[121],该策略首先用全套变异算子在失败测试用例覆盖的每个语句上产生变异,以确保能够使用完整类别的变异算子;然后利用每个语句上的变异体抽样策略,选择使用特定百分比的变异体;

· 另一种是动态变异执行策略[122],该策略会确定优先执行的变异体和测试用例首先执行,避免进行无用的执行来降低计算开销.

2018 年,Oliveira 等人[123]提出一种面向失败测试的变异运行策略FTMES 来提高基于变异的缺陷定位的有效性,并且降低其所需的计算开销.FTMES 只使用一组失败的测试用例来执行变异,并且通过使用覆盖率数据替换终止信息来避免执行已通过的测试用例.

5.3 基于多种模态的缺陷定位

很多方法只考虑了某一种类型的缺陷定位技术,比如:基于信息检索的方法只考虑了缺陷报告中的文本信息及静态特征;基于程序频谱的方法只考虑动态的程序频谱特征.很多研究者发现:同时结合两种或以上类型的缺陷定位技术能够发挥出各自的优势,从而能够获得更好的缺陷定位效果.以下是部分相关研究工作.

2015 年,Le 等人[45]将多模态信息检索与程序频谱组合进行缺陷定位,并且自适应地创建了一个特定于某个缺陷的模型,以将特定的缺陷映射到它可能的位置.该方法同时考虑了缺陷报告中的文本描述和程序的频谱信息,最后结合两者的分析结果获得可疑的术语或单词,并且以此来判断程序组件包含缺陷的可疑程度.

2017 年,Dao 等人[54]研究了代码运行信息对基于信息检索的缺陷定位的帮助.作者在文中比较了3 种目前流行的基于信息检索的缺陷定位方法(BugLocator[28],BLUiR[24],AmaLgam[31])和3 种代码运行信息(程序覆盖、程序切片和程序频谱).实验证明,代码的运行信息会很大改进基于信息检索的缺陷定位方法.

2019 年,Hoang 等人[67]也发现了只考虑缺陷报告和只考虑执行跟踪的方法的限制.他们提出了一种多模态缺陷定位方法,通过联合使用缺陷报告和执行跟踪来解决现有方法存在的问题.

5.4 基于新型应用的缺陷定位

目前,大多的IRBL 方法在进行缺陷定位时并没有细致考虑到缺陷的类型,他们的研究是针对所有类型的缺陷而言.在现实应用中,进行缺陷定位要面临不同的应用场景,此时,直接使用这些方法可能无法得到预期效果.因此,有部分研究开始在更加细分类别的缺陷上研究定位方法.

· 对软件崩溃的定位.软件崩溃开始研究一种特殊缺陷,这种缺陷经常发生在用户使用软件的过程中,它导致软件无法正常工作而出现崩溃界面,因而严重影响用户体验.这类缺陷通常会由软件后台自动收集相应的崩溃信息提交给后台服务器.Wu 等人通过挖掘这些崩溃信息,提出了CrashLocator[126]和ChangeLocator[127],分别在方法级别和变更级别定位这种缺陷.2020 年,Guo 等人[128]在ChangeLocator的基础上对崩溃变更的特征进行选择,他们发现:过滤后的特征,能够用来构建更好的崩溃变更定位模型;

· 对Android 应用缺陷的定位.Android 应用与开源的桌面软件有所不同,它们运行在手机操作系统之上,这类应用的历史缺陷报告较少,并且没有充足的详细描述信息.因此,很难将现有的IRBL 方法直接用于对Android 应用进行缺陷定位.2019 年,Zhang 等人[100]基于提交信息,提出了一种适用于Android 应用的缺陷定位方法.

5.5 小 结

本节从程序频谱、变异分析、多模态和新型应用这4 个方面简要介绍了缺陷定位领域中其他相关研究.下面简述主要的发现:

(1) 程序频谱是主流的动态缺陷定位方法,其相关研究一直是缺陷定位领域的另一个热点;

(2) 变异分析是一种有效的动态缺陷定位方法,目前多数研究主要致力于降低这类方法的计算成本;

(3) 多模态的缺陷定位方法可以结合多种定位技术的优点,近年来也逐渐受到研究者的重视;

(4) 缺陷定位的应用已经开始逐步细分到研究具体类型的缺陷,这种趋势有利于更精细化地将缺陷定位技术应用到实践中.

6 挑 战

从现有文献来看,IRBL 技术的相关研究已经取得了很好的成效,最新的定位方法已经能够将定位性能提升到一个较高的层面.但是我们应当注意到,现有的研究技术在工业界中并没有被广泛应用[39],因为它还难以满足实际软件开发和维护过程的需求.本节从局限性、泛化性、准确性和实用性这4 个角度来介绍IRBL 领域的研究面临着以下挑战.

(1) 局限性.目前,对IRBL 方法的性能评估是基于该方法在一组缺陷报告上测试的平均性能值(例如MRR).这类评估指标可以在整体上对某个方法进行评价,但是有一点需要注意:在整体上具有较高的评估分数,不代表该方法在每个具体缺陷报告的推荐结果也令人满意[73].对任何IRBL 方法来说,是不可能对所有的缺陷报告都给出最优排序结果的.在应用一种方法时,可能会遇到以下情况:对某些(可能仅仅一小部分)缺陷报告进行推荐时,该方法会将这些缺陷报告对应的源文件排在十分靠后的位置.对这样的推荐结果,开发者按照列表顺序从头审查将会花费巨大的工作量.尽管这种推荐结果出现的次数较少,但是由于开发者不知道何时会遇到这种推荐,他们会倾向于不使用该方法.上述情况属于一个IRBL 方法的应用局限性.能够准确分析每个IRBL 方法的局限性十分关键,这可以在使用时规避上述情况的发生.现有研究的一个问题是局限性分析较少,导致开发者不能够在恰当的场景下使用这些IRBL 方法,从而这些方法的最大优势不能被充分利用,同时在使用时不能及时避免其劣势;

(2) 泛化性.影响泛化性的因素有两点.

1) 测试数据集稀少.虽然现在已有多个公开数据集,最近两年提出的一部分IRBL 方法[41,64,65,79,94,99]仍仅仅在很少的测试项目(Zhou 等人[28]在2012 年提供的4 个项目)上进行了验证.特别地,这些项目数据大多是是由Java 语言开发的,因此多数现有的实验结果是适用于Java 项目的[35],但是在其他类型的项目上的性能表现未知,即IRBL 方法的泛化性能未知.由于存在这种不确定性,目前的方法很难受到开发人员的信任,并且他们也很难挑选出优秀的方法.因此,许多工作[25,31,80]指出,仍然需要在更多的项目上进行实验来测试IRBL 方法的性能;

2) 人工设计特征.现有的IRBL 方法的特征选取和挖掘都是人工根据某一部分的缺陷数据进行设计的,用这种方式构建出的方法可以在可以一些数据上达到较好的效果.然而,遇到具有不同特征的数据,这些方法的定位能力便会降低,从而就表现为泛化性低下[68];

(3) 准确性.准确的实验数据集是保证定位方法质量的重要依据.现有的数据集虽然都是按照Dallmeier等人[115]提供的方法进行收集的,但是不同的研究者在具体操作过程中会有细节上的差别[28,35,39,115],从而导致不同数据集的准确性受到影响.其中,一些重要的细节信息需要验证,例如:与缺陷报告进行匹配的源代码的版本是否为被修复前的版本[47];数据集中明显不包含缺陷的部分(例如测试文件)应当被排除在推荐列表之外[39]等等.这些不完全统一的处理细节会严重影响方法测试结果的准确性,甚至产生互相矛盾的比较结果[66];

(4) 实用性.目前的IRBL 方法仅活跃在实验研究阶段,它们并没有在工程实践中大量应用[39].除了准确性和泛化性较低的因素之外,更重要的原因是这些定位方法(如BugLocator[28],BRTracer[30],Locus[32]等)只能够提供给开发者建议性的缺陷文件列表,无法为开发人员修复缺陷提供更多的指导信息.在生产实践中,开发人员需要完全依靠自己对代码的理解来手动检查,所以目前缺陷定位技术所提供的帮助很小,我们分析,这是导致它们的实用性很难满足开发者的需要的另一个重要原因.

针对缺陷定位技术面临的问题挑战,我们从结果分析、实验验证和修复指导总结了以下几方面可能将会成为进一步深入研究的重要方向.

(1) 结果分析.其中一个研究方向是在缺陷定位框架中应当具有侦测机制,对缺陷报告的特征进行检测并进行分类,根据检测结果,缺陷定位框架应当决定是使用他们提出IRBL 方法进行定位还是放弃对该报告的定位.这一过程的实现,有利于开发者充分发挥IRBL 方法在其擅长处理的缺陷报告中进行推荐的能力,并且避免他们给出低效的推荐结果.这种机制的建立,需要对IRBL 方法的定位结果进行分析,通过收集较差的推荐列表所对应的的缺陷报告,分析这些缺陷报告的特征,在应用时,遇到具备这类特征的缺陷报告就停止使用IRBL 方法,而是进行人工处理或者借助其他技术来帮助定位.除此之外,需要增多对IRBL 方法进行工作量感知[36,37]方面的性能评估分析;

(2) 实验验证.针对泛化性和准确性的挑战问题,一个研究方向是增加科学准确对比实验研究目前方法的有效性.主要包括两个方面.

1) 收集全面精准的数据集.目前的研究所使用的数据集极其不统一,所以他们得出的结论具有片面性,不能代表其真实的性能.为基于信息检索的缺陷定位研究收集更多的准确数据集,需要涵盖各种语言的书写的项目以及各个领域的项目,用来验证方法的有效性和泛化性;

2) 设置科学的实验流程和设置.目前的研究所用的实验设置比较混乱,这也会影响实验结果的准确性.因此,需要在科学统一的流程和设置下进行实验.实验设计要符合现实开发的场景,以确保其合理性;

(3) 修复指导.为了提高定位方法的实用性能,一个重要的研究方向便是对缺陷定位的结果提供修复指导提示信息.对于给定的推荐结果列表,开发人员只能按照顺序从头开始审查,这还是需要大量花费精力来理解缺陷.如果IRBL 方法能够指出其中列表中的文件中哪些特征是与缺陷报告描述内容相符,这可以在很大程度上帮助开发人员快速理解缺陷,并顺利进行后续的修复工作.

7 结束语

近年来,基于信息检索的缺陷定位技术(IRBL)由于其具有外部依赖少、计算成本低的优势,成为了缺陷定位领域的研究热点.本文围绕IRBL 方法的模型改良和模型评估两大方面,对当前的研究工作进行了梳理和总结.基于当前的研究进展,本文总结了该领域面临的主要挑战并指出了未来可能的研究方向.主要工作总结如下:(1) 针对模型改良,本文从更换检索模型、使用特征分析和进行查询重构这3 个维度进行归类和阐述;(2) 针对模型评估,本文从模型比较、评价指标和实验数据这3 个维度总结该领域的评估现状和存在的问题;(3) 本文从局限性、泛化性、准确性和实用性这4 个角度总结了当前IRBL 领域研究面临的问题挑战,并针对性地指出了未来的研究方向.

致谢感谢各位审稿专家提出的宝贵意见.