🤖 AI

Approximate SMT Counting Beyond Discrete Domains

本文提出了名为 pact 的混合公式 SMT 模型计数器，它利用基于哈希的近似计数方法，通过优化哈希函数将 SMT 求解器调用次数控制在投影变量的对数级别，从而在理论保证下显著提升了混合域模型计数的性能。

原作者： Arijit Shaw, Kuldeep S. Meel

发布于 2026-03-02

📖 1 分钟阅读☕ 轻松阅读

原作者： Arijit Shaw, Kuldeep S. Meel

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文介绍了一个名为 pact 的新工具，它就像是一个超级高效的“数数机器”，专门用来解决一种非常复杂的数学问题：混合逻辑公式的模型计数。

为了让你轻松理解，我们可以把这篇论文的核心内容想象成一场**“在巨大的迷宫中寻找出口”**的游戏。

1. 背景：什么是“混合迷宫”？

想象一下，你面前有一个巨大的迷宫（这就是SMT 公式）。

普通的迷宫：只有“左”或“右”两种选择（这是离散变量，比如开关是开还是关）。
连续的迷宫：你可以向任何方向走，甚至可以在墙上滑翔（这是连续变量，比如温度、速度、时间）。
混合迷宫：这个迷宫既包含“开关”（离散），也包含“滑翔”（连续）。

我们要解决的问题是：在这个复杂的混合迷宫里，有多少种不同的**“开关组合”**（即离散变量的状态）能让我们找到出口？

难点：因为迷宫里还有“滑翔”部分，路径是无限多的，直接数数是不可能的。我们只关心“开关”有多少种合法的组合。
现状：以前的工具（比如论文里提到的 CDM）就像是一个拿着小本本、一步一步慢慢数的人。面对稍微大一点的迷宫，他们数到一半就累晕了（超时），或者根本数不过来。

2. 主角登场：pact 是什么？

pact 是一个聪明的“估算大师”。它不打算笨拙地数每一个出口，而是使用一种叫**“哈希（Hashing）”的魔法技巧来“切蛋糕”**。

核心魔法：切蛋糕与抽样

想象你要知道一个巨大的蛋糕（所有可能的解）里有多少块（解的数量），但你不想把整个蛋糕切开数。

撒网（哈希函数）：pact 会往蛋糕上撒一张巨大的网（哈希函数）。这张网把蛋糕切成了很多小块（分区）。
抽样：它只去数其中一小块网里的蛋糕块有多少。
推算：如果这一小块里有 10 块蛋糕，而网把蛋糕切成了 1000 块，那么它就能估算出总共有 $10 \times 1000 = 10,000$ 块。

pact 的聪明之处在于：

它不是随便切，而是用数学保证切得大小均匀。
它会反复切几次（使用不同的网），取一个中位数，这样就算某一次切歪了，最终结果依然非常准确。
它承诺：只要给它足够的时间，它算出来的数字误差不会超过 80%（ $\epsilon=0.8$ ），而且 80% 的情况下是准的（ $\delta=0.2$ ）。

3. 三种不同的“切网”方式

pact 尝试了三种不同的切网工具（哈希函数家族），就像厨师用不同的刀：

XOR 刀 (pactxor)：这把刀专门切“开关”（位向量）。它非常锋利，而且利用了现代计算机里专门处理“异或”运算的硬件加速。
- 比喻：就像用激光刀切豆腐，又快又准。
乘法刀 (pactprime)：用乘法取余数来切。
移位刀 (pactshift)：用移位操作来切。

结果：实验发现，XOR 刀 (pactxor) 是最快的，也是最有效的。

4. 战绩如何？（实验结果）

论文团队拿来了 3,119 个 不同的迷宫（测试案例）来比赛：

旧冠军 (CDM)：只成功数完了 83 个迷宫。剩下的都因为太复杂而放弃了。
新冠军 (pact)：成功数完了 456 个迷宫！
- 这意味着 pact 的能力是旧工具的 5 倍多！
- 而且，pact 算出来的结果非常准，平均误差只有 3.3%，远好于它承诺的 80% 误差上限。

5. 这有什么用？（应用场景）

