ConFuzzius: A Data Dependency-Aware Hybrid Fuzzer for Smart Contracts

这篇工作发表于EuroS&P21

Torres C F, Iannillo A K, Gervais A, et al. Confuzzius: A data dependency-aware hybrid fuzzer for smart contracts[C]//2021 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE, 2021: 103-119.

符号执行的方法存在过拟合，导致假阳率
现有的模糊测试方法分析浅层的漏洞比较有效，对于执行时的深层的漏洞分析不够有效，导致较低的代码覆盖率/假阳
传统程序测试中已经证明结合符号执行和模糊测试的可行性

ConFuzzius是第一个针对智能合约的混合模糊测试器，采用进化的模糊测试方法执行合约的浅层部分，约束求解来生成符合复杂条件的输入，防止进化模糊测试方法探索深层部分。

ConFuzzius充分利用动态的数据依赖分析来生成更可能导致出现漏洞的交易序列

实验数据采用精选的128个合约和包含21000真实世界的合约，结果显示比当前最好的工具多检测出了23%的漏洞，代码覆盖率达到了69%，动态数据依赖分析可以加速漏洞检测18%

Introduction

如果允许一个参与者修改智能合约，合约的信任将不复存在

智能合约系统中不允许中立的第三方，不能被废止，不可篡改性的代价是智能合约在部署前必须经过大量的测试

验证智能合约行为的四种方法：

单元测试：需要人力来覆盖代码的全部部分，仅能去除测试用例中的一小部分bug
符号执行：抽象分析程序的行为；对于复杂的合约检测速度慢（路径爆炸）
静态分析：不执行代码，过度近似合约的行为，能够获得整个合约的执行情况；但是存在假阳率，需要手工检查
模糊测试：通过自动生成测试用例来快速推理合约，比静态分析假阳率低；代码覆盖率低

模糊测试的挑战：

输入生成：输入空间可能很大
状态探索：智能合约是基于状态的应用，执行可能依赖于特定输入序列下可达的状态
环境依赖：智能合约的运行时环境暴露了和底层区块链相关的额外的输入（时间戳、其他部署的合约），导致合约的执行流程可能依赖于环境信息和交易信息

作者解决三个挑战的思路是采用符号污点分析来生成五点输入的路径约束。观察到模糊器不处理时，启动约束求解器解决当前的约束问题，将这个解决方案收集在一个变异池中，模糊器可以从中获取来跨越具有挑战性的合约条件。

现有的混合工具（如Driller）在卡住时停止fuzzer并且切换到conbolic(concrete symbolic)方法来越过复杂条件，之后重启fuzzer，本文的解决方法保持模糊器运行并且只使用约束求解来生成模糊器最终会通过变异池选择的即时数据。

除了约束求解之外，本文进行路径终止分析来清除变异池中的不相关输入。

挑战2：为了处理合约的状态性，采用遗传算法的选择和交叉算子。遗传算法包括三个操作：

选择：从中种群选择2个个体
交叉：交叉算法将2个个体结合生成2个新的个体，挑战在于如何生成有意义的输入。因此，个体之间的数据依赖性指导我们的选择和交叉算子，只有当它们遵循一个写后读（RAW）数据依赖关系时才接受两个个体。
变异

挑战3：为了解决环境依赖的困难问题，对执行环境（即以太坊虚拟机）进行工具化，以模糊环境信息，并将合约的输入建模为一个元组，包含交易和环境数据。

贡献

第一个智能合约hybrid模糊器的设计
利用状态变量间动态数据依赖，在运行时高效的生成输入序列
ConFuzzius，第一个hybrid模糊器的实现
对128个经过筛选的智能合约和21K个真实世界的智能合约进行了CONFUZZIUS的评估，并证明了方法不仅可以检测到更多的漏洞（高达23％），而且可以实现比现有符号执行工具和模糊器更高的代码覆盖率（高达69％）

Background

Ethereum Smart Contracts

简单介绍智能合约和EVM

fuzzing

模糊测试（Fuzzing）或模糊测试是一种自动化的软件测试技术，通过将畸形或意外的数据作为程序的输入，执行程序并监控其效果，来查找程序中的漏洞。

进化模糊

指采用遗传算法收敛，测试用例的一代被定义为一个种群，而单个测试用例是一个个体。简而言之，每个一代的个体都根据适应度函数进行评估。在每一代结束时，只有最适应的个体被允许繁殖，遵循达尔文的自然选择或“适者生存”的思想。最终，个体将在收敛于最优解的过程中触发漏洞。

初始种群可以随机选或者启发式采样

终止条件可以是到达指定时间或者超过最大的代数

混合模糊

模糊测试在解决复杂条件时比较困难，导致代码覆盖率低

流行的解决办法是采用符号执行，理论上可以探索所有路径，但实际上由于程序复杂时路径指数级增长，导致不具备可扩展性；另一个缺陷是和执行环境的交互太少。

混合测试的想法是各取所长，在模糊器不能继续覆盖代码时，自动切换为符号执行，为没有覆盖的分支条件进行穷举搜索，当符号执行发现了未覆盖的分支条件后，求解并回退为模糊器

模糊测试和符号执行的交错保证了对程序浅的路径快速的执行和对复杂路径的覆盖

Overview

Example

一般满足ERC-20. 用户想要以每天加1ether的价格出售代币，第一天代币的售价为42

存在三个漏洞：

访问权限：构造函数typo，compiler默认该函数为public
时间戳依赖：now
ether泄露：只有转出的代码，没有转入合约的代码

输入生成

输入数据生成可以是完全随机的（黑盒）或由运行时信息驱动的（灰盒），原始的方法是从之前的输入进行变异生成新的输入，然而现实世界中有比较复杂的条件，如figure1 line21，对应的CFG如下

传统的随机策略将不能通过该条件（因为$2^{256}$次尝试才能产生一个合理的解harvey依赖于计算为每个分支编译输入的的开销矩阵，本文采用约束求解来按需生成复杂条件的值。本文的fuzzer不直接传播该值而是存储在变异池中，fuzzer可以从池中选择（每个函数声明都对应一个变异池）

开始时变异池为空，fuzzer用随机数据输入目标函数，一旦无法发现新的路径时，激活约束求解器生成新的值，采用符号五点分析来生成约束求解器需要的表达，污点采用符号值的形式

状态探索

合约的状态不同时，以太坊的同一条交易可能出现不同的结果

例子中先调用bug和Tokensale函数再调用withdraw函数，攻击者能够实现恶意提款，然而在实际的分析中自动发现函数调用特定顺序可能触发漏洞是具有挑战性的工作。

a transaction influences the output of a subsequent set of transactions if and only if it modifies a storage variable that one of the subsequent transactions will use.

观察：交易影响合约的storge变量并且该变量被后续的合约使用，即写后读的数据依赖

ConFuzzius追踪所有交易读和写的storge，然后进行将所有交易组合成写后读的形式

环境依赖

EVM在执行区块内的交易时会分析其中包含的区块信息

本文将区块信息建模为可fuzz的输入来解决这个问题，和交易数据一样进行模糊测试的流程

修改EVM实现能够在合执行时插入模糊的区块信息

还需要模拟对其他合约的调用：通过对合约调用进行实现，并将返回值建模为可模糊的输入来类似地解决这个挑战，修改的EVM在运行时注入模糊的返回值。

Design and Implementation

overview

进化模糊器
EVM
执行路径分析器

python 6000行

输入合约的源代码和区块链的状态（后者可选），将合约编译后获得ABI和EVM字节码，进化模糊器基于ABI生成输入，基于标准的遗传算法进行变异，将新生成的个体发送给EVM执行，EVM将执行路径发送给分析器，分析器执行若干分析（符号污点分析，数据依赖分析）

终止条件：已经生成多少代或过去了多少时间

进化模糊器

对个体编码：
- 不好的编码可能影响效率，本方案的编码如图所示，将个体表示为输入的序列，每个输入包含一个环境信息和一个交易的k-v对
  - 环境信息包括区块信息和调用返回值、数据大小、节点规模等
  - 交易包含发送方的地址、交易金额、gas上限，data
    - data前4个字节是函数选择器，后面是参数
