Direction de recherche : Fabrice KORDON

Co-encadrement : BAARIR Souheib, THIERRY-MIEG Yann

Exploitation des symétries pour le modèle checking : du modèle au codage

Les systèmes répartis deviennent omniprésents au quotidien, en particulier dans des domaines critiques, requérant une forte garantie de fiabilité. Les approches basées sur le test sont intrinsèquement non-exhaustives, rendant nécessaire l’usage de méthodes formelles. Parmi elles, nous nous concentrons sur le model-checking, qui explore tous les comportements d’un système pour s’assurer que sa spécification est respectée. Mais cette approche se heurte à l’explosion combinatoire : le nombre d’états d’un système réparti croît exponentiellement avec son nombre de composants.
Nous retenons deux des nombreuses solutions à ce problème : - les symétries pour identifier des comportements similaires : ils partagent des propriétés communes, ce qui réduit le nombre d’états à explorer. - des structures de données compactes, comme les diagrammes de décision (DD), pour réduire l’empreinte mémoire de l’exploration.
Nous proposons trois principales contributions : - La réduction par symétries et les DD sont théoriquement orthogonaux, mais se combinent mal en pratique, car l’efficacité des DD repose sur l’emploi d’algorithmes dédiés. Nous proposons un nouvel algorithme pour appliquer la réduction par symétries sur des DD, et démontrons son efficacité pratique. - Classiquement, les opérations sur les DD sont encodées après un pré-calcul de toutes les entrées possibles. Nous offrons un nouveau mécanisme de manipulation des DD, entièrement symbolique, qui évite un tel pré-calcul. Nous démontrons son efficacité pour encoder une relation de transition. Nous montrons comment ces deux contributions peuvent être appliquées à un formalisme déjà existant, les Symmetric Nets with Bags.

Publications 2011-2018

• 2018
  • H. Metin, S. Baarir, M. Colange, F. Kordon : “CDCLSym: Introducing Effective Symmetry Breaking in SAT Solving”, Tools and Algorithms for the Construction and Analysis of Systems 24^th International Conference, TACAS 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, Thessaloniki, Greece, April 14-20, 2018, Proceedings,, Tessaloniki, Greece (2018)
• 2016
  • A. Linard, B. Barbot, D. Buchs, M. Colange, C. Démoulins, L. Hillah, A. Martin : “Layered Data: A Modular Formal Definition without Formalisms”, CEUR-WS.org, vol. 1591, CEUR Workshops Proceedings, Toruń, Poland, pp. 287-306 (2016)
• 2013
  • M. Colange : “Symmetry Reduction and Symbolic Data Structures for Model-Checking of Distributed Systems.”, soutenance de thèse, soutenance 10/12/2013, direction de recherche Kordon, Fabrice, co-encadrement : Baarir, Souheib, Thierry-mieg, Yann (2013)
  • M. Colange, S. Baarir, F. Kordon, Y. Thierry‑Mieg : “Towards Distributed Software Model-Checking using Decision Diagrams”, 25^th International Conference on Computer Aided Verification (CAV), vol. 8044, Lecture Notes in Computer Science, Saint-Petersbourg, Russian Federation, pp. 830-845, (Springer Verlag) (2013)
• 2012
  • M. Colange, F. Kordon, Y. Thierry‑Mieg, S. Baarir : “State Space Analysis using Symmetries on Decision Diagrams”, 12^th International Conference on Application of Concurrency to System Design (ACSD'2012), Hamburg, Germany, pp. 164-172, (IEEE Computer Society) (2012)
  • M. Colange, L. Hillah, F. Kordon, P. Parutto : “Extreme Symmetries in Complex Distributed Systems: the Bag-Oriented Approach”, Development, Operation and Management of Large-Scale Complex IT Systems, 17^th Monterey Workshop, Revised Selected Papers, vol. 7539, Lecture Notes in Computer Science, Oxford, United Kingdom, pp. 330-352, (Springer) (2012)
  • F. Kordon, A. Linard, D. Buchs, M. Colange, S. Evangelista, K. Lampka, N. Lohmann, E. Paviot‑Adet, Y. Thierry‑Mieg, H. Wimmel : “Report on the Model Checking Contest at Petri Nets 2011”, LNCS Transactions on Petri Nets and Other Models of Concurrency, vol. 7400 (VI), Lecture Notes in Computer Science, pp. 169-196, (Springer) (2012)
• 2011
  • M. Colange, S. Baarir, F. Kordon, Y. Thierry‑Mieg : “Crocodile: a Symbolic/Symbolic tool for the analysis of Symmetric Nets with Bag”, 32^nd International Conference on Petri Nets and Other Models of Concurrency (ICATPN 2011), vol. 6709, Lecture Notes in Computer Science, Newcastle, United Kingdom, pp. 338-347, (Springer) (2011)