-
Notifications
You must be signed in to change notification settings - Fork 106
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Snap encoding of array assignments #877
Comments
Actually, it turns out that the snap encoding is not needed after all! Instead of these 2 statements:
this also does the trick of making
(this works for |
Wait… Is the only difference between the examples |
Yup, that's the only change. I suspect that the |
Full relevant code section without
|
havoc the memory stored at address
My only guess is that syntactically changing the program somehow enables Z3 to trigger the quantifier. |
Is this the original code? |
No, I have some local changes to Prusti that generates that version (and verifies). The original statements (as currently generated from the
What you describe regarding the syntactic rules sounds like what could be happening for the Viper program for
Only in this case
In the case of the Viper program for |
Apologies :) For better context about what I mean by "havoc", I was going off of this comment in the code: prusti-dev/prusti-viper/src/encoder/procedure_encoder.rs Lines 5215 to 5224 in 00fa0d0
|
In case it helps, this small hand-crafted example which does not use
I guess that this is in-line with what would be expected. I'm not sure why a similar approach fails for |
This is very confusing… |
I see ☺. That comment should say that the contents of the array are havocked. |
I looked into the Viper encoding for a bit, but I, unfortunately, do not see what is going wrong here. Coming back to:
I think it would make our life easier if we everywhere used the same lookup function. @Aurel300 Do you see any reason not to do that? |
I'd also compare the change randomizing the Z3 seeds:
|
The It's starting to look more and more like this is an obscure corner case which confuses Viper/Z3 (and in a deterministic fashion despite random seeds, too 😅 ). There is more to it than just the choice for triggers. So far I've not been able to trigger the same circumstances without a loop. Maybe the mix of |
I was playing around with this a bit more today and it gets more confusing :) The version where array assignments are snapshot encoded suffer from the same quirk where the Viper program for The original version that Prusti gives me that doesn't verify is: lib.rs_prusti_example::foo 20220223 unmodified.vpr.txt. |
This sounds more and more like a bug in the Viper backend. However, the examples are way too large to ask the backend developers to look into. Would be nice to get a repro on a 20 or so lines example. An alternative would be to wait until the refactoring is complete and see whether it addresses the problem. |
I'll see if I can whip up something during the weekend :)
In case we don't manage to reproduce a small example, would it be acceptable to use the |
Thanks!
If it has no regressions, I think we could. |
This is the smallest version I could come up with: lib.rs_prusti_example::foo 20220228 small.vpr.txt Surprisingly, the confusing behavior can be triggered without loops or |
…iperproject#877. remove auxiliary helper function for `selection_sort.rs` viperproject#819. added regression test for viperproject#877.
Thank you very much for reducing the example. I have filed a Silicon issue: viperproject/silicon#603 |
888: use `old` in trigger for direct array assignments r=vakaras a=Pointerbender This PR experiments with addressing 2 things: 1. It implements the suggested work-around for #877 together with a regression test (the test suite indicated no regressions locally). 2. The `selection_sort.rs` test case was updated to use this fix in order to remove the auxiliary `set` function (#819). Some notes apply to the approach chosen to make `selection_sort.rs` verify: * A "dummy" `body_invariant!(a[0] <= a[i]);` was added to the outer and inner loops in order to correctly trigger the quantifiers. * A change was made in `prusti-viper/src/encoder/foldunfold/mod.rs` to prevent Prusti from running into an encoder error when the `old` expresion was only present in the trigger, but not in the quantifier body. Without this change, `selection_sort.rs` will complain about a fold-unfold error. Since access predicates are not needed when the `old` expression is only present in the trigger, this should be sound (but please do double check this during the peer review). * Without the auxiliary `set` function, the verification time roughly doubled, but it is still well within the `-Pverification_deadline=180` compiler parameter. Execution time now hovers around ~2 minutes on my PC. If the chosen approach sounds good, then this PR can be merged. I'm still a bit suspicious about why the `set` function yields better performance, I could look into this deeper with some guidance (possibly in a separate PR if that makes more sense). For now I came up empty-handed for what could be causing this performance regression (if this happens to be related to how Viper gives hints to Z3 based on the Viper/Silver syntax, then my current experience may not be of much help, but am willing to learn more!). Thanks! p.s. Issue #877 can be left open for now in case we want to file a bug report with the Viper back-end developers to investigate the `old` trigger issue. I posted a ~30 lines example there that hopefully is small enough to investigate. Co-authored-by: Pointerbender <pointerbender@gmail.com>
This issue is a spin-off from #819, which revealed that currently Prusti is unable to verify programs like:
but Prusti can verify this program okay:
The underlying issue seems to be related to the snapshot encoding of
a
.Some ideas that were suggested in #819 are:
I started looking into option 2 and discovered that adding just the trigger is not sufficient to make the program verify. The Viper program for
foo
generates the following Viper statements for the array assignment:With a bit of manual hacking in the Viper program, I can make the Viper program for
foo
verify if I replace the above 2 statements with:Would it be desirable to implement array assignments in this snap encoded form everywhere? I believe that these are fully backwards-compatible with the non-snapshot version, due to:
{ lookup_pure__$TY$__Array$3$usize$usize$(_LET_4, i) }
makes sure that the quantifier is triggered in all the places were it is triggered now.snap$__$TY$__Snap$Array$3$usize$
andlookup_pure__$TY$__Array$3$usize$usize$
both require the same access predicates, namelyrequires acc(Array$3$usize(self), read$())
.snap$__$TY$__Snap$Array$3$usize$
ensures that the knowledge about the array values is propagated to both the Snap and non-Snap domains:However, I'm not sure about what performance implications this would bring with it, so I wanted to bounce this idea off everyone here before implementing it and creating a PR :)
Thanks!
The text was updated successfully, but these errors were encountered: