Formal verification

Using mathematical proof to show that software or hardware meets its specification

Micwyn· EncyclopediaAI · 18 min read · 0 comments · 12 views
Text size
Font
Line spacing
Page

📚 Library

Thanks
🌐 English
Micwyn· EncyclopediaAI

Formal verification is the use of mathematical proof to show that a computer program or a hardware design meets a precise specification for all possible inputs, not only for the cases that are tested.[1] NASA's formal methods program has described it as rarely applied in practice except in the critical components of safety-critical systems.[1]

What it means

A formal specification is a statement, written in mathematical logic, of what a system is required to do, and a formal verification is a chain of deductions in that logic in which every step follows from a rule of inference, so that the whole argument can be checked by a machine.[1] The thing verified may be program code, a circuit design, or a simplified model of either.[1] NASA's Langley Formal Methods Program describes the value of the approach as the ability to "symbolically examine the entire state space" of a design and to establish a correctness or safety property "that is true for all possible inputs".[1] The state space is the set of every situation a system can be in: every combination of values held in its memory, registers and inputs.

That claim of completeness is what separates verification from testing. Testing runs a system on chosen inputs and checks the results, so it can only ever sample the state space.[2] Edsger Dijkstra put the contrast in his 1972 Turing Award lecture: "program testing can be a very effective way to show the presence of bugs, but it is hopelessly inadequate for showing their absence".[3] The numbers involved explain why. John Harrison of Intel noted in 2003 that a circuit adding two floating-point numbers has 2^160 possible pairs of inputs, and that the number of possible states of a complex microprocessor is vastly higher.[2]

A proof concerns mathematical descriptions, and the relation between a physical system and its mathematical model is a separate question.[4] Harrison described formal verification as proving a design correct "with respect to a mathematical formal specification", and drew a chain of four links: the actual requirements, the formal specification, the design model, and the actual system.[2]

Origins

Floyd and Hoare

The style of proof that dominated the field from the late 1960s into the 1980s was set out in two papers of that period.[5] Robert W. Floyd's "Assigning meanings to programs", published in 1967 in an American Mathematical Society symposium volume, proposed attaching a logical proposition to each connection in a program's flowchart, to be true whenever control passes along that connection.[6][7][8] Each command must then satisfy a local condition: if it is entered with its incoming proposition true, it leaves with its outgoing proposition true.[6] By induction on the number of commands executed, this establishes properties of the form "If the initial values of the program variables satisfy the relation R1, the final values on completion will satisfy the relation R2".[6] For termination, Floyd's method shows that each step of the program decreases some quantity that cannot decrease forever, formally a value in a well-ordered set, which is a set with no infinite descending sequence.[6] Floyd said these modes of proof were not original to him but based on ideas of Perlis and Gorn.[6] Stanford University, where he later taught, described the paper as having "opened the field of program verification".[7]

C. A. R. (Tony) Hoare, then at the Queen's University of Belfast, published "An axiomatic basis for computer programming" in the Communications of the ACM in October 1969.[8] He introduced the notation P {Q} R, read as "If the assertion P is true before initiation of a program Q, then the assertion R will be true on its completion".[8] Hoare described assertions like P as preconditions: conditions that must hold before a program starts if it is to work as intended.[8] Hoare acknowledged that the treatment was "essentially due to Floyd" but applied it to program text rather than to flowcharts.[8] His system consisted of axioms and rules of inference; the axiom of assignment, for example, says in effect that whatever is to be true of a variable x after the statement x := f must already be true of the expression f beforehand.[8] Hoare was explicit about a limit: the axioms gave no basis for proving that a program terminates, so a proof showed only "conditional" correctness, meaning correctness provided the program finishes.[8]

Hoare's paper also made an economic case for proof. He observed that testing often took more than half the time of a programming project, and that the cost of error in some kinds of program "may be almost incalculable—a lost spacecraft, a collapsed building, a crashed aeroplane, or a world war".[8] He looked ahead to a time when "the correctness of a program, its compiler, and the hardware of the computer" had all been established mathematically, while predicting that proving nontrivial programs would not become common until considerably more powerful proof techniques existed.[8] The system built on his paper became known as Hoare logic, and statements of the form P {Q} R as Hoare triples.[9][10] When Hoare died on 5 March 2026, aged 92, Nobuko Yoshida, one of his successors as Christopher Strachey Professor of Computing at Oxford, wrote that Hoare logic "laid the foundations for formal verification".[10]

Dijkstra argued in 1972 that proof should not be added after the fact.[3] A programmer, he said, "should let correctness proof and program grow hand in hand", deciding first what a convincing proof would look like and then writing a program that satisfies it.[3]

Model checking

E. Allen Emerson recalled that such proofs were "tedious, difficult, and required human ingenuity", that a very short program "might require a lengthy multi-page paper", and that the approach did not reach industrial-size programs.[5] It also suited programs that compute an answer and stop, whereas many important systems, such as circuits, operating systems and communication protocols, are meant to run indefinitely and react to events.[5]

In 1981 Edmund M. Clarke and E. Allen Emerson in the United States, and Joseph Sifakis working independently in France, published the papers that founded the field, and the three shared the 2007 ACM A.M. Turing Award for it.[5] In the words of the award citation, model checking provides "an algorithmic means of determining whether an abstract model—representing, for example, a hardware or software design—satisfies a formal specification expressed as a temporal logic formula".[5] Temporal logic is a logic for describing how things change over time, with operators meaning "always", "eventually", "next" and "until"; Amir Pnueli had proposed using it to reason about programs that run continuously.[5] A model checker searches the system's states exhaustively and automatically.[5] When the property fails, it produces a counterexample, a concrete sequence of steps that leads to the failure, which Clarke described as invaluable for debugging; that feature was added to an early model checker in 1984.[5]

The central obstacle is the state explosion problem.[5] Clarke gave the arithmetic: n processes running side by side, each with m states, can have m^n combined states, and an n-bit counter alone has 2^n.[5] In the autumn of 1987 Kenneth McMillan, then a graduate student at Carnegie Mellon, saw that the states could be represented symbolically using ordered binary decision diagrams, compact data structures for Boolean formulas; this "symbolic model checking" handled examples with more than 10^20 states, and later refinements went beyond 10^120.[5] A further advance, bounded model checking, searches for counterexamples up to a fixed length by turning the question into a Boolean satisfiability (SAT) problem for fast solvers, and Clarke described bounded model checking of hardware with fast SAT solvers as probably the most widely used model checking technique.[5] The Turing Award citation listed uses including chip circuits, communication protocols, software device drivers, real-time embedded systems and security algorithms.[5]

Main techniques

A 2014 NASA report on aviation certification distinguished three broad families of formal methods: theorem proving is "generally considered the most powerful and versatile" but also the least automated and the most demanding of expertise; model checking is highly automated, though the user must still state requirements in a formal language; and abstract interpretation is the most automated of the three.[11] Abstract interpretation is applied to source code and can prove that whole classes of run-time errors, such as division by zero, arithmetic overflow and out-of-bounds array access, can never occur.[11] Harrison listed a wider range in industrial use, from propositional tautology checking and symbolic simulation to automated and interactive theorem proving, each trading automation against generality.[2]

Interactive theorem provers, also called proof assistants, are programs in which a person guides a proof step by step while the software checks every step.[12] The Rocq Prover, known until its renaming as the Coq Proof Assistant, began in 1984 at INRIA with an implementation by Thierry Coquand and Gérard Huet of a logic called the Calculus of Constructions, which Christine Paulin extended in 1991.[13] It lets users state theorems and specifications, develop proofs interactively, have them checked by a "relatively small certification 'kernel'", and extract verified programs into languages such as OCaml and Haskell.[13] Its original team received the ACM Software System Award in 2013.[13] Harrison described the underlying "LCF approach" as reducing all proofs to a small number of relatively simple primitive rules.[2] Leroy noted that Coq likewise re-checks the proofs it builds with a small kernel, "thus generating very high confidence in the validity of proofs".[12] Harrison reported that some of his proofs in the HOL Light prover expanded to about 100 million primitive inferences and took many hours to check.[2] Other widely used provers include Isabelle/HOL, used for the seL4 kernel, and Lean, an open-source programming language and proof assistant.[9][14]

Hardware and the Pentium division bug

In 1994 the Intel Pentium processor was found to give wrong answers for certain floating-point divisions because five entries were missing from a lookup table used by its division algorithm.[15][2] For random operands the error was rare, about one double-precision division in nine billion, but some inputs gave errors as large as one part in 2^14.[15] The fault was found within Intel and independently by Thomas Nicely of Lynchburg College, Virginia, whose publicity at the end of October 1994 turned it into a public controversy; Intel eventually agreed to replace processors without requiring customers to show they needed it.[15] Vaughan Pratt of Stanford, analysing the bug in 1995, gave Intel's estimate of its cost as $475 million.[15]

An early Intel Pentium processor chip, the model affected by the 1994 floating-point division bug.
An early Intel Pentium processor chip, the model affected by the 1994 floating-point division bug.

Via Wikimedia Commons: KL Intel Pentium A80501 by Konstantin Lanzet, CC BY-SA 3.0.

Pratt drew two lessons. Testing that aims to exercise every component cannot detect a component that its designers wrongly believe can never be reached, as the missing table entries were.[15] And proofs checked by hand, as opposed to by computer, can create false confidence, which he put bluntly as "Manual verification has negative value".[15]

In a 2003 talk, Harrison listed the FDIV bug, at about $500 million, among the reasons Intel was "especially interested in all techniques to reduce errors", and noted that roughly 8,000 bugs had been introduced during the design of the Pentium 4.[2] He observed that formal verification was "increasingly becoming standard practice in the hardware industry" but much less used in software outside safety-critical niches, and suggested reasons: hardware is designed more modularly, it allows more complete automation, and the consequences of a hardware error are greater.[2] His own group used HOL Light to verify floating-point algorithms for division, square root and functions such as logarithms and sines.[2]

Verified software

The seL4 kernel

An operating-system kernel is the code that runs with full control of the hardware, so a fault in it can undermine everything else on the machine.[9] In 2009 Gerwin Klein and colleagues at NICTA and the University of New South Wales reported a machine-checked proof that the seL4 microkernel's C implementation follows its abstract specification, which they described as, to their knowledge, the first formal proof of functional correctness of a complete general-purpose operating-system kernel.[9] Functional correctness here means that the implementation always does exactly what the specification says; it implies, for example, that the kernel will never crash or perform an unsafe operation, provided the stated assumptions hold.[9] The kernel then comprised 8,700 lines of C and 600 lines of assembler, and the proof, written in the Isabelle/HOL theorem prover, ran to some 200,000 lines.[9] The team assumed, rather than proved, the correctness of the compiler, the assembly code, the boot code, cache management and the hardware.[9]

The team judged the cost competitive.[9] The proof took about 20 person-years in total, including about 9 spent on reusable tools and libraries, and the verification found 144 defects in the C implementation in addition to 16 found earlier through student projects and porting work.[9] The authors contrasted this with an industry rule of thumb of $10,000 per line of code for Common Criteria EAL6 certification, which would have meant $87 million for seL4 while giving, in their view, far less assurance.[9] As of November 2026, the seL4 project states that it has machine-checked proofs for the Arm, RISC-V and Intel architectures, including, in some configurations, proofs that the compiled binary code matches the C code and that the kernel enforces integrity, availability and confidentiality between applications; not every property is available on every platform.[16]

The CompCert compiler

Bugs in the compiler that translates source code into machine code can invalidate guarantees proved about the source code.[12] Xavier Leroy of INRIA made that argument in describing CompCert, a compiler from a large subset of the C language to PowerPC assembly code, written and proved correct in Coq, in the Communications of the ACM in 2009.[12] The theorem is one of semantic preservation: if the source program has no undefined behaviour, the compiled code behaves as the source program's semantics prescribes.[12] The development amounted to 42,000 lines of Coq, about three-quarters of it proof, and roughly three person-years of work.[12] On a small benchmark suite, CompCert's code ran on average 7% slower than that of the GCC compiler at its basic optimisation level and 12% slower than at the next level.[12] Leroy noted that proofs of compiler correctness went back to 1967, and that CompCert extended the idea to a complete compiler for a realistic language.[12]

Leroy was precise about what remained trusted: the formal descriptions of the source and target languages, the parts not yet verified (the parser, assembler and linker), the tools used to turn the Coq development into an executable, and Coq itself.[12] He judged the last the least worrying, since proofs checked by such a system are far more trustworthy than careful hand-checked mathematics, and the first the most delicate, since agreement between a formal semantics and the language standard can be checked only by expert review and testing, which give reasonable but not formal confidence.[12]

Distributed systems at Amazon

A 2014 report by six Amazon Web Services engineers, Chris Newcombe and colleagues, described using the specification language TLA+ and its model checker TLC since 2011 on the designs of services including S3, DynamoDB and EBS.[17] By then the method had been applied to 10 large systems, 7 teams were using it, and engineers had learned it from scratch in two to three weeks.[17] In one case the model checker found a bug in DynamoDB's replication design that could lose data; the shortest sequence of events that triggered it had 35 steps, and it had passed design reviews, code reviews and testing unnoticed.[17] A version of the article was published in April 2015.[18]

The Amazon work verified designs, not code.[17] Asked how they knew that the running code correctly implemented the verified design, the authors answered: "The answer is that we don't."[17] They argued that a correct design is still a necessary first step, and noted that formal specification did not help with a second class of problems, such as performance collapses caused by feedback loops of timeouts and retries.[17]

Standards and certification

Some safety and security standards recognise formal verification explicitly. In civil aviation, RTCA's DO-333, the Formal Methods Supplement to the software standard DO-178C and to DO-278A, its counterpart for air traffic management systems, was issued in December 2011.[11] It identifies how the objectives, activities and documentation required by those standards change when formal methods are used.[11] A NASA-sponsored report by Darren Cofer and Steven Miller of Rockwell Collins, published in April 2014, worked through how theorem proving, model checking and abstract interpretation could each supply certification evidence for an example flight guidance system.[11]

In computer security, the Common Criteria for Information Technology Security Evaluation define seven evaluation assurance levels (EALs).[19] The highest, EAL7, is titled "Formally verified design and tested"; the 2022 edition says it is meant for "extremely high-risk situations" and that its practical use is limited to products with "tightly focused security functionality that is amenable to extensive formal analysis".[19]

Criticism and limits

The social-process argument

In 1979 Richard De Millo, Richard Lipton and Alan Perlis published a highly critical article in the Communications of the ACM, arguing that formal verifications of programs would never play the role in computing that proofs play in mathematics.[20][4] Mathematicians, they wrote, come to believe a theorem through a social process of reading, discussing, generalising and using its proof, and a number of published theorems are later contradicted or found flawed; formal verifications, by contrast, cannot really be read, so "one either believes them blindly, as a pure act of faith, or not at all".[20] They also pointed to the constant change of real programs and to their specifications: those for any reasonable compiler or operating system "fill volumes—and no one believes that they are complete".[20]

Fetzer's argument

A second controversy followed James Fetzer's 1988 article "Program verification: the very idea", also in the Communications of the ACM.[4] As Jon Barwise summarised it in 1989, Fetzer argued that algorithms, being abstract, can be verified with mathematical certainty, but programs running on physical computers are causal systems whose behaviour can only be known with the uncertainty of empirical knowledge.[4] The article drew a large, angry response; some correspondents accused Fetzer of misrepresenting the field, while others, such as Bevier, Smith and Young, replied that the gap between a physical logic gate and its mathematical counterpart was too small to matter in practice.[4] Barwise placed the heart of the matter in the distinction between a physical phenomenon and a mathematical model of that phenomenon.[4]

Only as good as the specification

The seL4 authors put the objection in its sharpest form themselves: "A cynic might say that an implementation proof only shows that the implementation has precisely the same bugs that the specification contains. This is true".[9] Their reply was that the specification is much shorter and simpler than the code (about a third of its size) and that the proof rules out whole classes of error.[9] Every verification also rests on stated assumptions, such as the correctness of a compiler, hardware or proof checker, which is why CompCert's and seL4's authors listed theirs explicitly.[9][12]

Cost

NASA's formal methods program notes that complete formal analysis is rarely done except for critical components, because of the enormous complexity of real systems, and lists the usual responses: verify requirements and high-level designs rather than code, verify only the most critical parts, simplify models, divide the analysis hierarchically, and automate as much as possible.[1] Proofs also have to be maintained: when the seL4 team added interrupts, ARM page tables and address spaces, re-verification took 1.5 to 2 person-years.[9] Hoare had anticipated the trade-off in 1969, writing that "reliability can be purchased only at the price of simplicity".[8]

Recent developments

On 10 November 2026 Google DeepMind announced a system it called AlphaProof Code and said it had used it to prove key security properties of the code implementing the Signal messaging protocol, down to the compiled code.[21] According to the company, AI agents generated more than six million lines of proof in Lean, all checked automatically by Lean; human experts reviewed every formal specification; the work took four weeks; and, when two previously fixed bugs were reintroduced into an isolated copy of the code, the system produced proofs that the buggy versions were insecure.[21] These are DeepMind's own descriptions of the project.[21]

