Diamonds for security : a non-interleaving operational semantics for the applied pi-calculus

Aubert, Clément and Horne, Ross and Johansen, Christian; Klin, Bartek and Lasota, Sławomir and Muscholl, Anca, eds. (2022) Diamonds for security : a non-interleaving operational semantics for the applied pi-calculus. In: 33rd International Conference on Concurrency Theory. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, POL, 30:1-30:26. ISBN 9783959772464 (https://doi.org/10.4230/LIPIcs.CONCUR.2022.30)

[thumbnail of Aubert-etal-CONCUR-2022-Diamonds-for-security]
Preview
 Text. Filename: Aubert_etal_CONCUR_2022_Diamonds_for_security.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (1MB)| Preview

Abstract

We introduce a non-interleaving structural operational semantics for the applied π-calculus and prove that it satisfies the properties expected of a labelled asynchronous transition system (LATS). LATS have well-studied relations with other standard non-interleaving models, such as Mazurkiewicz traces or event structures, and are a natural extension of labelled transition systems where the independence of transitions is made explicit. We build on a considerable body of literature on located semantics for process algebras and adopt a static view on locations to identify the parallel processes that perform a transition. By lifting, in this way, work on CCS and π-calculus to the applied π-calculus, we lay down a principled foundation for reusing verification techniques such as partial-order reduction and non-interleaving equivalences in the field of security. The key technical device we develop is the notion of located aliases to refer unambiguously to a specific output originating from a specific process. This light mechanism ensures stability, avoiding disjunctive causality problems that parallel extrusion incurs in similar non-interleaving semantics for the π-calculus.

ORCID iDs

Aubert, Clément, Horne, Ross ORCID logoORCID: https://orcid.org/0000-0003-0162-1901 and Johansen, Christian; Klin, Bartek, Lasota, Sławomir and Muscholl, Anca
CORE (COnnecting REpositories)