智能合约模糊测试器性能优化实战

优化智能合约模糊测试器 - 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 -> 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数据类型的相同功能代码：

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编译器很聪明。它意识到最终状态终究会被需要，于是严格处理该项，避免占用巨额内存。相反，当编译使用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抽出时间提供有价值的反馈和建议。