Rust 形式化验证工程实战——从 Kani 模型检查器到 Verus 定理证明

---

在系统编程领域，"内存安全"并不等同于"逻辑正确"。Rust 的所有权模型可以杜绝 use-after-free、数据竞争等内存安全问题，但当我们面对一个并发无锁队列的状态机不变量、一段加密协议的关键属性、或者一个金融交易引擎的结算正确性时，编译器静态检查的边界就到了尽头。

形式化验证——用数学方法证明程序满足其规约——从学术殿堂走向产业实践的脚步正在加速。在 Rust 生态中，Amazon 主导的 Kani 和 Microsoft/Verus 团队推动的 Verus 代表了两种互补的技术路径。本文将深入探讨两者的理论基础、工程实战以及在生产环境中的落地方案。

---

一、形式化验证的两个基本范式

在进入工具链之前，我们需要理解底层的技术差异，因为这直接决定了工具的适用边界。

1.1 Bounded Model Checking（有界模型检验）

Kani 基于 CBMC（C Bounded Model Checker）的核心思想：

• 原理：将程序中的循环展开 k 次，将所有路径约束编码为一阶逻辑公式，然后交给 SAT/SMT 求解器判定是否存在反例
• 优势：全自动，无需手写循环不变量；能找到具体的反例 trace
• 局限：验证覆盖受 bound 限制，对无限状态空间（如递归、无界堆分配）需要人工辅助

1.2 Deductive Verification（演绎验证）

Verus 基于斯坦福大学（Nikolaj Bjorner 团队）的 SMT-based deductive verification 路线：

• 原理：开发者在代码中标注前置条件（requires）、后置条件（ensures）和循环不变量（invariant），工具将其编码为验证条件（Verification Condition），用 Z3 SMT 求解器证明
• 优势：可以验证无限状态空间、复杂的数据结构不变量、并发协议的全局性质
• 局限：需要人工编写规约（specification），对某些非线性算术理论判定不完全

---

二、Kani：零门槛的有界验证

2.1 安装与上手

Kani 作为一个编译器后端插件使用，当前支持 Rust toolchain 的特定版本（基于 nightly 分支）。

# 安装 Kani
cargo install --locked kani-verifier

对于 Cargo 项目，设置 Kani 特定的 toolchain
cargo kani setup

2.2 实战：验证无界队列的溢出检测

假设我们实现了一个环形缓冲区（Ring Buffer），需要验证其 push 操作不会越界：

// src/ring_buffer.rs
pub struct RingBuffer {
    buffer: Vec<u32>,
    head: usize,
    tail: usize,
    size: usize,
}

impl RingBuffer {
    pub fn new(capacity: usize) -> Self {
        RingBuffer {
            buffer: vec![0; capacity],
            head: 0,
            tail: 0,
            size: capacity,
        }
    }

    pub fn push(&mut self, value: u32) -> bool {
        if self.head == self.tail && self.buffer[self.head] != 0 {
            false // 缓冲区已满
        } else {
            self.buffer[self.head] = value;
            self.head = (self.head + 1) % self.size;
            true
        }
    }

    pub fn pop(&mut self) -> Option<u32> {
        if self.buffer[self.tail] == 0 {
            None
        } else {
            let val = self.buffer[self.tail];
            self.buffer[self.tail] = 0;
            self.tail = (self.tail + 1) % self.size;
            Some(val)
        }
    }
}

编写 Kani harness：

// kani_harness.rs
#[cfg(kani)]
mod verification {
    use super::*;

    #[kani::proof]
    fn verify_push_no_overflow() {
        let capacity: usize = kani::any();
        kani::assume(capacity > 0 && capacity <= 256);

        let mut rb = RingBuffer::new(capacity);

        // Kani 会自动探索所有可能的输入序列
        for _ in 0..10 {
            let val: u32 = kani::any();
            let _ = rb.push(val);

            // 断言：head 始终在合法范围内
            assert!(rb.head < capacity);
        }
    }

    #[kani::proof]
    fn verify_push_pop_roundtrip() {
        let capacity: usize = kani::any();
        kani::assume(capacity >= 1 && capacity <= 32);

        let mut rb = RingBuffer::new(capacity);
        let val: u32 = kani::any();

        if rb.push(val) {
            let popped = rb.pop();
            assert!(popped.is_some());
            assert_eq!(popped.unwrap(), val);
        }
    }
}

运行验证：

cargo kani --harness verify_push_no_overflow

当 Kani 发现反例时，它会生成可单步调试的 trace：

VERIFICATION:- FAILED
Checkpoint: push (src/ring_buffer.rs:16)

attempt to subtract with overflow: head + 1 when head = usize::MAX

2.3 高级技巧：循环展开与假设裁剪

对于复杂的数据结构，一个常见问题是路径爆炸。Kani 提供了一些控制手段：

