Formal Methods

Formal methods are the branch of software engineering that uses mathematical reasoning to establish what a program does.

12 frameworks, from 1967 to today · Software Engineering · Computer Science

still a working view ended · each leads to its entry below

Overview

Formal methods are the branch of software engineering that uses mathematical reasoning to establish what a program does1. Instead of testing a system on some inputs and hoping the rest behave, a formal method treats a program or a design as a mathematical object and tries to prove a property of it—that it never divides by zero, that two processes never deadlock, that a protocol delivers every message exactly once1. The stakes are highest where failure is unacceptable or invisible: flight control, medical devices, security protocols, chip designs, railway signalling. The field's history is a long argument about whether such reasoning can be made practical, and the gradual, uneven answer that it can—for some systems, at some cost.

Logics for programs, 1940s–1960s

The intellectual root is the idea that a program is a piece of mathematics. Alan Turing had already shown in 1936 that a machine's behaviour could be described formally, but the first logic built specifically for programs came from John McCarthy. In 1963 he proposed using mathematical logic to prove that programs meet their specifications, and his 1967 paper on the "mathematical science of computation" framed programs as recursive functions. Around the same time, Robert Floyd published "Assigning Meanings to Programs" (1967), which introduced assertions: statements about the state of a program placed at points in its text. Floyd showed how to reason from one assertion to the next through each statement, so that a proof about a whole program could be assembled from local steps. This was the seed of axiomatic semantics—giving a program meaning by the logical rules its statements obey2.

Hoare logic and the verification dream, 1969–1970s

The decisive step was C. A. R. Hoare's 1969 paper "An Axiomatic Basis for Computer Programming."23 Hoare introduced what became known as the Hoare triple: {P} S {Q}, read as "if assertion P holds before statement S, then Q holds afterwards." Each kind of statement got a rule—assignment, sequencing, conditionals, loops—so that a program's correctness could be proved by applying rules mechanically. The loop rule required a loop invariant: a property true before and after every iteration, which the programmer must supply1. That requirement revealed the field's central difficulty: proofs need human insight, and the insight is often as hard as writing the program.

The 1970s were the era of ambitious program verification. Projects such as the Stanford Pascal Verifier and the work of Edsger Dijkstra, whose 1976 A Discipline of Programming recast programming as deriving a program from its specification via weakest preconditions (the weakest condition that guarantees a desired outcome), aimed to make verified software routine. They largely did not. Proofs were long, tools were fragile, and the gap between toy programs and real systems was enormous. The lesson, absorbed slowly, was that full functional verification of large programs by hand was impractical—but the ideas were sound and would return in better tools.

Semantics: giving languages a mathematical meaning, 1970s

Parallel to verification, a community asked a more basic question: what does a program mean? Formal semantics of programming languages supplied answers in three main styles. Operational semantics, developed by Gordon Plotkin in the early 1980s (building on earlier work), defines meaning by the steps a machine takes. Denotational semantics, associated with Christopher Strachey and Dana Scott in the late 1960s and 1970s, maps each program to a mathematical function, with Scott's domain theory providing the spaces in which recursive definitions make sense. Axiomatic semantics is the Hoare-style approach4. These gave later tools a rigorous foundation: a compiler or analyser could be reasoned about because the language itself had a definition. Robin Milner's 1970s work on the ML language and its operational semantics, and later his π-calculus, carried this tradition into practice.

Concurrency and temporal logic, 1977–1980s

Sequential programs were hard enough; concurrent ones were worse, because their behaviour depends on interleaving. Two lines of work addressed this. First, temporal and modal logics of programs: Amir Pnueli's 1977 paper "The Temporal Logic of Programs" proposed describing a concurrent system's requirements in temporal logic—logic with operators like "always" and "eventually"—so that properties such as "the system never deadlocks" or "every request is eventually answered" could be written as formulas15. Second, process algebras: Hoare's Communicating Sequential Processes (CSP, 1978) and Robin Milner's Calculus of Communicating Systems (CCS, early 1980s) modelled concurrent systems as collections of processes interacting through channels or handshakes, with algebraic laws for reasoning about them678. These gave concurrency a vocabulary and a calculus; they also set up the question of how to check that a real system satisfied a temporal formula.

