Skip to content

Non-termination of proof on simple array copy example #8326

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

Closed
rod-chapman opened this issue Jun 12, 2024 · 4 comments
Closed

Non-termination of proof on simple array copy example #8326

rod-chapman opened this issue Jun 12, 2024 · 4 comments
Assignees
Labels
aws Bugs or features of importance to AWS CBMC users

Comments

@rod-chapman
Copy link
Collaborator

CBMC version: 6.0.0-alpha (built 12th June 2024)
Exact command line resulting in the issue: make TARGET=ctcc
What behaviour did you expect: It should work!
What happened instead:

Following issue #8303, cbmc no longer crashes but does not terminate on verification of the "ctcc" function in the latest version of code here:
https://github.com/rod-chapman/cbmc-examples/tree/main/arrays

The on-screen output ends with:

converting SSA
Runtime Convert SSA: 288.144s
Running SMT2 QF_AUFBV using Z3
Runtime Solver: 753.195s
Runtime decision procedure: 1041.34s
Running SMT2 QF_AUFBV using Z3
Runtime Solver: 2818.75s
Runtime decision procedure: 2818.75s
Running SMT2 QF_AUFBV using Z3

with very large runtimes for both the SSA conversion and subsequent Z3 runs.

This function is trivial, so I see no reason for this.

@tautschnig tautschnig added the aws Bugs or features of importance to AWS CBMC users label Jun 12, 2024
@rod-chapman
Copy link
Collaborator Author

I re-built wavefront CBMC this morning from source, and re-tried this example. The "Runtime convert SSA" phase is much better at 19 seconds (no idea why!), but Z3 is still taking forever...

@rod-chapman
Copy link
Collaborator Author

I found a problem with my code that helps. See commit
rod-chapman/cbmc-examples@b412c3f

The "assigns" contract in the loop was obviously wrong. It was

  __CPROVER_assigns(i, dst)

but it should be

__CPROVER_assigns(i, __CPROVER_object_whole(dst))

because the loop assigns to the array pointed to by dst, not the value of the dst pointer itself.

With that correction, the proof is OK in a reasonable time.

BUT... that error in the assigns clause should be reported with an easy-to-understand error message, not a giant runtime and/or non-termination of Z3, so still a problem to fix here.

@rod-chapman
Copy link
Collaborator Author

This might be the same problem as #8365

@rod-chapman
Copy link
Collaborator Author

Fixed, so close

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
aws Bugs or features of importance to AWS CBMC users
Projects
None yet
Development

No branches or pull requests

3 participants