Skip to content
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

Basic assigns clause implementation for function contracts #2594

Closed
JustusAdam opened this issue Jul 10, 2023 · 0 comments · Fixed by #2800
Closed

Basic assigns clause implementation for function contracts #2594

JustusAdam opened this issue Jul 10, 2023 · 0 comments · Fixed by #2800
Assignees

Comments

@JustusAdam
Copy link
Contributor

JustusAdam commented Jul 10, 2023

CBMC's default assumption for a function that receives a pointer is that no modification of the pointer or its target is performed. This means that for functions that receive (and mutate) &mut T we need to specify an assigns clause in addition to requires and ensures.

In the first iteration we propose to add a simple kani::assigns macro which takes a list of lvalues that are lowered the usual way and passed onto CBMC as a __CPROVER_assigns clause.

In addition to add some basic support for arrays we propose using slice syntax [..] to denote that an entire array or the pointed-to range of a pointer might be assigned to.

Here is an example of what this looks like

#[post(self.len() == 0)]
#[kani::assigns((*self).keys.buf.ptr.pointer.pointer[..], (*self).keys.buf.cap, (*self).keys.len)]
#[kani::assigns((*self).values.buf.ptr.pointer.pointer[..], (*self).values.buf.cap, (*self).values.len)]
pub fn clear(&mut self) {
    self.keys.clear();
    self.values.clear();
}

Note this is very basic and leaks private detail, e.g. the lvalues assigns can refer to private fields

@JustusAdam JustusAdam self-assigned this Jul 10, 2023
@JustusAdam JustusAdam added this to the Function Contracts MVP milestone Jul 10, 2023
@JustusAdam JustusAdam changed the title Basic assigns contract implementation Basic assigns clause implementation for function contracts Jul 10, 2023
@JustusAdam JustusAdam reopened this Oct 2, 2023
@celinval celinval assigned celinval and unassigned celinval Dec 4, 2023
feliperodri added a commit that referenced this issue Feb 2, 2024
Extends the function contract functionality with a `modifies` clause. 

The design is different from #2594 but serves a similar purpose. The
`modifies` clause allows the user to specify which parts of a structure
a function may assign to. Essentially refining the `mut` annotation.

We allow arbitrary (side-effect free) expressions in the `modifies`
clause. The expressions are evaluated as part of the preconditions and
passed to the function-under-verification as additional arguments. CBMC
is then instructed to check that those locations are assigned. Aliasing
means that this also adds the location in the original structure to the
write set.

Each expression must return a pointer to a value that implements
`Arbitrary`. On replacement we then simply assign `*ptr = kani::any()`,
relying again on aliasing to update the original structure.

Additional tests for the new functionality are provided.

Resolves #2594 

## Open Questions

### API divergence from CBMC (accepted)

The current design goes roughly as follows: We start with a `modifies`
annotation on a function

```rs
#[modifies(obj.some_expr())]
fn target(obj: ...) { ... }
```

And from this we generate code to the effect of (simplified here)

```rs
fn target_check(obj: ...) {
    // Undo the lifetime entanglements
    let modified_1 = std::mem::transmute::<&'a _, &'b _>(obj.some_expr());
    target_wrapper(obj, modified_1);
}

#[cbmc::assigns(*modified_1)]
fn target_wrapper(obj: ..., modified_1: &impl kani::Arbitrary) { ... }
```

Unlike CBMC we expect `obj.some_expr()` to be of a **pointer type**
(`*const`, `*mut`, `&mut` or `&`) that points to the object which is
target of the modification. So if we had a `t : &mut T` that was
modified, CBMC would expect its assigns clause to say `*t`, but we
expect `t` (no dereference).

The reason is that the code we generate uses the workaround of creating
an alias to whichever part of `obj` is modified and registers the alias
with CBMC (thereby registering the original also). If we generated code
where the right side of `let modified_1 =` is not of pointer type, then
the object is moved to the stack and the aliasing destroyed.

The open questions is whether we are happy with this change in API.
(Yes)

### Test cases when expressions are used in the clause.

With more complex expressions in the modifies clause it becomes hard to
define good test cases because they reference generated code as in this
case:

```rs
#[kani::requires(**ptr < 100)]
#[kani::modifies(ptr.as_ref())]
fn modify(ptr: &mut Box<u32>) {
    *ptr.as_mut() += 1;
}
```

This passes (as it should) and when commenting out the `modifies` clause
we get this error:

```
Check 56: modify_wrapper_895c4e.assigns.2
	 - Status: FAILURE
	 - Description: "Check that *var_2 is assignable"
	 - Location: assigns_expr_pass.rs:8:5 in function modify_wrapper_895c4e
```

The information in this error is very non-specific, hard to read and
brittle. How should we define robust "expected" test cases for such
errors?

### Corner Cases / Future Improvements

- #2907 
- #2908 
- #2909 

## TODOs

- [ ] Test Cases where the clause contains
  - [x] `Rc` + (`RefCell` or `unsafe`) (see #2907)
  - [x] Fields
  - [x] Statement expressions
  - [x] `Vec` (see #2909)
  - [ ] Fat pointers
- [ ] update contracts documentation
- [x] Make sure the wrapper arguments are unique.
- [x] Ensure `nondet-static-exclude` always uses the correct filepath
(relative or absolute)
- [ ] Test case for multiple `modifies` clauses.

By submitting this pull request, I confirm that my contribution is made
under the terms of the Apache 2.0 and MIT licenses.

---------

Co-authored-by: Zyad Hassan <88045115+zhassan-aws@users.noreply.github.com>
Co-authored-by: Felipe R. Monteiro <rms.felipe@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
No open projects
Status: Done
Development

Successfully merging a pull request may close this issue.

2 participants