After studying this material, you should be able to:

1. Explain what formal software verification is and why it matters
2. Describe how LLMs are making formal verification scalable
3. Understand the workflow of converting fuzz tests into formal proofs
4. Identify the limitations and trusted components of this approach
5. Recognize efficiency improvements that make this approach practical

---

Step-by-Step Teaching

Step 1: The Core Problem — Why Software Has Bugs That Won't Go Away

Start with the fundamental challenge.

The reality:

• Even the most tested software contains bugs
• The Linux kernel — running on billions of devices — had 1,000+ vulnerabilities disclosed recently
• AI models are now capable of chaining small, seemingly harmless bugs into critical exploits

Traditional defenses are no longer enough. We need something stronger than just finding bugs — we need to prove they don't exist.

Key insight: Testing can show the presence of bugs, but never their absence. No matter how many tests you run, you cannot guarantee you've covered every possible scenario.

---

Step 2: What Is Formal Verification?

Think of it as mathematical proof applied to code.

The process:

Code → Mathematical Model → Prove it follows security rules
         ↓
    If proof fails → Bug likely exists → Fix it → Try again
         ↓
    If proof succeeds → Guaranteed: no bug of that type exists

Real-world analogy:

Testing is like checking whether a bridge holds by driving cars over it repeatedly. Formal verification is like proving mathematically, using engineering equations, that the bridge cannot collapse under defined conditions.

Historical cost example:

This 10x cost ratio explains why formal verification was historically reserved only for mission-critical systems like Airbus avionics.

---

Step 3: The Specification Problem — What Does "Correct" Even Mean?

Before you can prove code is correct, you must define correctness. This is called the specification (spec).

Easy case: A PNG decoder — correctness means "follows RFC 2083 standard"

Hard case: A web browser — what does "correct" even mean here?

The clever solution used in this project:

Instead of writing specs from scratch, they converted existing fuzz tests into specs.

The rule becomes:

"This test suite always passes — for every possible input"

This sidesteps the hardest part of formal verification: writing the spec yourself.

---

Step 4: Understanding Fuzz Testing (The Starting Point)

You need to understand fuzz testing to appreciate the breakthrough.

How fuzzing works:

Developer writes entry point → Fuzzer generates millions of random inputs
                                        ↓
                              Any input that causes a crash = Bug found

Fuzzing's fatal limitation:

• There are infinite possible inputs
• The search can never be complete
• You can run trillions of tests and still miss a bug hiding in a rare edge case

Example from the article:

A bug was found that only triggered on inputs of ~20 MB with one specific rare layout. A fuzzer capped at 1 MB would never find this.

---

Step 5: The Core Innovation — Turning Fuzz Tests Into Proofs

This is the central breakthrough of the project.

The transformation:

Fuzz Test (finds bugs by chance)
        ↓
Compiled to RISC-V assembly
        ↓
+ Formal semantics of RISC-V + Linux OS
        ↓
Specification: "No crash for ANY input under 64 MB"
        ↓
Claude writes a formal proof
        ↓
Rocq proof checker verifies the proof
        ↓
RESULT: Mathematically guaranteed — fuzzing this entry point will never find new bugs

Why RISC-V assembly level?

• Proofs at the binary/assembly level mean you don't need to rewrite code in a special language
• The proof covers the actual code that runs, not just a high-level model of it

Scale achieved:

• ✅ 239 entry points proven
• ✅ 123 open-source libraries
• ✅ ~180 million lines of Rocq proof code
• ✅ Typical proof: ~600,000 lines covering ~18,000 RISC-V instructions

---

Step 6: What Gets Trusted — And What Doesn't

This is critical for understanding the honest limits of the approach.

You do NOT need to manually review the 180 million lines of proof. The Rocq proof checker does that automatically.

What you DO need to trust (the "trusted components"):

Key insight:

Instead of trusting millions of lines of application code, you only need to trust a small, well-defined set of components. Bugs can only hide in those components — and that's a much smaller attack surface.

---

Step 7: Bug Discovery as a Side Effect

An unexpected benefit emerged: attempting to write proofs finds bugs that testing never would.

Bugs discovered during this project:

The key insight:

Fuzzers find bugs by crashing. Logic bugs that don't crash are invisible to fuzzers. Formal verification finds them because it reasons about all behaviors, not just crashes.

---

Step 8: Proving More Than Just "No Crashes"

The approach proves richer properties than it first appears.

Example — LZO compression:

Fuzz test asserts: compress(input) → decompress → equals original input
If this fails → program crashes
Proving "no crash" = Proving "compression always round-trips correctly"

Example — cpp-httplib (surprising depth): To prove no stack overflow, Claude had to prove that:

libc++'s red-black tree rebalancing algorithm correctly keeps tree depth logarithmically bounded

...at the machine code level. This demonstrates that proofs can capture deep algorithmic correctness properties, not just surface-level safety.

---

Step 9: Efficiency — Why This Will Keep Getting Better

Two mechanisms are driving down cost:

Mechanism 1: Better Models Need Fewer Tokens

Opus 5 → Opus 5.5: Same tasks completed with ~40% fewer tokens

As models train on more verification tasks, they get more efficient.

Mechanism 2: Proof Reuse

Proofs are modular — built from smaller sub-proofs that can be shared.

Observed savings:

• Agents sharing a workspace used 17% fewer tokens than solo agents
• Some agents succeeded only when they could reuse others' work

Why this scales:

Most programs share common code (C runtime initialization, AddressSanitizer setup). Once that shared code is proven, every new program can reuse that proof and only prove its unique parts.

Analogy: This is how Mathlib (a formal math library) grew to 300,000 theorems — each new proof builds on existing ones.

---

Step 10: Honest Limitations

Understanding what the approach cannot guarantee is as important as understanding what it can.

Limitation 1: "Formally verified" ≠ "Bug-free"

The proof is only as good as the spec. If the spec doesn't match reality, bugs can still exist.

Limitation 2: The Model May Not Match Deployment

Limitation 3: Coverage Gaps

• ASan doesn't detect all memory safety bugs
• Not all entry points were verified for each library
• Dead code is not covered
• Callers of the library could still misuse it

The honest summary:

These proofs don't mean the libraries are bug-free. They mean: any remaining bugs must be in the trusted components or outside the proof's scope — and we know exactly where to look.

---

Summary: The Big Picture

BEFORE LLMs:
Formal verification → Requires expert years → Only for critical systems (avionics)

WITH LLMs:
Fuzz tests → Auto-converted to specs → Claude writes proofs → Rocq checks them
→ 123 libraries proven in weeks → Bugs found that survived trillions of test runs
→ Cost falling as models improve → Proof reuse compounds savings

TRAJECTORY:
Formal verification will become as routine as unit testing

The three-sentence takeaway:

Formal verification provides mathematical guarantees that code is free of certain bugs, but historically required years of expert effort. LLMs can now write these proofs autonomously at scale, by converting existing fuzz tests into specifications and proving them at the assembly code level. While limitations remain around spec completeness and deployment environment matching, the cost is falling rapidly, making this approach increasingly practical for mainstream software development.