基于遗传算法的航空机载软件测试用例优先级技术研究

冯廷智 成红芳

摘要：为了提高航空机载软件回归测试效率、降低回归测试成本，提出应用遗传算法实现测试用例优先级排序的方法。该方法将统一建模语言（UML）活动图转化为控制流图（CFG），对控制流图中各判定节点进行二进制编码生成初始种群，并通过选择、交叉和突变等操作搜索适应度最高的个体进行优先测试。以某型飞机机载环控系统综合控制器软件货舱供气旁路调节阀控制率计算功能为案例，证明该方法能够实现测试用例的优先级排序，可用于基于模型的机载软件自动化测试。

关键词：机载软件;遗传算法;测试用例优先级;回归测试;基于模型的测试

中图分类号：V219 文献标识码：A

随着现代航空机载软件规模和复杂度的不断增加，给软件测试带来了诸多挑战。由于功能完善、性能优化、错误修复等原因，软件往往处于动态演化中，会积累大量的冗余测试用例，使测试用例集的管理和维护成本增加[1]。执行回归测试时，测试人员从已有的测试用例集中选择可复用的用例子集，尽可能地满足测试需求。然而，选择的测试用例，其检错能力或覆盖能力有所不同，且仍可能包含冗余测试用例。若将其按照一定的准则进行排序后再执行，有助于在较短的时间内尽可能多地发现错误，并尽快达到覆盖率要求，这便是测试用例优先级技术[2]。

测试用例优先级是一种高效的回归测试技术，能在时间、环境等资源受限的情况下执行更多的有效测试用例，从而保证软件质量[3]。研究者提出了多种实现测试用例优先级排序的方法。李龙澍[4]等提出了多种群遗传算法实现测试用例优先级排序的方法。张娜[5]等设计的基于多目标优化的测试用例优先级方法，能利用测试过程中的反馈信息，在线调整测试用例优先级。常龙辉[6]等提出了能动态自适应地调整测试用例优先级的技术。郑锦勤[7]等结合了测试用例选择和测试用例优先级技术，对排序结果进行再选择，进一步缩小了回归测试用例集。

