Skip to content

Emitted GOTO programs are not reproducible: constant allocations are named after rustc AllocId #4821

Open

Description

@srivatsansamraj

I tried this: compile the same crate twice with the same Kani build and compare the emitted GOTO programs.

$ cd tests/perf/s2n-quic/quic/s2n-quic-core
$ cargo kani --tests --target-dir /tmp/t1 --harness slice::tests::vectored_copy_fuzz_test --keep-temps
$ cargo kani --tests --target-dir /tmp/t2 --harness slice::tests::vectored_copy_fuzz_test --keep-temps
$ goto-instrument --show-symbol-table /tmp/t1/kani/.../*vectored_copy_fuzz_test.symtab.out | grep '^Symbol' > /tmp/s1
$ goto-instrument --show-symbol-table /tmp/t2/kani/.../*vectored_copy_fuzz_test.symtab.out | grep '^Symbol' > /tmp/s2
$ comm -3 <(sort /tmp/s1) <(sort /tmp/s2)
s2n_quic_core.6ebb3df112ec5ac5::s2n_quic_core::AllocId(107, ThreadLocalIndex)
	s2n_quic_core.6ebb3df112ec5ac5::s2n_quic_core::AllocId(121, ThreadLocalIndex)
...

I expected the two programs to be identical.

Instead, the 22 symbols for constant allocations (panic message strings and the like) carry different numbers, and nothing else differs. The name is built in codegen_alloc_pointer (kani-compiler/src/codegen_cprover_gotoc/codegen/operand.rs) as format!("{}::{alloc_id:?}", self.full_crate_name()), so it embeds rustc's AllocId, which depends on the order allocations are created in that compilation. In four single-harness compilations three were byte-identical and one differed in 16 names; in four whole-crate compilations (the perf suite's cargo kani --tests) all four differed.

The effect shows up in the perf-benchcomp CI job: slice::tests::vectored_copy_fuzz_test uses kissat, and CBMC's reachability-check loop calls the external solver once per model until every reachable goal is covered. The renamed symbols change the variable order, the solver picks different models, and the same program needs 5, 7 or 8 calls of about 21 s each depending on the compilation: 106 s to 173 s of solver time with identical VCC and step counts. Running CBMC directly on the compiled programs repeats each program's count (8 and 8, 5 and 5, 7), so the program decides it. Two of these compilations side by side is a 1.64x "regression" under error_on_regression; #4801's CI run tripped on exactly this harness at 1.60x, and the same run of the job on two compilations of one main commit gave 173 s vs 106 s. #1693 is the same harness swinging for a related reason. The built-in incremental solvers do not show it (the checksum harness, CaDiCaL, is six rounds every time).

A name that does not depend on allocation order would make the output reproducible; a stable hash of the allocation's bytes, relocations and mutability with the crate name is one option, as long as distinct mutable allocations keep distinct names.

Kani version: 0.68.0 at e5f2e75, nightly-2026-08-21, CBMC 6.11.0, kissat 4.0.1 (Ubuntu 22.04).

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

    Z-Kani CompilerIssues that require some changes to the compiler[C] BugThis is a bug. Something isn't working.

    Type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions