Page 205 - 《软件学报》2025年第10期

4602 软件学报 2025 年第 36 卷第 10 期

α > 10 ∩ s , 0 then
22. if

23. for i = 1 → Total number of mutation operators n do
s ∑ k
24. e ω+ ← − → ω

e /s
k=1
f
∑ k
25. e ω− ← − → ω
e / f

k=1

26. R i ← ∥ e ω+ −e ω− ∥
27. χ.FunctionParameterUpdate(R i ,θ i )
28. end for
29. end if
算法 2 的第 1–21 行主要利用变异算子的权重来选择算子执行和执行次数. 第 1 次执行输入相同的初始变异
算子权重和执行次数限制, 之后每次迭代都使用新的变异算子权重. 输出是每个变异算子的执行次数. 值得一提的
是, 由于该算法在 CUAF 漏洞演化研究中用于生成变异样本, 样本量较小, 因此生成更高阶的变异只会增加程序
的复杂度, 正因为这个原因, 我们默认为这部分分配了较小的值. 然而, 当算法针对涉及较长代码跨度的漏洞类型

时, 需要为 x i 分配较高的初始值, 以确保突变能够覆盖更极端的情况. 优化函数 χ.FunctionTimesUpdate(x i ) 通过改
变 x i 来使得 F (X) 的值接近局部最大值, 因为 F (X) 的值不可以无限制地增长. 这是因为变异算子执行超过一定次
数可能导致变异体偏离现实世界中可能发生的情况.
该算法的第 22–29 行旨在调整变异算子的各自权重, 以适应特定类型的漏洞形成模式. 这是通过为与选择概
率 P i 相对应的权重设置变异算子执行的次数限制来实现的. 接下来, 算法将变异算子执行过程向量化. 然后, 它重
复执行突变, 根据生成的无效样本的比例为每个变异算子找到最佳向量. 最后, 函数 χ.FunctionParameterUpdate(R i ,θ i )
会在每轮执行后根据向量的绝对差异更新变异算子的权重. MOPSG 算法需要知道已经产生的变异样本是否是有
效的漏洞, 判定有效的过程由正则匹配过滤和人工观察判断结合完成.
2.6 变异策略优化
本文在抽象语法树层面执行变异算子的变异过程中, 为了解决变异样本数量爆发式增长的问题, 本节提出
了两种启发式方法进行优化. 第 1 种是固定关键算子顺序, 这可以避免一些不必要的变异操作在高阶变异过程
中错误地介入. 例如, 在演化生成 CUAF 漏洞过程中, 不含有线程的变异样本是无法触发该漏洞的, 则优先执行
增加线程变异算子能防止此类无效样本的产生. 但是, 随着变异过程的进行, 再次执行增加线程变异算子会显著
降低效率, 因此需要在更新变异算子序列后对其进行人工调整. 第 2 种启发式方法是部分子树截断, 这可以限制
变异顺序和次数, 从而降低无效样本的数量. 在执行变异算子时, 先将变异操作应用于抽象语法树的某个子树
上, 然后根据其效果再决定是否应该继续执行该变异操作. 这样可以避免无效样本的产生, 同时提高变异操作的
效率.
在利用算法 2 对样本代码进行变异来更新变异算子权重的过程结束后, 可以根据结果识别在多个轮次中权重
一直保持较高水平的变异算子, 然后考虑固定该变异算子再进行测试. 如果固定顺序整体比例降低, 则足以证明该
变异算子是演化形成漏洞应该介入的. 这种方法可以减少无效样本的数量, 同时提高演化算法的效率, 从而更快地
找到合适的漏洞.
部分子树截断算法是针对某一类漏洞的特征与共性, 对变异样本的子树进行识别并选择性停止某些样本继续
变异的过程. 该过程如算法 3 所示.

算法 3. 部分子树截断算法.
输入: 待变异的抽象语法树 T;
输出: 变异后的抽象语法树集合 T' = t 1 ,t 2 ,...,t n .