当前位置：网站首页>[论文分享] PATA: Fuzzing with Path Aware Taint Analysis

[论文分享] PATA: Fuzzing with Path Aware Taint Analysis

2022-06-10 22:12:00 【fa1c4】

PATA: Fuzzing with Path Aware Taint Analysis [S&P 2022]

清华和南大合作的一篇fuzzing结合污点分析的论文, 发在今年的S&P 2022上
论文链接 https://www.computer.org/csdl/proceedings-article/sp/2022/131600a154/1wKCe9rJFfi
github地址 https://github.com/PATA-FUZZ/PATA

概述

污点分析通过推断影响输入字节来辅助fuzzer解决复杂的fuzzing约束问题. 在真实的程序中, 执行路径经常会到达循环, 这些循环中的约束可以被多次访问和记录. 传统的污点分析技术在区分同一约束的多次出现时遇到困难. 因此这篇论文提出PATA, 一种实现路径感知污点分析的fuzzer, 即基于执行路径信息区分同一变量的多次出现.
首先, PATA识别约束中使用的变量, 并构造代表变量序列 (RVS), 包含所有代表性约束变量和值. 接着, PATA对输入进行扰动, 将其RVS与原始输入的RVS进行匹配查找值的变化, 以确定RVS中每个条目对输入字节的影响. 最后, PATA改变相应的输入字节来解决给定路径中的约束问题.

一句话: 通过路径感知的污点分析推断输入字节的影响辅助fuzzer解决复杂约束问题.

导论

基于突变的灰盒模糊测试是最流行的漏洞挖掘技术之一, 突变的输入采用随机方法生成. 这种盲生成方案严重限制了fuzzer的整体性能. 目前污点分析技术作为fuzzing技术的辅助技术受到广泛的关注, 具体来说污点分析通过识别给定约束的影响输入字节(the influencing input bytes)来提高模糊器的突变质量. 让fuzzer更关注关键字节而不是全部字节都遍历一遍.
有两种主流的污点分析技术

propagation: 用不同的标签污染输入的每个字节, 然后在程序执行期间使用传播规则传播这些标签
inference: 重复扰乱输入字节, 在程序运行过程收集变量的值, 如果一个变量值改变, 可以推断该变量和改变的的输入字节之间有数据依赖关系.

面临的难题: over-tainting和under-tainting将导致分析正确性的下降和fuzzing性能的损失.
最突出的原因之一是路径感知: 循环和多个函数调用站点可能会导致一个给定的约束被访问多次, 并在单个执行路径中受到不同输入字节的影响.
两种污点分析技术在无路径感知的场景下都有出错的可能性. (1) 基于传播的污染分析在没有路径感知的情况下存在过度污染问题. 它不能区分不同的出现, 也不能确定何时清除冗余标签. (2) 基于推论的污染分析在没有路径感知的情况下会受到污染不足的影响. 这种方法使用的字节级突变可能会改变执行路径，导致访问一个约束的时间不同，或者完全跳过它; 即使路径在突变过程中保持不变, 无路径感知的推理技术也只能捕获每个约束的值一次.

方法

挑战

论文基于这个缺陷和难题首次提出路径感知的基于推断的污点分析技术.
(1) 沿着执行路径把表示程序状态的约束变量收集到一个代表变量序列(Representative Variable Sequence)
这里的挑战是在污染分析中合理地追踪代表性变量. 由于分析是基于变量出现的情况, 因此保真度最高的方法是记录所有变量在执行期间的状态. 但是, 记录它们的费用太高, 因此必须改用特定策略的抽样, 即跟踪代表性变量.
(2) 为每个变量的出现标识相应的关键字节.
在推理过程中, 模糊器对输入的每个字节进行扰动, 并监视变量出现的值变化, 以识别关键字节. 问题在于原路径可能会偏离原路径.
这里的挑战是, 当执行路径更改时, 如何正确匹配变量的出现. 答案是需要一种匹配算法来正确匹配变化路径之间的变量.
(3) 利用路径感知污点分析的结果来指导fuzzer的突变过程.
挑战是有效地利用分析结果来探索原始路径的其他分支. 路径感知污点推断的结果由关键字节和每个变量出现的值组成. 所以需要设计一种突变策略来充分利用这些结果.

PATA

在这里插入图片描述
PATA的设计主要包括三个部分:

(A) 约束变量收集

约束变量由可以直接或间接影响约束的变量组成. 为了实现路径感知, 理想情况是记录所有遇到的约束变量及其值. 不过这是不现实的做法, 为了减少观察值变化的范围, PATA为所有约束搜索直接影响的变量.

(1) 识别代表变量(Representative Variables)
算法1 首先扫描所有的约束, 并将其转化为直接影响约束的约束变量. 这些变量被无重复地添加到V中. 接下来, 检查每个记录的约束变量:如果它是一个逻辑操作, 用它的所有操作数源替换它. 如果约束使用了字节数组的比较结果, 则替换为字节数组比较变量来记录参数. 重复直至V没有变化.
在这里插入图片描述

(2) 特征提取
在识别约束变量的同时, 提取出约束变量的详细特征. 变量特征包括

操作数特征 (操作数的数据类型和长度
模式特征 (约束类别, 如cmp, switch, call
块特征 (块特征记录了约束变量所属基本块的信息

(B) 关键字节识别

在执行路径在输入扰动期间发生变化时, 正确匹配变量的出现.
PATA通过byte-level突变和出现(occurrence)匹配来定位关键字节, 在字节级突变中, PATA收集由跨运行的变量出现组成的RVS. PATA将扰动输入的RVS与原始输入的RVS进行匹配, 从而为每个变量的出现识别相应的关键字节.
对于输入中的每个偏移量, 使用各种方法来修改它们, 包括位翻转、加1或减1. 其目的是对字节进行少量修改, 以尽可能地维护执行路径, 但要更改字节因变量(byte dependent variable)的值. 有些变量时不稳定的, 对于相同输入可能会有不同的值, 算法会跳过这些变量避免over-tainting. 通过监视值的变化, 可以识别相关的关键字节.

在这里插入图片描述

Variable Occurrence Subsequence. 一个映射型数据结构, 其中键是变量标识符, 值是路径中的出现序列. 该算法考虑公共前缀中匹配的出现次数, 并比较它们的值. 如果值在匹配的变量之间发生变化, 则推断变化的字节对发生至关重要.

(C) 路径导向的突变

对于RVS(Representative Variable Sequence)上每出现一个约束变量, 首先检查求解是否有意义. 例如, 如果这个变量的所有后续基本块都被覆盖了, 或者约束变量的值不稳定, 认为它是没有意义的.
接下来, 检查发生的关键字节是否已经成功定位. 使用给定约束变量的关键字节、值和特征, 依次使用以下方法改变输入: 直接复制、线性搜索和随机探索. 突变的种子将被传递给一个传统的fuzzer, 跟踪二进制执行检查它们是否触发了新的覆盖或表现出异常行为, 如果有, 则保存以作进一步的突变或异常分析.

在这里插入图片描述

直接复制 (direct copy): 输入字节直接用于约束变量. magic number 和 magic bytes 是fuzzing的常见阻碍, 探索直接复制是满足它们的决定性因素.

线性搜索 (linear search): 将每个关键字节视为一个独立变量, 并依次线性增加或减少字节的值.

实验

作者在两个广泛使用的基准上评估PATA: 谷歌的fuzzer-test-suit, 它包含一系列真实世界的程序; 以及LAVA-M, 它包含四个插入了bug的真实世界的程序. 在谷歌的fuzzer测试套件中, PATA的性能比7种最先进的fuzzer(如Angora和GREYONE)高出29%-1830%, 以及找到的唯一路径和覆盖的基本块的数量高出7%-87%.
进一步的评估, 将PATA应用于各种开源项目. PATA发现40个新的未知bug, 其中12个被确认为CVE.

横向对比
AFL [36], MOPT [24], TortoiseFuzz [33], VUzzer [26], Angora [11], REDQUEEN [6], and GREYONE [17]

初始种子
对于谷歌的模糊测试套件和LAVA-M, 所有fuzzer都使用从数据集中收集的相同种子. 当没有可用的种子时, 将使用空的种子作为后备选项. 对于真实的项目, 作者随机选择了一个从互联网上获得的有效输入.

评估指标
使用三个指标评估模糊器, 即执行的路径数量、覆盖的基本块和触发的bug. 由于不同的模糊器可能有不同的模糊状态表示, 为了进行公平的比较, 作者收集并运行了评估过程中产生的种子, 以收集路径数量(由AFL的算法识别)和基本块(由LLVM工具标识)来统一表示. 另外从崩溃中识别出真实bug的数量作为指标.

Google’s fuzzer-test-suite

path and basic blocks coverage
TABLE I 和 TABLE II 显示了每个fuzzer覆盖的路径和块的数量.
PATA相比AFL, MOPT, TortoriseFuzz, VUzzer, Angora, REDQUEEN 和 GREYONE
发现路径数增加111%，63%，125%， 1830%， 343%， 43%， 29%;
基本快覆盖率增加19%， 12%， 21%， 87%， 41%， 7%，和19%.

在这里插入图片描述

Bug Triggering
VUzzer没有发现任何bug, 安哥拉只在2个项目中发现了2个bug, 而AFL、MOPT、TortoiseFuzz、REDQUEEN和GREYONE分别触发了16、21、18、18和9个bug. PATA发现11个项目中的31个bug. 谷歌的fuzzer-test套件列出了一些可以在其项目中找到的bug. 值得注意的是, PATA不仅发现了fuzzer-test-suite中列出的bug, 而且还在project json、libxml2、llvm-libcxxabi和pcre2中分别发现了1、1、5和10个未列出的bug.
在这里插入图片描述

LAVA-M

TABLE IV 显示了每个fuzzer在5次运行中检测到的错误数的范围. 结果表明, 与其他模糊器相比, PATA能更有效地发现LAVA-M中的bug. PATA分别比AFL、MOPT、TortoriseFuzz、VUzzer、Angora、REDQUEEN和GREYONE
多发现2593、2564、2593、2474、361、2和1个bug.

在这里插入图片描述

Fuzzing Real-world Programs

在github开源项目中, PATA总共发现了40个未知bug, 其中12个bug获得CVE编号.
在这里插入图片描述

Figure 4 展示了在5次24小时实验中执行的路径数量和覆盖的基本块的增长趋势.
PATA的表现比其他fuzzer更好, 并在大多数时间在两个指标上保持领先,
另外PATA的阴影区域很小, 代表PATA的性能比其他模糊器更稳定.

在这里插入图片描述

总结

Related work

[6] Cornelius Aschermann, Sergej Schumilo, Tim Blazytko, Robert Gawlik, and Thorsten Holz. Redqueen: Fuzzing
with input-to-state correspondence. In NDSS, volume 19, pages 1–15, 2019.
[11] Peng Chen and Hao Chen. Angora: Efficient fuzzing by principled search. In 2018 IEEE Symposium on Security and Privacy (SP), pages 711–725. IEEE, 2018.
[17] Shuitao Gan, Chao Zhang, Peng Chen, Bodong Zhao, Xiaojun Qin, Dong Wu, and Zuoning Chen. Greyone: Data flow sensitive fuzzing. In 29th USENIX Security Symposium (USENIX Security 20). USENIX Association, Boston, MA. https://www. usenix. org/conference/usenixsecurity20/presentation/gan, 2020.
[24] Chenyang Lyu, Shouling Ji, Chao Zhang, Yuwei Li, WeiHan Lee, Yu Song, and Raheem Beyah. Mopt: Optimized mutation scheduling for fuzzers. In 28th USENIX Security Symposium (USENIX Security 19), pages 1949–1966, 2019.
[26] Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida, and Herbert Bos. Vuzzer: Application-aware evolutionary fuzzing. In Proceedings of the Network and Distributed System Security Symposium (NDSS), 2017.
[36] Michal Zalewski. American fuzzy lop, 2015.