Skip to the content ForoHackers
Log inJoin

Formal methods and verification: start here

Formal methods and verification
#3215 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply