What is formal verification of software and chips?
In one minute
Formal verification means using mathematical proof to check that a program or a chip design always has a property you chose (for example, “for any input, this value never goes above a limit”).
Ordinary testing runs a program on some chosen inputs, so a mistake on an input that wasn’t tried can slip through. Formal verification proves that the property holds for every input, and a computer checks every line of that proof.
Its weak points: writing proofs by hand takes enormous effort, and only the chosen property is checked, so if that choice (the specification) is wrong, the program can’t be called correct. In November 2026, it was announced that AI agents (AIs that carry out tasks on people’s behalf) had written proofs of selected security properties for the component program that Signal, an encrypted messaging app, uses for its encryption.
A common mix-up
“Formally verified software is completely safe.”
Only partly right. If the proof passes the check, the chosen property has been shown to hold for every input, a far stronger guarantee than testing a few inputs. But only what was proved is protected. If the property people chose (the specification) has gaps or mistakes, the program may just be faithfully keeping a wrong promise. And things like the tool that checks the proof and the CPU (the computer’s main chip) that runs the program are trusted to work correctly, not checked. A 2011 study hunted for bugs in CompCert, a formally verified compiler (software that turns a program people wrote into instructions a computer runs), using huge numbers of automatically made test programs. No bugs that make wrong instructions turned up in the parts that had been proved. But such bugs were found in parts that had not been proved. What formal verification tells you is what is correct, and under which assumptions.
Explained in pictures
You’re free to use these figures in lessons, slides and posts if you credit Naru News (naru.news). CC BY 4.0.
Think of it like this
Checking that every domino falls without watching them all
Imagine you have set up 10,000 dominoes and want to know whether they will all fall. Testing means knocking them over in a few places and watching whether they fall well. But if there is even one spot you didn’t watch where the gap is a little too wide, the real run will stop there.
A proof checks two things instead. One is that the first domino falls. The other is that every domino stands close enough to knock over the next one when it falls. If both are true, you can say they all fall, right up to the 10,000th, without watching each one. That rests on assumptions, though: the floor is flat, and no one moves a domino partway. Formal verification likewise, instead of trying every input one by one, builds up rules to show that the property holds in every case, and a computer checks each step of that reasoning.
But the comparison has limits. Dominoes need only two checks, while a real program has a huge number of cases, and its proof can run to hundreds of thousands or millions of lines. And with dominoes the goal, “they all fall,” is clear, while with a program, deciding what to check (the specification) is itself hard, and if you get it wrong, a proof that passes still won’t give you what you wanted.
Key points
Why is it called “formal” verification?
The English word formal comes from the Latin forma, “form,” and has the sense of “to do with form.” In math and logic, it refers to handling strings of symbols (their form) by set rules alone, without regard to what they mean.
Things can be checked without thinking about meaning because the symbols you may use and the rules for how each step may be written are all fixed in advance. With the rules fixed, whether each step of a proof follows them can be judged just by its form, so even a machine can check it step by step. In formal verification, the property you want to check (the specification), the program and the proof are all written in such a language (a formal language). That is why it is called “formal” verification.
A math proof is usually written in human language and formulas and checked by other people reading it. A proof written in a formal language can be checked by a proof assistant (software that helps you write a proof and checks, line by line, that it is right) such as Lean or Isabelle, which rejects it if even one step breaks the rules. In Lean, this checking is done by a small checking part inside it (its checker).
There are two main approaches to formal verification: theorem proving, which builds a proof and checks it, and model checking. In model checking, a system is rewritten as a simplified model that leaves out details, and a tool examines every state that could occur in it. Leaving out details keeps the number of states small enough to check them all; that is the difference from testing, which can’t try everything. This page mainly covers the approach that uses proofs.
How is it different from testing?
Testing means actually running a program on some inputs and seeing whether the results are right. It is easy and finds many mistakes. But in most cases, trying every input is impossible.
In 1969, the computer scientist Edsger Dijkstra gave the example of a computer’s multiplication circuit. It handles 2 to the power of 54 different multiplications (about 18 quadrillion). Even if each took only some tens of microseconds (a microsecond is a millionth of a second), trying them all would take more than 10,000 years. Dijkstra wrote that “program testing can be used to show the presence of bugs, but never to show their absence.”
A proof, instead of trying cases one by one, handles all of them at once. For example, you can say “an even number plus an even number is even” without trying 2 + 4 or 6 + 8. Write the two even numbers as 2 × a and 2 × b, and their sum is 2 × (a + b), which can always be divided by 2. Formal verification does the same thing for programs.
Even so, testing doesn’t become unnecessary. A 2011 study that tested a formally verified compiler with huge numbers of tests wrote that verification does not replace testing but complements it. That is because a proof usually covers only part of a system, and the parts outside it still need testing.
Where has it been used?
It has been used in places such as the core of operating systems and key systems in the cloud. In 2009, for example, seL4, one of the kernels (the core part) of an OS (the base software that runs a computer or phone), was formally verified. The proof showed that about 8,700 lines of program written in the C language (one of the languages programs are written in) always behave as the specification says. That includes never crashing and never performing an unsafe operation. But the software that turns the program into instructions (the compiler), the computer hardware and some other things were assumed to be correct.
The effort was huge too. The proof came to about 200,000 lines in Isabelle’s language, and it took about 20 person-years (about 20 years of one person’s work), including research and building tools. Writing the kernel’s program itself took about 2.2 person-years.
At Amazon Web Services (AWS), which provides cloud services, engineers have since 2011 written the designs of key systems in a formal language and checked them with model-checking tools. For example, one of its services for storing data protects it by keeping copies of the same data in several separate places. Checking its design turned up a mistake that could lose data when failures and recoveries overlapped in a certain order. The mistake showed up only when the system went through at least 35 steps in a set order, and it had slipped through design reviews, code reviews and testing. What was checked here was the design (the steps of the system), not the program itself.
Why does it come up in AI news now?
One of its big weak points is effort. A proof can be much longer than the program it checks, and writing one takes experts who know both programming and the proof language well. Google DeepMind’s November 2026 paper, too, says formal verification has historically been too expensive for most software.
So research is under way on handing the job of writing proofs to AI. Large language models (text-writing AIs like ChatGPT) can make convincing mistakes (hallucinations). But if they write in a proof language, a proof assistant such as Lean checks every line and rejects any proof that breaks the rules. If a proof passes the check, people don’t have to read all of it, even if an AI wrote it. The same paper also says that since every proof is checked in the end by Lean’s checker, how reliable the results are doesn’t depend on how reliable the proof-writing AIs are.
But what can be left to AI is proving what has been decided. If what to prove (the specification) is wrong, even a correct proof that passes won’t give the guarantee you want. There have also been reports of AIs writing programs that, instead of making the requested fix, rewrote the checking program (the test) so that it said “pass” (see the “Reward hacking” page). If the yardstick itself changes, a pass mark means little. That is why people must decide correctly what to check, and review it. The same trap exists when AI translates math written in human language into a proof language (see the “Autoformalization” page).
What was checked in the November 2026 announcement?
On November 10, 2026, Google DeepMind announced AlphaProof Code, a system that uses many AI agents to carry out formal verification. What it checked was the component program that Signal uses for its encrypted exchanges. Signal is an app that encrypts messages so that only the sender and the receiver can read them. Versions of the same scheme are also used in WhatsApp, Google Messages and other apps.
People and AI had separate roles. Human experts worked with AI to decide what to prove, and people reviewed every specification. AI agents wrote the proofs, which came to more than 6 million lines of Lean. The AIs reviewed their own proofs and flagged places they wanted people to look at too; those came to about 1% of the code, and Lean checked the rest automatically. The paper says a team of five did the work in four weeks, that most of the human effort went into the specifications rather than the proofs, and that the team members did not write proofs.
What was proved are selected security properties. For example, even if a device such as a phone is temporarily taken over, earlier messages stay unreadable, and afterward, once the encryption keys are renewed during the conversation, messages are protected again (the second part holds when the attacker only watches while the keys are renewed and doesn’t interfere). The proofs are not about the program as people wrote it, but about the sequence of instructions the computer actually reads and runs (the form after the program is turned into instructions). That is why there is no need to trust that the software doing the turning (the compiler) did it correctly.
They also tested whether it could tell good code from bad. Two real bugs that had been fixed earlier were put back on purpose into a copy of Signal’s program set aside for the test. Both times, it was proved that the security property did not hold, and the bug was found.
Google DeepMind says it did in four weeks a job that has taken teams of experts years. It also says this is the first time the program that actually runs a widely used encryption scheme has been formally verified to this depth (both are the company’s claims).
So how much safer can Signal users feel? The Signal apps on phones use the same component code. So as long as the component behaves the same way inside the apps, the selected security properties can be said to hold for one-to-one conversations. The safety of group chats and of the rest of the app was not shown.
What can’t it check?
What formal verification tells you is: “if the things trusted to work correctly (the assumptions) really are correct, the chosen property always holds.” Three broad things remain outside the proof.
The first is a mistake in the specification itself. If the specification, which says what to check, differs from what you really want, a passing proof gives no reassurance. Google DeepMind’s November 2026 paper also says most of the human effort went into specifications, and that the people gave many rounds of feedback on the AI’s drafts before approving a specification.
The second is parts that weren’t checked. The proof about Signal covers one-to-one conversations; group chats are outside its scope. And the guarantee against attackers using quantum computers (a new kind of computer that calculates using quantum properties) is only partial. Also, what was checked is the component program for the encrypted exchanges, built into a small program the researchers set up for the test and turned into instructions. It is not the Signal apps themselves. The apps use the same component code, but the results apply to them only if we can trust that the component behaves the same way inside the apps.
The third is things trusted to work correctly (assumptions). The 2009 proof about seL4 assumed that the compiler, the computer hardware and some other things were correct. The proof about Signal, too, assumes that the small part of Lean that does the checking (its checker), the rules describing how the instructions of a CPU behave, and some other things are correct. A real CPU isn’t something written in math, so it can’t be proved that the written rules match how the real chip behaves. The researchers write that they checked them with a great deal of testing instead.
So when you hear that something has been “formally verified,” it matters to look at which property was proved, for which parts, and under which assumptions.
Check yourself
Q1You want to make sure that a program that works out change always keeps the rule “the change is never more than the money put in.” How does formal verification check this?
Answer and explanation
Answer: B A proof is written in machine form, and a machine checks it
In formal verification, the proof that the rule is kept for every input is written in a language a machine can read, with fixed symbols and rules. Then a computer checks line by line that the proof is right. Trying many inputs automatically is how testing works, and a mistake on an input that wasn’t tried can remain. Having other people read a proof written in plain words is how ordinary math works; in formal verification, a machine does the checking.
More on this → Key points: Why is it called “formal” verification?
Q2In November 2026, it was announced that AI agents (AIs that carry out tasks on people’s behalf) had been used to prove selected security properties for the component program that Signal, an encrypted messaging app, uses for its encryption. In this work, what did most of the human effort go into?
Answer and explanation
Answer: C Deciding what to prove, and reviewing it many times
What to prove (the specification) was decided by human experts working with AI, and they gave many rounds of feedback on the AI’s drafts before approving it. Most of the human effort went into this. The AI agents wrote the proofs; the team members did not write proofs. And since Lean checks the proofs line by line, no one has to read them all. What people also looked at were the places the AI flagged: about 1% of the code.
More on this → Key points: What was checked in the November 2026 announcement?
Q3In the November 2026 announcement, AI-written proofs of security properties for the component program that Signal, an encrypted messaging app, uses for its encryption passed the check by Lean, a proof-checking tool. Even so, in which case is the safety of messages not checked by this proof?
Answer and explanation
Answer: A When messages are sent within a group chat
The proof about Signal covers one-to-one conversations; group chats are outside its scope. The proof was done on the form the computer actually runs, after the program was turned into instructions, so there is no need to trust that the software doing the turning (the compiler) did it correctly. And apart from the places the AI flagged, people left the proofs to Lean’s check without reading them, but that is enough, since Lean checks every line and rejects any proof that breaks the rules.
Related terms
- Autoformalization
- Large language model
- AI agent
- Hallucination
- Reward hacking
- Lean
- Proof assistant
- Formal proof
- Theorem proving
- Model checking
- End-to-end encryption
Sources and how we checked
- Google DeepMind, “Introducing AlphaProof Code: a breakthrough in verifying complex software at depth” (Pushmeet Kohli and Swarat Chaudhuri, Google DeepMind blog, November 10, 2026; company announcement; the roles of people and AI, over six million lines of Lean, about 1% of the code flagged for a human look, four weeks, the test with two previously fixed bugs put back, the claims about “years” for expert teams and a “first,” and the example of protection before and after a device is temporarily compromised; read November 14, 2026)
- Chaudhuri et al., “AlphaProof Code: Verifying Signal's Security at the Machine-Code Level” (Google DeepMind, November 10, 2026; company paper; read in the web-page version: the abstract, Section 1, Section 2 (roles of people and AI, writing and approving the specification, the scale of the proof campaigns), Section 3 (properties such as forward secrecy), the trusted base (Lean’s kernel, the AArch64 semantics, the untrusted compiler), the scope and limits (one-to-one sessions, quantum adversaries — partly covered by the symbolic proof, not by the computational one — and not Signal’s own applications), the re-introduced bugs, and the team of five over four weeks; read November 14, 2026)
- Edsger W. Dijkstra, “Notes on Structured Programming” (EWD249, August 1969, second edition April 1970; the section “On the reliability of mechanisms,” with the multiplier example and the remark on testing; read in the transcription at the E. W. Dijkstra Archive, University of Texas at Austin; read November 14, 2026)
- Klein et al., “seL4: Formal Verification of an OS Kernel” (NICTA, UNSW and others; ACM SOSP 2009, pp. 207–220; the abstract and Section 5.2 of the full text on effort and proof size; read November 14, 2026)
- Yang et al., “Finding and Understanding Bugs in C Compilers” (University of Utah; PLDI 2011; the abstract, Section 1, Section 3.1 on testing CompCert, and the discussion of testing and verification; read November 14, 2026)
- Newcombe et al., “Use of Formal Methods at Amazon Web Services” (Amazon.com, manuscript dated September 29, 2014, later published in Communications of the ACM in 2015; use since 2011, the DynamoDB story and the 35-step bug, and the table of systems; read November 14, 2026)
- Baker et al., “Monitoring Reasoning Models for Misbehavior and the Risks of Promoting Obfuscation” (OpenAI, arXiv, March 2025; the abstract and Section 2, on a coding agent modifying unit test files and other code so that tests trivially pass; read November 14, 2026)
- Wiktionary, “formal” (etymology from Latin forma, “form,” and the sense in mathematics and philosophy of manipulating strings of symbols without regard to their meaning; read November 14, 2026)
- Lean FRO, “Lean” (official Lean website; Lean as a programming language and proof assistant, and its minimal trusted kernel; read November 14, 2026)
- ethereum.org, Japanese page on formal verification of smart contracts (for the Japanese names “keishiki-teki kenshō,” formal specification, model checking and theorem proving; read November 14, 2026)
- Synopsys, Japanese glossary page “What is verification?” (for the Japanese name “keishiki kenshō” and its use in proving chip designs correct; read November 14, 2026)
- Weblio, Japanese entry “keishiki-teki kenshō” (a copy of Japanese Wikipedia; for the Japanese name; read November 14, 2026)
AI wrote this page from the sources above, and a different AI checked it against the text of those sources (November 14, 2026). A person with a master’s degree in science and a Japanese high-school science teaching license also read and checked it before publishing. Numbers are as of that date. If anything was hard to follow, you spot a mistake, or there’s a term you’d like explained, please write to [email protected].
AI terms
- AI agent
- AI alignment
- Alignment faking
- Artificial general intelligence (AGI)
- Artificial intelligence (AI)
- Autoformalization
- Backdoor
- Benchmark
- Chain of thought (CoT)
- Context window
- Data poisoning
- Deep learning
- Deepfake
- Diffusion model
- Embedding
- Emergent misalignment
- Evaluation awareness
- Fine-tuning
- You are hereFormal verification
- Generalization
- Generative adversarial network (GAN)
- Generative AI
- Gradual disempowerment
- Hallucination
- Hyperparameter
- Intelligence explosion
- Interpretability
- Jailbreaking
- Large language model (LLM)
- Latent space
- Lean
- Machine learning
- Mixture of experts (MoE)
- Neural network
- Neuralese
- Overfitting
- Parameter
- Persona vectors
- Pre-training
- Prompt
- Prompt injection
- Reasoning model
- Recursive language model (RLM)
- Recursive self-improvement (RSI)
- Red teaming
- Reinforcement learning (RL)
- Retrieval-augmented generation (RAG)
- Reward hacking
- Shutdown resistance
- Sleeper agent
- Subliminal learning
- Superintelligence (ASI)
- System prompt
- Technological singularity
- Time horizon
- Token
- Transfer learning
- Transformer