论文精炼：CarpetFuzz

(Updated: )
Paper Distilled
, ,
views
Word count: 2.2k (~7 mins to read) Last updated:

论文精炼：CarpetFuzz

CarpetFuzz

Automatic Program Option Constraint Extraction from

Documentation for Fuzzing

核心Idea

现代的大规模软件项目往往存在大量程序选项。有些漏洞需要特定参数的组合触发。然而我们不能简单地穷举这些参数的排列组合，因为这会导致工作量指数级别的膨胀。我们注意到许多参数之间存在互斥、依赖等关系，而这些关系正记录在Manual中。因此本篇文章通过NLP的手段从文档中提取参数关系并应用于Fuzzing（基于AFL）中（名为CarpetFuzz，开源）。

关键参数：

参数组合准确性？Precision: 96.10% Recall: 88.85%

和暴力排列相比减少的工作量？68%

和一般的Fuzz相比，额外的路径？46%

这篇paper是比较工程性的工作？

精华所在是对隐式的选项关系进行提炼，而核心思路是找到不同选项描述中结构类似的句子对，从而得出两个选项的冲突关系。

行文逻辑

  • 大型项目（Kernel/Apache/…）结构极其复杂，攻击面广，利用链深。人工审阅代码几乎已经不可能。自动化是所有软件测试方法的大势所趋，包括Fuzz在内的自动化技术被官方探索应用。
  • 对于Fuzz而言，覆盖率是金标准（之一）。然而许多项目的覆盖率不够理想，文章认为其中一个原因是忽视了程序命令行参数对程序运行的影响。某些代码块只有在特定参数组合下才存在遍历的可能。
  • 然而简单的穷举不可行：ImageMagick有242个不同的选项。参数的常见组合也许是个好想法，文章的idea则是只保留可行组合，而非像先前的一些工作直接把参数纳入变异。
  • 难点：选项间的依赖关系在文档中以自然语言描述。Solution：NLP
    • 刁钻的示例（强context）
      • 依赖：-o在-g启用时将添加额外调试输出
      • 冲突：xx选项仅在正式环境中启用……要切换到正式环境请使用—release

NLP具体方法

  1. 给定一个程序的文档
  2. CarpetFuzz解析“OPTIONS”部分提取出所有选项及其相应的statement
  3. CarpetFuzz使用机器学习来确定statement中是否声明了某种关系
    1. 由于这样的statement在文档中占比小，文章使用基于熵的不确定性采样（主动学习），来减少人工标记训练数据的工作量。
    2. 针对上述的隐晦的自然语言statement，解决方案是让CarpetFuzz总结一系列“隐含statement”的特征，并利用NLP找到满足这些特征的所有“sentence pairs”
  4. 这样依赖关系就可以被确定，从而构建一个依赖树
  5. CarpetFuzz正向/反向遍历依赖树中找到与关系相关的节点*
    1. （说实话我没看懂这边）
  6. CarpetFuzz基于语言学，利用polarity-based的有限状态机确定具体的关系*
    1. (其实就是双重否定表肯定这种比较简单的状态机)
  7. CarpetFuzz最终得以筛选出所有可用参数组合

背景工作

经典Fuzzing流程，Option预定义好并固定不参与实际执行

经典Fuzzing流程，Option预定义好并固定不参与实际执行

关于命令行参数相关Fuzzing的其他工作

AFLargv：限制命令行参数的数量和范围；

Song等 ：通过检查参数对程序运行的影响来判断有效性；

Zeller等人 ：通过特定选项解析模块推断。

局限性：效率低

ConfigFuzz ：手动检查，需要熟悉测试的目标软件用法，对测试人员以及大规模测试是无法接受的。

基于NLP的其他工作

主要方向：代码注释+严格格式化文档，局限性强

程序结构

Untitled

Overview of CarpetFuzz. EDR: explicitly declared
relationships, IDR: implicitly declared relationships.

R=Relationship

数据集来源：man 命令的说明页面