别以为这只是数学游戏，pact 能解决很多现实世界的难题：

自动驾驶的安全：想象一辆自动驾驶汽车。我们需要知道有多少种“传感器故障 + 天气变化”的组合会导致车祸？pact 可以帮我们快速估算出这些危险组合的数量，从而评估系统有多安全。
软件漏洞检测：一个软件里有多少种“输入组合”会导致程序崩溃？pact 能帮我们量化风险。
信息泄露：一个密码系统里，有多少种输入能让黑客猜出密码？pact 能算出这个概率。

总结

这篇论文介绍了一个叫 pact 的新工具，它像是一个**“聪明的抽样侦探”**。

面对那些既包含“开关”又包含“连续数值”的超级复杂迷宫，以前的工具只能数很少几个就放弃了。而 pact 通过**“切蛋糕”（哈希分区）和“聪明抽样”**的方法，不仅能数出以前数不了的大量案例，而且算得又快又准。

这就好比以前我们要数清一个体育场里有多少观众，只能一个个点名（太慢）；现在 pact 发明了“随机拍几张照片，数照片里的人数，然后乘以倍数”的方法，瞬间就能给出一个非常靠谱的答案。这对于保障汽车安全、软件稳定和信息保密都有着巨大的意义。

论文技术总结：Beyond Discrete Domains 的近似 SMT 计数 (pact)

1. 研究背景与问题定义

背景：
Satisfiability Modulo Theories (SMT) 求解器在自动化推理领域取得了巨大进展，能够处理离散（如位向量、整数）和连续（如实数、浮点数）域上的复杂公式。然而，现有的模型计数（Model Counting）技术主要集中在离散域（如布尔公式或纯位向量公式）。对于混合 SMT 公式（Hybrid SMT Formulas，即同时包含离散和连续变量的公式），尤其是需要投影到离散变量（Projected Counting）的场景，现有的计数方法面临巨大的可扩展性挑战。

核心问题：
给定一个混合 SMT 公式 $F$ 和一个离散投影变量集 $S$ ，如何高效且准确地估算满足 $F$ 的解在 $S$ 上的投影数量 $|Sol(F)\downarrow S|$ ？

挑战： 连续变量的存在使得解空间无限，直接枚举不可行；而现有的基于位爆破（Bit-blasting）的方法仅适用于离散变量，无法直接处理混合域。
目标： 开发一种具有理论保证的近似模型计数器，能够在合理的时间内处理大规模混合 SMT 实例。

2. 方法论：pact 框架

作者提出了 pact，这是一个基于哈希近似模型计数（Hashing-based Approximate Model Counting）的工具，专门用于混合 SMT 公式的投影计数。

2.1 核心算法流程

pact 的核心思想是利用哈希函数将巨大的解空间划分为大小相等的“单元格”（Cells），通过枚举小单元格内的解来估算总数。

参数设置： 根据用户指定的误差容忍度 $\epsilon$ 和置信度 $\delta$ ，计算阈值 thresh（单元格最大解数）和迭代次数 numIt。
哈希划分：
- 生成一组成对独立（Pairwise Independent）的哈希函数 $H$ 。
- 将哈希约束 $h(x) = \alpha$ 添加到原公式 $F$ 中，形成 $F \land H$ 。
- 利用 SMT 求解器（CVC5）检查 $F \land H$ 的解数量是否小于 thresh。
自适应搜索（Galloping Search）：
- 使用 NextIndex 子程序通过“跳跃搜索”快速找到合适的哈希约束数量，使得解空间被划分到目标大小范围内。
- 如果解空间过大，增加哈希约束；如果过小，则调整。
FixLastHash 优化：
- 当使用非 XOR 哈希（如 $H_{prime}$ 或 $H_{shift}$ ）时，如果最后一步划分导致解数刚好在阈值附近，算法会调用 FixLastHash 子程序，移除最后一个哈希并尝试更精细的划分，以获得更精确的估计。
- 对于 $H_{xor}$ 哈希，由于其天然将空间二分，无需此步骤。
统计与输出：
- 重复上述过程 numIt 次，收集每次的估算值。
- 返回这些估算值的中位数作为最终结果，以满足 $(\epsilon, \delta)$ 的理论保证。

