原文标题：POLYFUZZ: Holistic Greybox Fuzzing of Multi-Language Systems
原文作者：Wen Li；Jinyang Ruan；Guangbei Yi；Long Cheng；Xiapu Luo；Haipeng Cai
发表会议：In 32nd USENIX Security Symposium (USENIX Security 23)
PDF：https://www.usenix.org/system/files/sec23summer_411-li_wen-prepub.pdf
视频：https://www.usenix.org/conference/usenixsecurity23/presentation/li-wen
主题类型：漏洞检测
笔记作者：柳蓉@Web攻击检测与追踪
主编：黄诚@安全学术圈

1、研究概述

PolyFuzz的基本框架如图1所示，主要由三个阶段组成：

(1) 静态分析和插桩

(2) 敏感分析与种子生成（Sensitivity analysis & seed generation）

(3) 核心模糊测试

PolyFuzz需要两个输入：待测程序P和初始种子。其基本流程为：在第一阶段将P的每个函数翻译为语言无关的中间语言表示，提取分支变量约束，对P进行插桩；在第二阶段生成更有针对性的种子，第二阶段包含两种模式：模糊测试模式（fuzzing mode）和学习模式（learning mode），当第二阶段的动态事件监控器检测到内存数据库中的分支变量更新，第二阶段即从模糊测试模式切换到学习模式，通过对种子输入和分支变量的回归模型训练学习，进行敏感分析，生成与分支变量关联度更高的种子，切换回fuzzing mode继续进行模糊测试；第三个阶段进行路径覆盖引导的核心模糊测试，产生结果输出。

图 1 PolyFuzz流程概述

第一阶段主要包括三个部分：

（1）IR翻译：作者实现了一个自定义IR（SAIR），翻译针对每个基本块进行，并且记录每个基本块的前驱和后继来构建控制流图，算法如图2所示。

图 2 翻译给定函数为SAIR

（2）插桩引导计算：作者提出通过删除控制流图中的支配基本块与后支配基本块实现最小化插桩。算法如图3所示。

图 3 计算插桩引导

（3）静态/动态插桩：在基于最小化插桩位置的基础上进行插桩，对于编译语言进行静态插桩（C），对于解释型语言（Python）进行动态插桩。

第二阶段解决的主要问题是如何在灰盒测试中生成优质的种子，包括四个部分：

（1）动态事件监控：针对第一阶段生成的插桩程序P’进行模糊测试，同时将过程中产生的动态事件记录到shadow event queue中，监控器从队列中提取事件信息存储到内存数据库中，检查是否覆盖了新的分支变量，如果产生了改变，则切换模式进入到learning mode中。

（2）种子划分与采样：作者将种子划分为定长的种子块进行变异，在对种子进行分块之后，PolyFuzz对每个种子块的取值范围进行采样：对当前的值进行随机变异，之后重新运行P’，利用动态事件监控器监控分支变量值发生的变化，最终生成SBP(seed block, branch variable)列表存储在内存数据库中。算法如图4所示。

图 4 种子划分与采样算法

（3）分支输入回归模型：通过对当前内存数据库中存储的SBP进行回归模型的训练来捕获分支变量和种子块之间的关系，通过回归模型对扩展后的相应分支约束值进行预测而生成新的种子块，算法如图5所示。

图 5 分支输入回归模型算法

（4）种子生成：PolyFuzz通过聚合回归模型生成的种子块生成新的种子。

第三阶段是核心模糊测试阶段：使用AFL++进行模糊测试（包括种子选择、变异和bug报告等）。

2、贡献分析

a) 贡献点1：论文针对当前主流的fuzzer大多适用于单语言程序模糊测试的问题，提出了适用于多语言程序模糊测试的方法，实现了语言无关的模糊测试；

b) 贡献点2：论文针对利用单语言fuzzer对多语言编程的程序模糊测试过程中出现缺少反馈无法进行覆盖引导的问题，提出了将不同语言表达为相同IR实现统一插桩获取反馈的方法，实现了自定义中间语言表示SAIR；

c) 贡献点3：论文针对模糊测试过程中种子变异有效性较低的问题，提出了利用回归模型学习种子块与分支变量之间关系的方法，实现了利用回归模型进行种子划分与生成；

3、代码分析

代码链接：https://github.com/Daybreak2019/PolyFuzz/tree/main

a) 代码使用类库分析，是否全为开源类库的集成？

代码使用到的库包括：AFL++；LLVM库；Soot框架 不全为开源类库的集成，PolyFuzz为作者提出针对多编程语言程序进行模糊测试的框架。

b) 代码实现难度及工作量评估；

算法复杂度：PolyFuzz是一种复杂的模糊测试方法，它结合了多个模糊测试技术，包括语法模糊测试、语义模糊测试和混合模糊测试。实现PolyFuzz需要理解并实现这些模糊测试技术，以及它们的组合和交互。

代码复杂度：PolyFuzz的实现涉及多个组件和模块，包括模糊生成器、代码覆盖率分析、测试用例选择策略等。这些组件之间需要进行合理的组织和协调，确保它们能够协同工作。此外，PolyFuzz还需要与目标程序进行交互，并获取程序的执行结果和覆盖信息。因此，代码的实现比较复杂，并需要充分考虑组件之间的交互和数据传递。