拆分句子→识别包含选项关系的句子（R句子）

关系：冲突、依赖、（蕴含、相似和取代 =冲突，因为复用不能有效增加覆盖率）

寻找R句子

寻找R句子

添加主语是为了避免NLP的解析错误。

还有一个预处理是把选项名字替换为自定义标识符以免干扰分析（这怎么发现的？）。

某个选项的关键是谓词（效果）与目标（作用对象）。

隐式的冲突参数

实际上，隐式的描述语句只涉及冲突：例如，-B和-L选项的描述分别是“Force output to be written with Big-Endian byte order”和“Force output to be written with Little-Endian byte order”

那么这些句子的语法树结构是相同的。因此这些“sentence pairs”很关键，需要被提取识别。

同时还有一些常见的冲突写法，例如用| 分隔。当然这也可能是别名，具体看描述句子中是“这些参数”还是“这个参数”来确定到底是别名还是一些冲突的参数。

极性分析

情感分析常用，这里用来解析参数之间的冲突

Untitled

例如主语A对(B&C)呈现negative的极性，我们就可以认为A不能与B/C一起使用。

神经网络实现的分类器来判断一个句子有多大可能是R句子。准确率是比较高的，但召回率比我想的多。

实际测试

文章首先认为参数数量超过一定数量没有实际意义（大部分生产环境下也用不到更多的）。测试也表明基本上超过6个参数就很难有新的发现。所以使用6-wise

为了找到更有价值的参数组合，测试器会关注参数的变化能够引导出多少新的代码路径覆盖率；对于太低价值的组合会逐渐被剪枝掉。

那这边实际上是Song.的工作的Idea了。

杂项

剩下的主要是一些对实现细节（例如模型超参数、预处理工作）的一些描述。

然后还有就是有效性度量，主要是准确率和性能速度。

1
2
3
4
5
6
7
8
9

Q1. CarpetFuzz的性能如何？
Q2. 关系识别的准确性如何？（那必须好）
Q3. 关系提取的准确性如何？（那必须好）
**Q4. CarpetFuzz的优先级排序技术的有效性如何？
  “结果显示，相比随机抽样，我们的剪枝技术可以减少更多组合（98.91%），
同时仅略微损失边的覆盖率（2.54%）”**
Q5. 与最先进技术相比，CarpetFuzz的模糊测试性能如何？（那必须好，因为前人的工作看起来确实比较粗糙）
Q6. CarpetFuzz能否发现真实世界的漏洞？（事实证明可以）

在5次48h的fuzzing中，

结果显示，平均有94.59%的CarpetFuzz的唯一边没有被其他模糊器发现，CarpetFuzz平均能够帮助AFL发现多出45.97%的边。

边指的是构成代码路径的jmp之类的跳转？

“唯一边”这个性能指标确实可以展示其能发现新的未被探索过的代码路径。

Real-world测试也发现了很多特殊的crash，然后搞到43个0day

局限性

这篇文章也指出局限性主要来自NLP模型的准确率问题（猜到了）。不过好在这基本只会导致跑太多无效的测试，并不怎么漏报。

还有一个问题是缺乏人类常识，例如他不知道水平和垂直是反义词。解决方案是知识图谱（是否有点太古典机器学习了）

我怎么觉得这俩问题都是大语言模型最擅长的？

文章总结

原文摘抄如下：

我们设计并实现了CarpetFuzz，一种基于自然语言处理的模糊测试辅助技术，用于提取程序选项约束。通过采用主动学习、机器学习和自然语言处理技术，CarpetFuzz能够准确地从文档中提取选项之间的关系，并过滤掉67.91%的组合选项。借助经过修剪的有效组合，CarpetFuzz帮助AFL在20个常用程序中找到了其他模糊器无法发现的路径的增加了45.97%，并发现了57个独特的崩溃，其中30个被分配了CVE ID。此外，CarpetFuzz在之前的基准测试中发现了94个独特的崩溃，是之前工作的1.71倍。

感谢您的阅读🙂