《Symmetry》：An Efficient Deep Path Coverage-Based Approach for Automated Software Structural Testing
Bahman Arasteh,
Mohammadali Ipchi Sheshgelani and
Huseyin Kusetogullari
编辑推荐：
结构软件测试是软件开发生命周期中的一个关键阶段，其中实现高覆盖率和缺陷检测仍然是一个重大挑战。对于具有大量模块和功能的程序，手动测试成本高昂且效率低下。自动化测试数据生成解决了这一问题，但其有效性取决于所使用的优化策略。研究人员引入了一种新颖的混合优化算法，结
结构软件测试是软件开发生命周期中的一个关键阶段，其中实现高覆盖率和缺陷检测仍然是一个重大挑战。对于具有大量模块和功能的程序，手动测试成本高昂且效率低下。自动化测试数据生成解决了这一问题，但其有效性取决于所使用的优化策略。研究人员引入了一种新颖的混合优化算法，结合了灰狼优化器（Gray Wolf Optimizer，GWO）和粒子群优化（Particle Swarm Optimization，PSO），以覆盖程序的深层路径并生成高效的测试数据。通过所提出的混合PSO-GWO方法平衡探索与利用，该方法能够很好地适应不同规模和复杂度的程序。所提出的方法在26个标准基准程序上进行了评估。实验结果表明其优越性能，实现了88.37%的覆盖率，高于现有方法，以及67.45%的变异分数，反映了改进的缺陷检测能力。此外，它产生更少的测试用例，平均执行时间为1257.7秒，大约是遗传算法（GA）、GWO和PSO单独所需时间的一半。在本研究中，分析了程序控制流和执行路径的对称和不对称结构方面，以生成自动化测试。所建议的深层路径覆盖技术利用基于对称性的优化原则来实现软件的有效和可靠结构测试。总体而言，所提出的混合算法生成的测试数据更少、更快、更有效。与现有方法相比，所提出的方法是一种可靠且高效的测试生成器。
# 论文解读：基于PSO-GWO混合优化的深层路径覆盖自动化软件结构测试方法
## 研究背景与问题
软件测试是软件质量保证的核心环节，尤其是在技术快速发展的背景下，维护软件质量与性能面临更大挑战。手动测试成本高昂且效率低下，尤其对于包含大量模块和功能的程序而言。自动化测试数据生成虽能缓解此问题，但其效果高度依赖于所采用的优化策略。现有方法存在诸多不足：基于优化的方法容易过早收敛，生成冗余测试用例，增加测试成本；机器学习和大语言模型（LLM）辅助方法依赖模型质量和计算资源；边界聚焦或优先级排序方法难以应对复杂程序；许多方法仅提升代码覆盖率而未直接改善缺陷检测能力。此外，深层嵌套条件、稀有执行路径和复杂分支组合等难以覆盖的代码区域常被忽视，导致即使整体覆盖率较高，敏感或易错部分仍可能未经充分测试。因此，迫切需要一种能同时提升覆盖率与缺陷检测能力、高效探索困难程序路径、减少冗余测试用例的方法。
## 研究内容与结论
本研究提出一种混合启发式算法，将粒子群优化（PSO）和灰狼优化器（GWO）相结合，用于生成软件测试用例。该方法通过平衡探索与利用，适配不同规模和复杂度的程序。研究人员在26个标准基准程序上进行了评估，实验结果显示：所提方法实现了88.37%的平均覆盖率，显著高于随机测试（75.88%）、遗传算法GA（78.18%）、GWO（83.05%）、PSO（84.43%）及GA-GWO混合（83.65%）；变异分数（Mutation Score，缺陷检测能力）达到67.45%，优于其他对比方法；生成的平均测试用例数量仅为3.5个，远少于GA、GWO和PSO的12个左右；平均执行时间为1257.7秒，约为GA（2626秒）、GWO（2919.1秒）和PSO（3025.65秒）的一半。论文发表在《Symmetry》上，强调利用对称性与非对称性结构分析程序控制流和路径，以生成自动测试。
## 关键技术方法
研究人员主要使用了以下关键技术方法：
1. **混合启发式优化算法**：将灰狼优化器（GWO）的领导者探索机制与粒子群优化（PSO）的快速收敛能力结合，通过时变概率参数ρ(t)（范围0.2至0.8）自适应平衡探索与利用。
2. **双重适应度函数**：综合行覆盖率、分支覆盖率和变异分数（Mutation Score）作为优化目标，兼顾结构覆盖与缺陷检测。
3. **遗传算子增强**：在每次迭代后对种群应用遗传算法的交叉（概率0.7）和变异（概率0.2）操作，增加种群多样性，避免早熟收敛，并保留具有潜在覆盖优势的低适应度个体。
4. **程序解析与测试自动化**：利用Roslyn编译器平台（Microsoft.CodeAnalysis）对C#源代码进行语法解析，提取可测试方法及输入参数信息；并开发了变异注入平台（基于Stryker mutator）进行缺陷检测评估。
（样本队列来源：26个标准基准程序，包括简单函数如IsLeapYear到复杂程序如AES和MS_MergeSort_Obf，均取自公开C#项目或常见算法实现。）
## 研究结果
以下按论文原始小标题介绍研究发现：
### 4.3.1 生成测试数据的覆盖率
研究人员通过行覆盖率和分支覆盖率评估各方法在26个基准程序上的性能。结果表明，PSO-GWO混合方法在大多数函数上实现了最高覆盖率，尤其在复杂程序中表现突出。平均行覆盖率为88.37%，分支覆盖率为82.88%，均优于随机测试、GA、GWO、PSO及GA-GWO。低方差分析显示PSO-GWO具有最佳稳定性，能持续覆盖深层和难以到达的代码位置。
### 4.3.2 生成测试数据的缺陷发现率
变异分数（Mutation Score）衡量测试套件检测注入错误的能力。PSO-GWO实现了67.45%的平均变异分数，显著高于GA-GWO（61.47%）、GA（59.92%）、PSO（55.03%）、GWO（51.37%）和随机测试（47.70%）。部分复杂函数（如f05和f19）中，其他方法甚至无法检测到任何变异，而PSO-GWO仍能有效发现缺陷。
### 4.3.3 测试集大小评估
统计各方法生成的测试用例数量：GA、GWO和PSO平均生成约12个测试数据，而混合方法GA-GWO和PSO-GWO仅生成约3.5个。这表明混合方法能在保持甚至提升覆盖率的前提下大幅减少冗余测试，提高效率。
### 4.3.4 测试数据生成时间
测试生成时间对比：GA需2626秒，GWO需2919.1秒，PSO需3025.65秒，而GA-GWO需1639.6秒，PSO-GWO仅需1257.7秒，约为其他单一启发式算法的一半。PSO-GWO在大部分函数上均表现出最快生成速度。
## 讨论与结论总结
### 讨论部分总结
讨论指出，PSO-GWO的优势源于PSO快速利用与GWO广泛探索的协同作用，使其能有效避开局部最优并搜索深层路径。混合方法通过保留低适应度但具潜在覆盖价值的候选解，引导搜索深入难覆盖区域，显著降低了未覆盖分支比例（17.12%）。进一步与商业工具IntelliTest（基于符号执行的混合测试）及现代工具EvoSuite、ChatUniTest、ChatTester比较，PSO-GWO在分支覆盖率上仍为最优（82.88%），优于IntelliTest（77.45%）、EvoSuite（81.00%）、ChatTester（80.20%）和ChatUniTest（82.41%）。此外，参数敏感性实验表明默认配置（配置1）提供了最好的探索-利用平衡。研究也承认存在效度威胁：基准程序规模有限、未考虑不可达路径问题、缺乏强测试预言等。
### 研究结论翻译
实验结果表明，所提出的基于PSO-GWO的测试生成器在软件测试数据生成方面优于所有对比方法。所建议的元启发式驱动测试生成器实现了最高的平均覆盖率（88.37%）和变异分数（67.45%），证实了其在探索输入空间和检测隐藏缺陷方面的卓越能力。这些发现凸显了将PSO的快速收敛与GWO的强探索能力相结合的优势，使算法能够生成多样且有效的测试数据。此外，PSO-GWO通过生成更少的测试用例并需要最短的生成时间，展现了显著的效率。这意味着混合方法不仅提高了测试有效性，还降低了计算成本。总体而言，实验结果表明，在相同的基准程序和实验设置下，PSO-GWO方法在自动化测试数据生成方面比所测试的算法具有更高的有效性和效率。它提供了更好的缺陷检测、更高的覆盖率和更快的执行速度，使其成为实际软件测试和基于预言测试自动化的未来研究中极具前景的技术。未来工作将关注不可达路径识别、覆盖易错路径、开发高效测试预言、减少冗余用例、降低混合方法实现复杂度以及自适应调整生成测试用例数量。
