基于遗传算法的函数级别软件错误定位

黄晴雁，牟永敏，崔展齐，张志华

1.北京信息科技大学 计算机学院，北京100101

2.北京信息科技大学 网络文化与数字传播北京市重点实验室，北京100101

1 引言

软件调试在软件开发中扮演了极其重要的角色，而快速准确地找到程序中的错误是软件调试的关键[1]。手工调试方法耗时耗力且效率低下，为了能够高效准确地定位软件错误的位置，研究人员提出了很多行之有效的自动化软件错误定位方法。自动化软件错误定位方法分为静态分析和动态分析两类。静态分析方法[2-3]不需运行程序，通过分析程序的源代码和结构等信息定位到具体的错误源；动态分析方法[4]通过运行程序分析测试用例的执行轨迹以及运行结果来辅助定位错误位置。

动态分析是自动化软件错误定位研究的重点，大致可以分为基于程序频谱、基于依赖关系、基于数据挖掘以及基于程序切片的错误定位等方法[3-6]。其中，基于程序频谱的错误定位是目前主流的研究思路[7]，通过执行大量测试用例得到程序实体覆盖信息和执行结果，使用统计学方法计算实体的可疑值，对具有单一错误的程序表现出良好的定位效果。Jones 等[8]提出了Tarantula 可疑度计算公式，认为被更多的失败测试用例执行到的实体，其含有错误的可能性要高于其他实体。随后，Abreu等[4]根据聚类分析提出了Jaccard 公式，受分子生物学启发提出了Ochiai可疑度计算公式，提高了错误定位的效果。Wong等[9]在Kulczynski系数的基础上提出了DStar方法，实证研究中发现该方法的定位效果要优于其他方法。

近年来，基于搜索的软件工程（Search Based Software Engineering，SBSE）逐渐被应用于软件错误定位和错误自动修复领域[10-12]。SBSE 将传统软件工程问题建模为组合优化问题，利用元启发式搜索技术搜索求解。基于此，张蓓等[13]提出了一种基于增强遗传BP神经网络的软件错误定位方法，在效率和精确度上均有进步。王赞等[14]提出了一种基于遗传算法的多缺陷定位方法，对多缺陷定位问题进行建模，有效减少了人工交互。

目前，大多数的错误定位方法针对语句级别，很少基于函数粒度进行研究。语句级别的定位是一种细粒度的定位方法，可以将错误定位到某一条语句。然而在实际软件开发过程中，软件错误的发生大多是由于某个函数内部的逻辑或语句顺序出现错误造成的。在粗粒度的函数级别上进行错误检测定位比细粒度的语句级别更为合理有效。同时，在程序较为复杂，并且存在多个错误位置时，基于搜索的软件工程能够提供良好的定位结果。而遗传算法作为主流的搜索算法，具有很强的通用性、鲁棒性和全局搜索能力。因此，本文提出一种基于遗传算法的函数级别软件错误定位框架FGAFL，通过执行测试用例得到函数级别的程序频谱，借助基于搜索的软件工程思想进行建模，结合函数间的调用信息，利用遗传算法搜索求解。

2 相关概念与技术

2.1 软件错误定位

基于程序频谱的错误定位就是根据程序运行的频谱信息来统计程序中各个实体的可疑值并进行排序，越可疑的实体含有错误的可能性越大[15]。接下来对相关概念依次给出定义，并在之后的内容中采用本节定义的符号概念。

定义1 测试用例集：T={t1,t2,…,tm}表示待测程序的m 个测试用例集合。其中ti表示第i 个测试用例。根据运行结果将T 分为失败测试用例集TF和成功测试用例集TP。

定义2 待测程序实体集：E={e1,e2,…,en}表示待测程序中包含n 个函数。其中ei表示程序中第i 个函数。

定义3 覆盖矩阵：M=(Mij)表示测试用例集T 和程序实体集E 之间的覆盖关系。 M 是一个由0和1构成的m×n 阶矩阵。当Mij=1 时，表示测试用例i 覆盖了函数j，当Mij=0 时，表示测试用例i 未覆盖函数j。MF=(Mij)是失败测试用例覆盖矩阵，包含失败测试用例集TF的覆盖信息；MP=(Mij)是成功测试用例覆盖矩阵，包含成功测试用例集TP的覆盖信息。

定义4 测试用例结果向量：R={r1,r2,…,rm}表示测试用例集中m 个测试用例的测试结果。其中ri表示第i 个测试用例的执行结果，ri的取值为0或1，当ri=1时，表示第i 个测试用例执行失败，当ri=0 时，表示第i个测试用例执行成功。

2.2 函数调用路径

在错误定位分析的过程中，文献[16]提出了软件错误关联的思想，即失效相关性。在此基础上，本文认为各个函数之间具有直接或间接的关联关系，一个有错误的函数往往会影响到与之关联的函数，对找到真正的错误根源会造成一定的干扰。为了解决这一问题，本文在函数调用路径（Function Call Path，FCP）的基础上进行错误定位，在一定程度上减少函数间的关联对错误定位造成的干扰。

以函数为基本单位，把程序的一次执行轨迹描述为一条函数调用路径，实际上是程序中基于函数调用并且结合数据流、控制流的一种函数执行路径的静态描述集合[17]。下面给出函数调用路径的相关定义。

定义5 函数调用路径：W 是基于函数调用的一条完整的程序执行路径，表示为Wi={vi0,vi1,…,vim}，路径中的相邻节点表示函数之间的调用或顺序执行关系。

整个程序的函数调用路径的合集组成函数调用路径图，与函数调用图不同的是函数调用路径图展示了函数之间的调用与顺序执行的关系，而函数调用图仅分析了函数之间的调用关系，忽略了控制流、数据流等信息。函数调用图与函数调用路径图的对比如图1所示。

图1中的源程序包括四个函数：main、f1、f2、f3。其中main函数调用了f1、f2、f3三个函数。图（a）中函数调用图没有考虑调用这些函数时的控制流信息，不能正确反映函数可能的执行路径，而图（b）中函数调用图可以更为准确地反映出该程序中存在的函数执行路径，路径1(main →f1→f2→end)和路径2(main →f1→f3→end)。

2.3 遗传算法

遗传算法（Genetic Algorithm，GA）是一类仿生型优化算法，由Holland[18]于20 世纪70 年代提出。该算法模拟生物界“优胜劣汰”的进化过程，是目前主流的启发式搜索算法之一。基于遗传算法的技术已经被用于解决函数优化、机器学习、人工智能等领域的问题。

图1 函数调用图与函数调用路径图对比

遗传算法的核心部分包括：（1）确定种群染色体编码；（2）生成初始种群；（3）构建适应度函数以及评估个体适应度；（4）利用遗传操作算子实现进化。其中，常用的编码方法有二进制编码、实数编码和符号编码等，遗传操作算子包括选择算子（select operator）、交叉算子（crossover operator）以及变异算子（mutation operator）[19-20]。

在预处理阶段，遗传算法根据实际问题的参数进行编码，组成染色体；其次，初始化一定规模的种群，由多个个体组成；然后，算法通过适应度函数衡量每个个体的优劣，采取选择、交叉、变异等遗传操作算子对种群进行演化搜索，直到满足终止条件；最后，输出得到的最优解。遗传算法的执行过程如图2所示。

3 错误定位方法FGAFL

3.1 方法框架

图2 遗传算法执行过程

本文针对多错误定位问题提出FGAFL 框架，将软件错误定位的研究粒度提升到函数级别，同时提出新的适应度函数，将基于函数调用路径得到的函数之间的关联度作为适应度函数的惩罚因子。FGAFL框架的主要研究内容包括三部分：一是对待测程序以及测试用例进行预处理；二是利用遗传算法搜索寻找最优候选种群；三是根据得到的最优解确定有错误的函数。

