Skip to content

Ruling needed: "mutating immutable bytes" in Kani-based solutions #733

Open

Description

@feliperodri

24 challenge specs require proofs to rule out "mutating immutable bytes". Kani has no aliasing model (model-checking/kani#314), so it can't check this in general. Ch6, Ch9, Ch11 and Ch14 were resolved with Kani-only solutions anyway. #638 (Ch13) and #582 (Ch26) are waiting on a decision.

Using Ch13 (CStr) as the example, the property splits into three obligations. I checked each one locally with Kani 6ce55b9, VeriFast 26.10 and Verus 0.2026.10.18:

Obligation Kani VeriFast Verus
1. Methods don't write the bytes they borrow ✅ a contract with no modifies fails on any write ✅ ✅
2. clone_to_uninit's dest doesn't overlap self only with an explicit non-overlap requires (model-checking/kani#5040 would check it automatically) ✅ by construction ✅ by construction
3. After from_ptr, the caller doesn't mutate the bytes while the &'a CStr lives ❌ can't be expressed expressible ✅ a write while the reference is in use is rejected
Runs on the unmodified std file ✅ ❌ blocked by verifast/verifast#1047, and needs 3 edits to compile a copy ❌ code must be rewritten inside verus!

The VeriFast and Verus results come from small models of these functions, not from the real core/src/ffi/c_str.rs.

Covering the property doesn't mean rewriting a Kani solution. Obligations 1 and 2 need at most one extra requires. Obligation 3 would be a separate, small proof: about 20 lines of VeriFast annotations on strlen, from_ptr and clone_to_uninit, once verifast/verifast#1047 is fixed. Verus would need the code rewritten, and it isn't an approved tool yet (#554).

Question for the committee: should we accept a solution that covers everything Kani can express (obligations 1 and 2 here), and treat caller-side obligations like 3 as out of scope? Or should challenges with this criterion require a complementary proof, for example in VeriFast, for those obligations?

Recommendation: accept, which is consistent with Ch6, Ch9, Ch11 and Ch14, and say so in the challenge book. A complementary VeriFast proof for obligations like 3 could then be a separate, optional contribution.

Activity

  1. added theissue type on Oct 21, 2026
  2. added
    QuestionUse for any clarification or general question about the contest
    on Oct 21, 2026
  3. feliperodri commented on Oct 23, 2026

    @feliperodri
    MemberAuthor

    Two more items on the same lists can't be established with Kani today, and two approved PRs already leave them out:

    Proposal: extend the question above to these two items. Accept solutions that cover everything Kani can check, and list data races and invalid values as out of scope for Kani until a tool can establish them. That matches how #683 and #587 were approved, and it settles #582 (Ch26) the same way.

  4. feliperodri commented on Oct 30, 2026

    @feliperodri
    MemberAuthor

    An update from the Kani side: Kani now has an experimental aliasing model, -Z aliasing-checks. It checks Tree Borrows' rules, including writes to immutable bytes, inside each harness. It isn't merged in Kani yet: it's on a branch, and the speed-up it needs (diffblue/cbmc#9238) is merged in CBMC but not yet in a release. I ran the existing harnesses of the challenges above with it, with contracts and harnesses unchanged and the same flags as CI. Kani commit 0e902a603, 2 jobs, 12 GB and 900 s per harness:

    Challenge without the checks with the checks
    Ch11 (292 harnesses) 292 verified, 8 min 292 verified, 2.8 h (median 22 s, ≤ 1.0 GB per harness)
    Ch14 (190 harnesses) 190 verified, 5 min 190 verified, 1.4 h (median 21 s, ≤ 0.5 GB per harness)
    Ch9 (24) 24 verified 15 verified, 9 run out of 12 GB
    Ch6 (96) 96 verified 27 verified, 64 out of memory, 4 time-outs, 1 inconclusive (a call through &dyn, not followed yet)
    Ch13, #638 (14) 14 verified 0 verified, all out of memory
    Ch26, #582 (1332) 1332 verified not run yet: compiling all 1332 at once runs out of memory

    No harness reports aliasing UB.

    A harness that verifies with the checks has no execution that breaks the implemented rules at any byte, among the inputs it allows and under the contract's preconditions. Where the checks can't tell which reference a pointer came from, the result is inconclusive, never a pass. The rules are tested against Miri's own borrow tests: of 165, Kani misses none of the UB Miri reports, and reports none that Miri doesn't. They are not proved equivalent to Miri.

    For Ch11 and Ch14 this covers "mutating immutable bytes" without changing the solutions. Those functions mostly take and return plain values, though, so the code that does real pointer work (Ch6, Ch9, Ch13, Ch26) is where it matters, and that's still blocked on cost. I'm working on that next.

    Where I'd like input: once the inconclusive cases are resolved, would this evidence (tested against Miri, inconclusive rather than unsound where the checks give up) be enough for Kani-based solutions to claim the property? If not, what would be?

  5. patricklam commented on Nov 10, 2026

    @patricklam

    I think the extra VeriFast proof on the side is the most sound solution. There's no reason it has to be in the main challenge, and makes things cleaner in general.

    I am unclear about the extent of the guarantees provided by -Z aliasing-checks. Are they as sound as VeriFast? Or, in other words, does this option check all of the Tree Borrows rules?

    As for the miri checks: am I correct in understanding that miri is going to check for undefined behaviour that is triggered by the inputs given to the code it is asked to run? As in, Miri's borrow tests aren't exhaustive. They do provide additional assurances, which are helpful.

  6. feliperodri commented on Nov 13, 2026

    @feliperodri
    MemberAuthor

    One more item from the same UB lists that Kani-based solutions can't establish in CI today: reading from uninitialized memory (Ch2, Ch13, Ch25 and others list it).

    Proposal: rule on it together with invalid values. Don't block solutions on it now, and ask for -Z uninit-checks runs once those Kani issues are closed.

  7. feliperodri commented on Nov 18, 2026

    @feliperodri
    MemberAuthor

    Update with a concrete case: the Challenge 2 solution (#649), which is otherwise complete. Of the UB items Challenge 2 lists, this is where it stands, and what it would take to close each gap.

    UB item Status in #649
    Invoking UB via intrinsics ✅ checked: every intrinsic's requires is verified
    Dangling or misaligned accesses ✅ checked: out-of-bounds mutants are caught
    Reading uninitialized memory ❌ not checked in CI (see below)
    Mutating immutable bytes ❌ not checked: no aliasing model in Kani main
    Producing an invalid value ❌ not checked in CI (see below)

    Reading uninitialized memory. can_dereference checks initialization only under -Z uninit-checks, which CI doesn't pass. With the flag, 303 of #649's 394 intrinsics::verify harnesses pass. The other 91 stop on constructs Kani's uninit checking doesn't support yet: [MaybeUninit<_>; N] buffers, including Kani's own PointerGenerator (model-checking/kani#5151), and trait-object pointers (model-checking/kani#5166). None of them reports an uninitialized read.

    On other challenges the same flag also hits model-checking/kani#5164 (pure intrinsics), rust-lang#5165 (niche enums) and rust-lang#4852 (a crash). Where it runs, it works: an injected uninitialized read in VecDeque::get passes CI's flags and fails with -Z uninit-checks.

    Once those issues are fixed, adding -Z uninit-checks to CI looks feasible. On the VecDeque harnesses it roughly doubled the run time (90 s to 201 s), so I'd start with a non-blocking CI job to measure the cost before making it required.

    Mutating immutable bytes. Kani has an experimental aliasing model, -Z aliasing-checks, on a branch that isn't merged yet (feliperodri/kani aliasing-contracts), as reported above for Ch11 and Ch14. It's the path to checking this property. It doesn't run on every proof yet: on the symbolic-size buffers of Ch25's VecDeque proofs, CBMC currently crashes in its value-set analysis (value_set.cpp:1595). That's being worked on.

    Producing an invalid value. I ran all 140 of #649's own harnesses with -Z valid-value-checks on Kani main at 0aac16e, the newest commit on this repository's nightly, which includes the fix model-checking/kani#5057:

    On the pinned Kani (c5e65fd) there were 5 invalid-value reports. The 3 extra ones were false positives that rust-lang#5057 fixed.

    So for this solution, none of the three open items has a known violation. They're unestablished because of Kani gaps that are now each tracked by an issue. That's the question for the committee here: accept Kani solutions with these three items stated as not proven, as is done for Ch6, Ch9, Ch11 and Ch14, or require the flags once those Kani issues are fixed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    QuestionUse for any clarification or general question about the contest

    Type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions