Model checking

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In computer science, model checking, or property checking, is, for a given finite-state model of a system, exhaustively and automatically checking whether this model meets a given specification (a.k.a. correctness properties). Typically, one has hardware or software systems in mind, whereas the specification contains safety requirements such as the absence of deadlocks and similar critical states that can cause the system to crash, as well as liveness requirements.

In order to solve such a problem algorithmically, both the model of the system and the specification are formulated in some precise mathematical language. To this end, the problem is formulated as a task in logic, namely to check whether a given structure satisfies a given logical formula. This general concept applies to many kinds of logic and suitable structures. A simple model checking problem is verifying whether a given formula in the propositional logic is satisfied by a given structure.

Overview[edit]

Property checking is used for verification when two descriptions are not functionally equivalent. During refinement, the specification is complemented with details that are unnecessary in the higher level specification. There is no need to verify the newly introduced properties against the original specification, since it is not even possible. Therefore, the strict bi-directional equivalence check is relaxed to a one-way property check. The implementation or design is regarded as a model of the circuit, whereas the specifications are properties that the model must satisfy.[1]

An important class of model checking methods have been developed for checking models of hardware and software designs where the specification is given by a temporal logic formula. Pioneering work in temporal logic specification was done by Amir Pnueli, who received the 1996 Turing award for "seminal work introducing temporal logic into computing science".[2] Model checking began with the pioneering work of E. M. Clarke, E. A. Emerson,[3][4][5], by J. P. Queille, and J. Sifakis.[6] Clarke, Emerson, and Sifakis shared the 2007 Turing Award for their seminal work founding and developing the field of model checking.[7][8]

Model checking is most often applied to hardware designs. For software, because of undecidability (see computability theory) the approach cannot be fully algorithmic; typically it may fail to prove or disprove a given property. In embedded systems hardware, it is possible to validate a specification delivered i.e. by means of UML activity diagrams[9] or control interpreted Petri nets.[10]

The structure is usually given as a source code description in an industrial hardware description language or a special-purpose language. Such a program corresponds to a finite state machine (FSM), i.e., a directed graph consisting of nodes (or vertices) and edges. A set of atomic propositions is associated with each node, typically stating which memory elements are one. The nodes represent states of a system, the edges represent possible transitions which may alter the state, while the atomic propositions represent the basic properties that hold at a point of execution.

Formally, the problem can be stated as follows: given a desired property, expressed as a temporal logic formula p, and a structure M with initial state s, decide if . If M is finite, as it is in hardware, model checking reduces to a graph search.

Algorithms[edit]

state space enumeration, symbolic state space enumeration, abstract interpretation, symbolic simulation, symbolic trajectory evaluation, symbolic execution

Explicit-state model checking[edit]

Symbolic model checking[edit]

Instead of enumerating reachable states one at a time, the state space can sometimes be traversed more efficiently by considering large numbers of states at a single step. When such state space traversal is based on representations of set of states and transition relations as logical formulas, binary decision diagrams (BDD) or other related data structures, the model-checking method is symbolic.

Historically, the first symbolic methods used BDDs. After the success of propositional satisfiability in solving the planning problem in artificial intelligence (see satplan) in 1996, the same approach was generalized to model checking for the Linear Temporal Logic LTL (the planning problem corresponds to model-checking for safety properties). This method is known as bounded model checking.[11] The success of Boolean satisfiability solvers in bounded model checking led to the widespread use of satisfiability solvers in symbolic model checking.[12]

Techniques[edit]

Model checking tools face a combinatorial blow up of the state-space, commonly known as the state explosion problem, that must be addressed to solve most real-world problems. There are several approaches to combat this problem.

  1. Symbolic algorithms avoid ever explicitly constructing the graph for the finite state machines (FSM); instead, they represent the graph implicitly using a formula in quantified propositional logic. The use of binary decision diagrams (BDDs) was made popular by the work of Ken McMillan[13] and development of open-source BDD manipulation libraries such as CUDD[14] and BuDDy.[15]
  2. Bounded model checking algorithms unroll the FSM for a fixed number of steps and check whether a property violation can occur in or fewer steps. This typically involves encoding the restricted model as an instance of SAT. The process can be repeated with larger and larger values of until all possible violations have been ruled out (cf. Iterative deepening depth-first search).
  3. Partial order reduction can be used (on explicitly represented graphs) to reduce the number of independent interleavings of concurrent processes that need to be considered. The basic idea is that if it does not matter, for the kind of things one intends to prove, whether A or B is executed first, then it is a waste of time to consider both the AB and the BA interleavings.
  4. Abstraction attempts to prove properties of a system by first simplifying it. The simplified system usually does not satisfy exactly the same properties as the original one so that a process of refinement may be necessary. Generally, one requires the abstraction to be sound (the properties proved on the abstraction are true of the original system); however, sometimes the abstraction is not complete (not all true properties of the original system are true of the abstraction). An example of abstraction is to ignore the values of non-boolean variables and to only consider boolean variables and the control flow of the program; such an abstraction, though it may appear coarse, may in fact be sufficient to prove e.g. properties of mutual exclusion.
  5. Counterexample guided abstraction refinement (CEGAR) begins checking with a coarse (imprecise) abstraction and iteratively refines it. When a violation (counterexample) is found, the tool analyzes it for feasibility (i.e., is the violation genuine or the result of an incomplete abstraction?). If the violation is feasible, it is reported to the user. If it is not, the proof of infeasibility is used to refine the abstraction and checking begins again.[16]

Model checking tools were initially developed to reason about the logical correctness of discrete state systems, but have since been extended to deal with real-time and limited forms of hybrid systems.

Computational complexity[edit]

First-order logic[edit]

[needs copy edit]

The model checking problem is studied in the field of computational complexity theory. Specifically, a first-order logical formula is fixed without free variables and the following decision problem is considered:

Given a finite interpretation, for instance one described as a relational database, decide whether the interpretation is a model of the formula.

This problem is in the circuit class AC0. The problem is tractable when imposing some restrictions on the input structure: for instance requiring that it has treewidth bounded by a constant (which more generally implies the tractability of model checking for monadic second-order logic), bounding the degree of every domain element, and more general conditions such as bounded expansion, locally bounded expansion, and nowhere-dense structures.[17] These results have been extended to the task of enumerating all solutions to a first-order formula with free variables.[citation needed]

Monadic second-order logic[edit]

Tools[edit]

Here is a partial list of model checking tools that have a Wikipedia page:

  • Alloy (Alloy Analyzer)
  • BLAST (Berkeley Lazy Abstraction Software Verification Tool)
  • CADP (Construction and Analysis of Distributed Processes) a toolbox for the design of communication protocols and distributed systems
  • CPAchecker, an open-source software model checker for C programs, based on the CPA framework
  • ECLAIR, a platform for the automatic analysis, verification, testing and transformation of C and C++ programs
  • FDR2, a model checker for verifying real-time systems modelled and specified as CSP Processes
  • ISP code level verifier for MPI programs
  • Java Pathfinder – open source model checker for Java programs
  • mCRL2 Toolset, Boost Software License, Based on ACP
  • NuSMV, a new symbolic model checker
  • PAT – an enhanced simulator, model checker and refinement checker for concurrent and real-time systems
  • Prism, a probabilistic symbolic model checker
  • Roméo, an integrated tool environment for modelling, simulation and verification of real-time systems modelled as parametric, time and stopwatch Petri nets
  • SPIN a general tool for verifying the correctness of distributed software models in a rigorous and mostly automated fashion.
  • TAPAs: tool for the analysis of process algebra.
  • TAPAAL, an integrated tool environment for modelling, validation and verification of Timed-Arc Petri Nets
  • TLA+ model checker by Leslie Lamport
  • UPPAAL, an integrated tool environment for modelling, validation and verification of real-time systems modelled as networks of timed automata
  • Zing[18] – experimental tool from Microsoft to validate state models of software at various levels: high-level protocol descriptions, work-flow specifications, web services, device drivers, and protocols in the core of the operating system. Zing is currently being used for developing drivers for Windows.

See also[edit]

References[edit]

Citations[edit]

  1. ^ Lam K., William (2005). "Chapter 1.1: What Is Design Verification?". Hardware Design Verification: Simulation and Formal Method-Based Approaches. Retrieved December 12, 2012.
  2. ^ "Amir Pnueli - A.M. Turing Award Laureate".
  3. ^ Allen Emerson, E.; Clarke, Edmund M. (1980), "Characterizing correctness properties of parallel programs using fixpoints", Automata, Languages and Programming, Lecture Notes in Computer Science, 85: 169–181, doi:10.1007/3-540-10003-2_69, ISBN 978-3-540-10003-4
  4. ^ Edmund M. Clarke, E. Allen Emerson: "Design and Synthesis of Synchronization Skeletons Using Branching-Time Temporal Logic". Logic of Programs 1981: 52-71.
  5. ^ Clarke, E. M.; Emerson, E. A.; Sistla, A. P. (1986), "Automatic verification of finite-state concurrent systems using temporal logic specifications", ACM Transactions on Programming Languages and Systems, 8 (2): 244, doi:10.1145/5397.5399
  6. ^ Queille, J. P.; Sifakis, J. (1982), "Specification and verification of concurrent systems in CESAR", International Symposium on Programming, Lecture Notes in Computer Science, 137: 337–351, doi:10.1007/3-540-11494-7_22, ISBN 978-3-540-11494-9
  7. ^ Press Release: ACM Turing Award Honors Founders of Automatic Verification Technology
  8. ^ USACM: 2007 Turing Award Winners Announced
  9. ^ I. Grobelna, M. Grobelny, M. Adamski, "Model Checking of UML Activity Diagrams in Logic Controllers Design", Proceedings of the Ninth International Conference on Dependability and Complex Systems DepCoS-RELCOMEX, Advances in Intelligent Systems and Computing Volume 286, Springer International Publishing Switzerland, pp. 233–242, 2014
  10. ^ I. Grobelna, "Formal verification of embedded logic controller specification with computer deduction in temporal logic", Przeglad Elektrotechniczny, Vol.87, Issue 12a, pp.47–50, 2011
  11. ^ Clarke, E.; Biere, A.; Raimi, R.; Zhu, Y. (2001). "Bounded Model Checking Using Satisfiability Solving". Formal Methods in System Design. 19: 7–34. doi:10.1023/A:1011276507260.
  12. ^ Vizel, Y.; Weissenbacher, G.; Malik, S. (2015). "Boolean Satisfiability Solvers and Their Applications in Model Checking". Proceedings of the IEEE. 103 (11): 2021–2035. doi:10.1109/JPROC.2015.2455034.
  13. ^ * Symbolic Model Checking, Kenneth L. McMillan, Kluwer, ISBN 0-7923-9380-5, also online.
  14. ^ "CUDD: CU Decision Diagram Package".
  15. ^ "BuDDy – A Binary Decision Diagram Package".
  16. ^ Clarke, Edmund; Grumberg, Orna; Jha, Somesh; Lu, Yuan; Veith, Helmut (2000), "Counterexample-Guided Abstraction Refinement" (PDF), Computer Aided Verification, Lecture Notes in Computer Science, 1855: 154–169, doi:10.1007/10722167_15, ISBN 978-3-540-67770-3
  17. ^ Dawar, A; Kreutzer, S (2009). "Parameterized complexity of first-order logic" (PDF). ECCC.
  18. ^ Zing

Sources[edit]

Further reading[edit]