Page 253 - 《软件学报》2021年第7期

姜淑娟 等:基于路径分析和信息熵的错误定位方法 2171

更多与错误相关的信息;反之,若仅有少数测试用例失败,那么其更有利于错误定位.基于此,文献[18]提出了一种
基于事件信息量的方法 SIQ.本文在其基础上,利用信息熵加以改进,进一步提高错误定位的精度.
信息熵是表示随机事件不确定性的数学化度量,是所有随机事件信息量的期望.对于一组随机事件 X 
{, ,x x  , },x 假设 x i 发生的概率为 P(x i ),则其信息熵 H(x)的定义如下:
1 2 n
n n
H ( )x  E [ ( )]I x i    ( ( ) log ()) ( )P x  i P x H x  i E [ ()]I x i    ( () log ( ))Px  i Px i (1)
i 1 i 1
错误定位中的测试事件主要分为 4 类,即执行成功的事件 P 和执行失败的事件 F、覆盖程序实体的测试事
件 C(s)和未覆盖程序实体的测试事件 U(s),它们的信息熵表示如下:

() 
[ ( )] 
HP E I P    N S   log N S   (2)
 N  S N F N  S N F 
[ ( )] 
() 
HF E I F    N F   log N F   (3)
 N  S N F N  S N F 
()
( )
(( ))s 
C
C
HC E [ ( ( ))]I C s      Ns  log Ns   (4)
 N C () s  N U () s N C () s  N U () s 
()
()
(( ))s 
U
U
HU E [ ( ( ))]I U s      Ns  log Ns   (5)
 N C ( ) s  N U () s N C () s  N U () s 
为避免程序实体全部被覆盖执行或全部不执行两类随机事件的发生,我们取未执行一次代替全部执行的
事件,同理,用覆盖一次代替全部不执行的事件.
对测试事件进一步分析可知:N CF 和 N US 的数值越高,说明覆盖程序实体的测试事件更容易导致执行失败而
未覆盖程序实体的测试事件更容易使得执行成功,这两个参数与怀疑度计算成正比.同理可得,N CS 和 N UF 的数
值与怀疑度计算成反比.
利用信息熵 H(P)、H(F)、H(C(s))和 H(U(s))将程序语句存在错误可能性的信息量加权平均,对计算公式中
参数设置权重进行动态调整,辅助语句可疑度的计算.由于测试事件执行成功与否和其覆盖信息并不是相互独
立的,两者的信息熵无法相加,故以乘积的方式引入.综上所述,我们得到的怀疑度计算公式如下:
( ( ())HC s  H ( )F  N ( )) ( ( ())s  H U s  H ( )P  N ( ))s
susp ()s  CF US (6)
( ( ())HC s  H ( )P  N CS ( )) ( ( ())s  H U s  H ( )F  N UF ( ))s
2.4 示例分析
本节引入了一个简单的例子程序,该例子程序包含 12 条语句,错误语句位于 s 5 处,例子程序及其控制流图如
图 3 所示.

Fig.3 An example program and its CFG
图 3 示例程序及其控制流图