如何在 ACSL 中编写 "is power of 2" 谓词？

Question

我尝试编写一个 ACSL 谓词来查看整数是否是 2 的幂是这样的：

/*@
  predicate positive_power_of_2 (integer i) =
    i > 0 &&
    (i == 1 || ((i & 1) == 0 && positive_power_of_2 (i >> 1)));
 */

然而，当我将一些断言行添加到一个随机函数中时，一些超时（即失败）。我不明白为什么？

//@ assert positive_power_of_2 (1);  // Timeout
//@ assert positive_power_of_2 (2);  // Valid
//@ assert positive_power_of_2 (4);  // Valid
//@ assert !positive_power_of_2 (7); // Timeout

Answer 1

附带说明一下，对于此类纯逻辑属性，您可以使用 lemma 而不是 assert，如 //@ lemma pow2_1: positive_power_of_2(1); 中那样。由于 lemma 是一个全局注释，它使您不必为了持有 assert.

而编写函数

现在回到问题本身。将按位运算与算术运算混合（less-than 比较）往往会混淆自动定理证明器。您没有指定您使用的是哪一个，但如果您只使用一个，您可能想尝试安装其他的（现在，alt-ergo、z3 和 cvc4 的混合往往会提供良好的结果）。也就是说，对 WP 的内部简化器 QED 的一个小的交互式帮助也足够了：通过使用 GUI（参见 WP manual 的第 2.4 节），您可以通过展开每个 positive_power_of_2 的定义来得出结论目标（据我所知，没有 command-line 选项可以做同样的事情）。

基本上，一旦进入 GUI 的 WP Proofs 面板，您必须双击与您要处理的证明义务对应的行的 Script 列，这会让你进入交互证明模式，如下图所示：

现在，重点是可用策略列表（右侧）是上下文相关的：仅显示与您在证明义务（左侧）中选择的术语相关的那些。有些策略总是相关的，例如 Cut，它可以让你证明一个辅助陈述，可以在其余证明中用作假设，但展开定义只有在你的定义中有要展开的情况下才有意义选择。因此你必须点击 P_positive_power_of_2 让战术出现。之后只要点击对应的三角让WP展开定义，然后尝试完成证明。

如何在 ACSL 中编写 "is power of 2" 谓词？

How do I write an "is power of 2" predicate in ACSL?

frama-c

acsl