Editing Formal verification

{{short description|Proving or disproving the correctness of certain intended algorithms}}
{{hatnote group|
{{Distinguish|Verificationism}}
{{for|the Wikipedia policy|Wikipedia:Verifiability|selfref=true}}
}}
{{Use mdy dates|date=June 2019}}

In the context of [[Computer hardware|hardware]] and [[software]] systems, '''formal verification''' is the act of [[Mathematical proof|proving]] or disproving the [[correctness (computer science)|correctness]] of a system with respect to a certain [[formal specification]] or property, using [[formal methods]] of [[mathematics]].<ref>{{cite journal|last=Sanghavi|first=Alok|title=What is formal verification?|journal=EE Times Asia|date=May 21, 2010}}</ref> 
Formal verification is a key incentive for [[formal specification]] of systems, and is at the core of [[formal methods]].
It represents an important dimension of [[Electronic design automation#Analysis and verification|analysis and verification]] in [[electronic design automation]] and is one approach to [[software verification]]. The use of formal verification enables the highest [[Evaluation Assurance Level]] ([[EAL7]]) in the framework of [[common criteria]] for [[computer security]] certification.<ref>{{cite web |url=https://www.commoncriteriaportal.org/files/ccfiles/CC2022PART5R1.pdf |title=Common Criteria for Information Technology Security Evaluation Part 5: Pre-defined packages of security requirements |access-date=April 15, 2025}}</ref>

Formal verification can be helpful in proving the correctness of systems such as: [[cryptographic protocol]]s, [[Combinational logic|combinational circuits]], [[digital circuit]]s with internal memory, and software expressed as [[source code]] in a [[programming language]]. Prominent examples of verified software systems include the [[CompCert]] verified [[C programming language|C]] [[compiler]] and the [[L4 microkernel family#High assurance: seL4|seL4]] high-assurance [[Kernel (operating system)|operating system kernel]].

The verification of these systems is done by ensuring the existence of a [[formal proof]] of a [[mathematical model]] of the system.<ref>{{cite book |editor1=Clarke, Edmund M. |editor2=Henzinger, Thomas A. |editor3=Veith, Helmut |editor4=Bloem, Roderick |author1=Sanjit A. Seshia |author2=Natasha Sharygina |author3=Stavros Tripakis |title=Handbook of Model Checking |date=2018 |publisher=Springer |isbn=978-3-319-10574-1 |pages=75–105 |url=https://doi.org/10.1007/978-3-319-10575-8 |chapter=Chapter 3: Modeling for Verification|doi=10.1007/978-3-319-10575-8 }}</ref> Examples of mathematical objects used to model systems are: [[finite-state machine]]s, [[labelled transition system]]s, [[Horn clause]]s, [[Petri net]]s, [[vector addition system]]s, [[timed automaton|timed automata]], [[hybrid automata]], [[process algebra]], formal semantics of programming languages such as [[operational semantics]], [[denotational semantics]], [[axiomatic semantics]] and [[Hoare logic]].<ref>[http://embedded.eecs.berkeley.edu/research/vis/doc/VisUser/vis_user/node4.html Introduction to Formal Verification], Berkeley University of California, Retrieved November 6, 2013</ref>

== 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.

== Verification and validation ==
{{main|Verification and validation}}

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., is the product specified to the user's actual needs?
* '''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/structural and dynamic/behavioral aspects. E.g., for a software product one can inspect the source code (static) and run against specific test cases (dynamic). Validation usually can be done only dynamically, i.e., the product is tested by putting it through typical and atypical usages ("Does it satisfactorily meet all [[use case]]s?").

== Automated program repair ==
{{main|Automatic bug fixing}}

Program repair is performed with respect to an [[Oracle (computability)|oracle]], encompassing the desired functionality of the program which is used for validation of the generated fix. A simple example is a test-suite—the input/output pairs specify the functionality of the program. A variety of techniques are employed, most notably using [[satisfiability modulo theories]] (SMT) solvers, and [[genetic programming]],<ref>{{cite journal |last1=Le Goues |first1=Claire |author1-link=Claire Le Goues|last2=Nguyen |first2=ThanhVu |last3=Forrest |first3=Stephanie |last4=Weimer |first4=Westley |title=GenProg: A Generic Method for Automatic Software Repair |journal=IEEE Transactions on Software Engineering |date=January 2012 |volume=38 |issue=1 |pages=54–72 |doi=10.1109/TSE.2011.104 |s2cid=4111307 |url = https://www.proquest.com/openview/f837f11066e9c9552df9e497064d6d80/1?pq-origsite=gscholar&cbl=21418&casa_token=X2fQSRNgLNwAAAAA:CBjvmrcBLZRqV7kjC-MY74s0wF68lhBvLF6rV4DWZkalzo2KdlUUzuMU38YgSmXGbwEL2NAr4w}}</ref> using evolutionary computing to generate and evaluate possible candidates for fixes. The former method is deterministic, while the latter is randomized.

Program repair combines techniques from formal verification and [[program synthesis]]. Fault-localization techniques in formal verification are used to compute program points which might be possible bug-locations, which can be targeted by the synthesis modules. Repair systems often focus on a small pre-defined class of bugs in order to reduce the search space. Industrial use is limited owing to the computational cost of existing techniques.

== Industry use ==

{{Cleanup|section|date=October 2022|reason=needs a more well-rounded overview of the subject; filter for what is actually used in industry; only mention notable papers}}

The growth in complexity of designs increases the importance of formal verification techniques in the [[Electronics industry|hardware industry]].<ref>{{Cite book|doi=10.1109/LICS.2003.1210044|year=2003|last1=Harrison|first1=J.|title=18th Annual IEEE Symposium of Logic in Computer Science, 2003. Proceedings|pages=45–54|isbn=978-0-7695-1884-8|chapter=Formal verification at Intel|s2cid=44585546}}</ref><ref>[http://portal.acm.org/citation.cfm?id=800667 Formal verification of a real-time hardware design]. Portal.acm.org (June 27, 1983). Retrieved on April 30, 2011.</ref> At present, formal verification is used by most or all leading hardware companies,<ref>{{cite web|url=http://formalverificationbook.com|title=Formal Verification: An Essential Tool for Modern VLSI Design by Erik Seligman, Tom Schubert, and M V Achutha Kirankumar|year=2015}}</ref> but its use in the [[software industry]] is still languishing.{{citation needed|date=December 2011}} This could be attributed to the greater need in the hardware industry, where errors have greater commercial significance.{{citation needed|date=December 2011}} Because of the potential subtle interactions between components, it is increasingly difficult to exercise a realistic set of possibilities by simulation. Important aspects of hardware design are amenable to automated proof methods, making formal verification easier to introduce and more productive.<ref>{{cite web|url=http://www.cl.cam.ac.uk/~jrh13/slides/types-04sep99/slides1.pdf |title=Formal Verification in Industry |access-date=September 20, 2012}}</ref>

{{As of|2011}}, several operating systems have been formally verified:
NICTA's Secure [[L4 microkernel family#University of New South Wales and NICTA|Embedded L4 microkernel]], sold commercially as [[seL4]] by OK Labs;<ref>{{cite web |url=https://sel4.systems/Docs/seL4-spec.pdf |title=Abstract Formal Specification of the seL4/ARMv6 API |access-date=May 19, 2015 |url-status=dead |archive-url=https://web.archive.org/web/20150521171234/https://sel4.systems/Docs/seL4-spec.pdf |archive-date=May 21, 2015  }}</ref> OSEK/VDX based real-time operating system ORIENTAIS by [[East China Normal University]];{{Citation needed|date=March 2012}} Green Hills Software's [[Integrity (operating system)|Integrity operating system]];{{Citation needed|date=March 2012}} and [[SYSGO]]'s [[PikeOS]].<ref>Christoph Baumann, Bernhard Beckert, Holger Blasum, and Thorsten Bormer [http://www-wjp.cs.uni-saarland.de/publikationen/Ba10EW.pdf Ingredients of Operating System Correctness? Lessons Learned in the Formal Verification of PikeOS] {{Webarchive|url=https://web.archive.org/web/20110719110932/http://www-wjp.cs.uni-saarland.de/publikationen/Ba10EW.pdf |date=July 19, 2011 }}</ref><ref>
[http://www.ganssle.com/rants/gettingitright.htm "Getting it Right"] by Jack Ganssle</ref>
In 2016, a team led by Zhong Shao at Yale developed a formally verified operating system kernel called CertiKOS.<ref>{{cite web|url=https://www.zdnet.com/article/certikos-a-hacker-proof-os/|title=Unhackable OS? CertiKOS enables creation of secure system kernels|first=Robin|last=Harris|website=ZDNet|access-date=June 10, 2019}}</ref><ref>{{cite web|url=https://www.ibtimes.co.uk/certikos-yale-develops-worlds-first-hacker-resistant-operating-system-1591712|title=CertiKOS: Yale develops world's first hacker-resistant operating system|date=November 15, 2016|website=International Business Times UK|access-date=June 10, 2019}}</ref>

As of 2017, formal verification has been applied to the design of large computer networks through a mathematical model of the network,<ref>{{cite web|last=Scroxton|first=Alex|title=For Cisco, intent-based networking heralds future tech demands|url=http://www.computerweekly.com/news/252434028/For-Cisco-intent-based-networking-heralds-future-tech-demands|publisher=Computer Weekly|access-date=February 12, 2018}}</ref> and as part of a new network technology category, [[Intent-Based Networking|intent-based networking]].<ref>{{cite web|last=Lerner|first=Andrew|title=Intent-based networking|url=https://blogs.gartner.com/andrew-lerner/2017/02/07/intent-based-networking/|publisher=Gartner|access-date=February 12, 2018}}</ref> Network software vendors that offer formal verification solutions include [[Cisco]]<ref>{{cite web|last=Kerravala|first=Zeus|title=Cisco brings intent based networks to the data center|url=https://www.networkworld.com/article/965142/cisco-brings-intent-based-networks-to-the-data-center.html|publisher=NetworkWorld|access-date=February 12, 2018|archive-date=December 11, 2023|archive-url=https://web.archive.org/web/20231211215137/https://www.networkworld.com/article/965142/cisco-brings-intent-based-networks-to-the-data-center.html|url-status=live}}</ref> Forward Networks<ref>{{cite web|title=Forward Networks: Accelerating and De-risking Network Operations|work=Insightssuccess Media and Technology Pvt. Ltd. |date=January 16, 2018 |url=http://www.insightssuccess.com/forward-networks-accelerating-de-risking-network-operations/|publisher=Insights Success|access-date=February 12, 2018}}</ref><ref>{{cite web|title=Getting Grounded in Intent=based Networking|url=https://images.idgesg.net/assets/2018/01/idg_2018_intent-based_networking.pdf|publisher=NetworkWorld|access-date=February 12, 2018}}</ref> and Veriflow Systems.<ref>{{cite web|title=Veriflow Systems|url=https://www.bloomberg.com/research/stocks/private/snapshot.asp?privcapid=274750862|publisher=Bloomberg|access-date=February 12, 2018}}</ref>

The [[SPARK (programming language)|SPARK programming language]] provides a toolset which enables software development with formal verification and is [[SPARK (programming language)#Industrial applications|used in several high-integrity systems]].{{citation needed|date=October 2022}}

The [[CompCert|CompCert C compiler]] is a formally verified C compiler implementing the majority of ISO C.<ref>{{Cite web |title=CompCert - The CompCert C compiler |url=https://compcert.org/compcert-C.html |access-date=2023-02-22 |website=compcert.org}}</ref><ref>{{Cite journal |last1=Barrière |first1=Aurèle |last2=Blazy |first2=Sandrine|author2-link=Sandrine Blazy |last3=Pichardie |first3=David |date=2023-01-09 |title=Formally Verified Native Code Generation in an Effectful JIT: Turning the CompCert Backend into a Formally Verified JIT Compiler |journal=Proceedings of the ACM on Programming Languages |volume=7 |issue=POPL |pages=249–277 |doi=10.1145/3571202 |s2cid=253736486 |issn=2475-1421|doi-access=free |arxiv=2212.03129 }}</ref>

== See also ==

{{Wiktionary|verifiability}}

* [[Automated theorem proving]]
* [[Model checking]]
* [[List of model checking tools]]
* [[Formal equivalence checking]]
* [[Proof checker]]
* [[Property Specification Language]]
* [[Static code analysis]]
* [[Temporal logic in finite-state verification]]
* [[Post-silicon validation]]
* [[Intelligent verification]]
* [[Runtime verification]]
* [[Software verification]]
* [[Hardware verification]]

== References ==
{{Reflist}}

[[Category:Electronic circuit verification]]
[[Category:Formal methods]]
[[Category:Logic in computer science]]
[[Category:Theoretical computer science]]