Page 33 - 《软件学报》2025年第7期

2954 软件学报 2025 年第 36 卷第 7 期

挑战 3. 覆盖新分支时的权重奖励. 在灰盒模糊测试工具中, 分支覆盖信息用以指导灰盒模糊测试如何选择种
子程序. 由于我们替换了灰盒模糊测试工具中的选择策略, 因此我们的算法需要承担起这部分功能. 更具体地, 我
′
们需要在当前变异操作符 o 应用在程序 p 上所生成的程序 p 探索到新的分支时, 进行权重调整, 以奖励这样的行为.

3.1 动态权重选择算法
给定种子程序池 P 和变异操作符集合 O, 该算法的重心是维护一个权重映射 W = {(p,o) 7→ w|(p,o) ∈ P×O}.
,
在模糊测试进行到选择种子程序和变异操作符这一阶段的时候, 通过 W 加权采样出一组 (p,o), 其中 p ∈ P o ∈ O,
p
′
并将操作符 o 应用于 p 获得新的程序 .
我们将选择操作符和种子程序表述为算法 4 中的 select 函数 (对应前文算法 1 的第 2 行所调用的函数), 给
定动态维护的权重映射 W = {(p,o) 7→ w|(p,o) ∈ P×O}, 在进行选择时, 选择算法根据当前权重采样一个 (p,o) 组合
(算法 4 第 6 行) 返回给算法 1 进行变异.

算法 4. 寻找适合的基于语义信息的变异操作符和种子程序.

全局: 种子程序池 P, 变异操作符集合 O, 权重映射 W : P×O 7→ weight;
输出: (p,o) 一组可以进行变异操作的操作符 o 和程序 p.
1. function select() {
2. E ← {(p,o)|W [e] =⊥}
|E|
(0,1) <
3. if (random ) {
|P×O|
4. return randomly_select (E)
5. } else {
6. return weighted_sample (P×O− E,W)
7. }
8. }

⊥, 表示当前没有历史信息可供参考, 所有权重均未知. 这样的设计是为了在
权重映射 W 初始化所有权重为
(p,o) 组合. 对于这部分组
整个模糊测试刚开始的阶段, 以及新的程序被加入的时候, 区分出没有变异历史记录的
合, 我们以一定概率进行完全随机采样 (算法 4 第 4 行), 该概率会随着权重映射 W 中有记录的项数占比提升而降
低. 对应算法 4 第 3 行 |E| 越大, random (0,1) < |E|/|P×O| 的概率越小, 进行第 4 行 randomly_select (E) 的概率也越

小. 且当 |E| = |P×O| 时, random (0,1) < |E|/|P×O| 的概率为 0, 意味着当所有组合都有记录时, 不再进行完全随机
采样.

3.1.1 权重更新策略
前文描述了在给定权重映射 W 的情况下, 如何进行采样以选出合适的程序 p 和变异操作符 o. 而对于权重映
p 以及权重映
′
射 W 如何进行更新, 这里会详细展开说明. 具体来说, 给定变异操作符 o, 种子程序 p, 变异后的程序
射 W, 我们会就表 2 所示的事件对权重映射 W 进行调整.

表 2 动态权重算法关注的事件和会采取的策略

事件 采取动作
用 o 变异 p 失败或生成重复程序 给组合 (p,o) 降低权重
p 已多次失败且权重低于阈值
用 o 变异 将组合 (p,o) 从权重映射 W 中移除
成功变异但未覆盖新分支 给组合 (p,o) 增加权重
p 覆盖了新的分支 给组合 (p,o) 增加权重, 并对所有 o ∈ O 将 (p ,o) 加入权重映射 W
′
′

算法 5 描述了如何基于表 2 所示的事件对权重映射 W 进行调整更新, 对应权重更新函数记为 update, 该函数
同样也对应前文算法 1 第 4 行所调用的函数. 该函数用以在操作符 o 被用于变异程序 p 之后, 根据变异的结果和