为了进一步提高测试效率和测试质量，产生了基于模型的自动化软件测试方法。根据软件开发文档对被测系统进行形式化建模，通过算法由模型自动生成测试用例，能够显著提高软件测试的充分性和自动化程度。统一建模语言（Unified Modeling Language，UML）是一種可被用于自动化测试的典型模型，尹建月等[$1提出了一种基于UML活动图模型生成测试用例的方法，结合深度优先搜索生成了测试路径。Sabharwal[9]等和Nejad[10]等将遗传算法应用于基于UML模型的测试，实现了测试用例的优先级排序。

本文将遗传算法应用于航空机载软件测试用例优先级技术中，以某型飞机机载环控系统综合控制器软件货舱供气旁路调节阀控制律计算功能为案例，以该功能的UML活动图为输入，将其转化为控制流图（Control Flow Graph，CFG），用遗传算法实现测试用例的优先级排序，并讨论该方法在机载软件回归测试中的应用前景。

1 基于遗传算法的测试用例优先级技术

1.1 遗传算法

遗传算法[11]是一种模拟自然界遗传机制和生物进化论而形成的搜索最优解的方法，具有自适应的特点，能够处理复杂的非结构化问题，且操作步骤规范，便于具体实施[12]。遗传算法的处理对象为一定数量的染色体，染色体是一串二进制数字，每个数字代表基因。遗传算法的基本执行过程如图1所示，简述如下：

（1）初始化

确定种群规模、交叉概率、突变概率和终止进化的条件，并随机生成一定数量的个体作为初始种群。

（2）个体评价

计算种群中每个个体的适应度，适应度可以定义为个体在环境中的生存能力或再生能力。

（3）种群进化

种群进化过程中主要执行三种操作：选择（Selection）、交叉（Crossover）和突变（Mutation）。首先，选择适应度高的个体作为母体。其次，依据一定的概率，互换两个个体的基因或序列生成新的种群，这就是交叉或重组。最后，依据一定的概率，使个体的基因发生突变，引入新的基因特征，保持种群的多样性。

（4）终止进化

再次评价个体适应度，如果已经满足优化准则，则输出适应度最大的个体作为最优解;否则，返回第（3）步。

1.2 用遗传算法实现测试用例优先级排序的步骤

UML活动图能通过模拟一个活动到其他活动的控制流描述出系统功能，本文以活动图为输入，用个体适应度表征测试用例的优先级，通过遗传算法搜索种群中适应度最高的个体，找出最重要、最复杂的路径进行优先测试，防止错误在后续过程中增殖或传播。下面为具体的实现步骤：

（1）将活动图转换为控制流图（CFG）

在控制流图中，节点表示活动。

（2）采用基于堆栈的内存分配方法和IF模型为CFG中各节点分配权重

堆栈具有“后进先出”的存取特性，只能在栈顶对数据进行插入和删除，访问或修改某一元素时，需要删除其上方的数据。基于堆栈的内存分配方法中，对CFG各节点分配的权重（w_SB）与在堆栈中访问该节点的操作数相关。访问某一节点的操作数越高，分配的权重越高，该节点的复杂度也越高。同时，访问该节点的成本亦会逐渐升高。在IF模型中，将信息流应用于系统的元件设计。本文将CFG中的节点作为元件，计算了CFG中每个节点的IF值。以A节点为例，其IF值的计算公式如下：式中FAN-IN（A）为A节点的扇入，FAN-OUT（A）为A节点的扇出。CFG中节点的总权重为基于堆栈的权重与IF值的和。

（3）选择

遗传算法的处理对象为二进制编码组成的染色体，通过对CFG中的判定节点进行编码生成染色体或个体，编码的位数与CFG中判定节点的数量相关。例如，CFG中有4个判定节点，染色体的编码由4位二进制数组成，每位二进制数代表一个基因。每个基因可以取1或0，1表示该判定节点选择了为真的路径，0则表示选择了为假的路径。图2为某个染色体，该染色体对应的CFG中有4个判定节点，分别为第2、5、7和10节点;4位编码按照左右顺序分别与各判定节点的取值一一对应。

评估个体的适应度后，选择适应度较高的染色体作为母体进行再生。每个染色体的适应度由式（2）计算得到：式中：w_i为目标路径中第i个节点的权重，n是该路径中的节点数。第i个节点的权重为IF值和基于堆栈的权重之和：

（4）交叉或重组

基因的交叉和重组的实质是交换两个个体的基因或编码序列。本文设定交叉或重组的可能性为80%[9]。种群进化过程中，给定一个随机数R（0

（5）突变

为了避免搜索过程陷人局部最优解，需要通过突变引入新的特征，保持种群的多样性。发生突变时，染色体的编码会在0和1之间跳转。本文设定突变的概率为20%[9]，当R小于20%时，对该染色体执行突变操作。

2 机载环控系统综合控制器软件应用案例

某型飞机机载环控系统综合控制器软件货舱供气旁路调节阀控制率计算功能的活动图如图3所示，该功能根据驾驶舱供气流量实测值，计算出目标值与实测值之间的系统控制误差，再依据控制逻辑输出调节阀的占空比，以实现对驾驶舱入口流量的控制。

根据1.2节所述的采用遗传算法实现测试用例优先级排序的方法，首先将图3所示的活动图转化为CFG，如图4所示。采用基于堆栈的内存分配方法，为各节点分配权重，见表1。k表示当前节点之前的节点数;s表示插入当前节点后堆栈的大小，因此，堆栈的最大容量s^max为12。w_SB表示为该节点分配的基于堆栈的权重，通过w_SB=s^max-k计算得到。例如，CFG中节点1是第一个插入堆栈的节点，其权重为w_SB=12-0=12，类似地，节点2之前的节点数为1，其权重为w_SB=12-1=11.从表1可以看出，节点1的权重最大，意味着访问或修改节点1需要的操作数最多。

表2为各节点的复杂度。A为基于堆栈中删除操作的复杂度，由表1查得。例如节点8，其权重为7，则基于删除操作的复杂度为8;节点9的权重为6或7，则基于删除操作的复杂度为6+7=13。B为节点的IF值，通过式（1）计算得到。各节点的总复杂度等于该节点基于删除操作的复杂度与IF值的和，即A+B。

从图4可以看出，该CFG有5个判定节点，分别为4，6、10、13、14。使用5位二进制数对这5个节点进行编码，即可生成染色体或个体。例如，5个判定节点都取0时，该染色体为00000，对应的路径将历经节点1、2、3、4、6、8、9、10、12、14、18、19;该测试用例的适应度为路径中各节点复杂度的和，即12+12+11+11+10+8+15+13+10+9+6+7=124。

根据遗传算法的执行步骤，首先随机生成初始种群，由4个个体组成：11111、10000、00001、11100，见表3。表3中X为随机生成的染色体或个体，代表测试用例。F（X）为该染色体的适应度。以该案例中随机生成的个体为例，11111代表的测试用例为节点1、2、3、4、5、9、10、11、13、15、19所在的路径，其适应度为115;10000代表的测试用例为节点1、2、3、4、5、9、10、12、14、18、19所在的路徑，其适应度为115;00001代表的测试用例为节点1、2、3、4、6、8、9、10、12、14、17、19所在的路径，其适应度为124;11100代表的测试用例为节点1、2、3、4、5、9、10、11、13、16、19所在的路径，其适应度为115。R为随机生成的0到1之间的数;C和M分别表示交叉和突变操作后的个体，当R小于80%时执行交叉操作;当R小于20%时，执行突变操作。F'（Al为执行遗传操作后生成的新个体的适应度。表3～表6为每次迭代后的结果。每次迭代后，将种群中的个体按其适应度重新排序。

如表6所示，该案例中生成的初始种群经8次迭代后，其适应度已达到最大值，且不再发生明显变化。可以认为，表6所示的个体或测试用例的优先级最高，应最先对其进行测试。染色体00101和01111表示节点1、2、3、4、6、8、9、10、11、13、16、19所在的路径，染色体01100表示节点1、2、3、4、6、7、9、10、12、14、18、19所在的路径，染色体00001表示节点1、2、3、4、6、8、9、10、12、14、18、19所在的路径。分析上述4个个体可知，优先级较高的染色体都是节点6所在的路径。实质上，从节点6至节点7和节点8的路径是对称的，从节点10至节点11和节点12的路径也是对称的，判定节点6、10、13、14的取值不会影响染色体的适应度。因此，决定染色体适应度的关键判定节点为节点4，节点4取值为0的路径优先级较高。

出现上述现象的原因主要是本文所选案例相对简单，活动图中有三处对称结构。然而，以环控系统综合控制器软件为例的现代航空机载软件中存在大量的复杂逻辑，判定节点多，如果仅依赖人工生成测试用例，不仅效率低下，且难以保证测试充分性，无法实现测试用例优先级。综上所述，该案例已经证明，本文提出的方法和步骤能够通过遗传算法实现测试用例的优先级排序。

3 结论

本文提出了应用遗传算法实现航空机载软件测试用例优先级排序的方法。以某型飞机机载环控系统综合控制器软件货舱供气旁路调节阀控制率计算功能为例，以其UML活动图为输入，通过选择、交叉和突变等遗传操作搜索出适应度最高的个体进行优先测试。证明基于遗传算法的测试用例优先级技术，可被用于基于模型的机载软件测试。在后续工作中，将对比分析遗传算法与其他算法的优化速率，并研究通过遗传算法实现机载软件测试用例优先级排序的自动化工具。

参考文献

[1]张智轶，陈振宇，徐宝文，等.测试用例演化研究进展明.软件学报，2013，24（4）：663-674.

[2]Yoo S，Harman M.Regression testing minimization，selectionand prioritization：A survey [J].Software Testing，Verificationand Reliability，2012，22（2）：67-120.（in Chinese）

[3]曲波，聂长海，徐宝文.回归测试中测试用例优先级技术研究综述[J].计算机科学与探索，2009，3（3）：225-233.

[4]李龙澎，李森，廖敏，等.基于多种群遗传算法测试用例优先级技术研究[J].计算机技术与发展，2011，21（4），112-119.

[5]张娜，姚澜，包晓安，等.多目标优化的测试用例优先级在线调整策略[J].软件学报，2015，26（10）：2451-2464.

[6]常龙辉，缪淮扣，肖蕾.基于历史信息的自适应测试用例优先级技术明.计算机科学，2015，42（9）：154-158.

[7]郑锦勤，牟永敏.基于函数调用路径的回归测试用例选择排序方法研究[J].计算机应用研究，2016，33（7）：2063-2067.

[8]尹建月，周萌，陈升来.基于uML活动图的测试用例生成方法设计[J].信息化研究，2014，40（3）：28-32.

[9]Sangeeta S，Ritu S，Chayanika S.Applying genetic algorithmfor prioritization of test case scenarios derived from UMLdiagrams[J].International Journal of Computer Science Issues，2011，8（3）：433-444.

[10]Fatemeh M N，Reza A，Mohammad M D.Using memeticalgorithms for test case prioritization in model based softwaretesting[C]//1”Conference on Swarm Intelligence andEvolutionary Computation（CSIEC 2016），Higher EducationComplex of Bam，Iran，2016.

[11]Holland J H.Adaptation in natural and artificial systems[M].AnnArbor：University of Michigan Press，1975.

[12]葛繼科，邱玉辉，吴春明，等.遗传算法研究综述[J].计算机应用研究，2008，25（10）：2911-2916.