RR-3899 : Efficient On-the-Fly Model-Checking for Regular Alternation-Free Mu-Calculus

Abstract : Model-checking is a successful technique for automatically verifying concurrent finite-state systems. When building a model-checker, a good compromise must be made between the expressive power of the property description formalism, the complexity of the model-checking problem, and the user-friendliness of the interface. We present a temporal logic and an associated model-checking method that attempt to fulfill these criteria. The logic is an extension of the alternation-free mu-calculus with ACTL-like action formulas and PDL-like regular expressions, allowing a concise and intuitive description of safety, liveness, and fairness properties over labeled transition systems. The model-checking method is based upon a succinct translation of the verification problem into a boolean equation system, which is solved by means of an efficient local algorithm having a good average complexity. The algorithm also allows to generate full diagnostic information (examples and counterexamples) for temporal formulas. This method is at the heart of the EVALUATOR 3.0 model-checker that we implemented within the CADP toolset using the generic OPEN/CAESAR environment for on-the-fly verification.

Résumé : a vérification basée sur les modèles (model-checking) est une technique utilisée avec succès pour la vérification automatique des systèmes concurrents à états finis. Lors de la construction d'un évaluateur (model-checker), il est nécessaire d'effectuer un bon compromis entre l'expressivité du formalisme de description des propriétés, la complexité du problème de la vérification et la facilité d'utilisation de l'interface. Nous présentons une logique temporelle et une méthode de vérification associée conçues afin de satisfaire ces critères. La logique est une extension du mu-calcul sans alternance avec des formules sur actions comme en ACTL et des expressions régulières comme en PDL, permettant une description concise et intuitive des propriétés de sûreté, vivacité et équité sur des systèmes de transitions étiquetées. La méthode de vérification est basée sur une traduction succincte du problème vers un système d'équations booléennes qui est résolu au moyen d'un algorithme efficace ayant une bonne complexité moyenne. L'algorithme permet aussi de générer des diagnostics (exemples et contre-exemples) pour les formules temporelles. Cette méthode sert de base à l'évaluateur EVALUATOR 3.0 que nous avons implémenté dans la boite à outils CADP en utilisant l'environnement générique de vérification à la volée OPEN/CAESAR.

RR-3899 - Efficient On-the-Fly Model-Checking for Regular Alternation-Free Mu-Calculus