Foundry、Echidna 与 Wake：模糊测试收缩算法比较

liumuhui 1天前阅读数 2 #区块链

文章标签模糊测试智能合约 Foundry Echidna Wake

介绍

模糊测试对于安全的智能合约测试至关重要，但也面临着挑战。测试执行通常很慢，而分析失败可能需要更多的时间和精力。

Shrinking（缩减）解决了这个问题。当模糊测试在有状态测试期间发现错误时，缩减算法会最小化重现该错误所需的操作序列。这会将复杂的失败转化为更简单的失败，从而更快、更有效地进行调试。

现代模糊测试工具，如 Foundry、Echidna和 Wake 都支持 shrinking，尽管每个工具都使用不同的方法。本文比较了它们的算法以及每种设计背后的权衡。

Foundry 不变性测试中的 Shrinking 算法

来源：Foundry shrink.rs

Foundry 在不变性测试期间支持使用自顶向下的方法进行 shrinking。它尝试从序列的开头删除交易，并检查错误是否仍然发生。

过程：

每次删除一个交易，从顶部开始。
重新运行序列以检查不变性失败是否仍然存在：
- 如果失败仍然存在，则保持删除该交易。
- 如果不再失败，则恢复该交易。
重复此操作，直到达到缩减限制或无法进一步缩减为止。
返回仍然触发失败的最短序列。

此方法保留了不变性失败，但不尝试重现其他错误。它也不简化函数调用参数。

在这三个工具中，Foundry 使用了最简单的 shrinking 策略。

Echidna 中的 Shrinking 算法

来源：Echidna Shrink.hs

Echidna 系统地将失败的测试用例缩小为最小的可重现示例，它结合了结构化缩减和参数简化。

将reverting交易替换为 NoCall 占位符（除了最后的交易，它始终被保留）。
删除不推进时间或区块号的不必要的 NoCall 交易。
应用两种随机选择的策略之一：
- “Shorten”（缩短）：删除一个随机选择的交易。
- “Shrink”（缩减）：通过以下方式简化所有交易：
  - 减少参数值（例如，减小数字或简化地址）
  - 降低 ETH 金额、gas 价格以及时间或区块延迟
  - 将发送者替换为更简单的地址
清理由 shrinking 引入的任何新的无用 NoCall 交易。
重新运行序列以确认失败仍然可以重现。
重复此操作，直到达到缩减限制或无法进一步缩减为止。

Echidna 支持交易和参数的 shrinking，这使其能够生成高度缩减的测试用例，从而实现高效调试。

Shrinking 参数

Echidna 还通过将值减小到更小的数字并将地址替换为更简单的地址来简化函数输入。

这确保了在逐步简化失败用例的同时，该错误仍然可以重现，从而使开发人员可以更快、更轻松地进行调试。

Wake 中的 Shrinking 算法

来源：Wake fuzz_shrink.py

阶段 0：收集流程状态

重新运行模糊测试序列，以从失败的测试中收集初始状态数据和详细的错误上下文。

阶段 1：按流程类型删除

列出所有流程函数类型及其调用计数。
从调用次数最多的类型开始，并尝试删除该类型的所有调用。
重新运行序列以检查错误是否仍然发生。

阶段 2：逐步删除

从上到下遍历序列，一次删除一个流程函数。

如果错误仍然可以重现，则保持删除。
如果不能，则恢复删除的调用。

使用快照来跳过重新执行序列中先前缩减的部分。

Wake 还支持 shrinking 期间的快捷方式。如果在序列的早期触发了相同的错误，它会将原始错误替换为这个更早的实例，通常会导致大幅度缩减。

Foundry、Echidna 和 Wake 中 shrinking 算法的对比表，显示了在简易性、序列长度和灵活性方面的差异。

三者之间的主要区别

Foundry、Echidna 和 Wake 中使用的模糊测试策略直接影响了每个工具实现 shrinking 的方式。

Foundry 采用了最简单的方法。它通过随机调用函数并检查不变量来进行模糊测试。它的 shrinking 算法仅删除交易，不简化参数。

Echidna 以更短的序列运行更长时间，系统地探索执行路径。默认情况下，这通常会导致更紧凑的失败用例。它的 shrinking 将交易删除与参数简化相结合，使用 NoCall 占位符和随机策略来最小化失败的输入。

Wake 通过在 Python 中重新实现合约逻辑并验证预期状态来应用差分模糊测试。这允许精确地定位攻击向量和内部检查。但是，Wake 倾向于生成更长的序列，这需要更激进的 shrinking。它的算法使用 Python 的 deepcopy 和 EVM 状态快照来支持灵活的测试组合。与 Echidna 不同，它不使用删除的失败交易，以便在测试中保持灵活性。