一种嵌入式基础软件代码分支覆盖测试数据遗传搜索方法

摘要

本发明涉及计算机信息处理技术领域，具体涉及一种嵌入式基础软件代码分支覆盖测试数据遗传搜索方法，该方法将测试数据寻找过程转化为基于遗传算法的搜索和优化过程，适应度函数以被测软件的分支谓词为基础，测试数据能够遍历被测软件的所有分支，而且测试数据非常靠近输入子空间的边界。而交叉变异是从一个点的群体而不是从一个单一点进行搜索，因而落入假峰的概率比点到点的转移搜索大大减少了，数据遗传搜索效率高。

说明书

技术领域

本发明涉及计算机信息处理技术领域，具体涉及一种嵌入式基础软件代码分支覆盖测试 数据遗传搜索方法。

背景技术

遗传算法（Genetic Algorithm）是美国的Holland在1975年首先提出来的，它是一种基 于自然选择原理和自然遗传机制的搜索寻优算法，它模拟自然界中的生命进化机制，在人工 系统中实现特定目标的优化。它的操作对象是一群染色体（称为个体），即种群（Population）。 这里每个染色体都对应于问题的一个解。遗传算法从初始种群出发，采用基于适应度比例的 选择策略在当前种群中选择个体，使用交叉和变异来产生下一代种群。如此一代一代地演化 下去，直到满足期望的终止条件。遗传算法在问题解空间的表示上，是用单一的染色体表示 问题的一个潜在的可能解，运行在一个染色体群体上的进化过程和通过一个潜在解空间的搜 索相对应。

嵌入式基础软件是一种安全关键软件，为保证其质量和可靠性，一般需要进行软件代码 逻辑覆盖测试。逻辑覆盖又可分为语句覆盖、分支覆盖、路径覆盖等。按分支覆盖准则进行 测试是指设计若干组测试数据，运行被测程序，使得程序中每个判断的取真分支和取假分支 至少经历一次，即判断的真假值均曾被满足。

根据域测试（Domain Testing）原理，被测软件的输入空间（即域）可分为不同的子空间， 而子空间的划分是由被测软件中的分支谓词决定的。靠近子空间边界的测试数据能够更有效 地发现被测软件的路径错误和计算错误。因此，分支覆盖测试数据选择的目标是，以少量测 试数据使被测软件的所有分支都被执行到，并且这些测试数据尽可能地接近子空间的边界。

由于嵌入式基础软件的规模较大，复杂程度较高，开发分支覆盖测试数据需要花费大量 的人力、物力，采用自动化的手段可以有效地提高测试数据搜索的效率和质量。许多传统自 动化方法处理搜索空间的一个单点。例如爬山法，它使用迭代改进法，每次迭代从现时点的 领域选择一个新的点。显然，在多峰搜索空间中，它易于陷入假的局部峰值。

发明内容

针对现有技术的不足，本发明提供一种嵌入式基础软件代码分支覆盖测试数据遗传搜索 方法，本发明测试数据遗传搜索方法可以方便地加以扩展，以支持不同的输入数据类型、复 杂的分支谓词、各种分支和循环程序结构。

本发明的目的是采用下述技术方案实现的：

一种嵌入式基础软件代码分支覆盖测试数据遗传搜索方法，其改进之处在于，所述方法 包括下述步骤：

（1）生成随机数；

（2）选择初始种群；

（3）按照参数编码方式对所述初始种群的个体串映射成实际参数值，并传递给被测软件；

（4）确定适应度函数；

（5）交叉变异对测试数据进行改进，形成新一代更优种群；

（6）循环进行步骤（1）-（5），直至找到覆盖所有嵌入式基础软件分支的目标参数值， 测试数据遍历被测软件的所有分支，结束该搜索过程。

其中，所述步骤（2）中，按照嵌入式基础软件参数要求选择初始种群。

