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

Echidna概述

使用Echidna时，用户需要提供智能合约和一组无论发生什么情况都应满足的条件列表（例如"用户硬币数量永远不能为负数"）。然后，Echidna生成大量随机交易序列，使用这些交易序列调用合约，并检查合约执行后条件是否仍然满足。

Echidna使用覆盖率引导的模糊测试；这意味着它不仅使用随机化生成交易序列，还会考虑之前的随机序列覆盖了多少合约代码。覆盖率可以更快地发现错误，因为它偏向于深入程序并触及更多代码的序列；然而，许多用户注意到，当开启覆盖率时，Echidna运行速度明显变慢（在我的计算机上慢六倍以上）。我实习期间的任务是追踪执行时间缓慢的来源，并加速Echidna的运行时间。

优化Haskell程序

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

Haskell性能分析器

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

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

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

记忆化修复

在代码库中搜索时，我发现了一个减慢运行时的问题：getBytecodeMetadata函数在每个执行周期中对同一小组合约重复调用。通过存储getBytecodeMetadata的返回值，然后在需要时查找而不是重新计算，我们可以显著提高代码库的运行时间。这种技术称为记忆化。

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

状态修复

我发现的另一个问题是运行时间很长的以太坊交易（例如，计数器达到一百万的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