Model Checking for Software

Model checking automatically verifies whether a system's model satisfies a temporal-logic specification by exhaustively exploring its reachable states.

Definition

Model checking is an automatic verification technique that, given a finite-state model of a system and a temporal-logic specification, exhaustively checks whether the specification holds and produces a counterexample trace if it does not.

Scope

This topic covers automatic verification of finite-state and concurrent systems against temporal-logic properties (safety and liveness), the state-explosion problem and techniques to combat it (symbolic representation with binary decision diagrams, partial-order reduction, abstraction), bounded model checking with SAT/SMT, and counterexample-guided abstraction refinement for software.

Core questions

• How can a property be verified by exploring all reachable states?
• What is the state-explosion problem and how is it mitigated?
• How do symbolic and bounded methods scale model checking?
• How are infinite-state software systems abstracted to finite models?

Key theories

Temporal-logic model checking

Clarke, Emerson, and Sistla, and independently Queille and Sifakis, introduced algorithms to check finite-state concurrent systems against temporal-logic specifications automatically.

Symbolic model checking

Burch and colleagues represented sets of states symbolically with binary decision diagrams, allowing verification of systems with astronomically many states and overcoming naive state explosion.

Clinical relevance

Model checking is used to verify hardware designs, communication protocols, and concurrent and safety-critical software, where it finds subtle bugs that testing misses and provides counterexamples that pinpoint faults. Its automation distinguishes it from interactive theorem proving.

History

Building on Pnueli's introduction of temporal logic for programs, Clarke and Emerson and, independently, Queille and Sifakis devised model checking around 1981-82, work later recognized with a Turing Award. Symbolic model checking with binary decision diagrams (1990s) and SAT-based bounded model checking greatly extended its reach, and abstraction-refinement methods brought it to software.

Debates

Combating state explosion

The central challenge is that the number of states grows exponentially with system size; researchers debate the best mix of symbolic representation, abstraction, partial-order reduction, and bounded checking to keep verification tractable.

Key figures

• Edmund Clarke
• E. Allen Emerson
• Joseph Sifakis
• Kenneth McMillan
• Amir Pnueli

Seminal works

• clarke1986
• queille1982
• burch1992

Frequently asked questions

How does model checking differ from theorem proving?

Model checking is fully automatic and explores a system's state space exhaustively for finite or abstracted models, while theorem proving uses logical deduction (often interactively) and can handle infinite-state systems but requires more human guidance.

What is the state-explosion problem?

It is the exponential growth in the number of reachable states as a system gains components or variables, which limits naive model checking and motivates symbolic, bounded, and abstraction-based techniques.