优化智能合约模糊测试器 - 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 和内存资源。

记忆化修复

通过代码库排查，我发现一个导致运行缓慢的问题：在每个执行周期中，getBytecodeMetadata函数都会在同一小组合约上重复调用。通过存储getBytecodeMetadata的返回值并在后续直接查询而非重新计算，我们可以显著提升代码库运行效率。这种技术称为记忆化。

实施更改并在示例合约上测试后，我发现运行时间降低至原时间的 30%以下。

状态修复

另一个发现的问题是处理长时间运行的以太坊交易（例如计数器高达百万次的循环）。这些交易无法计算，因为 Echidna 会耗尽内存。该问题的根源在于 Haskell 的惰性求值机制使堆空间充满了未求值的 thunk。

幸运的是，此问题的修复方案已由他人在 GitHub 上提出。修复涉及 Haskell 的 State 数据类型，该类型用于更方便（且更简洁）地编写传递状态变量的函数。修复方案主要是避免在特定函数中使用 State 数据类型，改为手动传递状态变量。该修复此前未被纳入代码库，因为它产生了与当前代码不同的结果，尽管这本应是不影响行为的简单性能修复。处理完这个问题并清理代码后，我发现它不仅解决了内存问题，还提高了 Echidna 的速度。在示例合约上测试表明，运行时间通常降低至原时间的 50%。

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

import Control.Monad.State.Strict
stateChange :: Int -> Int -> IntstateChange num state  | even state = (state div 2) + num  | otherwise = state + num
stateExample :: Int -> State Int IntstateExample 0 = getstateExample n = modify (stateChange n) >> stateExample (n - 1)
main :: IO ()main = print (execState (stateExample 50000000) 0)

该程序运行正常但占用大量内存。现在我们编写不使用 State 数据类型的相同功能代码：

stateChange :: Int -> Int -> IntstateChange num state  | even state = (state div 2) + num  | otherwise = state + num
stateExample' :: Int -> Int -> IntstateExample' state 0 = statestateExample' 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 编译器很聪明。它意识到最终状态终究会被需要，于是严格处理该项，避免占用巨额内存。相反，当编译使用 State 数据类型的第一示例时，过多的抽象层阻碍了编译器意识到可以将(... $ stateChange 50000000 0)项设为严格。通过不使用 State 数据类型，我们使代码对 Haskell 编译器更易读，从而更容易实施必要的优化。

我在 Echidna 内存问题中解决的正是相同情况：最小化 State 数据类型的使用帮助 Haskell 编译器认识到某项可设为严格，从而大幅降低内存使用并提升性能。

替代修复方案

解决上述示例内存问题的另一种方法是将stateExample n的定义行替换为：

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

注意第三行使用的$!运算符。这会强制严格求值新状态，无需优化机制代为严格化。

虽然这个方案在简单示例中也能解决问题，但在 Haskell 的 Lens 库中情况会变得更复杂，因此我们选择不在 Echidna 中使用put $!，而是直接消除 State 的使用。

结论

我非常享受在冬季实习期间参与 Echidna 代码库的工作。我深入学习了 Haskell、Solidity 和 Echidna，并获得了处理性能问题和大型代码库的宝贵经验。特别感谢 Artur Cygan 抽出时间提供有价值的反馈和建议。更多精彩内容 请关注我的个人公众号 公众号（办公 AI 智能小助手）公众号二维码

办公AI智能小助手