1.一种基于mRMR算法挑选可疑度公式的程序错误定位方法,包括如下步骤:(1)统计软件程序中各条语句在每组测试用例下的语句覆盖情况,得到对应的语句覆盖矩阵;
(2)统计每组测试用例在软件程序运行下的执行结果:正确或错误;
(3)根据语句覆盖情况以及执行结果计算每条语句的程序频谱数据;
(4)对于任一可疑度公式,根据程序频谱利用该公式计算软件程序中每条语句的错误可疑度,进而根据错误可疑度从高到低的顺序对所有语句进行排序得到语句排序列表;
(5)根据步骤(4)遍历通过基因编程技术生成的所有可疑度公式,得到这些可疑度公式所对应生成的语句排序列表;其中通过基因编程技术生成可疑度公式的具体过程为:首先初始化生成一定规模的种群,使种群中个体进行交叉、变异操作后生成子代个体,比较子代个体与父代个体的适应度,使适应度较优的子代个体替换掉父代个体,保持种群规模不变,从而完成一次迭代过程;依此完成多次迭代或种群的整体适应度水平达到所需的要求,则终止该过程并输出当前种群;所述适应度即通过个体对应的可疑度公式定位到错误语句所排查的语句数量占整个程序语句总数量的百分比;
(6)根据可疑度公式的语句排序列表采用mRMR算法计算公式之间的相关性,并根据计算结果挑选出一定数量的可疑度公式;
所述mRMR算法通过衡量同个语句被不同公式所计算出的不同可疑度值来刻画各公式之间的相关性,具体地:给定一个公式集合S,其标签为c,则公式与标签之间的最大相关性D的计算公式如下,算法采用所有公式与标签之间互信息的平均值来近似化;
其中:|S|为公式集合S中的公式数量,c为标签,xi为公式集合S中的第i个公式,I(xi:c)为公式xi与标签c之间的互信息;
通过Max‑Relevance选择的公式之间可能存在冗余,当两个公式之间是冗余的,则通过以下公式来剔除冗余公式;
其中:R为公式xi与公式xj之间的最小冗余性;
mRMR算法定义了一个算子Φ来将Max‑Relevance和Min‑Redundancy结合,即:Φ=D‑R
假设已经生成公式子集Sm‑1,需要在剩余的公式集合中选择第m个公式,则采用增量搜索的方法得到近似最优解,通过最大化Φ算子选择公式,即:其中:Sm‑1为已经选择了m‑1个公式组成的公式子集;
(7)对于软件程序中的任一条语句,利用所挑选出的可疑度公式计算出该语句的错误可疑度并组成向量作为输入,以该语句在软件程序中是否为错误语句作为标签,选择机器学习算法对其进行训练,训练完成得到语句错误可疑度估计模型;
(8)对于需要进行错误定位的软件程序,利用所述估计模型计算出其中每一条语句的错误可疑度,根据错误可疑度从高到低对所有语句进行排序并逐条进行错误排查。
2.根据权利要求1所述的程序错误定位方法,其特征在于:所述步骤(1)中语句覆盖情况的定义为:以某一测试用例作为软件程序的输入,若软件程序在整个运行过程中执行了某一条语句,则该语句在该测试用例下的语句覆盖情况表示为1,否则表示为0。
3.根据权利要求1所述的程序错误定位方法,其特征在于:所述步骤(1)中语句覆盖矩阵的大小为m×n,m为软件程序中的语句总数,n为测试用例总数;该矩阵中第i行第j列的元素值为第i条语句在第j组测试用例下的语句覆盖情况,i和j均为自然数且1≤i≤m,1≤j≤n。
4.根据权利要求1所述的程序错误定位方法,其特征在于:所述步骤(3)中对于软件程序中的任一条语句s,其程序频谱数据包括了以下四个因子:a11表示软件程序对于测试用例的整个运行过程中执行了s且执行结果为正确的测试用例个数;
a00表示软件程序对于测试用例的整个运行过程中未执行s且执行结果为错误的测试用例个数;
a10表示软件程序对于测试用例的整个运行过程中执行了s且执行结果为错误的测试用例个数;
a01表示软件程序对于测试用例的整个运行过程中未执行s且执行结果为正确的测试用例个数。
5.根据权利要求1所述的程序错误定位方法,其特征在于:所述步骤(7)中的机器学习算法可选用随机森林算法或支持向量机算法。
6.根据权利要求1所述的程序错误定位方法,其特征在于:所述步骤(8)中对于需要进行错误定位的软件程序,利用步骤(6)所挑选出的可疑度公式计算程序中每一条语句的错误可疑度,对于任一条语句,将各个可疑度公式对其计算得到的错误可疑度组成向量形式输入至模型中,得到由模型估计出的语句错误可疑度。