Ph.D Thesis | |

Ph.D Student | Shoham Buchbinder Sharon |
---|---|

Subject | Abstraction-Refinement and Modularity in Mu-Calculus Model Checking |

Department | Department of Computer Science |

Supervisor | PROFESSOR EMERITUS Orna Grumberg |

Full Thesis text |

Model checking is an automated technique for checking whether or not a given system model fulfills a desired property, described as a temporal logic formula. Yet, as real models tend to be very big, model checking encounters the state-explosion problem, which refers to its high space requirements. Two of the most successful approaches to fighting the state-explosion problem in model checking are abstraction and compositional model checking.

*Abstractions* hide certain
details of the system in order to result in a smaller model. In some cases the
abstraction is too coarse, resulting in an inconclusive model checking result.
Thus, the abstract model is *refined* by adding more details into it,
making it more similar to the concrete model. Iterating this process is called *abstraction-refinement*.
In *compositional* model checking, on the other hand, one tries to verify
parts of the system separately in order to avoid the construction of the entire
system.

In this research, we investigate abstraction-refinement and compositional techniques for specifications in the mu-calculus, which is a powerful formalism for expressing properties of transition systems using fixpoint operators. Our work exploits and extends the game-based approach to mu-calculus model checking, in which the model checking problem is formulated as a game between a verifier and a falsifier. We develop novel abstraction-refinement schemes for the mu-calculus, based on a 3-valued semantics. The 3-valued semantics allows an abstract model to be used for verification as well as falsification, unlike traditional abstraction which is only used for verification. We investigate both the efficiency and the precision of abstract models used within the abstraction-refinement framework. We then extend our work on abstraction-refinement to the arena of compositional verification, thus joining the forces of both approaches. We use techniques taken from the game-based 3-valued model checking for abstract models to obtain a novel fully automatic compositional technique that can determine the truth value of the full mu-calculus with respect to a given system.