Formal methods use mathematics to specify what a system must do and to prove, or exhaustively check, that it does. Testing samples behaviour; verification covers all of it within a model. The cost is effort and training, so these methods are used where failure is expensive: protocols, kernels, compilers, hardware, safety systems.
Key concepts
- Specification: a precise statement of the required properties, written in logic or a modelling language.
- Model checking: automatically exploring every reachable state of a finite model against a property.
- Theorem proving: building machine-checked proofs, by hand or with automation, in a proof assistant.
- Safety and liveness: nothing bad ever happens, and something good eventually does.
- Abstraction and refinement: reasoning on a simple model, then showing the real design respects it.
Vocabulary
- Invariant: a property that holds in every reachable state, or at every loop iteration.
- Precondition and postcondition: what must hold before a function runs, and what it guarantees after.
- SAT and SMT solvers: tools that decide logical formulas, used inside many verifiers.
- State explosion: the number of states growing too fast to enumerate.
What to study, in order
- Propositional and first-order logic, and proof by induction.
- Write a small specification and check it with a model checker such as TLA+ or Alloy.
- Annotate a small program with contracts and verify it with an automatic tool.
- Prove a simple property of a data structure in a proof assistant.
- Study how a verified component, such as a compiler or a kernel, is specified and what is left unproved.