2.2 哈希函数家族

pact 实现了三种不同的哈希函数家族，以适应不同的 SMT 理论特性：

$H_{xor}$ (Bitwise XOR): 基于位操作，利用 CryptoMiniSat 的 XOR 推理能力，计算开销小，但划分粒度固定（二分）。
$H_{prime}$ (Multiply-mod-prime): 基于乘法取模，适用于位向量，可灵活调整划分粒度，但涉及模运算，SMT 求解开销较大。
$H_{shift}$ (Multiply-shift): 基于乘法移位，同样适用于位向量，性能介于两者之间。

2.3 实现细节

底层求解器： 基于 CVC5 构建，利用其增量求解（Incremental Solving）能力，提高多次查询的效率。
切片技术（Slicing）： 针对任意宽度的位向量，将其切分为符合哈希函数定义域宽度的小块进行处理。
支持理论： 支持多种 SMT 理论组合，包括线性/非线性实数、浮点算术、数组、位向量等（如 QF ABVFP, QF BVFPLRA 等）。

3. 主要贡献

首个可扩展的混合 SMT 投影计数器： 提出了 pact，解决了混合域 SMT 公式投影计数的可扩展性难题。
理论保证： 证明了 pact 返回的计数值 $c$ 满足 $Pr[\frac{c}{1+\epsilon} \leq Est \leq (1+\epsilon)c] \geq 1-\delta$ 。
高效的查询复杂度： 算法对投影变量数量 $|S|$ 仅进行 $O(\log(|S|))$ 次 SMT 求解器调用，显著优于线性或指数级方法。
多样化的哈希策略： 深入研究了不同哈希函数家族（XOR, Prime, Shift）在混合 SMT 环境下的性能权衡，发现 XOR 哈希在特定场景下表现最佳。
开源工具： 发布了基于 CVC5 的开源工具，支持多种 SMT-Lib 标准理论。

4. 实验结果

作者在 3,119 个来自 SMT-Lib 2023 的基准测试实例上进行了评估。

求解能力对比：
- pact (使用 $H_{xor}$ ): 成功解决了 456 个实例。
- 现有最先进工具 (CDM [26]): 仅解决了 83 个实例。
- 提升： pact 的求解实例数量是 CDM 的 5.5 倍 以上。
不同哈希函数的表现：
- $H_{xor}$ 表现最佳（456 个），其次是 $H_{shift}$ (40 个) 和 $H_{prime}$ (33 个)。
- 原因分析： $H_{xor}$ 利用了求解器原生的 XOR 推理能力，且避免了复杂的乘法和模运算，降低了 SMT 求解的复杂度。
精度验证：
- 在 64 个已知精确解的实例上，pact 的平均相对误差仅为 3.3% ( $H_{xor}$ )，远低于理论设定的 $\epsilon=0.8$ 。
- 最大误差为 0.26，表明实际性能显著优于理论最坏情况。
运行时间： 通过 Cactus 图显示，pact 在解决大量实例时，运行时间显著短于 CDM。

5. 意义与应用

科学意义：

填补了混合 SMT 公式模型计数领域的空白，证明了基于哈希的近似计数方法可以成功扩展到连续与离散混合的领域。
为处理高维、混合域的组合优化和验证问题提供了新的理论框架和实用工具。

实际应用价值：
论文列举了四个关键应用场景，证明了该技术的必要性：

汽车网络物理系统 (CPS) 的鲁棒性分析： 量化潜在的攻击向量数量。
关键软件的可达性分析： 统计控制流图中满足特定违规条件的路径数量。
定量软件验证： 评估断言失败的具体输入数量，而不仅仅是检测是否存在错误。
信息流量化： 测量工业软件中的信息泄露程度。

总结：
pact 通过创新的哈希策略和高效的 SMT 求解器集成，成功克服了混合 SMT 模型计数的可扩展性瓶颈。其开源工具和显著的性能提升（相比现有最先进工具解决了 5 倍多的实例），使其成为软件验证、安全分析和系统可靠性评估中极具价值的工具。未来的工作将包括实现整数投影变量支持以及开发更专用的位向量哈希推理引擎。