#[kani::proof]
fn verify_sorting_algorithm() {
    let len: usize = kani::any();
    // 限制输入规模，避免状态空间爆炸
    kani::assume(len >= 2 && len <= 8);

    let mut arr: Vec<i32> = vec![0; len];
    for i in 0..len {
        arr[i] = kani::any();
    }

    // 执行排序
    my_sort(&mut arr);

    // 验证输出有序
    for i in 1..len {
        assert!(arr[i-1] <= arr[i]);
    }
}

kani::any() 在 Kani 语义下具有全称量化意义——它会探索所有可能的值，而不像模糊测试那样随机采样。 ---

三、Verus：工业级定理证明

3.1 语言哲学：Specification as Code

Verus 的核心设计哲学是规约即代码——specification 与实现共享同一套语法和类型系统。这意味着你可以用 Rust 表达式直接书写数学规约，无需学习额外的规约语言（如 Dafny 的 special 语法或 F\* 的 effect 系统）。

// 使用 Verus 的规约语言
vested! {

spec fn sorted_range(s: &Seq<int>, start: int, end: int) -> bool {
    forall|i: int, j: int| 
        0 <= i <= j < end - start 
        ==> s[i] <= s[j]
}

spec fn is_permutation(original: &Seq<int>, result: &Seq<int>) -> bool {
    original.len() == result.len()
    && exists|perm: Map<int, int|> 
        perm.dom().contains_all(original.to_set()) &&
        result.to_set() == original.to_set()
}

}

3.2 实战：验证并发 BTreeMap 的不变性

我们将验证一个简化版的手写无锁 B+Tree 操作的"分裂正确性"——即分裂操作完成后，所有叶子节点仍保持有序，且没有数据丢失。

#![allow(unused_imports)]
use vstd::prelude::*;

vested! {

pub struct Node {
    keys: Seq<int>,
    children: Seq<ptr<Node>>,
    is_leaf: bool,
}

impl Node {
    pub spec fn is_sorted(self) -> bool {
        if self.is_leaf {
            sorted_range(&self.keys, 0, self.keys.len() as int)
        } else {
            sorted_range(&self.keys, 0, self.keys.len() as int)
            && forall|i: int| 0 <= i < self.children.len() as int
                ==> self.children[i].is_sorted()
        }
    }

    pub spec fn key_count(self) -> int {
        self.keys.len() as int
    }

    /// 规约：分裂后的两棵子树必须满足：
    /// 1. 两者都保持有序
    /// 2. 左子树的所有 key <= 右子树的所有 key
    /// 3. 总 key 数不变
    pub fn split(&mut self, out_left: &mut Node, out_right: &mut Node)
        requires
            old(self).is_sorted(),
            old(self).key_count() > 1,
            old(self).is_leaf,
        ensures
            out_left.is_sorted(),
            out_right.is_sorted(),
            out_left.key_count() + out_right.key_count() == old(self).key_count(),
            forall|i: int| 0 <= i < out_left.key_count() 
                ==> out_left.keys[i] == old(self).keys[i],
            forall|j: int| 0 <= j < out_right.key_count() 
                ==> out_right.keys[j] == old(self).keys[(out_left.key_count() + j) as int],
            out_left.key_count() > 0,
            out_right.key_count() > 0,
    {
        ... // 实现细节
    }
}

}

3.3 Verus 的选择性验证策略

Verus 支持一种被称为 "Sleq" (specification-level equality) 的优化技术，允许开发者在关键验证路径上分配更多资源，而在辅助逻辑上使用轻量级近似：

// 对关键 safety property 使用完整 Verus 验证
#[verifier::spec] fn critical_safety_condition(...) -> bool { ... }

// 对性能要求高的辅助逻辑使用 Kani-bound 检查
#[verifier::external_body]
fn performance_helper(...) { / 通过模糊测试 + Kani 覆盖 / }

这种"选择性深度验证"策略在实际工程中至关重要——你不会对日志格式化函数使用定理证明，但对涉及资金流转的核心逻辑则需要完全形式化。 ---

四、Kani vs Verus：工程选型决策框架

维度	Kani	Verus
学习曲线	低（几乎零标注）	中（需学习规约语法）
验证范围	有界路径 + 局部不变量	无限状态空间 + 全局性质
自动化程度	高（全自动探索）	中（需循环不变量）
错误报告	具体反例 trace	不可满足的 VC（需人工分析）
并行/并发验证	有限支持	强大（专门的并发推理规则）
MSRV 兼容	较严格的 nightly 限制	较宽松的 nightly 分支
生态系统成熟度	中等（Amazon 强力投入）	中等（Microsoft 团队主导）

推荐策略：

1. 新功能开发阶段：用 Kani 的 kani::proof 快速捕获边界条件错误——相当于"智能穷举测试"
2. 核心安全关键模块：用 Verus 编写完整规约，尤其涉及并发协议、加密原语、状态机正确性
3. 遗留代码迁移：先写 Kani harness 锁定当前行为，再用 Verus 逐步引入形式化规约

---

五、CI/CD 集成与团队实践

5.1 增量验证管道

形式化验证的计算成本不可忽视。一个实用的策略是分层验证：

# .github/workflows/formal-verification.yml
jobs:
  # Tier 1: Kani 快速验证（5-10 分钟）
  kani-bounded:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v4
      - uses: model-checking/kani-github-action@v1
      - run: cargo kani --tests --default-unwind 16

  # Tier 2: Verus 关键模块验证（15-30 分钟）
  verus-core:
    runs-on: ubuntu-latest
    if: github.ref == 'refs/heads/main' || contains(github.event.head_commit.message, '[verify]')
    steps:
      - uses:谁家/actions/checkout@v4
      - run: cargo verify --features verification
      - name: 验证报告归档
        uses: actions/upload-artifact@v4
        with:
          name: verus-reports
          path: target/verification-results/

  # Tier 3: 全量验证定时任务（每周）
  full-verification:
    runs-on: ubuntu-latest
    schedule:
      - cron: '0 2   0'  # 每周日凌晨 2 点
    steps:
      - run: cargo kani --workspace --default-unwind 32
      - run: cargo verify --all-features

5.2 团队协作中的规约评审

形式化验证不仅仅是技术工具，更是一种思维方式的转变。我们建议团队建立以下实践： 1. Spec-First 开发：先写 spec fn 定义函数行为，再实现函数体。这在 API 设计阶段就能捕获歧义。 2. 规约评审（Spec Review）：规约错误的危害大于实现错误——一个过于宽松的 spec 会让错误代码"通过"验证。规约本身必须经过严格的人工审查。 3. 验证覆盖矩阵：

模块	验证级别	工具	触发条件
协议状态机	完整归纳证明	Verus	每次提交
序列化/反序列化	Roundtrip 性质	Kani	每次提交
内存分配器	安全 + 活性	Verus	每日定时
密码学原语	恒定时间保证	Kani + dudect	每次提交
并发队列	线性化性质	Verus	每次提交

5.3 应对 SMT 求解器的"不可判定性"

SMT 求解器在遇到非线性算术、某些理论组合时可能返回 unknown 而不是 sat/unsat。实用的应对策略：

// 策略1：限制数值范围到可实现的理论片段
#[requires(x >= 0x1000 && x < 0x10000)]  // 避免 u64 范围
fn allocate_aligned(size: usize) { ... }

// 策略2：使用有界整数类型（vstd::prelude 提供）
fn compute_discount(rate: u8, amount: u32) -> u64  // 使用 u8 而不是 usize，减少求解空间

// 策略3：对复杂数学运算使用 Verus 内置引理
lemma_mul_upper_bound(x: int, y: int, max: int)
    requires 0 <= x <= max, 0 <= y <= max
    ensures x  y <= max  max

---

六、展望：形式化验证的下一个前沿

6.1 LLM 辅助规约生成

2025-2026 年的一个新兴方向是用 LLM 自动生成 verification harness 和 loop invariant。Amazon 团队已经展示了 Kani + 大语言模型结合可以将验证效率提升 3-5 倍。核心思路：

开发者代码 → LLM 生成候选 invariant → Kani/Verus 验证 → 
若失败，LLM 基于反例 trace 修正 invariant → 循环直至通过

这类似于人类证明助手中的"tactic"自动搜索，但利用了大语言模型的语义理解能力。

6.2 验证驱动的 Refactoring

传统重构依赖测试覆盖率保障正确性——但测试只能证明存在性（"这个场景能工作"），无法证明普遍性（"所有场景都能工作"）。形式化验证将重构的安全性从"基于测试的统计信心"提升到"基于数学证明的逻辑保证"。

// 重构前：基于测试的信心
#[test]
fn test_merge() { / 测试几个典型情况 / }

// 重构后：基于证明的信心
#[requires(...)]
#[ensures(is_permutation(&old(input), &result))]
fn merge(input: Vec<...>) { ... }

---

七、总结

Rust 的形式化验证生态正在从"学术界玩具"向"工业级基础设施"快速演进。Kani 提供了几乎零上手门槛的有界验证路径，适合团队快速获得验证收益；Verus 虽然学习曲线更陡，但其验证表达能力足以覆盖并发协议、安全关键不变量等最复杂的场景。 对于希望在项目中引入形式化验证的团队，我的建议是：从 Kani 的 kani::proof 开始，每周固定时间审查验证报告中发现的 bug，逐步建立团队对形式化方法的信任；然后在最关键的 10% 代码上投入 Verus 形式的规约验证。 形式化验证不是万能药——它不能替代架构设计、代码审查和系统测试。但在正确的地方使用正确的方法，它能将你的软件从"大概率正确"提升到"数学上正确"，这通常是区分可靠系统与灾难性故障的最后一道防线。 --- 本文涉及的代码示例基于 Kani 0.56+ 和 Verus 2025.10 版本，完整可运行仓库见作者 GitHub。