-
Notifications
You must be signed in to change notification settings - Fork 99
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
Proof with AnySlice
does not terminate, memory grows unbounded
#2634
Comments
Thanks @arctic-alpaca for the bug report and the testcase. I'm indeed noticing a memory blowup with extern crate kani;
use kani::slice;
fn min(s: &[i32]) -> Option<i32> {
s.iter().min().copied()
}
#[kani::proof]
#[kani::unwind(31)]
#[kani::solver(cadical)]
fn main() {
let s: slice::AnySlice<i32, 30> = slice::any_slice();
let res = min(&s);
assert!(s.len() == 0 || res.is_some());
if let Some(res) = res {
let index: usize = kani::any_where(|i| *i < s.len());
assert!(res <= s[index]);
}
} |
This performance issue might not be directly related to extern crate kani;
fn min(s: &[i32]) -> Option<i32> {
s.iter().min().copied()
}
#[kani::proof]
#[kani::unwind(31)]
#[kani::solver(cadical)]
fn main() {
let s: [i32; 30] = kani::Arbitrary::any_array::<30>();
let res = min(&s);
assert!(s.len() == 0 || res.is_some());
if let Some(res) = res {
let index: usize = kani::any_where(|i| *i < s.len());
assert!(res <= s[index]);
}
} Only adding the last assertion causes CBMC to get stuck in propositional reduction for a while and it triggers the performance bottleneck. |
Adding a proof with #[kani::proof]
fn works1() {
let mut data: [u8; 100] = kani::Arbitrary::any_array::<100>();
let data_start_offset = kani::any();
kani::assume(data_start_offset < 110);
if let Ok(mut to_test) = NewDataBufferMut::<_>::new(&mut data, data_start_offset) {
let _ = to_test.cut_ieee_802_2_snap(kani::any(), kani::any());
NewDataBufferMut::<_>::new(to_test.into_inner(), data_start_offset).unwrap();
}
} |
I might have found two possible work-arounds for this issue while
I'd appreciate feedback whether the verified properties are actually equivalent to |
If you want it to cover the case where the slice spans the whole array, the loop needs to include for i in 0..=SLICE_LENGTH { Otherwise, it looks equivalent. You may also replace the loop with a non-deterministic slice, e.g.: let data: [u8; SLICE_LENGTH] = kani::Arbitrary::any_array::<SLICE_LENGTH>();
let end: usize = kani::any_where(|e| *e <= SLICE_LENGTH);
let slice = data[..end]; Not sure how Kani would perform on this harness compared to the loop-based one. For the record, this is how the old implementation of
This one should be equivalent. |
I missed that, thanks.
That's perfect! It terminates with much more complex proofs than Out of curiosity, wouldn't it be possible to replace the |
With the caveat mentioned in #2759 (which you already noticed).
That would make sense if it continues to have superior performance even after fixing #2759. |
With the release of 0.37.0, the |
Indeed :( If I revert the change to +++ b/library/kani/src/vec.rs
@@ -14,9 +14,10 @@ pub fn any_vec<T, const MAX_LENGTH: usize>() -> Vec<T>
exact if exact == MAX_LENGTH => exact_vec::<T, MAX_LENGTH>(),
_ => {
let mut any_vec = exact_vec::<T, MAX_LENGTH>();
- any_vec.truncate(real_length);
- any_vec.shrink_to_fit();
- assert!(any_vec.capacity() == any_vec.len());
+ //any_vec.truncate(real_length);
+ //any_vec.shrink_to_fit();
+ unsafe { any_vec.set_len(real_length) }
+ //assert!(any_vec.capacity() == any_vec.len());
any_vec
}
} the proof goes through quickly. If you're not worried about the code making illegal accesses to the slice, you can explicitly create the slice, e.g: #[kani::proof]
fn works_slices() {
let mut arr: [u8; SLICE_LENGTH] = kani::any();
let nd_index = kani::any_where(|i| *i <= SLICE_LENGTH);
let slice = &mut arr[..nd_index];
let data_start_offset = kani::any();
kani::assume(data_start_offset < DATA_START_OFFSET);
if let Ok(mut to_test) =
NewDataBufferMut::<_>::new(slice, data_start_offset)
{
let _ = to_test.cut_ieee_802_2_snap(kani::any(), kani::any());
NewDataBufferMut::<_>::new(to_test.into_inner(), data_start_offset).unwrap();
}
} |
Thanks, that's what I'm going to do. Luckily the unsoundness issues doesn't seem to affect safe code. Accessing an index out of slice bounds still fails the proof as expected. |
Deprecate kani::slice::any_slice in Kani 0.38.0 (and the related AnySlice struct), and remove it in a later version. Motivation: The Kani library's `slice::any_slice` API is doing more harm than benefit: it is meant to provide a convenient way for users to generate non-deterministic slices, but its current implementation aims to avoid any unsoundness by making sure that for the non-deterministic slice returned by the API, accessing memory beyond the slice length is flagged as an out-of-bounds access (see #1009 for details). However, in practical scenarios, using it ends up causing memory to blowup for CBMC. Given that users may not care about this type of unsoundness, which is only possible through using a pointer dereference inside an unsafe block (see discussion in #2634). Thus, we should leave it to the user to decide the suitable method for generating slices that fits their verification needs. For example, they can use Kani's alternative API, `any_slice_of_array` that extracts a slice of a non-deterministic start and end from a given array.
Sounds good! We've deprecated |
Hi,
I'm using kani to verify the absence of panics in some network parsing/manipulation code (without unsafe).
With some manipulation functions, using
AnySlice
leads to Kani not terminating and CBMC's memory usage growing until it's killed to prevent OOM.Depending on the function, the memory grows at different speeds but the result is the same. Kani/CBMC does not terminate.
Switching from
AnySlice
to an array withkani::any()
works without issue but does not verify the same properties.The reproduction code contains three proofs, one using
kani::any()
and two usingAnySlice
. The working proof withAnySlice
shows what I initially did to verify the code does not panic. To also verify that the manipulating method produces a valid state, the buffer is parsed (new()
) again. Adding this second parsing triggered the non-terminating behavior. I did encounter this behavior before in other situations but attributed it to being too complex to useAnySlice
so I reduced the scope of the proof. With this, reducing the scope is not possible without losing some property of the proof.Different verifiers or using loop unwinding lead to the same outcome.
The reproduction is not really minimal but I hope this is alright. The memory usage in this example increases very slowly (over multiple hours it slowly used up over 16GiB) but it was the easiest to extract. If helpful, I can link my whole code with a proof where it takes less than 5 min to reach OOM kill.
The text was updated successfully, but these errors were encountered: