You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

Frama-C 24.0归纳策略疑似Bug:归纳目标为true问题求助

Frama-C 24.0与25.0归纳证明分支差异原因(循环不变量验证)

我正在对一段C代码做形式化证明,针对循环不变量result_val采用以begin为基例、对i的归纳策略验证。在Frama-C 24.0中,归纳的sup分支需要证明的目标是true,可直接得证;但切换至25.0版本后,该分支生成了更复杂的条件(显式计算最弱前置条件,更符合正确归纳逻辑),然而所有尝试的SMT解算器均无法证明该条件。我对24.0版本结果的正确性存疑,因归纳证明目标为true不符合常理,想知道这是24.0的Bug还是版本间的实现差异?

相关代码

#include <stdbool.h>
#define  SIZE       1000

bool data[SIZE] ;


/*@
    logic integer count(integer begin, integer end)=
        begin >= end ? 0 : (data[begin]==true) ? count(begin+1, end)+1 : count(begin+1, end);
*/

/*@
    requires SIZE > begin >= 0;
    requires SIZE >= end >= 0;
    requires begin <= end;
    assigns \nothing;
    ensures \result == count(begin, end);
 */
unsigned int occurrences_of(int begin, int end)
{
    unsigned int result = 0;

    /*@
        loop invariant i_bound: begin <= i <= end;
        loop invariant result_bound: 0 <= result <= i-begin;
        loop invariant result_val: result == count(begin, i);
        loop assigns i, result;
        loop variant end-i;
    */
    for (unsigned int i = begin; i < end; ++i){
        result += (data[i] == true) ? 1 : 0;
    }
    return result;
}

Frama-C 24.0输出结果

Proof:
  Goal Invariant 'result_val' (preserved) (Induction: proved)
   + Goal Induction (Base) (proved)
   + Goal Induction (Induction (sup)) (proved)
   + Goal Induction (Induction (inf)) (proved)
Qed.
--------------------------------------------------------------------------------

Goal Induction (Induction (sup)):
Prove: true.

Frama-C 25.0输出结果

--------------------------------------------------------------------------------
Proof:
  Goal Invariant 'result_val' (preserved) (Induction: pending)
   + Goal Induction (Base) (proved)
   + Goal Induction (Induction (sup)) (pending)
   + Goal Induction (Induction (inf)) (proved)
End.
--------------------------------------------------------------------------------

Goal Induction (Induction (sup)):
Let x_0 = to_uint32(end@L1).
Let x_1 = to_uint32(tmp@L12).
Let x_2 = data@L1[i@L6].
Let x_3 = result@L6.
Let x_4 = result@L13.
Let x_5 = to_uint32(1 + i@L6).
Assume {
  Have: begin@L1 < i@L6.
  Have: i@L6 <= end@L1.
  Have: i@L6 < x_0.
  Have: 0 <= x_3.
  Have: x_5 <= end@L1.
  Have: begin@L1 <= x_5.
  Have: (begin@L1 + x_3) <= i@L6.
  Have: (begin@L1 + x_4) <= x_5.
  Have: is_uint32(i@L6).
  Have: is_bool(x_2).
  Have: is_uint32(x_3).
  Have: if (x_2 = 1) then (tmp@L12 = 1) else (tmp@L12 = 0).
  Have: forall i_0 : Z. let x_6 = L_count(data@L1, begin@L1, i_0) in
      let x_7 = to_uint32(1 + i_0) in let x_8 = to_uint32(x_1 + x_6) in
      let x_9 = data@L1[i_0] in ((i_0 <= end@L1) -> ((begin@L1 <= i_0) ->
      ((i_0 < i@L6) -> ((i_0 < x_0) -> ((0 <= x_6) -> ((x_7 <= end@L1) ->
      ((begin@L1 <= x_7) -> (((begin@L1 + x_6) <= i_0) ->
      (((begin@L1 + x_8) <= x_7) -> (is_uint32(i_0) -> (is_bool(x_9) ->
      (is_uint32(x_6) ->
      ((if (x_9 = 1) then (tmp@L12 = 1) else (tmp@L12 = 0)) ->
      (L_count(data@L1, begin@L1, x_7) = x_8)))))))))))))).
  [...]
  Stmt { L6:  }
  Stmt { tmp = tmp_0;  }
  Stmt { L12: result = x_4;  }
  Stmt { L13:  }
}
Prove: L_count(data@L1, begin@L1, x_5) = x_4.

Goal id:  typed_occurrences_of_loop_invariant_result_val_preserved
Short id: occurrences_of_loop_invariant_result_val_preserved
--------------------------------------------------------------------------------
Prover Alt-Ergo 2.4.2: Timeout (Qed:52ms) (10s).

内容的提问来源于stack exchange,提问作者Yu-Fang Chen

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.08.17 00:05:32