Verify the safety of slice functions (challenge #17)#603
Open
MavenRain wants to merge 5 commits into
Open
Conversation
Safety contracts + Kani proof_for_contract harnesses for split_at_unchecked, split_at_mut_unchecked, and swap_unchecked (12 harnesses, all pass) via the proof_for_contract(<[T]>::method) + kani::slice::any_slice_of_array pattern.
…ns (challenge model-checking#17) Completes the unsafe-function half of challenge model-checking#17: get_unchecked/_mut (#[requires(N != 0 && len % N == 0)] via proof_for_contract per concrete (T,N)), and get_disjoint_unchecked_mut (plain proof + assume: in-bounds + pairwise distinct). 39 harnesses, all pass. With tranche 1 and the existing align_to/ align_to_mut, all 10 unsafe slice functions in the challenge now verify. Signed-off-by: Onyeka Obi <softwareengineerasaservant@isurvivable.cv>
…_chunk/ first_chunk_mut, last_chunk/last_chunk_mut, split_first_chunk/_mut, split_last_chunk/_mut, split_at_checked/split_at_mut_checked. 24 harnesses over representative element types and chunk sizes (incl. the N=0 edge), all pass; each uses a symbolic-length slice so both the None and cast/split branches are covered. No loops, so no unwind bounds. Signed-off-by: Onyeka Obi <softwareengineerasaservant@isurvivable.cv>
… (challenge model-checking#17) No-UB harnesses for the O(1)/log/N-bounded safe abstractions: as_chunks/_mut/ as_rchunks, as_flattened/_mut, as_simd/_mut (replay align_to), binary_search_by (logarithmic loop, unwind 7), get_disjoint_mut + get_disjoint_check_valid (const-N loops). 19 harnesses, all pass. Brings challenge model-checking#17 to 30/37 (all 10 unsafe + 20 of 26 safe). Signed-off-by: Onyeka Obi <softwareengineerasaservant@isurvivable.cv>
…el-checking#17) -- 37/37 copy_from_slice, copy_within, swap_with_slice, partition_dedup_by (symbolic length, small backing + #[kani::unwind]); rotate_left, rotate_right (concrete (length, amount) configs with symbolic values -- a symbolic rotation amount makes ptr_rotate's symbolic-size memcpy intractable >6GB here, so rotate is proven per-config). 16 harnesses, all pass. Completes all 37 functions in challenge model-checking#17 (10 unsafe + 27 safe abstractions). Signed-off-by: Onyeka Obi <softwareengineerasaservant@isurvivable.cv>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Challenge 17: Verify the safety of
slicefunctionsResolves the verification targets in
doc/src/challenges/0017-slice.md(tracking #281).This adds Kani harnesses for all 37 functions in the challenge: the 10 unsafe
functions (with safety contracts) and the 27 safe abstractions (proven UB-free).
Unsafe functions (contracts +
proof_for_contract)get_unchecked/get_unchecked_mutswap_uncheckeda < len && b < len#[requires]+kani::modifies(self)split_at_unchecked/split_at_mut_uncheckedmid <= len#[requires]as_chunks_unchecked/as_chunks_unchecked_mutN != 0 && len % N == 0#[requires], per concrete<[T]>::…::<N>align_to/align_to_mutmain)get_disjoint_unchecked_mutSafe abstractions (proven free of UB)
first_chunk(_mut),last_chunk(_mut),split_first_chunk(_mut),split_last_chunk(_mut),split_at_checked,split_at_mut_checked,as_chunks,as_chunks_mut,as_rchunks,as_flattened,as_flattened_mut,as_simd,as_simd_mut,binary_search_by,get_disjoint_mut,get_disjoint_check_valid,copy_from_slice,copy_within,swap_with_slice,partition_dedup_by,rotate_left,rotate_right(andreverse,pre-existing on
main).Approach
#[cfg(kani)] mod verifyat the end oflibrary/core/src/slice/mod.rs, following the establishedalign_topattern.#[kani::proof_for_contract(<[T]>::method)](incl. const-generic turbofish<[T]>::as_chunks_unchecked::<N>), spread over representative element types(
(),u8,u64,char, …) and chunk sizes — source-generic, proof-concrete.kani::slice::any_slice_of_array(_mut)helper (the same "unbounded" encoding
align_touses).binary_search_by,rotate_*,copy_*,swap_with_slice,partition_dedup_by) carry an explicit#[kani::unwind(K)]— a verifiedunwinding assertion, not an assumption.
Honest caveats (please review)
align_toharnesses, the symbolicslice length ranges over
[0, ARR_SIZE]for a fixedARR_SIZE. The per-index/-elementsafety obligation is structurally identical at every position, so a modest bound
exercises it, but coverage is bounded rather than literally unbounded.
get_unchecked,get_unchecked_mut,get_disjoint_*). Thesafety precondition is index-type-specific (
idx < lenforusize; range bounds forRange) and cannot be expressed as one#[requires]over the generic indexI(a contract closure only borrows its args, and
SliceIndexexposes no genericin-bounds predicate). These are proven with plain
#[kani::proof]at concrete indextypes, with the documented caller obligation established by
kani::assume. Same propertythe contract would express; happy to adjust if you'd prefer a different encoding.
rotate_left/rotate_rightare per-config, not symbolic-length. A symbolicrotation amount makes
ptr_rotateperform symbolic-sizememcpys at a symbolic splitpoint and explore its block-swap/juggling paths; CBMC exceeded a 6 GB budget (and kept
climbing) even at length 4 on the dev machine. They are instead verified over
representative concrete
(length, amount)configurations with symbolic element values(a single concrete
ptr_rotatepath). A higher-memory environment could attempt thefully symbolic version.
swap_uncheckedomits the ZST instantiation.kani::modifies(self)over azero-size slice region trips a CBMC contracts-library limitation (
car_set_insert);swapping ZSTs moves zero bytes, so it is trivially safe. The non-ZST instantiations
exercise the actual
ptr::swapwrites.Tooling / disclosure
Verified with the repo's pinned Kani (commit
415ca50,nightly-2025-10-09) viaverify-std. Authored with AI assistance (Claude); all proofs were run and confirmedto pass locally (sequential CBMC).