invariant statements is not supported?

[muyaview]

say below codes

procedure {:entrypoint} main(x: int)
returns ($r: int)
{
    var i: int;

    i := 0;
    while (i < 10)
        invariant (i <=11);
    {
        i := i + 1;
    }
    assert i > 10;

    $r := i;
    return;
}

the assert error could be found by boogie verifier without specify /unroll argument.
However corral couldn't do this. Seems corral always handle the loops by unrolling. And the invariant statement is not be used.
Or if invariant is supported by corral, how to enable it?

[akashlal]

Corral must return a full program trace witnessing an assert failure. It relies on unrolling to produce this trace. It does support using program invariants to prove the absence of errors whenever possible. I have used procedure requires and ensures in the past. I am not sure what happens with the invariant keyword for loops. Corral converts loops to procedures and its likely that the invariant gets lost.

[shuvendu-lahiri]

Agree with Akash that invariants may not be useful for an assertion that does not hold.

In fact, here is an example that shows that Corral fails to exploit an invariant to get a proof (something Akash and I discussed offline a few months back). But it is not a bug, but more of an enhancement.

var a:[int]int;
var b:[int]int;

procedure Foo(n: int) 
modifies a, b;
{
  var i:int;
  
  a[0] := 0;
  b[0] := 0;
  
  i := 0;
  while (i < n) 
  invariant a[0] == b[0];
  {
    a[i] := a[i] + 1;
    b[i] := b[i] + 1;
    i := i + 1;
  }
  assert (a[0] == b[0]);
}

[bitcalc]

I ran shuvendu-lahiri's example with or without the invariant, corral always reports "no bugs" with and without the invariant clause. And also from reading the above comments, we can conclude that corral ignores the loop invariant clause, right?

[akashlal]

Yeah, I think invariant needs to properly get lifted to ensures postconditions when loop are lifted to recursive procedures. This can be done in the Boogie code -- the relevant procedure is ExtractLoops

[akashlal]

Corral doesn't exactly ignore invariant. I think it still gets converted to assert or assume. It is just that corral isn't able to make best use of it.

[bitcalc]

Corral doesn't exactly ignore invariant. I think it still gets converted to assert or assume. It is just that corral isn't able to make best use of it.

I'm confused about this. If it gets converted to assume, then it should be used.

[akashlal]

Yes, it is used, but still corral isn't able to construct a proof of correctness. There are other ways of making it put a proof together, e.g., using Houdini to infer pre-post conditions,

[bitcalc]

We're Smack/Corral users. After looking through some Corral code, we don't think that we currently have the in-depth knowledge of Corral to make non-trivial changes or making use of Houdini for it. Could you please make a plan to solve this problem? The loop invariant is a distinctive feature of BoogiePL, and Corral should support it.

[akashlal]

Can you more precisely define the behavior that you're looking for? Example: "if I supply this input, then this is how corral should behave".

[bitcalc]

Here're two handy examples:

1. For muyaview's example, corral should report the assertion violation.
2. For a slightly modified shuvendu's example:

var a:[int]int;
var b:[int]int;

procedure {:entrypoint} Foo(n: int)
modifies a, b;
{
  var i:int;
  assume (n > 1); // make the loop interate

  a[0] := 0;
  b[0] := 0;

  i := 0;
  while (i < n)
  invariant a[0] == b[0];
  {
    a[i] := a[i] + 1;
    b[i] := b[i] + 1;
    i := i + 1;
  }
  assert (a[0] != b[0]);
}

Corral should report the assertion violation too.

We'll try to collect more examples to show the expected behaviors.

Thank you very much.

[shazqadeer]

It would be good to first understand Corral's behavior on an annotated program with (potentially recursive) procedures but no loops. Suppose the procedures in such a program are annotated with preconditions and postconditions. Would Corral use these procedure specifications during its search? If yes, please explain how Corral uses them. I am particularly interested in understanding whether Corral expects these specifications to be sound and verified by another approach such as Houdini or whether Corral is able to internally justify their soundness?

…

On Tue, Aug 20, 2019 at 3:14 AM Akash Lal ***@***.***> wrote: Yes, it is used, but still corral isn't able to construct a proof of correctness. There are other ways of making it put a proof together, e.g., using Houdini to infer pre-post conditions, — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#96?email_source=notifications&email_token=AB2RCFRI7FIGKRHUXYWLSLLQFO7W3A5CNFSM4INPN3Z2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD4VZGQQ#issuecomment-522949442>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AB2RCFQPFFTJTHJ32WJNDZDQFO7W3ANCNFSM4INPN3ZQ> .

[akashlal]

Let me reply to @bitcalc first. Corral is not design to meet your expectations. If there is an assertion that can fail, then Corral must be given an unroll bound that is enough to unroll the loops that are needed to get to the assertion. This issue is orthogonal to supporting invariant. Think about it as follows. Corral is under the obligation of returning a concrete error trace when it believes an assertion can fail. In @muyaview's example, the trace needs to go through the loop 10 times. There is no other way to get to the assert. Therefore, you must supply an unroll bound of 10, regardless of any invariant you supply.

The case of using invariant properly is only relevant to establishing a proof of correctness (or pruning search).

Does this make sense?

[akashlal]

I will given an operational answer to @shazqadeer. When given a program with multiple procedures (no loops) that have ensures and requires, corral first instruments the program in the following manner. For each requires R, an assertion assert R is inserted on all call sites, and the requires is converted to a free requires. For each ensures E, an assertion assert E is inserted at the point of return from the procedure and the ensures itself becomes free ensures !assertsPassed || E. The variable assertsPassed is a global variable that is initially true but is assigned false when an assertion fails.

Therefore, corral does use procedure specifications, but it does check them as well to retain soundness. The free annotations act like default summaries that stratified inlining will use to prune search whenever possible.

Hope this is clear.

An invariant is lowered to an assert but no attempt is made to lift it to spec of the extracted procedure for the loop.

[bitcalc]

I now see how Corral handles assertion violations and invariants. In Corral's terms, we are actually making an enhancement request here to combine these two so that Corral can use invariants provided manually during its verification process.

In its general form, the request comes in at different levels:

1. For a given loop invariant, Corral should assume and use its truth in verifying assertions, and the use of invariant should take precedence over (or be controlled by a command option) loop unrolling.

2. If Corral unrolls the loop with an invariant, it should check the correctness of the invariant up to the unrolling bounds, and gives information about it.

3. Ideally, Corral should combine 1 and 2 so that a given loop invariant is assumed and used and meanwhile "checked" up to certain unrolling depth.

I don't know how difficult to do the above, but from a user's point of view, they're extremely useful because we have manually written loop invariants and need to use them in verifying program properties.

[akashlal]

Some of this is possible, while other parts sound like research. I think if you want corral to check the invariant, then its very likely that corral will end up unrolling the loop completely. This is because corral does not fire off a separate inductiveness check for invariants. So it will keep unrolling and checking the asserted invariant.

On the flip side, if you provide a free invariant (i.e., assumed, not asserted) then we should enhance the ExtractLoops procedure in Boogie to lift free invariant to a free ensures of the extracted procedure. Shuvendu wanted to do this. @shuvendu-lahiri are you still up for it?

I think its a nice research problem to enhance corral with inductiveness checks (for loop invariants, as well as postconditions of recursive procedures) so that it can dramatically prune off search. Sounds like a good paper can come out of it.

[bitcalc]

On the flip side, if you provide a free invariant (i.e., assumed, not asserted) then we should enhance the ExtractLoops procedure in Boogie to lift free invariant to a free ensures of the extracted procedure. Shuvendu wanted to do this. @shuvendu-lahiri are you still up for it?

I think its a nice research problem to enhance corral with inductiveness checks (for loop invariants, as well as postconditions of recursive procedures) so that it can dramatically prune off search. Sounds like a good paper can come out of it.

Both sound great plans, and we'd love to see them in Corral. Yes, free should be used before invariant to keep its semantics consistent with free ensures and free requires. For inductiveness checks, it's surely doable. We're happy to validate its effectiveness in some real-world application areas.

[shazqadeer]

Loop invariants are compiled into assert statements at the loop head. Free invariants are likely compiled to assume statements. Perhaps ExtractLoops could be enhanced to lift both. An assert will get converted into both a requires and ensures and an assume will converted into both a free requires and free ensures. Does that make sense?

…

On Tue, Aug 20, 2019 at 9:10 PM Akash Lal ***@***.***> wrote: Some of this is possible, while other parts sound like research. I think if you want corral to *check* the invariant, then its very likely that corral will end up unrolling the loop completely. This is because corral does not fire off a separate *inductiveness* check for invariants. So it will keep unrolling and checking the asserted invariant. On the flip side, if you provide a free invariant (i.e., assumed, not asserted) then we should enhance the ExtractLoops procedure in Boogie to lift free invariant to a free ensures of the extracted procedure. Shuvendu wanted to do this. @shuvendu-lahiri <https://github.com/shuvendu-lahiri> are you still up for it? I think its a nice research problem to enhance corral with inductiveness checks (for loop invariants, as well as postconditions of recursive procedures) so that it can dramatically prune off search. Sounds like a good paper can come out of it. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#96?email_source=notifications&email_token=AB2RCFSNI7G7OSITY2UHVW3QFS54NA5CNFSM4INPN3Z2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD4YLXCY#issuecomment-523287435>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AB2RCFQFJ75P2VWHYSU3Z4DQFS54NANCNFSM4INPN3ZQ> .

[zvonimir]

This makes sense to me, and I was wondering myself if there is anything more to it.

[bitcalc]

Since ExtractLoops is in the boogie module, so I assume that it's Boogie code. I'm wondering how the Boogie verifier handles loop invariants. Does it check the validity of loop invariants by inductiveness or any other means?