{ "id": "ep1wdz8k37", "slug": "formal-specification", "title": "Formal specification", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" } ], "geo": [ { "id": "geo.nongeo.t1800.technology.computing", "label": "Non-geographic · 1800 to 1945: Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.technology.computing", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1800", "label": "Non-geographic · 1800 to 1945", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800" }, { "id": "geo.nongeo.t1800.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.technology" }, { "id": "geo.nongeo.t1800.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.technology.computing" } ] }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Non-geographic · 1946 to 2000: Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" } ] } ], "excerpt": "A formal specification is a description of what a system should do, written in a language with mathematically defined syntax and semantics, so correctness can be checked by proof.", "snippet": "A formal specification is a description of what a system should do, written in a language with mathematically defined syntax and semantics, so correctness can be checked by proof.", "node": "technology.computing.ai", "markdown": "# Formal specification\n\nA formal specification is a description of what a system should do, written in a language with mathematically defined syntax, semantics, and proof theory, so that claims about the description can be checked by proof rather than by intuition.[1](https://webperso.info.ucl.ac.be/~avl/files/FormalSpec-avl.pdf) A method counts as formal when its techniques and tools can be explained in mathematics.[2](https://havelund.com/Publications/fm-50-2022.pdf) The artifact produced is a mathematical model of behavior, often serving as a contract between a module's user and its implementer, each of whom can verify correctness without knowing the other's design.[3](https://lamport.org/pubs/spec.pdf) Formal specification underpins the activities called formal methods: specification analysis and proof, transformational development, and program verification, all grounded in discrete mathematics such as set theory, logic, and algebra.[4](https://ifs.host.cs.st-andrews.ac.uk/Books/SE9/WebChapters/PDF/Ch_27_Formal_spec.pdf)\n\n| Key fact | Detail |\n|---|---|\n| What makes a specification formal | A language with rules for grammatical well-formedness (syntax), interpretation (semantics), and inference (proof theory) [1](https://webperso.info.ucl.ac.be/~avl/files/FormalSpec-avl.pdf) |\n| Canonical system specification form | TLA+: Init ∧ □[Next]v ∧ L, with initial predicate, next-state disjunction of actions, and fairness conditions [5](https://members.loria.fr/Stephan.Merz/talks/argentina2005/handout.pdf) |\n| Main styles | Model-oriented (concrete data types) vs algebraic (abstract carrier sets with axioms); sequential vs concurrent system languages [2](https://havelund.com/Publications/fm-50-2022.pdf) • [6](https://dl.acm.org/doi/10.1145/242223.242257) |\n| seL4 kernel verification | 200,000 lines of Isabelle proof, about 20 person-years, 144 defects found by verification [7](https://dl.acm.org/doi/10.1145/1629575.1629596) |\n| AWS DynamoDB | TLA+ specification written in a couple of weeks; distributed TLC on 10 EC2 instances found a data-loss bug [8](https://fi.upm.es/docs/estudios/2461_aws-formal-methods.pdf) |\n| Paris metro line 14 | About 100,000 lines of B specification, 28,000 lemmas proved automatically, no errors found by conventional testing [1](https://webperso.info.ucl.ac.be/~avl/files/FormalSpec-avl.pdf) |\n| LLM-generated specifications | Up to 26.6% syntactic but only 8.6% semantic correctness across 30 evaluated models [9](https://arxiv.org/abs/2606.05792) |\n\n## How it works\n\nMost specification languages rest on a small mathematical core. TLA+ is based on untyped ZF set theory, first-order logic, and the Temporal Logic of Actions; a typical specification has the form \\( Init \\wedge \\Box[Next]_{v} \\wedge L \\), where \\( Init \\) describes initial states, \\( Next \\) is a disjunction of actions, and \\( L \\) is a conjunction of fairness conditions.[10](https://lamport.azurewebsites.net/pubs/spec-and-verifying.pdf) An action formula uses unprimed variables for the first state of a step and primed variables for its second.[10](https://lamport.azurewebsites.net/pubs/spec-and-verifying.pdf)\n\nProperties divide into safety properties, what a program is allowed to do, and liveness properties, what it must eventually do;[3](https://lamport.org/pubs/spec.pdf) liveness received a formal definition from Bowen Alpern and [Fred B. Schneider](https://www.edgepedia.org/fred-b-schneider) in 1985.[11](https://doi.org/10.1016/0020-0190%2885%2990056-0) In TLA, implementation, satisfaction, and refinement all mean the same thing, logical implication: \\( S_{1} \\) implements \\( S_{2} \\) iff \\( S_{1} \\Rightarrow S_{2} \\) is a valid formula.[12](https://lamport.azurewebsites.net/pubs/spec-book-chap.pdf)\n\n## How it is done\n\nThe specifier models the state and the next-state relation, states invariants, and proves them inductively. To show that a predicate \\( I \\) is an invariant of a specification \\( S \\), one proves \\( S \\Rightarrow \\Box I \\) by finding an invariant \\( Inv \\) of \\( Next \\) satisfying \\( Init \\Rightarrow Inv \\), \\( Inv \\wedge Next \\Rightarrow Inv' \\), and \\( Inv \\Rightarrow I \\).[10](https://lamport.azurewebsites.net/pubs/spec-and-verifying.pdf) The basic proof rule derives \\( I \\wedge \\Box[Next]_{v} \\Rightarrow \\Box I \\) from \\( I \\wedge Next \\Rightarrow I' \\) and \\( I \\wedge v' = v \\); invariants usually must be strengthened for the inductive proof to go through.[5](https://members.loria.fr/Stephan.Merz/talks/argentina2005/handout.pdf)\n\nA model checker such as TLC explores all reachable states for safety properties, checking invariants and deadlock, and prints a guaranteed minimal-length error trace on violation.[10](https://lamport.azurewebsites.net/pubs/spec-and-verifying.pdf) Refinement then moves the specification toward code in two stages, a high-level document followed by a low-level one in a guarded command language, separating data refinement from operation refinement, with proof obligations such as \\( pre[A] \\subseteq pre[B] \\).[13](https://www.cs.ox.ac.uk/files/3414/PRG101.pdf)\n\n## Origin\n\nFormal specification grew out of work on defining programming languages. The Vienna Definition Language (VDL) described language semantics with a recursive abstract interpreter that takes a program and a starting state and computes a final state; the Vienna Development Method (VDM) evolved from this work and covered a far wider area than language semantics.[14](https://www.jucs.org/jucs_7_8/the_transition_from_VDL/Jones_C_B.pdf) A later survey credits VDM to Bjørner and Jones's 1978 meta-language work as one of the first formal methods.[15](https://ar5iv.labs.arxiv.org/html/1911.02564) The parts of VDM aimed at formal program development first appeared in book form in Cliff B. Jones's 1980 Software Development: A Rigorous Approach.[14](https://www.jucs.org/jucs_7_8/the_transition_from_VDL/Jones_C_B.pdf) Z is structured around set types, relations, functions, and schemas.[16](https://courses.cs.washington.edu/courses/cse503/00sp/zrm.pdf) Abrial's early Z paper set its principles: a strict formalism inherited from mathematical practice, set theory as a sound basis for formalization, and strong structuring of the formal text.[17](https://se.inf.ethz.ch/~meyer/publications/languages/Z_original.pdf) [TLA+](https://www.edgepedia.org/tla) is credited to [Leslie Lamport](https://www.edgepedia.org/leslie-lamport)'s 2002 book Specifying Systems;[18](https://link.springer.com/chapter/10.1007/978-3-319-33600-8_13) Alloy descends from Z, addressing its lack of automatic tool support;[19](https://people.csail.mit.edu/dnj/publications/alloy-journal.pdf) Event-B is credited to Abrial's 2010 Modeling in Event-B.[20](https://doi.org/10.1017/cbo9781139195881) Temporal-logic model checking was reported by E. M. Clarke, E. A. Emerson, and A. P. Sistla in 1986,[21](https://doi.org/10.1145/5397.5399) and the SPIN model checker by G. J. Holzmann in 1997.[22](https://doi.org/10.1109/32.588521)\n\n## Variants\n\nSpecification languages differ along several axes. Model-oriented specifications use concrete data types such as numbers, sets, lists, and maps, with operations defined as functions over them; algebraic specifications use abstract carrier sets with axioms over operation signatures.[2](https://havelund.com/Publications/fm-50-2022.pdf) Languages for sequential systems, such as Z, VDM, and Larch, use sets, relations, functions, and pre/postconditions, while CSP, CCS, Statecharts, temporal logic, and I/O automata target concurrent behavior.[6](https://dl.acm.org/doi/10.1145/242223.242257) Larch, by John V. Guttag, James J. Horning, and colleagues, appeared in 1993.[23](https://doi.org/10.1007/978-1-4612-2704-5) Z specifications are built from schemas over a mathematical toolkit, with operation and data refinement for sequential systems.[16](https://courses.cs.washington.edu/courses/cse503/00sp/zrm.pdf) VDM includes [VDM-SL](https://www.edgepedia.org/vdm-sl) with modules and object-oriented VDM++, and uses a refinement process called reification.[15](https://ar5iv.labs.arxiv.org/html/1911.02564) Event-B models state with sets and functions and state change with events, requiring proofs that refinements preserve invariants, and has been used in industrial transportation, aerospace, and automotive projects.[20](https://doi.org/10.1017/cbo9781139195881) • [15](https://ar5iv.labs.arxiv.org/html/1911.02564) TLA+ is a model-based language for reactive and distributed systems, as opposed to property-oriented axiomatic styles.[5](https://members.loria.fr/Stephan.Merz/talks/argentina2005/handout.pdf)\n\n## Applications\n\nThe most quantified deployment is seL4, a third-generation L4-provenance microkernel of 8,700 lines of C and 600 lines of assembler, for which the SOSP 2009 paper claims the first formal proof of functional correctness of a complete, general-purpose operating-system kernel, from abstract specification down to C implementation, assuming correctness of compiler, assembly code, and hardware.[7](https://dl.acm.org/doi/10.1145/1629575.1629596) The proof is 200,000 lines of Isabelle script and cost about 20 person-years, of which 11 were seL4-specific; verification uncovered 144 defects beyond the 16 found by earlier use and porting.[7](https://dl.acm.org/doi/10.1145/1629575.1629596) • [24](https://www.trustworthy.systems/publications/nicta_full_text/1842.pdf) At Amazon, an engineer learned TLA+ and wrote a detailed DynamoDB specification in a couple of weeks; the distributed TLC model checker, run on a cluster of 10 EC2 instances, found a bug that could lose data under a particular interleaving of failures and recovery.[8](https://fi.upm.es/docs/estudios/2461_aws-formal-methods.pdf) IBM's 1980s CICS work with Oxford University using Z yielded an estimated 9% reduction in total development cost and a Queen's Award for Technological Achievement.[6](https://dl.acm.org/doi/10.1145/242223.242257) TLA+ is used in industry at [Amazon Web Services](https://www.edgepedia.org/amazon-web-services), Microsoft's Cosmos DB, and MongoDB, and formal verification is mandated for the highest [Common Criteria](https://www.edgepedia.org/common-criteria) assurance level, EAL7, though even there only design-level verification is required.[25](https://link.springer.com/chapter/10.1007/978-3-032-32519-8_8) • [26](https://www.trustworthy.systems/publications/nicta_full_text/5396.pdf)\n\nSince 2023, LLM-assisted specification has become an active area. nl2spec interactively translates unstructured natural language to temporal logics with large language models.[27](https://doi.org/10.48550/arxiv.2303.04864) Specula is a push-button agentic system that generates TLA+ models and invariants for system code, checks them with TLC, and validates model-code conformance through trace validation, repairing the model when validation fails.[28](https://arxiv.org/html/2607.25333v1) Measured quality remains low: an evaluation of 30 LLMs across eight families on 205 TLA+ specifications found up to 26.6% syntactic but only 8.6% semantic correctness, with model size not predicting quality.[9](https://arxiv.org/abs/2606.05792)\n\n## Limitations and alternatives\n\nFormal specification does not replace testing, because the abstract machine and the target machine may behave differently; the two are combined by using the specification to generate test cases and check results.[29](https://www.kneuper.de/English/Publications/limits-formal-methods.pdf) Even where a correctness proof is believed to exist, dynamic testing remains important, and a specification enables provably correct test oracles for observed behavior.[30](https://staffwww.dcs.shef.ac.uk/people/A.Simons/research/papers/landscapes.pdf) In general it is undecidable whether a program satisfies a specification; Hoare-logic verification requires identifying loop invariants, which cannot be done automatically,[29](https://www.kneuper.de/English/Publications/limits-formal-methods.pdf) and automated test generation faces the undecidable feasibility problem of whether a chosen path can be executed.[30](https://staffwww.dcs.shef.ac.uk/people/A.Simons/research/papers/landscapes.pdf) Specifications themselves can be wrong: formal methods increase the likelihood of correctness but provide no absolute guarantee, since the specification may be incorrect, the environment description incomplete, or the method misapplied.[29](https://www.kneuper.de/English/Publications/limits-formal-methods.pdf) Adoption barriers include other methods improving quality, time-to-market pressure, poor fit for user interfaces, and limited scalability, with successful projects mostly small, critical kernel systems.[4](https://ifs.host.cs.st-andrews.ac.uk/Books/SE9/WebChapters/PDF/Ch_27_Formal_spec.pdf) Maintenance is costly: a change to less than 5% of the seL4 code base once forced proof rework equivalent to 17% of the entire original proof effort.[26](https://www.trustworthy.systems/publications/nicta_full_text/5396.pdf) [Model checking](https://www.edgepedia.org/model-checking), though completely automatic and able to produce counterexamples for debugging, suffers the state explosion problem; BDD-based symbolic model checking counters it, and checkers routinely handle 100 to 200 state variables, with systems of \\( 10^{120} \\) reachable states checked.[6](https://dl.acm.org/doi/10.1145/242223.242257)\n\n## References\n\n1. [Formal Specification: a Roadmap (Axel van Lamsweerde)](https://webperso.info.ucl.ac.be/~avl/files/FormalSpec-avl.pdf)\n2. [A Half Century of Formal Methods (Bjørner & Havelund, 2022)](https://havelund.com/Publications/fm-50-2022.pdf)\n3. [Specifying (concurrent program modules with temporal assertions)](https://lamport.org/pubs/spec.pdf)\n4. [Chapter 27: Formal Specification (Sommerville, Software Engineering, 9th ed.)](https://ifs.host.cs.st-andrews.ac.uk/Books/SE9/WebChapters/PDF/Ch_27_Formal_spec.pdf)\n5. [Modeling and Developing Systems Using TLA+ (Stephan Merz, course handout)](https://members.loria.fr/Stephan.Merz/talks/argentina2005/handout.pdf)\n6. [Formal Methods: State of the Art and Future Directions (Clarke & Wing, ACM Computing Surveys 28(4), 1996)](https://dl.acm.org/doi/10.1145/242223.242257)\n7. [seL4: Formal Verification of an OS Kernel (SOSP 2009, ACM DL page)](https://dl.acm.org/doi/10.1145/1629575.1629596)\n8. [How AWS uses formal methods (CACM 2015)](https://fi.upm.es/docs/estudios/2461_aws-formal-methods.pdf)\n9. [Can LLMs Write Correct TLA+ Specifications? Evaluating Natural-Language-to-TLA+ Generation](https://arxiv.org/abs/2606.05792)\n10. [Specifying and Verifying Systems With TLA (Lamport, Microsoft Research)](https://lamport.azurewebsites.net/pubs/spec-and-verifying.pdf)\n11. [Defining liveness (Information Processing Letters, 1985)](https://doi.org/10.1016/0020-0190%2885%2990056-0)\n12. [Book chapter on TLA+ (comparison with Z, TLC, validation workflow)](https://lamport.azurewebsites.net/pubs/spec-book-chap.pdf)\n13. [PRG-101: From Z to C, Illustration of a Rigorous Development Method (Oxford PRG)](https://www.cs.ox.ac.uk/files/3414/PRG101.pdf)\n14. [The Transition from VDL to VDM (C. B. Jones)](https://www.jucs.org/jucs_7_8/the_transition_from_VDL/Jones_C_B.pdf)\n15. [The role of formalism in system requirements (full version)](https://ar5iv.labs.arxiv.org/html/1911.02564)\n16. [The Z Notation: A Reference Manual, 2nd edition (J. M. Spivey, 1992)](https://courses.cs.washington.edu/courses/cse503/00sp/zrm.pdf)\n17. [Abrial's original Z specification language paper](https://se.inf.ethz.ch/~meyer/publications/languages/Z_original.pdf)\n18. [How to Select the Suitable Formal Method for an Industrial Application: A Survey (Kossak & Mashkoor, ABZ 2016, LNCS 9675)](https://link.springer.com/chapter/10.1007/978-3-319-33600-8_13)\n19. [Alloy: A Lightweight Object Modelling Notation (Daniel Jackson)](https://people.csail.mit.edu/dnj/publications/alloy-journal.pdf)\n20. [Jean-Raymond Abrial (2010). Modeling in Event-B. Cambridge University Press eBooks.](https://doi.org/10.1017/cbo9781139195881)\n21. [E. M. Clarke, E. A. Emerson, A. P. Sistla (1986). Automatic verification of finite-state concurrent systems using temporal logic specifications. ACM Transactions on Programming Languages and Systems.](https://doi.org/10.1145/5397.5399)\n22. [G.J. Holzmann (1997). The model checker SPIN. IEEE Transactions on Software Engineering.](https://doi.org/10.1109/32.588521)\n23. [John V. Guttag and colleagues (1993). Larch: Languages and Tools for Formal Specification. .](https://doi.org/10.1007/978-1-4612-2704-5)\n24. [Mind the Gap: A Verification Framework for Low-Level C](https://www.trustworthy.systems/publications/nicta_full_text/1842.pdf)\n25. [The TLA+ Model Checker Apalache](https://link.springer.com/chapter/10.1007/978-3-032-32519-8_8)\n26. [Large-Scale Formal Verification in Practice: A Process Perspective](https://www.trustworthy.systems/publications/nicta_full_text/5396.pdf)\n27. [Cosler, Matthias and colleagues (2023). nl2spec: Interactively Translating Unstructured Natural Language to Temporal Logics with Large Language Models. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.2303.04864)\n28. [Specula: Scaling formal specifications for autonomous model checking of system code](https://arxiv.org/html/2607.25333v1)\n29. [Limits of Formal Methods (Kneuper)](https://www.kneuper.de/English/Publications/limits-formal-methods.pdf)\n30. [Using Formal Specifications to Support Testing](https://staffwww.dcs.shef.ac.uk/people/A.Simons/research/papers/landscapes.pdf)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [], "url": "https://www.edgepedia.org/formal-specification", "markdown_url": "https://www.edgepedia.org/formal-specification.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Formal specification\", Edgepedia (EdgeChat), https://www.edgepedia.org/formal-specification. Edgepedia Community License 1.0.", "credit_md": "\"[Formal specification](https://www.edgepedia.org/formal-specification)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/formal-specification](https://www.edgepedia.org/formal-specification). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Formal specification\", Edgepedia (EdgeChat), https://www.edgepedia.org/formal-specification. Edgepedia Community License 1.0.", "speakable": "A formal specification is a description of what a system should do, written in a language with mathematically defined syntax and semantics, so correctness can be checked by proof." }