Frama-C-discuss mailing list archives

This page gathers the archives of the old Frama-C-discuss archives, that was hosted by Inria's gforge before its demise at the end of 2020. To search for mails newer than September 2020, please visit the page of the new mailing list on Renater.

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Frama-c-discuss] Some information on invariant needs

  • Subject: [Frama-c-discuss] Some information on invariant needs
  • From: dmentre at linux-france.org (David MENTRE)
  • Date: Fri, 21 Sep 2012 15:07:12 +0200
Hello,

A long time ago (last December), we discussed about the need for
invariants and how to support them. Claude (March?) underlined the
difficulty to support them (due to aliasing) and requested more
information on the desired invariants I had in mind:
  http://lists.gforge.inria.fr/pipermail/frama-c-discuss/2011-December/002922.html

Since then, I had the opportunity to work with Frama-C on a security
domain program. I also looked at other specifications that could be
formalized in the railway domain. Therefore I have a few more
information to provide.

Regarding restriction on allowed invariants, I would consider useful
to have module wide (i.e. C file) and program wide invariants on:
  * Basic C variables (integer mainly);

  * Nested arrays and C struct, all sizes known at compile time.

Regarding properties to express, weak (checked at function entry/exit)
with first order logic is enough for safety properties. Being able to
express strong (at every program step) invariants on read and write
access to variables would be a big plus for security programs.

As a kind of example:

typedef struct {
  unsigned char AES_key[32];
  unsigned char validity;
} key_t;

key_t keys[2];

unsigned char admin_level;

Example of properties that would be useful to express (pseudo Frama-C syntax):
 * admin_level is 0, 1 or 2: "weak invariant: 0 <= admin_level &&
admin_level <= 2;"

 * only one key can be valid at any time: "weak invariant:
(keys[0].validity == GOOD ==> keys[1].validity == BAD) &&
(keys[1].validity == GOOD ==> keys[0].validity == BAD);"

 * only admin level 2 can manipulate keys: "strong invariant:
\write(keys) ==> admin_level == 2;"


Regarding a hypothetical railway program:

unsigned int current_speed;
unsigned int speed_limit[SPEED_LIMIT_MAX];

 * Current speed always in speed limit: "weak invariant: \forall i:
integer. 0<= i && i < SPEED_LIMIT_MAX ==> current_speed <=
speed_limit[i];"

Function would directly access above global variables. For example:
void swap_validity(void)
{ unsigned char tmp; tmp = keys[1].validity; keys[1].validity =
keys[0].validity; keys[0].validity = tmp; }

Would it be feasible to verify above invariants? Anyway, I hope it
brings some useful information.

Best regards,
david