其中，所述步骤（3）中，当初始种群的个体串映射成实际参数值，并传递给被测软件时， 驱动被测软件运行；所述被测软件是指嵌入式基础软件。

其中，所述步骤（4）中，根据被测嵌入式基础软件代码确定适应度函数，所述适应度函 数以嵌入式基础软件代码的分支谓词为基础。

其中，为获取嵌入式基础软件代码分支覆盖测试数据对被测软件进行插装。

其中，所述步骤（5）中，所述交叉变异是从一个点的群体开始进行。

其中，所述方法为自适应的测试数据搜索方法。

与现有技术比，本发明达到的有益效果是：

嵌入式基础软件代码分支覆盖测试数据遗传搜索方法比其它方法具有更高的搜索效率。 本发明的测试数据搜索方法以分支谓词为基础，测试数据能够遍历被测软件的所有分支，而 且测试数据非常靠近输入子空间的边界。为了优化适应度函数，通过遗传算法一代一代地不 断修改测试数据，形成了一种自适应的测试数据搜索方法。本方法是从一个点的群体而不是 从一个单一点进行搜索，而许多传统方法处理搜索空间的一个单点，因而本方法落入假峰的 概率比点到点的转移搜索大大减少了，具有更好的收敛性和更高的搜索效率。

本测试数据搜索方法可以方便地加以扩展，以支持不同的输入数据类型、复杂的分支谓 词、各种分支和循环程序结构。

附图说明

图1是本发明提供的嵌入式基础软件代码分支覆盖测试数据遗传搜索方法流程图；

图2是本发明提供的IF-THEN-ELSE控制流树及原被测软件示意图；

图3是本发明提供的被测软件插装举例示意图；

图4是本发明提供的被测软件控制流树。

具体实施方式

下面结合附图对本发明的具体实施方式作进一步的详细说明。

本发明提供的嵌入式基础软件代码分支覆盖测试数据遗传搜索方法流程如图1所示，该 方法包括下述步骤：

（1）生成随机数；

（2）选择初始种群；

（3）按照参数编码方式对所述初始种群的个体串映射成实际参数值，并传递给被测软件；

（4）确定适应度函数；

（5）交叉变异对测试数据进行改进，形成新一代更优种群；

（6）循环进行步骤（1）-（5），直至找到覆盖所有嵌入式基础软件分支的目标参数值， 测试数据遍历被测软件的所有分支，结束该搜索过程。

适应度函数以嵌入式基础软件代码的分支谓词为基础，整个搜索过程从生成初始种群开 始，然后按照参数编码方式将种群中的个体位串映射成实际参数值，并传递给被测软件，驱 动被测软件的运行。根据被测嵌入式基础软件代码的特点确定适应度函数，被测软件运行时 计算出适应度函数值，评估每组测试数据的适应度，适应度越高说明测试数据与预期效果越 接近，之后利用交叉、变异等基本算子对测试数据进行改进，形成新一代更优种群，如此往 复，直至找到覆盖所有分支的目标参数值，测试数据能够遍历被测软件的所有分支，就可以 结束该搜索过程。

下面结合IF条件语句，说明基于遗传算法的分支覆盖测试数据搜索策略。图2显示了一 个简单的IF-THEN-ELSE条件的例子。C_N代表分支谓词，S_N+1（对应于节点（N+1））和S_N+2（对应于节点（N+2））分别为待执行的语句序列。如果C_N为真，执行S_N+1，否则执行S_N+2。

假设C_N为A=B，A和B为整数（也可能是输入参数的复杂函数）。为了执行节点（N+1） 中的S_N+1，A必须取值B。为执行节点（N+2）中的S_N+2，A可以取不等于B的任何值（A ≠B）。但是A的优先取值为（B+1）和（B-1），因为这两个值紧邻子空间边界，更有利于发 现程序错误。从遗传算法角度来说，对于节点（N+1），A值与B越接近，适应度（Fitness） 就越高。为了获取分支覆盖测试数据需要对被测软件进行插装，具体如下：

