在 CBMC 中表达“exactly once”的更好方式

Question

我真的很努力地想出一个更好的解决方案来在 CBMC（C 有界模型检查器）中声明“恰好一次”属性。我的意思是一行中只有一个元素位置应该具有值 1（或任何可以检查为布尔值真值的正数），其余必须全为零。

For M = 4

for(i=0;i<M;i++){
__CPROVER_assume( (update[i][0]) ?  
    ( !(update[i][1]) && !(update[i][2])  &&!(update[i][3]) ) :         
     ((update[i][1]) ?  (!(update[i][2])  && !(update[i][3]) ) :                  
     ((update[i][2]) ? !update[i][3] : update[i][3] )) )   ;
}`

For M bigger than that It's huge problem. Lets say M = 8 I have to do something like :

for(i=0;i<M;i++){
   __CPROVER_assume( (update[i][0]) ?  ( !(update[i][1]) && !(update[i][2])  && !(update[i][3]) && (update[i][4]) && !(update[i][5])  && !(update[i][6]) && !(update[i][7]) )  :
           ((update[i][1]) ?  (!(update[i][2])  && !(update[i][3]) && !(update[i][4]) && !(update[i][5])  && !(update[i][6]) && !(update[i][7]) ) :
             ((update[i][2]) ? ((!update[i][3]) && !(update[i][4]) && !(update[i][5])  && !(update[i][6]) && !(update[i][7]))  :
                   ((update[i][3]) ? (!(update[i][4]) && !(update[i][5])  && !(update[i][6]) && !(update[i][7]))  : 
                   ((update[i][4]) ? (!(update[i][5])  && !(update[i][6]) && !(update[i][7])) : 
                      ((update[i][5]) ? (!(update[i][6]) && !(update[i][7])) :  
                         ((update[i][6]) ? !(update[i][7]) : (update[i][7])))))))) ;
}

检查 exactly once 的违规情况很容易，但声明它看起来很重要。我可能还有一个选择：将二维数组问题表述为一维位向量问题，然后进行一些智能异或。但我目前不确定。

有没有人有更好的解决方案？

Answer 1

如何计算真值的数量，然后检查有多少：

for (i = 0; i < M; i++) {
    int n_true = 0;
    int j;

    for (j = 0; j < M; j++) {
        n_true += (update[i][j] ? 1 : 0);
    }

    __CPROVER_assume(n_true == 1);
}

在 CBMC 中表达“exactly once”的更好方式

Better way to express “exactly once” in CBMC

c

model-checking

sat

cbmc