Harvey: A Greybox Fuzzer for Smart Contracts

本文由ConsensusSys的Valentin Wüstholz和MPI-SWS的Maria Christakis两位作者，发表于FSE ‘20。

Intro

本文介绍了为智能合约设计的灰盒Fuzzer：HARVEY。对智能合约进行模糊测试的工作有许多，本文的主要贡献是提供了真实工业可用的合约交易序列生成器，并保证了搜索空间和测试结果的可追踪性。

灰盒是一种介于 符号执行/白盒 与 完全随机/黑盒测试 之间的方法，可以在性能和有效性之间保持一定的平衡。实现过程中，这类方法不一定需要进行复杂的程序分析和约束求解，而是依赖于轻量的插桩来指示路径。

HARVEY的设计目标是解决Fuzzing在智能合约中应用的两个问题：交易执行时分枝覆盖率较低、合约生存周期中状态变化较多。作者设计了1.新输入预测 和 2.定点按需fuzz交易序列，两个方法来提高合约fuzzer的表现，并在27个真实合约中进行了验证。

Challenges

Challenge #1

尽管灰盒可以在性能和有效性之间有一定的平衡，但完全随机的输入（如随机bit翻转），并不完全适应智能合约。这会使得大量的输入都无法产生新路径。现有工作已经可以处理一些低频率路径、易被攻击的路径、深路径或者程序中特定的一部分代码路径。这些工作大都聚焦于调整种子的优先性和突变的位置。

Challenge #2

智能合约的生存周期中，状态会变化许多次（比如一个读博游戏）。而这些状态变化可能代表新路径们也可能只是旧路径的无意义重复，fuzzing的执行过程中，需要对这些状态变化进行探索，但这些状态变化又可能随着交易序列指数增长。因此在工业中，发现状态变化相关的bug很难。

FUZZING WITH INPUT PREDICTION

这段代码构造了一个智能合约函数baz，输入是三个256-bit整数，输出一个整数，共有5条路径，每个路径都有不同的返回值。

使用AFL进行测试时，12小时内只找到了4条路径。这个过程中使用了四个输入的测试集，输出2在311M不同输入的情况下依然没有被找到，这是因为分支的检查条件太“窄”了。比如在代码14行，fuzzer很难精准突变出42，并且同时符合其他条件来执行分支。在本工作中使用的输入预测不需要预先分析或者求解，但是也需要一些额外插桩来收集更多信息。

Fuzzer的输入为程序、种子和代价函数f_cost。它可以把执行状态转换为代价的数值表示，当程序执行到某一状态s时，fuzzer计算f_cost(s)。比如在上述程序中，每个minimize都会在执行时计算一次cost，这种cost是计算在EVM内，而不是在程序编译时插桩，所以不会影响语义，也不会影响gas。

上图中程序的代价计算定义了最优的分支反转条件。举例，当变量d=0时，程序在第一个if处会走then分支，第四行的minimize表达式为1，这意味着当前执行顺序到在该处执行else的距离为1；当d=-1时，这里也会走then分支，minimize表达式的值为2，意味着距离执行else分支更远了。

基于这些信息，我们的输入预测就可以提出新的输入，来试图让这段代码走向else，如下一个测试用例中d=7的话，第4行的minimize确实最小了，但第五行的minimize表达式值为7，为这处代码距离执行then的距离。

这样继续计算分支，7-8、12-13、19-20行都可以计算出反转分支的最小cost。这种插桩的目标是最大化路径覆盖，因此不会有一种情况可以同时最小化所有的值，当所有分支都被遍历到的时候，fuzzer也就完成了全路径覆盖。

这里HARVEY遍历了所有5种路径，花费时间8s，产生不同的输入15545个。

State Space Exploration

上图展示了一个合约Foo，构造函数初始化了状态变量x和y。在函数Bar中，12行的断言是一个bug，这个断言会使得交易回滚，并浪费gas。要产生这个bug需要三个交易，第一个调用SetY（42），第二个 CopyY（），第三个Bar（）。

有三种方法可以用fuzzer测试这个合约：

1）每个function单独fuzz，不考虑state

2）每个function单独fuzz，考虑state作为input

3）对整个合约fuzz，并尝试探索可能的交易顺序

对于我们想发现的bug来说，第三种是最合适的，同时也有一定的挑战。序列的不同组合会使得用例指数增长，也就更难在有限时间里发现一个单独的case。

这里使用的方法是 按需驱动的-序列模糊测试（demand-driven sequence fuzzing）。首先，fuzzer会发现唯一一个需要超过一个交易来覆盖的就是断言之前的分支。因此，HARVEY会只生成以Bar结尾的交易序列。第二点，这种方法目标是增加最后调用函数的路径覆盖。换言之，其他前序的交易都只是为了设定函数之间共享的状态变量。所以调用SetY（42）和IncX（）四十二次其实会产生同样的覆盖结果。

HARVEY在29秒之内就找到了这个断言报错的情况，共生成了48117个输入。

Evaluation

这里选取了27个benchmark来验证，大多数合约长度为几百行代码（至多～3000行）。

这里主要验证以下几个方面的问题：

RQ1：输入预测的有效性

输入预测在提升检测速度和覆盖率方面都非常有效。

RQ2：迭代输入预测的有效性

仅使用一次Secant迭代就已经可以提升效果，这也说明大多数测试用例的条件都是线性或者部分线性的。

RQ3：按需驱动的序列测试的有效性

大多数Bug都需要交易序列才能触发，这里可以看到剪枝的效果非常有效。

RQ4：工业背景下的有效性

这里是在用户的合作下完成的，B设定最快，并检测了48376条指令，9118个路径，发现了需要8个交易序列才能触发的问题，比A快了2倍，比D快了12 倍。