生成测试用例是软件测试的必要前提,路径覆盖测试用例自动生成（ATCG-PC）作为一种智能化软件测试技术,是提高软件测试效率的有效途径。此外,ATCG-PC可视为一个大规模黑盒优化问题,其高效求解算法研究对于软件工程与优化算法领域均有重要的研究意义。本文将针对测试用例生成面向分支覆盖或更低覆盖标准、测试用例生成效率低、求解速度慢、缺乏可解释性、需要人工辅助这些痛点逐一展开研究。研究从路径覆盖测试用例生成问题优化建模展开,将测试用例生成从简单的分支覆盖推广到更难的路径覆盖;根据多种软件应用场景抽象出三类典型的路径覆盖测试用例生成问题模型,并在此基础上设计三种搜索算子提升算法求解效率,检测实际应用的缺陷;以时空置换等算法设计原理为基础,研究单元测试用例自动生成问题的通用求解方法,提升算法的可解释性;研究单元测试用例自动生成技术在实际工程代码上的应用。与现有的研究思路不同,本文将测试用例编码空间进行划分,通过找到与优化目标对应的有效决策子集（即远小于整个测试用例编码空间且包含优化目标最优解的子空间）,并动态分配全局空间与有效决策子集的搜索算力,来极小化测试用例生成的计算代价。本文的主要研究内容包括:1)研究路径覆盖测试用例生成问题的首要工作是建立问题的优化模型。因此,本文首先将研究如何建立路径覆盖测试用例生成问题的优化模型,该研究将测试用例生成技术推广到更加复杂的路径覆盖。研究将基于模型揭示的启发式信息设计自适应评估函数,实现路径覆盖测试用例的半自动生成。2)测试用例与路径间多对一的黑盒特征是路径覆盖测试用例生成问题求解困难的主要原因,如何挖掘测试用例-路径间的关联关系、避免算法的重复开销是本文重点研究的科学问题。为此,本文针对雾计算、自然语言处理、区块链智能合约等应用场景抽象出三类典型的路径覆盖测试用例生成问题模型,并设计了测试用例-路径关系矩阵搜索算子、动态多点搜索策略与重入性漏洞检测方法。提出的求解策略能够显著提升现有优化算法的测试用例生成效率,加快算法求解速度,最终辅助程序漏洞检测。3)基于上述两项研究内容,本文将进一步研究路径覆盖测试用例生成问题的通用求解方法,以提升路径覆盖测试用例生成问题这类大规模黑盒优化问题的求解速度。受到流形分布假设的启发,本文定义了有效决策子集等相关概念,并提出了求解路径覆盖测试用例生成问题的流形启发式算法:通过快速找到优化目标的有效决策子集,动态分配搜索找到的子空间与剩余空间的算力,实现路径覆盖测试用例的高效生成。该方法能够在确保算法效率的前提下,使得算法同时拥有较强的可解释性。实验结果说明流形启发式算法拥有显著优于其他前沿算法的性能。4)如何实现无需人工参与分析的自动单元测试框架是本文的一项重要研究内容。为此,本文设计了单元程序自动分析与路径覆盖测试用例生成的应用框架。通过对插桩后的字节码进行分析,获取被测单元程序的流程图与分支结点等信息,自动生成评估函数,并在此基础上搜索生成路径覆盖测试用例,极大地提升了路径覆盖测试用例生成的自动化程度。