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] how to abstract the loop

Hello,

2011/12/29 ?? <luoting8609 at 163.com>

>    I  thought the prover could not understand the iteration without loop
> invariants ,no matter which properties  I want to verify.
>

In the loop:

while (...)
{
  x = 1;
  y = 100 / x;
  ...
}

The division can be found safe without any significant loop invariant. You
can use "true" as loop invariant and it will still be clear that the
program is not dividing by zero.

In the loop:

u32 s0;
u32 te0[256];
...
for (...)
{
  t0 = Te0[s0 >> 24] ...
}

The reason the memory access at Te0 is safe is that any u32 number shifted
by 24 is in the correct interval, and *not* that the particular value of s0
is known.

 If without loop invariants, some corresponding VCs  would not be
> discharged, right?
>

A same loop has several loop invariants. Indeed, every loop admits \true as
invariant in addition to any other invariant it may have. You should write
the simplest invariant for what you want to do. If you are verifying
cryptographic code, you almost never want to write the most precise
invariant, which captures what the entire N rounds do. It's an enormous,
unwieldy formula that is designed not to simplify and to be hard to invert.
What do you expect you will be able to do with it?

What you should never do is write false invariants (as you have done). If
you do that, then you will not verify anything.

  I  am using frama-c/jessie/why to verify the safety of AES. After that ,
> I plan to  verify  information flow security. However , I have no idea
> about how to formalize this property.
>

Perhaps you would like to see something like this:

[from] Function rijndaelEncrypt:
         out[0..3] FROM rk; Nr_0; pt; ct; in[0..15]; key[0..40];
Te0[0..255];
                        Te1[0..255]; Te2[0..255]; Te3[0..255]; Te4[0..255]
            [4..7] FROM rk; Nr_0; pt; ct; in[0..15]; key{[0..39]; [41]; };
                        Te0[0..255]; Te1[0..255]; Te2[0..255]; Te3[0..255];
                        Te4[0..255]
            [8..11] FROM rk; Nr_0; pt; ct; in[0..15]; key{[0..39]; [42]; };
                         Te0[0..255]; Te1[0..255]; Te2[0..255]; Te3[0..255];
                         Te4[0..255]
            [12..15] FROM rk; Nr_0; pt; ct; in[0..15]; key{[0..39]; [43]; };
                          Te0[0..255]; Te1[0..255]; Te2[0..255];
Te3[0..255];
                          Te4[0..255]

I obtained this with the attached file and command. I had to use option
-no-annot because your invariant is false, and this stopped the value
analysis propagation.

 >  It does not simplify (or Rijndael would be a very bad cipher indeed).
>    Do you mean Frama-c  is not  suitable to verify the properties of
> Rijndael, for its source code is complicated?
>

Absolutely not. As shown above, Frama-C can verify the safety and compute
the information flow of Rijndael, in one use case, automatically in half a
second.

What I am saying is that in Rijndael, like in any other cryptographic
function, the safety of the software does not depend on knowing precisely
the relation between inputs and outputs, because the relation between
inputs and outputs is *designed* to be intractably complicated.

I want to verify the security of some cryptographic software with
> frama-c/jessie/why. I have seen someone verified RC4 with
> frama-c/jessie/why. Rijndael is popular and I want to try , but it seems to
> be not  easy .  Would you give me some advice about  some other
> cryptographic software easier to be verified with frama-c/jessie/why.
>

If you absolutely want to use Jessie, then I can only wish you good luck
(and perhaps, for the verification of information flow, recommend the
article
http://bts.frama-c.com/dokuwiki/doku.php?id=mantis:frama-c:functional_dependencieswhich
contains ideas that you may be able to use).

If you are willing to try another Frama-C plug-in, then the verification of
Skein-256 is the topic of the value analysis' tutorial:
http://frama-c.com/download/frama-c-value-analysis.pdf
With only a little bit of additional work, the value analysis would also
tell you that beyond the information flow shown above, AES is susceptible
to cache-timing attacks (
http://cr.yp.to/antiforgery/cachetiming-20050414.pdf ). And it would verify
that Skein-256 is not. This kind of verification was put together with
researchers and students at University of Minho, and it's currently not
documented, but you could also look at their published work, in which they
use Jessie and Why to verify properties of cryptographic software (google
"universidade do Minho frama-c jessie" or, if they are reading this, they
may provide a better overview of what they are doing with crypto software
and Jessie).

Pascal
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.gforge.inria.fr/pipermail/frama-c-discuss/attachments/20111229/49a56b1b/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mymain.c
Type: text/x-csrc
Size: 504 bytes
Desc: not available
URL: <http://lists.gforge.inria.fr/pipermail/frama-c-discuss/attachments/20111229/49a56b1b/attachment.c>