在预处理阶段，运行测试用例得到每个测试用例对函数的覆盖信息和运行结果，构建覆盖矩阵和结果向量，同时分析静态待测程序的函数调用路径，量化函数之间的关联关系；在遗传算法搜索阶段，采用二进制编码方式对问题进行参数编码，构建初始种群，使用选择、交叉和变异三种算子对种群进行操作，不断进行迭代演化，直到终止条件被满足，得到最优候选种群；在错误定位阶段，统计并分析得到的最优候选种群，对应到程序中具体的函数，得到最终的函数可疑度排序。

图3为FGAFL框架的整体流程。

图3 整体流程图

3.2 预处理过程

3.2.1 染色体编码方式

本文采用二进制编码方式，将个体C 表示为一个二进制向量C={c1,c2,…,cn}。其中n 为被测程序中可执行函数的个数，ci表示第i 个函数是否存在错误。若ci=0，则该被测程序中第i 个函数被认为不存在错误；若ci=1，则该被测程序中第i 个函数被认为存在错误。

例如，有个体C={0,1,0,0,0,0,1,0,0,0}，表示被测程序中有10个可执行函数，其中第2个函数和第7个函数被认为存在错误，其余函数不存在错误。

3.2.2 函数关联度计算

计算函数之间的关联度有以下两个步骤：首先，分析程序中的数据流和控制流的逻辑关系，得到函数调用路径图；其次，结合函数调用路径图和覆盖矩阵、结果向量，分析并量化各函数间的关联关系。

本文选择Gini 指数作为量化函数调用序列中目标函数与运行结果之间联系的指标。一般来说，Gini指数用于衡量数据的不纯度或者不确定性，Gini 指数越大，表示数据集的纯度越小。举例说明(f1调用函数f2、f3)，如表1所示。

表1 函数调用的关联关系示例

表1中，第二行第二列表示覆盖该调用序列f1→f2的失败测试用例的个数为5，第三行第二列表示覆盖该序列的成功测试用例的个数为35。计算Gini指数如下：

定义函数f1基于函数调用的关联关系量化后的特征值为relation(f1)，可以得到：

3.2.3 适应度函数

在基于程序频谱的软件错误定位中，Tarantula、Ochiai以及DStar等可疑度公式主要针对程序中含有一个错误的情况。文献[21]在Ochiai 公式的基础上，提出了Multi-Ochiai公式作为遗传算法中的适应度函数。本文在此基础上提出FMD*可疑度公式，表示为：

φ(C)是个体C 解释失败测试用例的能力，即若一个失败测试用例经过了个体C 中被认为有错的函数，则说该个体可以解释这一失败测试用例。个体C 能解释的失败测试用例越多，则该个体越可疑。φ(C)可以表示为[14]：

在该公式中，函数λ(x)为示性函数：

类似于φ(C)，P(C)表示的是个体C 解释成功测试用例的能力。若某个函数被越多的成功测试用例运行覆盖，则该函数有错的可能性越小，即个体C 的可疑度与该个体能解释的成功测试用例的数量成反比。P(C)可以表示为：

Q(C)表示个体C 中被认为有错的函数未被失败测试用例覆盖的情况。如果一个函数没有被失败测试用例运行覆盖，那么该函数有错的可能性较低。Q(C)表示为：

其中，μ(x)为另一个示性函数：

该函数的含义为个体C 中被认为有错的个体只要未被所有的失败测试用例运行覆盖，就将μ(x)的值置为1。

影响因子R(C)表示了函数之间的调用关系，即为上一节中得到的对函数调用之间的关联关系的量化。R(C)表示为：

该公式表示对个体C 中被认为有错的函数计算函数调用关联关系的特征值，并求和。

3.3 遗传算法获得最优种群

3.3.1 初始化种群

高质量和多样性的初始种群能够提高遗传算法的收敛速度以及最终结果的质量，本文结合贪心算法Additional-Greedy（AG）[22]生成初始种群。生成初始种群P 的算法流程如下所示。

该方法的输入包括失败测试用例覆盖矩阵MF以及种群的规模NP。对于有n 个函数的程序首先生成n个个体，同时每个个体只有一个函数被认为有错，且被认为有错的函数位置不相同（即生成n 阶单位矩阵），如图4所示：

