Repository navigation
TOMBSTONE v0.2.0 — C99 Proofs & Verified Toolchain Reuse
TOMBSTONE v0.2.0 consolidates the formal-verification work introduced across Phases 8–20 and adds the first OPT-inspired CI reuse implementation.
The verification programme targets the actual C99 implementation, records the assumptions behind each result, and preserves unsuccessful attempts alongside accepted evidence. Automated gates reject missing, incomplete, stale, or incorrectly identified proof results.
Changes since v0.1.0:
-
Release provenance and reproducible source assets — PR #9
Added post-merge CI records, an exact source-commit identity, and SHA-256 manifests for the original v0.1.0 source release. Packaging independently generates the archive twice and requires identical bytes. These assets remain tied to the immutable v0.1.0 release. -
Phase 8: bounded symbolic verification — PR #10
Introduced CBMC checks that directly include the production C99 deletion engine. Symbolic inputs of up to four bytes exercise splice relationships, return statuses, observation classification, and unchanged outputs on failure. A verification-only hash-success stub keeps the SHA-provider assumption explicit. -
Phase 9: unbounded splice-relation checks — PR #11
Added mathematical contracts and loop invariants to the actualsplice_equalhelper used by the witness API. Frama-C/WP checks exact relationships between before, removed, and after buffers for arbitrary valid lengths, including runtime safety and the absence of caller-memory writes. -
Phase 10: witness validation before hashing — PR #12
Isolated and verified the production helper that checks arguments, sizes, offsets, and length mismatches before hashing begins. Native fault-injection tests separately exercise all three SHA failure sites and check that unsuccessful calls preserve the caller’s output. -
Phase 11: modular public-witness verification — PR #13
Added modular WP checks for fingerprint collection, private witness staging, and the publictb_witness_deletefunction, recording 88/88 discharged obligations. The implementation commits output only after successful staging. These results retain explicit external SHA-provider and toolchain-model assumptions. -
Phase 12: actual OpenSSL provider failure evidence — PR #14
Exercised the real C99 OpenSSL wrapper with injected allocation, initialization, update, and finalization failures. Tests check error propagation, output preservation, and context cleanup. An assumption ledger distinguishes these observed behaviours from outstanding universal provider proofs. -
Phase 13: optional pinned HACL backend — PR #19*
Added an optional HACL* SHA2-256 backend whose upstream source files are pinned to an immutable revision. Adapter checks, failure injection, and provider-parity tests compare its behaviour with the existing implementation. OpenSSL remains the default; upstream HACL* verification does not automatically verify TOMBSTONE’s integration. -
Phase 14: production receipt-parser checks — PR #20
Added contracts for actual C99 decimal accumulation and duplicate-field detection, plus bounded parser checks and adversarial receipt tests. Coverage includes numeric boundaries, malformed inputs, output preservation, canonical fixture bytes, and chain tampering. Complete parser and canonical-encoding proofs remain separate obligations. -
Phase 15: Rust ABI and executable evidence — PR #21
Compared actual C99 layouts, alignments, enum values, and status codes with the Rust FFI representation. Added error-output tests, input-limit checks, and independent executable rebuild comparisons across supported Linux compiler, architecture, and provider combinations. This records target-specific evidence without claiming a compiler-correctness proof. -
Phase 16: external anchors and target assumptions — PR #22
Addedverify-chain --trusted-head-filefor checking a chain against a separately retained commitment. Strict file and syntax validation accompanies an explicit target/trust ledger. The supplied anchor is never treated as trustworthy merely because it matches the receipts being checked. -
Phase 17: chain-rejection and anchor checks — PR #24
Extended direct-source verification of chain argument checks and invalid-genesis rejection before hashing. Native replay covers frozen receipt orderings, chain prefixes, incorrect links, digest tampering, and trusted-head mismatches across GCC/Clang, x86-64/ARM64, and both SHA providers. -
Phase 18: unbounded receipt-chain verification — PR #26
Added a conditional WP proof of the actual chain verifier for arbitrary valid nonempty chain lengths. The 54/54-obligation theorem covers genesis, predecessor-link equality, optional trusted-head comparison, and caller-memory preservation under explicitly stated helper contracts. -
Phase 19: actual receipt-helper refinement — PR #27
Targeted the realequal32andcalculate_hashbodies to refine assumptions used by the chain proof. Verification covers byte comparison and hash-helper control flow, with separate error-path checks. Libc comparison semantics, formatter behaviour, and streaming SHA-provider obligations remain explicit premises. -
P19-03: caller-memory composition and ownership — PR #29
Connected helper and chain contracts through a separately named caller-memory theorem and a model of provider ownership, call ordering, and cleanup. This accommodates private provider-state effects without silently weakening the original Phase 18 theorem or claiming that concrete backend heap behaviour has been fully proved. -
Phase 20: receipt validation, formatting, and model correction — PR #30
Added verification of actual receipt validators, formatter bounds and memory effects, both hex-encoder bodies, and their shared helper/chain composition. An isolated correction addresses the reproduced Frama-C Bytes-model inconsistency. Fresh contradiction checks, affected library-lemma replays, and semantic negative controls guard acceptance while historical failures remain preserved. -
Verified toolchain reuse and measured CI savings — PR #31
Added restoration of an independently pinned toolchain after checking its producer, dependency identities, archive digests, and complete file manifest. Missing approved artifacts or changed inputs require a cold build; integrity failures stop acceptance. A forced-cold path remains available, and every canary and proof still runs afresh.
Verification at the final reviewed PR head, 1d25cb602d95d92265d24ffeee625c9a702f27f8, completed:
- 22/22 workflows passed.
- 14/14 Phase 20 jobs passed.
- 1,392/1,392 positive WP/runtime-error obligations discharged under the documented premises.
- All three designated semantic negative controls rejected their deliberately incorrect implementations.
- Original Phase 18/19 theorem replays completed without changing their contracts.
- 34 new reuse and replay-binding regression tests passed alongside the existing 117 evidence-tamper checks.
Three cold/reuse benchmark pairs measured:
| Preparation mode | Median preparation plus fresh canaries |
|---|---|
| Cold build | 65.469 seconds |
| Verified reuse | 54.044 seconds |
This is a 17.45% reduction, saving approximately 11.4 seconds per preparation. Every trial executed fresh canaries and produced matching semantic outcomes. The measurement excludes the shared container-image download and does not represent whole-CI speedup. Proof-result caching remains disabled.
The public C99 ABI and frozen v1 receipt fixtures are preserved. The existing v0.1.0 release remains immutable. TOMBSTONE remains an offline C99 evidence engine with Rust interfaces, licensed under Apache-2.0.
Formal results remain conditional on their documented libc, provider, and memory-model premises. Actual SHA-provider refinement, complete canonical-JSON/parser semantics, Rust ownership refinement, and source-to-executable correctness remain open. Model regressions do not establish general toolchain soundness. These results do not prove historical deletion, trusted identity or time, or secure erasure.
Release source: 881e7db29054a02273b0e924b08409a777ce42ea
Contributions: @EmergentMonk
Executed Phase 20 proofs · Reuse benchmark · Full changelog: v0.1.0 → v0.2.0