如何用 Frama-C 证明 C stringCompare 函数的功能？

Question

我想用 Frama-c 和 WP 插件表达，下面编写的 stringCompare 函数作为“它应该”的行为 - 即：给定相同的输入字符串，函数 returns 0，如果字符串不相同，则结果不同于 0。我已经注释了如下所示的相关功能，并且希望能够证明WP生成的未经证实的目标，那怎么办？

我尝试运行带有注释的插件得到的输出，可以在代码下面看到

#include <string.h>
#include <stdio.h>

/*@  
    requires validPointers: \valid_read(s1) && \valid_read(s2) ;
    requires validLengthS1: 100 >= strlen(s1) >= 0;
    requires validLengthS2: 100 >= strlen(s2) >= 0;
    assigns \nothing ;
    allocates \nothing ;  
    frees \nothing ;
    behavior allEqual:
        assumes \forall integer k; 0 <= k < n ==> s1[k] == s2[k];
        ensures \result == 0;
    behavior SomeDifferent:
        assumes \exists integer k; 0 <= k < n ==> s1[k] != s2[k];
        ensures \result != 0;
    
    disjoint behaviors;
    complete behaviors;
    */ 
int stringCompare(const char* s1, const char* s2, int n) {
    if (s1 == s2) 
        return 0;
    int i = 0;

    /*@ assert \valid_read(s1) ; */
    /*@ assert \valid_read(s2) ;*/
    /*@ loop invariant 0 <= i; 
        loop assigns i , s1, s2; */    
    while (*s1 == *(s2++))
    {
        /*@ assert i <= 2147483647 ; */
        ++i;
        if (*(s1++) == '[=10=]')
            return 0;
    }
   
    return *(unsigned char*)s1 - *(unsigned char*)(--s2);
}

/*@ assigns \nothing ;
    ensures rightResult: \result == strlen(\old(str));
    ensures rightEndCharacter: str[\result] == '[=10=]' ;  */
int stringLength(const char* str) {
    int result = 0;

    /*@ loop assigns result ;
        loop invariant 0 <= result ; */
    while (str[result++] != '[=10=]');

    return --result;

}

/*@ assigns \nothing ;
    ensures \result == 0 ;*/
int main(void) {

   const char* hello = "hello";
   const char* helli = "helli";

   /*@ assert \valid_read(hello) && \valid_read(helli) ; */
   stringCompare(hello, helli, 5);
   return 0;
}

WP 正在运行使用以下命令：'frama-c -wp -wp-model "Typed+var+int+real" -wp-timeout 20 strcmp.c'

WP 插件生成的输出：

[wp] Warning: Missing RTE guards
[wp] strcmp.c:48: Warning:
  Cast with incompatible pointers types (source: sint8*) (target: uint8*)
[wp] strcmp.c:48: Warning:
  Cast with incompatible pointers types (source: sint8*) (target: uint8*)
[wp] 49 goals scheduled
[wp] [Alt-Ergo 2.2.0] Goal typed_real_main_call_stringCompare_requires_validLengthS1 : Timeout (Qed:2ms) (20s)
[wp] [Alt-Ergo 2.2.0] Goal typed_real_main_call_stringCompare_requires_validLengthS2 : Timeout (Qed:2ms) (20s)
[wp] [Alt-Ergo 2.2.0] Goal typed_real_main_call_stringCompare_2_requires_validLengthS1 : Timeout (Qed:4ms) (20s)
[wp] [Alt-Ergo 2.2.0] Goal typed_real_main_call_stringCompare_2_requires_validLengthS2 : Timeout (Qed:3ms) (20s)
[wp] [Alt-Ergo 2.2.0] Goal typed_real_main_call_stringCompare_3_requires_validLengthS1 : Timeout (Qed:8ms) (20s)
[wp] [Alt-Ergo 2.2.0] Goal typed_real_main_call_stringCompare_3_requires_validLengthS2 : Timeout (Qed:8ms) (20s)
[wp] [Alt-Ergo 2.2.0] Goal typed_real_main_call_stringCompare_4_requires_validLengthS1 : Timeout (Qed:11ms) (20s)
[wp] [Alt-Ergo 2.2.0] Goal typed_real_main_call_stringCompare_4_requires_validLengthS2 : Timeout (Qed:12ms) (20s)
[wp] [Alt-Ergo 2.2.0] Goal typed_real_stringCompare_disjoint_SomeDifferent_allEqual : Timeout (Qed:3ms) (20s)
[wp] [Alt-Ergo 2.2.0] Goal typed_real_stringCompare_allEqual_ensures : Timeout (Qed:15ms) (20s) (Stronger, 2 warnings)
[wp] [Alt-Ergo 2.2.0] Goal typed_real_stringCompare_SomeDifferent_ensures : Timeout (Qed:14ms) (20s) (Stronger, 2 warnings)
[wp] [Alt-Ergo 2.2.0] Goal typed_real_stringLength_ensures_rightResult : Timeout (Qed:5ms) (20s)
[wp] Proved goals:   37 / 49
  Qed:              30  (1ms-3ms-11ms)
  Alt-Ergo 2.2.0:    7  (8ms-43ms-126ms) (464) (interrupted: 12)

Answer 1