图4 生成n 个个体

利用失败测试用例覆盖矩阵MF以及图4 中生成的n 个个体，计算每个个体C 解释失败测试用例的能力。如果φ(C)=| TF|，说明个体C 可以解释所有的失败测试用例。如果φ(C)＜| TF|，则需要对个体C 表示的函数错误分布情况进行修正。利用AG 算法修改个体C的错误分布情况，将C 中一个或多个为0的基因位变为1，增加个体中被认为有错的函数个数，使修正后的个体能够解释所有失败测试用例。对个体进行修正时，需要满足以下几个条件：（1）优先选择能够尽可能多地解释失败测试用例的函数，将其位置变为1；（2）尽可能地选择还未被认为有错的函数进行修改；（3）保证修改的函数个数尽可能地少。具体算法过程是：对于一个不能解释全部测试用例的个体C 来说，选择能够解释最多失败测试用例的函数fx加入到个体C 中；将fx对应的位置置为1 后，若个体C 能够解释所有失败测试用例，则过程结束，若不能，则需要再选择其他解释失败测试用例能力强的函数加入个体C ，直到该个体能够解释所有的失败测试用例。

获得一个有n 个个体的种群后，需要对种群的规模进行调整。若n ＜NP，则随机复制NP-n 个个体补充到初始种群中，使种群的规模达到预定的NP；若n ＞NP，则选择适应度值较高的NP个个体组成初始种群。

该初始种群生成算法只需挨个检查图4 中的n 个个体，判断解释失败测试用例的能力即可。该算法在最坏情况下是n 个个体均不能解释全部失败测试用例，需要对所有个体进行修正，时间复杂度为T(n)=O(n2)；最好情况是均可以解释全部失败测试用例，不需要对其修正，时间复杂度为T(n)=O(n)。因此，该初始种群生成算法的时间复杂度为T(n)=O(n2)。

通过AG过程构建初始种群：一是保证初始种群中的每个个体C 都能够解释所有失败测试，具有较高的适应度；二是使个体C 中被认为有错的函数的数量尽可能少；三是使不同个体之间有不同的错误分布情况，保证初始种群的多样性。

3.3.2 遗传算子

得到初始种群之后，需要利用遗传操作算子迭代优化，产生优质的个体组成新种群，主要包括选择、交叉和变异三种遗传算子。

（1）选择算子

选择算子（Selection Operator）模拟了自然界的自然选择。适应度高的个体能够以较大的概率被选择，直接遗传到下一代或者进行后续的交叉、变异操作。

本文将轮盘赌选择策略作为选择算子，基本思想是个体被选择的概率与其适应度函数的值成正比。假设种群大小为n，个体i 的适应度为Fi，则i 被选中遗传到下一代种群的概率为：

1771年10月间，叶卡德琳娜二世颁布了“关于废除土尔扈特汗国的命令，同时取消了‘汗’和汗国总督的称号”。(参见《卡尔梅克苏维埃社会主义自治共和国史纲》)由于这项命令的实施，建立于伏尔加河流域一个半世纪的土尔扈特汗国已不复存在；

（2）交叉算子

交叉算子（Crossover Operator）通过交换两个个体部分位置的信息，组合出新的个体遗传到下一代种群。本文采用均匀交叉（Uniform Crossover）策略，使两个父代个体的每对等位基因点都能够以一定的概率Pcro进行交换。

举例说明，选择两个个体被作为父代个体进行交叉：

随机生成一组屏蔽字Mask，与个体长度等长。对于其中的每一位mi，若mi=1，则父代个体对应的基因位进行交换，遗传到子代个体；若mi=0，则子代个体分别继承对应的父代个体的基因值。以如下屏蔽字为例：

最后，经过均匀交叉后得到子代的两个个体为：

（3）变异算子

变异算子（Mutation Operator）是产生新个体的辅助方法，是指将个体中某些编码位上的基因值，用该编码位置的其他等位基因来替换。一般来说，变异概率Pmut的建议取值范围为0.000 1～0.5。

针对本文的问题，选择较低的变异概率Pmut进行变异。同时，为了避免个体中的基因从0无限制地变异为1，设置参数para 控制个体中1的数量。当个体中错误的数量超过para 时，个体中的基因不再从0变异为1，使得个体不再通过变异产生更多的错误位置。

3.3.3 重插入与终止条件

在本方法中，设置迭代次数Ngen作为终止条件。在得到初始种群之后，迭代进行遗传算子运算以及重插入操作，直到循环的次数达到Ngen，迭代得到最终的最优候选种群，进行下一步确定软件错误位置的操作。

3.4 确定错误位置

经过一系列遗传操作算子的计算操作得到最优候选种群之后，需要将得到的错误分布种群转换为对应的函数可疑度的排名。若个体的适应度值较高，说明该个体代表的程序错误分布较为可疑。首先，比较最优候选错误种群中每个个体的可疑度，按从高到低的顺序进行排列。然后，根据得到的有序排列的种群，统计所对应的函数的可疑度情况。适应度值排名越靠前的个体中，同一位置的函数被认为含有错误的次数越多，则该函数实际有错误的可能性就越大。以如下最优候选错误分布种群为例：

上述种群中按个体的适应度由高到低、从上往下排列，排序越靠前的个体中被认为有错的函数的可疑度越大。在第一个个体中编号为2、6、9的函数被认为有错，同时参考种群中其他个体的分布情况，若分布情况相同，则随机排序。该例中，编号为6的函数在前3个个体中均被认为有错，该函数的可疑度最高，其次为编号为2的函数。因此，通过该种群最终得到的函数可疑度排序为＜e6,e2,e9,e1,e4,e3,e7,e5,e10,e8＞。

4 实验评测

为证明FGAFL 方法的有效性，分别针对单错误和多错误情况设计实验。

4.1 实验数据与评测指标

4.1.1 实验数据

本文选取来自SIR（http：//sir.unl.edu/portal/index.php）网站的测试程序Siemens Suite作为实验数据。Siemens Suite被视为评估错误定位技术有效性的典型数据[23]，包含7个C语言程序，代码行数最多有565行，可执行代码行数最多有203行，属于小规模程序，分别是printtokens、printtokens2、replace、schedule、schedule2、tcas、totinfo。该测试套件中的每个程序都包含一个正确版本和多个错误版本，且大多数的错误版本中只有一个错误，因此选择在printtokens、replace、schedule 和tcas 程序中植入多个错误，用于多错误定位效果的验证。本文实验评测程序的主要信息如表2所示。

表2 Siemens Suite程序的主要信息

4.1.2 评测指标

本文在Abreu 等人[4]提出的评测标准的基础上将EXAM 作为评测指标，定义为发现程序中所有错误时需检查的代码行数占总程序中代码行数的百分比，具体公式为：

其中，exami表示检测到第i 个错误需要检查的代码行数，n 表示程序中错误总个数，N 表示程序中总代码行数。该评测指标适用于单错误定位和多错误定位，当EXAM用于评价单错误定位问题时，可以表示为EXAM=exam/N×100%，即为发现程序中错误需要检查的代码行数占总代码行数的百分比。

4.2 实验内容与结果

本文实验内容主要分为两方面：一是验证在适应度函数FMD*的指数（*）不同取值的情况下，FGAFL 方法的定位效果；二是将FGAFL方法与经典方法进行对比。

4.2.1 不同指数（＊）的影响

在本节中，针对适应度函数FMD*不同的指数（*）进行实验，*的取值范围为1～30，增量为1，实验结果如图5所示。

图5 FGAFL在不同指数（*）数值下的错误定位效果

从图5 中可以观察到，随着指数（*）值逐渐增大，EXAM 值逐渐减小并最终趋于稳定，即找到程序中的错误需检查的代码量随着指数（*）的增大而减少。同时，在单错误定位情况下的EXAM 比多错误定位情况下更早地趋于稳定。由此可以认为，前期指数（*）增大对单错误定位效果影响较大，可以较快地提高定位效果，而对于多错误定位则需要指数（*）增大到一定程度才会较为明显地提高定位效果。多错误定位与单错误定位不同的是，一般程序中的多个错误会跨越多条语句或多个函数，需依次检查排名较为靠前的函数，在确定第一个错误的位置后仍需检查后面的函数，直到发现所有的错误为止。而这些被检查的函数中可能没有错误但依然被较多的失败测试用例经过或较少的失败测试用例未经过，因此需要赋予φ(C)更多的权值才能较为明显地提高定位准确性。

4.2.2 与其他方法的对比实验

针对单错误和多错误程序进行实验，选取经典的错误定位方法Ochiai、Tarantula 和DStar2 进行对比。这三种方法均是通过构造可疑度公式，分析程序运行时的覆盖情况和运行结果，得到程序中每一个实体有错误的可能性（即可疑度）。

实验设置适应度函数FMD*的指数（*）为2 和10，表示为FMD2、FMD10。实验结果如图6所示。

图6 对比实验结果

从图6中可以看出，无论是单错误定位还是多错误定位，FGAFL（图中表示为FMD2、FMD10）、Ochiai 和DStar2 方法均明显优于Tarantula。图6（a）是针对单错误定位得到的实验结果，FGAFL 的整体定位趋势与其他方法类似，且在检查程序中的语句为30%时，FMD10能检查出的错误数更接近于100%，FMD2 的定位效果要略差于FMD10。针对多错误定位得到的实验结果为图6（b），可以看出FGAFL、DStar2 方法要明显优于Ochiai 和Tarantula 方法，FMD2 与DStar2 的定位效果类似，但是FMD2要早于DStar2检查到全部错误。从检查的语句为40%开始，FMD10 的定位效果都要优于其他方法。

另外，统计了FGAFL 方法与Ochiai、Tarantula 和DStar2方法在各程序版本上的平均执行时间，经多次实验取得平均值。这四种方法均需要执行测试用例收集程序频谱信息，因此只需关注错误定位部分的执行效率，如表3所示。其中Ochiai、Tarantula和DStar2方法只需计算程序中各个语句的可疑度即可，执行时间较短，然而这三种方法在多错误定位中效果不佳，且理论上应多次运行逐个定位。虽然执行时间短，但需要花费较多的人工时间去确定错误的位置。本文提出的FGAFL方法需要通过遗传算法迭代寻优，但是需要检查的代码量比较少，提高了人工检查错误的效率。

表3 执行时间比较 s

5 结束语

本文基于函数调用路径的知识，在遗传算法的基础上提出了一种函数级别的软件错误定位方法，主要包括以下研究内容：

（1）将软件错误定位问题转化为一类组合优化问题，利用改进的遗传算法搜索求解，结合错误定位的特点对生成初始种群的方法进行优化。

（2）结合函数调用路径技术，在已有的适应度函数上进行改进，提出新的适应度函数FMD*，保证在搜索寻优过程中可以有效地衡量个体优劣。

（3）将函数作为错误定位的研究粒度，可以有效地缩短个体的长度，降低搜索空间的规模，提高搜索效率。

（4）选取Siemens Suite 作为实验数据，设计评测指标并进行实验，同时选择经典的错误定位方法进行定位效果的对比。实验结果表明，本文提出的方法FGAFL具有可行性和有效性，且有较高的精度和效率。

除此之外，在本文方法的基础上仍有一些值得关注的问题需要进行后续的研究：

（1）尝试将本文方法应用到更大型的程序中进行实验，包括Linux 系统下运行的程序以及不同语言的程序。

（2）为了进一步提高本文方法的性能，尝试将遗传算法与其他搜索算法结合，或者选择不同的搜索算法进行实验。

（3）进一步考虑将函数粒度的研究与语句粒度相结合，做到先定位到函数后定位到语句，对函数中的语句进行可疑度排序，进一步提高定位错误的效率。