因此，PolyFuzz工作的代码实现难度可以被认为是中等到较高的。

工作量：PolyFuzz整体实现包括了12KLoC，其中Java部分包括0.6KLoC，Python包括1.2KLoC，C部分包括0.3KLoC。结合代码中各个组件的实现部分，以及在论文中作者进行的多个比较实验，PolyFuzz的工作量属于中等偏高。

c) 代码关键实现的功能（模块）

PolyFuzz的代码模块结构如图6所示：

• AFL++：PolyFuzz的核心模糊测试模块，使用AFL++工具完成，对开源工具AFL++的一些编译模式和选项进行了修改，引入了frida_mode（-O）模式进行纯二进制模糊测试。
• SAIR Parser：这部分代码实现了作者提出的自定义IR，作者提供的开源代码中仅实现了Java、C和Python语言的IR翻译；

针对C语言的翻译使用了LLVM库中的clang编译器实现；

针对Java语言的翻译使用了Soot框架成对Java字节码的分析和处理；

针对Python语言的翻译使用了AST模块完成翻译，使用Pybind进行动态插桩。

• IGC（Instrumentation guidance computation）：这部分代码是为了完成插桩引导计算，在基于CFG（Control Flow Graph）图的基础上实现最小化插桩，实现构建控制流图、判断支配关系和插入插桩语句。

• DynTrace：此模块具有三个主要功能：初始化用于在AFL++中进行覆盖率计算的共享内存字节映射的API；初始化用于在SASG期间缓存已覆盖的分支变量的影子事件队列的API；提供跟踪动态事件（例如块信息、分支变量）的API。所有这些API可以直接由语言的插桩器调用，或者通过相应语言接口的包装器（例如Java的JNI包装器）间接调用，然后插入到模糊测试目标中。即DynTrace是PolyFuzz中的一个C库，提供了初始化覆盖计算和事件跟踪所需的API功能，可以通过插桩器直接调用或通过语言接口的包装器插入到被模糊测试的目标代码中。

• SASG（sensitivity analysis and seed generation）：这部分代码实现对种子块的划分和种子块与分支变量之间的语义关系进行回归模型建模学习，以针对性对种子进行变异。

图 6 PolyFuzz代码结构

4、论文点评

论文针对目前主流的fuzzer设计是针对单一编程语言设计，从而无法对多编程语言进行高效的模糊测试这一问题进行了研究，提出了PolyFuzz这一多编程语言模糊测试框架。但同时本文提出的框架也存在一定的问题：

（1）本文提出的SAIR中对于变量类型的分类只包括整型变量和非整型变量两种，但是在真实程序中依旧存在一定的非整型的分支变量，对于这部分的分支变量的探讨在PolyFuzz的设计中是缺失的。也就导致后续PolyFuzz试图学习分支变量和输入之间的语义关系不完整。

（2）本文提出SASG试图学习输入和分支变量之间的语义关系，但是输入和分支变量之间的相关性可能过于复杂，无法用任何类型的回归模型来建模，甚至都不存在。在这种情况下，SASG可能没有帮助。

（3）在种子划分和采样阶段，在随机突变过程中，程序的执行路径可能会发生变化，从而影响到分支变量的覆盖范围，从而导致无法收集到足够的数据来训练回归模型。当种子长度过长时，针对种子进行的块划分和采样的过程需要消耗的时间也会随之变长，这就会导致框架停留在SASG阶段时间过长，导致模糊测试的整体效率下降。

未来的改进方向：

（1）处理非整数分支变量需要解决的问题包括如何统一在不同的语言中的数据表示以及什么样的数据存储方式是高效的。例如，Python对象（例如，列表）或Java对象（例如，散列表）。

（2）对于分支变量和种子块之间不存在相关性的情况，主要包括两类变量：函数的返回值（只取特定的值，比如0或1）；以及从配置中获取的值（例如，从环境变量或配置文件中读取）。如何高效对种子进行变异影响这部分分支变量从而探索到更多的程序路径是未来可以改进的方向。

（3）针对长种子会影响模糊测试效率的问题可以通过将采样大小翻倍的方式进行改进，同时对采样的长度进行限制，从而提高种子生成时的效率。

5、论文文献

[1].Li W, Ruan J, Yi G, et al. POLYFUZZ: Holistic Greybox Fuzzing of Multi-Language Systems[J].

6、作者

• Wen Li，华盛顿州立大学普尔曼分校博士生，研究兴趣软件安全、程序分析、网络安全、网络流量分析/模式匹配。https://awen-li.github.io/
• Haipeng Cai，华盛顿州立大学普尔曼分校副教授，研究主要集中在软件工程和软件安全，目前的重点是程序分析和机器/深度学习，用于多语言软件、分布式系统和移动应用程序的安全应用。目前正在招人中， https://chapering.github.io/

安全学术圈招募队友-ing 
有兴趣加入学术圈的请联系 secdr#qq.com