From Wikipedia, the free encyclopedia

"Verifiability" redirects here. For the Wikipedia policy, see Wikipedia:Verifiability.

In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics.

Contents 1 Explanation 2 Usage 3 Approaches to formal verification 4 Validation and Verification 5 Program verification 6 See also 7 External links

Software testing alone cannot prove that a system does not contain any defects. Neither can it prove that it does have a certain property. Only the process of formal verification can prove that a system does not have a certain defect or does have a certain property. It is impossible to prove or test that a system has "no defect" since it is impossible to formally specify what "no defect" means. All that can be done is prove that a system does not have any of the defects that can be thought of, and has all of the properties that together make it functional and useful.

Formal verification can be used for example for systems such as cryptographic protocols, combinational circuits, digital circuits with internal memory, and software expressed as source code.

The verification of these systems is done by providing a formal proof on an abstract mathematical model of the system, the correspondence between the mathematical model and the nature of the system being otherwise known by construction. Examples of mathematical objects often used to model systems are: finite state machines, labelled transition systems, Petri nets, timed automata, hybrid automata, process algebra, formal semantics of programming languages such as operational semantics, denotational semantics, axiomatic semantics and Hoare logic.

There are roughly two approaches to formal verification.

The first approach is model checking, which consists of a systematically exhaustive exploration of the mathematical model (this is possible for finite models, but also for some infinite models where infinite sets of states can be effectively represented). Usually this consists of exploring all states and transitions in the model, by using smart and domain-specific abstraction techniques to consider whole groups of states in a single operation and reduce computing time. Implementation techniques include state space enumeration, symbolic state space enumeration, abstract interpretation, symbolic simulation, abstraction refinement.

The second approach is logical inference. It consists of using a formal version of mathematical reasoning about the system, usually using theorem proving software such as the HOL theorem prover or Isabelle theorem prover. This is usually only partially automated and is driven by the user's understanding of the system to validate.

The properties to be verified are often described in temporal logics, such as linear temporal logic (LTL) or computational tree logic (CTL).

Verification is one aspect of testing a product's fitness for purpose. Validation is the complementary aspect. Often one refers to the overall checking process as V & V.

• Validation: "Are we trying to make the right thing?", i.e., does the product do what the user really requires?
• Verification: "Have we made what we were trying to make?", i.e., does the product conform to the specifications?

The verification process consists of static and dynamic parts. E.g., for a software product one can inspect the source code (static) and run against specific test cases (dynamic). Validation usually can only be done dynamically, i.e., the product is tested by putting it through typical usages and atypical usages ("Can we break it?"). See also Verification and Validation

Program verification is the process of formally proving that a computer program does exactly what is stated in the program specification it was written to realize. This is a type of formal verification which is specifically aimed at verifying the code itself, not an abstract model of the program.

For functional programming languages, some programs can be verified by equational reasoning, usually together with induction. Code in an imperative language could be proved correct by use of Hoare logic.

• Automated theorem proving
• Formal equivalence checking
• LURCH
• Model checking
• Proof checker
• Property Specification Language
• Selected formal verification bibliography
• Static code analysis
• Temporal logic in finite-state verification

• EmbeddedValidator, Matlab/Simulink/Stateflow/Targetlink Formal Verification Environment
• Statemate ModelChecker, Statemate Models Robustness Checking
• Statemate ModelCertifier, Statemate Models Requirements Certification
• Prover Plug-In, a widely used commercial formal verification engine
• GC6 - The Verification Grand Challenge for Computing
• Polyspace Technologies and the Polyspace Verifier
• The ESC/Java program verifier and Simplify theorem-prover
• The SMVS formal verification project at Man-Made Minions
• The SPARK Ada language and SPARK Examiner verification toolset
• The Spec# language, compiler and program verifier
• LDRA and the LDRA tool suite
• The KeY verification system