Frama-C 警告：缺少赋值子句（改为赋值 'everything'）

Question

我正在用 frama-c 测试这个小程序，但我总是遇到同样的错误。我不确定这是什么意思。我对 assigns everything 的含义特别困惑。

这是带有 ACSL 注释的问题代码：

// assuming n is nonnegative and even, f returns n

/*@ requires n>=0;
*/

int f(int n) {
  int i=0;
  while (i<n) {
    i+=2;
  }
  //@ assert i==n;
  return i;
}

以下是我尝试测试代码时终端显示的内容：

[wp] warning: Missing RTE guards
p3.c:9:[wp] warning: Missing assigns clause (assigns 'everything' instead)
[wp] 1 goal scheduled
[wp] [Alt-Ergo] Goal typed_f_assert : Unknown (Qed:8ms) (54ms)
[wp] Proved goals:    0 / 1
    Alt-Ergo:        0  (unknown: 1)

Answer 1

首先，您的属性不正确，因为您不需要 n 在函数的前提条件中。因此，我将向您展示如何在循环体中使用 i += 1 证明程序的变体。

assigns 子句是 WP 要求您为每个循环和每个外部函数调用指定的内容。它必须包含可能被循环（或函数）修改的所有内存位置（即变量）的列表。它需要这个才能知道其他所有内容都是 not 由循环修改的。特别是，在这个程序中，WP 需要知道 i 的值在循环中可能会改变，而 n 的值不会改变。但是如果你不告诉它是这样的话，它就假定循环可能赋值"everything"，包括n.

要指定这一点，您可以在循环上方插入以下注释：

/*@ loop assigns i; */

如果您尝试证明这一点（在 GUI 中），您将看到 WP 可以验证此分配子句。

但是，你在循环后的断言仍然不能用这个来证明。那是因为除了赋值子句之外，每个循环还必须有一个 循环不变量：在循环的每次迭代之前和之后始终为真的东西。选择正确且足够强大的循环不变量是一门黑暗的艺术，但总的来说，不变量必须是这样的东西，一旦循环条件为假并且循环终止，我们就可以在循环后得出断言。

也就是说，我们希望公式 I 具有属性的不变式：

I && !(i < n)  ==>  i == n

因此，循环不变量 i <= n 是一个不错的选择，因为 if i <= n 但我们知道 i < n 是 not true（因为循环已停止迭代），则 i 必须等于 n.

将所有内容放在一起，这是您程序的一个带注释的变体：

/*@ requires n>=0;
*/

int f(int n) {
  int i=0;
  /*@ loop assigns i;
    @ loop invariant i <= n;
   */
  while (i<n) {
    i += 1;
  }
  //@ assert i==n;
  return i;
}

这是自动验证的：

[wp] warning: Missing RTE guards
[wp] 4 goals scheduled
[wp] Proved goals:    4 / 4
    Qed:             4

Frama-C 警告：缺少赋值子句（改为赋值 'everything'）

Frama-C warning: Missing assigns clause (assigns 'everything' instead)

automated-tests

frama-c

acsl