Model Checking and the State-Space Explosion
Finite-state model checking decides a stated property over reachable behavior, using explicit or symbolic methods. Component state counts give a product bound on possible global states. A reduction must preserve the behavior relevant to the property; a conservative abstraction can introduce counterexamples that the original system cannot follow.
What a learner can do afterwards
- Read a safety counterexample trace and distinguish a model violation from a confirmed implementation bug
- Calculate a product bound on global states and explain two property-preserving abstraction methods
- Explain the behavior-preservation condition needed to transfer an abstract safety result to the modeled system
1 · Read
You have distinguished safety from liveness. A finite-state checker decides a stated property over reachable behavior. It can visit states explicitly or represent many states symbolically. Safety failures have finite counterexample traces. In common temporal logics, a liveness failure can be shown by a prefix followed by a repeating cycle. Fairness assumptions determine which runs count.
Model lock clients A and B with bits (a,b), A's bit first. A bit of 1 means holding the lock. Safety forbids both bits being 1. The trace (0,0) -> (1,0) -> (1,1) violates safety when B acquires while A holds. It is an execution of the model. Check whether the implementation permits those steps before calling it an implementation bug.
A global state combines local component states. Three components with two local states each have 2 x 2 x 2 = 8 possible combinations. Some may be unreachable. Adding independent choices grows this product, but adding a component need not increase the reachable state count.
For a conservative safety abstraction, every concrete execution from an initial state must map to an allowed abstract execution, and concrete violations must remain abstract violations. An abstract pass then transfers safety to the concrete model. An abstract failure may be a false alarm. Applying the result to an implementation also requires a faithful implementation model.
Two abstraction methods are hiding data and merging states. Hidden data must retain its possible effects on transitions. Merged states need a relation preserving property-relevant future behavior; equal current labels are insufficient. A reduction justified for safety need not preserve liveness.
Hiding a queue length might admit an acquisition that the original queue rules forbid. Replay the abstract trace against the original model. If no original execution matches, the trace is spurious. Restore the missing constraint and check again.
Check reachable behavior against a property. Interpret traces in their model. Transfer abstract safety through a checked behavior-preservation relation.
Original lesson, questions and flashcards about model checking, written for this dataset.
2 · Watch
En anglaisTake it off screen
Where it sits
Optional connections
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.