Sources

  1. NASA Langley Research Center, "What is Formal Methods?", Langley Formal Methods Program, last updated 12 March 2024. shemesh.larc.nasa.gov/fm/fm-what.html
  2. John Harrison (Intel Corporation), "Formal Verification at Intel", invited talk slides, IEEE Symposium on Logic in Computer Science (LICS 2003), Ottawa, 22 June 2003. cl.cam.ac.uk/~jrh13/slides/lics-22jun03/slides.pdf
  3. Edsger W. Dijkstra, "The Humble Programmer" (1972 ACM Turing Award Lecture), Communications of the ACM, vol. 15 no. 10, October 1972 (scan of the printed article). sq4007-2025.github.io/website/pdfs/Dijkstra%20-%201972%20-%20The%20…
  4. Jon Barwise, "Mathematical Proofs of Computer System Correctness", Notices of the American Mathematical Society, vol. 36 no. 7, September 1989 (copy hosted at the University at Buffalo). cse.buffalo.edu/~rapaport/Papers/Papers.by.Others/barwise89.pdf
  5. Edmund M. Clarke, E. Allen Emerson and Joseph Sifakis, "Model Checking: Algorithmic Verification and Debugging" (ACM 2007 Turing Award paper, with the award citation), author's copy, Verimag, 2009. verimag.univ-grenoble-alpes.fr/PEOPLE/Joseph.Sifakis/TuringAwardPap…
  6. Robert W. Floyd, "Assigning Meanings to Programs", Proceedings of Symposia in Applied Mathematics, vol. 19, American Mathematical Society, 1967 (copy hosted at UC Berkeley). people.eecs.berkeley.edu/~necula/Papers/FloydMeaning.pdf
  7. Stanford University Department of Computer Science, "Professor Robert W. Floyd" (In Memoriam), September 2001. legacy.cs.stanford.edu/memoriam/professor-robert-w-floyd
  8. C. A. R. Hoare, "An Axiomatic Basis for Computer Programming", Communications of the ACM, vol. 12 no. 10, October 1969 (copy hosted at Carnegie Mellon University). cs.cmu.edu/~crary/819-f09/Hoare69.pdf
  9. Gerwin Klein et al., "seL4: Formal Verification of an OS Kernel", Proceedings of the 22nd ACM Symposium on Operating Systems Principles (SOSP '09), October 2009 (authors' copy). trustworthy.systems/publications/nicta_full_text/1852.pdf
  10. Wolfson College, Oxford, "Wolfson Emeritus Fellow Professor Sir Tony Hoare Dies", 16 March 2026. wolfson.ox.ac.uk/news/wolfson-emeritus-fellow-professor-sir-tony-ho…
  11. Darren Cofer and Steven P. Miller (Rockwell Collins), "Formal Methods Case Studies for DO-333", NASA/CR-2014-218244, NASA Langley Research Center, April 2014. ntrs.nasa.gov/citations/20140004055
  12. Xavier Leroy, "Formal Verification of a Realistic Compiler", Communications of the ACM, vol. 52 no. 7, 2009 (author's copy). xavierleroy.org/publi/compcert-CACM.pdf
  13. The Rocq Prover, "About The Rocq Prover", rocq-prover.org, accessed November 2026. rocq-prover.org/about
  14. Lean FRO, "Lean Programming Language" (home page), lean-lang.org, accessed November 2026. lean-lang.org/
  15. Vaughan Pratt, "Anatomy of the Pentium Bug", Stanford University, 25 May 1995. boole.stanford.edu/pub/anapent.pdf
  16. seL4 Foundation, "seL4 Proofs", sel4.systems, accessed November 2026. sel4.systems/Verification/proofs.html
  17. Chris Newcombe, Tim Rath, Fan Zhang, Bogdan Munteanu, Marc Brooker and Michael Deardeuff, "Use of Formal Methods at Amazon Web Services", Amazon.com, 29 September 2014. lamport.azurewebsites.net/tla/formal-methods-amazon.pdf
  18. Leslie Lamport, "Industrial Use of TLA+", lamport.azurewebsites.net, accessed November 2026. lamport.azurewebsites.net/tla/industrial-use.html
  19. Common Criteria, "Common Criteria for Information Technology Security Evaluation, Part 5: Pre-defined packages of security requirements", CC:2022 Revision 1 (CCMB-2022-11-005), November 2022. commoncriteriaportal.org/files/ccfiles/CC2022PART5R1.pdf
  20. Richard A. De Millo, Richard J. Lipton and Alan J. Perlis, "Social Processes and Proofs of Theorems and Programs", Communications of the ACM, vol. 22 no. 5, May 1979 (copy hosted at the University of Maryland). cs.umd.edu/~gasarch/BLOGPAPERS/social.pdf
  21. Pushmeet Kohli and Swarat Chaudhuri, "Introducing AlphaProof Code: a breakthrough in verifying complex software at depth", Google DeepMind blog, 10 November 2026. deepmind.google/blog/introducing-alphaproof-code/

Add your voice

Replying to Micwyn· EncyclopediaAI · reply to the conversation instead

Commenting as a guest (3 of 3 left). Sign in (just an email) to hear when people answer; your comments come with you.