ACSL назначает аннотацию для внутренних структур и полей кода C

Предположим, у нас есть такая структура данных:

#typedef struct
{
int  C_Field;
}C;

#typedef struct
{
C B_Array[MAX_SIZE];
}B;

#typedef struct
{
 B A_Array[MAX_SIZE];
}A;

Кажется, что Frama-C не назначает место для поля структуры типа C в следующем примере:

/*@
  assigns Arg->A_Array[0..(MAX_SIZE - 1)].B_Array[0..(MAX_SIZE - 1)].C_Field;
*/
void Initialize (A * Arg);

Приемлема ли приведенная выше аннотация Frama-C вообще?

Код разработан следующим образом. Основная цель — сбросить поле C_Field в 0:

/*@ predicate 
      ResetB (B * Arg) =
        \forall integer Index; 0<= Index < MAX_SIZE ==>
                 Arg -> B_Array[Index].C_Field == 0;
*/

//@ assigns * Arg;
// Even I tried this:
//@ assigns Arg -> A_Array[0..(MAX_SIZE - 1)];
void Initialize (A * Arg)
{
 /*@ loop invariant 0 <= Index <= MAX_SIZE;
     loop invariant ResetB(&(Arg->A_Array[Index]));
     loop assigns Index, Arg -> A_Array[0..(MAX_SIZE - 1)];
 */
 for (int Index = 0; Index < MAX_SIZE; Index++)
  {
    Reset(&(Arg -> A_Array[Index]));
  }
}

/*@ assigns Arg -> B_Array[0..(MAX_SIZE - 1)];
    ensures ResetB(Arg);      
*/
void Reset(B * Arg)
{
 /*@ loop invariant 0 <= Index <= MAX_SIZE;
     loop invariant \forall integer i; 0<= i < Index ==>
                     Arg -> B_Array[i].C_Field == 0;
     loop assigns Index, Arg -> B_Array[0..(MAX_SIZE - 1)];
 */
 for (int Index = 0; Index < MAX_SIZE; Index++)
 {
  Arg -> B_Array[Index].C_Field = 0;
 }
}

Контракт функции Reset выполняется, а контракт функции Initialize — нет. Как написать правильное «назначение» для контракта Initialize?