Model checking: exhaustive search that worked, 1981–1990s

The answer came from model checking, introduced independently by Edmund Clarke and E. Allen Emerson (1981) and by Jean-Pierre Queille and Joseph Sifakis (1982). The idea: represent a system as a finite state transition graph—every possible state and every allowed move between states—and check a temporal-logic formula against it by exhaustive search1. For finite-state systems this is decidable and can be automated completely; no loop invariants, no human proof. The obstacle was size: the number of states grows exponentially with the number of components. The breakthrough was symbolic model checking, developed by Ken McMillan, Clarke and others in the early 1990s, which represented sets of states with binary decision diagrams and could handle systems with astronomically many states. Model checking became the field's great practical success, especially in hardware, where finite-state descriptions are natural. Intel, IBM and others adopted it for chip verification; the 2007 Turing Award went to Clarke, Emerson and Sifakis for the work1.

Abstract interpretation: reasoning about all inputs at once, 1977

Where model checking enumerates states, abstract interpretation reasons about programs by over-approximating their behaviour1. Introduced by Patrick and Radhia Cousot in 1977, it maps a program's concrete states onto a simpler abstract domain—say, intervals of integers—and computes what must hold in the abstract world. If the abstraction says "this variable is never zero here," that conclusion is sound for every concrete execution. The price is imprecision: the abstraction may report a possible error that cannot actually occur. Abstract interpretation became the basis of static analysers, notably the Astrée tool, which proved the absence of runtime errors in the flight-control software of the Airbus A380—a landmark demonstration that formal analysis could scale to industrial code.

Specification languages and refinement, 1980s–1990s

To prove anything, one needs a precise statement of what is wanted. Formal specification languages supplied it. Z, developed at Oxford in the late 1970s and 1980s, described systems in set theory and first-order logic; VDM, from Cliff Jones and colleagues in the 1970s, used a model-based style with pre- and postconditions. Later, the B method (Jean-Raymond Abrial, 1980s–1990s) and its successor Event-B supported refinement: starting from an abstract specification and stepping down through increasingly concrete designs, each step proved to preserve the abstract behaviour9. This correct-by-construction approach—build the system so that correctness is established as you go, rather than checked at the end—was used on real railway systems, including driverless metro lines in Paris9. The specification languages made the central trade-off explicit: precision costs effort, and the effort must be repaid by the assurance gained.

Interactive theorem proving, 1970s–present

For systems too complex or too infinite for automatic methods, interactive theorem provers let a human and a machine cooperate on a proof10. The lineage runs from Automath (Nicolaas de Bruijn, late 1960s) through the LCF family (Robin Milner, 1970s), which introduced the idea of a small trusted kernel that checks every proof step. Later systems—HOL, Isabelle, Coq, and more recently Lean—grew into large libraries of mathematics and program theory110. Their use in software includes the CompCert project (Xavier Leroy and colleagues, 2000s), a C compiler whose correctness—that it preserves the meaning of the source program—was proved in Coq. CompCert showed that a real, widely used tool could be verified end to end, and it is now used in safety-critical settings.

Lightweight formal methods and runtime verification, 1990s–2000s

The recurring complaint was cost. Lightweight formal methods answered it by applying formal techniques selectively: not proving a whole system correct, but using a model checker on a protocol design, or a type system or static analyser to catch a class of bugs1. The term, promoted by Daniel Jackson and others around the late 1990s, reframed formal methods as tools in a working engineer's kit rather than an all-or-nothing commitment. Jackson's Alloy tool, which searches for counterexamples to a specification within a bounded scope, is a representative example: it does not prove correctness, but it finds flaws cheaply111. Runtime verification, emerging in the early 2000s, took another route: instead of proving properties ahead of time, monitor a running system and check that it obeys a formal specification, raising an alarm when it does not12. This brought formal specifications into deployed systems where full verification was impossible.

The present

Today the field is less a single programme than a family of techniques at different costs and strengths. Model checking is standard in hardware and increasingly in software, aided by bounded variants and by SMT solvers—automated decision procedures for logical formulas over arithmetic, arrays and bit-vectors—that power tools like CBMC and the deductive verifiers descended from Hoare logic. Deductive verification tools such as Why3, Frama-C and Dafny let programmers write specifications and discharge proof obligations, partly automatically and partly with interactive help1. Abstract interpretation underpins commercial static analysers. Interactive provers verify compilers, operating-system kernels and cryptographic libraries1. The open questions are the old ones in sharper form: how to make specifications cheap enough to write, how to scale proofs to the systems industry actually builds, and how to combine the assurance of proof with the flexibility that changing software demands. The history's arc is from the conviction that programs could be proved right to the working knowledge of when and at what cost they can be.

References

  1. Formal methods (introduction, Verification, Automated proof, History, Applications, Interactive theorem proving, Semi-formal methods, Deductive program verification), Wikipedia
  2. Semantics (programming languages) (History), Wikipedia
  3. Hoare logic, Wikipedia
  4. Axiomatic semantics, Wikipedia
  5. Linear temporal logic, Wikipedia
  6. Communicating sequential processes, Wikipedia
  7. Process calculus (History), Wikipedia
  8. Calculus of communicating systems, Wikipedia
  9. B-Method (History, Event-B), Wikipedia
  10. Proof assistant (introduction, History), Wikipedia
  11. Alloy (specification language), Wikipedia
  12. Runtime verification (History and context), Wikipedia

The frameworks of Formal Methods

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1967-Present

    Axiomatic semantics

    What logical rules give a program its meaning?

    Fly to its tower in Nousfarer

  2. 1967-Present

    Semantics

    What does a program mean, mathematically?

    Fly to its tower in Nousfarer

  3. 1970-Present

    Proof assistant

    How can a machine check a human proof?

    Fly to its tower in Nousfarer

  4. 1975-Present

    Formal Specification and Refinement

    How do we state precisely what a system must do?

    Fly to its tower in Nousfarer

  5. 1977-Present

    Abstract Interpretation

    How can we reason about all inputs at once?

    About Abstract Interpretation
    In the late 1970s, formal methods faced a practical impasse. Hoare logic offered rigorous proofs of program correctness, but the manual effort required was prohibitive for all but the smallest programs. Formal specification languages like VDM and Z raised the level of abstraction to system design, but they did not automatically verify that an implementation matched its specification. What was needed was a way to extract useful, guaranteed-correct information about a program's runtime behavior automatically—without executing it and without the full cost of theorem proving. Abstract interpretation, formalized by Patrick Cousot and Radhia Cousot in 1977, provided exactly that: a theory of sound approximation that made static program analysis both principled and practical.
    At its core, abstract interpretation replaces the concrete, infinite set of possible program states with a finite, computable abstraction. The key intellectual move is to define a Galois connection between two worlds: a concrete domain (the actual semantics of the program) and an abstract domain (a simpler, finite representation). A concretization function maps abstract values back to the sets of concrete states they represent, while an abstraction function goes the other way. This pair of functions must form a Galois connection, ensuring that reasoning in the abstract domain is sound with respect to the concrete semantics.
    The curriculum for a first course in abstract interpretation typically proceeds through these clusters:
    1. Foundations: Abstract domains and Galois connections. Students first learn how to define an abstract domain—a lattice of abstract values—and the pair of monotonic functions (abstraction and concretization) that relate it to the concrete domain. The monotonic function property ensures that the ordering in the abstract domain respects the ordering in the concrete domain.
    1. Abstract semantics and soundness. The concrete semantics of a program is given by a collecting semantics—the set of all possible states reachable at each program point. An abstract semantics is defined by replacing each concrete operation with an abstract transformer that operates on abstract values. The central theorem is soundness (over-approximation): the abstract semantics must produce a superset of the concrete reachable states, guaranteeing that no real behavior is missed (though false positives are possible).
    1. Fixpoint semantics and computation. The abstract semantics is defined as the least fixpoint of a system of equations over the abstract domain. Computing this fixpoint directly may not terminate if the abstract domain has infinite ascending chains. Widening operators accelerate convergence by jumping to a safe over-approximation, while narrowing operators refine the result after widening. Chaotic iteration is the standard algorithm for computing the fixpoint efficiently by iterating over program points in an order that respects control flow.
    1. Applications: Program invariants and static analysis. The output of abstract interpretation is a set of program invariants—properties that hold at every program point for all executions. These invariants are the basis for static analysis tools that detect bugs (e.g., division by zero, buffer overflows) or enable compiler optimizations (e.g., constant propagation, dead code elimination).
    Abstract interpretation emerged directly from the limitations of earlier formal methods. Patrick Cousot and Radhia Cousot, both French computer scientists, introduced the framework in their 1977 paper "Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints." Their key insight was to unify a scattered set of ad-hoc program analysis techniques (like data-flow analysis and type inference) under a single mathematical theory based on lattice theory and fixpoint semantics. The Cousots showed that many existing analyses could be seen as instances of abstract interpretation with different abstract domains, and that the theory provided a systematic way to design new analyses and prove them correct.
    The framework coexisted with and complemented its peers. While Hoare logic (1969) and axiomatic semantics focused on deductive verification of code, abstract interpretation automated the discovery of invariants. Formal specification languages (VDM, Z, B Method) targeted design-time correctness, but abstract interpretation could analyze the final implementation. Model checking (emerging around 1981) explored state spaces exhaustively but suffered from state explosion; abstract interpretation provided a way to soundly approximate those state spaces. Theorem proving (HOL, Isabelle, Coq) offered full expressiveness but required human guidance; abstract interpretation was fully automatic but traded completeness for automation.
    Abstract interpretation's legacy in formal methods is profound. It provided the first rigorous foundation for static analysis, transforming it from an ad-hoc collection of compiler tricks into a principled discipline. Today, virtually all production static analyzers—from simple type checkers to sophisticated industrial tools like Astrée (used to verify avionics software) and Polyspace—are built on abstract interpretation. The framework also influenced later developments: lightweight formal methods like Alloy and TLA+ adopted similar approximation strategies, and SAT/SMT-based verification (1990s onward) automated the search for counterexamples in a way that abstract interpretation had automated the search for invariants.
    A common misconception is that abstract interpretation is synonymous with static analysis. In fact, it is a specific theory of sound approximation; many static analysis tools are unsound (they may miss bugs) or use ad-hoc heuristics. Another pitfall is to confuse abstract interpretation with model checking: model checking explores all concrete states of a finite model, while abstract interpretation works with abstract states and is designed for infinite-state systems. The two are complementary: abstract interpretation can provide the invariants that model checking uses to prune its search, and model checking can verify properties that abstract interpretation cannot prove.
    The 16 concepts its tower teaches
    • Abstract domain
    • Abstract interpretation
    • Abstract semantics
    • Abstract transformer
    • Chaotic iteration
    • Collecting semantics
    • Concretization function
    • Fixpoint semantics
    • Galois connection
    • Least fixpoint
    • Monotonic function
    • Narrowing
    • Program invariant
    • Soundness (over-approximation)
    • Static analysis
    • Widening

    Fly to its tower in Nousfarer

  6. 1977-Present

    Temporal and Modal Logics of Programs

    How do we write down what a concurrent system must always do?

    Fly to its tower in Nousfarer

  7. 1978-Present

    Process calculus

    What laws govern interacting processes?

    Fly to its tower in Nousfarer

  8. 1981-Present

    Model Checking

    Can we check every possible state automatically?

    About Model Checking
    Model checking emerged in the early 1980s to address a pressing problem in formal methods: how to verify the correctness of finite-state systems automatically, without the manual ingenuity required by deductive verification. Where earlier frameworks like Hoare logic demanded that a human supply loop invariants and proof steps, model checking offered an algorithmic alternative. Given a finite-state model of a system and a specification expressed in temporal logic, a model checker can automatically determine whether the specification holds by exhaustively exploring all reachable states of the model. Crucially, when a property fails, the model checker produces a counterexample trace—a concrete sequence of states that leads to the violation—giving engineers a specific bug to fix rather than an abstract proof obligation. This combination of automation and actionable feedback made model checking one of the most practically successful formal methods, especially in hardware verification.
    Core curriculum. A first course in model checking typically builds from the system representation to the specification language, then to the core algorithms and their optimizations. The following concepts form the teaching spine:
    1. Finite-state model — the system under verification is abstracted as a directed graph where nodes represent states and edges represent transitions. Each state is labeled with atomic propositions that hold at that point.
    1. Temporal logic specification — desired system behavior is expressed in a logic that can reason about the ordering of events over time. The two main dialects are Computation Tree Logic (CTL) and Linear Temporal Logic (LTL). CTL quantifies over paths (e.g., "along all paths, eventually pp holds"), while LTL reasons about individual execution traces (e.g., "globally, if pp then eventually qq").
    1. Safety and liveness properties — specifications are classified into two broad categories: safety properties assert that "nothing bad ever happens" (e.g., the elevator door is never open while the cabin moves), and liveness properties assert that "something good eventually happens" (e.g., every floor request is eventually serviced).
    1. State space exploration — the fundamental algorithm: starting from the initial state, the model checker systematically visits all reachable states, checking the temporal logic specification against each state. For finite-state systems, this reduces to a graph search.
    1. **Büχ\chi automaton** — for LTL model checking, the specification is translated into a Büchi automaton, a finite automaton that accepts infinite words. The model checking problem then reduces to checking whether the product of the system model and the automaton has an empty language (i.e., no accepting run ∃\exists).
    1. Binary Decision Diagrams (BDDs) — a compact, canonical representation of Boolean functions. BDDs enable symbolic model checking, which manipulates sets of states implicitly rather than enumerating them individually, dramatically increasing the size of systems that can be verified.
    1. Partial order reduction — a technique that exploits the independence of concurrent events to reduce the number of interleavings that must be explored, mitigating state explosion in concurrent systems.
    1. Counterexample-guided abstraction refinement (CEGAR) — an iterative method that starts with an abstract model, checks it, and if a counterexample is found, refines the model to eliminate spurious counterexamples until either a real bug is found or the property is proved.
    1. Explicit-state model checking — the original approach, where each state is represented explicitly and stored in a hash table. This contrasts with symbolic model checking and is still used in tools like SPIN for protocol verification.
    1. Model checking tools (SPIN, NuSMV) — SPIN, developed at Bell Labs, specializes in LTL verification of asynchronous software models, especially communication protocols. NuSMV, derived from the original SMV (Symbolic Model Verifier), supports both CTL and LTL and is widely used for hardware verification.
    1. Property Specification Language (PSL) — an industrial standard for expressing temporal logic assertions in hardware design, bridging the gap between formal verification and engineering practice.
    Intellectual history. The intellectual roots of model checking lie in two earlier developments. First, Amir Pnueli's 1977 proposal to use temporal logic for specifying program properties provided the specification language that model checking would later adopt. Pnueli received the 1996 Turing Award for this work. Second, the tradition of automated theorem proving and deductive verification (Hoare logic, 1969) established the ideal of mathematical correctness but revealed the impracticality of manual proof for large systems.
    The framework itself was founded independently by two groups in the early 1980s. Edmund M. Clarke and E. Allen Emerson published their seminal paper "Design and Synthesis of Synchronization Skeletons Using Branching Time Temporal Logic" in 1981, introducing CTL model checking for finite-state systems. At roughly the same time, Jean-Pierre Queille and Joseph Sifakis developed a similar approach, published in 1982. These works defined the core problem: given a finite-state structure MM and a temporal logic formula pp, decide whether M⊨pM \models p. For their foundational contributions, Clarke, Emerson, and Sifakis shared the 2007 Turing Award.
    Early model checking used explicit-state enumeration, which quickly ran into the state explosion problem: the number of states grows exponentially with the number of system components. The breakthrough came in the late 1980s when Ken McMillan and others, building on Randal Bryant's work on Binary Decision Diagrams, developed symbolic model checking. By representing sets of states implicitly as BDDs, symbolic model checking could verify circuits with millions of states, making the technique practical for industrial hardware verification. The SMV tool, developed by McMillan at Carnegie Mellon, became the canonical implementation.
    In the 1990s, model checking expanded to software. Gerard Holzmann's SPIN tool, first released in 1991, applied explicit-state model checking to communication protocols, using ∂\partial order reduction to handle concurrency. The CEGAR technique, formalized by Edmund Clarke and others in the early 2000s, allowed model checking to scale to larger software systems by iteratively refining abstractions. These developments allowed model checking to coexist with peer frameworks: abstract interpretation provides static analysis without state enumeration, while lightweight formal methods like Alloy and TLA+ use bounded model checking or explicit-state exploration for software specifications. Model checking did not replace these frameworks but supplemented them, offering a distinct point in the design space: full automation and counterexample generation, at the cost of requiring finite-state models.
    Key insights: Model checking transformed verification from a manual proof activity into an automated debugging tool, introduced the crucial concept of counterexample-guided debugging, and demonstrated that exhaustive state exploration is feasible for many real-world systems when combined with symbolic representations and abstraction.
    Common pitfalls: Model checking is not testing—it exhaustively checks all behaviors of a finite-state model, not a sample. It is also not a silver bullet: state explosion remains a challenge, and infinite-state systems require abstraction or restriction to finite domains.
    The 16 concepts its tower teaches
    • Binary Decision Diagrams (BDDs)
    • Büchi automaton
    • Computation Tree Logic (CTL)
    • Counterexample trace
    • Counterexample-guided abstraction refinement (CEGAR)
    • Explicit-state model checking
    • Finite-state model
    • Linear Temporal Logic (LTL)
    • Model checking tools (SPIN, NuSMV)
    • Partial order reduction
    • Property Specification Language (PSL)
    • Safety and liveness properties
    • State explosion problem
    • State space exploration
    • Symbolic model checking
    • Temporal logic specification

    Fly to its tower in Nousfarer

  9. 1996-Present

    Lightweight Formal Methods

    How little formalism buys useful assurance?

    Fly to its tower in Nousfarer

  10. 2000-Present

    Deductive Software Verification Tools

    Can a tool prove a program meets its contract?

    Fly to its tower in Nousfarer

  11. 2000-Present

    SMT-Based Deductive Verification

    Can solvers discharge the routine proof steps?

    Fly to its tower in Nousfarer

  12. 2001-Present

    Runtime Verification

    Can we check a running system against its rules?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Axiomatic semanticsSemanticsProof assistantFormal Specification and RefinementAbstract InterpretationTemporal and Modal Logics of ProgramsProcess calculusModel CheckingLightweight Formal MethodsDeductive Software Verification ToolsSMT-Based Deductive VerificationRuntime Verification

Beyond the field

Where Formal Methods's ideas came from in other fields, and what they led to there: the strongest 12 of 33 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Formal Methods is a planet in Nousfarer

Its city has a tower for each of these 12 frameworks. Land, walk in, and climb one concept at a time.

Land on Formal Methods

Related fields

Fields its ideas are linked to

More in Software Engineering

See where Formal Methods sits on the Map of Human Knowledge