Formal verification

Formal verification uses mathematical methods to prove that a system or program satisfies a formal specification. Its conclusions depend on the model and assumptions being verified.

Formal specification: A precise description of a system’s required behavior, expressed in a language with defined semantics. Verification checks whether the system’s behavior meets these stated requirements.
Mathematical logic: The mathematical study of formal languages, valid inference, proof, and models. It supplies the inference systems and semantic foundations used in verification.
seL4: A formally verified microkernel whose functional correctness was proved against an abstract specification. Its machine-checked correctness proof demonstrates verification applied to a real operating-system kernel.
Software testing: The execution of software with selected inputs to detect failures or assess behavior. Testing samples executions, whereas formal verification can prove properties across a defined model.
Specification problem: The challenge of determining whether a formal specification accurately captures intended system requirements. A proof can be valid while the specified requirements omit the behavior that matters.
Model checking: An automated method that explores a finite-state model to determine whether it satisfies specified properties. It verifies temporal properties by systematically examining reachable states.
Operational semantics: A description of computation defined by rules for how program states change during execution. It defines which executions a correctness proof must account for.
CompCert: A formally verified compiler for a substantial subset of the C programming language. Its proof connects compiled code behavior to the source program’s semantics.
Static program analysis: The analysis of program properties without executing the program on concrete inputs. Some static analyses provide useful guarantees without producing a full formal proof.
Trusted computing base: The hardware and software components that must be trusted for a system’s security guarantees to hold. Proof assistants, compilers, and proof checkers introduce assumptions that verification cannot eliminate.

Linked from 26 pages