Skip to content

Latest commit

 

History

History
312 lines (273 loc) · 15.7 KB

PROOF-NEEDS.adoc

File metadata and controls

312 lines (273 loc) · 15.7 KB

Proof status: panic-attack

This file records each proof obligation in panic-attack, the verifier it belongs to, and its status. The rules are the estate proof policy, standards/3-practice/PROOF-POLICY.adoc at 9bdf864cc7f2c8e24b4df84bf00d04158eee3ad5. Statuses use its closed §5 vocabulary: PROVEN, PROVEN-WITH-AXIOMS, TESTED, ASSUMED, OPEN.

None of these obligations is a theory theorem (§1), so none carries a Proof Witness Grade.

Receipts (2026-11-09). Until this date no CI job type-checked src/abi/, and as committed none of the five modules checked: their module names did not match their paths, Types.idr and Stripping.idr had syntax errors, and Stripping.idr’s main theorem did not type-check at all. The ✅ marks below therefore had no receipt before that date. Each module is now checked on every PR by the `idris-abi job in .github/workflows/proven-tests.yml (scripts/ci/check-idris-abi.sh, Idris2 0.7.0, %default total, no believe_me, assert_total, assert_smaller, postulate or idris_crash). PROOF-POLICY §6 deviation, state open: Idris2 is built from its v0.7.0 tag, because the repo’s Guix manifest and container do not provide it.

  • src/abi/*.idr: 4 files — Types.idr, ClassificationSoundness.idr (PA2 ✅ 2026-04-11), Stripping.idr (PROOF-PROGRAMME Layer 1.0 line-comment slice: claimed 2026-06-02 but never checked; re-proved and checked 2026-11-09), AttestationUnforgeability.idr (PROOF-PROGRAMME §3.2 ✅ 2026-06-04 — conditional unforgeability from Ed25519 EUF-CMA + chain-hash collision-resistance hypotheses)

  • Dangerous patterns: 0 in own code (3 references are in the analyzer that DETECTS believe_me in other repos); 282 unwrap() calls

  • LOC: ~31,700 (Rust)

  • ABI layer: Idris2 with completeness + soundness proofs + Layer-1.0 stripping foundation

Where each kind of obligation belongs

  • Behaviour of first-party Rust code (stripping, reachability, taint propagation, dispatch): Creusot with Pearlite contracts, and Verus, on the implementation (§1.2). An Idris2 model of a Rust function is not evidence that the function is correct (§1, §2.2).

  • Interfaces, ABI encodings and cross-language protocols (the attestation chain, the C integer encodings): Idris2.

  • Statements true of any implementation (for example, a taint lattice and its fixed point stated abstractly): Agda, rechecked in Rocq and Lean (§2).

No Kani obligation arises (§4.1). With unsafe_code forbidden, cargo clippy --lib --bins --tests --benches --all-features — -F unsafe_code compiles at f2a6a70eaec0cb02331e3264e05f185b5faab0f7. The only unsafe is in examples/vulnerable_program.rs, a deliberately buggy program that exists to be scanned.

Receipt for the Idris2 modules

  • Checker: Idris2 0.7.0, the version proven-tests.yml pins, built from tag v0.7.0 (27780073c8631826d846499840b3857d9b9a4fd5) on Chez Scheme 9.5.8.

  • Source: src/abi/*.idr as committed. Stripping.idr is the re-proof from #281 (see the ledger row below).

  • Invocation: the modules are named PanicAttack.ABI.<M> but live in src/abi/, so idris2 --check src/abi/<M>.idr fails on a module-name mismatch from any directory. scripts/ci/check-idris-abi.sh stages the committed files at PanicAttack/ABI/<M>.idr as links and checks those. A pass is exit 0 and no Error: line, because idris2 --check can exit 0 while printing an error.

  • Result: all five modules pass. Every module sets %default total and uses no believe_me, assert_total, assert_smaller, postulate or idris_crash.

  • Negative controls: against this PR’s earlier Stripping.idr (3dc4728), a planted false lemma and a planted non-terminating definition were both rejected, so the check can fail.

  • Gate: the idris-abi job in .github/workflows/proven-tests.yml runs this check on every PR and blocks on failure (#281). The statuses here rest on that job’s receipt for the commit in question; it passed on main at 36f1055.

Ledger

Obligation Artefact Status Trust boundary and notes

Severity order: Low < Medium < High < Critical is a total order; sevMax is an upper bound; the numeric encoding is monotone (PA2)

src/abi/ClassificationSoundness.idr

PROVEN (model)

The model’s Severity matches the variant names and order of src/types.rs; that correspondence is ASSUMED (a hand transcription). The Rust order itself comes from #[derive(PartialOrd, Ord)].

Line-comment stripping is idempotent: strip (strip s) = strip s

src/abi/Stripping.idr

PROVEN (model)

Re-proved 2026-11-09. The 2026-06-02 proof (issue #113) never type-checked: its // case relied on reductions that do not hold for a variable character, and it used decEq without importing it. The new proof shows stripLineCommentsIdempotent (stripping twice equals stripping once) through two facts: stripping is the identity on text with no // (stripIsIdOnClean), and the strippers' output has no // (stripIsClean/bodyIsClean, by mutual induction). bodyIsFixedPoint follows. The strippers are restated with explicit Bool tests. An exhaustive differential run over every string of length up to 9 on {/, x, \n} (29,524 inputs) found no difference from the previous definitions. A mutant that blanks with / instead of a space is rejected. Nine closed sanity theorems, including two comments on different lines and ///.

The model now agrees with strip_proof_comments(s, "//", None), the slice it models. The compiled model and the Rust function give the same output on every string of length at most 9 over /, newline, x and space (349,525 inputs, local run). In CI, the_line_comment_slice_matches_the_idris_model re-checks a Rust transcription of the model’s equations up to length 8. Correspondence on that slice is therefore TESTED, with those bounds, not ASSUMED. Block comments, nesting and string literals are not modelled. Before the single-pass rewrite they disagreed: on //x the model gave three spaces and Rust gave the empty string.

strip_proof_comments blanks comments in place. The output has the input’s byte length; every byte outside a comment, and every newline, is unchanged; other comment bytes become spaces. Stripping is idempotent. Whichever comment opens first wins, and block comments nest.

src/assail/analyzer.rs, module strip_proof_comments_tests

TESTED

Exhaustive over bounded inputs, for the marker sets the analyzers pass: // with /* /, -- with /- -/, -- with {- -}, ( *) alone, and // alone. Each runs every string over a 4-letter alphabet up to length 8 (87,381 inputs) or a 5-letter alphabet up to length 7 (97,656 inputs). Each alphabet spells the markers, plus a newline and an ordinary character. The three counterexamples in the open obligations are regression tests, as are nesting, unterminated blocks and multibyte text.

Planted faults, all caught:

* the previous two-phase function; * deleting comment text instead of blanking it; * blanking that drops a newline; * one space per character instead of per byte; * no nesting; * an unterminated block that keeps code.

One mutant, a line comment that also consumes its newline, is equivalent: the newline is kept and the scan resumes after it, so no test can tell them apart.

Attestation chain: integrity, authenticity, non-repudiation

src/abi/AttestationUnforgeability.idr

PROVEN (model), relative to the ASSUMED hypotheses listed here

The module’s parameters block assumes:

* chainCR: the chain hash is injective. * sigCorrect: an honest signature verifies. * sigBindsMessage: a signature verifies only on the message signed. * sigOnlySigner: for every verifying signature there is a secret key whose public key is the verifying key and whose signature on that digest is that signature.

sigOnlySigner says such a key exists. It says nothing about who produced the signature, so authenticity inherits that limit: it shows the seal equals one a matching key would make, not that the key holder made it. chainCR and sigOnlySigner are idealisations, stronger than collision resistance and EUF-CMA, and false of any real fixed-length hash or signature scheme. So these are theorems of a symbolic (Dolev-Yao style) model, not a computational security reduction. Model to src/attestation/: ASSUMED. A computational proof is not claimed.

Analyzer routing (PA1). (a) Every language analyzer in analyzer.rs is reached by some language. (b) No language falls back to the generic analyzer while a dedicated one exists for it. (c) Cross-language checks run exactly on non-configuration content, and on scripts embedded in configuration. (d) The README’s language counts equal the languages the table supports.

src/assail/routing.rs: route, Route::analyzer, runs_cross_language and their tests

TESTED

The dispatch in analyze_inner matches on route(file_lang), so the table is the code that runs, not a model of it. route and the dispatch are exhaustive matches with no wildcard, so rustc makes every language and every route explicit. The tests run over all 52 Language variants (Language::ALL, kept complete by an exhaustive ordinal match). (a) and (b) compare the table with the analyzer methods found in the source. (c) scans a Justfile and a Lua file end to end. Each test was seen to fail on a planted fault: an unrouted analyzer, Java sent to the generic analyzer, cross-language checks forced on, and the README’s stale count of 49.

The cross-language checks blank // comments only in languages where // is a comment (slash_line_comments, an exhaustive table beside route). Blanking every file used to cut unquoted URLs in shell scripts and Justfile recipes, a recall gap found while testing (c). (c)'s test now uses an unquoted URL, and slash_comment_tests checks a shell script and a Rust doc comment. Blanking every language, and blanking none, were each seen to fail those tests. Languages whose comment syntax the table does not record keep the earlier blanking.

Routing is not coverage: Language::Unknown goes to InputAdapter, and a file there with no configuration adapter is marked unsupported in the coverage ledger and skipped. So (a) and (b) say which analyzer each language reaches, not that every file is analysed.

This replaces the Idris2 PatternCompleteness.idr, which was vacuous (GenericAnalyzer inhabited its witness for every language), stale (50 of 52 languages) and partly false (it said cross-language checks always run). It is retired.

Declarations for the ABI-facing types and their C integer encodings

src/abi/Types.idr

No theorem

Repaired in 3dc4728 so it compiles. It contains no proof and nothing imports it. Drift: its Severity is Info / Warning / Error / Critical where src/types.rs has Low / Medium / High / Critical, and LangId is bounded at 47 against 52 variants.

Hexad JSON round-trip is the identity

src/storage/mod.rs, hexad_json_roundtrip_is_identity (proptest)

TESTED

A serialize, deserialize, serialize round trip on proptest-generated hexads, compared as serde_json::Value. Bounds: proptest’s default 256 cases (the repository sets no override). id and program_path are 0 to 48 characters from [A-Za-z0-9:_./-]; language 0 to 12 lowercase letters; version 1 to 8 characters from [0-9.]; the four counts are below 10,000; robustness_score is in [0, 1]; categories holds 0 to 5 strings of 1 to 16 letters; attestation_hash is absent or up to 64 hex digits. Fixed, not generated: schema, created_at, tool, and document ({"weak_points": [], "n": total}), and the migration, finding, campaign and crosslang facets are all None. It does not call write_*_hexad or load_hexad_dir, so on-disk persistence is a separate obligation. The gateway octad projection is lossy by design, so this does not establish a faithful hexad-to-octad map.

Model-checked (TESTED, bounded)

Obligation Artefact Status and bounds

Generation-publish protocol P1–P3 (prototype, src/publish.rs; design docs/design/GENERATION-PUBLISH.adoc)

verification/proofs/tlaplus/GenerationPublish.tla (TLC 2.19, tla2tools v1.7.4, run by verify.yml job tlaplus) and tests/publish_model.rs (independent explicit-state checker)

TESTED: up to 3 writers, 1 reader, 2 files, crash at every writer step, collection of crashed and live writers' partial generations, keep 0 and 1. P1 (CURRENT names a complete generation), P2 (never moves backwards) and P3 (manifest reader never fails) hold. P4 (mirrors consistent once quiet) holds without crashes and fails after a crash, the documented limit. Three mutants each violate P1 or P2, so the invariants are not vacuous. PROOF-POLICY §4 exception: a concurrency protocol over crash interleavings, which Creusot and Verus do not state. §6 deviation (open): TLC is fetched from its release, digest-checked, because neither Guix nor the container provides it yet.

Open obligations

Obligation Verifier (§1, §1.2) Notes

Generation publish: pure decisions (src/publish.rs). The supersede comparison and the collect selection never remove the current or a newer generation, and keep the keep newest older ones

Creusot/Pearlite and Verus (§1.2)

OPEN. The model check above covers the protocol, not the Rust code; these contracts tie the implementation to P1 and P2.

Prove the strip_proof_comments properties in the ledger for all inputs

Creusot/Pearlite and Verus

The single-pass rewrite makes both properties true of the implementation; the ledger row has them TESTED within bounds. Pearlite contracts can state them directly: equal length, the per-byte relation, and idempotence. Three counterexamples held of the previous two-phase function and are now regression tests:

* Not idempotent: a//x/b/c gave a/b/c, and a second pass gave ac. * Positions moved: a/x/b gave ab, moving b from offset 6 to 1. * Ordering bug: block comments were stripped before line comments, so a block opener inside a line comment swallowed the code after it. code // see /* note, then hidden();, then */ tail, gave code `. The callers that pass both a line and a block marker were affected: `analyze_rust, is_rust_ffi_safe_wrapper, analyze_idris, analyze_lean and analyze_agda. In the Idris, Lean and Agda ProofDrift detectors such a comment could hide a later sorry, believe_me or postulate.

The function does not know about string literals. The Rust and Zig callers blank strings first; the Lean, Agda, Idris, Coq and Isabelle callers do not, so a comment marker inside a string literal there still starts a comment. The Idris2 model’s remaining slices (block comments, strings, composition; issue #114) are optional once the implementation proof exists.

Patch Bridge reachability is sound: no reachable dependency is classified as phantom

Creusot/Pearlite and Verus

src/bridge/reachability.rs. A missed reachable dependency is a security gap.

Kanren taint analysis tracks every tainted flow

Creusot/Pearlite and Verus; Agda for the abstract theory

Any implementation-independent statement (the lattice, monotonicity, the fixed point) is theory and belongs in Agda with Rocq and Lean rechecks. Its realisation in src/kanren/ is a Rust obligation.

Prove PA1 (a) to (c) on route and runs_cross_language

Creusot/Pearlite and Verus

Pearlite contracts on the two functions, proved by both verifiers. The tests above are exhaustive over a finite enum, but they are tests, and (a) reads the source with a pattern match. (d) is a documentation check and stays a test.