智能算法 | 又一大进步，软件测试开销过大的问题这样解决！

图文已经华南理工大学智能算法实验室授权。

实验室负责人：黄翰教授

联系邮箱：hhan@scut.edu.cn

近年来，在软件开发过程中（如图一）据统计有50%的开销来自于测试环节。软件测试的主要目的是以最少的人力、物力和时间找出软件中潜在的各种缺陷和错误，通过修正缺陷和错误提高软件质量，回避软件发布后由于潜在的软件缺陷和错误造成的隐患。其中黑盒测试和白盒测试是两种常见的测试类型，黑盒测试着重于评估测试程序的表现，白盒测试则能够揭露程序逻辑上的潜在缺陷。而测试用例自动生成问题（ATCG）是一类迫切需要解决的白盒测试问题，以往测试用例的自动生成大多通过人工手段实现，ATCG问题的解决可以有效帮助减少软件测试过程中的人力、物力资源的开销。

为了解决软件测试环节人力、物力和时间等方面的开销问题，华南理工大学软件学院智能算法实验室展开了一系列对测试用例自动生成问题（ATCG）的研究，现已成功在IEEE TII上发表针对ATCG的“测试用例-路径”关系矩阵的研究成果论文。下面让我们一起回顾关于本研究工作的发展进程与相关成果。

图1 软件开发过程示意图

首先，本工作从雾计算程序中的ATCG-PC问题背景出发，在了解整个雾计算系统（如图2）的概念下，我们从中可知雾计算程序中ATCG-PC问题目标就是要最大化路径覆盖率，同时测试用例开销也需要尽可能控制到最小。而在解决ATCG问题上，雾计算程序只是作为对比的benchmark function，也就是基准测试函数；路径覆盖测试用例自动生成问题的需求其实就是在有限的测试用例开销内，找到覆盖基准测试函数中所有可行路径的测试用例。那么，针对目前仍有一些路径并不能被测试用例覆盖的问题上，下面我们提出了一种基于“测试用例-路径”关系矩阵的差分进化算法（RP-DE）。

图2 雾计算系统示意图

本算法通过收集测试用例变量与路径节点相关性，找出测试用例编码空间中与覆盖路径相关的同胚低维欧氏空间（与目标路径相关的测试用例编码维度构成的搜索空间），并通过关系矩阵中的信息指导算法将更多的计算资源分配搜索该同胚低维欧氏空间，从而减少算法的测试用例开销，并提升算法搜索效率。

该算法的流程主要通过先初始化种群和关系矩阵R的初始工作，然后不断重复DE算法的变异和交叉操作，和使用“测试用例-路径”关系矩阵覆盖目标路径这两步，直到最后满足终止条件，即当路径覆盖率c为100%或者生成的测试用例数目T大于等于预设最大测试用例开销Max时，算法停止退出。算法框架如下图3所示：

图3 RP-DE算法框架

基于上述的算法思想，本课题立足iFogSim这个雾计算工具包中常用的几个函数作为基准测试函数，最后成功实现了对该工具的单元测试用例生成的工作，下面图4和图5便是我们使用关系矩阵更新测试的用例示例。

图4 使用关系矩阵更新测试用例示例图（1）

图5 使用关系矩阵更新测试用例示例图（2）

在本次研究课题中，我们提出了一种雾计算程序的ATCG-PC问题数学模型，其问题为单目标优化问题，每个测试用例仅需评估一次，并且可以解决雾计算程序以及其他具有不可覆盖路径时，其他数学模型无法对比求解算法性能的问题；提出了RP-DE算法，在测试雾计算程序以及其他测试程序的单元测试中，相对对比的算法均拥有显著的优势，具有较强的鲁棒性。

与此同时，我们将设计的算法应用于实际，开发出相对应的软件、工具以及测试平台来解决自然语言处理、深度学习等工具的测试问题。通过探究智能软件测试用例编码空间的同胚欧式空间映射关系，以及研究在同胚欧式空间与剩余搜索空间的计算资源分配问题，已经成功搭建一款智能软件的测试与系统验证平台。

参考文献

[1]Han Huang,Fangqing Liu*,Zhifeng Hao. Differential Evolution Based on Self-Adaptive Fitness Function for Automated Test Case Generation, IEEE Computational Intelligence Magazine, 12(2),46-55, May 2017.

[2]Han Huang, Fangqing Liu*, Zhongming Yang, Zhifeng Hao. Automated Test Case Generation Based on Differential Evolution with Relationship Matrix for iFogSim Toolkit. IEEE Transactions on Industrial Informatics(Early Access), 2018, [DOI: 10.1109/tII.2018.2856881].