Alleysira's blog
0%

ITYFuzz

Posted on Edited on

Shou C, Tan S, Sen K. Ityfuzz: Snapshot-based fuzzer for smart contract[C]//Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis. 2023: 322-333.

Abstract

作者个人主页：https://scf.so/

代码仓库：https://github.com/fuzzland/ityfuzz

对应的slides：https://docs.google.com/presentation/d/1Z7fQMSs-fMCpoYDIVE3iQv-I18rGuk7m8tOR3IFg8mU/edit?usp=sharing

因为智能合约依赖于复杂的区块链状态，难以fuzz。对交易序列进行变异很复杂，并且通常会导致对输入和程序空间的次优探索空间。

创新点：

  • ItyFuzz是基于快照的模糊测试器，对状态和单个交易进行快照。

  • 引入了数据流路径点（waypoint）机制来辨认更有潜力的状态。

  • 利用比较航点机制来删减状态空间。

结论：通过维护状态快照，ITYFUZZ能够综合考虑具体的漏洞（重入），响应时间快，支持对链上合约及时验证

实验：对真实世界合约和被黑的Defi项目进行了实验，指令覆盖率和发现的漏洞均优于现有fuzzer。

项目开源地址：https://github.com/fuzzland/ityfuzz

Introduction

智能合约审计现在是十亿美元规模的行业，审计的目的是确保合约没有漏洞，不会导致存储在合约内的资产损失。目前的模糊测试工具仅支持在本地环境中模糊测试，而不是直接在区块链上。链上模糊测试的挑战在于对给定状态的探索要足够快，因为链上状态在不断变化；攻击者可能在任何时候发起攻击。现有fuzzer效率不够高，不能即时获得链上状态并迅速完成审计。

链上审计的必要性可以通过以下场景来说明：

  • 特定代码只能在特定的链上状态下才能到达（确实），本地执行永远无法到达
  • 目前的合约依赖外部的合约作为信息来源，链上审计可以即时获得信息（如预言机）

链上审计的挑战在于必须要在攻击者执行攻击前暂停合约

  • 链上审计需要的时间需要是秒级，现有的工具对时间优化不足，覆盖合约的全部指令需要若干小时
    • ITYFuzz能在几秒内达到较高的覆盖率
  • fuzz合约的挑战在于：合约依赖状态，合约的依赖复杂
    • 为了解决状态的问题，一些之前的工作每次fuzz均从全新状态开始，以一系列交易作为输入；变异阶段部分交易序列被变异，因此现有工具在重新执行交易以返回到先前状态时存在较高的开销。对于需要通过多个交易建立的深层状态进行探索，重新执行的成本呈线性增长。此外，现有工具只针对交易具有反馈机制，而不针对状态，然而状态和交易具有不同的探索难度。
    • 作者认为，对于具有状态的模糊测试，状态的有趣性与事务的有趣性同样重要，而当前的状态模糊测试工具中不存在选择有趣状态进行探索的反馈机制。（即不再从fresh state开始）

快照（Snapshot）本质上是某些交易触发的中间状态的复制，通过将所有有趣的快照存储在状态语料库（corpus）中，能够以O(1)的复杂度“时间穿越”到先前的状态，支持对交易和状态空间的高效探索

重构了一个现有的EVM实现来支持快速的快照

由于运行时内存资源有限，将所有快照存储到语料库中仍然不现实，而快照的数量随着总执行时间的增加而线性增加。存储的快照大小可能在几秒钟内增长到几个千兆字节。为了解决这个问题并优先探索最有趣的状态，作者设计了两种反馈机制（即路径点）来对有趣的状态进行分类，并设计了一种语料库修剪技术，在必要时减少有趣状态的数量。

同样可以适用到其他领域，如现代硬件设计

贡献

  • 提出一种基于快照的模糊测试算法，以减少有状态智能合约模糊测试的重新执行开销
  • 提出了新的路径点机制，支持高效程序探索
    • 数据流路径点：基于未来加载的内存
    • 对比路径点：概率性采样和固定采样结合
  • 开发了模糊测试工具，展示了其有效性
  • 提出了一种新的智能合约审计方法，该方法基于从区块链上获取的状态进行测试，检测和复现了价值数百万美元的在线项目的漏洞。

Background

fuzzing

为了提高探索效率，模糊测试器一般会采用启发式方法或反馈机制来变异已有的输入生成新的输入

算法例子：初始时的语料库为空，如果某次执行覆盖了新的点则该执行

这里的伪代码多少有点问题：

  • if后面一行应该是 $I\gets I\ \cup \ i_m$
  • corpus可能会变为空

image-20240222163752301

合约的fuzzer必须输入为一系列的交易

waypoint

FuzzFactory[OOPSLA19]引入了一般化的反馈机制waypoint。路径点是在执行目标程序后提供有趣反馈的中间输入。例如，在覆盖引导的模糊测试算法中，如果运行目标程序产生新的覆盖，就会记录新的输入（路径点）。然而，路径点不仅限于覆盖点，其他常见的路径点还包括执行时间、内存使用和两个比较值之间的距离等。为了实现定制的路径点，需要在程序执行过程中收集其他目标动态信息，并提供一个新的谓词函数 is_interesting替换图1中的 第9行

Motivating Example

image-20240223110801874

对于上面的合约，调用inc 0, inc 1, buggy() 即可出发漏洞

现实世界中的交易序列可能会相当复杂和长，当T增大时，现有的漏洞检测工具 如SMARTIAN不能即时检测出漏洞

直观来想，如果随机调用函数，抵达某个指定深度的时间是指数级的，重复执行来到达某个指定状态的（比如目标是10，到达8）的操作架重执行。SMARTIAN中，重新执行占据了总模糊测试时间的90%以上。

如果在执行一系列交易后到达的状态可以被记忆，那么重新执行的时间可以被消除。然而，记忆化需要保存的状态数量与交易序列的指数成正比。ItyFuzz的关键在于是只能记忆化一组“有趣的状态”，称为快照，而不是记忆化所有中间状态，并且仅使用这些有趣的状态来探索新状态而无需重新执行。一个状态的“有趣程度”是通过两个新颖的航点概念来定义的。

image-20240223112037082

Methodology

Architecture

image-20240225101344843

可以把EVM理解为$S\times T \to S$，状态在输入交易下发生变化

和现有工具一样，ITYFuzz的输入是种子输入语料库，每次从库中选一个种子（交易和状态）作为输入交给EVM执行，执行后使用 执行路径点 来判断当前执行是否增加了覆盖率，如果增加了把(s,t)就加入到语料库中。(会记录当前的执行状态$s$，这就是快照的含义)

snapshot-based fuzzing

为了返回到某个中间状态，现有方法是重新执行交易。本文直接记录状态并保存

由于快照仅记录执行交易前的状态s和交易，丢失了执行交易后的状态$s’$，本文设计了另外一个语料库infant state corpus”，来记录执行后的状态，以判断当前状态是否能导致未来的有趣的执行。

image-20240225111932947

变异有两种可能，变异后的st永远是sound的（交易可以随便造，状态是从历史状态中得到的，意味着可能从一个交易序列到达记录的状态）

  • 变异交易：变异器来执行
  • 变异状态，从$C_s$ 中选一个

执行完交易后进行两个路径点判断

Dataflow Waypoint

目前有了对输入有趣程度进行度量的waypoint机制（FuzzFactory），没有对状态的路程点定义。设置航点的目标是判断从这些状态出发的的未来执行是否有趣，因此设计需要获得关于状态有趣程度的语义信息。

主要从两个方面来思考

  • 如果内存是未来的load指令的目标，可能是有趣的

  • 如果状态变化包括了对某些特殊内存位置的写

作者利用字节码插桩来进行动态数据流分析，通过观察运行时的load和store指令。由于传统的数据流分析是通过对源代码进行静态分析来实现的。然而，静态分析工具在智能合约模糊测试中效果不佳，因为智能合约可能会动态地调用外部合约。然而，仅从目标合约获取的静态数据流信息是不够的。

由于决定内存位置的“有趣程度”的load指令发生在未来，因此目前无法确定store指令的“有趣程度”。为了解决这个问题，本文提出了利用过去的load来估计未来可能的有趣的地址。

ItyFuzz跟踪过去加载过的内存位置以及被加载的值的抽象。如果当前执行中的值存储操作写入了这样一个内存位置，并且被写入的值的抽象与该位置之前存储的所有抽象值都不同，那么我们称这个存储操作是有趣的，并且在存储之后产生的状态也是有趣的。

插桩算法维护了两个map，分别记录是否执行过load和是否执行过store以及store的值

image-20240225164440432

Loc % MAP_SIZE是对Loc的粗略抽象，为了创建一个较小的抽象地址空间。较小的抽象地址空间有助于降低存储和查找开销。

桶抽象是类似于AFL中使用的分桶机制。分桶有助于减少插入映射的总值量，从而减少存储和评估成本，以换取插入数据的粒度损失。每个桶是实际值域的一个分区，在EVM的上下文中，实际值是一个256位整数。使用桶来避免存储所有状态。执行Store(Loc, Value)时，首先抽象出值该在的桶，再检查S(loc%size)(bucket(v))是否为true。

