Page 127 - 《软件学报》2025年第5期

孙百才 等: 代理辅助多任务进化优化引导的 MPI 程序路径覆盖测试用例生成 2027

MPI program. Then, the fitness of evolutionary individuals is estimated using the surrogate model corresponding to each target sub-path,
and a candidate set of test cases is formed. Finally, all surrogate models are updated based on the candidate set and the actual fitness for
each target sub-path. The proposed approach is applied to the basis path coverage testing of seven benchmark MPI programs and
compared with several state-of-the-art approaches. The experimental results show that the proposed approach significantly improves testing
efficiency while ensuring high effectiveness in generating test cases.
Key words: test case generation for path coverage; surrogate-assisted multi-task evolutionary optimization; candidate set of test case

MPI 程序是一类由若干进程构成的并行程序, 被广泛应用于高效解决经济安全和社会发展中很多复杂的问
题 [1,2] . 测试一个 MPI 程序时, 采用的测试准则非常重要, 除了能够引导测试用例的生成外, 还能评价测试用例的充
分性. 目前为止, 已经提出多种测试准则, 其中, 基本路径覆盖是一种同时满足分支与语句覆盖准则的测试方法, 已
经成为一种常用的结构覆盖准则 [3] .
已知的是, MPI 程序的一条目标路径通常由每一进程内一条目标子路径组合而成. 鉴于此, 可独立分析 MPI
程序目标路径内每条目标子路径的测试用例生成问题. 考虑到路径覆盖测试用例生成问题能够被转换为最优化问
题 [4] , 因此, 这里将每条目标子路径的测试用例生成问题转换为最优化问题, 并建立相应的优化模型. 鉴于多任务
进化优化已经广泛用于并行解决若干最优化问题 [5−7] , 因此, 本文将面向 MPI 程序目标路径内每条目标子路径的
优化模型置于一个优化任务中, 并在基于进化算法并行求解每一优化模型的过程中, 形成候选测试用例集, 用于覆
盖 MPI 程序目标路径.
基于进化算法并行求解每一优化任务中优化模型的过程中, 需反复执行被测 MPI 程序, 以便评价该优化任务
中进化个体适应值. 然而, 重复执行被测 MPI 程序通常需要高昂的计算成本, 这导致每一优化模型的求解变成一
个昂贵优化问题. 为降低昂贵优化问题的求解成本, Wang 等人 [8] 提出了一种具有区域划分的代理辅助差分进化算
法. 此后, Si 等人 [9] 研究了基于代理辅助进化算法的大规模昂贵单/多目标优化问题求解, 并表明在解决昂贵优化
问题方面, 代理辅助进化算法具有明显优势. 此外, Jin 等人 [10] 指出进化优化可能受益于代理模型引入的估计误差,
该误差能够使得种群多样性更好和不容易陷入局部最优. 鉴于此, 本文将在目标路径内每条目标子路径的优化任
务中训练一个代理模型, 用于代替被测 MPI 程序的实际执行, 以及估计进化个体面向该目标子路径的适应值, 从
而降低 MPI 程序的实际执行成本.
综上, 本文提出一种代理辅助多任务进化优化引导的 MPI 程序路径覆盖测试用例生成方法. 所提方法中, 首
先面向目标路径内每条目标子路径, 训练相应的代理模型; 然后, 在每条目标子路径的测试用例生成优化任务中,
基于相应的代理模型, 估计进化个体的适应值, 并选择最优进化个体, 用于形成候选测试用例集; 最后, 继续在每条
目标子路径对应的优化任务中, 基于候选测试用例集及其面向每条目标子路径的真实适应值, 更新相应的代理模型.
所提方法的优势之一是基于每一优化任务从局部方面寻找覆盖目标路径内每条目标子路径的最优进化个体,
并基于最优进化个体, 形成候选测试用例集, 进而从全局方面验证某一候选测试用例是否覆盖了目标路径. 显然,
以上优势恰好符合局部寻优加速全局最优的原理. 此外, 所提方法另一优势为进一步利用代理模型来降低每一优
化任务中进化个体适应值的评价成本. 结合上述分析, 所提方法将有利于高效生成 MPI 程序目标路径的测试用例.
本文第 1 节是相关工作. 所提方法在第 2 节给出, 包括: 总体框架、代理模型训练、候选测试用例集形成, 以
及代理模型更新. 第 3 节将提出方法应用于若干 MPI 程序路径覆盖测试中, 并与多种方法对比, 给出实验数据与
分析结果. 实验有效性的威胁在第 4 节讨论. 最后, 第 5 节总结全文, 并指出需要进一步研究的问题.

1 相关工作

1.1 基础知识
与本文相同, 文献 [4] 也研究了 MPI 程序路径覆盖测试. 因此, 文献 [4] 中涉及如下基础知识同样适用于本文:
MPI 程序及其测试输入的表示、节点、子路径相似度等. 为更好地理解相关基础知识, 我们给出如图 1 所示的一
个 MPI 程序示例代码.