这里有不少要点。首先，我要说的是，在遇到验证问题时，尝试使用内存模型可能不是第一件事（特别是，由于您没有使用浮点运算，因此 +real 组件完全没用）。因此，我建议从等式中完全删除 -wp-model，默认选择通常就足够了。另一方面，添加 -wp-rte 以检查潜在的运行时错误可能会很有趣。

当您指定 \valid_read(s1) 时，您是说您可以访问 s1[0]，但没有别的。如果你想谈论几个记忆单元的有效性，你可以使用 \valid_read(s1 + (0 .. n))，或者，在空终止 C 字符串的情况下，\valid_string(s1).

您在 stringCompare 的两种行为中的假设子句都是不正确的：我们只在 strlen(s1)（包括）之前搜索差异，而不是在 n（顺便说一下非常无用，可能会被删除：您想指定 strlen(s{1,2}) 是有界的，但是 stdint.h 中的 SIZE_MAX 应该可以做到这一点）。此外，\forall i, P(i) ==> Q(i)的反义词是\exists i, P(i) && !Q(i)（即在\exists之后不要使用==>）。

对于打算用作偏移量的 C 变量，最好使用 size_t。否则对于非常大的字符串可能会发生奇怪的事情。

你缺少一些不变量。基本上，在 stringCompare 中，您必须捕捉到以下事实：

i 停留在 0 和 strlen(s1) 之间（分别为 strlen(s2)）
s1 的当前值实际上是 \at(s1,Pre)+i （同上 s2）
到目前为止，s1和s2的所有元素都相等...
...和非空

由于 Frama-C 的目标默认体系结构使用 char 作为签名，因此在 return 语句中转换为 unsigned char 会使 WP 混淆。诚然这是WP本身的弱点。

对于stringLength，还需要像valid_string(str)这样的东西。但是，这次你必须限制 strlen(str) 严格小于 SIZE_MAX（假设你更改你的 return 类型并且 result 的声明为 size_t） , 因为 result 必须上升到 strlen(str)+1 而不会溢出。

同样，必须加强循环不变量：result 受 strlen(str) 限制，我们必须指出到目前为止所有字符都是非 0。

最后，在您的 main 函数中，WP 的另一个弱点阻止检查是否满足 stringCompare 的先决条件。如果 hello 和 helli 明确定义为 char 数组，那么一切都会好起来的。

tl;dr：下面的代码完全可以用 frama-c -wp -wp-rte file.c（Frama-C 22.0 Titanium 和 Alt-Ergo 2.2.0）

来证明

#include <stdint.h>
#include <string.h>
#include <stdio.h>

/*@  
    requires validPointers: valid_read_string(s1) && valid_read_string(s2);
    requires validLengthS1: n >= strlen(s1) >= 0;
    requires validLengthS2: n >= strlen(s2) >= 0;
    assigns \nothing ;
    allocates \nothing ;  
    frees \nothing ;
    behavior allEqual:
        assumes \forall integer k; 0 <= k <= strlen(s1) ==> s1[k] == s2[k];
        ensures \result == 0;
    behavior SomeDifferent:
        assumes \exists integer k; 0 <= k <= strlen(s1) && s1[k] != s2[k];
        ensures \result != 0;
    
    disjoint behaviors;
    complete behaviors;
    */ 
int stringCompare(const char* s1, const char* s2, size_t n) {
    if (s1 == s2) 
        return 0;
    size_t i = 0;

    /*@ assert \valid_read(s1) ; */
    /*@ assert \valid_read(s2) ;*/
    /*@ loop invariant index: 0 <= i <= strlen(\at(s1,Pre));
        loop invariant index_1: 0<= i <= strlen(\at(s2,Pre));
        loop invariant s1_pos: s1 == \at(s1,Pre)+i;
        loop invariant s2_pos: s2 == \at(s2,Pre)+i;
        loop invariant equal: \forall integer j; 0<= j < i ==> \at(s1,Pre)[j] == \at(s2,Pre)[j];
        loop invariant not_eos: \forall integer j; 0<= j < i ==> \at(s1,Pre)[j] != 0;
        loop assigns i , s1, s2; */    
    while (*s1 == *(s2++))
    {
        /*@ assert i <= n ; */
        ++i;
        if (*(s1++) == '[=10=]')
            return 0;
    }
   
    return *(s1) - *(--s2);
}

/*@
  requires valid_string(str);
  requires strlen(str) < SIZE_MAX;
  assigns \nothing ;
  ensures rightResult: \result == strlen(\old(str));
  ensures rightEndCharacter: str[\result] == '[=10=]' ;  */
size_t stringLength(const char* str) {
    size_t result = 0;

    /*@ loop assigns result ;
        loop invariant 0 <= result <= strlen(str);
        loop invariant \forall integer i; 0<= i < result ==> str[i]!=0;
    */
    while (str[result++] != '[=10=]');

    return --result;

}

/*@ assigns \nothing ;
    ensures \result == 0 ;*/
int main(void) {

   const char hello[] = { 'h', 'e', 'l', 'l', 'o', '[=10=]'};
   const char helli[] =  { 'h', 'e', 'l', 'l', 'i', '[=10=]'};

   /*@ assert \valid_read(&hello[0]) && \valid_read(&helli[0]) ; */
   stringCompare(hello, helli, 5);
   return 0;
}

如何用 Frama-C 证明 C stringCompare 函数的功能？

How to prove the functionality of a C stringCompare function with Frama-C?

c

static-analysis

frama-c