Editing Formal verification (section)

== Approaches ==

=== Model checking ===

[[Model checking]] involves a systematic and exhaustive exploration of the mathematical model. Such exploration is possible for [[Finite model theory|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.{{citation needed|date=December 2014}} The properties to be verified are often described in [[temporal logic]]s, such as [[linear temporal logic]] (LTL), [[Property Specification Language]] (PSL), [[SystemVerilog]] Assertions (SVA),<ref>{{Cite book|title = SystemVerilog Assertions Handbook|edition = 4th |last1 = Cohen|first1 = Ben| first2=Srinivasan |last2 =Venkataramanan |first3=Ajeetha |last3 =Kumari |first4=Lisa |last4 =Piper | publisher = CreateSpace Independent Publishing Platform|year = 2015|isbn = 978-1518681448}}</ref> 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.

=== Deductive verification ===

Another approach is deductive verification.<ref>{{cite book |title=Deductive Software Verification - The KeY Book: From Theory to Practice |editor-first1 = Wolgang |editor-last1 = Ahrendt |editor-last2 = Beckert| editor-first2 = Bernhard |editor-last3 = Bubel |editor-first3 = Richard |editor-last4 = Hähnle |editor-first4 = Reiner |editor-last5 = Schmitt |editor-first5 = Peter H. | date=2016 |publisher=Springer International Publishing : Imprint: Springer |location=Cham |isbn=978-3-319-49812-6 |edition=1st 2016}}</ref><ref>{{cite book |title=Engineering secure and dependable software systems |editor-last1 = Pretschner |editor-first1 = Alexander |editor-last2 = Müller |editor-first2 = Peter |editor-last3 = Stöckle |editor-first3 =  Patrick |date=2019 |publisher=IOS Press |location=Amsterdam, Netherlands |isbn=978-1-61499-976-8 | chapter = 
Building Deductive Program Verifiers - Lecture Notes}}</ref> 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 [[proof assistant]]s (interactive theorem provers) (such as [[HOL theorem prover|HOL]], [[ACL2]], [[Isabelle (theorem prover)|Isabelle]], [[Rocq (software)|Rocq]] (previously known as ''Coq'') or [[Prototype Verification System|PVS]]), or [[Automated theorem proving|automatic theorem provers]], including in particular [[satisfiability modulo theories]] (SMT) solvers. This approach has the disadvantage that it may require 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 a sequence of theorems to be proved or in the form of specifications (invariants, preconditions, postconditions) of system components (e.g. functions or procedures) and perhaps subcomponents (such as loops or data structures).

=== Application to software ===

Formal verification of software programs involves proving that a program satisfies a formal specification of its behavior. Subareas of formal verification include deductive verification (see above), [[abstract interpretation]], [[automated theorem proving]], [[type system]]s, and [[formal methods#Lightweight formal methods|lightweight formal methods]]. A promising type-based verification approach is [[dependent types|dependently typed programming]], in which the types of functions include (at least part of) those functions' specifications, and type-checking the code establishes its correctness against those specifications. Fully featured dependently typed languages support deductive verification as a special case.

Another complementary approach is [[program derivation]], in which efficient code is produced from [[functional programming|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 [[program synthesis]].

These techniques can be ''[[soundness|sound]]'', meaning that the verified properties can be logically deduced from the semantics, or ''unsound'', meaning that there is no such guarantee. A sound technique yields a result only once it has covered the entire space of possibilities. An example of an unsound technique is one that covers only a subset of the possibilities, for instance only integers up to a certain number, and give a "good-enough" result. Techniques can also be ''[[decidability (logic)|decidable]]'', meaning that their algorithmic implementations are [[Termination analysis|guaranteed to terminate]] with an answer, or undecidable, meaning that they may never terminate. By bounding the scope of possibilities, unsound techniques that are decidable might be able to be constructed when no decidable sound techniques are available.