执行后，如果存储map中的一个桶从false变为true，并且L(Loc % MAP_SIZE)的相应位置也为true（算法2的第2行），则认为新状态是有趣的。每个桶的大小和范围可以作为超参数进行调整。每个槽中的桶数量越多，评估为有趣的状态就越多，$C_s$的大小也会增加。随着$C_s$的增大，选择下一个要探索的状态变得更加困难，并且会引起存储开销。

image-20240225164449714

Comparison Waypoint

只采用dataflow航点存在的问题，由于过于抽象，如果桶2-4已经有了2,3的状态就不再被认为是有趣的了。如果只使用数据流航点，如果域的划分（即桶）对于目标智能合约来说不够精细，那么可能无法包含某些状态。

细粒度划分的问题在于初始状态语料库中的状态数量庞大，这会导致对于大型智能合约而言，随着时间的推移内存使用开销巨大。为了有效地解决这个开销问题，本文提出使用比较航点。比较航点只考虑所有中间状态，其中一些比较指令的操作数相比之前的执行更接近彼此，这对于达到更高的覆盖率是必需的，被认为是有趣的。

image-20240225174337363

ItyFuzz使用最大可能值初始化一个局部映射$C_{local}$，该映射仅针对当前执行。在执行过程中，对于每个比较指令，ItyFuzz根据程序计数器%MAP_SIZE（即比较指令的位置）更新键值对应的距离（第4行less than和第6行）。距离反映了两个值在比较中实现平衡的接近程度，由它们之间差值的绝对值确定。例如，如果ItyFuzz处理EQ(1, 3)操作，距离将为2。当执行中的任何比较指令更有可能为真时，执行被认为是有趣的。换句话说，在算法4中描述的方式，如果当前执行在local映射中显示的距离比记录在先前执行中最小距离的映射（）中的距离更小，则认为该执行是有趣的。

比较点能够用于判断是否该将状态从$C_s$中移除，算法4是具体的投票算法，票数反应了状态的有趣程度。

image-20240225192248662

Implementation

基于LibAFL，revm作为EVM的执行引擎；支持从支持Geth的链的某个状态开始fuzz

开源地址：https://github.com/fuzzland/ityfuzz

Evaluation

考虑

  • 覆盖率：在3个数据集上，对比1个工具
  • 能否发现现实世界中的漏洞
    • 36/42个项目中已知的漏洞
    • 45000个合约项目（BSC和以太坊，均有>100个交易），1384项目发现了漏洞
  • 存储快照带来的内存开销，以及能否被waypoint解决
  • 链上审计对发现合约漏洞的帮助
    • 研究了两个被黑的defi项目，给出的实例证明了，仅仅在开发环境中测试室不够的，还需要链上审计
    • image-20240305205240351
  • 效率是否支持链上审计

数据集

  • 论文里的数据集 57个合约
    • Sunbeom So, Myungho Lee, Jisu Park, Heejo Lee, and Hakjoo Oh. 2020. VERISMART: A Highly Precise Safety Verier for Ethereum Smart Contracts. In 2020 IEEE Symposium on Security and Privacy, SP 2020, San Francisco, CA, USA, May 18-21, 2020. IEEE, 1678–1694. https://doi.org/10.1109/SP40000.2020.00032
  • 以太坊收集的572个合约

对比工作

  • SMARTIAN：比较了覆盖率

时间优势来源于快照缩减了re-execution时间；comparison waypoints能够快速提高覆盖率

image-20240305203726288

image-20240305203735599

对比实验不够，做消融实验ablation study

image-20240305204523492

为了研究对内存开销的依赖

image-20240305204653257

Related work

反馈驱动的模糊测试

  • 基于覆盖率的模糊测试：AFL HonggFuzz FairFuzz
  • 自定义的waypoint：
    • Validity fuzzing利用输入的有效性作为反馈
    • 采用程序执行的深度；
    • FuzzFatory形式化了waypoint机制

带状态的模糊测试

  • SMARTIAN 从0状态开始，发送一系列交易到达目的状态
  • Nyx采用了操作系统层面的快照策略 Nyx-Net
  • CorbFuzz对web应用程序进行fuzz，对状态进行了建模

智能合约安全工具

  • ContractFuzzer

  • Echidna Harvey 工业界的fuzzer

  • SMARTIAN hybrid，混合了静态分析和动态 数据流分析

Q

  • 什么是链上审计？如果链上进行模糊测试，支持的每秒测试次数是多少
  • 快照带来的额外存储代价评估，有
  • 从语料库中选择种子的算法
  • 每个桶的大小和范围如何设置和调节
    • 参考了AFL的设计，AFL的桶是1-2,2-4,4-8
  • 本文的覆盖率和其他工作的覆盖率对比