if C_N then

CHECK_BRANCH(NODE_NUMBER);

LOOKING_BRANCH(NODE_NUMBER_{_SIB},DATA1_{_SIB},DATA2_{_SIB});

S_N+1

else

CHECK_BRANCH(NODE_NUMBER_{_SIB});

LOOKING_BRANCH(NODE_NUMBER,DATA1,DATA2);

S_N+2

end if；

CHECK_BRANCH只有一个整数类型的输入参数，即节点号NODE_NUMBER。 CHECK_BRANCH记录了该节点是否执行过。如果已经被执行，保存有关的测试数据。这样， 可以开始为下一个未遍历的节点生成测试数据。

LOOKING_BRANCH的输入参数有3个，包括兄弟节点号NODE_NUMBER_{_SIB}。如果兄 弟节点尚未被遍历，LOOKING_BRANCH计算兄弟节点的适应度。looking变量保存下一个 未遍历节点的节点号，LOOKING_BRANCH根据变量looking了解兄弟节点是否为需要遍历 的下一个节点。

DATA1和DATA2的值仅取决于分支谓词函数，不需要其它信息。在上述例子中，执行 节点（N+1）的条件为C_N（A=B），此时DATA1的值为A，DATA2的值为B。对于节点（N+2）， DATA1不变，而DATA2采用(B-1)，如图3所示，在使用“>”的情况下（例如IF A>B THEN）， 取真分支的适应度函数形式为FITNESS_FUNCTION(A，B+1)。在这里选择（B＋1）与A配 对，因为它是与A最接近的数据。反之，如果使用“IF A<B”，则选择（B-1）。

实施例

下面以一个简单的例子，说明嵌入式基础软件代码分支覆盖测试数据遗传搜索过程，被 测软件的控制流树及插装形式如图4所示。在此例子中，遗传算法的主要参数设置如下：生 存概率Ps=0.5，变异概率P_m=0.1，采用单点交叉。

原被测软件IF条件语句如下：

if A≤B then

put(“node 2”);

if A=B then

put(“node 3”);

else

put(“node 4”);

end if；

else

put(“node 5”);

end if；

经过插装的被测软件IF条件语句如下：

if A≤B then

CHECK_BRANCH(2);

LOOKING_BRANCH(5,A,B+1);

if A=B then

CHECK_BRANCH(3);

LOOKING_BRANCH(4,A,B-1);

else

CHECK_BRANCH(4);

LOOKING_BRANCH(3,A,B);

end if；

else

CHECK_BRANCH(5);

LOOKING_BRANCH(2,A,B);

S₃

end if；

（1）第一代

表1显示了第一代种群的4个成员，它们是由测试数据生成工具随机生成的。其中P_i表 示父代种群（Parent Population）的成员，A和B为输入变量值，looking为待执行节点的编号， Path表示被当前测试数据（A和B）遍历的节点。chromosome显示的是二进制形式的测试数 据，每个测试数据通过5比特表示，因此染色体长度为10比特，前5比特表示输入数据A， 后5比特表示输入数据B。f_i为根据测试数据和待遍历节点计算的适应度，适应度较高的群组 成员进入下一代的生存概率更大，F_t代表该种群的总适应度。

表1第一代的父代种群

第一组测试数据（P₁）输入被测软件后，待执行的第一个节点是节点2（looking值为2）。 对于节点2，其适应度函数为f＝1/(|A-B|+0.01)²，因为遍历条件A≤B的边界测试数据为A=B。 该适应度函数保证了A和B在数值上相互接近的测试数据具有更高的适应度。第一代测试数 据执行了节点1、2、4、5，仅有节点3没有执行。当looking节点被某测试数据执行后（在 此例子中节点2被第一组测试数据P₁执行），仍然要计算其余测试数据对于looking节点的适 应度，但不生成子代种群（Offspring Population）。

（2）第二代

