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

3452 Journal of Software 软件学报 Vol.31, No.11, November 2020

件调试带来更大干扰.因此,融入丰富的有效信息对覆盖信息矩阵进行优化,获得更为精准的定位有效信息,有
利于提高错误定位精度.
2 基于词频-逆文档频率的错误定位方法

(1) 方法原理
基于词频-逆文档频率的错误定位方法的基本思想是,利用 TF-IDF 技术构建覆盖信息矩阵.这个矩阵中的
每一个元素的值不再是代表执行或未执行的二进制信息,而是表示语句对测试用例的影响程度.TF(s,t)对应的
是语句 s 在测试用例 t 中的 TF 值.一个测试用例中执行的语句数越多,按照公式(1)中 TF 值的计算,测试用例 t
中每个语句出现一次,分子为 1,分母为语句数的总和,因此 TF(s,t)值越小.IDF(s)是语句 s 在所有测试用例的执行
频度:如果 s 在许多测试用例中执行,则 IDF(s)值较小;如果 s 在少数测试用例中执行,则 IDF(s)值较大.
假设程序 P 包括 N 个语句,分别为{s 1 ,s 2 ,…,s N },这些语句被 M 个测试用例 T 执行.测试用例 T 为{t 1 ,t 2 ,..,t M },T
中至少包含一个失败的测试用例.图 3 左侧的 M×(N+1)矩阵为测试用例运行后的语句覆盖信息矩阵以及测试用
例的运行结果.如果语句 s i 被测试用例 t k 执行,则 x ik 为 1,否则为 0.errors 表示测试用例执行结果,它是由 M 个测
试用例的结果{e 1 ,e 2 ,..,e M }组成. e i 的值为为 0 表明 t i 是成功的测试用例,值为 1 表明 t i 是失败的测试用例.可以发
现,二进制矩阵仅表示语句在测试用例中是否被执行,并不能得出语句对测试用例的影响程度.因此,本文方法
采用 TF-IDF 对矩阵进行重新计算.在左侧 M×(N+1)的二进制矩阵的基础上,对矩阵中的元素 x ij 计算出
TFIDF(x ij ),具体计算方法为公式(4)~公式(6).
TF ()x ij = x × ij 1 (4)
+
N t
1 log( ( ))
i
IDF(x ij )=log 10 (M/DF(s j )) (5)
TFIDF(x ij )=TF(x ij )×IDF(x ij ) (6)
公式(4)计算 x ij 的 TF 值.在公式(4)中,x ij 为图 3 左侧二进制矩阵中的一个元素,值为 1 或 0.N(t i )为测试用例
t i 中被执行的语句的个数,即图 3 左侧二进制矩阵 M×N 中第 i 行值为 1 的个数.公式(5)计算 x ij 的 IDF 值.M 为测
试用例的总数,DF(s j )为所有测试用例中执行语句 s j 的测试用例数(如果 DF(s j )为 0 时,取 IDF(x ij )为 0).参照实验
数据,公式(4)和公式(5)选取常用的 log 和 log 10 .最后,基于公式(4)和公式(5),公式(6)计算 x ij 的 TF-IDF 值.
N statements errors N dimensional errors
x ⎡ 11 x 12 ... x 1N ⎤ ⎡ 1 e ⎤ ⎡ TFIDF (x 11 ) TFIDF (x 12 ) ... TFIDF (x 1 ) ⎤ N ⎡ 1 e ⎤
⎢ ⎥ ⎢ ⎥ → ⎢ ⎥ ⎢ ⎥
⎢ x 21 x 22 ... x 2N ⎥ ⎢ 2 e ⎥ ⎢ TFIDF (x 21 ) TFIDF (x 22 ) ... TFIDF (x 2 ) ⎢ 2 e ⎥
N ⎥
⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥
⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥
⎣ M x 1 M x 2 ... x MN ⎦ M e ⎣ ⎦ ⎣ TFIDF ( M x 1 ) TFIDF x 2 ) ... TFIDF x ) M e ⎣ ⎦
( MN ⎦
( M
Fig.3 Binary matrix and the TF-IDF matrix of M executions
图 3 M 个测试用例的二进制矩阵和 TF-IDF 矩阵
本文基于构建的 TF-IDF 矩阵重新定义语句 s j 的 4 个参数 a np ,a nf ,a ep ,a ef .公式(7)~公式(10)分别为语句 s j 的 4
个参数 a np ,a nf ,a ep ,a ef 的计算公式.
a np ()s = ∑ M 1 (1 TFIDF− ( )) (1x ij × − e i ) (7)
i=
j
a nf ()s = ∑ M 1 (1 TFIDF− ( ))x ij × e i (8)
i=
j
a ep ()s = ∑ i= M 1 TFIDF ( ) (1x × ij − e i ) (9)
j
a ef ()s = ∑ M 1 TFIDF ( )x × e i (10)
ij
j
i=
最后,本文方法根据 4 个重新定义的参数,采用表 1 的可疑值计算公式计算出每个语句的可疑值.
(2) 例子演示
如图 4 所示,本小节通过包含错误语句 s 6 的程序 P 展示基于 TF-IDF 的错误定位方法工作原理.这个例子选