runtimeverification / runtimeverification/mir-semantics
Add simplifications for plausible custom overflow criteria
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 52
- Forks
- 5
- PR merge metrics
- No merged PRs in 30d
Description
The current program cannot currently be proven by kmir:
pub fn check_checked_add(u1: u64, u2: u64) {
let result = u1.checked_add(u2);
if u64::MAX - u2 < u1 {
assert!(result.is_none());
} else {
assert!(result.is_some());
}
}
The reason is that the overflow criterion used for checked_add is (u1 + u2) & (2^64 - 1) == u1 + u2, and the SMT solver cannot conclude that in this case (2^64 - 1) - u2 < u1 is false.
While the criterion u1.checked_add(u2).is_none() can be used instead in the use case where this comes from, a few suitable lemmas should be added to cover the MAX - .. subtraction way , and other plausible non-standard ways, to check for overflows.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with kmir's checked_add overflow criterion and the handling of SMT simplifications. Trace how the existing criterion is encoded, then identify where lemmas for MAX-u2<u1 and other plausible overflow checks belong. Done means the shown check_checked_add example can be proven and the additional non-standard criteria are covered.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100