在 Promela LTL 语句中引用以前的状态

Question

我刚开始使用 Promela，但在表达一些 LTL 公式时遇到问题。

一个例子是下面的 sequence 我想断言的值是单调递增的。直觉上我想写 在下一个状态下，序列 >= 其先前的值 ，但是通过文档查看，我没有找到表达这一点的方法。有没有表达这种公式的方法？

byte sequence = 0;
ltl p0 { [] sequence >= prev(sequence) }
... processes that manipulate sequence ...

假设可以表达上面sequence的单调递增属性，我想知道是否有通配符数组索引的语法。和上面的例子类似，我直觉上想引用之前所有的索引条目。

byte values[N];
byte index = 0;
ltl p1 { values[0..index-1] are monotonically increasing }
... processes ...

非常感谢您的帮助。 Promela 看起来真的很棒 :)

Answer 1

据我所知，

单调非递减序列。

Linear Temporal Logic 有一个 X 运算符，它允许一个人表达一个属性，它指的是 布尔条件 保持在 下一个状态，相对于前一个状态。

但是，不能在 LTL 公式中直接比较当前状态的整数值与下一状态的值，因为X 评估为布尔值。

理论上，可以做的是通过位爆破将整数上的<=运算符编码为布尔值属性，例如通过巧妙地使用模运算符或按位运算 （对于无符号变量应该不会太难） 和 位到位 对应布尔值的比较 （见最后注释）.

然而，从建模的角度来看，最简单的方法是使用 prev_value 变量丰富您的模型，并简单地检查每个状态下属性 prev_value <= cur_value 是否成立。请注意，在这种情况下，您应该使用 d_step 命令将两个值分配组合在一起，以便将它们合并在一个没有中间转换的状态中，例如

...
byte prev_value;
byte cur_value;
...
d_step {
    prev_value = cur_value;
    cur_value = ... non-blocking function ...
}

否则，与 prev_value 到 cur_value 相关的 不变式属性 可能会导致在相应的 自动机上被破坏 对于某些状态 s_i。 （注意：这实际上不会妨碍对您感兴趣的特定 LTL 属性的验证，但它可能是其他公式的问题）

通配符索引。

如果我没理解错的话，你要表达一个属性s.t。 -- 在每个状态中-- 只有从 0 到 index-1 的内存位置需要 单调非递减 ，其中 index 是可以改变值的变量（任意？）.

这样的属性的结构应该是：

ltl p1 {
    [] (
        ((1 <= index) -> "... values[0] is monotonically non-decreasing ...") &&
        ((2 <= index) -> "... values[1] is monotonically non-decreasing ...") &&
        ((3 <= index) -> "... values[2] is monotonically non-decreasing ...") &&
        ...
        ((N <= index) -> "... values[N-1] is monotonically non-decreasing ...")
    )
}

我相信您问题的答案是否。但是，我建议您将 macros 用于 C 预处理器 以简化属性的编码并避免一遍又一遍地编写相同的内容。

注：

让我们采用 curr_int 和 next_int 0-1 整数 变量 s.t。 next_int等于curr_int在下一个状态下的值（又名，curr_int是next_int的前一个值），和一个 curr 布尔变量 s.t。 curr 是 true 当且仅当 curr_int 等于 1.

然后，根据 LTL 语义，X curr 是 true 当且仅当 curr_int (next_int)在下一个(当前)状态下等于1。

考虑以下 truth-table 状态 s_i:

curr_int | next_int | curr_int <= next_int

    0    |     0    |          1
    0    |     1    |          1
    1    |     0    |          0
    1    |     1    |          1

根据上面的定义，我们可以改写为：

  curr   |  X curr  |         EXPR

  false  |  false   |         true
  false  |  true    |         true
  true   |  false   |         false
  true   |  true    |         true

由真相-table可知EXPR对应

  !curr v (X curr)

可以更优雅地重写为

  curr -> (X curr)

这是给定状态 s_i 的 curr_int <= next_int 的最终 LTL 编码 版本，当两者都是 0-1 时整型变量.

Answer 2

Promela 中没有这个符号。然而，任何 Past Time LTL 公式都可以转化为 Future Time LTL（可能更麻烦）。

虽然不确定是否有一种简单的方法来比较不同状态下的变量值。

还要检查 LTL specification pattern repository 过去。

参见 CS stackexhange 中的讨论

https://cstheory.stackexchange.com/questions/29444/do-past-time-ltl-and-future-time-ltl-have-the-same-expressiveness

在 Promela LTL 语句中引用以前的状态

Referencing previous state in Promela LTL statement

model-checking

spin

promela