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

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

Surr_Model_Set_Train(P ), SurrModelSet(EvoPop j ), Best_Ind_Select(EstFit j ), CovFlag_CTSet_Etc(BestInd j ), Mod_
∗

np
(iter,CTSet,RealFit j ) 的具体实施细节, 将分别在第 2.2–2.4 节中给出.
Upd

2.2 代理模型训练
基于进化优化的 MPI 程序路径覆盖测试用例生成过程中, 进化个体适应值的评价需要重复执行被测 MPI 程
序, 而被测程序的反复执行需要高昂的计算成本. 鉴于此, 训练合理的代理模型, 用于代替 MPI 程序的实际执行,
将能够显著降低 MPI 程序的执行成本.
训练代理模型之前, 需采样一定数量具有代表性的测试输入. 考虑到拉丁超立方采样已经成功应用于 MPI 程
序测试输入采样中, 且证明采样的测试输入集能够满足均匀分布 [17] , 因此, 这里同样基于拉丁超立方采样, 获取具
有代表性的测试输入集, 其实施细节如下: 首先, 平均划分测试输入 X 中每维变量 x i (i = 1,2,..., M) 的取值范围为
k R (k = 1,2,...,InSize) 内, 采样一个变量
k
InSize 个区间, 记为 {R |k = 1,2,...,InSize} ; 然后, 在变量 x i 对应的每一区间
i i
值, 并把这 InputSet (i = 1,2,..., M) 中, 不放回随
InSize 个变量值作为一个集合, 记为
InputSet ; 最后, 依次在每一
i i
机提取一个变量值, 用以组合成一个测试输入, 直至 InputSet 为空. 至此, 把采样的 InSize 个测试输入作为一个集
i
k
合, 记为 InputSet = {x |i = 1,2,..., M;k = 1,2,..., InSize} , 如公式 (3) 所示.
i
 1 1 1 
x x ... x
 1 2 M 
 
 
 
 
 x 2 x 2 ... x 2 
 
 1 2 M 
   
InputSet =   . . . .   (3)
 . . . . 
 . 
 . . . 
 
 
 
 
 
x InSize x InSize ... x InSize
1 2 M
采样具有代表性测试输入集合后, 需基于每一测试输入执行被测 MPI 程序, 并计算出该测试输入对目标路径
k
P ∗ np 内每一目标子路径的覆盖程度, 具体操作细节如下: 首先, 依次提取公式 (3) 中每一行变量值 InputSet (k = 1,
k
k InputSet 执行一个 MPI 程序, 以此获取该测试输入
2,...,InSize) = {x |i = 1,2,..., M} , 即一个测试输入; 然后, 基于
i
实际遍历该 MPI 程序内每一进程 π j ( j = 1,2,...,N) 的子路径, 表示为 p j (InputSet ) ; 最后, 基于公式 (1), 计算
k
k
k ∗ k ∗ Sim . 相应地, 基于所有测试输
p j (InputSet ) 与相应目标子路径 p 的相似度, 即 InputSet 对于 p 的覆盖程度, 记为 j
j
j
入执行 MPI 程序后, 将计算的面向目标路径 P ∗ 内每一目标子路径的覆盖程度矩阵表示为 CovMat = {Sim | j =
k
np j
1,2,...,N;k = 1,2,...,InSize} , 如公式 (4) 所示.

 Sim 1 Sim 1 ... Sim 1 
 1 2 N 
 
 
 
 2 2 2 
 
 Sim Sim ... Sim 
 1 2 N 
 
 
CovMat =   . . . .   (4)
 . . . . 
 . . . . 
 
 
 
 
 
 InSize InSize InSize 
Sim 1 Sim 2 ... Sim N
CovMat 内每一列覆
获取覆盖程度矩阵 CovMat 后, 需基于测试输入集合 InputSet 内每一行变量值与矩阵
盖程度, 形成对应目标路径 P ∗ 内每一目标子路径的训练样本集, 其具体实施步骤如下: 首先, 提取 InputSet 内第 k
np
k k CovMat 内第 行和第 列覆盖程
k
行变量值 InputSet = {x |i = 1,2,..., M} , 作为第 个训练样本的输入; 然后, 抽取 k j
i
k
k
j
∗
∗
度, 作为第 k 个训练样本面向第 条目标子路径 p 的输出, 即 Sim ; 接着, 针对 P ∗ 内 p , 形成第 个训练样本, 记
j j np j
k k k p 的 ∗ 个训练样本组成的集合, 记为
为 Sample = (InputSet ,Sim ) ; 最后, 重复上述步骤, 直至形成对应 InSize
j j j
k
SampleSet j ( j = 1,2,...,N) = {Sample |k = 1,2,...,InSize} .
j
基于形成的样本集, 训练代理模型之前, 需选定合适的代理模型类型. 考虑到克里金模型 (Kriging model) 已经
广泛应用于估计进化个体的适应值 [23,28] , 因此, 这里采用克里金模型作为代理模型类型. 随后, 这里将基于形成的
∗
SampleSet j , 训练对应目标路径 P ∗ 内每一目标子路径 p 的代理模型, 记为 SurrModel j . 合并所有代理模型, 得到
np j
对应 P ∗ 内所有目标子路径的代理模型集合, 记为 SurrModelSet = {SurrModel j | j = 1,2,...,N} .
np
算法 2 给出了训练代理模型的伪代码, 即 Surr_Model_Set_Train(P ) . 算法 2 的输入为第 np 条目标路径 P ∗ ,
∗
np np
输出为对应 P ∗ 内所有目标子路径的代理模型集合 SurrModelSet . 算法 2 首先采样测试输入集合和计算覆盖程度
np