白泽带你读论文 | STOCHFUZZ

STOCHFUZZ: Sound and Cost-effective Fuzzing of Stripped Binaries by Incremental and Stochastic Rewriting

如需转载请注明出处，侵权必究。

本文发表于IEEE Symposium on Security and Privacy (Oakland) 2021，第一作者是来自于普渡大学的Zhuo Zhang。

1. 背景

Fuzzing技术由于在运行时需要实时地收集程序运行中的一些信息，例如分支覆盖情况等，所以需要在被Fuzz的程序中插入一些相关的代码，例如AFL的AFL Trampoline。对于有源码的Fuzzing，这显然是比较容易的，但无源码的情况（称为Binary-only Fuzzing）则比较困难。现有的Binary-only Fuzzing解决方案主要有以下三种：

(I) 基于硬件特性（如Intel PT）来支持Fuzzing。代表工作是ptfuzzer。这些收集到的运行时信息数量会非常大，因此需要后续的处理。另外，这种方法收集除了控制流trace之外的信息比较困难。

(II) 使用QEMU、PIN等动态二进制重写引擎，在程序运行时（on-the-fly）对它本身进行插桩或重写。代表工作是afl-qemu。这种方法看上去是可靠的，但是开销巨大，对比有源码的fuzz会慢4-5倍。

(III) 在Fuzzing执行之前对程序本身进行二进制重写，然后再Fuzz。代表工作是e9patch、ddisasm。然而，由于stripped binary缺少符号信息，这种方法本身相当困难，有很多挑战，例如区分代码与数据、确定间接跳转目标等。目前的解决方案都是基于启发式规则，所以不可靠，而且往往要求binary本身满足某些特性（没有inline data，重定位信息可用等）。

为了解决这些缺陷，作者提出了STOCHFUZZ，一种新的递增性、随机性的二进制重写技术，可以用来做stripped binary的无源码fuzzing的目标程序插桩，并且能够兼顾可靠性和效率。

 

2. 设计与实现

STOCHFUZZ基于两个基本的Insight:

(I) Fuzzing不断变换输入然后执行的过程也可以被增强为不断即时变换程序然后执行，所以，反汇编和静态重写可以随着fuzzing逐渐提升性能，解决由于缺少符号信息导致的难以离线判定间接跳转的问题。

(II) Fuzzing是一个高重复性的过程，提供了很多试错的机会。所以，可以尝试不同的代码/数据分割，在运行的过程中，可以不断收集很多的样本用来修正二进制重写。

系统的工作流程如下图所示，可以分为5个部分：概率分析器、二进制重写器、程序分发器、执行引擎，以及崩溃分析器。

概率分析器的工作流程如下：

(I) 将二进制代码逐字节反汇编，并收集代码中的一系列事实，作者规定了4种事实的类型：

- 某一地址范围内是一个合法的指令。

- 某一地址是另一地址的后继等。

- 某一地址的指令读或写了某一寄存器。

- 某一地址范围是一个以0x00结尾的ASCII字符串。

收集完成之后，该工具构造了一个UCFG，与普通CFG的区别是将所有地址的合法指令均呈现在图中，如下图所示。

 

(II) 推断谓词。本文定义了3种谓词：

- 某一地址到另一地址明确可达。

- 从某一地址到另一地址过程中，某寄存器存活。

- 某地址是指令/数据。

该工具根据之前收集到的事实进行谓词推断，具体推断规则如下图所示。

 

(III) 计算概率。通过之前的计算，每个地址都会有一个是代码的先验概率观察值和是数据的先验概率观察值。由于涉及的节点非常多，传统的sum-product算法不太适合，所以作者提出了一种新的one-step product算法去计算这个后验概率。作者将UCFG中的循环子图称为SCC，在SCC内部使用乘积算法把先验概率的观察值乘起来，认为在一个SCC中所有的结点都有相同的代码观察值。数据观察值对于每个地址，用规则8单独处理。最后每个地址都有一个聚合代码观察值Oneg和聚合数据观察值Opos，构造一个简单的因子图，有两个因子结点Fcode和Fdata，令随机变量a表示该地址是为数据（1）还是代码（0），a的后验概率是两个因素的归一化乘积。

计算完成之后，对于每一个地址都得到一个是代码/数据的概率。重写器的工作为根据该概率值，生成多个样本程序，每一个地址以（1-数据概率值）的概率被替换为hlt（停机指令），然后分发给执行引擎执行。如果一个地址被替换为了hlt，就说明这次运行认为这个地址是代码。另外，重写器还会进行一些地址转换工作，例如将call转化为push+jmp等，以及一般的Binary-only fuzzing重写器的工作，即将原代码重定位到Shadow memory中，然后在合适的位置插入AFL Trampoline等Fuzzing相关代码。

在经过执行引擎的执行之后，程序有可能会出现Crash，此时会将Crash交给崩溃分析器分析。在该工具中存在两种Crash，一种是hlt指令被执行导致的Crash，称为预期Crash，另一种则是由于其他原因导致的非预期Crash。如果hlt指令被执行，则说明该位置原本就应该是一条指令。而如果遇到非预期Crash，则会采用二分查找的方式，去确定哪个hlt的替换导致了这个Crash，相应的替换位置则应该是一个数据字节。如果找不到，那么就说明这个Crash是程序本身出现了错误。通过Crash分析获得上述信息之后，概率分析器会根据这些信息再次重新计算每个地址是代码或数据的概率，反复上述过程，最终就可以正确地进行代码和数据的区分，从而正确地重写Binary。下图是一个递增重写过程的例子。

 

 

3. 实验

本文在3个数据集上进行了实验，耗费了超过5000个CPU小时。首先，作者在Google FTS数据集上将STOCHFUZZ与目前最新的工具进行了可靠性和效率的对比。在可靠性上，STOCHFUZZ是唯一一个可以将数据集中所有程序都成功Fuzz的工具，如下表所示。

 

在效率上，STOCHFUZZ表现了与基准（AFL- GCC，有源码的Fuzz工具）相近或更高的性能，与同类的Binary-only Fuzzing工具对比，在更高的可靠性的前提下，除了个别case，效率也更高，如下图所示。

 

在发现Bug的时间方面，相比于其他工具，STOCHFUZZ也有相近或更好的性能，如下表所示。

 

为了测试STOCHFUZZ准确区分代码与数据的能力，作者将Google FTS中的程序进行了一些修改，增加了一些刻意的数据内联。可以看到，随着迭代过程不断运行，FP与FN都下降得很快。

 

最后与RetroWrite进行了对比，在RetroWrite本身需要binary有多个先决条件的情况下，在RetroWrite的benchmark上仍然能达到相似的代码覆盖率。

 

 

4. 总结

本文提出了一种新的增量性、随机性的二进制重写技巧，利用了fuzzing多次运行的特性，去进行不断的试错，从而达到正确的重写效果。

本文开发了一种轻量级的近似算法，去判断每个地址是否为数据的可能性。本文将这个问题定义为了一种概率推理问题，但传统的推理算法过于重量级而且在这个场景下可扩展性不够，所以开发了一种轻量级近似算法。

本文开发了一些额外的原语来支持这个过程，例如自动定位并修复重写中的问题。

本文开发了STOCHFUZZ这个原型工具，与最新的Binary-only fuzzing工具和一些有源码fuzzing工具进行了对比实验，该工具可以在所有的case上成功运行，且效率明显领先于其他的binary-only fuzzer。

 

5. Q&A

Q：本文的工具以及实验设计还有什么缺陷？

A：没有评估工具修改binary需要的时间，只评估了修改之后的binary的效率；动态运行时无法覆盖的程序部分是否会对coverage有影响没有评估。

 

Q：本文的工具有一些优化，为什么开启优化之后对一些软件有negative impact？

A：作者的说法是有些优化会导致缓存性能出现问题（Further inspection seems to indicate that the optimizations cause some tricky complications in cache performance.）。

 

Q：什么情况会对STOCHFUZZ的coverage收集结果造成影响？

A：一种是data被错误地认为成代码，并被patch成了hlt，且对执行路径有影响，但是没有发生crash，会使收集到的coverage信息有错误；另一种是code被当成data，没被patch，会导致某些代码会被忽略掉，所以导致coverage变少。

 

Q：文章中所采用的技术为什么能比动态插桩的开支小？

A：在evaluation里面会出现某些case中它的效率比afl-gcc还快，可能是它的几个优化是针对afl-gcc的缺陷进行的优化，所以可能会比afl-gcc快。

 

Q：引入概率模型的作用？

A：如果不使用概率模型而直接全部替换，重写错误过多会导致STOCHFUZZ无法进行自修正，程序不断crash就会使得fuzz始终卡住，无法推进。

了解更多更新鲜的安全攻防信息、想要深入认识复旦白泽战队和系统与软件安全实验室、联系或者加入我们，欢迎扫描下方二维码关注公众号“复旦白泽战队”，我们在这里等你来！

复旦白泽战队

一个有情怀的安全团队

还没有关注复旦白泽战队？

公众号、知乎、微博搜索：复旦白泽战队也能找到我们哦~

文章 | SXQ

编辑 | LC

戳“阅读原文”即可查看论文原文哦~

原文始发于微信公众号（复旦白泽战队）：白泽带你读论文 | STOCHFUZZ