Model checking verifies whether a formally represented system satisfies a specified property, often a temporal logic formula over a finite transition system. A safety question asks whether a bad state is reachable; exhaustive state exploration can either find a counterexample path or establish its absence in the model. Symbolic model checking represents sets of states compactly, while bounded methods search executions up to a chosen horizon. Verification is relative to the model and assumptions: a missing physical behaviour is not ruled out merely because it was omitted from the transition relation.[ref]
https://www.cs.cmu.edu/~modelcheck/. CMU model-checking group, finite-state verification and temporal specifications
State-space explosion is the rapid growth of a model's possible global configurations as its components are combined. If independent components each have two local states, their Cartesian product has global states. Thirty such components already permit combinations, before accounting for additional data values.
Model checking must establish a property over relevant reachable behavior, so checking one representative execution is insufficient. The reachable subset can be much smaller than the full product, and symbolic representations can compactly describe many configurations at once. However, compactness depends on structure; it is not a universal removal of exponential difficulty. The practical aim is to exploit shared structure without omitting behavior needed for the claimed formal verification.[ref]
https://www.cs.cmu.edu/~modelcheck/. CMU model-checking group, finite-state concurrent systems and symbolic traversal
Symbolic model checking verifies a Transition system by representing sets of states and transitions as formulas or decision structures rather than enumerating each state separately. Encode a current state by bits and its successor by bits . A formula describes the transition relation. If denotes currently reachable states, the next reachable set isIterating from the initial-state formula reaches a fixed point in a finite system. Intersecting that set with a bad-state formula checks a safety property.
Binary decision diagrams can make these operations compact when the represented Boolean structure is favorable. A system with Boolean state components has up to states, so sharing structure can be decisive. The representation can nevertheless become exponentially large, and variable ordering strongly affects a decision diagram's size. Symbolic representation mitigates state-space explosion; it does not abolish it.
For a state formula in a fixed labelled transition system, its satisfaction set is . This is a set of states; it is distinct from the assertion that every initial state satisfies the formula.
A formal verification method that encodes a bounded execution and a violated specification as a Boolean satisfiability problem. A satisfying assignment yields a counterexample. For infinite-path properties, a lasso path can finitely represent a repeated execution. Failure to find a counterexample at one finite bound alone does not prove an unbounded property.[ref]
Symbolic Model Checking without BDDs by Armin Biere and others. §§2–4, bounded encodings; §5, bounds
Articles by others on the same topic
Model checking is a formal verification technique used in computer science and systems engineering to systematically explore the states of a finite system model to verify whether certain properties hold. It is often applied to hardware and software systems, where the goal is to ensure that the system behaves correctly under all possible scenarios. Key components of model checking include: 1. **Model**: The system being verified is represented as a mathematical model. This model typically captures the system's states, transitions, and behaviors.