作者：此彼
公众号：蚂蚁安全实验室

近日，蚂蚁安全天穹实验室安全专家吴潍浠在国际安全会议Hack In The Box Singapore上分享了议题《探索先进自动化漏洞挖掘技术中的不足》。

议题通过几个具有特殊逻辑的演示代码，揭示出AFL、libFuzzer、KLEE、QSYM等几款传统自动化漏洞挖掘工具，在某些特定程序逻辑下存在的无法高效覆盖的问题。

议题同时提出“约束反向传播”的新思路，并用demo证明在某些特定程序逻辑的漏洞挖掘工作中，新方法能够大大提升Fuzz的效率和覆盖度；最后，结合传统Fuzzer的技术，提出了实现模仿人工代码审查的混合fuzz新思路。

一、动机

希望实现一个自动化漏洞挖掘工具，其ROI能够达到或超过一般人工代码审查的能力。

二、目前现实

在使用现有的fuzz工具之前我们通常需要做很多准备工作，一般准备工作有：

1. 将代码中的魔数和关键词制作成字典提供给工具。

2. 移除数据完整性验证代码，如libPNG中的checksum函数。

3. 提供涉及代码不同功能的种子文件，如使用不同压缩算法的mp4文件。

4. 编写代码，将fuzz工具提供的数据解释成API调用来测试目标代码。

编写代码，将fuzz工具提供的数据改写成目标代码可接收处理的格式。

这些工作基本都是为了弥补现有工具能力的不足而做的。

三、不足原因

假设代码((volatile uint8_t )0) = 0是我们想要找到并触发其运行的bug。

1、无法求解无法逼近的约束

AFL无法在以下代码中找到bug

AFL采用的是反馈驱动的遗传算法。其反馈信息中不包含任何条件信息，无法构造满足特定条件的数据，完全靠碰撞。当遇到32位整型条件时，碰撞概率为2的32次方分之一，几乎不可能碰撞成功。

AFL和libFuzzer无法在以下代码中找到bug

虽然libFuzzer已经在反馈中添加了对条件判断语句的反馈，但只使用汉明距离和绝对值距离计算条件语句中左值和右值的距离。这两种算法的逼近作用是有限的，很多条件是逼近不了的。

下图是libFuzzer计算距离的部分代码：

变量HammingDistance和AbsoluteDistance就是计算出的汉明距离和绝对值距离。

2、存在巨量不存在漏洞的代码路径

AFL、libFuzzer、KLEE和QSYM都无法在以下代码中找到bug

当形成漏洞的路径藏在2的大几十甚至几百次方数量级的可执行路径中，正向遍历或者随机选择都毫无意义。

四、解决方法

漏洞的形成都是有充要条件的，利用这些充要条件，去选择可形成漏洞的路径。

我们可以假设漏洞是存在的，再去证明其不存在。

变量约束反向传播

步骤：
1. 获得形成漏洞的充分必要约束

如代码：

if (flags == 0xff)

                      *((volatile uint8_t *)0) = 0;

的充要约束为：

如代码：

的充要约束为：

size > allocated_size(dst) || size > allocated_size(src)

2.沿着变量赋值的反方向，将约束传播给新变量

下图展示了约束表达式在每次传播后的变化

3.当所有的约束都只作用于输入变量且可解时，求解约束，就能得到一个能触发漏洞的输入数据

demo实现

以下demo是在LLVM的bitcode中间码上实现了简单的变量约束反向传播，下图是示意图。

下图是一段“按位与”运算反向传播的代码实现。

代码将旧的变量会从需要反向传播的变量列表中删除，将新的需要反向传播的变量加入，并构造约束。

demo效果

一定程度上解决了上面AFL、libFuzzer、KLEE、QSYM等常见Fuzzer在特定逻辑下难以覆盖到某些漏洞的问题。

最终可能的实现的是Constraint-guided Fuzz

在实际的工程领域，想要通过变量约束反向传播解决实际问题还有大量的工作要做：

1. 借助assert和address sanitizer做漏洞假设，形成充要约束。

2. 利用libFuzzer或AFL快速找到多个涉及不同代码块的具体路径。

3. 在一定距离上做反向传播。因为有大量的函数指针、外部函数等间接调用使得反向传播路径不一定能找到。

4. 在反向传播中断时，可以利用像libFuzzer中的逼近算法去满足变量的约束。

五、给研究者建议

如果你的目标仅仅是挖掘漏洞并实现利用，现有的Fuzz工具效率最高；如果对特定的逻辑下Fuzz的有效性更加感兴趣，可以用本文的思路去开发新的Fuzz工具。

只不过由于本文主要目的在于抛出一个利用反向传播技术实现的新的Fuzz思路，想要依据这个思路开发成熟的Fuzz工具还需要投入大量的时间。漏洞挖掘手段的革新往往会带来成倍的收益，但是其投入也不是一般的漏洞挖掘所能比拟的。

关于作者

吴潍浠：蚂蚁安全天穹实验室支付安全专家，国内第一个谷歌安卓漏洞赏金获得者，某国内知名PWN新基建特别奖获得者，研究领域覆盖漏洞。

扫码关注蚂蚁安全实验室微信公众号，干货不断！

本文由 Seebug Paper 发布，如需转载请注明来源。本文地址：https://paper.seebug.org/1404/