Foundry 符号执行升级在 SMT 求解之前证明有界非线性 EVM 字恒等式【免费下载链接】foundryFoundry is a blazing fast, portable and modular toolkit for Ethereum application development written in Rust.项目地址: https://gitcode.com/GitHub_Trending/fo/foundry导读本文解读 Foundry 仓库中.changelog/symbolic-polynomial-normalization.md记录的forge变更符号执行引擎foundry-evm-symbolic在把路径约束交给 SMT 求解器之前先通过本地规范化normalization证明更多有界非线性 EVM 字恒等式包括小型多项式等式、非回绕乘法、除法与位移的边界性质。读完本文你将理解这条变更背后的代数模型环 Z/(2^256) 上的稀疏多项式、它的触发条件与复杂度上限以及它如何与区间分析、单调乘积事实、硬算术回退搜索共同构成forge test --symbolic的求解前流水线并学会用源码与测试用例验证这些行为。变更背景foundry-evm-symbolic与forge test --symbolicFoundry 的原生符号执行引擎位于 crates/evm/symbolic它驱动forge test --symbolic让符号测试感觉像普通 Forge 测试编写 Solidity、运行 Forge要么得到证明结果要么得到经普通执行器回放确认的具体反例。关于结果语义PASS/FAIL/FAIL: incomplete与使用方式crates/evm/symbolic/README.md 有完整说明其中默认求解器命令是z3需本地安装如brew install z3或sudo apt-get install z3。符号测试是名为check*、prove*的函数例如// SPDX-License-Identifier: UNLICENSED pragma solidity ^0.8.20; import forge-std/Test.sol; contract MathSymbolicTest is Test { function check_average(uint256 a, uint256 b) external pure { uint256 average (a b) / 2; // Forge 应找到一个溢出反例。 assertGe(average, a b ? a : b); } }运行方式forge test --symbolic --match-test check_average forge test --symbolic --match-contract MathSymbolicTest这条 changelog 变更forge: minor正是发生在该引擎的求解器前端在真正发起 SMT 查询之前先尽量在本地证明非线性恒等式从而减少对求解器的依赖、缩短验证时间也让有界非线性性质在无需求解器参与的路径上直接得到证明。变更核心SMT 求解之前的本地规范化阶段求解器的查询流水线位于 crates/evm/symbolic/src/runtime/solver.rs其顺序清楚地体现了先本地、后求解器用normalize_constraints_for_solver_cached做带缓存的约束规范化缓存受SYMBOLIC_SOLVER_SAT_CACHE_MAX_ENTRIES约束见 solver.rs 顶部的normalize_constraints_for_solver_cached实现依次尝试fallback_single_var_model、fallback_two_var_model等局部回退模型当约束包含硬算术符号变量参与的乘法、除法、取模等且不含符号哈希时先运行hard_arith_fallback_model见 hard_arith_fallback.rs上述均不成立才调用query_normalized进入真正的 SMT 查询。本 changelog 的变更集中体现在第 1 步normalize_expr_for_solver/normalize_bool_for_solver新增了多项式恒等式判定与更丰富的有界边界重写。这些重写必须保持 EVM 位向量语义AGENTS.md 明确要求 Keep solver rewrites semantics-preserving under EVM bit-vector behavior。多项式规范化在环 Z/(2^256) 上识别恒等式环语义回绕不是障碍普通整数算术中(x y) * z x * z y * z是分配律在 EVM 上加法与乘法的字运算是模 2^256 的回绕wrapping依然保持环律。源码中的注释直接说明了这一设计opt.rs/// A sparse polynomial over the EVM word ring Z/(2^256). /// /// Addition, subtraction, and multiplication of EVM words obey the ring laws even when they /// wrap. Canonicalizing small expressions here lets the solver recognize nonlinear algebraic /// identities without replacing bit-vector semantics with unbounded integer arithmetic. struct Polynomial { terms: HashMapMonomial, U256, }也就是说规范化不会把位向量语义替换成无界整数算术而是在字环内做稀疏多项式展开与合并同类项从而识别分配律、消去律等非线性代数恒等式。判定入口polynomial_identity核心判定函数位于 opt.rsfn polynomial_identity(left: SymExpr, right: SymExpr) - bool { if !polynomial_normalization_can_help(left) !polynomial_normalization_can_help(right) { return false; } matches!( (Polynomial::from_expr(left), Polynomial::from_expr(right)), (Some(left), Some(right)) if left right ) }它被用于Eq比较的规范化当左右两侧都能展开为稀疏多项式且展开结果相等时等式直接规范化为常量true见 opt.rs 附近normalize_bool_for_solver中的调用点。触发条件跨和 × 积边界的表达式polynomial_normalization_can_helpopt.rs只对跨求和/乘积边界的表达式生效乘法Mul的某个操作数是加法或减法Add | Sub——典型的未展开分配律形状加法或减法的某个操作数是乘法Mul加法或减法中包含常量位移量 256的左移Shl因为常量左移在环内等价于乘以 2^k位移表达式同样按一次操作与一次乘法计入形状。随后它计算表达式的环形状操作数与乘法次数只有当operations 1 multiplications 0时判定多项式规范化可能有用。整个形状分析受MAX_LOCAL_ANALYSIS_NODES节点预算限制防止深层嵌套字节码表达式把证明捷径变成无界递归。稀疏多项式展开与复杂度上限Polynomial::from_expropt.rs带缓存自底向上构建常量与符号变量是基底Add/Sub/Mul递归组合运算基于wrapping_add/wrapping_mul天然对应环 Z/(2^256)。系数合并同类项时使用wrapping_add因此回绕项会正确相消。为避免对抗性表达式导致分发展开爆炸代码显式设置了三个上限opt.rsconst MAX_POLYNOMIAL_TERMS: usize 32; const MAX_MONOMIAL_FACTORS: usize 8; const MAX_POLYNOMIAL_PRODUCTS: usize 256;注释说明动机型记账恒等式需要两个项、每个项两个因子这些上限在覆盖普通恒等式的同时防止恶意表达式失控。因此该判定是有界的超出预算时from_expr返回None直接放弃多项式路径而不是让求解阶段变慢。保留非恒等式的形状一个容易被忽略但至关重要的性质不是恒等式的等式不会被乱改。测试solver_polynomial_normalization_keeps_non_identity_equality_shapetests.rs验证了(x y) * z expected在无法证明为恒等时保持原形状不变从而不干扰后续的求解器查询与反例搜索。非回绕乘法与区间分析非回绕乘法边界non-wrapping multiplication bounds由两部分支撑。WordInterval结构区间ConstraintContext维护每个符号表达式的上/下界upper_bounds/lower_boundsopt.rs并结合结构分析计算WordInterval。structural_intervalopt.rs支持常量 → 精确单点区间And与常量掩码 →[0, mask]Add/Sub/Mul→ 基于子区间边界做checked_add/checked_sub/checked_mul注意checked_mul失败即表示可能回绕此时不再给出区间这正是非回绕的判据Shr常量位移 → 区间整体右移收缩Ite→ 两个分支区间的并。interval_cachedopt.rs将显式路径约束边界与结构区间合并并同样受节点预算约束。有了区间x * y C这类约束在区间乘积不越过 2^256 时可在本地直接判定无需 SMT。单调乘积事实monotonic_product针对有序比较、及正性monotonic_product.rs 收集OrderFactsless_than、less_or_equal、positive三类事实实现product_monotonic_unsat与remove_implied_monotonic_constraints若a b且两侧都是正数则a * c b * c这类乘积比较可被证明代码逐一移除被其余路径约束蕴含的硬算术比较一次移除一个避免两个候选相互证明后再一起消失见remove_implied_monotonic_constraints的注释更重要的是注释明确指出单调事实用于保持健全的单调成功路径不落入启发式见证搜索——因为回退搜索只能给出反例无法建立证明。除法与位移的有界重写除法比较的缩放重写normalize_udiv_comparisonopt.rs把带除法的比较改写为无除法比较n / d k→n k * dn / d k→n (k 1) * dk n / d→k * d nk n / d→(k 1) * d n。其旁支exact_ceil_div_factor/exact_scaled_div_factoropt.rs处理恰好整除的缩放因子把(n * factor) / d这类形状化简。而mul_div_identityopt.rs识别(x * d) / d x的乘除消去。这些重写在构造字加法之前会先验证后继不会回绕见 opt.rs 的注释保证重写语义严格等价。受检乘法的守卫分支模型Solidity 的checked_mul展开为守卫x 0 || (x * y) / x y。checked_mul_guard_branch_modelhard_arith_fallback.rs把该守卫的语义情形直接建模为零分支、非零精确积、以及两种操作数顺序下的回绕积并为支持约束设定MAX_CHECKED_MUL_SUPPORT_VISITS 256的访问预算hard_arith_fallback.rs避免一次未命中消耗超过其要规避的求解器回退成本。位移乘法视角与区间收缩在多项式形状判定中常量左移Shl位移 256被视作乘法计入opt.rs因为x k ≡ x * 2^k (mod 2^256)从而共享乘法恒等式的证明能力而右移Shr在区间分析中被视为区间收缩运算min shift、max shift见structural_interval。两者共同覆盖了 changelog 提到的位移边界。求解前流水线的完整顺序综合 solver.rs 与上述模块一次model查询的本地阶段顺序为规范化约束带normalization_cache缓存条目数受限若规范化后直接矛盾as_const() Some(false)立即返回不可满足单变量、双变量回退模型搜索fallback_single_var_model/fallback_two_var_model若含硬算术且变量数 ≤HARD_ARITH_FALLBACK_MAX_VARS运行hard_arith_fallback_model含checked_mul_guard_branch_model返回经回放验证的模型单调乘积事实的不可满足判定product_monotonic_unsat与蕴含约束移除remove_implied_monotonic_constraints仍然未决才调用query_normalized发起 SMT 查询。而多项式恒等式判定发生在第 1 步的表达式规范化中(x y) * z x*z y*z、x x*0xFFFF...FF 0这类约束在进入任何回退或 SMT 查询之前就被直接折叠为true。这与 changelog 的措辞before SMT solving在 SMT 求解之前完全一致。测试验证crates/evm/symbolic/src/tests.rs与opt.rs内的模块测试直接验证了本变更的行为测试验证内容位置solver_normalizes_wrapping_polynomial_distributivity(x y) * z x*z y*z规范化为常量true回绕下分配律成立tests.rssolver_normalizes_wrapping_polynomial_cancellationx x * U256::MAX 0规范化为true环内消去律-x ≡ x·(2^256−1)tests.rssolver_polynomial_normalization_keeps_non_identity_equality_shape非恒等式(x y) * z expected保持原形状tests.rspolynomial_identity_handles_shared_dag共享 DAG 的多项式恒等判定opt.rspolynomial_factors_use_interned_identity_order因式顺序经 intern 规范化后left*right right*leftopt.rspolynomial_identity_stops_at_factor_limit/_term_limit/_product_limit超过因子、项、乘积上限时放弃判定opt.rspolynomial_identity_skips_irrelevant_and_unsupported_shapes无关/不支持形状不触发多项式路径opt.rspolynomial_analysis_stops_at_input_node_limit输入节点数超限时终止分析opt.rssolver_does_not_invert_guarded_zero_self_divisionite(a0, a/a, 0)规范化保持语义不错误消去自除tests.rs此外AGENTS.md 记录了实现层面的不变量可帮助理解为何这些重写是安全的规范化后的交换律字运算把较简单的操作数放在 RHS常量最终落在 RHSSymExpr::binop必须先接受两种 EVM 操作数顺序因为简化发生在交换律规范化之前Eq比较是可交换的并通过同一表达式排序助手排序有符号/无符号序比较不可交换不得移除左常量比较分支改动表达式排序或布尔简化时必须保留规范化/缓存行为求解器模型在回放确认之前不是用户可见的反例。如何验证与体验仓库提供了一致的本地验证命令见 AGENTS.md 的 Testing 一节cargo fmt --all cargo check -p foundry-evm-symbolic cargo nextest run -p foundry-evm-symbolic git diff --checkForge 集成行为可用聚焦的 CLI 测试cargo nextest run -p forge --test cli test_cmd::symbolic SYMBOLIC_CONFORMANCE1 cargo nextest run -p forge --test cli symbolic_conformance SYMBOLIC_LIMITS1 cargo nextest run -p forge --test cli symbolic_limits其中 conformance 与 limits 套件需要本地求解器且刻意更宽泛、更慢。日常使用只需安装z3后运行forge test --symbolic例如针对(x y) * z x*z y*z这类恒等式性质编写check*测试——现在它们会在 SMT 求解之前就被本地证明从而显著缩短反馈回路。小结.changelog/symbolic-polynomial-normalization.md这条forge: minor变更本质上是给foundry-evm-symbolic求解器前端增加了一层代数直觉在环 Z/(2^256) 上做稀疏多项式展开以识别分配律与消去律用区间分析证明非回绕乘法边界用缩放重写消除除法比较用Shl↔乘法的等价关系覆盖位移边界并全部受显式复杂度预算约束。它不替换位向量语义、不改变非恒等式的形状、不让求解器模型绕过回放验证最终让有界非线性 EVM 字恒等式在进入 SMT 求解器之前就有机会被直接证明。【免费下载链接】foundryFoundry is a blazing fast, portable and modular toolkit for Ethereum application development written in Rust.项目地址: https://gitcode.com/GitHub_Trending/fo/foundry创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考