aiwiki.page
中文

SMT-LIB

SMT-LIB 是一项国际倡议,为可满足性模理论求解器提供标准语言、逻辑理论和基准测试集。

16 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
可满足性模理论算法布尔可满足性问题Lisp(编程语言)类型系统一阶逻辑形式验证整数溢出SMT-LIB

SMT-LIB 是一项国际倡议,旨在为可满足性模理论(SMT)制定通用语言、理论规范和基准测试集。其中最广为人知的组成部分是 SMT-LIB 语言,它是一种标准化的文本接口,用于表达逻辑约束并与 SMT 求解器交互。这项倡议促进工具之间的互操作、实验的可复现性,以及对自动推理系统的系统性评估。它本身不是求解器,也不规定具体的求解算法。

目的与范围

SMT 求解器用于判断一个逻辑公式在指定背景理论下是否存在使其成立的解释;背景理论可以是整数算术、数组或固定位宽的位向量等。它通过赋予加法、比较和数组访问等运算以数学含义,扩展了布尔可满足性问题。

例如,当 xx 为整数时,约束 x>3x>3 与 x<5x<5 可以同时满足,但加入 x≠4x\neq4 后便不可满足。SMT 求解器根据这些表达式的算术含义进行推理,而不是把每个比较都视为互不相关的布尔变量。

SMT-LIB 对这一过程中的几个不同部分进行了标准化:

  • 表达式语言:用于表示项、公式、声明和命令。
  • 背景理论:规定内置的类及运算的含义。
  • 逻辑:确定允许使用的理论组合及对公式的限制。
  • 基准测试集:提供用于测试和比较求解器的问题。

这些组成部分各有用途。理论定义数学含义;逻辑定义允许处理的问题类别;脚本则通过一系列交互来指挥求解器。

语言与语义

项、类与公式

SMT-LIB 使用基于 S表达式的带括号前缀记法,这种记法在 Lisp编程语言中也很常见。加法写作 (+ x 1),比较写作 (< x 5)。分号用于引入注释,注释延续至行末。

该语言以多类逻辑框架为基础。类(sort)标识一个项所属的域,例如 Bool、Int 或 Real。类也可以带有参数:(_ BitVec 32) 表示 32 位位向量,而 (Array Int Bool) 表示以整数为索引、元素为布尔值的数组。这套类规则所起的作用类似于编程语言中的类型系统。

在现行的 SMT-LIB 2 框架中,公式是带等词的多类一阶逻辑中的布尔项。该语言包含布尔联结词、函数应用、条件表达式、局部绑定和量词。脚本还可以引入额外的类和函数符号。

例如:

(declare-const x Int)
(declare-fun f (Int) Int)

第一条命令引入一个值有待确定的整数常量。第二条命令引入一个从整数到整数的函数,但不提供其定义。这样的未解释函数必须像数学函数一样保持一致性,但除此之外,其解释仅受问题中的断言约束。

数学含义

SMT-LIB 区分数学域与机器层面的表示。Int 表示数学上的整数,而非固定位宽的机器整数类型。Real 表示数学上的实数,而非硬件浮点值。固定位宽算术和浮点运算使用各自独立的理论。

这种区别在形式验证中十分重要。采用整数编码并不会自动复现程序中的整数溢出。位向量编码可以表示模算术,而浮点理论则提供与 IEEE 754浮点运算标准相对应的运算。

定义中还有一些细节与常见的编程惯例不同。例如,通常的理论函数都是全函数,因此看似异常的输入不一定会导致运行时错误。某些运算在特定情况下被有意保留为不完全规定的状态,而不是指定唯一的结果。

脚本与求解器交互

SMT-LIB 脚本由一系列命令组成。常见命令包括:

命令 用途
set-logic 选择一个命名逻辑
set-option 配置标准选项或实现特有的选项
declare-sort、declare-fun、declare-const 引入符号
define-fun 为函数给出显式定义
assert 添加布尔约束
check-sat 检查当前断言的可满足性
get-model 请求一个满足断言的解释
push、pop 保存和恢复断言上下文
exit 结束会话

以下是一个完整示例:

(set-option :produce-models true)
(set-logic QF_LIA)

(declare-const x Int)
(assert (> x 3))
(assert (< x 5))

(check-sat)
(get-model)

(push 1)
(assert (distinct x 4))
(check-sat)
(pop 1)

(exit)

QF_LIA 表示无量词线性整数算术。第一次可满足性检查返回 sat,模型给出赋值 x=4x=4。在压入的上下文中,新增断言排除了这个值,因此第二次检查返回 unsat。pop 命令会移除这条临时断言。

结果与诊断输出

可满足性检查可能返回:

  • sat:存在满足这些断言的解释。
  • unsat:在选定的语义下,不存在满足这些断言的解释。
  • unknown:求解器尚未确定上述任一结论。