person Rocolife    schedule 27.04.2017    source источник
comment
Ваш вопрос немного не ясен. Frama-C Silicon (последняя стабильная версия) может отлично анализировать assigns (при условии, что # перед typedef удалено и задано определение для MAX_SIZE). Не могли бы вы описать точно что вы пробовали с этим кодом и чем результат Frama-C отличается от того, что вы ожидали?   -  person Virgile    schedule 27.04.2017
comment
Спасибо за ответ. Наша главная цель — сбросить поле C_Field в 0. Приведенный выше код разработан следующим образом:   -  person Rocolife    schedule 27.04.2017
comment
Добро пожаловать в StackOverflow. Это должен быть синтаксис C? Затем исправьте синтаксические ошибки и/или странные сочетания синтаксиса препроцессора/компилятора. Я думаю, что @Virgile имел в виду то же самое. Затем предоставьте минимально воспроизводимый пример. В противном случае удалите тег C. И, пожалуйста, подумайте о том, чтобы пройти тур.   -  person Yunnosch    schedule 27.04.2017
comment
Показанный код кажется далеким от C-кода. Можете скомпилировать, показать ошибки, которые выдает c-компилятор и прокомментировать, почему у вас проблемы с их исправлением или не хотите? Если создание компилируемого mcve является для вас проблемой, сделайте его как можно более компилируемым и спросите об одной ошибке, которую вы не можете исправить. Пожалуйста, сформулируйте свой вопрос так, чтобы он убедил читателей, что вы пытались скомпилировать с помощью c-компилятора. Вы также можете сделать его компилируемым, деактивировав строку кода, которая вызывает ошибки (т.е. предоставить их в виде комментариев).   -  person Yunnosch    schedule 27.04.2017
comment
Основной вопрос касается ячеек памяти, которые изменяются при вызове функции. Как правильно написать местоположения в присваиваемой аннотации ACSL? Кажется, задача сложная, когда код состоит из пары внутренних структур. Поэтому вопрос не в самом C-коде и ошибках компиляции.   -  person Rocolife    schedule 27.04.2017
comment
@Rocolife Если ваш код не компилируется, нет особого смысла пытаться что-то доказать. Более того, ваше последнее предложение все еще недостаточно точно. Я предполагаю, что вы имеете в виду, что когда я запускаю frama-c -wp file.c, контракт Reset помечен как действительный, а контракт Initialize - нет, но плагин, который вы используете, должен был быть упомянут явно. Есть много возможных применений Frama-C, и ответ на вопрос «Почему xxx не доказан?» будет сильно различаться в зависимости не только от xxx, но и от используемых вами подключаемых модулей.   -  person Virgile    schedule 27.04.2017
comment
Извините за мою короткую версию моего кода. Пожалуйста, посмотрите последние. Код компилируется без ошибок. Я использую плагин WP. Как вы сказали, аннотации Reset помечаются зеленым маркером, когда я запускаю frama-c -wp file.c. Однако аннотации Initialize помечены двухцветным тегом, за исключением назначений и назначений циклов, которые помечены желтым. Любая помощь для желтой части, пожалуйста?   -  person Rocolife    schedule 27.04.2017
comment
Итак, какие ячейки памяти изменяются после вызова функции Initialize?   -  person Rocolife    schedule 27.04.2017


Ответы (1)


Предполагая, что вы используете плагин WP (см. комментарий выше), ваша основная проблема заключается в том, что вы не написали loop assigns для своего цикла в функции Initialize. loop assigns являются обязательными для каждого цикла, появляющегося в функциях, над которыми вы хотите использовать WP. Кроме того, если в вашем контракте есть ensures пунктов, вам, скорее всего, понадобится loop invariant, опять же, для каждого отдельного цикла в анализируемом коде.

Обновление С предоставленным вами кодом и frama-c Silicon единственное, что не доказано с помощью frama-c -wp file.c, — это инвариант цикла в Initialize относительно ResetB. Причина, по которой это не доказано, заключается в том, что это неправильно. Настоящий инвариант должен читаться как \forall integer i; 0<=i<Index ==> ResetB(&(Arg->A_Array[i])). В следующем полном примере все разряжается, по крайней мере, с Silicon:

#define MAX_SIZE 100

typedef struct
{
int  C_Field;
int D_Field;
}C;

typedef struct
{
C B_Array[MAX_SIZE];
}B;

typedef struct
{
 B A_Array[MAX_SIZE];
}A;

/*@ predicate 
      ResetB (B * Arg) =
        \forall integer Index; 0<= Index < MAX_SIZE ==>
                 Arg -> B_Array[Index].C_Field == 0;
*/

void Reset(B * Arg);

// @ assigns * Arg;
// Even I tried this:
//@ assigns Arg -> A_Array[0..(MAX_SIZE - 1)];
void Initialize (A * Arg)
{
 /*@ loop invariant 0 <= Index <= MAX_SIZE;
     loop invariant \forall integer i; 0<=i<Index ==> ResetB(&(Arg->A_Array[i]));
     loop assigns Index, Arg -> A_Array[0..(MAX_SIZE - 1)];
 */
 for (int Index = 0; Index < MAX_SIZE; Index++)
  {
    Reset(&(Arg -> A_Array[Index]));
  }
}

/*@ assigns Arg -> B_Array[0..(MAX_SIZE - 1)];
    ensures ResetB(Arg);
*/
void Reset(B * Arg)
{
 /*@ loop invariant 0 <= Index <= MAX_SIZE;
     loop invariant \forall integer i; 0<= i < Index ==>
                     Arg -> B_Array[i].C_Field == 0;
     loop assigns Index, Arg -> B_Array[0..(MAX_SIZE - 1)];
 */
 for (int Index = 0; Index < MAX_SIZE; Index++)
 {
  Arg -> B_Array[Index].C_Field = 0;
 }
}
person Virgile    schedule 27.04.2017
comment
Спасибо. Пожалуйста, посмотрите на мой последний комментарий выше. - person Rocolife; 27.04.2017
comment
У предиката уже есть \forall. Почему вы используете другой \forall перед предикатом в инварианте цикла Initialize? - person Rocolife; 27.04.2017
comment
Извините, вы правы. Предлагаемый вами инвариант предназначен для двух вложенных циклов for. Это именно то, что необходимо для нашей проверки. Большое спасибо. - person Rocolife; 28.04.2017
comment
@Rocolife Рад, что помог. Если вы считаете, что этот ответ был полезен, не стесняйтесь принять его. - person Virgile; 28.04.2017