优化智能合约模糊测试器 - Trail of Bits博客

Sam Alws
2022年3月2日
fuzzing, blockchain

在我的冬季实习期间，我应用了代码分析工具（如GHC的Haskell分析器）来提高Echidna智能合约模糊测试器的效率。最终，Echidna的运行速度提升了超过六倍！

Echidna概述

使用Echidna时，用户需要提供智能合约和一系列在任何情况下都应满足的条件（例如"用户持有的代币数量永远不能为负数"）。然后，Echidna会生成大量随机交易序列，用这些交易序列调用合约，并检查合约执行后条件是否仍然满足。

Echidna使用覆盖引导的模糊测试；这意味着它不仅使用随机化生成交易序列，还会考虑之前的随机序列覆盖了多少合约代码。覆盖引导能更快地发现漏洞，因为它倾向于选择能深入程序并触及更多代码的序列；然而，许多用户注意到，开启覆盖引导后Echidna运行速度明显变慢（在我的电脑上慢了六倍多）。我实习的任务是找出执行时间缓慢的根源，并加速Echidna的运行时间。

优化Haskell程序

优化Haskell程序与优化命令式程序非常不同，因为执行顺序通常与代码编写顺序大相径庭。Haskell中一个常见问题是因惰性求值导致的内存使用量极高：表示为"thunk"的计算被存储起来以备后续求值，因此堆不断扩展直至耗尽空间。另一个更简单的问题是，一个慢速函数可能会被重复调用，而实际上只需要调用一次并将结果保存即可（这是编程中的普遍问题，并非Haskell特有）。在调试Echidna时，我必须同时处理这两个问题。

Haskell分析器

我大量使用了Haskell的分析功能。分析让程序员能够查看哪些函数占用了最多的内存和CPU时间，并查看显示函数调用关系的火焰图。使用分析器非常简单，只需在编译时添加一个标志（-prof），并在运行时添加另一对标志（+RTS -p）。然后，可以使用此工具根据生成的纯文本分析文件（这本身非常有用）制作火焰图；以下是一个示例：

此火焰图显示了每个函数占用的计算时间。每个条形代表一个函数，其长度代表所占用的时间。一个条形堆叠在另一个条形上表示一个函数调用另一个函数。（条形的颜色是随机选择的，出于美观和可读性考虑。）

在样本输入上运行Echidna生成的分析文件主要显示了通常预期的函数：运行智能合约的函数、生成输入的函数等。然而，引起我注意的是一个名为getBytecodeMetadata的函数，它扫描合约字节码并查找包含合约元数据（名称、源文件、许可证等）的部分。这个函数只需要在模糊测试器启动时调用几次，但它却占用了大量的CPU和内存。

Memoization修复

在代码库中搜索后，我发现了一个拖慢运行时的问题：在每个执行周期中，getBytecodeMetadata函数都会在同一小组合约上重复调用。通过存储getBytecodeMetadata的返回值并在后续查找而非重新计算，我们可以显著提高代码库的运行速度。这种技术称为memoization。

添加此更改并在一些示例合约上测试后，我发现运行时间降低到了原始时间的30%以下。

状态修复

我发现的另一个问题与运行时间很长的以太坊交易有关（例如，计数器高达100万的for循环）。这些交易无法计算，因为Echidna内存不足。这个问题的原因是Haskell的惰性求值用未求值的thunk填满了堆。

幸运的是，这个问题已经被其他人在GitHub上发现并提出了修复建议。修复与Haskell的State数据类型有关，该类型用于更方便（且更简洁）地编写传递状态变量的函数。修复基本上包括在某个函数中避免使用State数据类型，并改为手动传递状态变量。这个修复尚未添加到代码库中，因为它产生了与当前代码不同的结果，尽管它本应是一个不影响行为的简单性能修复。在处理了这个问题并清理代码后，我发现它不仅修复了内存问题，还提高了Echidna的速度。在示例合约上测试修复后，我发现运行时间通常降低到了原始时间的50%。

为了解释这个修复为何有效，我们来看一个更简单的例子。假设我们有以下使用State数据类型对所有从5000万到1的数字进行简单状态更改的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import Control.Monad.State.Strict

-- 如果状态为偶数，则除以2并加num，否则只加num
stateChange :: Int -> Int -> Int
stateChange num state
    | even state = (state div 2) + num
    | otherwise = state + num

stateExample :: Int -> State Int Int
stateExample 0 = get
stateExample n = modify (stateChange n) >> stateExample (n - 1)

main :: IO ()
main = print (execState (stateExample 50000000) 0)

这个程序运行正常，但占用大量内存。让我们编写不使用State数据类型的相同代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

stateChange :: Int -> Int -> Int
stateChange num state
    | even state = (state div 2) + num
    | otherwise = state + num

stateExample' :: Int -> Int -> Int
stateExample' state 0 = state
stateExample' state n = stateExample' (stateChange n state) (n - 1)

main :: IO ()
main = print (stateExample' 0 50000000)

这段代码使用的内存远少于原始代码（在我的电脑上是46 KB对3 GB）。这是因为Haskell编译器的优化。我使用-O2标志编译：ghc -O2 file.hs; ./file，或ghc -O2 -prof file.hs; ./file +RTS -s获取内存分配统计信息。

未经优化时，第二个示例的调用链应该是：stateExample' 0 50000000 = stateExample' (stateChange 50000000 0) 49999999 = stateExample' (stateChange 49999999 $ stateChange 50000000 0) 49999998 = stateExample' (stateChange 49999998 $ stateChange 49999999 $ stateChange 50000000 0) 49999997 = ...。注意不断增长的(... $ stateChange 49999999 $ stateChange 50000000 0)项，它扩展以占用越来越多的内存，直到n达到0时最终被迫求值。

然而，Haskell编译器很聪明。它意识到最终状态无论如何最终都会被需要，并使该项严格，因此不会占用大量内存。另一方面，当Haskell编译使用State数据类型的第一个示例时，中间有太多抽象层，它无法意识到可以使(... $ stateChange 50000000 0)项严格。通过不使用State数据类型，我们使代码对Haskell编译器更易读，从而更容易实现必要的优化。

在我帮助解决的Echidna内存问题中也发生了同样的事情：最小化State数据类型的使用帮助Haskell编译器意识到一个项可以变得严格，从而显著减少了内存使用并提高了性能。

替代修复

修复我们上述示例内存问题的另一种方法是将定义stateExample n的行替换为以下内容：

1
2
3
4

stateExample n = do
    s <- get
    put $! stateChange n s
    stateExample (n-1)

注意第三行中$!的使用。这强制对新状态的求值变得严格，消除了需要优化为我们使其严格的需求。

虽然这在我们简单的示例中也修复了问题，但在Haskell的Lens库中事情变得更加复杂，因此我们选择不在Echidna中使用put $!；而是选择消除State的使用。

结论

我们引入的性能改进已经在2.0.0版本中提供。虽然我们这一轮取得了巨大成功，但这并不意味着我们在Echidna模糊测试速度上的工作已经完成。Haskell是一种编译为本地代码的语言，通过足够的分析努力，它可以非常快。我们将继续对Echidna进行基准测试，并关注慢速示例。如果您认为自己遇到了一个，请提交问题。

我非常享受在冬季实习期间从事Echidna代码库的工作。我学到了很多关于Haskell、Solidity和Echidna的知识，并获得了处理性能问题和处理相对较大代码库的经验。我特别感谢Artur Cygan抽出时间提供宝贵的反馈和建议。

如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News