AdvancedTopic 104 of 104Software & Computing
Formal verification
Mathematically proves that software or hardware satisfies a specification.
In depth
Formal verification proves that software or hardware satisfies a mathematical specification, using model checking, theorem provers (Coq, Isabelle, Lean), SMT solvers and verified compilers. Used for safety-critical and security-critical code such as seL4 and CompCert. Costly but eliminates whole classes of bugs.
Key points
- Specifications and invariants
- Soundness
- Hoare logic
ExampleThe seL4 microkernel has a machine-checked proof of correctness.
What is Formal verification?
Mathematically proves that software or hardware satisfies a specification.
Why is it important to understand formal verification?
Formal verification proves properties of software or hardware mathematically, which gives strong assurance where failure is very costly.
What does formal verification provide that testing does not?
It considers all possible inputs and states within the model, while testing only checks the cases you run.
What are the limits of formal verification?
It proves the model matches the specification, so errors in the specification or assumptions outside the model can still cause failures.
How is Formal verification used in practice?
Typical applications include proving that a flight control function never divides by zero, verifying that a cryptographic protocol meets its security goals and checking the logic of a railway interlocking against its specification.
What should I learn before Formal verification?
Study "Infrastructure as code" first (topic 103 of 104 in Software & Computing). It covers the groundwork this topic builds on.
What are the key points of Formal verification?
Specifications and invariants. Soundness. Hoare logic.
Can you give an example of Formal verification?
The seL4 microkernel has a machine-checked proof of correctness.
What comes after Formal verification?
This is the final topic in Software & Computing.
How difficult is Formal verification?
It is classed as Advanced in Software & Computing (topic 104 of 104). It is an advanced topic. It assumes you are comfortable with the intermediate topics in Software & Computing.