sFuzz: 高效自适应的智能合约 fuzz

前言

本文将对 ICSE 2020 会议论文 sFuzz: An Efficient Adaptive Fuzzer for Solidity Smart Contracts 进行解读。这篇论文的主要研究内容是综合运用 AFL 的策略和自适应方法来 fuzz 智能合约，并开发为一整套工具，其价值在于这种互补的策略使得 fuzz 更加高效，且达到了较高的代码覆盖率，可以发现更多漏洞。

论文地址：https://dl.acm.org/doi/10.1145/3377811.3380334

源码地址：https://github.com/duytai/sFuzz

论文作者：Tai D. Nguyen, Long H. Pham, Jun Sun, Yun Lin, Quang Tran Minh

正文

研究背景

现如今，智能合约作为图灵完备的程序在区块链上以分布式自治信任的方式执行，在给各行业带来革命性改变的同时，也有着极大的安全隐患。

和传统程序不同，智能合约一旦部署上链就无法轻易更改，这使得漏洞具有极强的危害性，近年来对以太坊智能合约的攻击日益增多，其中最著名的便是发生于 2016 年的 The DAO Attack，直接导致了以太坊的硬分叉与社区的分裂。

本文主要关注自动化测试技术用于发掘智能合约中的漏洞，必须解决以下三个问题：

• 如何运行测试用例
• 如何生成测试用例
• the oracle problem

这里需要解释一下 oracle 的概念，整个以太坊系统可以看作分布式的状态机，为了保证达成共识，避免状态的不一致，链上所有操作都是确定性 (deterministic) 的。但现实世界就是充满不确定性的，oracle 就是和链上链下沟通的中间件，而 oracle 本身又是中心化的，现实世界中的软件安全问题都会在其身上体现，具体有哪些安全问题本文并未详细说明。最早关于以太坊智能合约攻击的研究参见 A Survey of Attacks on Ethereum Smart Contracts SoK，其列举了如 Gasless Send, Reentrancy 等漏洞，详见下表

针对智能合约的自动化测试之前已经有一些研究，比如 ContractFuzzer 和 Oyente 分别用模糊测试 (fuzzing) 和符号执行 (symbolic execution) 技术来进行自动挖掘。而本文的工作结合了这两种互补的技术，并且使用了一种高效的自适应策略来选取 fuzzing 所用的种子 (seeds) 以解决 AFL-based fuzzing 难以覆盖具有严格进入条件的分支这一问题。

样例展示

上图为一个简单的猜数字游戏合约程序，调用函数 start_quiz_game 以设置问题和答案，调用函数 Try 来支付 100 finney 并猜测数字，如果答案正确则会向调用者转帐。但该合约程序存在 Gasless Send 漏洞，可能导致调用者的 fallback function 被执行，从而引发 out-of-gas exception。

要挖掘合约中的漏洞，首先要建立一个区块链网络，配置相应的地址和数额，将合约部署在某一地址上，生成 test case（即一系列交易）来生成参数并调用函数 start_quiz_game 和 Try，但 AFL 随机生成数据的策略很难满足第二个条件，即仅有 1/2^256 的概率生成值为 100 的 uint 数据，所以很难覆盖到这一分支。sFuzz 使用了一种自适应的策略作为补充，定量计算 seed 与分支条件之间的距离，从而使 seed 能越来越接近满足分支条件。这一例子是仅包含一个 just-missed 分支的最简单情形，包含多个分支的 multi-objective 场景也能适用。

算法细节

基于反馈的 fuzzing 主要思想就是将 test generation problem 变为 optimization problem,使用某种形式的反馈作为 objective function 来解决最优化问题，而 sFuzz 策略的自适应性在于其会根据反馈来改变 objective function，整体上看属于遗传算法，如下图所示。

Init Polulation

初始化配置，生成多个 test cases（即交易函数调用），在为参数生成随机值时需要注意考虑变长的类型如数组，会先在 [0,255] 内确定个数，再对应生成每个元素的随机值。每个 test case 都会编码成如下 bit vector 的形式

Fit To Survive

适者生存阶段，通过设定如下距离函数来挑选新 seeds

该阶段算法如下：

策略受 search-based software testing (SBST) 启发但又更加高效，

Crossover and Mutation

这一阶段将之前生成的 seeds 进行变异，采用了 AFL 中的所有变异策略，还针对智能合约引入了一些如下新策略：

检查变异后的数据是否 valid，丢弃 invalid 和重复的结果。为了减少无效工作也同样采用了 AFL 中的启发式方法，比如当对某一块数据进行 WalkingByte 变异操作没有覆盖任何新分支则之后不再变异该块数据。

具体实现

编写了约 4347 行 C++ 代码，主要有三个组件：

• runner 管理 test case 的执行
  • 获取智能合约的字节码及其 ABI（application binary interface）作为输入，并生成用于分析 ABI 的 bash 脚本
  • 设置用于部署智能合约的区块链网络，并创建一个随机地址池，部署 normal attacker 和 reentrancy attacker
• libfuzzer 解决 test 的生成问题
  • 使用前文所述策略选择性地生成 test cases
  • 首先在运行时构建 CFG，因为在 fuzz 之前静态构建是很困难的，EVM 中分支跳转由操作码 jumpi 实现，其操作数是程序动态执行时的目标 PC 值，只有模拟整个栈才能获知，但代价太高。因此在 fuzz 过程中构建 CFG，当执行到 jumpi 时再记录目标并相应作为新节点添加到 CFG 中 。
  • 跳过不改变状态的 view, pure, constant 函数
• liboracles 解决 oracle problem
  • 通过 EVM 提供的 hook 机制以监测 test case 的执行
  • 可能存在 false positive

效果验证

Efficient

sFuzz 平均每秒可执行 208 个 test cases，明显比 ContractFuzzer 和 Oyente 高效，因为 ContractFuzzer 模拟整个区块链网络，而 sFuzz 仅模拟和智能合约漏洞相关的细节，且其基于 Node.js 和 Go，相比 C++ 低效。而 Oyente 采用符号执行，比 sFuzz 运行得更慢更是理所应当。

Effective

测量分支覆盖率较困难，因此以覆盖到不同的分支数作为指标。

绝大部分情况下 sFuzz 比 ContractFuzzer 更有效，少数例外也是由于 sFuzz 不改变状态的函数故而这些函数中的分支未被统计，而且 ContractFuzzer 生成 invalid 的 test cases 根本不符合编译器生成的 mandatory constraints 故而覆盖到了多余的分支。

Oyente 在绝大部分情况下覆盖了更多的分支，因为符号执行可以满足几乎所有分支条件，能发现 integer overflow，但现实中许多 state variable 无法被任意赋值，很多条件根本无法满足，这是其方法上的重大缺陷。

为了分析 sFuzz 的 soundness，作者手动检查了从结果中随机采样的智能合约，最终数量和真阳率结果如下表所示：

Adaptiveness

图表说明 AFL 的策略容易覆盖大多数分支，而自适应策略平均来讲也贡献了三成的 test cases。而且仅仅是运行了两分钟的结果，延长运行时间效果还会提高。

相关工作

智能合约 Fuzzer：ContractFuzzer 可以检查7种不同类型的漏洞，但并没有使用任何反馈来改进。Echidna 据说能够检查合约是否违反了某些用户预定义的属性，但未找到任何相关出版物。

符号执行引擎：有 teEther 和 MAIAN，sFuzz 可以与之结合形成混合的 fuzzing engine

还可与形式化验证 (formal verification) 和对智能合约的分析相联系

成果总结

针对智能合约的 Fuzz 是较新的领域，ContractFuzzer 应该是最早且引用最多的文章，而本文提出的 sFuzz 主要贡献在于使用自适应的策略以有效地覆盖 AFL 无法进入的分支。个人有收获的点：对问题的定义，test case 的表示（将函数调用编码为 bit vector），遗传算法部分是关键但缺乏相关背景无法完全理解。

参考文献

[1] Nguyen, Tai D., et al. “sfuzz: An efficient adaptive fuzzer for solidity smart contracts.” Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering. 2020.

[2] Jiang, Bo, Ye Liu, and W. K. Chan. “Contractfuzzer: Fuzzing smart contracts for vulnerability detection.” 2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2018.

[3] Atzei, Nicola, Massimo Bartoletti, and Tiziana Cimoli. “A survey of attacks on ethereum smart contracts (sok).” International conference on principles of security and trust. Springer, Berlin, Heidelberg, 2017.

[4] Luu, Loi, et al. “Making smart contracts smarter.” Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 2016.

[5] Grieco, Gustavo, et al. “Echidna: effective, usable, and fast fuzzing for smart contracts.” Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis. 2020.