Formal verification means proving, with a machine-checked mathematical argument, that a program satisfies a stated property for every possible input, rather than testing some inputs. It gives the strongest guarantee software engineering has, but it has been expensive: the post cites the seL4 microkernel, which took two person-years to implement and twenty to verify (section "Introduction"). This post, published on 22 October 2026 by Anthropic's Frontier Red Team with the formal-verification company Theorem, argues that language models change that cost. Its motivation is defensive: models now find and exploit bugs readily, so the post argues for ways to prove some classes of bug absent. Its headline result is that Claude proved, for 239 fuzz-test entry points across 123 open-source libraries, that the compiled programs never crash on any input below 64 MB, under stated assumptions.
The post (about 4,400 words) has fifteen named authors in its byline, beginning with Keane Lucas, Aengus Lynch and Luna Tong and ending with Nicholas Carlini, Rajashree Agrawal and Jason Gross; the byline does not say which work for Anthropic and which for Theorem. A six-page appendix PDF, dated the same day, gives the theorem statements, proof sizes, the token-efficiency tasks and a section on how the proofs look to a formal-verification expert. The released proofs are in the repository theorem-labs/oss-verify-proofs (release commit 8f5f467, 22 October 2026), whose README states exactly what each proof says and does not say. These three documents are the version of record; no paper on arXiv was found as of 13 November 2026.
What the project did
Turning fuzz tests into specifications
A proof needs a specification, a precise statement of what "correct" means. The post's approach is to reuse tests the developers already wrote. Google's OSS-Fuzz project runs fuzz tests for open-source libraries: an entry point (a test harness function) receives generated inputs, and any input that makes it crash is a bug the developers care about. OSS-Fuzz builds C and C++ code with AddressSanitizer (ASan), which makes the program crash on improper memory access. A fuzzer can only sample inputs. The project turns "this entry point never crashes" into a theorem about every input (section "Turning tests into proofs").
The theorem is about the compiled binary, not the source code. Each library and its fuzz test are compiled to a RISC-V executable, and Theorem's formal model of RISC-V instructions and of a Linux process turns that binary into a mathematical object in the Rocq proof assistant. Claude writes the proof, and the Rocq kernel checks it. The appendix ("What our OSS-Fuzz proofs prove") states the full claim: for two binaries, the ASan build and the plain build, on every input under 64 MiB and every memory layout, neither binary faults, aborts or reaches behavior the model does not describe, and both produce the same sequence of reads and writes, exit the same way, and leave the file system in the same state. Proving the plain build equivalent to the ASan build is what carries the guarantee to the binary users would actually run.
Because a failed assertion is a crash, a proof of "no crash" also establishes whatever property a test asserts. The post's example is the LZO compression test, which it says "asserts that if you compress an input, then decompress it, the result is the same as the original," so that proving no crash "is equivalent to proving the property itself" (section "Proving more than memory safety"). The appendix prints that harness ("Assertions in real OSS-Fuzz entry points"), and its assertions are narrower: both steps return success and the decompressed length equals the original length. The full harness in OSS-Fuzz (projects/lzo/lzo_compress_target.c, last changed December 2023) contains no comparison of the bytes, skips the decompression check when the input does not compress, and truncates inputs to 1 MiB. On this note's reading, a proof that this harness never crashes shows that compressible inputs decompress successfully to the right length, not that they decompress to the original bytes; the appendix's own sentence that Claude "had to prove that LZO's compressor and decompressor round-trip correctly" is stronger than the assertions it prints.
Letting Claude patch bugs, and the risk that creates
When a proof attempt failed because of a real bug, Claude was allowed to patch the code, regenerate the specification and prove the patched version, so that it did not have to stop for a human. Footnote 6 names the risk: Claude "could make any theorem provable by rewriting the program into one that trivially never crashes." To discourage this, the team "penalized any patch," gave extra credit for proving which inputs a patch changes and how few, and "logged and audited the patches." The post does not report how many patches were made or what the audit found.
What it reports
The OSS-Fuzz proofs
- Scale. "Over the span of a few weeks," Claude patched the bugs it found and proved no-crash theorems for 239 entry points in 123 OSS-Fuzz libraries, about 180 million lines of Rocq in total; a typical proof is about 600,000 lines for a binary with a median of 18,000 RISC-V instructions (section "Turning tests into proofs").
- Attempts versus successes. The appendix ("Details on Claude's generated proofs") says Claude wrote about one billion lines of Rocq across a few hundred attempted entry points, of which about 180 million were in proofs that passed the checker. Proofs ran from about 330,000 to 900,000 lines, in some 1,400 files each, and their size "barely tracks the library's": in the cJSON proof only about a tenth of the lines concern cJSON, because each proof covers the C start-up code, the allocator and ASan's runtime again from scratch. Over half of each proof is machine-emitted by tools Claude wrote, and checking one proof takes from 30 minutes to several hours of CPU time.
- Bugs found. The post says the attempts "discovered hundreds of bugs" (section "Finding and fixing bugs") and describes examples: a counter underflow in a copied decompressor that leads to an out-of-bounds write only on inputs of about 20 MB with one rare layout; an out-of-bounds read in an image decoder needing a 64 MB input and over 2 GB of memory; a bug needing a specific sequence of calls across two handles to one file; a rediscovery of a known libexpat vulnerability, CVE-2026-56132; and a logic bug in which a file-loading restriction was not always enforced. It notes that fuzzers typically cap inputs at 1 MB. The post does not give a full count or list, and says it is withholding proofs that could reveal unpatched bugs.
- What was released. The post says it is publishing a subset: Claude's complete proofs for fuzz tests that needed no patching, the trusted components, and specifications for tests it could not prove. The repository README lists 60 entry points in 25 libraries with proofs, checked with Rocq 9.2.0. Its provenance page says some proofs were written by Theorem and others adapted from proofs Anthropic wrote, and that many were adapted to the release's binaries and checked again (docs/origin.md).
Smaller case studies
- zlib. Claude wrote a formal specification of RFC 1950, the zlib format, and proved that the Linux kernel's zlib implementation meets it, working directly on the x86 binary with x86 semantics that Claude generated; the process was repeated for "half a dozen other widely used libraries," finding minor, unexploitable corner-case bugs (section "Other formal verification case studies"). Footnote 7 says the generated x86 semantics can boot an Ubuntu userspace and that generating them surfaced "hundreds of mistakes" in official reference documentation, though "we can not be sure our semantics themselves are perfect."
- A Python interpreter in Rust. Claude built an interpreter for a large subset of Python and proved, with the Verus tool, that it follows a formal semantics based on an academic paper. Run on over 1.7 million mostly random Python programs, it matched CPython in 99.95% of tests (post). The appendix adds that all 17 tiers of the interpreter verify, and that of seven bugs deliberately injected into an early version, five survived the random tests while all seven broke the proof ("Building a Python interpreter in Rust"). The proved theorem is partial: "Whenever the interpreter returns a result, that result is the one the formal semantics prescribes" (appendix), so it says nothing about runs that fail or never return. Agreement with CPython was measured empirically, not proved.
- Other applications. The post reports a logic bug latent for more than a decade in one widely used application and, in a PDF reader, "as many security bugs in one week as are typically reported in a year," without naming either.
Token efficiency and proof reuse
- Newer models. On 36 small verification tasks built by shrinking real OSS-Fuzz programs (283 to 2,491 instructions, inputs limited to 64 bytes, a simplified sanitizer; appendix), "Opus 5.5 proves half of them with about 40% fewer tokens than Opus 5" (section "Newer models need fewer tokens"). Each task had three independent single-agent attempts at a 5-million-token budget. The chart also shows Fable 5.1. The post gives no interval for the 40% figure.
- Shared workspaces. Agents allowed to copy one another's proofs used 17% fewer tokens than agents working alone; in 30 of the 34 completed proofs the shared-workspace cost was lower, and two proofs were completed only in the shared setting (section "Proofs can be reused"). At full scale, most of each proof concerns code every program contains, so agent teams copied and adapted other teams' finished proofs.
What the proofs do not cover
The post states the limits directly, in a section whose first paragraph opens: "Formally verified" does not mean "bug-free" (section "Limitations"). A proof holds only for its model of the machine and only for its stated claim. The trusted components are the RISC-V and Linux process models, the exact theorem statements and the Rocq checker, and through it the hardware, operating system and OCaml compiler it runs on (section "Turning tests into proofs" and footnote 5). Specifically:
- The machine model differs from deployment. The proofs concern single-threaded, static RISC-V binaries linked against the musl C library; most users run these libraries on x86 or ARM, dynamically linked against glibc (section "Limitations").
- The claim is narrower than "secure". ASan does not detect all memory-safety bugs, not every entry point of each library was verified, verifying all entry points would still not cover the whole library, and callers can misuse a library safely proved on its own.
- Termination is not covered. The post's introduction says Claude proved that the programs "will always exit normally," but the theorem the appendix states rules out faults, aborts and unmodeled behavior, not runs that never end; the appendix notes that a crash and a silent infinite loop look the same in the trace-based equivalence, which is why a separate no-crash theorem is needed for the plain build. The repository README at release adds that the release has no proof of a halting statement, "so none of them rules out a run that never ends," and that statements cover only inputs on which the plain build stays within its memory budget (2 GiB for statements about ASan builds). The 64 MiB limit is enforced by the test driver, which rejects larger files with status 2 (docs/statements.md). The repository has since grown: on 10 November 2026 its README lists 90 entry points in 32 libraries and 179 proved halting statements, each under its own premises (a 16 GiB memory premise and no unforced refusals by the environment).
- The model of Linux is incomplete. The README calls its process model "best effort and not complete."
Who checked the work
The Rocq kernel checks every published proof against its statement, and the post invites independent re-checking of the release. The appendix's section "How do Claude's proofs look to a human formal verification expert?" is the post's "expert's take," but the expert is not named. That section reports that agents often stated short specifications of what a program can output (median about 110 lines, against a median program of 86 KB) and then proved both builds match them, but that the proofs are verbose, spelling out register contents and every branch where human proof engineers "would have immediately introduced abstractions." It cites the experience of another project, MachCSL, to suggest that agents may "hit a complexity wall" with this style on more complex programs, and leaves open whether expert input is needed to find better abstractions. No outside replication or published critique was read for this note; secondary coverage mentions an analysis by Cornford and Cross (23 October 2026) that could not be found.
The specifications and instructions used
The text that governed the agents' work here is mostly formal: theorem statements generated mechanically from each compiled binary, the fuzz harness, and Theorem's semantics. The post describes the incentive used against one failure mode (penalties for patches and credit for minimal ones, footnote 6), and Theorem publishes a Claude skill file to help developers enroll their own projects. The post does not report varying the instructions given to agents or measuring their effect, apart from the comparison of solo and shared workspaces.
Limitations and open questions
- Developer-reported, with a partner. The results are reported by Anthropic and Theorem, which offers the pipeline as a service; the subset released, 60 of the 239 entry points, is about a quarter of those claimed (this note's arithmetic).
- Patch audit not reported. The post acknowledges that patching opens a route to reward hacking and describes safeguards, but gives no counts of patches or audit results.
- Bug counts not itemized. "Hundreds of bugs" is not broken down by severity, and most examples are unnamed.
- Small benchmark. The model comparison uses 36 simplified tasks, three attempts each, with no interval reported.
- Model-written trusted components in places. The x86 semantics used for zlib were generated by Claude and tested empirically; the post says they may not be perfect.
- Scaling of the proof style is uncertain, by the appendix's own expert section.
Research questions
- How many patches did Claude make, and how many changed behavior beyond the bug? The post names the reward-hacking risk. Publishing the patch log with the audit outcome would show whether the safeguards worked.
- How do the found bugs break down? Counts by severity, with how many were confirmed and fixed upstream, would let readers compare the bug-finding yield with fuzzing on the same targets.
- How much does the RISC-V and musl setting limit the guarantee in practice? Re-running a sample of proofs against x86 or ARM semantics with glibc, or testing the released binaries' behavior against deployed builds, would measure the gap the post names.
- Can agents be taught the abstractions human proof engineers use? The expert section asks this. Comparing proof size and success rate with and without supplied abstractions (a calling-convention model, a disjoint-pointer notion) would answer it.
- Is the 40% token saving robust? Repeating the 36-task comparison with more attempts per task and reporting intervals would show how much of the difference between model generations is noise.
- Does proof reuse keep paying at scale? Tracking tokens per new library as the shared body of proofs grows would test the post's argument that reuse amortizes cost across the dependency graph.
How it connects
- Measuring LLMs’ ability to develop exploits is the post this one links in its opening sentence, on AI's ability to find and exploit bugs, part of its motivation.
- Partnering with Mozilla to improve Firefox’s security (March 2026) reports model-found vulnerabilities in Firefox; this post cites a later Mozilla blog post (May 2026) on hardening Firefox as evidence that AI now finds bugs easily. The link to the library note is the note's own.
- Formalizing Fermat's Last Theorem reports machine-checked proof at a similar scale in mathematics, in Lean; both rely on a proof checker as the arbiter and both report verbose, machine-written proofs. The comparison is the note's own.
- Progress on provable inference for large language models, a Frontier Red Team post from November 2026, also pairs AI-written code with formal proofs and distinguishes what is proved from what is trusted. The connection is the note's own.
- Discovering cryptographic weaknesses with Claude is another Frontier Red Team report of model-found security results with human validation. The connection is the note's own.
References
- Lucas, K., Lynch, A., Tong, L., et al. (2026, October 22). LLMs are making formal software verification feasible at a much larger scale. Anthropic Frontier Red Team, in collaboration with Theorem. https://www.anthropic.com/research/formal-verification record
- Anthropic (2026, October 22). Appendix: LLMs are making formal software verification feasible at a much larger scale. 6 pages. https://assets.claude.com/6867eadf760258fa8b42a504600cd3c036d16358.pdf record
- Google OSS-Fuzz. projects/lzo/lzo_compress_target.c (last changed 7 December 2023). https://github.com/google/oss-fuzz/blob/master/projects/lzo/lzo_compress_target.c record
- Theorem. OSS Verify: proofs about OSS-Fuzz fuzz targets. https://github.com/theorem-labs/oss-verify-proofs, README.md, docs/origin.md and docs/statements.md read at release commit 8f5f467 (22 October 2026). record
- Theorem. A Rocq model of a Linux process that runs a RISC-V binary. https://github.com/theorem-labs/rocq-linux-process-semantics (the release pins commit f1006fe; not read in detail). record
- Theorem. OSS Verify (program page). https://theorem.dev/oss-verify/ record