种群初始化：最开始为N个个体，每个仅有交易，交易内的函数选择器是循环选取的，函数声明是基于ABI获取的，针对不同参数类型为每个函数生成参数，过去的k代不再影响代码覆盖率时重新选，这种软重启的方法将多样性重新引入种群并在种群变得同质化时延迟过早的收敛。
- 固定长度：随机选或者从触发有效输入域的情况的一组输入中获取
适度评估：评估个体的适度非常关键，由于需要多次计算效率，需要非常高（指数级影响），虽然获得完整的代码覆盖并不一定意味着所有的漏洞都会被发现，但未被探索的代码里的漏洞不可能被发现。适度函数定义基于分支覆盖和数据依赖，对个体$i$的适度函数定义如下：
- $fit(i)=fit_{branch}(i)+fit_{RAW}(i)$
- $fit_{branch}(i)$：计算该个体仍未探索过的分支，迭代该个体的执行路径然后分析所有条件分支jump指令，通过从堆栈中提取真分支的跳转目标来获取其跳转目标，并通过将程序计数器增加一来获取假分支的跳转目标。对于目的地址不在执行分支上的情况，将$fit_{branch}(i)$加1，优先选出探索更多分支的个体；
- 同样能够生成有用交易序列的个体也很重要。$fit_{RAW}(i)$利用执行路径分析器给出的交易依赖考虑该因素，初始时为0，当出现raw后+1
选择：为交叉阶段选择两个个体，本文选择的是参考文献[41]中提出的Linar ranking selection，将种群考虑为一个整体，而不是子集；
- Linar ranking selection：适度高的个体排在前面，被选择的概率和个体适度在种群中的排名成比例；可以给更适应的个体更多的权重，同时仍然允许一些机会选择适应度较低的个体，并潜在地为种群的多样性做出贡献。
- 传统的线性排名选择没有考虑数据依赖，两个个体一个采用线性排名方法选择，第二个个体是基于与第一个个体具有RAW依赖性的迭代方式进行选择的
交叉：交叉算子通过对输入两个现有个体进行重新组合生成两个新的个体。
- 本文不是随机组合两个个体，而是只有在第一个个体对存储位置进行写操作时，第二个个体才进行读操作（即RAW依赖性），才会将它们组合起来。
- 两种排列方式，个体 $ab/ba$
- 和传统的方法相比，本方案在合并两个个体而不是拆分开交换输入序列
- 如果两个个体间不存在依赖性，返回未加修饰的1/2个个体
- 存在RAW关系不意味着一定能交叉，存在交叉概率$p_c$
- 防止个体变得太长，交叉前检查长度的和小于$l$
  - $l$ 越小处理时间越短，发现漏洞的时间越短——效率
  - 反之，发现的漏洞可能更多——完备性
变异：变异算子随机编辑个体的某些部分来产生一个新的个体，为种群带来多样性
- 遍历输入序列，基于概率$p_m$变异每个交易和环境信息的值
- 变异可以有两种形式
  - 采用随机的值取代原来的值
  - 采用变异池中的值替代：类似于短期内存，允许模糊器重用之前观察到或学习到的值
    - 总共有9个不同的变异池：senders, amounts, gaslimits, function arguments, timestamps, block numbers, call results, call data sizes, and external code sizes
    - 每个池是循环数组，大小能存10个值

EVM

EVM负责在测试的合约的运行时字节码上执行个体生成的交易。性能对模糊器整体的性能表现影响很大，需要有很高的交易处理速度

现有的智能合约客户端需要对交易进行RLP编码来序列化交易数据，作者发现实际的EVM执行时间和编解码相比可以忽略不计，因此本工具采用了开源的EVM python实现，集成到了模糊器中。该实现去除了挖矿的负担和编解码交易的时间，极大地增加了执行效率（合理吗？）

修改了EVM的设计

使得能够得到交易的执行路径，包括指令名、计数器、执行栈、调用深度、执行期间是否出现内部错误
简化设计，采用简单的存储模拟器记录执行时的状态变化，均保留在内存中
- 方便进行EVM状态的快照和恢复
- 允许插入定制的环境信息或修改函数调用结果

执行分析器

从EVM收到执行路径后，执行

代码覆盖率评估：计算执行路径中程序计数器的值
数据依赖分析：在模糊器执行过程中记录所有状态变量以及状态变量的读写情况，和现有静态分析的方案相比，本方案动态的获得运行时的状态变量的情况
- 静态分析快需要源代码；对于复杂的数组需要源代码
- 动态运行时分析可以追踪复杂的变量，缺点是额外的运行时间和实现开销，下图是以太坊对不同类型的状态变量计算方式
符号污点分析：产生符号约束，污点的形式是符号值的形式，跟踪污点的流动
- 仅对能进行fuzz的指令进行动态污点分析
- 跨存储的污点的传播使得能够实现跨交易的污点分析
- 污点传播的逻辑遵循过度污点策略，如果指令的输入中至少有一个被污染，那么该指令的输出将被标记为污染
约束求解：模糊测试无法通过复杂的条件语句时，进化模糊器可能会过早收敛，约束求解器用于生成一个有效的输入来越过复杂的条件
- 作者自己实现的轻量级符号执行器仅执行算数相关的指令，比较逻辑和比特级运算符
- 否定最后一个约束条件，将逻辑公式中其余的符号变量替换为已用作触发执行跟踪的具体值，并使用Z3 SMT求解器生成输入以到达开放分支
- 实例化减小了公式的复杂度
- 将生成的输入加入到变异池中
终止分析：执行路径可能包含输入有效性的反馈，模糊器获得并得知一个输入是否有效、终止分析检查执行路径中表示执行正确和错误的操作码。检查到错误后分析最后一个路径约束，获得导致终止的输入并从池中移除
漏洞检测：综合以上输出进行漏洞检测，为下述漏洞类型设计了检测器：
- 断言错误
- 整数溢出
- 重入
- 交易顺序依赖
- 区块依赖
- 未处理异常
- 不安全的delegate调用
- ether泄露
- 未受保护的自毁

