Approaches To Formal Verification
One approach and formation 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 finitely by using abstraction or taking advantage of symmetry). 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 properties to be verified are often described in temporal logics, such as linear temporal logic (LTL) or computational tree logic (CTL). The great advantage of model checking is that it is often fully automatic; its primary disadvantage is that it does not in general scale to large systems; symbolic models are typically limited to a few hundred bits of state, while explicit state enumeration requires the state space being explored to be relatively small.
Another approach is deductive verification. It consists of generating from the system and its specifications (and possibly other annotations) a collection of mathematical proof obligations, the truth of which imply conformance of the system to its specification, and discharging these obligations using either interactive theorem provers (such as HOL], ACL2, Isabelle, or Coq), automatic theorem provers, or SMT solvers. This approach has the disadvantage that it typically requires the user to understand in detail why the system works correctly, and to convey this information to the verification system, either in the form of an sequence of theorems to be proved or in the form of specifications of system components (e.g. functions or procedures) and perhaps subcomponents (such as loops or data structures).
A slightly different (and complementary) approach is program derivation, in which efficient code is produced from functional specifications by a series of correctness-preserving steps. An example of this approach is the Bird-Meertens Formalism, and this approach can be seen as another form of correctness by construction.
Read more about this topic: Formal Verification
Famous quotes containing the words approaches to, approaches, formal and/or verification:
“Someone approaches to say his life is ruined
and to fall down at your feet
and pound his head upon the sidewalk.”
—David Ignatow (b. 1914)
“The closer a man approaches tragedy the more intense is his concentration of emotion upon the fixed point of his commitment, which is to say the closer he approaches what in life we call fanaticism.”
—Arthur Miller (b. 1915)
“The formal Washington dinner party has all the spontaneity of a Japanese imperial funeral.”
—Simon Hoggart (b. 1946)
“A fact is a proposition of which the verification by an appeal to the primary sources of our knowledge or to experience is direct and simple. A theory, on the other hand, if true, has all the characteristics of a fact except that its verification is possible only by indirect, remote, and difficult means.”
—Chauncey Wright (1830–1875)