什么循环不变量用于整数对数？

Question

由于我正在使用 Frama-C 进行 C 形式验证的第一步，因此我尝试正式验证一个整数二进制对数函数，如下所示：

//@ logic integer pow2(integer n) = (n == 0)? 1 : 2 * pow2(n - 1);

/*@
    requires n > 0;
    assigns \nothing;
    ensures pow2(\result) <= \old(n) < pow2(\result + 1);
 */
unsigned int log2(size_t n)
{
    unsigned int res = 0;
    while (n > 1) {
        n /= 2;
        ++res;
    }
    return res;
}

我正在使用 Frama-C 20.0 (Calcium)，命令为 frama-c-gui -rte -wp file.c（出于某种原因我没有 Jessie 插件）。我已经检查了 post-条件以保持最多 n = 100,000,000（使用标准库断言），但尽管我尽了最大努力，此函数仍无法正式验证，并且 Frama-C 教程通常涉及琐碎的循环变体每次迭代都递减（而不是减半），因此与我想要做的不太接近。

我已经尝试了以下代码注释，其中一些可能是不必要的：

//@ logic integer pow2(integer n) = (n == 0)? 1 : 2 * pow2(n - 1);

/*@
    requires n > 0;
    assigns \nothing;
    ensures pow2(\result) <= \old(n) < pow2(\result + 1);
 */
unsigned int log2(size_t n)
{
    unsigned int res = 0;
    /*@
        loop invariant 0 < n <= \at(n, Pre);
        loop invariant \at(n, Pre) < n * pow2(res + 1);
        loop invariant pow2(res) <= \at(n, Pre);
        loop invariant res > 0 ==> 2 * n <= \at(n, Pre);
        loop invariant n > 1 ==> pow2(res + 1) <= \at(n, Pre);
        loop invariant res <= pow2(res);
        loop assigns n, res;
        loop variant n;
     */
    while (n > 1) {
    L:
        n /= 2;
        //@ assert 2 * n <= \at(n, L);
        ++res;
        //@ assert res == \at(res, L) + 1;
    }
    //@ assert n == 1;
    return res;
}

验证失败的注释是循环不变量2和5（Alt-Ergo 2.3.0和Z3 4.8.7超时）。就不变量 2 而言，困难似乎与整数除法有关，但我不确定要添加什么才能使 WP 能够证明这一点。至于不变量5，WP可以证明它成立，但不能证明它保留。它可能需要属性能够捕获当 n 变为 1 时发生的情况，但我不确定什么可以工作。

我如何指定缺失的信息来验证这些循环不变量，是否有另一个 Frama-C 分析可以让我更容易地找到循环不变量？

感谢您的考虑。

Answer 1

一般来说，为注释命名通常是个好主意，尤其是当您开始为同一循环设置多个循环不变量时。它将允许您更快地查明失败的名称（请参见下面的示例，尽管您可以自由地不同意我选择的名称）。

现在回到你的问题：重点是你的不变量 2 有点太弱了。如果当前循环中的 n 是奇数，则无法确定不等式在下一步成立。使用更严格的界限，即 \at(n,Pre) < (n+1) * pow2(res)，当前步骤开始时的假设足以证明不变量在步骤结束时成立，前提是我们知道 res 不会溢出（否则 1+res 最终会变成 0，不等式将不再成立。

为此，我使用中间幽灵函数来证明 n < pow2(n) 任何unsigned，这让我，感谢下面的pow2_lower不变量，确保res_bound被任何循环步骤保留。

最后，关于 pow2 的一个小评论：这里并不重要，因为参数是 unsigned，因此是非负的，但在一般情况下，integer参数可以是负数，因此您可能希望通过在 n<=0.

时返回 1 来使定义更健壮

总而言之，下面的程序完全用Frama-C 20和Alt-Ergo (frama-c -wp -wp-rte file.c)证明了。似乎仍然需要两个断言来指导 Alt-Ergo 的证明搜索。

#include "stddef.h"

/*@ logic integer pow2(integer n) = n<=0?1:2*pow2(n-1); */

/*@ ghost
/@ assigns \nothing;
   ensures n < pow2(n);
@/
void lemma_pow2_bound(unsigned n) {
  if (n == 0) return;
  lemma_pow2_bound(n-1);
  return;
}
*/

/*@
    requires n > 0;
    assigns \nothing;
    ensures pow2(\result) <= \old(n) < pow2(\result + 1);
 */
unsigned int log2(size_t n)
{
    unsigned int res = 0;
    /*@
        loop invariant n_bound: 0 < n <= \at(n, Pre);
        loop invariant pow2_upper: \at(n, Pre) < (n+1) * pow2(res);
        loop invariant pow2_lower: n*pow2(res) <= \at(n, Pre);
        loop invariant res_bound: 0 <= res < \at(n,Pre);
        loop assigns n, res;
        loop variant n;
     */
    while (n > 1) {
    L:
        /*@ assert n % 2 == 0 || n % 2 == 1; */
        n /= 2;
        /*@ assert 2*n <= \at(n,L); */
        res++;
        /*@ ghost lemma_pow2_bound(res); */
    }
    //@ assert n == 1;
    return res;
}

什么循环不变量用于整数对数？

What loop invariants to use for an integer logarithm?

c

frama-c

formal-verification

loop-invariant

proof-of-correctness