Formal verification

Formal verification

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.

Usage

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.

Approaches to formal verification

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 a HOL theorem prover, the ACL2 theorem prover or the 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).

Validation and Verification

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

ee also

*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
*Post silicon validation

* [http://www.fmnet.info/gc6/ GC6 - The Verification Grand Challenge for Computing]

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Formal equivalence checking — process is a part of electronic design automation (EDA), commonly used during the development of digital integrated circuits, to formally prove that two representations of a circuit design exhibit exactly the same behavior. Equivalence checking… …   Wikipedia

• Formal methods — In computer science and software engineering, formal methods are particular kind of mathematically based techniques for the specification, development and verification of software and hardware systems.cite web|author=R. W. Butler|title=What is… …   Wikipedia

• Verification and Validation (software) — In software project management, software testing, and software engineering, Verification and Validation (V V) is the process of checking that a software system meets specifications and that it fulfils its intended purpose. It is normally part of… …   Wikipedia

• Verification — The word Verify And Verification can refer to:* Verification and Validation: In engineering or a quality management system, verification is the act of reviewing, inspecting, testing, etc. to establish and document that a product, service, or… …   Wikipedia

• Verification and validation — IV V redirects here. For NASA s IV V Facility, see Independent Verification and Validation Facility. Verification and validation is the process of checking that a product, service, or system meets specifications and that it fulfills its intended… …   Wikipedia

• Formal — The term formal has a number of uses, including:General*relating to formality *opposite of informalocial* Formal occasion ** Formal attire worn on such occasions ** Formals are particular meals at some British universities ** In Australian or… …   Wikipedia

• Formal specification — A formal specification is a mathematical description of software or hardware that may be used to develop an implementation. It describes what the system should do, not (necessarily) how the system should do it. Given such a specification, it is… …   Wikipedia

• Verification (spaceflight) — Verification in the field of space systems engineering covers two verification processes: Qualification and Acceptance Overview Verification standards are developed by organizations like the NASA and the ECSS to establishes the requirements for… …   Wikipedia

• Verification and Validation — Verification Validation is the process of checking that a product, service, or system meets specifications and that it fulfils its intended purpose. These are critical components of a quality management system such as ISO… …   Wikipedia

• verification — ver·i·fi·ca·tion /ˌver ə fə kā shən/ n 1: an act or process of verifying 2: a sworn statement of truth or correctness submitted a verification signed by the defendant with the petition Merriam Webster’s Dictionary of Law. Merriam Webster. 1996 …   Law dictionary