符号状态探索在符号模型检查中的工作原理

Question

以下algorithm is a rough sketch of model checking with Computational Tree Logic (CTL):

表示：

The model-checking problem for CTL is to verify for a given transition system TS and CTL formula Φ whether TS |= Φ... The basic procedure for CTL model checking is rather straightforward:

the set Sat(Φ) of all states satisfying Φ is computed recursively, and

it follows that TS |= Φ if and only if I ⊆ Sat(Φ) where I is the set of initial states of TS...

The recursive computation of Sat(Φ) basically boils down to a bottom-up traversal of the parse tree of the CTL state formula Φ.

所以你基本上（根据我的理解），你为系统提供了一个 CTL 公式 Φ，它是一个解析树，然后它搜索状态，并通过 CTL 解析树，并检查是否有任何状态满足Φ.

问题是：

在 Sat(Φ) 方法中，大致发生了什么（符号的东西）。他们在下面说 (2)，其中 S 是状态，A 是原子命题。想知道他们实际上是如何检查状态的，考虑到该程序实际上并不是运行。它是（至少我认为）符号模型检查。想知道是否可以大致解释状态检查的工作原理。似乎某种 input generation 必须发生，但与此同时我在想也许它不应该发生。

对我来说很难理解的原因是这样的。假设其中一个断言是针对函数 addTricky(x, y) 的，它是这样实现的：

function addTricky(x, y) {
  if (y >= 1) return 3
  return x + y
}

然后我会有一个 布尔表达式 在一些逻辑中说 "before addTricky : z = 0. after z = addTricky(x, y) : y >= 1 -> z = 3 ; y < 1; z = x + y".

基本上是想解决模式的问题。如果 Sat(Φ) 基本上是在做我刚刚在那个布尔表达式中所做的事情，我想知道它是否曾经 calls/invokes 函数 addTricky，或者它是否可以以某种方式象征性地完成这一切。我还不知道它是如何工作的，想知道是否可以稍微解释一下符号执行工作原理的基础知识。对我来说，我一直在想象它会进行某种单元测试，例如插入 addTricky(1, 1) 并检查所有可能性。也许那是 "explicit state exploration" 与符号探索，不确定。

非常感谢您的帮助！

(1) For each node of the parse tree, i.e., for each subformula Ψ of Φ, the set Sat(Ψ) of states is computed for which Ψ holds.

(2) Sat(a) = {s ∈ S | a ∈ L(s)}, for any a ∈ A

Answer 1

我认为您的问题分为两个部分：1) 如何从软件功能过渡到过渡系统以及 2) 过渡系统如何用于检查满意度。

1) 转换系统基本上是有限状态自动机的扩展。如果你有一个像你描述的功能，你首先需要把它转换成一个过渡系统。例如，这可以通过为代码的每个可执行行引入状态，并根据代码的条件在这些状态之间进行转换来完成。在转换系统级别，您没有函数调用的概念，因此您需要在翻译过程中注意这一点，例如，通过内衬函数定义。此步骤与您验证转换系统的方式无关。正如您想象的那样，这会导致相当大的过渡系统。

还有其他不基于转换系统的方法模拟程序的执行并沿途收集符号约束。符号执行就是这样一个例子。

2) 假设您内联了 addTricky 函数并按照这些行得到了一些东西

L0: z=0
    if (y>=1)
L1:     z=3
    else
L2:     z=x+y

一个可能的 TS 是：

(L0: z=0) --[y >= 1]--> (L1: z=3) 
    |
  [y<1]
   \/
(L2: z=x+y)

您有 3 个可执行语句，这将导致一个 TS，其符号状态 (S) 为：

 L0: Z=0; X=?; Y=?
 L1: Z=3; X=?; Y>=1
 L2: Z=X+Y; X=?; Y<1

在哪里？表示任何值。这种方法的强大之处在于，您可以在单个符号状态中紧凑地表示 X 和 Y 的所有值。

符号状态探索在符号模型检查中的工作原理

How the Symbolic State Exploration works in Symbolic Model Checking

algorithm

logic

model-checking

formal-verification