For each claim in “Verifying RustCrypto’s Fixsliced AES-128 in ACL2: An Aeneas Backend and an Executable MIR Semantics” that a careful reader might meet with “where is that justified?” or “where in the code is that done?” — the answer, with file, line, theorem name, and where possible a command that checks it.
Provenance of this document
Drafted by Claude Fable 5 (Anthropic) under the author’s direction, as was the work it explains; the author reviews and maintains it. File paths, line numbers, theorem names, and counts were re-verified mechanically against the pinned sources below. Additional proofreading by GPT-6 Astra (OpenAI).
Aeneas extraction and equivalence proofs (§1–§5). Verified 2026-09-05 against commit 23cf8c8 of branch acl2-backend of bendyarm/aeneas. The pinned toolchain that rebuilds it from scratch is bendyarm/aeneas-acl2-devenv: its pins.env fixes the Charon fork, Aeneas branch, and ACL2 image; the published image is ghcr.io/bendyarm/aeneas-acl2-dev; the v1.0.0 release is archived on Zenodo, DOI 10.5281/zenodo.22365956.
MIR interpreter, importer, and AES harness (§6). Verified 2026-10-28 against master commit b652707d of acl2/acl2 (books/kestrel/rust).
Links point at branch or master views; substitute the commit for a pinned view. Entries whose evidence is a certificate say so; entries resting on development-session observation say that instead — the chips distinguish the two. Section numbers (§1–§7, and A for the appendix) refer to the paper; the glossary, this note’s companion sections, and the index are the explainer’s own.
theorema certified ACL2 event states exactly thisexecutedcertified by running code (assert-event / KAT)coderead it directly at the cited file and linedocumentedrests on a cited publication or in-repo documentdev logattested by the development sessions, not by an artifact you can re-runpending codea run or measurement not yet reproducible from the repository (no entry currently carries this chip)
“the Rust standard library now runs a verification campaign of over 16,000 proof harnesses per code change in continuous integration”
The figure is reported by the Kani team’s own paper (arXiv:2607.01504, to appear at ASE 2026 Industry Showcase), describing the verify-rust-std campaign in which each pull request re-runs the harness suite. The paper cites it as \cite{kani} at that sentence. The number is theirs, current as of their writing; the sentence attributes it to CI practice, not to us.
“ACL2 … has met Rust only for programs written to fit a restricted subset designed for transpilation; it has had no path from the ecosystem’s existing code.”
The prior path is David Hardin’s Restricted Algorithmic Rust (RAR): ACL2’22 (EPTCS 359, pp. 202–216, DOI 10.4204/EPTCS.359.16) and ACL2’23 (EPTCS 393, pp. 161–174, DOI 10.4204/EPTCS.393.13). In Hardin’s own words, RAR programs are “transpiled” source-to-source into Restricted Algorithmic C and reach ACL2 through Russinoff’s RAC translator. Both halves of our sentence are calibrated to that: RAR is a real path (hence “met Rust”), and its programs are written into the subset (hence “no path from the ecosystem’s existing code”). The vendored subject of this paper is RustCrypto’s shipped implementation, audited statement-identical to upstream (E18).
“with both extracted directions—encryption and decryption, key schedule included—proved equal to the ACL2 AES-128 specification for all keys and blocks, every assertion and bounds check proved to pass”
This is the pair of main theorems, quoted verbatim in the paper’s §5 and certified in the suite: encrypt-correct at tests/acl2/aes_fixslice_final.lisp:337 and decrypt-correct at tests/acl2/aes_fixslice_decfinal.lisp:347. “Key schedule included” because the extracted drivers encrypt/decrypt run the extracted aes128_key_schedule internally rather than taking round keys as input. For why an ok conclusion covers assertions, bounds, and fuel, see E23.
“the Aeneas backend, the proof development, and the MIR semantics and loader described in this paper were developed by Claude Fable 5 … working under the author’s direction; the author specified goals, reviewed the work, and certified and integrated all results”
This statement satisfies the workshop’s guidance on AI assistants, which asks that substantial AI contributions be credited (the title carries a \thanks footnote) and that AI-performed work described in a paper be explained in the text. The division of labor it describes is the factual one: goals, review, certification runs, commits, and pushes were the author’s; drafting of code, proofs, and prose was the assistant’s. This explainer has the same provenance (see the box at the top).
“Because Aeneas does not establish termination, recursive functions are extracted with fuel.”
Visible in the generated book: every recursive loop function takes a leading fuel parameter n and returns the distinguished out-of-fuel failure when it reaches zero — e.g. aes-fixslice-encrypt-aes128-encrypt-loop0 (n rkeys state-var rk-off) at aes_fixslice_encrypt.lisp:1306. The extraction flags that select this treatment are -use-fuel -loops-to-rec (Makefile, E20). The main theorems instantiate fuel 100 and conclude ok, which is what discharges termination in practice (E23).
“The verification target is the AES-128 specification in the ACL2 community books (kestrel/crypto/aes): an executable, audited rendering of FIPS-197, covering both cipher directions and the key expansion.”
The specification is books/kestrel/crypto/aes/aes-spec.lisp in the ACL2 community books — not written for this project and not modified by it. The functions the theorems mention: aes::aes-128-encrypt, aes::aes-128-decrypt, aes::keyexpansion, and the input recognizer aes::inp (defined at line 141 of the copy pinned in our development tree). Its prior use to verify JVM bytecode and x86 AES implementations is the published Axe line: Smith’s thesis and the Smith–Dill FMCAD 2008 paper cited at the same sentence.
“one path proves the extracted program correct; the other path checks the compiled program independently of Aeneas and our backend, sharing only rustc and Charon’s translation of MIR, run with different options”
The sharing claim is an inventory: the proof path is rustc → Charon (LLBC, with the Aeneas preset’s reshaping) → Aeneas → ACL2 backend → generated book; the interpreter path is rustc → plain Charon (ULLBC JSON) → ACL2 loader → MIR fixtypes → interpreter. Shared: rustc up to promoted MIR, and Charon’s translation of MIR into its own IR, run with different options (the extraction reads promoted MIR and monomorphizes and restructures it; the interpreter path reads the later runtime MIR, unmonomorphized) — and that translation is more than a serializer: the pinned fork’s ULLBC pipeline runs real normalization passes before writing JSON (pointer-metadata insertion, unit-return assignment, storage-marker insertion, drop desugaring; charon/src/transform/mod.rs). Aeneas, the backend, the loader, and the interpreter each appear in exactly one path. The paper draws only the scoped conclusion this sharing supports: agreement on the tested vectors is evidence against errors in the unshared stages, not a proof for all inputs (§6.4) — a bug whose effect lies outside the tested inputs would escape even a fully correct interpreter.
“a handwritten book, rust-primitives, that gives first-order ACL2 meanings to the Rust value layer … u32-add returns ok on in-range sums and a failure otherwise, with rules characterizing both cases”
tests/acl2/rust-primitives.lisp: u32-add is defined at line 64; massert at line 153. The book is handwritten (it is the model, part of the trusted meaning of the extraction, alongside the printer itself) and every generated book includes it. The paper’s list — checked arithmetic per width, total bitwise ops, monadic shifts, casts, arrays/slices as lists with bounds-checked array-index/array-update, range structures, Result/Option plumbing — is the book’s table of contents, readable top to bottom.
“Upstream debug_assert!s extract as massert forms—ok-binders on the asserted condition”
massert (rust-primitives.lisp:153) returns (ok ...) exactly when its argument is true and a failure otherwise; the printer emits each debug_assert! as a b*ok-binder on a massert call, so a failed assertion poisons the whole computation’s result. The Charon preset used for extraction keeps debug assertions rather than compiling them out — documented in PORTING-NOTES-ACL2.md (“the charon preset KEEPS them”). This is the mechanism behind “every assertion proved to pass” (E23).
“The AES crate exercises this on its three upstream loop shapes: the key schedule’s rcon fold, the encrypt round loop, and the decrypt round loop with its descending offset counter and mid-body break.”
The three recursive loop functions in the generated book, with their fuel parameters: aes128-key-schedule-loop0 (line 1487), aes128-encrypt-loop0 (line 1306), aes128-decrypt-loop0 (line 1785, threading the descending rk-off) of aes_fixslice_encrypt.lisp. The upstream texts they extract are the crate’s literal loop {{ ... break }} blocks, restored verbatim in vendoring passes 3 and 11 (E17).
“it defunctionalizes the write-back continuation into a list of pending writes: the identity continuation becomes nil, each wrapping lambda becomes a cons, and generated companion functions apply the list”
Read it in the generated book. shift-rows-2-loop0 (n iter back) (line 416) recurses as (... (cons x_189 back)) and is applied at line 435 after starting from nil; the zip case, add-round-key-loop0 (line 1276), conses pairs of pending writes, one per zipped slice. The claim that this translation is checked “independently of AES” is the iterator probe crates in the test suite — itermut_probe, subslice_probe, lebytes_probe, rev_range — each with a generated book and a hand proof book (*-proofs.lisp) beside it; the Makefile’s regen recipe documents what each probe pins.
“We therefore run a carve-out configuration, contributed to our Charon fork: types capable of carrying mutable borrows stay polymorphic while everything else monomorphizes”
The exact configuration is the displayed command in §4.3 of the paper, and it is not retyped for the paper — it is the Makefile recipe that regenerates the AES book: tests/acl2/Makefile lines 82–90, flags --monomorphize --monomorphize-mut=except-types --remove-adt-clauses --lift-associated-types='*'. The motivation (indiscriminate monomorphization bakes out borrow-carrying instantiations and Aeneas rejects the input) is documented with the vendoring history in PORTING-NOTES-ACL2.md.
“The per-round standalone ShiftRows disappears: the state simply drifts one ShiftRows frame per round, the implementation provides four conjugated variants mix_columns_0 through mix_columns_3 that each absorb the current frame, and the cycle closes every four rounds. What remain, and do permute the words, are boundary and key-schedule corrections …”
This is the fixslicing idea as published by Adomnicai and Peyrin (TCHES 2021(1), DOI 10.46586/tches.v2021.i1.402-425), and it is visible in the vendored source: the define_mix_columns! macro instantiates exactly mix_columns_0..3, and the round loops index the variant by round number. The frame-drift reading is not just prose — it is what the proof’s ladder invariant formalizes, with the frame exponent c(r) cycling mod 4 (E25).
The surviving permutations are visible at their call sites: encryption calls shift_rows_2 before the final round (line 481), decryption applies its inverse near entry (line 819), and the key schedule applies inverse variants to key windows (lines 581–583). These are the boundary and key-schedule corrections the paper names; only the per-round standalone ShiftRows is gone.
“The S-box circuit has 113 gates—32 ANDs, 77 XORs, and 4 XNORs; the implementation realizes them as 32 & and 81 ^ operations, absorbing the XNORs’ inversions into the key schedule”
The gate counts are the fixslicing paper’s (the circuit descends from the Boyar–Peralta construction), and the operator counts were confirmed by the author against the implementation: the four XNORs cannot be written as ^ without an inversion somewhere, and upstream’s sub_bytes_nots applies the compensating NOTs — folded into the stored round keys, which is why the key schedule carries a byte mask (the 0x63-pattern constant the proof’s mask algebra tracks, E30). Read sub_bytes and sub_bytes_nots in the pristine upstream copy, tests/src/reference/fixslice32-aes-v0.9.1.rs.
“vendored by hand from aes v0.9.1, src/soft/fixslice32.rs (repository RustCrypto/block-ciphers, tag aes-v0.9.1, commit 507938c), and the pristine upstream file is checked in beside it”
# the checked-in reference really is upstream's file at that tag:
curl -sL https://raw.githubusercontent.com/RustCrypto/block-ciphers/aes-v0.9.1/aes/src/soft/fixslice32.rs \
| diff - tests/src/reference/fixslice32-aes-v0.9.1.rs
“a sequence of eleven restoration passes replaced each de-sugared form with the verbatim upstream text”
The audit section of PORTING-NOTES-ACL2.md is the ledger: each delta class is a table row marked struck through RESOLVED with its pass number — re-rolled encrypt loop (pass 3) and decrypt loop (pass 11), iter_mut()/zip() loops (pass 10), LE byte plumbing (pass 8), key-schedule subslice borrows and step_by fold (pass 9), upstream signatures (pass 7), memshift32 (passes 1+7), asserts (passes 1+2, completed by 7+8). The de-vendoring roadmap beneath it is the source of the paper’s future-work line on completing the job.
“the shared round-operation and key-schedule bodies are statement-identical to upstream; what remains is the adaptation layer around them … four added single-block entry points—encrypt, encrypt_block, decrypt, decrypt_block, the functions the theorems name—wrap a batch driver, duplicating the one block into both lanes and returning lane 0. Dropped scope: AES-192/256, the cipher-crate trait implementations, and the untaken cfg path.”
The ledger is PORTING-NOTES-ACL2.md at the repository root: the byte-identical helpers, the de-sugaring classes each struck through as a restoration pass resolved it, and the dropped scope. The audit is function-by-function and whitespace/comment-insensitive.
Two of the adaptation-layer deltas, anchored: inv_bitslice’s initializer — upstream writes BatchBlocks::default() (reference line 1275), the vendored copy [[0u8; 16]; 2] (line 297), a delta the ledger records inline (“BatchBlocks/State::default() → array literals remain the documented de-sugar”); and the four single-block entry points, which exist only in the vendored copy, with the main theorems stated about two of them. The thirteen debug_assert!s and the S-box operator counts match upstream exactly (E19).
Check one function yourself
# normalize whitespace/comments and compare a body, e.g. sub_bytes:
for f in tests/src/aes_fixslice_encrypt.rs \
tests/src/reference/fixslice32-aes-v0.9.1.rs; do
sed -n '/^fn sub_bytes(/,/^}$/p' $f \
| sed 's|//.*||; s/[[:space:]]\+/ /g; s/^ //; s/ $//' \
| grep -v '^$' | md5sum
done # same hash twice
“all thirteen upstream debug_assert!s” / “every one of the thirteen upstream assertions … succeeds”
Thirteen in the pristine upstream file, thirteen in the vendored copy. A pleasing detail from the restoration, recorded in the porting notes: sub_bytes_nots only touches indices 0,1,5,6, so the proof originally needed just len ≥ 7; upstream’s assert demands len == 8 exactly, and the lemma hypothesis was tightened to match upstream rather than weakening the subject to match the proof.
“The crate goes through the carve-out pipeline … charon rustc --preset=aeneas --monomorphize ...”
The displayed command is the Makefile’s AES recipe (tests/acl2/Makefile, lines 82–90, inside the regen target), lightly re-wrapped for the paper’s line width. Running make regen with CHARON and AENEAS pointing at the forks regenerates every golden book, the AES book included; the committed generated book is the recipe’s output.
One subtlety the appendix’s recipe encodes: every Aeneas invocation in the regen target ends in || true (so the expected-failure probe crates can run), and the Charon invocations silence their output — so a failed extraction could leave a stale committed book, a clean git status, and a passing make regen. The recipe therefore deletes the 19 generated books first (they carry the GENERATED BY AENEAS header), which turns any silent failure into a visible missing file. Run under that protocol in the pinned devenv image: all 19 books deleted, regen exit 0 in 136 s, git status clean — every book regenerated, byte-identical.
“The main theorems equate the extracted drivers—key schedule included—with the audited AES-128 specification … for all keys and blocks”
Displayed verbatim in the paper and certified at aes_fixslice_final.lisp:337 and aes_fixslice_decfinal.lisp:347. The hypothesis aes::inp is the specification’s own recognizer for 16-byte inputs (aes-spec.lisp:141 in the pinned copy) — both key and block range over all 2128 values.
“Because the conclusion is an ok result, the theorems also establish that no execution path fails: every one of the thirteen upstream assertions, every bounds check, and every fuel decrement succeeds, for every input. The natural next theorem is correctness of the two-block batch: each output lane equal to the specification of its own input.”
This is an argument from the shape of the extraction, not an extra theorem, and it goes: every failure — a false massert, an out-of-range array-index, an overflowing checked add, fuel hitting zero — produces a failure value, and the b*ok-binders propagate any failure to the driver’s result (there is no catch construct in the extracted language). The theorems conclude the result equals(ok <spec value>) for all inputs; a single reachable failing check on any input would falsify that equality. So “assertions pass” is a corollary of the main equalities plus the monad’s definition in rust-primitives.lisp — all certified material. The paragraph’s closing sentence is scope, not claim: the verified entry points duplicate one block into both lanes (E18), where a transposition of the lanes would be invisible, and the batch-level theorem it names — each output lane the specification of its own input — is the stated next step, not a certified result; the GL facts beneath already quantify over two distinct lanes (E27).
“each layer names its job and the encrypt | decrypt books that implement it”
The figure’s book names are the file names under tests/acl2/, prefix aes_fixslice_: collapse in cipher/decipher; push-ins in cipherops/decipherops with decoptypes carrying the decrypt side’s type closure; algebra in maskalg/decmask; ladders in ladder/decladder; spec hop in final/decfinal; GL side-facts in round, subbytes, mixcolumns, shiftrows, addroundkey, invops/invops2/invops3, bijection; key-schedule window facts in windows and keymain atop the sixteen-book key* stack.
“The ladder layer proves the per-round invariant … as nine explicit round lemmas plus a final one, no induction needed.”
Count them: aes_fixslice_decladder.lisp holds eleven defthm dec-ladder-* events — dec-ladder-0 (the base, after the initial AddRoundKey) through dec-ladder-9 (the nine middle rounds), plus the terminal event for the final round; aes_fixslice_ladder.lisp mirrors the same shape on the encrypt side (eleven defthm ladder-* events). The round lemmas themselves are proved without induction — each carries :do-not-induct t and rewrites using the previous one plus that round’s algebra, which is what “explicit” means here. The supporting chain lemmas beneath them do use induction (tl-of-sbn-chain at aes_fixslice_ladder.lisp line 40, inp-of-y-chain at line 113, inp-of-z-chain on the decrypt side), which is why the paper scopes its no-induction claim to the round lemmas.
“with the extracted key schedule’s windows already bridged to aes::keyexpansion”
The window facts are window-bitslice-0 … window-bitslice-10 (with companion wstatep-window-N/ib-window-N events) in aes_fixslice_windows.lisp — eleven windows for round keys 0–10, each relating an 8-word window of the extracted schedule’s 88-word output to the specification’s aes::keyexpansion, in that window’s frame and mask dress. They rest on aes128-key-schedule-ok and the per-window theorems of aes_fixslice_keymain.lisp, the summit of the key* stack.
“Facts that are true because of bit-level computation … are proved by GL bit-blasting, as symbolic BDD computations over all 2256 packed states or all 2128 byte lanes.”
The suite contains 72 def-gl-thm events (count below). The two quantification shapes are visible in the :g-bindings: 32 byte variables a0..a15,b0..b15 (two 16-byte lanes — 2256-state facts, e.g. aes_fixslice_decmask.lisp:172) and 16 byte variables (single-lane 2128 facts, e.g. line 185 of the same book). Everything outside these events is rewriting; the GL books sit on the side of Figure 2 exactly because their conclusions are consumed as rewrite rules by the main stack.
“The fix was a variable ordering: … interleaving the sixteen byte variables along the frame’s diagonals makes each output column read contiguous BDD variables, and the same blasts that died at seven gigabytes certify in under a minute.”
The orderings themselves are in the certified books — read the :g-bindings of aes_fixslice_invops2.lisp:13 (order 0,5,10,15,4,9,14,3,… — the frame-1 diagonals), line 33 (0,9,2,11,… — frame 2), and invops3.lisp:11 (0,13,10,7,… — frame 3); decmask.lisp lines 212 and 225 use the same orders on single lanes. What the certificates cannot show is the road there: the memory numbers (out-of-memory at ~7 GB under natural order, sub-minute under diagonal order) are development-session measurements, hence the amber chip. That the books certify now, with these orderings, on modest memory is re-checkable by anyone.
“heavy blasts live in books with the slimmest possible include chains, memoization tables are cleared between them, and the heaviest blast in a session is sequenced last. We could have used Axe or a SAT back end, but that would have required a trust tag, which we avoided with the GL engineering work.”
The structural half is visible in the tree: decoptypes exists as a separate book precisely so the 2256 type-closure blast certifies on a slim include chain, and within GL books the heaviest event sits last. The operational half (clearing memo tables, the failures that taught the rule) is development history. The porting notes and the paper both present this as engineering guidance, not as a theorem. The closing sentence’s factual half is measured, not taste: an external solver enters ACL2 under a trust tag, and the suite’s trust-tag-free standing across the full closure is E32’s measurement; the GL engineering it credits is E28’s orderings plus this entry’s discipline.
“each add_round_keydeposits the key’s mask, and the following inv_sub_bytesconsumes it … the conjugated inverse MixColumns (whose coefficients also sum to 1, so the uniform mask is fixed) … the final round key window is stored unmasked and unrotated”
Each clause is a certified lemma family in aes_fixslice_decmask.lisp: the inverse-S-box-consumes-mask facts are the GL events around invsbox16 (defined at line 37); the mask-through-inverse-MixColumns commutation is the masked imcN family (the coefficient-sum observation — 9⊕11⊕13⊕14 = 1 in GF(28), so a uniform mask passes through — is why those lemmas are true, and GL checks them without needing the arithmetic argument); the final window’s undressed storage is window-bitslice-0 in windows.lisp — decryption’s lastadd_round_key uses round key 0, certified as plain kk-iter key 0 under bitslice; its first key, window 10, is stored masked but unrotated (window-bitslice-10 wraps kk_10 in sub-bytes-nots-bytes), which is where the deposit-and-consume flow begins. (The first published version of this page said window-bitslice-10 here; drafting the glossary’s code sample caught the slip — the ledger audits itself, too.) The narrative arc (“the mask flows the other way”) is exposition over these certificates.
“we ran the extracted code and the specification on FIPS-197 data and matched the extracted value against a table of candidate spec stages under every frame rotation and mask combination … no discovered equation later failed to certify”
The probes were interactive ACL2 sessions, and their tables are not checked-in artifacts — this is method description, chip amber accordingly. What survives, and is re-runnable, is everything the probes led to: the ladder invariants they read off are the certified ladder/decladder events (E25), and the executions they began with live on as the certified known-answer books (E32). The specific claim “the first run of the decrypt probe was also the extracted decrypt’s first end-to-end known-answer test” is a true statement about development order, attestable only by the sessions themselves.
“The complete development is 78 books … books certifying FIPS-197 known-answer vectors by execution … All books are in logic mode with no axioms, no skip-proofs, and no trust tags, and the suite recertifies from scratch in about twelve minutes with two parallel jobs”
The counts and hygiene are one-liners (below). The known-answer books: aes_fixslice_encrypt-proofs.lisp certifies the FIPS-197 Appendix C.1 vector through the full extracted cipher — encrypt, decrypt, and both round-trip compositions — and aes_fixslice_keyschedule.lisp certifies the Appendix A.1 key-expansion example (key 2b7e…3c) against aes::keyexpansion via assert-event. The key-expansion vector is Appendix A.1, not Appendix B: B’s plaintext 3243f6a8… appears nowhere in this suite (the §6 interpreter harness, a different suite, does run Appendix B — E35). The paper’s “twelve minutes with two parallel jobs” is a wall-clock measurement on the author’s development machine, so it is not itself a certificate — but the from-scratch run is reproducible in a pinned, published environment, and has been reproduced end-to-end first-hand on a 2-core / 7 GB sandbox. Pulling the aeneas-acl2-devenv image and running its documented loop: make -C tests/acl2 regen re-extracted every generated book byte-for-byte identical to the committed golden (a clean git status, about two and a half minutes; under the delete-first protocol of E20, all 19 books removed first and regenerated identically), and make -C tests/acl2 verify JOBS=1 certified all 78 books against ACL2 @ 0612757 in 955 seconds (about sixteen minutes), exit 0, with no axioms, skip-proofs, or trust tags — the slowest books were keystep (119 s), decmask (65 s), and cipherops (60 s). Single-threaded here versus two jobs on the author’s machine is the whole gap between the two figures; the pinned one is what anyone can re-run. The hygiene claim also extends through everything the suite includes: loading aes_fixslice_final and aes_fixslice_decfinal in the pinned image and asking ACL2 itself gives ttags-seen = nil, and a scan of the full 338-book include-book closure finds zero defaxiom events — the lemma libraries are proved, not trusted. (Running the extraction first-hand also retires the last uncertainty about provenance: the generated books are exactly what the pinned Charon fork and Aeneas produce.)
Check it yourself
ls tests/acl2/*.lisp | wc -l # 78
grep -L '(in-package' tests/acl2/*.lisp | wc -l # 0 stragglers
grep -l 'defaxiom\|skip-proofs\|defttag' tests/acl2/*.lisp # no output
cd tests/acl2 && cert.pl -j2 *.lisp # recertify all
# transitive hygiene: in ACL2, after (include-book "aes_fixslice_final"):
# (global-val 'ttags-seen (w state)) => NIL
§6An executable MIR semantics
Everything this section describes is committed in the ACL2 community books, books/kestrel/rust at the pinned master commit: the interpreter and importer (mir/, import/), the gzipped ULLBC sample with the carved crate source and a generation README pinning the devenv image and Zenodo DOI (samples/), the program fixture, and the two test books that tie them together (E34, E35). The whole development certifies from scratch in the pinned devenv image: 16 books, 102 s with two jobs, exit 0. (The development-time probe programs §6.1 mentions are interactive-session checks, not a committed suite — E36.)
“Coverage follows the crate’s own MIR, and the interpreter handles a superset of what the crate exercises: six terminator kinds … Assign statements and StorageLive/StorageDead markers, eight rvalue forms, and twelve binary operators … Thirty-three named standard-library functions are given ACL2 models, twenty-three of which the imported AES program calls”
The subset is readable in mir/abstract-syntax.lisp, and the interpreter’s small-step shape (“small-step at the statement and terminator level”) in mir/interp.lisp as exec-statement, exec-terminator, exec-shim, and run-fn — that structural claim holds exactly. assign is one of five statement tags (line 330); storage-live and storage-dead are two of the other four, and the crate exercises them heavily — the dump carries 22,831 storage markers (3,794 live, 19,037 dead).
The superset, in the detail the paper has no room for: the terminator deftagsum (line 377) defines eight tags — the crate-exercised seven (goto, switch-int, return, call, assert, abort, unreachable: “six … plus the Abort”) plus drop, which AES never triggers (its state is all Copy, no destructors) but the interpreter handles anyway. The bin-op deftagsum (line 208) defines nineteen operators against the crate’s twelve — support ⊇ exercise again. The rvalue deftagsum has exactly eight tags (line 297: use, ref, binary-op, unary-op, cast, aggregate, repeat, discriminant); dialect descriptions that count overflow-checked operations as a separate rvalue (older rustc’s CheckedBinaryOp) fold into bin-op here, under one binary-op rvalue. The exercised counts are the paper’s, because they are the ones unlikely to change as the interpreter grows.
The standard-library inventory is *shim-names* in mir/interp.lisp (line 1757): 33 supported names, all dispatched through exec-shim, of which 23 are called by the imported AES fixture; the two modeled panic entry points (core::panicking::panic, core::panicking::assert_failed) occur in the fixture only as Abort-terminator payloads, never as calls, so 25 of the 33 names appear in its text — all three counts verified mechanically for this entry. The absent eight are unused variants like u32::wrapping_add, slice::iter, and Range::next_back. The seven shim- helper definitions (iterator and slice machinery) are implementation structure beneath those 33 names, not the count.
“an ACL2 importer turns that into a program value … expands Charon’s serialization sharing (each shared value is written in full at its first occurrence and referenced by id afterwards …), then maps JSON into the MIR fixtypes with nil-tolerant navigation functions whose termination ACL2 accepts after a handful of linear lemmas … a classifier names … declarations by implementation self-type and trait … the standard-library model to invoke is chosen per call site from the call’s generic arguments.”
The importer is two books. Sharing expansion is import/charon-hashcons-expand.lisp: it consumes Charon’s {"HashConsedValue": [id, value]} markers (line 142) into an id→value map and re-inflates references. The JSON→fixtypes mapping is import/ullbc-to-mir.lisp, and its comments confirm each mechanism the paper names: the navigation functions “accept and return optional values” (nil-tolerant, line 143) and carry measure-transparency lemmas “measuring by json::value-count” (line 245); the declaration classifier keys on “its defining impl’s self type and trait” (line 77) with generic-serving shim names “finalized at each call site from the call’s generic arguments” (line 84). This is the “reusable pattern” sentence, checkable at the lines above.
The specific figures are checkable against the committed sample. samples/aes_ullbc_elaborated.json decompresses to 6,875,076 bytes (“6.9 MB”), and its sharing markers count exactly 19,249 — 1,084 HashConsedValue definitions plus 18,165 Deduplicated references, both re-counted mechanically for this entry. “Under a second” for the import step is a dev-machine figure; as corroboration, the whole import test — gunzip, parsing the 6.9 MB of JSON, sharing expansion, import, and the fixture comparison — certifies in 9.0 s in the pinned devenv image.
“The interpreter runs the imported crate end to end: encrypt reproduces the FIPS-197 ciphertexts of Appendix C.1 and Appendix B byte for byte, and decrypt inverts both … Sixty-six further inputs, two corner cases and sixty-four pseudorandom key/block pairs generated in-book, are checked differentially: the interpreted encrypt agrees on every one with aes::aes-128-encrypt itself, the same specification function that the theorems of §5 equate the Aeneas extraction to, and the interpreted decrypt inverts the pseudorandom ciphertexts. One interpreted encryption, 83,602 machine steps with each standard-library call a single step, takes about a quarter of a second.”
Certificate-backed, and re-run first-hand at the pinned commit. The harness is mir/tests/aes-fixslice.lisp: after a leaf-function check on ror (line 76), assert-equal events run the committed program fixture’s encrypt and decrypt through run-fn on the Appendix C.1 and Appendix B vectors, both directions (lines 85–100) — the constants come from the specification’s own aes-spec-tests book, not duplicated — and differentially against aes::aes-128-encrypt on all-zeros and all-ones (lines 104–110). It runs from the committed fixture *aes-fixslice-program*; that the fixture is exactly what the importer produces from the committed sample is checked by import/aes-import-test.lisp (E34). Certifying it here in the pinned devenv image: 6.5 s for the book, including its six whole-cipher interpreter runs — consistent with the paper’s quarter-second per encryption (83,602 machine steps) on the author’s faster machine, so the timing stays a dev-machine measurement while everything else in the quote is a certificate. The step count, though, is exact and machine-independent, and was verified in the pinned image: run-fn on the C.1 key and block completes with fuel 83,602 and exhausts at fuel 83,601 — one mstep per statement, terminator, or standard-library call, by construction. The sixty-four pseudorandom pairs are mir/tests/aes-fixslice-random.lisp: a fixed-seed splitmix64 generator expands seed 0 into the pairs in-book — 128 interpreted runs, every encrypt equal to aes::aes-128-encrypt, every decrypt inverting its ciphertext — certified here in 56 s in the pinned devenv image. The methodological point: the differential target is the same specification object that the §5 theorems equate the extraction to, so the two assurance paths meet at one reference.
Check it yourself
cd books/kestrel/rust
cert.pl -j2 import/aes-import-test.lisp mir/tests/aes-fixslice.lisp \
mir/tests/aes-fixslice-random.lisp
# the asserts run during certification; expect three .cert files (~2.5 min)
“During development, running the real crate exposed one semantic gap, in iterator conversion: add_round_key zips against a bare slice, relying on the standard library’s zip to convert it to an iterator (IntoIterator) internally—a conversion the interpreter had not modeled.”
The fix is in the code, commented as exactly this problem: mir/interp.lisp notes that “IntoIterator implementations perform inside zip and in for loops over references” (line 1444), and shim-zip-next (line 1454) handles the conversion. What stays report-sourced is the discovery — that live execution of the crate is what first surfaced the gap, and that a probe test came with the fix; that is a fact about the development sessions, not something the committed code re-runs (the crate run itself is committed — E35). So: the fix, code; the story of how it was found, dev log.
“Kani, for instance, translates the MIR of each proof harness, and of the code it reaches, into CBMC’s GOTO programs through a translation that is itself trusted”
Kani’s own paper says this plainly in its threat-model/limitations discussion (the MIR-to-GOTO translation is part of the trusted base), which is the sentence’s source; the point is offered with sympathy, not as criticism — our extraction chain is equally trusted until the translation-validation program of §8 lands. Cited as \cite{kani} at the sentence.
“The verification of §5 is only as trustworthy as the translation chain that produced the extracted functions. Our second line of assurance gives MIR itself a formal semantics in ACL2, so the same compiled program can be read a second way, independently of Aeneas and our backend … We formalize, as fixtypes and functions in the ACL2 community books, a subset of MIR sufficient for the AES crate: values, places and their projections, rvalues, statements, terminators, bodies, and a machine state.”
The development builds both classic embedding styles without ever using the textbook names; this entry supplies the vocabulary (glossary). A shallow embedding translates each object-language program into functions of the host logic: meaning is inherited from the host, so its rewriter, its bit-blaster, and its evaluator apply to the program directly — but programs are definitions rather than values, nothing in the logic can quantify over them, and the translator that produced them is trusted. A deep embedding represents the object language’s syntax as host data and gives it meaning once, with an interpreter written in the host: the program becomes an inspectable value, one semantics covers every program in the subset, and program-level metatheory becomes expressible — at the price that reasoning about any one program goes through the interpreter.
Each assurance path is one style. The extraction path is the shallow embedding: Aeneas resolves borrows symbolically, and the backend emits the crate’s pure functional image as ordinary ACL2 definitions — the generated book is the crate as 74 defuns, loops arrive as fueled recursive functions (fuel being the standard shallow device for partiality in a logic of total functions, glossary), library operations are the handwritten rust-primitives models (E9), and the §5 theorems are host theorems about those terms. What §7 credits to the untyped target — “ACL2’s executability and industrial-strength rewriting” (E42) — is the shallow embedding’s payoff, and what E41 books as trusted translation is its bill. The MIR semantics is the deep embedding: the fixtypes under mir/ (abstract-syntax.lisp and its siblings) are MIR syntax as data, the importer parses Charon’s serialized output into a program value whose identity is certified against the committed fixture (E34), and interp.lisp’s mstep/run-fn are the one semantics — the compiled crate sits in the logic as *aes-fixslice-program* and is run, not translated (E35). Its one deliberate shallow seam is the library boundary: the thirty-three shims (E33) model named standard-library functions as host functions, one step per call, instead of interpreting their MIR. The AES specification is neither: it is native ACL2 with no object language in sight, which is exactly what lets both embeddings terminate at the same host object.
The two styles trade the classic strengths — shallow bought theorems for all inputs on top of a trusted translator; deep bought a small, auditable semantic basis that runs the compiler’s actual output, and here yields testing rather than proof — and §6.4’s closing sentence is the standard playbook for connecting them: proving the interpreted MIR equal to the extracted functions is per-program translation validation, the deep embedding discharging the shallow one’s trusted translation, while proving it equal to the specification directly would promote the deep embedding from test harness to proof vehicle (the route the §8 plan to run Axe over the MIR semantics would industrialize).
Check it yourself
# deep: syntax as data, meaning by interpreter (books/kestrel/rust)
grep -n 'fty::deftagsum statement' mir/abstract-syntax.lisp # line 330
grep -n '(define mstep' mir/interp.lisp # line 1991
# shallow: the same crate as host definitions (aeneas tests/acl2)
grep -c '^(defun ' aes_fixslice_encrypt.lisp # 74
“The interpreter is small-step at the statement and terminator level, with big-step evaluation of operands, places, and rvalues, which are functional.”
The sentence names its genus only by its species, so here is the genus (glossary). The classical ways to give a language meaning: operational semantics defines meaning by how programs execute, as steps of a machine or as evaluation derivations; denotational semantics assigns each program a mathematical object through a semantic function; axiomatic semantics defines meaning by what assertions hold around a program — a program logic. “Small-step” (Plotkin’s structural operational semantics: a transition function between machine configurations, one step at a time) and “big-step” (Kahn’s natural semantics: syntax taken straight to its final value in one derivation) are the two standard styles of operational semantics — the terms have no non-operational use, so the paper’s sentence says “operational” implicitly and unambiguously.
The mixed granularity is the standard engineering split, and the committed code mirrors the sentence clause by clause. mstep (mir/interp.lisp, line 1991) is the small-step transition function: “one step of the machine: execute the next statement or terminator of the top frame.” Statements and terminators are where control flow, the frame stack, and the Abort/panic outcomes live, and making exactly these the countable steps is what gives E35 its exact, machine-independent step count — 83,602 for one encryption, one step per statement, terminator, or standard-library call. Below that line, evaluation is big-step: eval-operand (line 909), eval-place (line 874), and eval-rvalue (line 940) take syntax straight to a value in one recursion, with no intermediate configurations to resume — safe precisely because those layers are “functional” in the sentence’s sense, pure and terminating, so ACL2 admits them as ordinary total recursions and nothing is lost by being unable to pause inside them. Whole-program divergence is pushed to a single place: mrun (line 2043) iterates mstep under a fuel bound, and run-fn (line 2060) is the fueled entry point — the clocked-interpreter pattern traditional for ACL2 machine models, and the deep-embedding twin of the fuel the extraction uses for its loops (glossary, E43).
One refinement worth having: written as total functions of the host logic, the big-step layer is what Owens, Myreen, Kumar, and Tan call functional big-step semantics (ESOP 2016) — an operational style that doubles as a denotation, because the evaluator is itself a mathematical function one can prove theorems about. That double reading is what §6.4’s prospective theorems would exploit: translation validation, or a direct proof against the specification, would quantify over runs of exactly these functions.
Check it yourself
# the sentence, clause by clause (books/kestrel/rust)
grep -n '(define mstep' mir/interp.lisp # small-step: one statement or terminator per step (1991)
grep -n '(define eval-rvalue' mir/interp.lisp # big-step: syntax straight to value, pure (940)
grep -n '(define mrun' mir/interp.lisp # fuel-indexed iteration of mstep (2043)
§7Related work & the bibliography
E38dev log§7, the “distinguishing constraint” framing
“Our distinguishing constraint is that the subject is shipped, third-party, optimization-heavy code, verified essentially as-is under a mechanical audit against upstream.”
The framing is deliberately a constraint claim, not a priority claim — the paper asserts no “first.” Due diligence behind the neighboring prose, from the drafting sessions: the Signal/BAIF Lean verification effort had published curve25519 work and in-progress SPQR but no AES at drafting time; SAW’s public Rust examples (via mir-json/crux-mir) showed no RustCrypto AES; Aeneas’s own test tree (106 Lean files) contains none. These are absence-of-evidence searches with a date on them, which is why they justify cautious wording in the paper rather than a novelty sentence.
The bibliography was rebuilt under an explicit policy, recorded in the header comment of paper.bib: numeric fields are verified against a publisher page, arXiv record, or DOI resolution, and fields that could not be verified are omitted rather than guessed (bibtex’s “empty pages” warnings on a few entries are the visible cost of that choice).
“KMIR now gives the compiler’s Stable MIR JSON export a K semantics with concrete and symbolic execution. Of the existing efforts, KMIR is the nearest relative of our loader-plus-interpreter”
“Nearest relative” is an architectural comparison, checkable from public artifacts: Runtime Verification’s mir-semantics consumes SMIR JSON produced by their stable-mir-json exporter and executes it in K, concretely and symbolically — the same route shape as our plain-Charon ULLBC JSON plus loader plus interpreter, with a different serializer, IR dialect, and host. The differences named in the paper (host, and adjacency to a specification library and an extraction proof stack) are the honest ones.
“…Aeneas, on which we build, handles borrows themselves by translating them away, with backends for F*, Rocq, HOL4, and Lean. Our backend adds an untyped, first-order target to that family … what buys ACL2’s executability and industrial-strength rewriting for the proofs.”
Behind that clause sits a comparative question: in which of the family’s provers does the extraction run inside the prover? Checked against the pinned Aeneas tree (23cf8c88): natively and totally, only ACL2 — the definitions the theorems quantify over are themselves executable logic-mode functions, so the known-answer and differential books certify as part of the build (E35), with no translation step between the proof object and the thing that runs. Lean is the other backend whose output runs in practice: its library defines iteration and primitives with Lean’s partial_fixpoint (Std/VecIter.lean, line 58), the construct that makes possibly-diverging definitions both compilable — #eval runs them — and reasoned about through kernel-checked equations. Two caveats separate that from the ACL2 situation: #eval goes through Lean’s compiler, outside the kernel, so execution adds a trusted component; and axiomatized opaque functions have no executable body at all. The recent SymCrypt verification works the Lean side exactly this way — generated models “executable, albeit much slower than their Rust counterparts,” checked against known-answer vectors and against translated Rust unit tests (Scaling Verification of Cryptographic Software with Aeneas, Rust, and Lean, arXiv:2609.15648). The rest of the family, briefly: Rocq has real in-prover computation (Compute, vm_compute), but the stock primitives declare the pointer-size bounds as axioms (backends/coq/Primitives.v, line 107), and axioms do not reduce, while the fuel option that would make recursion total is off by default (src/Config.ml, line 219); F* executes by extraction to OCaml or C, outside the prover; and the HOL4 port exercises no in-logic evaluation. (The paper claims executability only for its own backend; this entry is the survey behind the comparison.)
Check it yourself
# in the pinned Aeneas checkout (23cf8c88)
grep -n partial_fixpoint backends/lean/Aeneas/Std/VecIter.lean # Lean iteration: partial_fixpoint, runs under #eval
grep -n 'Axiom usize_max' backends/coq/Primitives.v # Rocq usize bound is an axiom: does not reduce
grep -n 'use_fuel' src/Config.ml # fuel (total recursion) is opt-in, default off
“On the ACL2 side the trusted base is the ACL2 core plus the specifications … The lemma libraries the proofs use … are themselves proved, adding nothing to that trusted base: across the two main theorems’ full include-book closure (338 books), there are no defaxioms and no trust tags.”
“Trusted base” is an accounting category, not a confidence rating: it answers, exhaustively, where doubt about encrypt-correct could still live. The specification has to appear in that answer on pain of circularity. Every machine-checked equivalence — the JVM bytecode AES, the x86 implementations, now this Rust crate — establishes that implementation and specification compute the same function; that the shared function is FIPS-197’s is not a theorem and cannot be one, since FIPS-197 is prose and tables. It is pinned down empirically instead: by the standard’s own vectors (E6), and by the fact that a wrong-but-self-consistent AES would fail against every other AES in the world on first contact with foreign ciphertext.
So listing the specification is bookkeeping, not doubt — and the calibration runs the other way: it is the best-corroborated item on the list. It reproduces the standard’s vectors and has been proved input-output equal to three independent implementations, in three languages, with radically different internal structure; they could agree with a wrong specification only by all being wrong identically. Each new equivalence proof is also evidence for the specification — this paper added one. Verification does not remove trust; it concentrates it, and here concentration has made the specification’s share cheap. The item that deserves the reader’s scrutiny is the younger, single-project rust-primitives model (E9): a misreading of Rust’s semantics there would not be caught by AES interoperation, and its corroboration — the known-answer books and the independent MIR-interpreter agreement (E35) — is real but thinner. The library-hygiene half of the quote is mechanically checked in E32.
GGlossary, with code samples
Terms of art the paper uses without room to unpack, ordered subject → pipeline → proofs. Code samples are verbatim from the repository except where a comment says lines are elided or re-wrapped; the index at the end maps terms to definitions and entries alphabetically.
bitslicing
Representing cipher state so that bit position i of every byte lives together in machine word i. The 32-bit fixsliced form packs two 16-byte AES blocks into eight 32-bit words, one word per bit position; a byte-level S-box lookup then becomes a fixed Boolean circuit evaluated on whole words — no table, no data-dependent memory access. The circuit is scheduled straight from the research literature, as upstream’s own comment says:
fn sub_bytes(state: &mut [u32]) {
debug_assert_eq!(state.len(), 8);
// Scheduled using https://github.com/Ko-/aes-armcortexm/tree/public/scheduler
// Inline "stack" comments reflect suggested stores and loads (ARM Cortex-M3 and M4)
let u7 = state[0];
let u6 = state[1];
tests/src/reference/fixslice32-aes-v0.9.1.rs, opening of sub_bytes (the 113-gate circuit follows, E15)
fixslicing the word in the paper’s title
Adomnicai and Peyrin’s refinement of bitslicing (E14): classical bitsliced AES must re-permute the packed representation every round to realize ShiftRows, and fixslicing deletes that work by fixing the slice layout and letting the state drift one ShiftRows frame per round. The price is paid in code shape, visible in the vendored source: MixColumns exists in four conjugated variants, one per frame, generated from one macro with frame-adjusted rotation helpers:
tests/src/reference/fixslice32-aes-v0.9.1.rs; variants 2 and 3 follow the same pattern. The proof meets this exactly at the frame algebra and ladder layers (E25).
lane
One of the two 16-byte blocks packed side by side in the fixsliced state. The theorems and ladder lemmas read a lane out of the packed state with inv_bitslice and take car (lane 0); the two-block batch interface is why bit-level GL facts quantify over 32 byte variables (E27).
frame ShiftRows frame
The cumulative ShiftRows permutation the fixsliced state is currently “wearing.” After round r the state sits in frame isrc(r) with c cycling mod 4; the conjugated MixColumns variant for that round absorbs one frame step, and the cycle closes every four rounds. In the proofs, frames are explicit functions on 16-byte lanes and “frame lemmas telescope one ShiftRows per round” (E25, E30).
mask sub_bytes_nots, sbn
The fixed byte pattern (the AES S-box constant 0x63, placed per the packing) that compensates for realizing the circuit’s four XNOR gates as XORs (E15). Upstream applies it with sub_bytes_nots; the proof books call the byte-level map sub-bytes-nots-bytes and abbreviate the story “sbn.” Stored round keys 1–10 carry it; on encrypt it cancels against the state’s own mask at each add_round_key, on decrypt it is deposited by add_round_key and consumed by the inverse S-box (E30).
MIR, LLBC, ULLBC
MIR is rustc’s Mid-level Intermediate Representation — the desugared, control-flow-graph form of a Rust program after borrow checking, before code generation. Charon serializes MIR for external tools: ULLBC (“unstructured low-level borrow calculus”) keeps the raw basic-block graph — our MIR interpreter’s input (E34) — and LLBC is its reconstructed structured form (loops and conditionals recovered), which Aeneas consumes for extraction.
deep vs. shallow embedding not the paper’s vocabulary
Two ways to put a programming language inside a logic. Shallow: translate each program into the logic’s own functions — meaning inherited from the host, the host’s provers and evaluator apply directly, the translator is trusted. Deep: represent the language’s syntax as data and write one interpreter for it in the logic — the program becomes an inspectable value and the interpreter is the thing to trust or validate. Here the Aeneas extraction is the shallow embedding and the MIR semantics (§6) is the deep one, with shallow models at its standard-library boundary; E43 maps every component.
operational semantics small-step, big-step
The family of semantics that defines meaning by how programs execute. Small-step: a transition function from machine state to machine state, one statement or terminator at a time (mstep) — control flow, panics, and step counts live here. Big-step: an evaluator that takes an expression straight to its value in one recursion (eval-rvalue and kin) — right for pure, terminating layers. The other classical families, denotational (meaning as mathematical objects) and axiomatic (meaning as a program logic), are not what an executable second reading needs; E44 unpacks the paper’s one-sentence design.
borrow
Rust’s reference discipline: &x (shared) and &mut x (unique) grant temporary access under compiler-enforced aliasing rules. Borrows are what make Rust memory-safe without garbage collection. A first-order logic can model references as data — the §6 interpreter does exactly that — but Aeneas’s contribution is translating them away entirely by symbolic execution, so the extracted code needs no memory model at all (the hard first-order problem in the backend is the function-valued continuations, E12); the crate’s iter_mut()/zip loops and key-schedule subslice borrows are the places this bites hardest here (E12).
monomorphization and the carve-out
Specializing generic code at each concrete type instantiation. ACL2’s untyped, first-order world wants everything monomorphic, but full monomorphization also specializes the borrow-carrying types (slice iterators, Option<&mut u32>), erasing the region information Aeneas’s analysis needs. The carve-out (E13): monomorphize everything except types capable of carrying mutable borrows, lift associated types, drop ADT clauses — the four flags of the extraction command (E20).
fuel
An explicit natural-number argument added to recursive functions so they are total: each recursive call decrements it, and exhaustion returns a distinguished failure. Aeneas emits fueled recursion because it does not prove termination (E5). The main theorems fix fuel 100 and conclude ok, so 100 is proved sufficient for every input — fuel exhaustion is ruled out along with every other failure (E23).
result monad ok-binders, massert
Extracted functions return (ok v) or a failure value; the b* binder ((ok x) <call>) continues with x on success and short-circuits the whole function on failure — Rust’s panic semantics, made value-level. A debug_assert! becomes an ok-binder on:
(defun massert (b)
(if b (ok (unit)) (result-fail (err-failure))))
tests/acl2/rust-primitives.lisp:153 — the two lines behind “every assertion proved to pass” (E23)
Replacing a function-valued datum by first-order data plus an interpreter for it. Aeneas models mutable iteration with backward functions — the loop state carries a continuation that writes mutated elements back into the slice — and our printer defunctionalizes that continuation into a list of pending writes: the identity continuation is nil, each wrap is a cons, and a generated apply-back replays them. Verbatim from the generated book:
tests/acl2/aes_fixslice_encrypt.lisp:416–428, one long generated name shortened to fit; see E12
GL bit-blasting, BDDs, :g-bindings
The GL framework proves a finite ACL2 conjecture by symbolically executing it over binary decision diagrams: each byte variable becomes 8 BDD bits, the conjecture becomes a BDD computation, and validity is checked by construction. :g-bindings assigns variables their BDD positions — the variable order — and order is everything for BDD size, which is what the diagonal orderings exploit (E28). The standing pattern in these books is a GL fact immediately re-stated for the rewriter, then memory hygiene:
(gl::def-gl-thm misb-of-sbn-gl ; the bit-level fact, checked over all 2^128 lanes
:hyp (and (unsigned-byte-p 8 a0) ... (unsigned-byte-p 8 a15)) ; 16 hyps elided
:concl (equal (map-invsbox16 (sub-bytes-nots-bytes (list a0 ... a15)))
(invsbox16 (list a0 ... a15)))
:g-bindings (gl::auto-bindings (:nat a0 8) ... (:nat a15 8)))
(defthm misb-of-sbn ; the same fact, shaped for structured rewriting
(implies (aes::inp b)
(equal (map-invsbox16 (sub-bytes-nots-bytes b)) (invsbox16 b)))
:hints (...)) ; instantiates the GL fact at (nth i b)
(value-triple (clear-memoize-tables)) ; memory discipline between blasts (E29)
(value-triple (hons-clear t))
tests/acl2/aes_fixslice_decmask.lisp, events misb-of-sbn-gl/misb-of-sbn; repeated elements elided with ...
collapse
The first proof layer (E24): turning a fueled recursive driver into an explicit ten-round chain by expanding the loop function at each of its descending fuel values under a pinned minimal theory, so the unrolling is deterministic and the rewriter explores nothing else. Books cipher / decipher.
push-in
The second layer: rules of the shape inv_bitslice(op(s)) = op-bytes(inv_bitslice(s)), one per round operation, that move the whole chain from the packed representation to per-lane byte transformations — after which the cipher is byte algebra. Books cipherops / decipherops (+ decoptypes for the decrypt side’s type closure).
ladder
The per-round invariant, proved as explicit lemmas — base, one per middle round, and a terminal collapse, no induction (E25). Round 1 of the decrypt ladder, statement verbatim (hints elided, re-wrapped):
tests/acl2/aes_fixslice_decladder.lisp:96 — lane 0 after one decrypt round is the spec chain, one frame on, mask consumed
window key-schedule window
Eight consecutive words of the extracted key schedule’s 88-word output — rd8(rkeys, 8j) is round key j in its stored dress: frame-rotated and masked for j = 1…9, masked but unrotated for j = 10, plain for j = 0. The two extremes, statements verbatim (hints elided, re-wrapped):
tests/acl2/aes_fixslice_windows.lisp; kk-iter is the byte-level image of aes::keyexpansion (E26)
spec hop
The last layer: a fact about the Kestrel specification alone — its cipher loop, read through the flat 16-byte representation, satisfies exactly the recurrence the ladder established for the extracted code. Equating the two closes the theorem without ever mixing bit-level and spec-level reasoning in one goal. Books final / decfinal.
probe, then prove
The discovery method of E31: run both the extracted operations and the specification on concrete FIPS-197 data, match observed values against candidate spec stages under every frame rotation and mask combination, read the invariant off the match table — then certify each matched equation as a lemma. Executability turns invariant discovery into observation; the certificates come after.
KAT known-answer test
A test against published input/output vectors — here FIPS-197’s. In ACL2 these are certified executions: assert-event forms that run the extracted cipher on the standard’s bytes at certification time, so a KAT book failing to certify is the test failing (E32).
logic mode, guards, trust tags, skip-proofs
ACL2 hygiene vocabulary, and the suite’s standing on each (E32): all 78 books are logic mode (every definition admitted into the logic, nothing merely executable); there are no defaxioms, no skip-proofs (proof obligations waved through), and no trust tags (defttag, escape hatches to unverified code). Guards — ACL2’s input-contract layer — are the one deliberate absence: the generated book declares none, so guard verification is future work in the paper, not a claim.
community books cert.pl
The ACL2 community’s shared library (github.com/acl2/acl2, under books/), which provides both the AES-128 specification (kestrel/crypto/aes) and the build tool cert.pl that certifies books in dependency order — the command in every “check it yourself” block that ends in .lisp.
RAR Restricted Algorithmic Rust
Hardin’s subset of Rust, designed so programs written in it transpile source-to-source into Restricted Algorithmic C and reach ACL2 through the RAC translator of industrial floating-point verification — the prior Rust-to-ACL2 path, and the reference point for the Introduction’s calibrated claim (E2).
About this explainer
This document exists because a 16-page limit and a 78-book development disagree about how much justification fits. The paper states each claim once; this page says where each claim lives — a certificate, a file and line, a published number, or, where the honest answer is “the development sessions,” exactly that. The chips are the point: a reader should never have to guess which kind of evidence stands behind a sentence.
It is also a working method, not just a presentation. Writing E32 forced a re-check that caught a real error in the paper (Appendix B vs. A.1) before submission; that is the behavior we want from documentation, and a reason to think the genre — a claims ledger adjunct to a paper — is worth standardizing.
Maintained alongside the paper source; corrections travel as patches like everything else. If a sentence in the paper raises a “where is that justified?” that this page does not answer, that is a bug in this page — request the entry.
IxIndex
Terms → the glossary definition (G) and the entries that touch them. The filter box narrows as you type; it needs JavaScript, the links do not.