第一代种群作为搜索遍历节点3测试数据的起点，见表2。节点3的访问控制谓词恰好 与节点2相同，因此表2中的第二代测试数据及其适应度与表1相同。在第二代种群中，looking 节点（节点3）没有被遍历，因此遗传算法需要通过交叉和变异生成后代，如表3所示，其 中k代表交叉点，变异的基因（比特）以斜体表示。

表2第二代的父代种群

表3第二代的子代种群

在表3中，通过交叉、变异新产生的子代测试数据以O_i表示，其父代以P_i表示。这些父 代成员是随机选择的。在重组过程中，两个父代成员生成两个子代成员。在子代种群中，O₃ 与节点3的距离与P₁相同，二者的适应度也相同（0.0278）。在子代种群中，O₃的适应度最 高，因此生存下来进入下一代种群的概率也比较高。但是子代种群的总适应度F_t低于父代种 群，这说明从一个种群到下一种群在整体没有得到改善。

现在我们有两个种群（父代种群和子代种群），它们各有4个成员，将从这8个成员产生 下一代种群。因为生存概率P_s为0.5，平均来说下一代种群由这两个种群的各2个成员组成。 表4显示了下一代4个成员的选择过程。对应于新一代种群的每个成员，生成一个0到1之 间的随机数，如表4中第二行所示。如果随机数大于0.5（即大于Ps），选择父代种群，否则 选择子代种群。完成种群选择以后，生成另一个随机数，选择种群中哪个成员生存进入下一 代。例如，选择下一代种种群成员member1的过程如下，第一次生成的随机数为0.678，这 意味着选择父代种群。生成的下一个随机数是0.257，因此选择父代种群中的P₁。重复这个过 程，得到下一代种群的其它3个成员。新一代显示在表5的上部。

表4子代种群的生存情况

（3）第三代

整个过程重复进行，直到所有节点都被遍历。表5-表7给出了第三代种群。通过F_t可以 看出，第三代中的父代种群整体适应度高于第二代。在通过交叉和变异生成的子代种群中， 测试数据O₁距全局最优仅3个整数单位（11-8=3）。O₁取得高适应度，因此得以两次生存下 来进入下一代。

表5第三代种群（一）

表6第三代种群（二）

表7第三代种群（三）

（4）第四代

表8-表10给出了第四代种群，在其中的子代种群中，两组测试数据（O₁和O₄）接近于 达到目标。实际上O₄更接近全局最优，因此也得到更高的适应度。从第三代到第四代，整体 适应度F_t提高了280％。

表8第四代种群（一）

  P_i  A   B   looking   Path   chromosome   f_i  F_t  P₁  8   11   3   1，2，4   00010 11010   0.1111   0.27   P₂  8   11   3   1，2，4   00010 11010   0.1111   P₃  8   15   3   1，2，4   00010 11110   0.0204   P₄  0   -6   3   1，5   00000 01101   0.0278

表9第四代种群（二）

表10第四代种群（三）

（5）第五代

表11-表12给出了第5代种群。一般来说，总适应度F_t会随着代数的增加逐步提高。在 第五代种群中，测试数据O₁（A=B=11）遍历了节点3。随着最后一个节点被遍历，测试数据 搜索过程宣告结束。

表11第五代种群（一）

表12第五代种群（二）

本发明提供的方法是从一个点的群体而不是从一个单一点进行搜索，而许多传统方法处 理搜索空间的一个单点，因而本方法落入假峰的概率比点到点的转移搜索大大减少了，具有 更好的收敛性和更高的搜索效率。

最后应当说明的是：以上实施例仅用以说明本发明的技术方案而非对其限制，尽管参照 上述实施例对本发明进行了详细的说明，所属领域的普通技术人员应当理解：依然可以对本 发明的具体实施方式进行修改或者等同替换，而未脱离本发明精神和范围的任何修改或者等 同替换，其均应涵盖在本发明的权利要求范围当中。