流形（Manifold）是局部具有欧几里得空间性质的空间，其概念是几何和现代数学物理中许多模型和方法的核心，广泛应用于计算和应用数学、机器学习、物理、化学等领域。

图1  有趣的流形

近年来，哈佛大学研究团队尝试应用几何方法研究深度学习[4]。近期，他们提出了流形分布定律，即根据计算共形几何中的数据分布假设和流形假设，同一类别的高维数据往往集中在低维流形附近[5]。

受到流形分布定律的启发，智能算法研究中心提出了一种基于流形搜索的测试用例自动生成算法（Manifold-Inspired Search-based Algorithm,MISA）[1]，为基于路径覆盖的测试用例自动生成（Automated Test Case Generation Based on Path Coverage,ATCG-PC）问题提供了优化方案，现已成功在智能优化领域的国际学术期刊IEEE Transactions on Emerging Topics in Computing（JCR一区，影响因子7.691）上发表研究成果论文。下面重点介绍MISA算法的主要思路。

在许多领域中，利用流形学习，可将非欧氏空间转化为低维欧氏空间，从而降低问题的求解难度。而MISA算法运用流形学习的思想，定义了等价映射子空间有效决策子集（Effective decision space, EDS）。MISA算法的主要思路是使用测试用例与路径之间的关系矩阵来找到等价映射子空间，并通过在子空间中搜索来生成涵盖所有可能路径的测试用例。

 

图2  流形思想在启发式优化算法的应用

下面介绍MISA算法的两大策略。

（1）定义等价映射子空间EMS

通过计算找到等价映射子空间EMS。在预设的子空间内进行搜索，减少搜索空间，以减少路径与测试用例一对多关系造成的函数评估次数（Function Evaluations, FEs）冗余，同时定位有效决策子集。

（2）自适应地分配FEs消耗

在子空间不是EMS的情况下，根据测试用例路径关系矩阵自适应地分配FEs，确保算法的有效性。

流形启发式优化算法（MISA）的流程如图3所示。该算法实现了以上两种策略，力求将ATCG-PC求解过程中产生的FEs降到最少。

图3  流形启发式优化算法流程图

MISA为基于路径的测试用例自动生成问题提供了优化方法。测试用例自动生成是软件工程中一类最基本的NP-Complete黑盒问题。该问题的求解可有效减少软件测试的资源开销。其中基于路径覆盖的测试用例自动生成算法最为关键。

目前，ATCG-PC问题求解有两个难点：一、从测试用例到路径的映射是一个黑盒，关系的未知性使得许多生成的测试用例重复覆盖相同路径，大大增加了FEs的消耗。二、测试用例搜索空间的表面是一个非欧氏的特殊空间，使得在大规模范围内找到覆盖目标路径的测试用例十分困难。

 

而MISA通过在ATCG-PC的等价映射子空间中查询和搜索，节省了大量的冗余FEs消耗，有效解决了ATCG-PC求解的难点。

为了验证MISA算法的有效性，智能算法研究中心搜集整理出一个全面的测试集（下载地址：https://github.com/peerfog/ATCG-PC-testing-benchmarks）。该测试集的详细信息如图4所示。

图4  测试集详细信息表

该测试集可分为三种类型：

第一类为数据包，对应图4中的iFogSim与CoreNLP两个数据包。iFogSim[2]是雾计算领域常用的工具包，通过模拟物联网和雾环境，测量资源管理技术在延迟、网络拥塞、能耗和成本方面的影响。CoreNLP[3]是自然语言处理领域常用的工具包，集成了非常多实用的功能，包括分词、词性标注和句法分析等。

第二类为开源工程中的函数，分别从gimp-2.2.4（图像处理与合成工具）、bibclean-2.08（清理bibtex文件工具）和tiff-3.8.2（图像处理工具）三个开源工程中共选取了六个函数添加进测试集。

第三类为基础函数，从众多函数中挑选了十个基础函数补充到测试集中，以完善测试集的功能。

该测试集共选取了两个广泛使用的数据包和16个开源基准函数，测试用例的数量庞大。另外，测试集覆盖的领域甚广，涉及雾计算、自然语言处理等。最重要的是，该测试集是面向路径覆盖的。相比于分支覆盖、语句覆盖等，面向路径覆盖的测试用例生成具有难度更高、覆盖逻辑路径更多等优势。

利用该测试集，将MISA算法与其他相关算法进行实验评估与对比，测试MISA算法的性能。

图5给出MISA与ATCG-PC两种最新算法的实验结果对比，在大多数基准程序中，MISA的平均FEs消耗明显少于其他算法。红色方框突出显示MISA优于其他比较算法的结果。

图5  MISA与部分最新算法的实验结果对比

为了验证EMS搜索策略（算法1）的有效性，我们将MISA预设子空间与整个搜索空间的大小进行比较。如图6所示，预设子空间的大小远小于整个搜索空间的大小，这将节省大量FEs消耗。

图6  MISA预设子空间和整个搜索空间的大小比较

实验结果表明，MISA算法的FEs消耗明显低于现有算法，其路径覆盖率是目前流行的算法中最高的。MISA算法在ATCG求解上具有显著的优势，将来可应用到具有函数嵌套和循环的大型软件中。

智能算法研究中心长期致力于将人工智能算法应用于解决智能化软件工程领域的前沿难题，并已取得一些初步成效。未来，我们将继续在这个领域进行探索，以期为软件工程的学科建设和发展作出积极贡献。

参考文献

[1] F. Liu, H. Huang, J. Su, S. D. Semujju, Z. Yang and Z. Hao,"Manifold-inspired search-based algorithm for automated test case generation," IEEE Transactions on Emerging Topics in Computing, vol. 99, pp. 1-15,2021.

[2] H. Gupta, A.Vahid Dastjerdi, S. K. Ghosh, and R. Buyya, "iFogSim: A toolkit for modelingand simulation of resource management techniques in internet of things, edgeand fog computing environments," Software: Practice and Experience, vol. 47, no. 9, pp. 1275-1296, 2017.

[3] C. D. Manning,M. Surdeanu, J. Bauer, J. Finkel, S. J. Bethard, and D. Mcclosky, "The stanfordcoreNLP natural language processing toolkit," in Proceedings of 52ndAnnual Meeting of the Association for Computational Linguistics: SystemDemonstrations, pp. 55-60, 2014.

[4] X. Gu, F. Luo,J. Sun, and S. Yau."Variationalprinciples for minkowski type problems, discrete optimal transport, and discretemonge-ampere equations," AsianJournal of Mathematics (AJM), vol. 20, no. 2, pp.383-398, 2016.

[5] N. Lei, Z. Luo, S. Yau, and X. Gu, "Ageometric understanding of deep learning," Engineering, vol. 6,no. 3, pp. 361-374, 2020.

总编：黄翰

责任编辑：袁中锦

文字：梁靖欣

图片：梁靖欣

校稿：何莉怡

时间：2021年07月26日