模糊测试中的位置自适应变异调度策略.pdf

努力努力再努力

10页

0次

2025-04-19

100墨值下载

模糊测试中的位置自适应变异调度策略

杨智

①

徐航

*①

桑伟泉

①

孙浩东

①

金舒原

②

①

(信息工程大学密码工程学院郑州 450004)

②

(中山大学计算机学院广州 510275)

摘要：种子自适应变异调度策略是基于变异的模糊测试中最新的技术，该技术能够根据种子的语法和语义特征

自适应地调整变异算子的概率分布，然而其存在两个问题：(1)无法根据变异位置自适应地调整概率分布；(2)使

用的汤普森采样算法在模糊测试场景中容易导致学习到的概率分布接近平均分布，进而导致变异调度策略失效。

针对上述问题，该文提出一种位置自适应变异调度策略，通过一种自定义的双层多臂老虎机模型为变异位置和变

异算子建立联系，并且采用置信区间上界算法选择变异算子，实现位置自适应的同时避免了出现平均分布的问

题。基于American Fuzzy Lop(AFL)实现了位置自适应的模糊测试器 (PAMSSAFL)，实验结果表明位置自适应

的变异调度策略能明显提升模糊测试器的bug发现能力和覆盖能力。

关键词：漏洞挖掘；模糊测试；变异；覆盖率

中图分类号：TN915.08; TP393.08 文献标识码：A 文章编号：1009-5896(2024)09-3797-10

DOI: 10.11999/JEIT240060

Position-Adaptive Mutation Scheduling Strategy in Fuzzing

YANG Zhi

①

XU Hang

①

SANG Weiquan

①

SUN Haodong

①

JIN Shuyuan

②

①

(School of Cryptographic Engineering, Information Engineering University, Zhengzhou 450004, China)

②

(School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510275, China)

Abstract: The seed-adaptive mutation scheduling strategy is the latest technology in mutation-based fuzzing,

which can adaptively adjust the probability distribution of the mutation operators according to the syntax and

semantic characteristics of the seed. However, it has two problems: (1) it is unable to adaptively adjust the

probability distribution according to the mutation position; (2) The Thompson Sampling algorithm used in the

fuzzing scenario is easy to lead to the learned probability distribution close to the average distribution, which

leads to the failure of the mutation scheduling strategy. Focusing on the above problems, a position-adaptive

mutation scheduling strategy is proposed. This technology establishes the relationship between the mutation

position and the mutation operators through a user-defined double-layer multi-armed bandit model, and uses

the Upper Confidence Bound algorithm to select the mutation operator, so as to achieve position adaptation

and avoid the problem of average distribution. The position-adaptive fuzzer Position-Adaptive Mutation

Scheduling Strategy AFL (PAMSSAFL) is implemented based on American Fuzzy Lop (AFL). The comparison

results show that the position-adaptive mutation scheduling strategy can improve the bug detection ability and

coverage ability of the fuzzer.

Key words: Vulnerability mining; Fuzzing; Mutation; Coverage

1 引言

基于变异的模糊测试通过在种子的不同位置应

用不同的变异算子生成大量的测试用例，然后将测试

用例输入到目标程序执行，其因简单高效而倍受从

业者青睐，当前主流的模糊测试器如AFL (American

Fuzzy Lop)

[1]

, Honggfuzz

[2]

和LibFuzzer

[3]

均采用变

异的方式生成测试用例。为了让生成的测试用例尽

可能多样化，基于变异的模糊测试器通常包括多种

变异算子，并且可能将任意一个变异算子应用在种

子的任意变异位置。变异调度是指每一次变异时变

异算子的选择，最新的变异调度策略是由Lee等人

[4]

提出的种子自适应的变异调度策略，该策略首先根

收稿日期：2024-01-26；改回日期：2024-07-13；网络出版：2024-08-02

*通信作者：徐航　1174290091@qq.com

基金项目：国家自然科学基金(62176265)

Foundation Item: The National Natural Science Foundation of

China (62176265)

第46卷第9期电子与信息学报 Vol. 46No. 9

2024年9月 Journal of Electronics & Information Technology Sept. 2024

据种子的语法和语义特征将种子聚类到最合适的种

子组，然后以种子组为单位利用汤普森采样算法

[5]

预估变异算子的期望值形成概率分布，因此变异算

子的概率分布是根据种子组发生变化的，但是其仍

存在如下两个问题：(1)在所有变异位置都利用相

同的概率分布选择变异算子，但实际上在不同变异

位置应用同一个变异算子的有效性不同，这导致可

能错过最有效的变异位置和变异算子的组合；(2)该

技术使用汤普森采样算法预估变异算子的期望值，

该算法需要将执行结果分为成功和失败两类，但定

制的分类标准在测试一部分程序时容易出现平均分

