<  Back to the Polytechnique Montréal portal

Symbolic approach to the analysis of security protocols

Stéphane Lafrance

Article (2004)

Published Version
Terms of Use: All rights reserved.
Download (567kB)
Cite this document: Lafrance, S. (2004). Symbolic approach to the analysis of security protocols. Journal of Universal Computer Science, 10(9), p. 1156-1198. doi:10.3217/jucs-010-09-1156
Show abstract Hide abstract


The specification and validation of security protocols often requires viewing function calls - like encryption/decryption and the generation of fake messages explicitly as actions within the process semantics. Following this approach, this paper introduces a symbolic framework based on value-passing processes able to handle symbolic values like fresh nonces, fresh keys, fake addresses and fake messages. The main idea in our approach is to assign to each value-passing process a formula describing the symbolic values conveyed by its semantics. In such symbolic processes, called constrained processes, the formulas are drawn from a logic based on a message algebra equipped with encryption, signature and hashing primitives. The symbolic operational semantics of a constrained process is then established through semantic rules updating formulas by adding restrictions over the symbolic values, as required for the process to evolve. We then prove that the logic required from the semantic rules is decidable. We also define a bisimulation equivalence between constrained processes; this amounts to a generalisation of the standard bisimulation equivalence between (non-symbolic) value-passing processes. Finally, we provide a complete symbolic bisimulation method for constructing the bisimulation between constrained processes.

Uncontrolled Keywords

bisimulation, equivalence-checking, formal methods, noninterference, process algebra, protocols, symbolic

Open Access document in PolyPublie
Subjects: 2700 Technologie de l'information > 2700 Technologie de l'information
2700 Technologie de l'information > 2713 Algorithmes
Department: Département de génie informatique et génie logiciel
Research Center: Non applicable
Date Deposited: 17 Jan 2019 15:19
Last Modified: 18 Jan 2019 01:20
PolyPublie URL: https://publications.polymtl.ca/3383/
Document issued by the official publisher
Journal Title: Journal of Universal Computer Science (vol. 10, no. 9)
Publisher: J.UCS Consortium
Official URL: https://doi.org/10.3217/jucs-010-09-1156


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only