Saltar al contenido ForoHackers

Formal methods and verification: start here

Métodos formales y verificación
#709 · Ophuscado · · Denunciar

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

  1. Propositional and first-order logic, and proof by induction.
  2. Write a small specification and check it with a model checker such as TLA+ or Alloy.
  3. Annotate a small program with contracts and verify it with an automatic tool.
  4. Prove a simple property of a data structure in a proof assistant.
  5. Study how a verified component, such as a compiler or a kernel, is specified and what is left unproved.

Related tags

#logic #type-theory #static-analysis #hardware-verification

Inicia sesión o únete para responder.