基于谓词频率统计的软件故障定位方法

摘要

本发明公开了一种基于谓词频率统计的软件故障定位方法，用于解决现有软件故障定位方法定位精度低的技术问题。技术方案是采用化整为零的方法，将所求面积分成N块，对每一块求值，最后将所有的N个子块的面积求和，即求得要求的总区间[0,1.0]上的总面积，也就是反映谓词和错误相关性的度量值。在一定范围内，N的值越高，计算的就越精确。本发明在将故障定位粒度细化至谓词级别的基础上，采用了基于非参数模型的统计方法，不需要被统计量符合某种已知分布模型，排除由于被统计数据的随机性对算法稳定性带来的影响，可以提高定位精度。

主权项

一种基于谓词频率统计的软件故障定位方法，其特征在于包括以下步骤：对某程序一次运行中某一个谓词P多次赋值的记录采用真值率来描述；①在程序的一次运行中，假设谓词P被记录为真的次数为n_t，被记录为假的次数为n_f，那么称：$\pi \left(P\right)=\frac{n_t}{n_t+n_f}---\left(1\right)$为谓词P在这次执行中的真值频率；由极大似然法知，在样本足够多的情况下，P的真值频率无限接近P取值为真的概率，因此π(P)在一定程度上反映了谓词P在一次取值中为真的概率；②假设对于一个程序，所有的测试用例集合为T，T_f表示失败的测试用例集合，T_p表示成功的测试用例集合，那么f(X|θ_p)和f(X|θ_f)分别表示T_f和T_p的真值率的概率密度函数；设f(X|θ_p)和f(X|θ_f)分别表示谓词P在成功的运行集合与失败的运行集合中的真值率的概率密度函数；采用f(X|θ_p)和f(X|θ_f)两者相差的部分的面积：$S\left(P\right)={\int }_0^1|f\left(X\right|{\theta }_p)-f\left(X\right|{\theta }_f)|d_{\pi \left(p\right)}---\left(2\right)$作为衡量二者差异的关键值；采取了化整为零、分段计算的方式代替直接求表达式的方式：假设在总共X次的程序执行中，谓词P得到了Y个真值率记录，有X>＝Y；谓词P的真值率π(P)的取值范围为闭区间[0,1.0]，将该区间化整为零，分成N段单独处理：取N＝10000，得到[0,0.0001)，[0.0001,0.0002)，[0.0002,0.0003)，[0.0003,0.004).....[0.9999,1.0]这10000个子区间；假设对于每个子区间[a,b](0<＝a<b<＝1)上，在成功运行和失败运行的样本中，π(P)落在该区间范围内的样本数分别为Z_p和Z_f，那么该区间的分布密度就分别等于公式(3)：$F_p(a,b)=\frac{Z_p}{Y}$和$F_f(a,b)=\frac{Z_f}{Y}---\left(3\right)$那么在该子区间上，两个函数的曲线围成的等效面积就等于公式(4)：$|\frac{Z_f}{Y}-\frac{Z_p}{Y}|---\left(4\right)$那么对应的有，在区间[0,1]上，两个函数围成的总面积就等于公式(5)：$\underset{i=1}{\overset{10000}{\Sigma }}|\frac{Z_{\mathrm{fi}}}{Y}-\frac{Z_{\mathrm{pi}}}{Y}|---\left(5\right)$当区间数目取值越大，每个子区间的长度就越小，误差就越小，当N接近正无穷时，误差为0，二者完全相等：${\int }_0^1|f\left(X\right|{\theta }_p)-f\left(X\right|{\theta }_f)|d_{\pi \left(p\right)}=\underset{N\to \infty }{\lim }\left(\underset{i=1}{\overset{N}{\Sigma }}\right|\frac{Z_{\mathrm{fi}}}{Y_f}-\frac{Z_{\mathrm{pi}}}{Y_p}\left|\right)---\left(6\right)$因此有$S\left(P\right)=\underset{N\to \infty }{\lim }\left(\underset{i=1}{\overset{N}{\Sigma }}\right|\frac{Z_{\mathrm{fi}}}{Y_f}-\frac{Z_{\mathrm{pi}}}{Y_p}\left|\right)---\left(7\right)$公式(7)就是FDI算法最后的结果，其中S(P)表示谓词P的可疑度取值。