基本信息
**原文名称：**ItyFuzz: Snapshot-Based Fuzzer for Smart Contract
**原文作者：**Chaofan Shou; Shangyin Tan; Koushik Sen
**原文链接：**https://dl.acm.org/doi/pdf/10.1145/3597926.3598059
**发表期刊：**Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis. 2023（ISSTA 2023）
**开源代码：**https://github.com/fuzzland/ityfuzz
一、引言
随着 Web 3.0 技术的日益普及和攻击数量的增加，对智能合约进行安全审计也成为关键产业。智能合约可以通过自动化的模糊测试工具进行审计，但所有用于智能合约的模糊测试工具仅支持在本地部署进行测试，而不支持在区块链上进行测试。
然而在特定情况下，区块链上的审计或直接使用从区块链不断获取的状态进行模糊测试至关重要，原因在于：
1
当特定代码位置只能从特定的区块链状态访问时，本地或开发环境下的模糊测试是无效的；
2
现代智能合约通常利用外部合约作为信息来源。通过区块链上的审计，可以实时动态地从区块链中提取这些数据。但由于区块链状态高速变化的特性，使得其随时可能产生攻击事件，因此在区块链上进行模糊测试需要在特定状态进行高速测试，要求测试工具能够提供秒级实时响应。
因此，本文提出了一种基于快照的模糊测试技术，开发了ItyFuzz工具，**可以在秒级的响应时间内实现对智能合约代码和状态的高覆盖率，以此支持在区块链上对智能合约进行审计。**ItyFuzz提出了以下方法：
(1) 使用快照存储感兴趣的合约状态，以实现高效的合约状态探索；
(2) 创建了针对优先探索有趣快照状态的新路径机制，实现了高效的程序探索：
**a. 数据流路径（Dataflow waypoint）**根据“未来”内存加载来评估状态的有趣程度。
**b. 比较路径（Comparison waypoint）**通过概率抽样和比较反馈来压缩状态库。
**二、**研究动机
举例说明，解释当前基于交易序列生成的模糊测试工具为什么在利用特定的漏洞上存在表现不好的问题。
以下图1中给出的智能合约代码为例，其中只有一个状态变量counter（计数器），函数incr在参数小于当前counter时增加1，函数decr在参数大于当前counter时减少1，当counter达到某个常数T时，buggy函数引入一个漏洞。
图 1 简单的智能合约示例
针对该智能合约的测试输入是一系列的交易序列，其中每个交易都包括要执行的函数及其相应的参数。随着T值的增大，需要构造用来触发漏洞的交易序列也会变得更加复杂。
在现实世界的情况下，触发漏洞的交易序列可能非常长且复杂。例如，黑客们利用了六笔交易，每笔交易平均包含40次函数调用，以建立使Team Finance去中心化金融（DeFi）平台受攻击的状态[1]。
在探索这个简单智能合约的交易序列空间时，先前的智能合约模糊测试工具，如SMARTIAN[2]，随着T的增加，检测到漏洞的时间也不断增长（如图2）。
图 2 不同T值情况下找到可以触发图1漏洞的交易序列的时间开销
这是因为在测试时，模糊测试工具需要从头重新执行整个交易序列（re-executing），包括部署要测试的交易。在任意状态中执行交易所需的时间必须包括重新执行达到该状态所需的交易序列的时间。
为了从实证角度研究重新执行（re-execute）如何减慢整体性能，作者在图1所示合约上以默认模式运行了 SMARTIAN，并将 T 设置为 10。
图 3 记录了重新执行（re-execute）的时间以及它们占总测试时间的百分比。重新执行时间是在 EVM 执行程序执行已执行过的（state,transaction）（状态，交易）对的时间。在 SMARTIAN 中，重新执行占总模糊时间的百分之九十以上。
图 3 SMARTIAN运行图1合约时重新执行时间（y轴）
和所占总测试时间百分比
**重新执行时间会随着交易序列长度的线性增长而呈指数级增长。**然而，通过存储执行交易序列之后的智能合约状态，可以降低重新执行的时间。但需要保存的状态数量与交易序列的数量的指数成正比，因此，ItyFuzz仅对有趣的状态（interesting states）进行保存，称为“快照”技术。
三、概述
ItyFuzz的基本框架如下图所示，主要由三个部分组成：
（1）基于快照的模糊测试（Snaphot-Based Fuzzing）
（2）数据流路径（Dataflow Waypoint）
（3）比较路径（Comparison Waypoint）
图 4 ItyFuzz流程概述
Solidity智能合约程序在以太坊虚拟机（EVM）上执行。EVM可以被视为一个函数EVM：（S×T）→S，将状态s∈S和交易t∈T映射到一个新状态s'∈S，用st来表示。
与传统覆盖引导的模糊测试器一样，ItyFuzz从种子池中选择输入开始（如图4左上角所示），在每次迭代中，从种子池中选择一个交易和状态对，并对其进行变异，生成一对，比如（s0，t0）。变异后的输入由EVM执行器执行。
执行后，ItyFuzz使用执行路径（execution waypoints）对执行期间收集的信息进行判断本次执行是否interesting。如果是，表示本次执行增加了某个waypoint的覆盖范围，ItyFuzz会将变异的输入对（s0，t0）添加到种子池中。
与传统的覆盖引导模糊器不同，EVM执行器同时会返回更新后的状态，同时使用快照保存更新的状态中有趣的状态（interesting states）。
**四、**基于快照的模糊测试（Snaphot-Based Fuzzing）
在智能合约执行中，状态s可以通过执行交易序列从初始状态构建。ItyFuzz通过快照保存状态直接回溯到某个中间状态，以节省重新执行交易使用的时间。
1. 种子池C（s, t）
作者通过维护一个种子池C，保存状态交易对（s, t）。初始测试从种子池中选择状态交易对进行测试，在执行（s, t）过程中如果被waypoints反馈为有趣的执行（interesting execution），则将该（s, t）保存到种子池中进行进一步变异测试。作者提出在执行t过程中产生了新的waypoints反馈，可认为是这个t可以进行进一步的变异以进行测试，因此在此处保存的是执行t之前的状态s与t的状态交易对。
2. 种子池Cs**（s）**
由于种子池C只维护了执行t之前的状态，而对于新产生的状态s’进行了丢弃，因此作者提出再次单独维护一个种子池Cs（称为infant state corpus）维护新的状态。而保存新的状态的规则依据后续提及的waypoints进行判断。
3.ItyFuzz模糊测试算法
图5展示了ItyFuzz基于快照的模糊测试算法，在fuzz循环的每次迭代中，首先从种子池C中选择一个交易状态对（s, t），接着选择对交易t进行结构性变异t_mut_或者从CS中选择一个新的状态s_mut_与t组合。变异后由EVM执行，生成一个新的状态s’，如果执行过程触发了新的waypoints，则将（s_mut_, t_mut_）保存到种子池C中，将新的状态s’保存到CS中。
图 5 ItyFuzz的模糊测试算法
五、数据流路径（Dataflow Waypoint）
作者提出数据流路径（dataflow waypoint）反馈信息，如果内存位置在将来作为加载指令（load instruction）的参数出现，那么这个内存位置是interesting的。
如果状态更改包含对interesting内存位置的唯一写入，就可以认为这个状态对于未来的测试是有帮助的。作者利用字节码插桩通过实时观察加载（load）和存储（store）指令来进行动态数据流分析。
图6和图7中的算法1和2描述了数据流路径算法。在执行交易的过程中，作者通过维护两个映射分别记load和store指令的内存位置的存储的值的抽象，通过检查执行交易的过程中是否向interesting的内存位置写入新的值来确定是否是本次执行是否需要被保留。
L映射load指令的内存位置，而S映射Store指令的内存位置和存储的值，对于值的存储使用了类似AFL的bucket机制。
图 6 数据流路径插桩的算法
图 7 数据流路径评估算法
**六、**比较路径（Comparison Waypoint）
作者提出比较路径进一步提高检测的效果，比较路径只考虑在某些比较指令的操作数之间逐渐接近彼此的中间状态，保留符合要求的状态。在这一环节中可能会出现两个问题：
(1) 需要保存的状态过多，符合要求的状态相似度过高；
(2) 状态库的增长过快，无法存储在主机中；
针对问题1，ItyFuzz首先使用vote算法对保存的状态进行排序。同时使用概率抽样和随机抽样，vote评分更高的状态有更高的概率被选择进一步进行测试。
针对问题2，ItyFuzz在状态库的大小达到提前设定的阈值时会对状态库进行修剪：根据其vote分数和访问次数（选择和执行该状态的次数）进行排序。算法如图8、9所示。
图 8 比较路径插桩的算法
图 9 比较路径评估算法
七、实验评估
作者通过以下五个研究问题进行实验，对ItyFuzz的效果进行评估：
RQ 1: ItyFuzz是否在指令覆盖率方面表现优于其他工具？
RQ 2: ItyFuzz是否能够识别并生成现实世界的漏洞利用？
**RQ 3:**使用存储状态而不是交易序列是否会导致高内存开销，使用waypoints机制能否解决这个问题？
**RQ 4:**在链上审计是否有助于发现在开发周期中被忽略的漏洞？
RQ 5: ItyFuzz的响应时间是否支持链上审计？
1. 实验准备
【数据集】
**B1：**从VERISMART[3]中提取，包含57个支持ERC20标准接口（即代币）的智能合约。
**B2：**72个从以太坊链上获取的智能合约。
**B3：**500个从以太坊链上获取的智能合约。
【实验环境】
AMD Epyc CPU（128核心）
256 GB内存
【消融实验】
**ItyFuzz-Rand：**以50%的概率对状态进行快照并存储到CS种子池中。
**ItyFuzz-DF：**基于仅数据流路径的方式对状态进行快照并存储到CS种子池中。
2.RQ 1: ItyFuzz是否在指令覆盖率方面表现优于其他工具
作者使用数据集B1、B2和B3将ItyFuzz与SOTA：SMARTIAN [2]进行比较。
对于每个数据集，仅使用指令覆盖率进行比较，因为控制流不能代表智能合约程序的状态性。通过计算所有已部署合约字节码中指令的数量来计算总的可能覆盖率。
由于ItyFuzz和SMARTIAN都不支持对哈希函数进行变异和生成不符合结构要求的虚假输入数据，作者不计算验证输入结构和哈希函数的基本块中的指令，同时删除了在程序的最后一个Return指令之后出现的无法访问的代码（即元数据）。
图10、图11、图12分别显示了B1、B2和B3数据集上每个工具的随时间的总指令覆盖率。尽管SMARTIAN使用了符号执行，但在指令覆盖率与时间的比较方面，ItyFuzz表现明显优于SMARTIAN。
对于B1中的智能合约，在10秒后，ItyFuzz几乎覆盖了所有指令，而SMARTIAN在一分钟内无法做到。这是因为比较路径优先探索那些可能改进未来覆盖率的状态。
图 10 B1数据集上不同工具的指令覆盖率
图 11 B2数据集上不同工具的指令覆盖率
图 12 B3数据集上不同工具的指令覆盖率
3. RQ2: ItyFuzz是否能够识别并生成现实世界的漏洞利用
作者在真实世界的智能合约项目上进行了测试：收集了42个先前被攻击的项目，并对每个项目进行了最多一小时的模糊测试。
ItyFuzz能够为其中的36个项目识别具体的漏洞利用，平均时间为13.8秒。
SMARTIAN在24小时内未能达到Bacon Protocol和EGD Finance的漏洞暴露状态（由自定义预测模型确定）。此外，对一些公司的42个项目进行了审计，没有误报，ItyFuzz识别出了可以在分叉链上执行的实际漏洞利用。
此外，还将ItyFuzz应用于在Binance Smart Chain和以太坊上接收了超过100笔交易的45000个智能合约项目（包括超过150,000个智能合约）。
通过对每个项目进行5分钟的模糊测试，ItyFuzz能够为21个项目中的资产窃取生成具体的漏洞利用，这些项目包括流动性池、ERC20代币和GameFi，总价值超过50万美元（使用Uniswap数据进行估算）。
ItyFuzz还能够在1384个项目中找到常见的漏洞，如任意外部调用和任意ERC20代币销毁，这些项目中的资产总价值超过800万美元。
作者对每个项目进行了消融研究，并报告了发现漏洞所需的时间。结果如表1所示。
表 1 对于漏洞检测时间的消融实验（OOM: Out of Memory）
对于大多数漏洞，ItyFuzz优于所有的消融版本。特别是当智能合约较为复杂且状态空间较深时，ItyFuzz可以在短时间内找到漏洞，而ItyFuzz-Rand和ItyFuzz-DF在一小时后超时。
4. RQ3: 使用存储状态而不是交易序列是否会导致高内存开销，使用waypoints机制能否解决这个问题
作者进行了ItyFuzz的消融研究，统计了在执行ItyFuzz及其消融版本时，随着时间推移，CS种子池中的总项目数量，使用了B1数据集进行实验。结果如图13所示。
图 13 Cs种子池存储开销，y轴为存储在Cs中的unique状态的数量
ItyFuzz-Rand在大多数智能合同中在大约三秒后崩溃，因为出现了内存溢出（OOM）。
ItyFuzz-DF的种子池中的状态在前20秒内逐渐增加，然后趋于稳定，因为测试刚开始，数据流路径会收集根据加载映射将存储到有趣位置的状态，并将存储映射bucket中的相应条目设置为true。
之后，状态不太可能被添加到语料库中，除非加载映射发生变化。ItyFuzz对CS种子池进行了修剪，因此其大小最终趋于稳定。
5. RQ4&5: 链上审计
作者对两个先前被黑客攻击的 DeFi 项目进行了评估：Nomad Bridge 和 Team Finance。
结果显示在表2中。Nomad Bridge 是一个允许资金转移的跨链桥梁，在2022年8月1日，该合约部署后的第41天，攻击者窃取了价值1.9 亿美元的资产，该合约的漏洞是由于部署上链时一个错误的初始化导致的。
表 2 漏洞检测时间
作者从区块15259103（在合约部署上联后）分叉实际链，并基于该状态进行模糊测试，ItyFuzz可以在0.3秒内识别漏洞，但在本地测试环境中无法识别漏洞（因为在测试环境中的初始化没有错误）。
这个例子说明在开发环境中的测试是不够，实际运行环境可能与测试和预发布环境不同，尤其是对于管理大量实际资产的代码。
此外，由于黑客采用的技术也在不断发展，这种漏洞很可能会在几分钟内被发现和利用。
由于ItyFuzz将漏洞发现时间降低到了足够低的值（0.3秒），合约部署者可以在部署后利用ItyFuzz进行持续监控，并在黑客之前获取具体的利用信息。
八、总结
本文设计了一个新的基于快照的智能合约模糊测试工具 ItyFuzz，用于有效地存储中间状态以减少重复执行的开销，实现了两种自定义的路径反馈机制，以高效地对有趣的状态进行分类和存储，实现更好的程序探索。
同时还展示了状态快照可以快速合成可重入攻击。最后，本文展示了使用ItyFuzz，可以实现响应时间较低的模糊测试，用以执行链上审计，识别和防止实际场景中针对智能合约应用的攻击。
参考文献
[1] Wüstholz V, Christakis M. Harvey: A greybox fuzzer for smart contracts[C]//Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 2020: 1398-1409.
[2] Choi J, Kim D, Kim S, et al. Smartian: Enhancing smart contract fuzzing with static and dynamic data-flow analyses[C]//2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2021: 227-239.
[3] So S, Lee M, Park J, et al. VeriSmart: A highly precise safety verifier for Ethereum smart contracts[C]//2020 IEEE Symposium on Security and Privacy (SP). IEEE, 2020: 1678-1694.
—END—
