A BSP algorithm for on-the-fly checking CTL* formulas on security protocols

Frédéric Gava (1) , Franck Pommereau (2) , Michael Guedj (1)

1 LACL - Laboratoire d'Algorithmique Complexité et Logique
2 IBISC - Informatique, Biologie Intégrative et Systèmes Complexes

This paper presents a distributed (Bulk-Synchronous Parallel or bsp) algorithm to compute on-the-fly whether a structured model of a security protocol satisfies a ctl {Mathematical expression} formula. Using the structured nature of the security protocols allows us to design a simple method to distribute the state space under consideration in a need-driven fashion. Based on this distribution of the states, the algorithm for logical checking of a ltl formula can be simplified and optimised allowing, with few tricky modifications, the design of an efficient algorithm for ctl {Mathematical expression} checking. Some prototype implementations have been developed, allowing to run benchmarks to investigate the parallel behaviour of our algorithms.

Keywords: Security protocols; Model-checking; ltl; State-space; bsp; ctl {Mathematical expression}

Domains: Modeling and Simulation; Networking and Internet Architecture [cs.NI]

Frédéric Gava, Franck Pommereau, Michael Guedj. A BSP algorithm for on-the-fly checking CTL* formulas on security protocols. Journal of Supercomputing, 2014, 69 (2), pp.629--672. ⟨10.1007/s11227-014-1099-8⟩. ⟨hal-00950399⟩