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

2034 软件学报 2025 年第 36 卷第 5 期

r 个候选测试用例. 注意, 基于不放回随机抽取的变量值组成一个候选测试用例时, 要避免组成的候选测试
表示第
用例与任一 BestInd j 重复.
P ∗ P ∗ 内每条目标子
可以看出, 上述形成的候选测试用例集不仅考虑了覆盖 np 的全局需求, 而且也考虑了覆盖 np
r
r
∗ X (r = 1,2,...,2N) 执行被测 X 面
路径 p 的局部需求. 得到 CTSet 后, 将基于每一候选测试用例 MPI 程序, 并计算
j
r
∗
∗
向 P ∗ 内每条目标子路径 p 的真实适应值, 记为 F j (X ) . 鉴于此, 可得到所有候选测试用例面向 p 的真实适应值
np j j
( )∑ N
r
r r ∗ 1 / F j (X ) = 1 ,
集合, 记为 RealFit j = {F j (X )|r = 1,2,...,2N} . 此外, 当 X 同时覆盖 P np 内所有目标子路径时, 即 N j=1
r ∗
X 即为覆盖 P 的测试用例, 记为 TC .
np
算法 5 给出了候选测试用例集的形成策略, 即函数 CovFlag_CTSet_Etc(BestInd j ) . 算法 5 的输入为每一优化
任务 task j 中最优进化个体 BestInd j , 输出为覆盖 P ∗ np 的标志 CovFlag 、测试用例 TC 、候选测试用例集 CTSet 及
RealFit j . 算法 5 CTSet 中 (行 1–3); 然后, 形成候选
其对应每条目标子路径的真实适应值 中, 首先添加 BestInd j 至
测试用例集 (行 4–9); 接着, 基于每一候选测试用例, 执行被测 MPI 程序, 并计算对应 p 的 RealFit j , 以及判定是否
∗
j
生成了测试用例 TC 等 (行 10–15); 最后, 返回 CovFlag 、 TC 、 CTSet , 以及 RealFit j (行 16).

2.4 代理模型更新
基于进化算法求解每一优化任务 task j 内优化模型 OptMod j 的过程中, 需要使用代理模型来估计 task j 内每一
SurrModel j 很难持续保证进
代种群内进化个体的适应值. 然而, 随着 task j 内 OptMod j 的进化求解, 相应代理模型
∗
化个体适应值的高估计准确度. 鉴于此, 本节有必要利用面向 P ∗ 内每条目标子路径 p 的测试知识, 补充训练样本
np j
集, 用于更新代理模型.
已知, 通过第 2.3 节中算法 5 p 的真实适应值
∗
能够得到候选测试用例集
CTS et 及其对应每条目标子路径
j
r RealFit j = {F j (X )|r = 1,2,...,2N} . 此外, 第 p 的
r
∗
RealFit j , 其中, CTSet = {X |r = 1,2,...,2N} 和 2.2 节已经给出面向
j
k
训练样本集, 即 SampleSet j = {Sample |k = 1,2,...,SampSize} . 注意, SampSize 的初始值为 InSize , 但随着 task j 内种
j
群的不断进化, SampSize 的值会变大. 可以看出, 这里将选择 CTSet 和 RealFit j 内具有价值的训练样本, 用于补充
SampleSet j .
∗
∗ p 的期望测试用例, 因此, 将该候选测试用例
考虑到面向 p 具有最高真实适应值的候选测试用例更接近覆盖
j j
补充至训练样本集, 并以此更新代理模型后, 所更新代理模型在期望测试用例附近区域的估计准确度将能够得到
提升. 此外, 鉴于一个数组的平均值能够反映该数组的集中趋势, 因此, 这里选择某一距离 SampleSet j 内所有训练
样本输入的平均值最远的候选测试用例, 并补充至训练样本集, 该训练样本集将具有更优异的均匀分布特性, 以此
更新的代理模型将具备更好的异常值估计准确度.
∗ SampleSet j 补充方法, 其实现步骤如下所示: 一方面, 选
基于以上分析, 这里将给出对应 p 的训练样本集
j
∗
择面向 p 具有最高真实适应值的候选测试用例, 并将该候选测试用例及其真实适应值分别作为训练样本的
j
SampleSet j 内所有训练样本输入的平均值, 基于此, 选择距离
输入与输出, 补充至 SampleSet j ; 另一方面, 计算
该平均值最远的候选测试用例, 也将该候选测试用例及其真实适应值分别作为训练样本的输入与输出, 补充
至 SampleSet j .
∗ SurrModel j , 原因在于, 反复地更新代
补充面向 p 的训练样本集 SampleSet j 后, 并不能直接用于更新代理模型
j
理模型也需要一定的计算成本. 考虑到现有工作已经表明基于进化代数阈值来更新代理模型, 能够显著降低代理
模型的更新成本 [29] , 因此, 本节也设定一个进化代数阈值, 记为 UpdGen , 并当每一 task j 内种群进化 UpdGen 代数
∗
后, 基于面向 p 的最新训练样本集 SampleSet j , 更新代理模型 SurrModel j .
j
算法 6 给出了代理模型更新的伪代码, 即 Mod_Upd(iter,CTSet,RealFit j ) . 该算法的输入为当前进化的代数 iter ,
∗
候选测试用例集 CTSet 及其对应每条目标子路径 p 的真实适应值 RealFit j , 输出为更新后的代理模型 SurrModel j .
j
算法 6 中, 一方面, 基于 CTSet 和 RealFit j 补充面向的 p 训练样本集 SampleSet j (行 1–5); 另一方面, 当种群进化到
∗
j
阈值时, 基于最新的 SampleSet j , 更新和返回代理模型 (行 6–9).