很难不赞同（

Evaluation

回答3个关键问题

相比于当前的符号执行或者fuzzing的工具，confuzzius是否实现了更高的代码覆盖率？
相比于当前的符号执行或者fuzzing的工具，confuzzius是否发现更多的漏洞？
ConFuzzius的不同组件在代码覆盖率和漏洞检测方面的相关性有多强？

数据集

测试代码覆盖率有源码 21147份合约，根据EVM字节码指令个数分为2类（采用标准的k-means分类算法，Elbow and the Silhouette方法确定分类器数量
- 小于3632，17803份合约
- 3344份合约
测试漏洞检测：128份合约（包含148注释出的漏洞），基于smartbugs，缺失了部分漏洞类型，作者从Smart Contract Weakness Classification进行了扩展

baseline

因为本工具是模糊测试和符号执行结合的，对比方案分别是符号执行和模糊测试两类

Smartbugs的结论是Mythril的效果比SmartCheck Securify和Maian更好

M-PRO采用了类似的交易序列结合策略

ILF是当前较好的fuzzing工具（比contractfuzzer和ECHIDNA好）

sFuzz基于AFL，没有和之前工作的对比

Setup

每个实验进行10次，每次的种子独立

第一个数据集 10 mins；1 hours
- 初步测试显示，大多数工具在这些时间之后并没有产生更多的覆盖率
第二个数据集每个合约10分钟

cluster 10个节点，每个128GB，CentOS release 7.6.1810，2个Intel® Gold 6132 CPUs with 14 cores, each clocked at 2.60 GHz.

代码覆盖率10代不变即种群重新初始化，个体最长长度为5

Z3 version 4.8.5，时间上限100ms

实验结果

代码覆盖率：ConFuzzius在第一个数据集上大小合约结果均表现最优（91% 81%）
- 大小合约差距最小（10%），Mythirl（31%）
- 更短时间内实现更高的覆盖率，1 second 66% instruction coverage, whereas ILF and
  SFUZZ achieve solely 12% and 15%, respectively
漏洞检测：10类漏洞，第二个数据集（真/假）
- 测出了106/148个漏洞，约71%
组件评估：分别评估约束求解、写后读数据依赖分析和环境实例化三部分组件的重要性，随机选了100个合约
- 意义最大的组件可能是Constraint Solving

Realted work

软件模糊测试：AFL是当前最广泛使用的模糊测试器，基于遗传算法；KLEE和SAGE是白盒模糊器，在受限环境中执行代码。Driller同样是混合模糊器，混合了选择性concolic方法
智能合约模糊测试：
- ContractFuzzer基于输入种子产生输出，部署了整个定制的测试网来模糊测试交易，Confuzzius仅模拟EVM，更加高效且不依赖用户提供的输入种子
- Echidna是基于性质的智能合约测试工具，利用了基于语法的模糊测试，依赖于用户定义的谓词（solidity的断言），无法自动化检查漏洞
- Harvey基于指令细粒度成本度量指标预测新的输入
- ILF基于模仿学习（imitation learning），在模糊测试前需要学习阶段，依赖一个神经网络
- sFuzz基于AFL，基于随机策略生成交易序列
- EHTPLOIT是基于模糊测试的智能合约漏洞生成器
智能合约符号执行：
- MPRO：结合了符号执行和数据依赖分析
- ETHracer采用相反的混合方式，先符号执行再fuzz，完全随机
智能合约静态分析：
- ZEUS：自动化验证的框架
- Securify：静态分析出语义信息，检查violation和compliance
- VANDAL，类似的工具

攻击检测器设计思路

Assertion Failure：检查执行路径是否包括ASSERTFAIL or INVALID
Integer Overflow：由于不是所有的溢出都有害而且编译器可能为了优化引入整数溢出
- 当溢出编辑了合约的状态才认为是有害的，计算的记过写入存储或被用来发钱
- 分析执行路径是否包含ADD, MUL or SUB指令
- 从栈中提取计算符然后执行算术操作，和栈中的结果比较
- 如果不同，将计算结果标记为污点，如果被标记的结果进入SSTORE CALL指令
重入漏洞：检查call的gas是否大于2300，转账金额大于0；如果call之前出现SLOAD,call之后SSTORE，CALL的存储地址和SLOAD一样
交易顺序依赖：检查是否两条执行路径发送者不同，前一条路径写某一存储位置，后一个读
区块依赖：检查CREATE, CALL,DELEGATECALL, or SELFDESTRUCT是否包含或依赖BLOCKHASH, COINBASE, TIMESTAMP, NUMBER, DIFFICULTY, or GASLIMIT
未处理异常：检查是否有call，并且压入1；再检查结果是否有对应的JUMP I
不安全的delagatecall：检查DELEGATECALL是否以STOP终止，并且发送的地址是攻击者（fuzzer生成攻击者和善良参与者的地址）
Ether泄露：检查call指令，接收者是从未在之前交易内向合约发送过ether的攻击地址，并且从来没有被非攻击者地址当做参数发送过
Ether锁定：检查合约是否能接受但不能发送ether
- 接受ether：检查是否有交易值大于0，以stop终止
- 发送ether：检查不包含任何CREATE, CALL, DELEGATECALL, or SELFDESTRUCT instruction
Unprotected Selfdestruct：依赖于攻击者账户，检查执行路径包含SELFDESTRUCT，发起者是攻击者地址，并且之前没有被当参数传递过

Conclusion

第一个混合的fuzzer/

解决了三个挑战：

输入生成：进化模糊算法+约束求解
状态探索：对状态数据依赖分析，生成交易序列
环境依赖：建模区块相关的信息作为fuzz的输入

实验在128 21K的数据集上分别测试了覆盖率、测出漏洞类型和工具组件重要性的结果

实验

玩了个孔子的谐音梗christoftorres/ConFuzzius: A data dependency-aware hybrid fuzzer for Ethereum smart contracts (EuroS&P 2021). (github.com)

1
2
3

docker pull christoftorres/confuzzius
docker run -i -t christoftorres/confuzzius
python3 fuzzer/main.py -s examples/TokenSale/contracts/TokenSale.sol -c TokenSale --solc v0.4.26 --evm byzantium -t 10

被测试合约为TokenSale.sol，比较简单

pragma solidity ^0.4.26;

interface Token {
  function transferFrom(address sender, address recipient, uint256 amount) external returns (bool);
  function allowance(address owner, address spender) external view returns (uint256);
}

contract TokenSale {
  uint256 start = now;
  uint256 end = now + 30 days;
  address wallet = 0xCafEBAbECAFEbAbEcaFEbabECAfebAbEcAFEBaBe;
  Token token = Token(0x1234567812345678123456781234567812345678);

  address owner;
  bool sold;

  function Tokensale() public {
    owner = msg.sender;
  }

  function buy() public payable {
    require(now < end);
    require(msg.value == 42 ether + (now - start) / 60 / 60 / 24 * 1 ether);
    require(token.transferFrom(this, msg.sender, token.allowance(wallet, this)));
    sold = true;
  }

  function withdraw() public {
    require(msg.sender == owner);
    require(now >= end);
    require(sold);
    owner.transfer(address(this).balance);
  }
}

实验结果显示代码覆盖率非常优秀，能够检测出区块信息依赖和以太币泄露漏洞

具体产生漏洞的交易序列：

测试较为复杂的合约WalletLibrary

代码覆盖率依然比较优秀，74.99%（2881/3842），单个合约仅10.62s

其他

其他人对Confuzzius的复现总结 CONFUZZIUS Comparisons - HackMD
会议简要视频介绍IEEE EuroS&P 2021 - ConFuzzius: A Data Dependency-Aware Hybrid Fuzzer for Smart Contracts - YouTube
后续可以阅读：
- 现有工具对比测试：[ICSE20]Smartbugs1.0、2.0
- 模糊测试：[CCS19]ILF >[ISSTA20]Echindna
- 符号执行：[HITB18]Mythril>[ASE19]Manticore