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. In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true, within the accepted standards of the field. ... In theoretical computer science, correctness of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification. ... Flowcharts are often used to represent algorithms. ... In computer science and software engineering, formal methods are mathematically-based techniques for the specification, development and verification of software and hardware systems. ... For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ...

Software Testing Portal

Image File history File links Portal. ...

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. A cryptographic protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods. ... This article is not about combinatory logic, a topic in mathematical logic. ... Digital circuits are electric circuits based on a number of discrete voltage levels. ...

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. Fig. ... In theoretical computer science, a state transition system is an abstract machine used in the study of computation. ... A Petri net is a mathematical representation of discrete distributed systems. ... In the first half of the 20th century, various formalisms were proposed to capture the informal concept of computable function, μ-recursive functions, Turing Machines and the λ-calculus possibly being the most well-known examples today. ... In computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way (See formal semantics of programming languages). ... In computer science, denotational semantics is an approach to formalizing the semantics of computer systems by constructing mathematical objects (called denotations or meanings) which express the semantics of these systems. ... Axiomatic Semantics is an approach based on mathematical logic to proving the correctness of computer programs. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ...

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. Model checking is the process of checking whether a given model satisfies a given logical formula. ... In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. ... There are very few or no other articles that link to this one. ...

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 various HOL (which stands for Higher Order Logic) systems are a family of interactive theorem proving systems sharing similar logics and implementation strategies. ... ACL2 is a software system consisting of a programming language, an extensible theory in a first-order logic, and a mechanical theorem prover. ... The Isabelle theorem prover is an interactive theorem proving framework, a successor of the HOL theorem prover. ...

The properties to be verified are often described in temporal logics, such as linear temporal logic (LTL) or computational tree logic (CTL). In logic, the term temporal logic is used to describe any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time. ... Linear temporal logic (LTL) is a modal temporal logic with modalities referring to time. ... Computational tree logic (CTL) is a branching-time logic, meaning that its model of time is a tree-like structure in which the future is not determined; there are different paths in the future, any one of which might be actual path that is realised. ...

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. The word validation has several uses: In general, validation is the process of checking if something satisfies a certain criterion. ...

• 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 Verification and Validation (V&V) is the process of checking that a product, service, or system meets specifications and that it fulfills its intended purpose. ...

See also

Look up verifiability in Wiktionary, the free dictionary.

• 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

Wikipedia does not have an article with this exact name. ... Wiktionary (a portmanteau of wiki and dictionary) is a multilingual, Web-based project to create a free content dictionary, available in over 151 languages. ... Automated theorem proving (ATP) or automated deduction, currently the most well-developed subfield of automated reasoning (AR), is the proving of mathematical theorems by a computer program. ... Formal equivalence checking process is a part of Electronic Design Automation, commonly used during the development of digital integrated circuits, to formally prove that two representations of a circuit design exhibit exactly the same behavior. ... Lurch is the fictional manservant to The Addams Family created by cartoonist Charles Addams. ... Model checking is the process of checking whether a given model satisfies a given logical formula. ... Proof checking is the process of using software for checking proofs for correctness. ... Property Specification Language is a language standardized by Accellera for specifying properties or assertions about hardware designs. ... This is a list of important publications in computer science, organized by field. ... Static analysis is the term applied to the analysis of computer software that is performed without actually executing programs built from that software (analysis performed on executing programs is known as dynamic analysis). ... Temporal Logic In Finite-State Verification In finite-state verification, model checkers examine finite-state machines representing concurrent software systems looking for errors in design. ...

External links

• Prover iLock, Signaling Design Automation Tool Suite
• 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
• Mathworks Polyspace, fomerly known as 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
• The VectorCAST tool suite for C/C++ and Ada unit and integration testing