unknown 并不是第三种数学真值,而是反映求解过程或其执行受到的限制。错误和不受支持的命令与这些可满足性结果是分开处理的。

根据已启用的选项和求解器的支持情况,脚本可以请求模型、特定表达式的值、证明或不可满足核。不可满足核给出断言的一个子集,该子集已足以导致不可满足;它不一定是满足这一条件的最小子集。

该标准还支持通过 check-sat-assuming 在临时假设下进行检查。这一功能与断言栈配合,可以实现增量求解,使应用程序能够连续提出一系列相关问题,而不必在每次查询时重新启动求解器。

理论与逻辑

SMT-LIB 将可复用的理论定义与命名逻辑分开。主要的理论类别包括:

  • 核心逻辑:包括布尔值、相等关系和条件表达式。
  • 整数与实数算术:包括算术运算和序关系。
  • 固定位宽位向量:包括模算术、按位运算、截取和拼接。
  • 数组:通过读取和更新索引位置上的值等操作来刻画。
  • 浮点算术:包含明确的格式和舍入模式。
  • 字符串与序列:包括拼接、求长度等操作。
  • 代数数据类型:用于表示由构造器构建的结构化值。

理论会不断演进,不同求解器发行版及语言版本对理论的支持也有所不同。

一种逻辑组合了选定的功能,并可能限制其使用方式。常见示例如下:

逻辑 主要范围
QF_UF 含未解释函数的无量词公式
QF_LIA 无量词线性整数算术
QF_LRA 无量词线性实数算术
QF_BV 无量词固定位宽位向量
QF_AUFBV 无量词数组、未解释函数和位向量
QF_NIA 无量词非线性整数算术

这里,QF 意为“无量词”。线性算术对乘法加以限制,不允许两个依赖变量的表达式相乘。

选择逻辑不只是为了说明问题:它还传达了预期问题所属的逻辑片段,并可能影响求解器配置及其对输入是否符合限制的检查。求解器可能接受所声明片段之外的构造,但这种宽容行为并不是该语言可移植的特性。

不同片段在可判定性和计算复杂性方面也有所差异。语法标准化并不能使所有可表达的问题都变得可判定。例如,无量词非线性整数算术在一般情况下是不可判定的。

历史与基准测试基础设施

SMT-LIB 倡议始于 2003 年,当时 SMT 工具尚缺乏足够统一的语言和共享的基准测试基础设施。早期工作为公式建立了通用表示,并围绕理论和逻辑组织基准测试问题族。

2010 年推出的 SMT-LIB 2 确立了一种面向命令的语言,支持与求解器进行交互式会话。后续修订扩展并澄清了语言和理论规范。版本之间的区别很重要,因为某一修订版或求解器发行版支持的构造,在另一个版本中可能不可用。

基准测试库既包含来自实际应用领域的问题,也包含生成的或专门构造的实例。基准测试文件可以附带来源、类别、预期可满足性状态以及说明性注释等信息。

SMT-LIB 与一年一度的 SMT 求解器竞赛 SMT-COMP 密切相关。该竞赛使用标准化输入和基准测试集,在规定条件下评估各个实现。不过,SMT-LIB 与 SMT-COMP 是两个不同的项目:前者提供规范和共享资源,后者负责组织评测并制定竞赛规则。

应用

SMT-LIB 被广泛用作约束生成工具与求解器之间的交换格式。应用领域包括软硬件验证、模型检测、符号执行、调度和自动定理证明。

验证工具可以将程序的一项性质转化为逻辑公式,使公式的满足赋值对应于反例。如果求解器报告 sat,模型可能有助于重建一条违反该性质的执行路径。如果报告 unsat,则说明在该编码及其假设范围内不存在反例。

文本格式也有助于调试和复现。工具可以保存提交给求解器的确切约束,以便检查、精简,或使用另一种实现进行测试。求解器直接提供的应用程序编程接口可能支持更丰富的集成方式,但 SMT-LIB 提供了一个相对独立于具体实现的交换层。

可移植性与局限

标准化的语法和语义提高了可移植性,但并不意味着所有实现都可以互换。求解器在支持的逻辑、资源消耗、模型呈现方式、证明格式和扩展命令方面各有不同。优化目标和专门的推理功能可能依赖求解器特有的接口,而非通用标准。

等价的编码也可能导致截然不同的求解时间。变量的表示方式、量词的使用,以及整数算术与位向量算术之间的选择,都可能显著影响搜索过程。因此,基准测试结果反映的是特定工作负载和配置下的性能,而不是普遍的优越性。

最后,求解器的结果仅适用于提交给它的公式。一个可靠的 unsat 结果,本身并不能证明对程序、电路或物理系统的建模是正确的。从原始问题到 SMT 约束的转换,仍然是验证论证中需要单独处理的部分。