Saltar al contenido ForoHackers

Formal methods and verification: start here

Métodos formales y verificación
#3215 · · Citar · 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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder