CADP 2011: a toolbox for the construction and analysis of distributed processes

Hubert Garavel1, Frédéric Lang1, Radu Mateescu1, Wendelin Serwe1
1INRIA/Laboratoire d’Informatique de Grenoble, VASY Team, Montbonnot St Martin, France

Tóm tắt

CADP (Construction and Analysis of Distributed Processes) is a comprehensive software toolbox that implements the results of concurrency theory. Started in the mid-1980s, CADP has been continuously developed by adding new tools and enhancing existing ones. Today, CADP benefits from a worldwide user community, both in academia and industry. This paper presents the latest release, CADP 2011, which is the result of a considerable development effort spanning the last five years. The paper first describes the theoretical principles and the modular architecture of CADP, which has inspired several other recent model checkers. The paper then reviews the main features of CADP 2011, including compilers for various formal specification languages, equivalence checkers, model checkers, compositional verification tools, performance evaluation tools, and parallel verification tools running on clusters and grids. Finally, the paper surveys some significant case studies.

Tài liệu tham khảo

Bouali, A., Ressouche, A., Roy, V., de Simone, R.: The Fc2Tools set: a toolset for the verification of concurrent systems. In: Proceedings of the 8th Conference on Computer-Aided Verification (New Brunswick, New Jersey, USA). Lecture Notes in Computer Science, vol. 1102. Springer, Berlin, Aug 1996

Champelovier, D., Clerc, X., Garavel, H., Guerte, Y., McKinty, C., Powazny, V., Lang, F., Serwe, W., Smeding, G.: Reference Manual of the LOTOS NT to LOTOS Translator (Version 5.4). INRIA/VASY, Sept 2011

Chossart, R.: Évaluation d’outils de vérification pour les spécifications de systèmes d’information. Mémoire maître ès sciences, Université de Sherbrooke, Canada, Mar 2010

Cleaveland, R., Li, T., Sims, S.: The Concurrency Workbench of the New Century (Version 1.2). User’s manual, July 2000

Crouzen, P., Lang, F.: Smart reduction. In: Proceedings of Fundamental Approaches to Software Engineering FASE’2011 (Saarbrücken, Germany). Lecture Notes in Computer Science, vol. 6603, pp. 111–126. Springer, Berlin, Mar 2011

Emerson, E.A., Lei, C.-L.: Efficient model checking in fragments of the propositional Mu-calculus. In: Proceedings of the 1st International Symposium on Logic in Computer Science LICS’86, pp. 267–278 (1986)

Fernandez, J.-C.: ALDEBARAN: un système de vérification par réduction de processus communicants. Thèse de Doctorat, Université Joseph Fourier (Grenoble), May 1988

Fernandez, J.-C., Garavel, H., Kerbrat, A., Mateescu, R., Mounier, L., Sighireanu, M.: CADP (CÆSAR/ALDEBARAN Development Package): A Protocol Validation and Verification Toolbox. In: Proceedings of the 8th Conference on Computer-Aided Verification (New Brunswick, New Jersey, USA). Lecture Notes in Computer Science, vol. 1102, pp. 437–440. Springer, Berlin, Aug 1996

Fernandez, J.-C., Richier, J.-L., Voiron, J.: Verification of protocol specifications using the CESAR system. In: Proceedings of the 5th IFIP International Workshop on Protocol Specification, Testing and Verification (Moissac, France), pp. 71–90. IFIP, North-Holland, June 1985

Garavel, H.: Compilation et vérification de programmes LOTOS. Thèse de Doctorat, Université Joseph Fourier (Grenoble), Nov 1989

Garavel, H.: On the introduction of gate typing in E-LOTOS. Rapport SPECTRE 94-3, VERIMAG, Grenoble, Feb. 1994. Annex D of ISO/IEC JTC1/SC21/WG1 N1314 Revised Draft on Enhancements to LOTOS and Annex C of ISO/IEC JTC1/SC21/WG1 N1349 Working Draft on Enhancements to LOTOS

Garavel, H.: Défense et illustration des algèbres de processus. In Actes de l’Ecole d’été Temps Réel ETR 2003 (Toulouse, France). Institut de Recherche en Informatique de Toulouse, Sept 2003

Garavel, H., Sighireanu, M.: Towards a second generation of formal description techniques—rationale for the design of E-LOTOS. In: Proceedings of the 3rd International Workshop on Formal Methods for Industrial Critical Systems FMICS’98 (Amsterdam, The Netherlands), pp. 187–230, Amsterdam, May 1998. CWI. Invited lecture

Garavel, H., Turlier, P.: CÆSAR.ADT: un compilateur pour les types abstraits algébriques du langage LOTOS. In: Actes du Colloque Francophone pour l’Ingénierie des Protocoles CFIP’93 (Montréal, Canada) (1993)

Groote, J.F., Ponse, A.: The syntax and semantics of μCRL. In: Algebra of Communicating Processes’94, Workshops in Computing Series, pp. 26–62. Springer, Berlin (1995)

Helmstetter, C.: TLM.OPEN: a SystemC/TLM Front-End for the CADP Verification Toolbox. Workshop on Simulation Based Development of Certified Embedded Systems SBDCES’09 (Awaji Island, Hyogo, Japan), Oct 2009

Hermanns H.: Interactive Markov Chains and the Quest for Quantified Quality. Lecture Notes in Computer Science, vol. 2428. Springer, Berlin (2002)

Holzmann G.J.: The SPIN Model Checker: Primer and Reference Manual. Addison-Wesley, Reading (2003)

ISO/IEC.: LOTOS—a formal description technique based on the temporal ordering of observational behaviour. International Standard 8807, International Organization for Standardization—Information Processing Systems—Open Systems Interconnection, Genève, Sept 1989

ISO/IEC. Enhancements to LOTOS (E-LOTOS). International Standard 15437:2001, International Organization for Standardization—Information Technology, Genève, Sept 2001

ITU-T.: Specification and Description Language (SDL). ITU-T Recommendation Z.100. International Telecommunication Union, Genève (1992)

Khan, A.M.: Connection of Compositional Verification Tools for Embedded Systems. Mémoire master 2 recherche, Université Joseph Fourier, Grenoble, June 2006

Magee, J., Kramer, J.: Concurrency: State Models and Java Programs. Wiley, New York (2006)

Malhotra, J., Smolka, S.A., Giacalone, A., Shapiro, R.: A tool for hierarchical design and simulation of concurrent systems. In: Proceedings of the BCS-FACS Workshop on Specification and Verification of Concurrent Systems (Stirling, Scotland), pp. 140–152, Swindon, UK. British Computer Society, July 1988

Mateescu, R.: Vérification des propriétés temporelles des programmes parallèles. Thèse de Doctorat, Institut National Polytechnique de Grenoble, April 1998

Mateescu, R., Garavel, H.: XTL: a meta-language and tool for temporal logic model-checking. In: Proceedings of the International Workshop on Software Tools for Technology Transfer STTT’98 (Aalborg, Denmark), pp. 33–42. BRICS, July 1998

Mateescu, R., Serwe, W.: Model checking and performance evaluation with CADP illustrated on shared-memory mutual exclusion protocols. Sci. Comput. Program. (2012). doi:10.1016/j.scico.2012.01.003

Milner R.: Communication and Concurrency. Prentice-Hall, Englewood Cliffs (1989)

Queille J.-P.: Le système CESAR: description, spécification et analyse des applications réparties. Université Scientifique et Médicale de Grenoble, Grenoble (1982)

Rose, A., Swan, S., Pierce, J., Fernandez, J.-M.: Transaction Level Modeling in SystemC. Open SystemC Initiative (2005)

Thivolle, D.: Langages modernes pour la vérification des systèmes asynchrones. Thèse de Doctorat, Université Joseph Fourier (Grenoble, France) and Universitatea Politehnica din Bucuresti (Bucharest, Romania), April 2011

Wolper, P.: A translation from full branching time temporal logic to one letter propositional dynamic logic with looping. Unpublished manuscript (1982)