Strand Spaces with Choice via a Process Algebra Semantics

Yang, Fan; Escobar, Santiago; Meadows, Catherine; Meseguer, José; Santiago, Sonia

Permalink

https://hdl.handle.net/2142/90989 Copy

Description

Title

Strand Spaces with Choice via a Process Algebra Semantics

Author(s)

• Yang, Fan
• Escobar, Santiago
• Meadows, Catherine
• Meseguer, José
• Santiago, Sonia

Issue Date

2016-07

Keyword(s)

• cryptographic protocol analysis
• narrowing-based reachability analysis
• process algebra
• rewriting logic

Abstract

Roles in cryptographic protocols do not always have a linear execution, but may include choice points causing the protocol to continue along different paths. In this paper we address the problem of representing choice in the strand space model of cryptographic protocols, particularly as it is used in the Maude-NPA cryptographic protocol analysis tool. To achieve this goal, we develop and give formal semantics to a process algebra for cryptographic protocols that supports a rich taxonomy of choice primitives for composing strand spaces. In our taxonomy, deterministic and non-deterministic choices are broken down further. Non-deterministic choice can be either explicit, i.e., one of two paths is chosen, or implicit, i.e. the value of a variable is chosen non-deterministically. Likewise, deterministic choice can be either an (explicit) if-then-else choice, i.e. one path is chosen if a predicate is satisfied, while the other is chosen if it is not, or implicit deterministic choice, i.e. execution continues only if a certain pattern is matched. We have identified a class of choices which includes finite branching and some cases of infinite branching, which we address in this paper. Our main theoretical results are two bisimulation results: one proving that the formal semantics of our process algebra is bisimilar to the forwards execution semantics of its associated strands, and another showing that it is also bisimilar with respect to the symbolic backwards semantics of the strands such as that supported by Maude-NPA. At the practical level, we present a prototype implementation of our process algebra in Maude-NPA, illustrate its expressive power and naturalness with various examples, and show how it can be effectively used in formal analysis.

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/90989

Sponsor(s)/Grant Number(s)

• Partially supported by NSF grant CNS-131910
• Partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN 2015-69175-C4-1-R and TIN 2013-45732-C4-1-P
• Paritally supported by Generalitat Valenciana under grant PROME- TEOII/2015/013.

Owning Collections