Page 133 - 《软件学报》2020年第11期

张卓 等:基于词频-逆文件频率的错误定位方法 3449

软件调试在软件开发过程中耗费了大量的人力物力,研究人员为了提高软件开发的效率,降低开发成本,提
出了许多错误定位方法(例如文献[1−5]).其中最典型的方法是基于频谱的错误定位方法(spectrum-based fault
[2]
localization,简称 SFL) .SFL 方法的原理是,首先,通过分析测试用例集运行信息,构建出语句覆盖信息矩阵;然
后,基于该矩阵,采用可疑值度量公式评估出语句为错误的可疑值;最后,依据可疑值对所有语句进行降序排列,
并根据语句排序列表来定位错误语句,其中的语句覆盖信息矩阵是 SFL 方法的关键基础,影响着后续可疑值计
算模型的精度.
然而,语句覆盖信息矩阵仅仅记录了语句是否被测试用例执行的二进制状态信息,即被执行为 1,未被执行
为 0.二进制状态信息表达信息能力很有限,无法展示出语句在具体测试用例执行中的重要程度,限制着错误定
[7]
[6]
位精度 .目前,一些研究 尝试将语句在测试用例中的执行次数融入到覆盖矩阵信息.然而,这些研究并没有考
虑到该语句在所有测试用例中的特征,由此产生一些偏差,对错误定位效果反而产生不利的影响.因此,有必要
研究如何融合更为丰富的有效信息到信息覆盖矩阵,使其能够更准确地反映出语句和测试用例之间的关系,解
决信息表达能力弱对定位精度上限的限制问题.
基于上述分析,本文提出基于词频-逆文件频率(term frequency and inverse document frequency,简称
[8]
TF-IDF) 的错误定位方法,以增强信息表达能力来实现错误定位效力的提升.该方法试图将词频-逆文档频率
技术融入到错误定位中,综合全局与局部两个维度,获取语句与测试用例之间更为丰富的有效关系信息,以此构
建出信息表达能力更强的信息模型.根据构建的信息模型,利用 SFL 的方法原理重新定义其中的参数来计算语
句的可疑值.本文在真实开源程序的大量错误版本上进行了实验.实验结果表明,基于 TF-IDF 的错误定位方法
能够大幅提升缺陷定位效能.具体来说,本文方法在高效能区间(即检查可执行语句的比例 5%~10%的区间)取得
最明显的效能提升,并且在严格统计学意义下,本文方法取得 7 个更优结果和 1 个相似结果.
本文第 1 节介绍相关背景知识.第 2 节介绍基于词频-逆文件频率的错误定位方法.第 3 节为实验描述和结
果分析.第 4 节为相关工作.第 5 节总结全文.

1 相关背景

(1) 词频-逆文档频率
在信息检索领域中,TF-IDF 是一种数值统计技术,旨在反映单词对文档集或一个语料库中的一份文件的重
要程度.在自然语言处理领域,TF-IDF 是最流行的词语加权方案之一,通常应用于信息搜索、文本挖掘和用户建
[8]
模 .TF-IDF 的主要思想是,假设有一个文本集合由多个文本组成,假设这个集合中某一个文本的某个词在所在
文本中出现较多次而在其他文本中出现的较少,则这个词对于区分这个文本集具有较好的能力,比较适合用来
做分类.TF 表示词频(term frequency),IDF 是逆文本频率指数(inverse document frequency).词频指的是一个词在
[8]
一个文件中出现的次数,逆文本频率指数指的是一个词在所有的文件中出现的频度 .如果一个词在某个文件
中出现的次数较多,则它的词频值较高,反之则词频值较低.这个次数是对词数量的归一化,防止它偏向于较长
的文本文件(同一个词无论重要与否,在短文件中出现的次数可能较少,而在长文件中较多).相反的,一个词如果
在许多文档中都出现,则它的逆文本频率指数值较低;反之,在较少的文档中出现,则逆文本频率指数值则较
高.IDF 是一个词语重要性的度量,具有较低 IDF 的词语表示区分能力不强,反之则是区分能力较强.下面举例说
明 TF-IDF 的一般计算方法:
公式(1)是 tf 的计算公式,假设一个文档集合 D 中的一个文本 L 包含 k 个词,按照从 1 到 k 的顺序进行编号,
第 i 个词的编号为 i,则第 i 个词的 TF 值为 tf i .公式(1)的分子为词 i 在文本 L 中出现的次数,记为 n i ,分母为文本
L 中从 1 到 k 所有词的出现次数之和,它们的比值即为词 i 的 TF 值.
n
tf = i (1)
k ∑ n k
i
公式(2)是 idf 的计算公式,D 为一个文档集合,文档的总数为 N,idf(t,D)表示一个单词 t 在文档集合 D 中的逆
文本频率指数.对于文档集合 D,d 为 D 中的一个文档,如果这个 t 在 d 中出现,则 t 的数目加 1,|{d∈D:t∈d}|指的