IR46智能电表软件白盒测试的基路径集生成方法研究

樊 博 梁 飞 黄吉涛 周媛奉 胡婷婷 郭林明 王文龙

1(国网宁夏电力有限公司电力科学研究院 宁夏 银川 750002)

2(四川大学电气工程学院 四川 成都 610065)

3(河南许继仪表有限公司 河南 许昌 461000)

0 引 言

智能电表是泛在电力物联网感知层中的关键器件。据国家电网的统计，目前60%智能电表的现场故障是由软件缺陷所引起的。作为新一代的智能电表，IR46智能电表[1]还需进行芯片参数整定、整机验证等测试。而智能电表作为典型的嵌入式产品，许多通用的测试软件并不能完全契合其要求[2]，为此本文提出白盒测试中一种新的基路径集生成方法。

白盒测试基于软件内部结构设计测试案例，能够充分测试程序内在逻辑，发现代码层面的错误。而基路径测试是语句覆盖率很高的白盒测试方法，发现错误的能力很强。基路径测试的不足是测试效率较低，为解决这个问题就需要改进基路径集生成方法[3]。现阶段，基路径集生成方法主要分为两种：基于图的方法和自动生成方法。基于图的方法是指在控制流图的基础上使用某种搜索算法来求取基路径集，该方法在处理复杂程序时效率较低，如基于图广度优先搜索[4]、图深度优先搜索[5]传统方法和基于元启发式算法的克隆选择算法[6]、遗传算法等[7]。自动生成方法使用某种方法识别程序结构，自动生成基路径集，如基于模型代数[8]、基于代码识别[9]等方法。该方法省去了程序到控制流图的转换工作，但要求程序符合规定的编程规范，限制了其在非结构代码上的应用。

以上方法没有从语句层面分析路径的重要性，不能指导测试顺序。IR46智能电表控制软件在某些情况需要进行快速测试，详尽的软件测试是不合理的，而通过识别错误倾向性较高的基路径，可以提高测试效率从而达到快速测试的目的。

因此本文从两个方面来提升测试效率。首先量化语句的错误倾向以确定路径重要性：引入语句的错误源(sources of errors，SOE)分析，通过赋予语句错误倾向权重(error propensity weight，EPW)来构建程序的加权有向图，依据路径的EPW决定测试优先级。然后改进基路径搜索算法：改进具有模型简单、效率高和鲁棒性强等优点[10]的二进制蝙蝠算法(Binary Bat Algorithm，BBA)得到OBBA(Optimized Binary Bat Algorithm)并将其用于路径搜索。仿真结果表明，该方法可以有效生成带EPW优先级的基路径集，所引入的SOE分析可以指示程序的错误倾向，OBBA也缩短了基路径生成的迭代周期，有助于提升白盒测试的效率。

1 基路径测试及SOE量化

1.1 基路径测试

基路径测试的思想是从可执行软件路径里找到一组能够完成软件测试任务且规模尽量小的基路径，以简化测试。目前被广泛应用的基路径集生成框架是McCabe度量法[11]。McCabe将程序路径视为向量空间里的向量，根据任何向量可以由基来线性表示的原理，就可以用基路径的测试来替代所有路径的测试。基路径测试的步骤如下：

1) 将待测程序转化为控制流图。

2) 根据控制流图的圈复杂度得到基路径的数目，定义为：

C(G)=m-n+2q

(1)

式中：m和n分别为控制流图的边和节点的数目；q为强连通分量个数，对于只有一个入口和一个出口的程序，q通常取1。而基路径数目N等于C(G)。

3) 使用某种搜索算法得到一组基路径，并验证是否满足基路径集三个条件：

(1) 基路径间至少有一条边是不同的。

(2) 基路径集能够覆盖所有的边。

(3)其余路径可以由基路径线性表示。

4) 设计测试案例，使每条基路径至少执行一次。

1.2 SOE量化

McCabe度量法没有衡量路径的错误倾向，不能区分基路径的重要性，为此本文对路径进行加权，以得到错误针对性更强的基路径集。IR46智能电表程序中的不同程序结构所包含的SOE各异，需要进行SOE量化。图1以循环结构为例说明SOE分析过程。可以看到该程序至少有4个SOE，将错误发生概率视为一致，且不考虑错误发生的后果，则EPW的值为wEPW=4。在实际应用中，可以将IR46智能电表的一些信息如语句重要性、风险分析、运行环境等以权值的形式添加到理论EPW中，以适应不同的应用环境。参照文献[12]对其他的程序结构做类似的SOE分析，再根据SOE数目及引入SOE的变量等，得到了基本程序结构的EPW，如表1所示。

图1 循环结构SOE分析示例

表1 基本程序结构SOE量化

续表1

2 改进二进制蝙蝠算法

2.1 二进制蝙蝠算法

蝙蝠算法模拟蝙蝠发射声波觅食的行为来进行全局最优解求取，其寻优效率高且原理简单，被广泛用于优化问题。基路径集生成可视为一个离散的组合优化问题，搜索空间是一个二进制离散空间，组合的变化通过0和1之间的翻转来实现。为此需要使用离散的二进制蝙蝠算法[13]，即BBA。BBA的思想是将蝙蝠的速度映射为蝙蝠位置改变的概率，能对每一个二进制位进行优化。

蝙蝠位置(x)是BBA的解，通过不断调节速度(v)、频率(f)两个属性来控制飞行，迭代地搜索最优解。而响度(A)和声波发射率(r)用于平衡局部搜索和全局搜索。其具体算法流程如下：

(1) 初始化。设置最大迭代数tmax、蝙蝠数目npop和频率上下界等参数，然后使用二进制编码对蝙蝠进行随机初始化，设置t=0。

(2) 按照式(2)、式(3)更新蝙蝠的频率和速度。

fi=fmin+(fmax-fmin)β

(2)

(3)

(3) 飞行产生新位置。使用式(4)的V型转换函数[13]将蝙蝠的速度映射为位置的二进制位改变的概率，并使用式(5)更新位置。

(4)

(5)

(4) 若随机数rand1

(6)

(5) 若随机数rand2

Ai(t+1)=αAi(t)

(7)

ri(t+1)=ri(0)[1-exp(-γt)]

(8)

式中：α是响度衰减系数；γ是发射率增长系数；ri(0)为初始发射率。

(6) 根据蝙蝠群体的适应度，更新全局最优位置。

(7) 令t=t+1，并迭代执行步骤(2)-步骤(6)直至求得基路径或达到最大迭代数。

2.2 参数自适应的二进制蝙蝠算法

BBA在避免局部优化上和收敛速度上较一些优化算法如粒子群优化(Particle Swarm Optimization,PSO)和遗传算法有一定的优势[13]。然而其在某些应用场景下还是会出现过早收敛的情况[14]，为此本文提出OBBA，OBBA从提高种群的多样性、平衡局部搜索和全局搜索两个方面来优化。

BBA属于仿生优化算法，需要考虑到周围环境的影响，比如惯性。为此本文引入惯性权重(w)来缓解BBA在迭代后期种群多样性不足的问题。参考PSO中速度和权重的关系[15]，得到的惯性权重迭代函数和优化后的速度更新函数如式(9)、式(10)所示。

(9)

c2(xbest-xi(t))ξ

(10)

在平衡搜索策略方面，将式(7)的参数α进行了修改。参数α与模拟退火算法中的冷却因子相类似[16]，值较小时倾向于局部搜索而较大时倾向于全局搜索，为了平衡两者，提出α的动态更新公式：

(11)

OBBA混合使用两种速度更新方式，设置一个概率阈值Pc，若随机数rand3

3 仿真分析

3.1 可行性验证

本文算法可分为三部分：待测程序预处理，SOE量化和利用OBBA搜索基路径集。本文算法流程如图2所示，其中：N为基路径数目；gmax是搜索一条基路径的最大OBBA执行次数；tmax为OBBA的最大迭代数；npop为蝙蝠数目；Fi为蝙蝠i的适应度；pend为控制流图的出口节点。下文将详述这三部分，并使用图3所示案例来进行可行性验证。

图2 本文算法流程

图3 案例程序控制流图

(1) 在程序预处理阶段，首先通过分支关键字识别的方式分析代码的分支信息，得到语句节点间的连接关系、语句的类型、节点数目、边的数目等信息；然后根据McCabe度量法计算圈复杂度，得到基路径数目N。而在程序较大的时候，可以将控制流图中一些非关键的且满足din+dout<3(din为节点入度，dout为节点出度)的节点合并以得到简洁高效的DD-graph(DDG)[5]。本文使用由首尾节点组成的连接矩阵来表示节点间的连接关系，表2的1、2列为案例程序的连接矩阵，而根据式(1)可算得案例程序的N为5。

表2 案例程序的输入矩阵

(2) 在SOE量化阶段，根据程序的预处理结果，由表1确定每条边的SOE并计算得到对应的wEPW，wEPW满足叠加性，若节点进行了合并需将其累加。案例程序包含了函数调用、if语句和逻辑操作等SOE，依照表1量化后可以得到如表2的第3列所示的wEPW向量。

(3) 在OBBA搜索基路径集阶段，首先需要给蝙蝠编码及确定适应度函数。本文提出如图4所示的编码格式，其中 ：pi为控制流图的节点；bi为对应的二进制位；F为路径所到达节点的标志位。若F等于出口节点pend，则表示该路径是连通的，为此使用F的值作为蝙蝠的适应度。然后将如表2所示的输入矩阵传入，执行OBBA搜索，求得带EPW优先级的基路径集。其中，连接矩阵用于校验路径的连通性，而wEPW向量用于计算路径的错误倾向。每一次运行OBBA，若满足Fi=pend的路径不满足基路径的条件，则舍弃该路径，继续迭代直至获得基路径或达到最大迭代次数。

图4 蝙蝠编码格式

在案例程序中，使用OBBA、BBA和二进制粒子群算法(Binary Particle Swarm Optimization,BPSO)进行了基路径集搜索，迭代情况如图5所示。可以看到，在本文方法框架下，三种算法都能收敛于“出口节点34”，即能够生成完整有效的路径，且OBBA的收敛速度优于BBA和BPSO。基路径集生成结果如图6所示，其满足了基路径集三个条件，能验证本文方法可以比较高效地生成带优先级的基路径集。

图5 案例程序在三种算法下的迭代次数对比

图6 案例程序基路径集生成结果

3.2 对比分析

为了进一步验证本文方法的可行性和良好效果，选用了7个IR46智能电表软件会涉及到的字符串处理程序来进行对比测试，测试程序分析如表3所示。将OBBA、BBA和BPSO的gmax、tmax和npop分别设为20、1 000和100，其余参数如表4所示，其中BPSO参数参考了文献[17]。然后分别进行20次重复实验，取均值作为最终结果。实验结果如图7所示，可以看到OBBA的迭代次数要少于BBA和BPSO，在测试程序7的更复杂的搜索空间中，优势更加明显，可以说明OBBA能更好地避免陷入局部最优，也有更好的收敛速度。

表3 待测程序分析

表4 待优化算法参数

图7 算法对比实验结果

4 结 语

本文对IR46智能电表软件白盒测试的基路径集生成方法进行了研究，提出一种有效的新方法。通过引入路径错误倾向权重(EPW)，提升了基本路径测试发现程序错误的能力，并能通过基路径优先级排序，指导测试顺序；优化了BBA的速度更新策略和响度更新表达式得到OBBA，减少了算法所需迭代次数，提高了路径生成效率；通过实际案例的可行性验证和OBBA与BBA、BPSO间的对比实验，证明了本文方法在提升基路径集生成效率上的有效性。下一步工作是将其应用于更复杂的程序中，并拓宽应用场景。