布进而导致变异调度策略失效。

考虑到同一个变异算子应用在种子不同变异位

置的有效性是不一样的，本文在种子自适应的变异

调度策略的基础上提出了一种位置自适应变异调度

策略。本文设计了一种双层多臂老虎机模型为变异

位置和变异算子建立联系，以此达到位置自适应的

目的，并采用置信区间上界算法

[6]

解决模糊测试场

景中的多臂老虎机问题，该强化学习算法仅需设置

成功的奖励值，避免了制定分类标准的问题。本文

基于AFL实现了位置自适应的模糊测试器PAMS-

SAFL(Position-Adaptive Mutation Scheduling

Strategy AFL)，与AFL

[1]

、DARWIN

[7]

和Seam-

Fuzz

[4]

进行对比实验，结果表明位置自适应的变异

调度策略在bug发现能力和覆盖能力方面优于已有

的变异调度策略。

2 相关工作

基于变异的模糊测试器通常实现一个循环，在

单次循环内选择一个种子进行变异，生成大量的测

试用例输入到目标程序中执行，然后进入下一轮循

环。以AFL

[1]

为例，每一轮循环的变异部分可以分

为两个阶段：确定变异和随机变异。确定变异生成

的测试用例是固定的，所以仅当种子首次进入循环

时才采用确定变异。随机变异首先根据种子的长

度、执行速度等特征计算出需要生成的测试用例数

量，然后对于每个待生成的测试用例，随机选择变

异堆叠次数(应用变异算子的次数)，每次堆叠时在

随机位置应用随机的变异算子。此外，在一轮循环

中没有覆盖任何新路径时，便会启动拼接，拼接指

组合一个种子的前半段和另一个种子的后半段形成

新的种子，拼接产生的新种子会重新进行随机变异。

在基于变异的模糊测试器中，确定变异不具有随机

性，因此提供了禁用该功能的参数选项，拼接则在

特定情况下启用，所以随机变异是最主要的测试用

例生成手段，并且随机变异的可拓展性很强，故现

有模糊测试器都将精力集中在随机变异阶段

[4,7]

。

随机变异阶段包含一组预定义的变异算子，可以分

为5种类型，如表1所示。

变异算子的选择即变异调度，按照变异调度策

略可以将基于变异的模糊测试器分为3类：程序无

感知的模糊测试器、程序自适应的模糊测试器、种

子自适应的模糊测试器。程序无感知的模糊测试器，

如AFL

[1]

，测试任何目标程序时都随机选择变异算

子，所以变异算子的概率分布永远为平均分布，沿

用AFL原有变异调度策略的模糊测试器

[8–10]

均为程

序无感知的。Lü等人

[11]

通过实验证明在测试相同

程序时，各个变异算子的有效性不同，并且在测试

不同程序时，相同变异算子的有效性也不同，因此

设计了一款程序自适应的模糊测试器MOPT-AFL，

该模糊测试器利用定制的粒子群优化算法动态计算

变异算子的最优概率分布，但是其包含多个参数，

调整参数使模糊测试器的性能达到最优需要丰厚的

专家知识；DARWIN

[7]

利用进化算法系统地优化变

异算子的概率分布，相较于MOPT-AFL，其采用

的算法复杂度低，并且不需要用户手动配置参数，

对用户更加友好；HavocMAB

[12]

将变异算子分为两

大类(块操作、单元操作)，并利用强化学习方法学

习最优的操作类别，但其对变异算子的分类粒度过

粗。以上3款模糊测试器选择变异算子的概率分布

都能根据目标程序动态调整，但是没有考虑将变异

算子应用至不同种子的有效性。

种子自适应变异调度策略

[4]

是基于变异的模糊

测试中最新的技术，其选择变异算子的概率分布随

着种子发生变化，整体流程如图1所示，与传统的

技术相比包含两个独特部分：种子聚类和自适应变

异调度。

(1) 种子聚类：考虑到同一个变异算子应用至

不同种子的有效性是不一样的，但是每次测试时保

存下来的种子有成百上千个，因此为每个种子单独

学习变异算子概率分布将会消耗大量资源，此外，

每个种子被选择的次数很少，这导致很难快速学习

到收敛的概率分布，并且已学习到的概率分布难以

被应用。为了解决上述问题，现有方法

[4]

将行为和

表 1 变异算子类型

类型释义

Flip(k) 翻转第k个比特，0翻转为1，1翻转为0

Overwrite(s, e, v) 将第s个字节至第e个字节的内容复写为v

Arithmetic(s, e, v)

将第s个字节至第e个字节的内容与

v进行算术运算

Delete(s, l) 从第s个字节开始删除长度l的内容

Insert(s, v) 在第s个字节之后插入v

3798 电子与信息学报第 46 卷

of 10

100墨值下载

测试

关注

评论