PSPSP: A tool for automated verification of stateful protocols in Isabelle/HOL

Abstract

In protocol verification, we observe a wide spectrum from fully automated methods to interactive theorem proving with proof assistants such as Isabelle/HOL. The latter provides overwhelmingly high assurance of the correctness, which automated methods often cannot: due to their complexity, bugs in such automated verification tools are likely, and thus the risk of erroneously verifying a flawed protocol is nonnegligible. There are a few works that try to combine the advantages from both ends of the spectrum: a high degree of automation and assurance. We present here a first step toward achieving this for a more challenging class of protocols, namely those that work with a mutable long-term state. To our knowledge, this is the first approach that achieves fully automated verification of stateful protocols in an LCF-style theorem prover. The approach also includes a simple user-friendly transaction-based protocol specification language embedded into Isabelle, and can also leverage a number of existing results, such as the soundness of a typed model.

Keywords

formal verification theorem proving security protocols

1. Introduction

There are at least three reasons why it is desirable to perform proofs of security in a proof assistant such as Isabelle/HOL or Rocq. First, it gives us an overwhelming assurance that the proof of security is actually a proof and not just the result of a bug in a complex verification tool. This is because the basic idea of an LCF-style theorem prover is to have an abstract datatype theorem so that new theorems can only be constructed through functions that correspond to accepted proof rules; thus implementing just this data type correctly prevents us from ever accepting a wrong proof as a theorem, no matter what complex machinery we build for automatically finding proofs. Second, a human may have an insight into how to easily prove a particular statement where a “stupid” verification algorithm may run into a complex check or even be infeasible. Third, the language of a proof assistant can formalize all accepted mathematics, so there is no narrow limit on what aspects of a system we can formalize. For instance, we have proved in Isabelle/HOL a compositionality result¹ for our protocol model: given a set of protocols for which we have proved security and that meet a number of requirements, then also their composition is correct. Since also the said requirements are proved in Isabelle, we arrive at a full security proof of the entire system checked by Isabelle. A result like this is beyond the scope of any standard verification tool. Note also that as part of the composition, some of the component protocols may be proved secure by different methods or even automatically.

Paulson² and Bella³ developed a protocol model in Isabelle and performed several security proofs in this model, for example, Paulson.⁴ That the proof of a single protocol (for which even some automated security proofs exist) is worth a publication, underlines how demanding it is to conduct proofs in a proof assistant. This raised the question of how one can automatically generate machine-checkable proofs. Goubault-Larrecq⁵ shows how one can verify Horn-clause based descriptions (e.g., in ProVerif⁶ internally) by finding a (finite) model for it that can easily be machine-checked. Scyther-proof⁷ produces Isabelle proofs for the backward search-based tool Scyther.⁸

A drawback of these approaches so far is that they only apply to Alice-and-Bob style protocols where there is no relation between several sessions. When we consider, however, any system that maintains a mutable long-term state, for example, a security token or a server that maintains a simple database, we hit the limits of several tools for infinite sessions such as Scyther. For instance, ProVerif is based on an abstract interpretation that basically abstracts away from states (and time). To overcome these limitations, several amendments to the abstraction were suggested, such as set-based abstraction,⁹ which our approach is based on, StatVerif¹⁰ and GSVerif,¹¹ and many of these ideas are now incorporated into ProVerif.

Moreover, there is also a tool that went a completely different way: Tamarin¹² (which also is not limited to protocols without long-term state) is actually inspired by Scyther-proof and has the flavor of a proof assistant environment itself, namely combining partial automation with interactive proofs, that is, supplying the right lemmas to show. Interestingly, there is no connection to Isabelle or other LCF-style theorem provers, while one may intuitively expect that this should be easily possible. The reason seems to be that Tamarin combines several specialized automated methods, especially for term algebraic reasoning, that would be quite difficult to “translate” into Isabelle/HOL—at least the authors of this paper do not see an easy way to make such a connection. In fact, if it were possible for a large class of stateful protocols, the combination of overwhelming assurance of proofs and a high degree of automation would be extremely desirable.

The goal of this work is to achieve exactly this combination for a well-defined fragment of stateful protocols. We are here using as a foundation the Isabelle/HOL formalization and protocol model by Hess et al.¹³ There are several reasons for this choice. First, the proof technique we present in this paper works only in a restricted typed model. Fortunately, that formalization ships with a typing result,¹⁴ namely an Isabelle theorem that says: if a protocol is secure in this typed model, then it is also secure in the full model without the typing restriction—as long as the protocol in question satisfies a number of basic requirements. Thus, we get fully automated Isabelle proofs for most protocols even without a typing restriction.

Second, as described already in Hess et al.,¹ building on this protocol model has allowed us to seamlessly integrate the PSPSP tool with the compositional reasoning results: a user can specify multiple protocols in PSPSP and give annotations for their composition. The PSPSP tool can then automatically check the requirements for the composition, automatically verify each component individually, and obtain a proof of the composed system entirely verified by Isabelle/HOL from beginning to end.

Third, related to that, one may of course prove only some components of a composition automatically with PSPSP and prove other components manually when they do not fall into the scope of what PSPSP can support. Also, one may integrate manual reasoning with automated PSPSP analysis: when the runtime of automated analysis is high, a human prover may have an idea to prove some aspect more easily avoiding, for example, some lengthy enumerations.

The automated proof technique we employ in PSPSP is based on the set-based abstraction approach of Mödersheim and Bruni¹⁵ and Bruni et al.¹⁶ The basic idea is that we represent the long-term state of a protocol by a number of sets; the protocol rules specify how protocol participants shall insert elements into a set, remove them from a set, and check for membership or nonmembership. (The intruder may also be given access to some sets.) Based on this, we follow an abstract interpretation approach that identifies those elements that have the same membership status in all sets and compute a fixed point, more precisely a representation of all messages that the intruder can ever know after any trace of the protocol (including the set membership status of elements that occur in these messages). One may wonder if considering just intruder-known messages limits the approach to secrecy goals, but thanks to sets, a wide range of trace-based properties can be expressed by reduction to the secrecy of a special constant $a t t a c k$ . (We cannot, however, handle privacy-type properties in this way.)

We thus check if the fixed point contains the $a t t a c k$ constant, and if so, we can abort the attempt to prove the protocol correct. This may also happen for a secure protocol as the abstraction entails an overapproximation. However, vice versa, if $a t t a c k$ is not in the fixed point, then the protocol is secure—if the fixed point is indeed a sound representation of the messages the intruder can ever know. The proof we perform in Isabelle now is thus basically to show that the fixed point is closed under every protocol rule: given any trace where the intruder knows only messages covered by the fixed point, then every extension by one protocol step reveals only messages also covered by the fixed point.

Contributions

Our main contribution is the formalization in Isabelle of the abstract interpretation approach for stateful protocols, as the PSPSP tool. In a nutshell, we have implemented in Isabelle the computation of the abstract fixed point—the proof idea, so to speak—and how Isabelle can convince herself that this fixed point covers everything that can happen in the concrete protocol. The Isabelle security proof that one obtains consists of two main parts: first, we have a number of protocol-independent theorems that we have proved in Isabelle once and for all, and second, for every protocol and fixed point, we have a number of checks that Isabelle can directly execute to establish the correctness of the given protocol. The entire protocol-independent formalization consists of more than 25,000 lines of Isabelle code (definitions, theorems, and proofs).

A second contribution is the development and integration into Isabelle of a simple protocol specification language for stateful protocols that is based on a notion of atomic transactions: in a transaction, an entity may receive a message, consult its long-term database, make changes to the database, and finally send out a reply. This language is more high-level than, for instance, multiset rewriting while directly defining a state-transition system. The language additionally allows the specification of analysis rules, which are rules that express how the intruder can extract knowledge from received messages built using cryptographic functions.

New contributions in this journal paper

The aforementioned contributions were also part of the conference version of the present paper.¹⁷ In the present journal version, we additionally have a number of new contributions and improvements. First, we have improved the verification method itself. We have devised a novel method for checking the fixed point coverage that significantly improves the runtime for two of our examples. We have also improved the check that the fixed point is analyzed, that is, covers also the knowledge that the intruder can gain by applying the analysis rules.

Second, we have improved the user experience of the tool, for example, by better error messages and support for understanding attacks. A trace of derivation steps for the $a t t a c k$ constant can be of great help: either this is a true attack and one can strengthen the protocol to prevent the attack, or it is a false positive induced by the over-approximation, and this may give a hint how to refine the model of the protocol. Our tool can now calculate such traces and present them to the user.

Third, we have two improvements on the semantic level of PSPSP. One improvement on the semantic level of PSPSP is that we have a soundness proof for the transformation that the tool is doing. The abstract interpretation approach requires that all values be sent out in the network as part of some message. However, our syntax for transactions does not enforce this, because it is reasonable to have a transaction that inserts a value in a set/database without sending it out as part of some message. Our tool solves this by a transformation that for every newly generated value $v$ in a transaction sends out a special message $o c c u r s (v)$ and modifies each transaction to receive $o c c u r s (v)$ for every nonfresh value $v$ . The tool includes this transformation, so the modelers do not have to make this encoding themselves. Now we have proved the soundness of this transformation. Another improvement concerns the definition of the semantics of transactions. While it is defined via symbolic traces of unbounded length (which is particularly practical for relative soundness results such as typing and compositionality), we have also proved the equivalence with a more standard ground semantics.

Fourth, we have a major new case study from working with the Danish company Logos. In this case study, we verify a protocol that the company is using for a travel card solution. The verification with PSPSP revealed a flaw in the protocol. After repairing the flaw, we were able to prove the security of the fixed protocol using PSPSP.

The complete formalization is available at the Archive of Formal Proofs (AFP) as the entry titled Automated Stateful Protocol Verification:¹⁸ https://www.isa-afp.org/entries/Automated_Stateful_Protocol_Verification.html The latest development version and related works can be found at the following webpage: https://people.compute.dtu.dk/samo/pspsp.html

The rest of this paper is organized as follows: Section 2 introduces preliminaries, Section 3 defines the protocol model, Section 4 explains the set-based abstraction approach, Section 5 introduces the protocol checks with optimizations introduced in Section 6, Section 7 presents and reports on the results of a number of experiments applying our approach to a selection of protocols, Section 8 gives a short demonstration of PSPSP from the user’s perspective (and discusses the application of the compositionality result¹), Section 9 presents and reports on a case study where we apply PSPSP to a protocol by the Danish company Logos and finally Section 10 is the conclusion where we also discuss related work.

2. Preliminaries

2.1. Terms and substitutions

We model terms over a countable set $Σ$ of symbols (also called function symbols or operators) and a countable set $V$ of variables disjoint from $Σ$ . Each symbol in $Σ$ has an associated arity, and we denote by $Σ^{n}$ the symbols of $Σ$ of arity $n$ . A term built from $S \subseteq Σ$ and $X \subseteq V$ is then either a variable $x \in X$ or a composed term of the form $f (t_{1}, \dots, t_{n}),$ where each $t_{i}$ is a term built from $S$ and $X$ , and $f \in S^{n}$ . The set of terms built from $S$ and $X$ is denoted by $T (S, X)$ . Arbitrary terms $t$ usually range over $T (Σ, V)$ , unless stated otherwise. By $s u b t e r m s (t)$ we denote the set of subterms of $t$ .

The set of constants $C$ is defined as the symbols with arity zero: $C \equiv Σ^{0}$ . It contains the following disjoint subsets:

The countable set $V$ of concrete values (or just values).

The finite set $A$ of abstract values.

The finite set $E$ of enumeration constants.

The finite set $S$ of database constants. [The databases that they refer to are simply sets of messages, and we therefore often refer to them simply as “sets” in this paper.]

And a special constant $a t t a c k$ .

Terms represent the messages sent during the run of a protocol, and the concrete values are atomic parts of these messages that are generated during the execution of the protocol, such as public keys, nonces, shared keys, and other data. The abstract values are then abstractions of the concrete values in the abstract interpretation approach that we are using. We elaborate on these in Section 4 and choose there a specific set for $A$ that suits the concrete abstract interpretation approach we are using.

The analyst, that is, the author of a protocol specification, may freely choose $E$ and $S$ as well as any number of function symbols $F$ with their arities (disjoint from the above subsets) which represent constructors and cryptographic functions used to build the messages.

Example 1
Consider a protocol with two users $a$ and $b$ , where each user $a$ has its own keyring $r i n g (a)$ , and the server maintains databases of the currently valid keys $v a l i d (a)$ and revoked keys $r e v o k e d (a)$ for $a$ . For such a protocol we define $E = {a, b}$ and $S = {r i n g (a), v a l i d (a), r e v o k e d (a) ∣ a \in E}$ .

We regard all elements of $S$ as constants, despite the function notation, which is just to ease specification. This work is currently limited to finite enumerations and finite sets, as handling infinite domains would require substantial complications of the approach (e.g., a symbolic representation or a small system result).

Arbitrary constants are usually denoted by $a$ , $b$ , $c$ , and $d$ , whereas arbitrary variables are denoted by $x$ , $y$ , and $z$ . By $\bar{x}$ , we denote a finite list $x_{1}, \dots, x_{n}$ of variables.

We furthermore partition $Σ$ into the public symbols (those symbols that are available to the intruder) and the private symbols (those that are not). We denote by $Σ_{p u b}$ and $Σ_{p r i v}$ the set of public and private symbols, respectively. By $C_{p u b}$ and $C_{p r i v}$ , we then denote the sets of public and private constants, respectively. The constant $a t t a c k$ , the values $V$ , the abstract values $A$ , and the database constants $S$ are all private.

The set of variables of a term $t$ is denoted by $f v (t)$ , and we say that $t$ is ground iff $f v (t) = \emptyset$ . Both definitions are extended to sets of terms as expected.

A substitution is a mapping from variables $V$ to terms. The substitution domain (or just domain) $d o m (θ)$ of a substitution $θ$ is defined as the set of those variables that are not mapped to themselves by $θ$ : $d o m (θ) \equiv {x \in V ∣ θ (x) \neq x}$ . The substitution range (or just range) $r a n (θ)$ of $θ$ is the image of the domain of $θ$ under $θ$ : $r a n (θ) \equiv θ (d o m (θ))$ . For finite substitutions, we use the notation $[x_{1} \mapsto t_{1}, \dots, x_{n} \mapsto t_{n}]$ to denote the substitution with domain ${x_{1}, \dots, x_{n}}$ and range ${t_{1}, \dots, t_{n}}$ that sends each $x_{i}$ to $t_{i}$ . Substitutions are extended to composed terms homomorphically as expected. A substitution $θ$ should be applied to a term $t$ only when $f v (t) \subseteq d o m (θ)$ . A substitution $δ$ is injective iff $δ (x) = δ (y)$ implies $x = y$ for all $x, y \in d o m (δ)$ . An interpretation is a substitution $I$ such that $d o m (I) = V$ and $r a n (I)$ is ground. A variable renaming $ρ$ is an injective substitution such that $r a n (ρ) \subseteq V$ . An abstraction substitution is a substitution $δ$ such that $r a n (δ) \subseteq A$ .
2.2. The intruder model

We employ the intruder model from Hess et al.,¹³ which is in the style of Dolev and Yao: the intruder controls the communication medium and can encrypt and decrypt with known keys, but the intruder cannot break cryptography. More formally, we define that the intruder can derive a message $t$ from a set of known messages $M$ (the intruder knowledge, or just knowledge), written $M ⊢ t$ , as the least relation closed under the following rules:

where $A n a (t) = (K, R)$ is a function that maps a term $t$ to a pair of sets of terms $K$ and $R$ . We also define a restricted variant $⊢_{c}$ of $⊢$ as the least relation closed under the $(A x i o m)$ and $(C o m p o s e)$ rules only.

The $(A x i o m)$ rule simply expresses that all messages directly known to the intruder are derivable, the $(C o m p o s e)$ rule closes the derivable terms under the application of public function symbols such as encryption or public constants (when $f \in Σ_{p u b}^{0} = C_{p u b}$ ). The $(D e c o m p o s e)$ rule represents decomposition operations: $A n a (t) = (K, R)$ means that $t$ is a term that can be analyzed, provided that the intruder knows all the “keys” in the set $K$ , and he will then obtain the “results” in $R$ . This gives us a general way to deal with typical constructor/destructor theories without needing to work with algebraic equations and rewriting. We may also write $K e y s (t)$ and $R e s u l t (t)$ to denote the set of keys, respectively, results from analyzing $t$ , that is, $A n a (t) = (K e y s (t), R e s u l t (t))$ .

Example 2
To model asymmetric encryption and signatures, we first fix two public $c r y p t, s i g n \in F^{2}$ and one private $i n v \in F^{1}$ function symbols. The term $c r y p t (k, m)$ then denotes the message $m$ encrypted with a public key $k$ , and $s i g n (i n v (k), m)$ denotes $m$ signed with the private key $i n v (k)$ of $k$ . To obtain a message $m$ encrypted with a public key $k$ , the intruder must produce $i n v (k)$ . Formally, we define the analysis rule ${A n a}_{c r y p t} (x_{1}, x_{2}) = ({i n v (x_{1})}, {x_{2}})$ . For signatures, we define the rule ${A n a}_{s i g n} (x_{1}, x_{2}) = (\emptyset, {x_{2}})$ modeling that the intruder can open any signature that he knows. We also model a transparent pairing function by fixing $p a i r \in Σ^{2}$ and defining the rule ${A n a}_{p a i r} (x_{1}, x_{2}) = (\emptyset, {x_{1}, x_{2}})$ .

Note that we have in this example used a simple notation for describing $A n a (t)$ for an arbitrary term $t$ : each rule ${A n a}_{f} (x_{1}, \dots, x_{n}) = (K, R)$ defines $A n a$ for a constructor $f \in F^{n}$ . Here $x_{i}$ are distinct variable symbols, and $K$ and $R$ are sets of terms such that $R \subseteq {x_{1}, \dots, x_{n}}$ and $K \subseteq T (F, {x_{1}, \dots, x_{n}})$ . Note that for each constructor $f$ , we have at most one analysis rule. For those constructors $f$ that have such a rule we define for each term $f (t_{1}, \dots, t_{n})$ the function $A n a$ as $A n a (f (t_{1}, \dots, t_{n})) \equiv {A n a}_{f} (t_{1}, \dots, t_{n})$ and for all constructors $g$ without an analysis rule we just have $A n a (g (t_{1}, \dots, t_{n})) \equiv (\emptyset, \emptyset)$ . (An example for the latter is a hash function: the intruder cannot obtain information from a hash value.)

The reason for this convention is that the formalization of Hess et al.¹³ requires that the $A n a$ function satisfies certain conditions, most notably that it is invariant under substitutions. [One may wonder why we do not allow for analysis rules of the form ${A n a}_{f} (t_{1}, \dots, t_{n}) = (K, R)$ , where the $t_{i}$ are arbitrary terms instead of just variables. Because of the substitution invariance requirement from Hess et al.¹³ on $A n a$ , such analysis rules would not lead to more expressive $A n a$ functions.] Without going into detail, our notation of the $A n a$ rules allows for an automated proof that all these requirements are satisfied. Thus, this allows the user to specify an arbitrary constructor/destructor theory with these $A n a$ rules without having to prove anything manually.
2.3. Typed model

PSPSP works in a typed model. That means every variable has an intended type, and the intruder can send only well-typed messages. Many protocol verification methods^2–4,19,20 rely on such a typed model since it simplifies the protocol verification problem. There exist many typing results^14,21–25 that show that a restriction to a typed model is sound for large classes of protocols: for a protocol falling in such a class, it is without loss of attacks to restrict the intruder to well-typed messages. Hess and Mödersheim¹⁴ is such a result that is part of the Isabelle formalization we employ. Since this result has itself been proved in Isabelle, to obtain the Isabelle proof that a protocol is secure in the unrestricted model, it is sufficient to have a proof that the protocol is secure in the typed model (e.g., automatically using PSPSP) and that the protocol satisfies type-flaw resistance, that is, the requirements of the typing result. We have automated the Isabelle proof of type-flaw resistance for the protocol specification language we present. Note that PSPSP only assumes a typed model, and the typing result here is just one way to discharge this assumption; there may be other ways to prove it, or one may leave it as an assumption. As PSPSP is not conceptually tied to the typing result, we give here only a brief summary of the result of Hess and Mödersheim.¹⁴

The typed model is parameterized over a typing function $Γ$ and a finite set of atomic types $T_{a}$ satisfying the following:

$Γ (x) \in T (Σ ∖ C, T_{a})$ for $x \in V$ (where $T_{a}$ here acts like a set of “variables”).

$Γ (c) \in T_{a}$ for $c \in C$ .

$Γ (f (t_{1}, \dots, t_{n})) = f (Γ (t_{1}), \dots, Γ (t_{n}))$ for $f \in Σ ∖ C$ .

A substitution

θ

is then said to be well-typed iff

Γ (θ (x)) = Γ (x)

for all variables

x

For instance, we may have a transaction with a step $r e c e i v e (X)$ , where $Γ (X) = h (N o n c e)$ . Note that in general the recipient would be unable to check if the received message is really of this form (e.g., the intruder could send them any value); the typing result shows that (if the protocol satisfies type-flaw resistance), if there is an attack, then there is a well-typed attack, and it is thus sound to replace the above step by $r e c e i v e (h (N))$ for a new variable $N$ of type $N o n c e$ (and replace all occurrences of $X$ with $h (N)$ in the rule). This does not mean that the recipient would learn $N$ , but only that the term can only be of the form $h (N)$ for some $N$ of type $N o n c e$ .

For such a typing result, one considers a set of submessage patterns ( $S M P$ ) that contains the messages of the protocol description and is closed under well-typed instances, subterms, and key terms that can occur during analysis steps. For instance with the operators in Example 2, if $c r y p t (k, m) \in S M P$ , then also $k, m, i n v (k) \in S M P$ . The main requirement of type-flaw resistance is: if two terms $s, t \in S M P ∖ V$ have a unifier, then $Γ (s) = Γ (t)$ .

For example, if $S M P$ contains messages $s = s c r y p t (X, p a i r (A, Y))$ and $t = s c r y p t (X^{'}, Z)$ for $Γ (X) = Γ (X^{'}) = Γ (Y) = Γ (Z) = v a l u e$ and $Γ (A) = e n u m$ , then $s, t$ have a unifier, but $Γ (s) \neq Γ (t)$ , so this violates type-flaw resistance. There is a cheap way to make basically any protocol type-flaw resistant: instead of pairs, consider formats, that is, public functions that represent a particular way of structuring clear-text messages (e.g., XML), one format for each type of message. In the example, it can be a binary format $f_{1}$ and a unary format $f_{2}$ , and using them for the different types of encrypted messages: $s = s c r y p t (X, f_{1} (A, Y))$ and $t = s c r y p t (X^{'}, f_{2} (Z))$ . Now $s$ and $t$ are no longer unifiable, since they use different formats, and it is just following prudent engineering principles that one should not encrypt raw data such as nonces, but add a few bits identifying what type of data it is.

As mentioned, we have now automated this check for type-flaw resistance; of course, $S M P$ is infinite, so we cannot directly compute it, but it is rather straightforward to compute the property symbolically. (One can avoid concrete constants and does not need to consider variants of terms that are equal modulo renaming of variables.)

The typing result for type-flaw resistant protocols is proved in Hess and Mödersheim¹⁴ by considering a symbolic search technique called the lazy intruder. The key idea is that the only way that the lazy intruder instantiates variables is by a substitution $σ$ that is the most general unifier of two nonvariable terms. For a type-flaw resistant protocol, the considered terms are always within $S M P$ , and the unifier between two nonvariable terms of $S M P$ is thus necessarily well-typed (thus, applying the unifier to other terms in the search keeps them also in $S M P$ ). Because the technique is sound and complete, it will find an attack if there is one, and this attack is well-typed for a type-flaw-resistant protocol.

In fact, like Hess and Mödersheim,¹⁴ we consider here stateful protocols where a message $m$ can be inserted, deleted, and checked for containment/noncontainment in a set $s$ . The requirement here is the following: if we have in the protocol a set operation with message $m$ and set $s$ and another set operation with message $m^{'}$ and set $s^{'}$ and if the pairs $(m, s)$ and $(m^{'}, s^{'})$ have a unifier, then they must be of the same type. For instance, we cannot put messages of different types into the same set.

In this paper, we use as atomic types only $T_{a} = {v a l u e, e n u m, s e t t y p e, a t t a c k t y p e}$ , and the elements of $A \cup V$ have type $v a l u e$ , the elements of $E$ have type $e n u m$ , the elements of $S$ have type $s e t t y p e$ and $a t t a c k$ has type $a t t a c k t y p e$ .

As a consequence of the typing result, when we have a variable $X$ of a composed type $Γ (X) = f (τ_{1}, \dots, τ_{n})$ , it is sound to replace it by the term $f (X_{1}, \dots, X_{n}),$ where $X_{i}$ are fresh variables of type $τ_{i}$ . Repeatedly applying this, it is thus not a restriction to have variables of only atomic types.

3. Transactions

The Isabelle protocol model of Hess et al.¹³ consists of a number of transactions (also called rules) specifying the behavior of the participants. A transaction consists of any combination of the following: input messages to receive, checks on the sets, modifications of the sets, and output messages to send. A transaction can only be executed atomically, that is, it can only fire when input messages are present, such that the checks are satisfied, and then they produce all changes and the output messages in one state transition. Instead of defining a ground state transition system,¹³ consider building symbolic traces as sequences of transactions with their variables renamed apart, and with any instantiation of the variables that satisfies the checks and the intruder model in the sense that the intruder can produce every input message from previous output messages. (Transactions can also describe additional abilities of the intruder, such as reading a set.) Security goals are formulated by transactions that check for a situation we consider as a successful attack, and then reveal the special constant $a t t a c k$ to the intruder. Thus, a protocol is safe if no symbolic constraint with the intruder finally sending $a t t a c k$ has a satisfying interpretation. Note that the length of symbolic traces is finite but unbounded (i.e., an unbounded session model), and that the number of enumeration constants and databases currently supported is arbitrary but fixed in the specification.

For the convenience of an automated verification tool, we have defined a small language called trac based on transactions with a bit of syntactic sugar, and this language is directly embedded into Isabelle. It is a simple text-based format directly accepted by our tool—see Section 8. To begin with, we introduce this language using a keyserver example adapted from Hess et al.¹³ that we also use as a running example for the remainder of this paper.

3.1. A keyserver protocol

Before we proceed with the formal definitions, we illustrate our protocol model through the keyserver example. The protocol specifies $E = {a, b, i}$ and uses the specification of $S$ from Example 1 and of $F$ from Example 2. We consider users $a$ and $b$ as honest users and $i$ as dishonest. In the specification, we will use sets $u s e r = E$ , $h o n e s t = {a, b}$ , and $d i s h o n e s t = {i}$ as types in the parameters of the transaction we specify. In the keyserver example, users can register public keys at a trusted keyserver, and these keys can later be revoked. Each user $U$ has an associated keyring $r i n g (U)$ with which it keeps track of its keys. (The elements of $r i n g (U)$ are actually public keys; we implicitly assume that the user $U$ knows the corresponding private key.)

First, we model a mechanism $o u t O f B a n d$ by which a user $U$ can register a new key $P K$ at the keyserver out-of-band, for example, by physically visiting the keyserver. The user $U$ first constructs a fresh public key $P K$ and inserts $P K$ into its keyring $r i n g (U)$ . We model that the keyserver—in the same transaction—learns the key and adds it to its database of valid keys for user $U$ , that is, into a set $v a l i d (U)$ . Finally, $P K$ is published: Note that there is no built-in notion of set ownership, or who exactly is performing an action: we just specify with such transactions what can happen. The intuition is that $r i n g (U)$ is a set of public keys controlled by $U$ (and $U$ has the corresponding private key of each) while $v a l i d (U)$ is controlled by the server (who is not even given a name here). Putting it into a single transaction model that this is something happening in collaboration between a user and a server.

Next, we model a key update mechanism that allows for registering a new key while simultaneously revoking an old one. We model this as two transactions, one for the user and one for the server, since here we model a scenario where the user and server communicate via an asynchronous network controlled by the intruder. To initiate the key revocation process, the user $U$ first picks and removes a key $P K$ from its keyring to later revoke, then freshly generates a new key $N P K$ and stores it in its keyring. (Again, the corresponding private key $i n v (N P K)$ is known to $U$ , but this is not explicitly described.) As a final step, the user signs the new key with the private key $i n v (P K)$ of the old key and sends this signature to the server by transmitting it over the network: The check $P K i n r i n g (U)$ represents here a nondeterministic choice of an element of $r i n g (U)$ . (Observe that a user can register any number of keys with the $o u t O f B a n d$ transaction.) We declare $P K$ as a variable of type $v a l u e$ , because $P K$ is not freshly generated here; all freshly generated elements, such as $N P K$ here, are automatically of type $v a l u e$ .

When the server receives the signed message, it checks that $P K$ is indeed a valid key, that $N P K$ has not been registered earlier, and then revokes $P K$ and registers $N P K$ . To keep track of revoked keys, the server maintains another database $r e v o k e d (U)$ containing the revoked keys of $U$ : As a last action, the old private key $i n v (P K)$ is revealed. This is, of course, not what one would do in a reasonable implementation, but it allows us to prove that the protocol is correct even if the intruder obtains all private keys to revoked public keys. (This could also be separated into a rule that just leaks private keys of revoked keys.)

Actions of the form $x n o t i n s (_)$ for $s \in Σ^{n}$ are syntactic sugar for the sequence of actions $x n o t i n s (a)$ for each $a \in E$ .

Finally, we define that there is an attack if the intruder learns a valid key of an honest user. This, again, can be modeled as a sequence of actions in which we check if the conditions for an attack hold, and, if so, transmit the constant $a t t a c k$ that acts as a signal for goal violations. Recall that $h o n e s t$ is a subset of $u s e r$ that contains only the honest agents. Then we define: The last action $a t t a c k$ is just syntactic sugar for $s e n d a t t a c k$ .

3.2. Protocol model

The keyserver protocol that we just defined consists of transactions (also called rules) that we now formally define. To keep the formal definitions simple, we omit the variable declarations and the syntactic sugar employed in our protocol specification language. Thus, only $v a l u e$ -typed variables remain in transactions since the enumeration variables are resolved as syntactic sugar.

A transaction $T$ is then of the form $T = S_{r} \cdot S_{c} \cdot F \cdot S_{u} \cdot S_{s},$ where the $S_{i}$ are strands built from the following grammar:

\begin{aligned} S_{r} & : : = r e c e i v e t_{1}, \dots, t_{n} \cdot S_{r} ∣ 0, \\ S_{c} & : : = x i n s \cdot S_{c} ∣ x n o t i n s \cdot S_{c} ∣ x ≐̸ x^{'} \cdot S_{c} ∣ 0, \\ F & : : = n e w x \cdot F ∣ 0, \\ S_{u} & : : = i n s e r t x s \cdot S_{u} ∣ d e l e t e x s \cdot S_{u} ∣ 0, \\ S_{s} & : : = s e n d u_{1}, \dots, u_{n} \cdot S_{s} ∣ 0, \end{aligned}

where

x, x^{'} \in V_{v a l u e}

s \in S

t_{i} \in T (E \cup F, V_{v a l u e})

u_{i} \in T (E \cup F, V_{v a l u e}) \cup {a t t a c k}

, and where

0

denotes the empty strand. We remark that only values can be inserted in the sets, which is why we require

x, x^{'} \in V_{v a l u e}

. This is needed for the abstract interpretation approach we present in Section 4.

The function $f v$ is extended to transactions by letting it collect all variables occurring in the strands of the transaction, and for a transaction $T = S_{r} \cdot S_{c} \cdot F \cdot S_{u} \cdot S_{s}$ we define $f r e s h (T) \equiv f v (F)$ (i.e., $x \in f r e s h (T)$ iff $n e w x$ occurs in $T$ ).

Protocols are defined as finite sets of such transactions $P = {T_{1}, \dots, T_{n}}$ . Their semantics is defined in terms of a ground transition system in which each configuration is of the form $(M, D, C)$ , where $M$ is the intruder knowledge (the messages sent so far), $D$ is a set of pairs representing the current state of the databases (e.g., $(k, s) \in D$ iff $k$ is an element of the database $s$ ) and $C$ keeps track of the constants that have been used already and thus cannot be considered fresh. For a configuration and a transaction, we can check if the transaction is executable from that configuration, and if so, then there is a transition to the new configuration that results from executing the transaction. When executing a transaction, variables $x$ occurring in $n e w x$ actions will be instantiated with fresh values. To ensure that these values are indeed fresh, they must not be in $C$ already. This instantiation takes care of the $n e w x$ actions, which are then no longer needed. The instantiation also requires a slightly more flexible syntax compared to the transaction syntax, to allow for actions such as $i n s e r t t s$ , where $t \notin V$ . We introduce a syntax that accounts for this, called constraints or traces:

\begin{aligned} A : : = & s e n d t_{1}, \dots, t_{n} \cdot A ∣ r e c e i v e t_{1}, \dots, t_{n} \cdot A ∣ t ≐̸ t^{'} \cdot A ∣ i n s e r t t t^{'} \cdot A ∣ d e l e t e t t^{'} \cdot A ∣ \\ t i n t^{'} \cdot A ∣ t n o t i n t^{'} \cdot A ∣ 0, \end{aligned}

where

t, t^{'} \in T (Σ, V)

and

0

is the empty constraint. Note also that in contrast to transactions, constraints are seen from the intruder’s point of view, in the sense that the directions of transmitted messages are swapped (so

r e c e i v e

s become

s e n d

s and vice-versa).

For the semantics of constraints, we define a relation $I ⊨_{D}^{M} A,$ where $A$ is a constraint, $M$ is the intruder knowledge, $D$ is a set of pairs representing the current state of the databases, and $I$ is an interpretation:

\begin{array}{lcl} I ⊨_{D}^{M} 0 & iff & t r u e, \\ I ⊨_{D}^{M} s e n d t_{1}, \dots, t_{n} \cdot A & iff & M ⊢ I (t_{i}), for all i \in {1, \dots, n}, and I ⊨_{D}^{M} A, \\ I ⊨_{D}^{M} r e c e i v e t_{1}, \dots, t_{n} \cdot A & iff & I ⊨_{D}^{M \cup {I (t_{1}), \dots, I (t_{n})}} A, \\ I ⊨_{D}^{M} i n s e r t t s \cdot A & iff & I ⊨_{D \cup {I ((t, s))}}^{M} A, \\ I ⊨_{D}^{M} d e l e t e t s \cdot A & iff & I ⊨_{D ∖ {I ((t, s))}}^{M} A, \\ I ⊨_{D}^{M} t ≐̸ t^{'} \cdot A & iff & I (t) \neq I (t^{'}) and I ⊨_{D}^{M} A, \\ I ⊨_{D}^{M} t i n s \cdot A & iff & I ((t, s)) \in D and I ⊨_{D}^{M} A, \\ I ⊨_{D}^{M} t n o t i n s \cdot A & iff & I ((t, s)) \notin D and I ⊨_{D}^{M} A . \end{array}

We say that

I

is a model of $A$ , written

I ⊨ A

, iff

I ⊨_{\emptyset}^{\emptyset} A

. We may also apply substitutions

θ

to constraints

A

, written

θ (A)

, by extending the definition of substitution application appropriately. The function

f v

is also extended to constraints.

We define what an intruder learns when a constraint $A$ is executed: $i k (A) = {t_{i} | 1 \leq i \leq n,$ $r e c e i v e t_{1}, \dots, t_{n} \in A}$ . We also define the database $d b (A, I, D)$ , which is the update of the database $D$ after the execution of the constraint $A$ from database $D$ under interpretation $I$ :

\begin{array}{rcl} d b (0, I, D) & = & D, \\ d b (t \cdot S, I, D) & = & {\begin{cases} d b (S, I, D \cup {(I (t), I (s))}) & if t = i n s e r t t s, \\ d b (S, I, D ∖ {(I (t), I (s))}) & if t = d e l e t e t s, \\ d b (S, I, D) & otherwise, \end{cases} \end{array}

With this in place, we define a transition relation

\Rightarrow_{P}

for protocols

P

in which states are configurations and the initial state is the empty configuration

(\emptyset, \emptyset, \emptyset)

. First, we define the dual of a constraint

A

, written

d u a l (A)

, as “swapping” the direction of the sent and received messages of

A

d u a l (0) = 0

d u a l (r e c e i v e t \cdot A) = s e n d t \cdot d u a l (A)

d u a l (s e n d t \cdot A) = r e c e i v e t \cdot d u a l (A)

, and

d u a l (a \cdot A) = a \cdot d u a l (A)

otherwise. The transition

(M, D, C) \Rightarrow_{P} (M \cup I (i k (A)), d b (A, I, D), C \cup (s u b t e r m s (A) \cap V))

is then applicable for a transaction

T \in P

if the following conditions are met:

(1)
$T = S_{r} \cdot S_{c} \cdot F \cdot S_{u} \cdot S_{s}$ for some $F$ ,
(2)
$σ$ is an injective substitution mapping $f r e s h (T)$ to fresh values (i.e., $d o m (σ) = f r e s h (T)$ , $r a n (σ) \subseteq V$ , and $r a n (σ) \cap C = \emptyset$ ),
(3)
$A = d u a l (σ (S_{r} \cdot S_{c} \cdot S_{u} \cdot S_{s}))$ , and
(4)
$I ⊨_{D}^{M} A$ .

A configuration $(M, D, C)$ is said to be ground reachable in $P$ iff $(\emptyset, \emptyset, \emptyset) \Rightarrow_{P}^{⋆} (M, D, C)$ where $\Rightarrow_{P}^{⋆}$ denotes the transitive reflexive closure of $\Rightarrow_{P}$ . For any configuration $(M, D, C)$ ground reachable in this transition system, $M$ and $D$ are ground because in each step the substitutions $σ$ and $I$ replace variables with ground terms in the elements added to these sets.

We now define a different semantics for protocols, namely one defined in terms of a symbolic transition system in which a single constraint is built up during transitions, essentially representing a trace of what has happened. We use this system as a basis for our formalization of both typing and compositionality because, for these two aspects, it is convenient to reason about the mentioned single constraint. For typing, it is convenient to reason about the many solutions it may have, and for compositionality, it is convenient to split the constraint into parts that then constitute constraints of the individual protocols. We call the system symbolic because we allow the built constraint to contain variables—this is in contrast to the ground transition system, which picks and applies a new interpretation $I$ in each transition. The symbolic transition system is defined using a transition relation $\Rightarrow_{P}^{∙}$ for protocols $P$ in which states are constraints and the initial state is the empty constraint $0$ . The transition
$A \Rightarrow_{P}^{∙} A \cdot d u a l (ρ (σ (S_{r} \cdot S_{c} \cdot S_{u} \cdot S_{s})))$
is applicable for a transaction $T \in P$ if the following conditions are met: (1)
$T = S_{r} \cdot S_{c} \cdot F \cdot S_{u} \cdot S_{s}$ for some $F$ ,
(2)
$σ$ is an injective substitution mapping $f r e s h (T)$ to fresh values (i.e., $d o m (σ) = f r e s h (T)$ , $r a n (σ) \subseteq V$ , and the elements of $r a n (σ)$ do not occur in $A$ ), and
(3)
$ρ$ is a variable renaming sending the variables of $T$ not in $f r e s h (T)$ to new variables that do not occur in $A$ or $P$ (that is, $d o m (ρ) = f v (T) ∖ f r e s h (T)$ and $(f v (A) \cup f v (P)) \cap r a n (ρ) = \emptyset$ ).

A constraint $A$ is said to be symbolically reachable in $P$ iff $0 \Rightarrow_{P}^{∙ ⋆} A$ where $\Rightarrow_{P}^{∙ ⋆}$ denotes the transitive reflexive closure of $\Rightarrow_{P}^{∙}$ . The protocol then has an attack iff there exists a symbolically reachable and satisfiable constraint where the intruder can produce the attack signal, that is, there exists a symbolically reachable $A$ in $P$ and an interpretation $I$ such that $I ⊨ A \cdot s e n d a t t a c k$ . If $P$ does not have an attack, then $P$ is secure.

We show that the notions of reachability in the two systems correspond to each other:
Theorem 1

$\begin{aligned} {(M, D) ∣ (M, D, C) is ground reachable in P} \\ = {(i k (I (A)), d b (A, I, \emptyset)) ∣ A is symbolically reachable in P and I ⊨ A} \end{aligned}$
[This theorem is called protocol_model_equivalence in the Isabelle formalization and can be found in the Stateful_Protocol_Model.thy theory file.]

For the remainder of the paper, we will focus our attention on the symbolic transition system as justified by the above theorem, and thus by reachable we will mean symbolically reachable.
3.3. Well-formedness

We are going to employ the abstraction-based verification technique from Mödersheim and Bruni¹⁵ in the following to automatically generate security proofs. The technique has a few more requirements in order to work and which we bundle in a notion of well-formedness.

First, if a transaction uses a variable for sending a message or performing a set update, then that variable must either be fresh or have occurred positively in a received message or check. Intuitively, transactions cannot produce a value “out of the blue,” but the value either has to exist before the transaction (in some message or set) or be created by the transaction. Formally, let $T = S_{r} \cdot S_{c} \cdot F \cdot S_{u} \cdot S_{s}$ . Then, we require:

C1:
$f v (S_{u}) \cup f v (S_{s}) \subseteq f v (S_{r}) \cup f v (S_{c}) \cup f r e s h (T)$
C2:
$f r e s h (T) \cap (f v (S_{r}) \cup f v (S_{c})) = \emptyset$
C3:
$f r e s h (T) \subseteq f v (S_{s}) \cup {x | i n s e r t x s \in S_{u}}$
The second condition simply states that values that are freshly generated by a transaction $T$ must neither occur in the received messages nor in the checks of $T$ .

A second concern is whether protocols allow the intruder to actually produce fresh values. That is not ensured in the protocol model we have presented so far, but the intruder being able to produce fresh values is standard in many models of security protocols, and we want it to be the case for our work. Suppose, for example, that a specification contains no transaction that generates any fresh value, but, say, only an attack rule like this: One might naturally expect that said protocol is not secure, but this is only the case if the intruder can actually produce fresh values.

We will therefore require that protocols include transactions that immediately produce and reveal fresh values to the intruder. We denote such transactions as initial-value-producing transactions. If the user does not include an initial-value-producing transaction, then our tool will automatically insert one. If the user does include one, then it is the design choice of the user to define exactly how it should look, as long as it lives up to the definition of being an initial-value-producing transaction. This is, in our opinion, more flexible than strictly enforcing a specific rule, since the user can adapt the rule to the context of a particular model. For instance, in the keyserver example, where values represent public keys, one may define the intruder rule that gives the corresponding private key to the intruder and inserts it into a dedicated set: Thus, we require (and automatically check) that each protocol specification includes an initial-value-producing transaction:
Definition 1
A transaction is an initial-value-producing transaction for a protocol $P$ if it is of the form $n e w x \cdot S_{u} \cdot s e n d t_{1}, \dots, t_{n},$ where $t_{i} = x$ for some $i$ , no other variable than $x$ occurs in $t_{1}, \dots, t_{n}$ and where $S_{u}$ is either $0$ or $i n s e r t x c$ for a set $c$ such that no transaction in $P$ deletes from nor does any check on $c$ .

It is clear that an initial-value-producing transaction is applicable in every state and generates a fresh value.

A third concern is that the abstraction approach that we employ would not work if, for example, an agent freshly creates a value and stores it in a set, but never sends it out as part of a message. This is because the abstraction discards the explicit representation of sets and just keeps the abstracted messages. As an easy workaround, we define a special private unary function symbol $o c c u r s$ and then do a transformation. The transformation augments every rule containing action $n e w x$ with the action $s e n d o c c u r s (x)$ , and also augments every transaction where variable $x$ occurs but is not freshly generated with $r e c e i v e o c c u r s (x)$ . To avoid bothering the user with this, our tool can make this transformation automatically using the following function:
Definition 2
Let $T = S_{r} \cdot S_{c} \cdot F \cdot S_{u} \cdot S_{s}$ be a transaction, let ${y_{1}, \dots, y_{n}}$ be its (possibly empty) set of fresh variables, and let ${x_{1}, \dots, x_{m}}$ be its (possibly empty) set of other free variables.

We define a function $a d d_o c c u r s_m s g s$ that ensures that $o c c u r s$ messages are being received and sent:
$a d d_o c c u r s_m s g s (T) = S_{r}^{'} \cdot S_{c} \cdot F \cdot S_{u} \cdot S_{s}^{'},$
where
$\begin{aligned} S_{r}^{'} = & if {x_{1}, \dots, x_{m}} = \emptyset then S_{r} else r e c e i v e (o c c u r s (x_{1}), \dots, o c c u r s (x_{m})) \cdot S_{r}, \\ S_{s}^{'} = & if {y_{1}, \dots, y_{n}} = \emptyset then S_{s} else s e n d (o c c u r s (y_{1}), \dots, o c c u r s (y_{n})) \cdot S_{s} . \end{aligned}$

Note that the $o c c u r s$ messages are only added during verification. One may wonder if the transformation is sound—after all, there is now the additional requirement that the intruder needs to send $o c c u r s$ messages in order to run the transactions. The transformation is sound, and the argument is essentially that if there was an attack in the original protocol, then the transformed protocol will have a similar attack that simply receives and sends the introduced $o c c u r s$ messages as needed. However, proving the transformation sound involves a challenge that stems from an interaction between the modified protocol and the typing result from Hess and Mödersheim.¹⁴ A requirement of applying the typing result is namely that there are infinitely many public constants of type $v a l u e$ that the intruder can get access to through the Compose rule. [The reason is that one of the main arguments used in the typing result is essentially that for attacks on type-flaw resistant protocols that use ill-typed messages, the intruder might as well have picked well-typed messages. For this to be true for an unbounded number of messages containing terms that should have had an atomic type such as $v a l u e$ , the intruder thus needs to be able to pick enough of such constants, and this is what this requirement ensures.] This is in contrast to the presentation we gave in Section 2, where we defined the type $v a l u e$ to contain only private values (i.e. $V$ ). The public constants of type $v a l u e$ are problematic because the intruder does not have $o c c u r s$ messages for those. Furthermore, one might fear that attacks that used public constants of type $v a l u e$ before the transformation are “blocked” after the transformation because they do not have corresponding $o c c u r s$ messages. As part of the following soundness proof, we will therefore prove that whenever the intruder might have used one of these public constants of type $v a l u e$ , he can instead use private constants of type $v a l u e$ that he obtains by using an initial-value-producing transaction. This is both central to the soundness of the occurs transformation and for us to justify not including public constants of type $v a l u e$ in the model presented in Section 2. We prove the following lemma, which transforms a run $A$ of $P$ relying possibly on public constants into one that relies only on private ones:
Lemma 1
Let $P$ be a protocol that includes an initial-value-producing transaction and which has a well-typed attack $A \cdot a t t a c k$ with model $I$ . Then there exists constraint $B$ and interpretation $J$ such that $B \cdot a t t a c k$ is a well-typed attack on $P$ with model $J$ and such that $J$ maps all $B$ ’s free variables to values from $V$ .
Proof Proof Sketch

The proof is essentially by induction on how $A$ was reached by $\Rightarrow^{∙}$ . Thus, we have to consider an $A$ being extended with a transaction $T = S_{r} \cdot S_{c} \cdot F \cdot S_{u} \cdot S_{s}$ to $A \cdot d u a l (ρ (σ (S_{r} \cdot S_{c} \cdot S_{u} \cdot S_{s})))$ and then show that the corresponding $B$ can similarly be extended in a way that preserves the properties required by the lemma. The substitution $σ$ picked some number $n$ of public constants. In the extension of $B$ , we will apply first an initial-value-producing transaction $n$ times to obtain $n$ values, and then use $T$ , but with a substitution $σ^{'}$ that uses these $n$ values instead of the public constants. The formalized proof is tricky, as it requires us to keep track of which fresh values and variables have been used so far in the induction, and we also need to meticulously update our model $J$ to ensure that it is indeed a model of $B$ . Therefore, in the formal proof, the induction is done in a central step where the property proved is strengthened to account for these aspects.

Theorem 2
Let $P$ be a protocol that includes an initial-value-producing transaction and which has a well-typed attack. Then the protocol ${a d d_o c c u r s_m s g s (T) ∣ T \in P}$ also has a well-typed attack. [This theorem is called add_occurs_msgs_soundness in the Isabelle formalization and can be found in the Stateful_Protocol_Verification.thy theory file.]
Proof Proof Sketch

The proof has essentially three steps: The first step relies on Lemma 1 by obtaining the attack $B$ and model $J$ described by that lemma’s conclusion. The second step inserts in $B$ the sending and receiving of appropriate $o c c u r s$ messages, thus turning it into an attack on ${a d d_o c c u r s_m s g s (T) ∣ T \in P}$ . The third step proves that $J$ is also a model of ${a d d_o c c u r s_m s g s (T) ∣ T \in P}$ .

The final concern to be discussed in this section is a small technical difficulty that arises when a transaction has two variables $x, y$ that could be the same value, that is, that allows for a model $I$ with $I (x) = I (y)$ . This is difficult to handle in the verification since the transaction may require inserting $x$ into a set and deleting $y$ from that very set. To steer clear of this, the paper¹⁵ simply defines the semantics to be injective on variables. [We elaborate on this in Section 5.1 after Definition 8.] For user-friendliness, we do not want to follow this, and rather do the following: for any rule with variables $x$ and $y$ that are not part of a $n e w$ construct, we generate a variant of the rule where we unify $x$ and $y$ , checking whether this yields a consistent transaction, that is, a transaction that avoids logically inconsistent checks such as $x i n r i n g (a)$ followed by $x n o t i n r i n g (a)$ , which will necessarily fail. If so, we add it to the protocol. Then we add the constraint $x ≐̸ y$ to the original rule. We do that until all rules have $x ≐̸ y$ for all pairs of variables that are not freshly generated. For instance, in the keyserver example, we have only one rule to look at: $k e y U p d a t e S e r v e r$ with variables $P K$ and $N P K$ . Since unifying $P K$ and $N P K$ gives an unsatisfiable rule, it is safe to add $P K ≐̸ N P K$ to it.

4. Set-based abstraction

We now come to the core of our approach: for a given protocol, how to automatically verify and generate a security proof that Isabelle can accept. As explained earlier, this is based on an abstract interpretation method called set-based abstraction.^9,15,16 Essentially, the method computes a fixed point which overapproximates the intruder’s accumulated knowledge in any sequence of transactions. While it is relatively easy to formalize the computation of this fixed point in Isabelle, the main work consists of convincing Isabelle that every transaction is covered by the fixed point in the following sense. Given any trace that is represented by the fixed point and in which a transaction is executable, then the resulting trace is covered by the fixed point. Thereby, all traces are covered by the fixed point, and when the attack predicate is not contained in the fixed point, it is not reachable in any trace of the protocol. The core of PSPSP is this coverage check that automatically performs a security proof in Isabelle. The fixed point can thus be regarded as a proof idea that no trace can contain an attack. If there was any mistake in the fixed point computation (or if the abstraction approach were actually unsound), then in the worst case, Isabelle would fail to be convinced by the coverage check.

Recall that in the previous section we formalized a protocol model by reachable constraints $A$ (i.e., a sequence of transactions where variables have been named apart and the send/receive direction has been swapped in order to express it from the intruder’s point of view) with their satisfying interpretations $I ⊨ A$ . Note that $⊨$ is defined via a relation $⊨_{D}^{M}$ , where here $M$ denotes the intruder knowledge (all the messages received so far) and $D$ denotes the state of the sets $S$ (all values inserted into a set that were not deleted so far). Note also that the values that can no longer be considered fresh are the set $C = s u b t e r m s (A) \cap V$ . We can thus characterize the state of the entire system after a number of instantiated transactions by these three items $M$ , $D$ , and $C$ .

Example 3
In our keyserver example, the following trace is possible (after taking a transition of $o u t O f B a n d$ with variables instantiated by $[P K \mapsto {p k}_{1}, U \mapsto a]$ followed by a transition of $k e y U p d a t e U s e r$ with variables instantiated by $[P K \mapsto {p k}_{1}, U \mapsto a, N P K \mapsto {p k}_{2}]$ ):
$\begin{array}{l} i n s e r t {p k}_{1} r i n g (a) \\ i n s e r t {p k}_{1} v a l i d (a) \\ r e c e i v e {p k}_{1} \\ {p k}_{1} i n r i n g (a) \\ d e l e t e {p k}_{1} r i n g (a) \\ i n s e r t {p k}_{2} r i n g (a) \\ r e c e i v e s i g n (i n v ({p k}_{1}), p a i r (a, {p k}_{2})) \end{array}$
Suppose we start in state $M_{0} = \emptyset$ , $D_{0} = \emptyset$ , and $C_{0} = \emptyset$ . After this trace, we have
$\begin{aligned} M = & {{p k}_{1}, s i g n (i n v ({p k}_{1}), p a i r (a, {p k}_{2}))}, \\ D = & {({p k}_{1}, v a l i d (a)), ({p k}_{2}, r i n g (a))}, and \\ C = & {{p k}_{1}, {p k}_{2}} \end{aligned}$

In general, $D$ consists of pairs $(v, s)$ where $v \in V$ is a value and $s \in S$ is a set. The idea of our abstract interpretation is that we stop distinguishing values that are members of the same sets. Let thus $A$ be the powerset of $S$ and define an abstraction function $α_{D}$ from $V$ to $A$ that depends on the current state $D$ : and we extend it to terms and sets of terms as expected. We thus write for the abstract value that corresponds to the subset $A$ of $S$ , for example, if $s_{1}, s_{2} \in S$ then . Remember that $A$ is included in $Σ^{0}$ , so we can build abstract terms that include elements of $A$ as abstract constants. [In fact, in the Isabelle type system, $Σ$ cannot contain both $S$ and subsets of $S$ ; we thus technically define the elements of $A$ as a constructor applied to any subset of $S$ . This is reflected here by the shading to ease presentation.]
Example 4
In the previous example, we have and . Thus .

The key idea is to compute the fixed point of all the abstract messages that the intruder can obtain in any model of any reachable constraint. Note that this fixed point is, in general, infinite, even if $S$ is finite (and thus so is $A$ ), because the intruder can compose arbitrarily complex messages and send them. This is why tools such as those in the literature^9,15,16 do not directly compute the fixed point but represent it by a set of Horn clauses and check using resolution whether $a t t a c k$ is derivable.

However, remember that we can restrict ourselves to the typed model and use the typing result of Hess and Mödersheim¹⁴ to infer the security proof without the typing restriction. All variables that occur in a constraint are of type $v a l u e$ (the parameter variables of the transactions are desugared) and thus, in a typed model, it holds that $I (x) \in V$ for every variable $x$ and well-typed interpretation $I$ . While $V$ is still countably infinite, the abstraction (in any state $D$ ) maps to the finite $A$ . Thus, the fixed point is always finite in a typed model.

There is a subtle point here: even though we limit the variables to well-typed terms, and thus also limit all messages that can ever be sent or received, the Dolev-Yao closure is still infinite, that is, for a (finite) set $M$ of messages there are still infinitely many $t$ such that $M ⊢ t$ . Only finitely many of these $t$ can be sent by the intruder in the typed model, but one may wonder if the entire derivation relation $⊢$ can be limited to “well-typed” terms without losing attacks. Indeed, we define well-typed terms as the set of terms that includes all well-typed instances of sent and received messages in transactions, and that is closed under subterms and $K e y s$ . We have proved in Isabelle that for the intruder to derive any well-typed term, it is sound to also limit the intruder deduction to well-typed terms, so no ill-typed intermediate terms are needed during the derivation. (This is indeed very similar to some lemmas we have proved for parallel compositionality, namely for so-called homogeneous terms, the deduction does not need to consider any inhomogeneous terms.¹³) Thus, it is sound to limit the fixed point and the intruder deduction to well-typed terms, which makes the fixed point finite.
4.1. Defining fixed points

Let us now see in more detail how to formally define the fixed point. An important aspect of the abstraction approach is that the global state is mutable, that is, the set membership of concrete values can change in transitions, and so their abstraction changes.

Example 5
The value ${p k}_{1}$ in Example 3 is created in the first transaction and has, after the first transaction, the abstraction . Since the second transaction deletes ${p k}_{1}$ from $r i n g (a)$ , it changes its abstract class to .

As such, transitions of the abstraction of values play a crucial role in the approach; we define the following notion:
Definition 3 (Term implication)

A term implication $(a, b)$ is a pair of abstract values $a, b \in A$ and a term implication graph $T I$ is a binary relation between abstract values, that is, $T I \subseteq A \times A$ . Instead of $(a, b) \in T I$ , we may also write $a \to \to b$ .

The reason we use the word “implication” is as follows. Suppose an abstract set of messages contains several occurrences of the same abstract value $a \in A$ , say $M = {f (a), g (a, a)}$ . Due to the abstraction, we have lost the information of how many distinct constants are represented here, for example, two corresponding concrete set of messages could be $M_{0} = {f (c_{1}), f (c_{2}), g (c_{1}, c_{2}), g (c_{1}, c_{1})}$ and $M_{1} = {f (c_{2}), g (c_{2}, c_{2}), g (c_{2}, c_{1})},$ where both $c_{1}$ and $c_{2}$ have the same set memberships $a$ . If now value $c_{1}$ changes its set memberships to, say, $b \in A$ , then the abstraction of $M_{0}$ becomes ${f (b), f (a), g (b, b), g (b, a)}$ and the abstraction of $M_{1}$ becomes ${f (a), g (a, a), g (a, b)}$ . Thus, in general, to include all possible terms that can be reached by a term implication $a \to \to b$ , each occurrence of $a$ can independently change to $b$ . This means that all of the original terms with now $a$ changed to $b$ are also reached, and hence we call it an implication. This is captured by the following definitions:

Definition 4 (Term transformation)

Let $(a, b)$ be a term implication. The term transformation under $(a, b)$ is the least relation $_{a} \to \to_{b}$ closed under the following rules:

\begin{aligned} \begin{matrix} {\bar{x_{a} \to \to_{b} x}}^{x \in V} \bar{a_{a} \to \to_{b} b} \frac{t_{1}_{a} \to \to_{b} s_{1} \dots t_{n}_{a} \to \to_{b} s_{n}}{f (t_{1}, \dots, t_{n})_{a} \to \to_{b} f (s_{1}, \dots, s_{n})} f \in Σ^{n} . \end{matrix} \end{aligned}

Note that this relation is also reflexive since $c_{a} \to \to_{b} c$ for $c \in A \subseteq Σ^{0}$ holds because of the third rule. If $t_{a} \to \to_{b} t^{'}$ then we say that $t^{'}$ is implied by $t$ under $(a, b)$ , or just $t^{'}$ is implied by $t$ for short.

Definition 5 (Term implication closure)

Let $T I$ be a term implication graph and let $t$ be a term. The term implication closure of $t$ under $T I$ is defined as the least set ${c l}_{T I} (t)$ closed under the following rules:

\begin{aligned} \begin{matrix} \bar{t \in {c l}_{T I} (t)} \frac{t^{'} \in {c l}_{T I} (t)}{t^{″} \in {c l}_{T I} (t)} \begin{matrix} (a \to \to b) \in T I, \\ t^{'}_{a} \to \to_{b} t^{″} \end{matrix} . \end{matrix} \end{aligned}

This definition is extended to sets of terms

M

as expected. If

t^{'} \in {c l}_{T I} (t)

then we say that $t^{'}$ is implied by $t$ (under $T I$ ).

Closing the fixed point under the term implication graph is actually quite large in many practical examples, and thus we just record the messages that are ever received by the intruder together with the term implication graph, but without performing this closure explicitly:

Definition 6 (Fixed point)

A protocol fixed point candidate, or fixed point for short, is a pair $(F P, T I)$ such that [here “candidate” is to emphasize that this is just a proof idea that has yet to be verified by Isabelle]

(1)
$F P$ is a finite and ground set of terms over $T (Σ ∖ V, \emptyset)$ .
(2)
$T I$ is a term implication graph: $T I \subseteq A \times A$ .

4.2. Limitations

There are some limitations of our approach that we now mention. First, PSPSP is limited to reachability properties. This is because privacy-type properties are quite hard to handle in infinite-state verification. To our knowledge, regarding automated tools for infinite sessions, only Tamarin¹² and ProVerif⁶ handle this by restriction to diff-equivalence.²⁶

We inherit the free algebra term model from Hess et al.¹³ (two terms are equal iff they are syntactically equal), and so we do not support algebraic properties such as needed for Diffie-Hellman. We inherit the limitations of AIF’s set-based abstraction approach:

We require each protocol to have a fixed and finite number of enumeration constants and sets. This typically means that also the number of agents is fixed—at least if the protocol has to specify a number of sets for each agent.

We require that the sets can only contain values. The reason is to allow these values to be abstracted by set membership. That would not work if we allowed composed terms in the sets.

We cannot refer directly to particular constants of type $v a l u e$ . This would not be very useful, as every value with the same set-membership status is identified with the same abstract value under the set-based abstraction.

We cannot check the equality of values, again, because two values may have the same abstraction.

As the following protocol shows, the abstraction may lose “connections” between values, and this can lead to spurious attacks. The example illustrates this using the transactions $s e n d_h$ and $d e l_s e t$ which result in the intermediate fixed point and the term implication . Thus under term implication we get the terms , , , and . The latter term triggers $a t t a c k_d e f$ , which emits an attack. However, on the concrete level. This attack is not possible because there any concrete chosen values for $N 1$ and $N 2$ in $h (N 1, N 2)$ , are either both in $s e t$ or both not in $s e t$ . We remark that many protocols do not rely on such “connections” between values, as demonstrated by our benchmark suite.

Our approach allows for an unbounded number of sessions. The only difference here between our work and, for example, Tamarin¹² and ProVerif⁶ is that we need, as mentioned, to fix the number of enumeration constants and sets, and thereby, in a typical specification, also fix the number of agents. However, there is no difference in the notion of unbounded sessions: We allow for an unbounded number of transitions, every set can contain an unbounded number of values, and the intruder can make an unbounded number of steps. There is potential for overcoming this limitation: Comon-Lundh and Cortier^27,28 show that a restriction to finitely many agents can often be without a loss of attacks. Mödersheim and Bruni¹⁵ indirectly show that similar results are possible for set-based abstraction, since one can compute a symbolic fixed point leaving agents uninstantiated variables. This, however, requires several restrictions on the use of negation, suggesting close limits of such an approach for set-based abstraction. As this would have also required a substantially more complicated concept for the fixed point computation and checking, we opted for not using this approach in Isabelle/PSPSP.

A minor limitation is that the method of PSPSP requires a typed model. In order to also be safe against type-flaw attacks one needs to employ a typing result like¹⁴ and thus also needs to satisfy the requirements of that result, but this is not a serious limitation for the class of protocols we consider and it is automatically checked (see Section 2.3).

Finally, PSPSP has a number of smaller limitations that we list here for completeness:

We require that all variables must have an atomic type. This restriction could actually be overcome because, for a type-flaw resistant protocol, it is sound to replace a variable of composed type with a corresponding composed term of atomic type variables. However, we consider it out of scope to implement and formally verify this transformation and its soundness, and thus require that all variables must have atomic type.

Our definition of the $(D e c o m p o s e)$ rule using ${A n a}_{f}$ means that one cannot let secret keys be values $S K$ and then define the corresponding public key as $p k (S K)$ . This is because ${A n a}_{f}$ does not allow definitions on the form $A n a (c r y p t (p k (k), m)) = ({k}, {m})$ . We consider this a small restriction because, as the examples show, one can instead let the public keys be values, and then have a function $i n v$ mapping them to private keys.

We are using pattern matching in the receipt of messaging. The user of our tool thus needs to understand that to implement a specified protocol, they need their implementation to reject messages received that are not in the expected format. This is in contrast to ProVerif’s $π$ -calculus,⁶ where the steps checking the format are stated more explicitly in the specifications. We do not consider this a significant limitation because this kind of pattern matching is quite standard in the modeling of security protocols, for example, AVISPA, and Meier et al.¹²

4.3. Example of a fixed point computation

Consider again the keyserver protocol defined in Section 3.1; for simplicity, we do this example for just one user $a$ who is also honest: $u s e r = h o n e s t = {a}$ . We show how the fixed point (or rather the candidate that we then check with Isabelle) is computed; to make it more readable, let us give the fixed point right away and then see how each element is derived: ${F P}_{k s} \equiv ({F P}_{k s}, {T I}_{k s}),$ where

The term implication graph ${T I}_{k s}$ can be represented graphically as follows with each edge $a \to \to b$ corresponding to an element of ${T I}_{k s}$ :

Note that we can actually reduce the representation of the fixed point a little, as we do not need to include facts that can be obtained via term implication from others; with this optimization, we obtain:

To compute ${F P}_{k s}$ , we first consider the transaction $o u t O f B a n d$ where a fresh key is inserted into both $r i n g (a)$ and $v a l i d (a)$ and sent out. The abstraction of this key is thus the value . This value is in the intruder’s knowledge in ${F P}_{k s}$ but redundant due to other messages we derive later. [In fact, the well-formedness conditions of the previous section require us to also include $o c c u r s$ facts, but for illustration, we have simply omitted them (as the intruder knows every public key that occurs).] Note that this rule cannot produce anything else, so we do not consider it for the remainder.

Next, let us look at the transaction $k e y U p d a t e U s e r$ . For $k e y U p d a t e U s e r$ , we need to choose an abstract value for $P K$ that satisfies the check $P K i n r i n g (a)$ . At this point in the fixed point computation, we have only . Since the transaction removes the key $P K$ from $r i n g (a)$ , we get the term implication . A fresh value $N P K$ is also generated and inserted into $r i n g (a)$ , and a signed message is sent out which gives us: . Also, this one is a message that later becomes redundant with further messages. By analysis, the intruder also obtains .

The new value allows for another application of the $k e y U p d a t e U s e r$ rule, namely with this key in the role of $P K$ . This now gives the term implication and the message . After this, there are no further ways to apply this transaction rule, because we will not get to any other abstract value that contains $r i n g (a)$ .

Applying the $k e y U p d a t e S e r v e r$ transaction to the first signature we have obtained (i.e., with and ), we get the term implications and , and the intruder learns . Applying the $k e y U p d a t e S e r v e r$ transaction with the second signature (i.e., with $P K = \emptyset$ and $N P K$ as before) is not possible because $v a l i d (a) \notin \emptyset$ and thus the transaction’s check of $P K \in v a l i d (a)$ will not be satisfied. However, because of the intruder’s knowledge of the first signature and the previously stated term implication , the intruder also knows the signature . If we apply the $k e y U p d a t e S e r v e r$ transaction with this signature (i.e., with and ) then we get the new term implication , the term implication , which we already knew, and the intruder learns , but that was already in the intruder knowledge.

Any other signature that the intruder knows as a consequence of the two signatures sent by the agent and the term implications will not satisfy the checks of the $k e y U p d a t e S e r v e r$ transaction. Note though, that we must also check if the intruder can generate a signature that works with $k e y U p d a t e S e r v e r$ : however, the only private keys he knows are those represented by , and they are not accepted for this transaction. (In a model with dishonest agents, the intruder can, of course, produce signatures with keys registered to a dishonest agent’s name, but here we have just one honest user $a$ .)

No other transaction can produce anything we do not have in ${F P}_{k s}$ already—in particular, we cannot apply the attack transaction, and this concludes the fixed point computation. Thus—according to our abstract interpretation analysis—the protocol is indeed secure. Next, we try to convince Isabelle.

5. Computing fixed points and checking fixed point coverage

In this work, we automatically calculate fixed points with the abstract interpretation approach as a “proof idea” for conducting the security proof on the concrete protocol. A major contribution of our work is the ability to turn this fixed point into a formal security proof in Isabelle. Essentially, we prove that the fixed point indeed “covers” everything that can happen. We break this down into an induction proof: given any trace that is covered by the fixed point, if we extend it by any applicable transition, then the resulting trace is also covered by the fixed point. This induction step we break down into a number of checks that are directly executable within Isabelle using the built-in term rewriting proof method code-simp. The induction is done in the proof of a protocol-independent Isabelle theorem (Theorem 3) that shows that any protocol that passes said checks is indeed secure. Note that these checks are not only fully automated, but they also terminate in all but a few degenerate cases. [It is technically possible to specify protocols for which the checks do not terminate. For instance, an analysis rule of the form ${A n a}_{f} (x) = ({f (f (x))}, R)$ , for some $f$ , $x$ and $R$ , would lead to termination issues when automatically proving the conditions for the typing result which we rely on, because we here need to compute a set that contains the terms occurring in the protocol specification and is closed under keys needed for analysis, and such a set would in this case be infinite. However, this is an artificial example that normally does not occur since it is usually the case that keys cannot themselves be analyzed.]

5.1. Automatically checking for fixed point coverage

Let us look at how we can automatically check if a fixed point covers a protocol. We first explain how this works in general and thereafter give an example, in Example 6, of how it works using the keyserver example.

A transaction of the protocol after resolving all the syntactic sugar has only variables of type $v a l u e$ . Thus, in a typed model and under the abstraction, we can instantiate the variables only with abstract values, that is, elements from $A$ . We first define what it means that a transaction is applicable under such a substitution of the variables with respect to the fixed point computed by the abstract interpretation:

Definition 7 (Fixed point coverage: preconditions)

Let $T = S_{r} \cdot S_{c} \cdot F \cdot S_{u} \cdot S_{s}$ be a transaction and let $F P = (F P, T I)$ be a fixed point. Let further $δ$ be an abstraction substitution mapping the variables of $T$ to abstract values of $A$ . We say that $δ$ satisfies the preconditions (for $T$ and $F P$ ), written $p r e (F P, δ, T)$ , iff the following conditions are met:

F1.
${c l}_{T I} (F P) ⊢ δ (t_{i})$ for all $r e c e i v e t_{1}, \dots, t_{n}$ occurring in $S_{r}$ and for all $i \in {1, \dots, n}$ .
F2.
$s \in δ (x)$ for all $x i n s$ occurring in $S_{c}$ .
F3.
$s \notin δ (x)$ for all $x n o t i n s$ occurring in $S_{c}$ .
F4.
for all $x \in f r e s h (T)$ .

Here, F1 checks that the intruder can produce all input messages for the transaction under the given $δ$ . Note that the intruder has control over the entire network, so he can use any message honest agents have sent and also construct other messages from that knowledge (hence the $⊢$ ). Moreover, we consider here the closure of the intruder knowledge $F P$ under the term implication rules, since that represents all variants of the messages that are available to the intruder; we will later show as an optimization that we can check whether ${c l}_{T I} (F P) ⊢ δ (t)$ holds without first explicitly computing ${c l}_{T I} (F P)$ . The two next checks, F2 and F3, verify that are that all set membership conditions are satisfied, and F4 checks that all fresh variables represent values that are not members of any set.

Now, for every $δ$ under which the transaction $T$ can be applied (according to $F P$ ), we compute what $T$ can “produce” and check that it is already covered by $F P$ . The transaction can produce outgoing messages and changes in set memberships. The latter is captured by an updated abstraction substitution $δ_{u}$ that is identical with $δ$ except for those values that changed their set memberships during the transaction:
Definition 8 (Abstraction substitution update)

Let $T = S_{r} \cdot S_{c} \cdot F \cdot S_{u} \cdot S_{s}$ be a transaction and $δ$ an abstraction substitution. We define the update of $δ$ w.r.t. $T$ , written $δ_{u}$ , as follows:

\begin{aligned} δ_{u} (x) & \equiv u p d (S_{u}, x, δ (x)), where \end{aligned}

\begin{aligned} u p d (0, x, a) & = a, \\ u p d (t \cdot S, x, a) & = {\begin{cases} u p d (S, x, a \cup {s}) & if t = i n s e r t x s, \\ u p d (S, x, a ∖ {s}) & if t = d e l e t e x s, \\ u p d (S, x, a) & otherwise . \end{cases} \end{aligned}

Note that according to this definition, if a transaction contains insert and delete operations of the same value $x$ for the same set, then “the last one counts.” But there is a more subtle point: suppose the transaction includes the operations $i n s e r t x s$ and $d e l e t e y s$ . The above definition would not necessarily formalize the updates of the set memberships if the transaction were applicable (in the concrete) under an interpretation $I$ with $I (x) = I (y)$ . Thanks to the preparations described in Section 3.3, we have in every transaction the constraint that all value variables have pairwise disjoint concrete values.

This leads to the following two postconditions:

Definition 9 (Fixed point coverage: post-conditions)

Let $T = S_{r} \cdot S_{c} \cdot F \cdot S_{u} \cdot S_{s}$ be a transaction and let $F P = (F P, T I)$ be a fixed point. Let $δ$ be an abstraction substitution and $δ_{u}$ the update of $δ$ w.r.t. $T$ . We say that $δ$ satisfies the postconditions (for $T$ and $F P$ ), written $p o s t (F P, δ, T)$ , iff the following conditions are met:

G1.
$δ (x) \to \to^{*} δ_{u} (x)$ for all $x \in f v (T) ∖ f r e s h (T)$ .
G2.
${c l}_{T I} (F P) ⊢ δ_{u} (t_{i})$ for all $s e n d t_{1}, \dots, t_{n}$ occurring in $S_{s}$ and for all $i \in {1, \dots, n}$ .

Here G1 expresses that every update of a value must correspond to a path in the term implication graph (it does not need to be a single edge). G2 means that the intruder learns every outgoing message $δ_{u} (t)$ and thus it must be covered by the fixed point when closed under term implication.

We can now put it all together: the preconditions restrict the coverage check to those abstraction substitutions that are actually possible in the fixed point. The postconditions check that the fixed point covers everything that the transaction produces under those same substitutions. Fixed point coverage is thus defined as follows:
Definition 10 (Fixed point coverage)

Let $T$ be a transaction and let $F P = (F P, T I)$ be a fixed point. We say that $F P$ covers $T$ iff for all abstraction substitutions $δ$ with domain $f v (T)$ , if $p r e (F P, T, δ)$ then $p o s t (F P, T, δ)$ . For a protocol $P$ we say that $F P$ covers $P$ iff $F P$ covers all transactions of $P$ .

With this defined, we can prove the following theorem:

Theorem 3
Let $P$ be a protocol and let $F P = (F P, T I)$ be a fixed point. If $a t t a c k \notin F P$ , and if $P$ is covered by $F P$ , then $P$ is secure. [This theorem is called protocol_secure in the Isabelle code and can be found in the Stateful_Protocol_Verification.thy theory file.]
Proof Proof Sketch

We gave the intuition of this proof in the introductory text of this section. We supplement that here with some further intuition. First, we define a notion of abstract intruder knowledge, namely $α_{i k} (A, I) = α_{d b (A, I, \emptyset)} (I (i k (A)))$ . The proof then relies on two insights about this abstract intruder knowledge.

The first insight is that if a term $t$ is in the intruder’s knowledge, then its abstraction is also in the abstract intruder knowledge. Formally if $t \in I (i k (A))$ then $α_{d b (A, I, \emptyset)} (t) \in α_{i k} (A, I)$ .

The second insight is to prove that for any reachable constraint $A$ , with satisfying interpretation $I$ , it is the case that any message $t$ (e.g., the $a t t a c k$ constant) in the abstract intruder knowledge is also derivable from the fixed point. Formally if $t \in α_{i k} (A, I)$ then ${c l}_{T I} (F P) ⊢ t$ . The proof of this second insight is by an induction on how $A$ was reached by $\Rightarrow^{∙}$ . The central part is the induction step where a reachable constraint $A^{'}$ is extended with the dual of a transaction $T$ . Here we see that the abstract intruder knowledge achieved by running the dual of $T$ is a result of messages sent in $T$ . The definition of coverage ensures that these sent messages are also derivable from the fixed point’s term implication closure.

Example 6
Consider the key update transaction $k e y U p d a t e S e r v e r$ from Section 3.1. We now show that the fixed point ${F P}_{k s}$ defined in Example 4.3 covers this transaction, that is, satisfies Definition 10.

The only variables occurring in $k e y U p d a t e S e r v e r$ are $P K$ and $N P K$ , so we can begin by finding the abstraction substitutions with domain ${P K, N P K}$ that satisfy the preconditions given in Definition 7. We denote by $Δ$ the set of these substitutions. Afterwards, we show that all $δ \in Δ$ satisfy the postconditions given in Definition 9.

The variables $P K$ and $N P K$ are not declared as fresh in $k e y U p d a t e S e r v e r$ so condition F4 is vacuously satisfied. From F2 and F3 we know that $v a l i d (a) \in δ (P K)$ and $v a l i d (a), r e v o k e d (a) \notin δ (N P K)$ , for all $δ \in Δ$ . From F1 we know that ${c l}_{{T I}_{k s}} ({F P}_{k s}) ⊢ δ (s i g n (i n v (P K), p a i r (a, N P K)))$ . The intruder cannot compose the signature himself since he cannot derive a private key of the form $i n v (b)$ where $b \in A$ and $v a l i d (a) \in b$ . Hence, the only signatures available to him—that also satisfy the constraints for $Δ$ that we have deduced so far—are for each . The only surviving substitutions are

That is, $Δ = {δ^{1}, δ^{2}}$ .

Next, we compute the updated substitutions w.r.t. the transaction $k e y U p d a t e S e r v e r$ :

Now we can verify that conditions G1 and G2 hold for $δ^{1}$ and $δ^{2}$ : We have that $δ^{i} (x) \to \to δ_{u}^{i} (x)$ is covered by ${T I}_{k s}$ , for all $i \in {1, 2}$ and all $x \in {P K, N P K}$ . We also have that the outgoing message $i n v (P K)$ is in ${c l}_{{T I}_{k s}} ({F P}_{k s})$ under each $δ_{u}^{i}$ . Thus $k e y U p d a t e S e r v e r$ is covered by ${F P}_{k s}$ .

We can, in a similar fashion, verify that the remaining transactions of the keyserver protocol are covered by the fixed point. Thus, the keyserver protocol is covered by ${F P}_{k s}$ .
5.2. Automatic fixed point computation

An interesting consequence of the coverage check is that we can also use it to compute a fixed point for protocols $P$ . In a nutshell, we can update a given fixed point candidate ${F P}_{0}$ for $P$ as follows: For each transaction of $P$ , we first compute the abstraction substitutions $Δ$ that satisfy the preconditions F1 to F4. Secondly, we use the postconditions G1 and G2 to compute the result of taking $T$ under each $δ \in Δ$ and add those terms and term implications to ${F P}_{0}$ . Starting from an empty initial iterand $(\emptyset, \emptyset)$ , we can then iteratively compute a fixed point for $P$ . Definition 11 gives a simple method to compute protocol fixed points based on this idea.

Definition 11
Let $P$ be a protocol and let $f$ be the function defined as follows:
$\begin{aligned} f ((F P, T I)) & \equiv (F P \cup {t \in {\hat{F P}}_{δ}^{T} ∣ T \in P, δ \in Δ_{F P, T I}^{T}}, \\ T I \cup {(a, b) \in {\hat{T I}}_{δ}^{T} ∣ T \in P, δ \in Δ_{F P, T I}^{T}}), \end{aligned}$
where
$\begin{aligned} Δ_{F P, T I}^{T} & \equiv {δ ∣ d o m (δ) = f v (T), p r e ((F P, T I), T, δ)}, \\ {\hat{F P}}_{δ}^{T} & \equiv {δ_{u} (t_{i}) ∣ s e n d t_{1}, \dots, t_{n} occurs in T, 1 \leq i \leq n}, \\ {\hat{T I}}_{δ}^{T} & \equiv {(δ (x), δ_{u} (x)) ∣ x \in f v (T) ∖ f r e s h (T)} . \end{aligned}$

Then we can compute a fixed point for $P$ by computing a fixed point of $f$ . This can be done, for example, by computing the least $n \in N$ such that $f^{n} ((\emptyset, \emptyset)) = f^{n + 1} ((\emptyset, \emptyset))$ because then $f^{n} ((\emptyset, \emptyset))$ is indeed a fixed point.

We provide, as part of our Isabelle formalization, a function to compute such a fixed point (with some optimizations to avoid computing terms and term implications that are subsumed by the remaining fixed point), using the built-in code generation functionality of Isabelle.
6. Improving the coverage check

We describe a number of improvements that are essential to an efficient check. Since we have proven the checks correct in Isabelle, there is no risk of affecting the correctness of the entire approach.

There are two major issues that make the coverage check from the previous section quite inefficient when implemented directly. One concerns the fact that to see if a protocol is covered, we need to consider for every received term any message that is in the fixed point closed under term implications and intruder deduction. Even though the typed model allows us to keep even the intruder deduction closure finite, explicitly computing the closure is not feasible even on rather modest examples. The second issue is about the abstraction substitutions $δ$ of the check: recall that in the check we defined above, for a given transaction we consider every substitution $δ$ of the variables with abstract values, which is of course exponential both in the number of variables and the number of sets.

Let us first deal with this second issue. We can indeed compute exactly those substitutions that satisfy conditions F2 to F4: every positive set-membership check $x i n s$ of the transaction requires that $s \in δ (x)$ , and similarly for the negative case. Moreover, $δ (x)$ can be only an abstract value that actually occurs as a member of the fixed point or as a subterm in the fixed point. Starting from these constraints often substantially cuts down the number of substitutions $δ$ that we need to consider in the check, especially when we have more agents than in the example. This is because typically (at least in a good protocol) most values will not be members of many sets that belong to different agents (but rather just a few that deal with that particular value).

The first issue, that is, avoiding computing the term implication closure ${c l}_{T I} (F P)$ when performing intruder deductions, is more difficult. The majority of this section is therefore dedicated to improving on conditions F1 and G2 so that we can avoid computing the entire closure ${c l}_{T I} (F P)$ —only in a few corner cases do we need to compute the closure for a few terms of $F P$ . A key to that is to saturate the intruder’s knowledge with terms that can be obtained by analysis and then work with composition only, that is, $⊢_{c}$ .

6.1. Intruder deduction modulo term implications

Recall that $⊢_{c}$ is the intruder deduction without analysis, that is, only the $(A x i o m)$ and $(C o m p o s e)$ rules. We first consider how we can handle in this restricted deduction relation the term implication graph $T I$ efficiently, that is, how to decide ${c l}_{T I} (M) ⊢_{c} t$ (for given $T I$ , $M$ , and $t$ ) without computing ${c l}_{T I} (M)$ . In a second step, we then show how to also handle analysis, that is, the full $⊢$ relation.

In fact, it boils down to checking the side condition of $(A x i o m)$ , that is, in our case, whether $t \in {c l}_{T I} (M)$ , without having to compute ${c l}_{T I} (M)$ first. (The composition rule is then easier because it does not “directly look” at the knowledge.) For this, it is sufficient if we can check whether $t \in {c l}_{T I} (t^{'})$ for any $t^{'} \in M$ , without having to compute ${c l}_{T I} (t^{'})$ .

Consider again Definition 5. We can use this to derive a recursive check function $t^{'} ⇝_{T I} t$ for the question $t \in {c l}_{T I} (t^{'})$ : it can only hold if either

$t$ and $t^{'}$ are the same variable,

or $t$ , $t^{'}$ are abstract values with a path from $t^{'}$ to $t$ in $T I$ ,

or $t = f (t_{1}, \dots, t_{n})$ and $t^{'} = f (t_{1}^{'}, \dots, t_{n}^{'})$ , where recursively $t_{i}^{'} ⇝_{T I} t_{i}$ holds for all $1 \leq i \leq n$ .

With this we can define a recursive relation $⊩_{c}$ that checks for given $M$ , $T I$ , and $t$ whether ${c l}_{T I} (M) ⊢_{c} t$ without computing ${c l}_{T I} (M)$ :

\begin{array}{rcl} M ⊩_{c}^{T I} t & iff & (\exists t^{'} \in M . t^{'} ⇝_{T I} t) or \\ t is of the form t = f (t_{1}, \dots, t_{n}) where f \in Σ_{p u b}^{n} and M ⊩_{c}^{T I} t_{i} for all i \in {1, \dots, n} . \end{array}

This relation indeed fulfills its purpose:

Lemma 2
${c l}_{T I} (M) ⊢_{c} t iff M ⊩_{c}^{T I} t$ .

Next, we show how to reduce the intruder deduction problem $⊢$ to the restricted variant $⊢_{c}$ .
6.2. Analyzed intruder knowledge

It has been observed that many intruder deduction problems can be regarded as local theories, that is, so that all intermediate terms in the deduction are subterms of the given intruder knowledge or the goal term to construct. This is because the intruder may, of course, compose a message and then decompose it again, but in most theories, that would only yield one of the terms that we started with. Observe that we only support theories where the result of an analysis step is $x$ direct subterms of the term being analyzed. This means that all deduction proofs that contain such a pair of encryption–decryption steps can be normalized to a simpler proof, eliminating the unnecessary detour. Thus, all decomposition steps are applied to messages composed by an honest agent, and thus all intermediate steps in an intruder deduction are subterms of what the intruder wants to construct or knows in advance. [We only mention here that this is indeed close to the concept of a local theory: it is sufficient to consider in a deduction $M ⊢ m$ only intermediate terms that are subterms of $M$ or $m$ . However, there are some exceptions to the locality property: in decomposition, the necessary key may not be a subterm of $M$ or $m$ . For instance, to decrypt $c r y p t (K, M)$ , one needs $i n v (K)$ , which may neither be part of $M$ nor $m$ . (In that case, since $i n v$ is private, the deduction step is only possible if $i n v (K)$ already occurs in $M$ .)]

The proof normalization argument we just sketched would be very difficult to integrate into Isabelle directly, since we would have to meta-reason in Isabelle about the definition of the intruder deduction rules. In fact, we have a similar way when reasoning about homogeneous message deduction in compositional proofs (i.e., that the intruder never needs to mix messages from the protocols being composed). Our Isabelle proofs work by induction over the size of terms (not over the structure of the deduction) that everything deducible is also deducible with a more restricted notion, in this case, that it is sufficient to only compose terms if the intruder’s knowledge is already analyzed. We note that such arguments do not hold in general when algebraic properties are considered (such as commutativity of exponents in Diffie-Hellman). For that case, our theory would need nontrivial adaptations.

The idea is thus that $⊢_{c}$ is actually already sufficient, if we have an analyzed intruder knowledge: we define that a knowledge $M$ is analyzed iff $M ⊢ t$ implies $M ⊢_{c} t$ for all $t$ . More in detail, we can consider a knowledge $M$ that is saturated by adding all subterms of $M$ that can be obtained by analysis. Then $M$ is analyzed, that is, we do not need any further analysis steps in the intruder deduction. This is intuitively the case because the intruder cannot learn anything from analyzing messages he has composed himself.

We define formally what it means for a term $t$ to be analyzed using the keys ( $K e y s (t)$ ) and results ( $R e s u l t (t)$ ) from the analysis as defined in Section 2.2:

Definition 12 (Analyzed term)

Let $M$ be a set of terms and let $t$ be a term. We then say that $t$ is analyzed in $M$ iff $M ⊢_{c} K e y s (t) implies M ⊢_{c} R e s u l t (t)$ (where $M ⊢_{c} N$ for sets of terms $M$ and $N$ is a shorthand for $\forall t \in N . M ⊢_{c} t$ ).

The following lemma then provides us with a decision procedure for determining if a knowledge is analyzed:

Lemma 3
$M$ is analyzed iff all $t \in M$ are analyzed in $M$ .

We consider again an intruder’s knowledge given as the term implication closure of a set of messages, that is, ${c l}_{T I} (M)$ instead of $M$ . Efficiently checking whether an intruder’s knowledge term implication closure is analyzed, without actually computing it, is challenging. The following lemma shows that if we can derive the results of analyzing a term $t$ in the knowledge $M$ , then we can also derive the results of analyzing any implied term $t^{'} \in {c l}_{T I} (t)$ :
Lemma 4
Let $t \in M$ . If ${c l}_{T I} (M) ⊢_{c} R e s u l t (t)$ then for all $t^{'} \in {c l}_{T I} (t)$ , ${c l}_{T I} (M) ⊢_{c} R e s u l t (t^{'})$ .

Therefore, if all $k \in K e y s (t)$ can be derived and $t$ is analyzed in ${c l}_{T I} (M)$ then we can conclude that all implied terms $t^{'} \in {c l}_{T I} (t)$ are analyzed in ${c l}_{T I} (M)$ . If, however, some of the keys for $t$ are not derivable, then we are forced to check the implied terms as well as the following example shows:
Example 7
Let $f, g \in Σ_{p r i v}^{1}$ , $T I = {a \to \to b}$ , and $M = {f (a), g (b)}$ . Define the analysis rules ${A n a}_{f} (x) = ({g (x)}, {x})$ and ${A n a}_{g} (x) = (\emptyset, \emptyset)$ . Then ${c l}_{T I} (M) = {f (b)} \cup M$ . The term $f (a)$ is analyzed in ${c l}_{T I} (M)$ because the key $g (a)$ cannot be derived: ${c l}_{T I} (M) ⊬_{c} g (a)$ . However, $f (a)_{a} \to \to_{b} f (b)$ and $f (b)$ is not analyzed in ${c l}_{T I} (M)$ : $A n a (f (b)) = ({g (b)}, {b})$ but the key $g (b)$ is derivable from ${c l}_{T I} (M)$ in $⊢_{c}$ , whereas the result $b$ is not. Thus ${c l}_{T I} (M)$ is not an analyzed knowledge.

So in most cases we can efficiently check if ${c l}_{T I} (M)$ is analyzed, and in some cases we need to also compute the term implication closure ${c l}_{T I} (t)$ of problematic terms $t \in M$ (but not necessarily compute all of ${c l}_{T I} (M)$ ). The former corresponds to the three “if” cases of the following definition, and the latter corresponds to the final “else”-branch:
Lemma 5
${c l}_{T I} (M)$ is analyzed iff for all $t \in M$ , the following holds:
$\begin{array}{l} if {c l}_{T I} (M) ⊢_{c} K e y s (t) then t is analyzed in {c l}_{T I} (M) \\ else if A \cap s u b t e r m s (K e y s (t)) = \emptyset then t r u e \\ else if \forall s \in {c l}_{T I} (K e y s (t)) . {c l}_{T I} (M) ⊬_{c} s then t r u e \\ else all t^{'} \in {c l}_{T I} (t) are analyzed in {c l}_{T I} (M) . \end{array}$

Lemma 5 provides us with the means to extend a knowledge $M$ to one whose term implication closure is analyzed: Suppose for a term $t \in M$ the three if conditions of the lemma fail, that is, when we have to check for every $t^{'} \in {c l}_{T I} (t)$ that $t^{'}$ is analyzed in ${c l}_{T I} (M)$ . If $t^{'}$ can be decrypted and the keys are available, but the result $R e s u l t (t^{'})$ of the decryption cannot be composed in $M$ , then (and only then) we add this result to $M$ . For instance, in Example 7, we need to extend $M = {f (a), g (b)}$ with $b$ , resulting in the analyzed knowledge $M^{'} = {f (a), g (b), b}$ .

The two “else–if”-branches are an improvement we have made for this journal version of the paper. The idea is the following: (1)
If $K e y s (t)$ are not derivable from the term-implication closed knowledge ${c l}_{T I} (M)$ , and if there is no abstract value occurring in $K e y s (t)$ , then $K e y s (s) = K e y s (t)$ for all implied terms $s$ of $t$ , and so $t$ is analyzed in ${c l}_{T I} (M)$ .
(2)
If none of the implied keys of $t$ are derivable then $t$ is also analyzed in ${c l}_{T I} (M)$ .

These two special cases are useful to speed up the analyzed-fixed point check when the fixed point contains terms that have lots of abstract values in them and that cannot be analyzed by the intruder (the last else branch would in such cases take a lot of time to compute since the size of ${c l}_{T I} (t)$ grows exponentially with the number of occurrences of abstract values in $t$ )—also, it is often the case that $K e y s (t)$ has fewer abstract values in it than $R e s u l t (t)$ , and so the size of ${c l}_{T I} (K e y s (t))$ is likely to be much smaller than ${c l}_{T I} (t)$ , hence the second “else–if” condition is usually much faster to check than the last else-branch.

As an example, when modeling private channels one may use terms of the form $s e c c h (s e c c h c r (a, b), t)$ , denoting that $t$ is sent on a private channel from agent $a$ to agent $b$ , where the term $t$ is derivable if the secret $s e c c h c r (a, b)$ is known, and where there would be an attack on the protocol if the intruder knew $s e c c h c r (a, b)$ for honest $a$ and $b$ . In a secure protocol, the term $s e c c h (s e c c h c r (a, b), t)$ , for honest $a$ and $b$ , would not be derivable by the intruder, and so it is sufficient to check that ${c l}_{T I} (M) ⊬_{c} s e c c h c r (a, b)$ and $A \cap s u b t e r m s (s e c c h c r (a, b)) = \emptyset$ instead of checking that all elements of ${c l}_{T I} (s e c c h (s e c c h c r (a, b), t))$ are analyzed in ${c l}_{T I} (M)$ , which may take a significant amount of time since $t$ may contain a lot of abstract values.

The improvements described from Section 6 up to here are the Default version of our coverage check. We will now explain an alternative check that improves the run time for some protocols. Note that in our implementation, we can make use of Isabelle’s parallelization framework, executing the default version and the alternative version in parallel, returning the result of whichever check terminates first. By that, we can ensure that the user always benefits from the runtime of the fastest check.
6.3. Restricting the number of abstraction substitutions further

We return to the second issue described at the beginning of this section: restricting how many abstraction substitutions need to be considered in order to conclude that a transaction is covered. The solution presented so far restricted the set of abstraction substitutions considered to those that satisfy conditions F2 to F4 of Definition 7. We now show how to take into consideration also condition F1 to further restrict that set. This will not be exactly the set of substitutions that satisfy F1 to F4, but rather an overapproximation that can be computed in an efficient way.

F1 essentially says that for each received term $t$ of a considered transaction, its abstraction $δ (t)$ must be derivable from the fixed point using the $⊢$ relation. However, we will, based on the previous two sections, restrict ourselves to the $⊢_{c}$ relation.

We, therefore, in this section, define functions that together calculate an overapproximation of the set of these $δ$ . These functions can be seen as implementing the $⊢_{c}$ relation. We will now, in this first part of this section, consider two functions based on the Axiom rule of $⊢_{c}$ , and in the second part of this section, we will then consider a function combining the Axiom rule and the Compose rule. We therefore will now introduce two functions ${m a t c h}^{'}$ and $m a t c h$ that are based on the Axiom rule. They work by matching terms in $r e c e i v e$ -steps, possibly containing variables, with ground terms in the fixed point, possibly containing abstract values. The idea is that by inspecting a term $t$ from the $r e c e i v e$ -steps and comparing it to the terms available in the fixed point we will be able to see what the variables in $t$ could be instantiated to if $δ (t)$ is to be a term from the fixed point. This is illustrated by the following example:

Example 8
Consider the term $t = f (X, X)$ from a $r e c e i v e$ -step in a transaction of a protocol and the term from a given fixed point. Observe that $s$ and $t$ have a similar structure, but the first and second arguments of $s$ are different, so there is no match between $s$ and $t$ . However, modulo term implication, there could be a match if the two abstract values in $s$ can flow together.

Consider the following term implication graph: The closure of is the set and the term implication closure of is . We can see that both considered abstract values share that they actually represent and . Thus, $t$ can be made equal to $s$ modulo term implication by choosing either to replace all occurrences of $X$ with or by choosing to replace all occurrences of $X$ with . Therefore there are two abstraction substitutions $δ$ such that $s \to \to δ (t)$ , namely and .

What we have done in this example is to use three steps to find out if there is a $δ$ such that $δ (t)$ can be found in ${c l}_{T I} (F P)$ . More generally, step 1 is to see if there is a term $s \in F P$ that matches $t$ , where different occurrences of the same variable may need to be matched with different abstract values (as for $X$ in the above example). Step 2 is to collect for each variable $X$ the set of every abstract value $a$ that works for every occurrence of $X$ simultaneously modulo term implication, that is, for every abstract value $b$ computed in step 1, $b \to \to a$ . Step 3 is to calculate every possible abstraction substitution $δ$ from step 2.

Let us first consider ${m a t c h}^{'}$ that captures the idea of step 1. It takes two terms $t$ and $s$ , where $t$ is a term from a rule (that may have variables) and $s$ is a term from the fixed point (that may not have variables). The function ${m a t c h}^{'}$ checks if $t$ and $s$ can be made equal by replacing occurrences of variables in $t$ with abstract values. If this is possible, it returns a singleton set containing function $θ$ mapping each variable $x$ to a set of abstract values, where each member of $θ (x)$ is a possible replacement for $x$ . If it is not possible, it returns the empty set. When trying to match a variable $x$ with an abstract value $a$ , ${m a t c h}^{'}$ returns a singleton set ${θ}$ and $θ$ maps $x$ to ${a}$ . For a composed term, we recursively compute the set of matches for each subterm and then pointwise merge the results, so that for each variable $x$ we get all abstract values it needs to have in some occurrence of $x$ in $t$ in order to allow for the match with $s$ . Note that in the following definition, $δ$ and $θ$ map from variables to sets of abstract values.
Definition 13
The function ${m a t c h}^{'}$ is defined as follows:
$\begin{aligned} {m a t c h}^{'} (x, a) & = {θ} if x \in V, a \in A, \forall y . θ (y) = i f x = y t h e n {a} e l s e \emptyset \\ {m a t c h}^{'} (t, s) & = {θ} if t = f (t_{1}, \dots, t_{n}), s = f (s_{1}, \dots, s_{n}), \\ \forall i \in {1, \dots, n} . {m a t c h}^{'} (t_{i}, s_{i}) \neq \emptyset, \\ Δ = {δ \in {m a t c h}^{'} (t_{i}, s_{i}) ∣ i \in {1, \dots, n}}, \\ \forall x . θ (x) = ⋃_{δ \in Δ} δ (x), \\ {m a t c h}^{'} (t, s) = & \emptyset otherwise . \end{aligned}$

Example 9
We return to Example 8 and see that ${m a t c h}^{'}$ indeed will calculate what the occurrences of $X$ should be replaced by. Here we have that . We notice that the set to which $X$ is mapped to consists exactly of the two abstract values that we expected to get from Example 8.

Having defined a function that implements step 1, we now turn to implementing a function $m a t c h$ that combines this with step 2. The function $m a t c h$ checks if $t$ and $s$ can be made equal modulo term implication by replacing variables in $t$ with abstract values. If this is possible, it returns a singleton set containing a function $θ$ mapping each variable $x$ to a set of abstract values, where each member of $θ (x)$ is a possible replacement for $x$ . If it is not possible, it returns the empty set.

The function does this as follows: If ${m a t c h}^{'}$ gave the solution $σ$ , $x$ is a variable, and $a \in σ (x)$ , that is, $a$ is one of the abstract values $x$ needs to match in some occurrence, then we compute all $b$ that can be reached from $a$ with term implication. Next, $σ^{'} (x)$ is the intersection of these sets (for any $a \in σ (x)$ ). Thus, $b \in σ^{'} (x)$ holds iff $a \to \to b$ for every $a \in σ (x)$ . This ensures that the term $s$ of the given fixed point can be rewritten by term implications so that it matches $t$ in every occurrence of $x$ . For instance, in Example 8, the variable $X$ could either be or , to allow a match between $s$ and $t$ modulo term implication. Match also checks that all free variables in $t$ can actually represent some abstract value, because if not, then it is not at all possible to make $t$ equal to $s$ modulo term implication. Finally, every variable that does not occur in $t$ we map to $O C C$ , the set of all abstract values that can occur.
Definition 14
Let $F P = (F P, T I)$ be a fixed point. Let $O C C$ be the abstract values that occur in $F P$ , that is, $O C C = A \cap s u b t e r m s ({c l}_{T I} (F P))$ . The function $m a t c h$ is defined as follows:
$\begin{aligned} m a t c h (t, s) & = {θ} if σ \in {m a t c h}^{'} (t, s), \\ \forall x . σ^{'} (x) = ⋂_{a \in σ (x)} {b ∣ (a, b) \in {T I}^{}}, \\ \forall x \in f v (t) . σ^{'} (x) \neq \emptyset, \\ \forall x . θ (x) = i f x \in f v (t) t h e n σ^{'} (x) e l s e O C C, \\ m a t c h (t, s) & = \emptyset otherwise . \end{aligned}$

We additionally lift $m a t c h$ to sets of terms $M$ using the following definition:
$m a t c h (t, M) = {θ \in m a t c h (t, s) ∣ s \in M} .$

We can finally conclude with step 3: $m a t c h (t, s)$ either is empty (if there is no match) or a single map $θ$ that tells for every variable the possible values under which we can match the terms. Now every abstraction substitution $δ$ that maps each variable $x$ to an element of $θ (x)$ is a solution:
Lemma 6
If $δ (t) \in {c l}_{T I} (s)$ and $f v (s) = \emptyset$ , there are no abstract values occurring in $t$ , and $δ$ is an abstraction substitution, then $m a t c h (t, s) = {θ}$ for some $θ$ such that for all variables $x$ , if $x \in f v (t)$ then $δ (x) \in θ (x)$ , and if $x \notin f v (t)$ then $θ (x) = O C C$ .
Example 10
Assume that the term implication graph is as in Example 8. Consider then the following calculation by the $m a t c h$ function: Here the terms and are indeed equal to the term modulo term implication. As explained in Example 8, this will lead to two abstraction substitutions that map the term $f (X, X)$ into the term modulo term implication, namely and .

This concludes our explanation of the two functions that are based on the Axiom rule of the $⊢_{c}$ relation: For a term $t$ from a $r e c e i v e$ -step and a fixed point $F P$ the function $m a t c h$ allows us to calculate the abstraction substitutions $δ$ such that $δ (t) \in {c l}_{T I} (F P)$ , or in other words, the abstraction substitutions $δ$ such that $δ (t)$ can be derived from $F P$ using the Axiom rule.

As promised, we will now introduce a function $r c v c o n s t r s$ that combines the Axiom and Compose rules. This function works by matching terms in $r e c e i v e$ -steps, possibly containing variables, with ground terms derivable from the fixed point. The idea is that by inspecting the terms $t_{1}, \dots, t_{n}$ from the $r e c e i v e$ -steps and comparing them to the terms derivable from the fixed point we will be able to see what the variables in $t_{1}, \dots, t_{n}$ could be instantiated to if all terms $δ (t_{1}), \dots, δ (t_{n})$ are to be terms derivable from the fixed point. This is illustrated by the following example:
Example 11
Consider a transaction receiving the set of terms ${c_{p u b}, X, f_{p r i v 2} (X, Y), f_{p u b 2} (f_{p r i v 1} (X), Y)},$ where $c_{p u b}$ is a public constant, $f_{p r i v 1}$ and $f_{p r i v 2}$ are private functions, and $f_{p u b 2}$ is a public function.

Assume that we have the following fixed point:

Assume also, for the sake of simplicity, that there are no analysis rules. Then this fixed point is clearly analyzed because all messages that the intruder can derive from $F P$ using $⊢$ can also be derived using $⊩_{c}$ . We will now investigate whether each of the received terms matches a term derivable from the fixed point, and additionally determine for the variables $X$ and $Y$ the set of possible abstract values. The first step is to compute $m a t c h (t, s)$ for every term $t$ in the received messages and every term $s$ in the fixed point. Additionally, if $t = f (t_{1}, \dots, t_{n})$ for a public $f$ such as $f_{p u b 1}$ , then we recursively check each $m a t c h (t_{i}, s)$ (for every $s$ in the fixed point) since the intruder can then apply $f$ to the respective instances of $t_{i}$ to generate an instance of $t$ that matches. We summarize this in Table 1.
Table 1.
Matching received terms with terms derivable from the fixed point.

Consider the row for $c_{p u b}$ . The term $c_{p u b}$ is immediately derivable using the Comp rule and this is the case with any replacement of $X$ or $Y$ in the term $c_{p u b}$ because these variables do not occur in $c_{p u b}$ . Consider the row for $X$ . For this to be a derivable abstract value, it needs to be some abstract value in $F P$ , that is, either or . Consider the row for $f_{p r i v 2} (X, Y)$ . Since $f_{p r i v 2}$ is private, we cannot derive it by composition, and so the only option is to use the two matching terms in the fixed point. Consider the row for $f_{p u b 2} (f_{p r i v 1} (X), Y)$ . No term in $F P$ matches it, but two matching terms can be constructed from the fixed point using the Comp rule.

Let us now construct the abstraction substitutions that map the variables in such a way that all the received terms are terms derivable from the fixed point. For $X$ , we thus need to pick the abstract values that appear in all cells in the “Replace $X$ with” column. In this case, there is only one such abstract value, namely . For $Y$ , we can pick or . This leads to two possible abstraction substitutions: and .
Example 12
Consider a transaction receiving the set of terms ${f_{p r i v 2} (X, Y)}$ , where $f_{p r i v 2}$ is a private function. Consider the fixed point and $T I = \emptyset$ . Assume also, for the sake of simplicity, that there are no analysis rules. We apply the approach from Example 11. Thus, both $X$ and $Y$ can be or , and thus we get four possible abstraction substitutions, namely , , and . Notice that we see here that an overapproximation is happening because actually only the first two abstraction substitutions will generate terms represented by the fixed point. We will tolerate this overapproximation.

The function $r c v c o n s t r s$ implements the idea from Examples 11 and 12. The function ${r c v c o n s t r s}_{x} (M)$ computes the set of abstract values that the variable $x$ can take so that the intruder can produce all terms in the set $M$ . This set is empty in case the intruder cannot produce all the terms in $M$ (for any choice of $x$ ). We will use this for a transaction $T$ that has the terms $M$ as receive steps and $x$ is any free variable in $T$ .
Definition 15
Let $M \neq \emptyset$ be a set of messages, $x$ be a variable, and $F P = (F P, T I)$ be an analyzed fixed point. We define ${r c v c o n s t r s}_{x} (M)$ recursively as follows:
$\begin{aligned} \begin{aligned} {r c v c o n s t r s}_{x} ({y}) = & {b ∣ \exists a \in F P \cap A . (a, b) \in {T I}^{}} & if x = y, \\ {r c v c o n s t r s}_{x} ({y}) = & O C C & if x \neq y, \\ {r c v c o n s t r s}_{x} ({c}) = & \emptyset & if c \in C_{p r i v} and c \notin F P, \\ {r c v c o n s t r s}_{x} ({c}) = & O C C & if c \in C_{p u b} or c \in F P, \\ {r c v c o n s t r s}_{x} ({f (t_{1}, \dots, t_{n})}) = & A & if f \in Σ_{p r i v}^{n}, n > 0, \\ Δ = m a t c h (f (t_{1}, \dots, t_{n}), F P), \\ A = ⋃_{δ \in Δ} δ (x), \\ {r c v c o n s t r s}_{x} ({f (t_{1}, \dots, t_{n})}) = & A_{1} \cup A_{2} & if f \in Σ_{p u b}^{n}, n > 0, \\ Δ = m a t c h (f (t_{1}, \dots, t_{n}), F P), \\ A_{1} = ⋃_{δ \in Δ} δ (x), \\ A_{2} = {r c v c o n s t r s}_{x} ({t_{1}, \dots, t_{n}}), \\ {r c v c o n s t r s}_{x} ({t_{1}, \dots, t_{n}}) = & ⋂_{i \in {1, \dots, n}} {r c v c o n s t r s}_{x} ({t_{i}}) & if n > 1. \end{aligned} \end{aligned}$

The definition of ${r c v c o n s t r s}_{x} (M)$ expresses how the requirement that the intruder has to produce the messages in $M$ constrains the choice of abstract values of $x$ . The first equation says that if $y = x$ is the message the intruder has to produce, we can choose for $x$ only abstract values that are in the fixed point or reachable via term implication. The second equation is the case where the intruder has to produce any other variable $x \neq y$ . In this case, this gives no constraint on $x$ , and we have thus $O C C$ . The third equation says that the intruder cannot produce a private constant that is not in the fixed point. The fourth equation says that the intruder can always produce all public constants and all constants in the fixed point, again not constraining the choice of $x$ . The fifth equation says that if the intruder has to produce a term $f (t_{1}, \dots, t_{n})$ that is composed of a private function then we use the $m a t c h$ function to determine all the mappings $Δ$ that map variables to set of abstract values under which said term is in the fixed point modulo term implication. We then return the union $A$ of all abstract values that any of these mappings allow for $x$ . The sixth equation is similar, but here $f$ is public, so we additionally consider the case that the intruder can produce the subterms $t_{1}, \dots, t_{n}$ (and apply $f$ to them), so we have the union of the values $A_{1}$ that give a direct match in the fixed point with the values $A_{2}$ under which the subterms can be produced. The final equation lifts ${r c v c o n s t r s}_{x}$ to sets of terms: to produce all the terms, the intruder must produce every single one of them.

In our implementation, we have one small optimization not presented above to avoid cluttering the presentation here. Consider again the sixth equation. If one of the $t_{i}$ is a private constant not in $F P$ , then we can “short circuit” the calculation of ${r c v c o n s t r s}_{x} ({t_{1}, \dots, t_{n}})$ because we then know that it will be equal to $\emptyset$ .

In Example 11, we saw how calculating the possible replacements for each variable related to the abstraction substitutions that instantiate the received terms to derivable terms. We express this idea in the following lemma that captures the idea of $r c v c o n s t r s$ :
Lemma 7
Let $T$ be a transaction with at least one $r e c e i v e$ -step, $F P = (F P, T I)$ be a fixed point where $F P$ is analyzed, $x \in f v (T)$ , $δ$ be an abstraction substitution with domain $f v (T)$ , and let $t_{1}, \dots, t_{n}$ be the terms occurring in the $r e c e i v e$ -steps of $T$ . If $F P ⊩_{c}^{T I} δ ({t_{1}, \dots, t_{n}})$ then $δ (x) \in {r c v c o n s t r s}_{x} ({t_{1}, \dots, t_{n}})$ .

This lemma essentially says that if there is an abstraction substitution that will instantiate a set of received terms to terms that the intruder can actually derive, then the application of that abstraction substitution to any variable $x$ will indeed be one of the abstract values that ${r c v c o n s t r s}_{x}$ calculates.

The following examples illustrate the idea:
Example 13
We here return to Example 11 and now apply the ${r c v c o n s t r s}_{X}$ and ${r c v c o n s t r s}_{Y}$ functions: We see that this corresponds to the choices for $X$ and $Y$ that we saw in Example 11. As in that example, this leads to two possible abstraction substitutions, namely and .
Example 14
We here return to Example 12 and now apply the ${r c v c o n s t r s}_{X}$ and ${r c v c o n s t r s}_{Y}$ functions: We see that this corresponds to the choices for $X$ and $Y$ that we saw in Example 12. As in that example, this leads to four possible abstraction substitutions, namely , , , and . We see again here that an overapproximation is happening because actually only the first two abstraction substitutions will generate terms represented by the fixed point.

We combine the techniques described from Section 6 up to here into an implementation of the coverage check that we denote the Receive coverage check.

This section demonstrates how the Isabelle formalization allows for describing different strategies in order to prove to Isabelle that the computed fixed point covers the transactions. Indeed, as part of such arguments, we show in Isabelle that the strategy is sound, such as in Lemma 7. Proving such theorems means that we do not need to be suspicious of implementation bugs even if a strategy gives significant improvements on some examples. The strategies can often negotiate an efficient solution between different extremes. For instance, not considering the messages the intruder needs to produce (F1) leads to an unnecessarily large set of abstractions to consider, while computing the precise set of abstractions that satisfy (F1) would often waste a lot of time on an optimization that is just not worth it (or it may even be undecidable). While we here used our intuition and experience with examples, in general, an extensive study of different variants on a larger benchmark suite could allow for further improvements.
7. Experimental results

In this section, we discuss empirical results. We start by introducing our main benchmark suite for individual protocols and discussing the performance of our tool, PSPSP, on this benchmark suite. Finally, we discuss an example of a composed protocol.

7.1. Our benchmark suite

We evaluated our tool, PSPSP, using the following protocols (see Table 2): The first group of protocols is based on a keyserver. The example KS_ $h$ _ $d$ is our keyserver running example for $h$ honest agents and $d$ dishonest agents. [We verify here a generalized version of the keyserver example (as compared to the running example): we include dishonest agents who can participate in the protocol. This also requires that agents maintain a set of deleted keys, because otherwise the abstraction $\emptyset$ leads to false attacks.] The example KS_Comp_ $h$ _ $d$ with $h$ honest agents and $d$ dishonest agents is inspired by Hess et al.¹³ where another keyserver protocol—named KS2_ $h$ _ $d$ here—runs in parallel on the same network and where databases are shared between the protocols.

Table 2.
Runtime measurements (time format: hh:mm:ss) experiments that took longer than 12 hours are marked with “-- : -- : --.”

Verification

Initialization Fixed point Safe check NBE check Eval check

Protocol Transl. Setup Comp. |FP| |TI| Default Receive Default Receive Default Receive Heuristic

KS_ $2$ _ $1$ 00:00:03 00:00:27 00:00:03 13 28 00:00:28 00:01:07 00:00:19 00:00:15 00:00:14 00:00:12 00:00:46

KS_ $3$ _ $1$ 00:00:04 00:00:26 00:00:03 17 41 00:00:40 00:03:02 00:00:21 00:00:18 00:00:16 00:00:12 00:01:01

KS_ $4$ _ $1$ 00:00:04 00:00:26 00:00:03 21 54 00:01:29 00:07:58 00:00:20 00:00:26 00:00:14 00:00:13 00:01:52

KS2_ $2$ _ $1$ 00:00:04 00:00:27 00:00:03 11 5 00:00:30 00:00:29 00:00:17 00:00:15 00:00:13 00:00:13 00:00:46

KS2_ $3$ _ $1$ 00:00:04 00:00:28 00:00:04 14 7 00:00:43 00:00:40 00:00:19 00:00:16 00:00:16 00:00:13 00:01:00

KS2_ $4$ _ $1$ 00:00:04 00:00:28 00:00:03 17 9 00:00:55 00:01:05 00:00:20 00:00:18 00:00:15 00:00:15 00:01:14

KS_Comp_ $2$ _ $1$ 00:00:05 00:00:27 00:00:04 22 108 00:07:35 00:47:07 00:00:50 00:01:52 00:00:16 00:00:14 00:07:49

KS_Comp_ $3$ _ $1$ 00:00:05 00:00:27 00:00:06 29 156 00:33:57 03:16:32 00:02:13 00:06:13 00:00:19 00:00:14 00:33:21

KS_Comp_ $4$ _ $1$ 00:00:05 00:00:25 00:00:10 36 204 01:44:22 10:18:07 00:06:08 00:16:19 00:00:26 00:00:16 01:45:54

NSLclassic 00:00:03 00:00:26 00:00:03 35 6 00:03:15 00:03:06 00:00:20 00:00:18 00:00:32 00:00:14 00:03:28

NSPKclassic 00:00:04 00:00:28 00:00:03 16 6 attack attack attack attack attack attack attack

PKCS#11_3 00:00:06 00:00:36 00:00:08 8 4 attack attack attack attack attack attack attack

PKCS#11_7 00:00:06 00:00:37 00:00:26 13 30 attack attack attack attack attack attack attack

PKCS#11_9 00:00:05 00:00:37 00:00:12 40 20 attack attack attack attack attack attack attack

TLS12_auth_simp 00:00:08 00:00:34 00:00:07 40 20 -- : -- : -- 04:23:08 01:31:14 00:03:05 00:00:38 00:00:30 04:30:37

Logos 00:00:07 00:00:37 00:00:14 48 31 -- : -- : -- 11:01:55 01:38:56 00:36:29 00:01:23 00:01:07 11:13:23

TLS12_SSO 00:00:13 00:00:26 00:15:25 359 35 -- : -- : -- -- : -- : -- 02:58:21 04:49:35 00:00:37 00:00:23 -- : -- : --

			Verification
KS_ $2$ _ $1$	00:00:03	00:00:27	00:00:03	13	28	00:00:28	00:01:07	00:00:19	00:00:15	00:00:14	00:00:12	00:00:46
KS_ $3$ _ $1$	00:00:04	00:00:26	00:00:03	17	41	00:00:40	00:03:02	00:00:21	00:00:18	00:00:16	00:00:12	00:01:01
KS_ $4$ _ $1$	00:00:04	00:00:26	00:00:03	21	54	00:01:29	00:07:58	00:00:20	00:00:26	00:00:14	00:00:13	00:01:52
KS2_ $2$ _ $1$	00:00:04	00:00:27	00:00:03	11	5	00:00:30	00:00:29	00:00:17	00:00:15	00:00:13	00:00:13	00:00:46
KS2_ $3$ _ $1$	00:00:04	00:00:28	00:00:04	14	7	00:00:43	00:00:40	00:00:19	00:00:16	00:00:16	00:00:13	00:01:00
KS2_ $4$ _ $1$	00:00:04	00:00:28	00:00:03	17	9	00:00:55	00:01:05	00:00:20	00:00:18	00:00:15	00:00:15	00:01:14
KS_Comp_ $2$ _ $1$	00:00:05	00:00:27	00:00:04	22	108	00:07:35	00:47:07	00:00:50	00:01:52	00:00:16	00:00:14	00:07:49
KS_Comp_ $3$ _ $1$	00:00:05	00:00:27	00:00:06	29	156	00:33:57	03:16:32	00:02:13	00:06:13	00:00:19	00:00:14	00:33:21
KS_Comp_ $4$ _ $1$	00:00:05	00:00:25	00:00:10	36	204	01:44:22	10:18:07	00:06:08	00:16:19	00:00:26	00:00:16	01:45:54
NSLclassic	00:00:03	00:00:26	00:00:03	35	6	00:03:15	00:03:06	00:00:20	00:00:18	00:00:32	00:00:14	00:03:28
NSPKclassic	00:00:04	00:00:28	00:00:03	16	6	attack	attack	attack	attack	attack	attack	attack
PKCS#11_3	00:00:06	00:00:36	00:00:08	8	4	attack	attack	attack	attack	attack	attack	attack
PKCS#11_7	00:00:06	00:00:37	00:00:26	13	30	attack	attack	attack	attack	attack	attack	attack
PKCS#11_9	00:00:05	00:00:37	00:00:12	40	20	attack	attack	attack	attack	attack	attack	attack
TLS12_auth_simp	00:00:08	00:00:34	00:00:07	40	20	-- : -- : --	04:23:08	01:31:14	00:03:05	00:00:38	00:00:30	04:30:37
Logos	00:00:07	00:00:37	00:00:14	48	31	-- : -- : --	11:01:55	01:38:56	00:36:29	00:01:23	00:01:07	11:13:23
TLS12_SSO	00:00:13	00:00:26	00:15:25	359	35	-- : -- : --	-- : -- : --	02:58:21	04:49:35	00:00:37	00:00:23	-- : -- : --

The next groups are NSLclassic and NSPKclassic, which are based on the NSL and Needham–Schroeder protocol specifications shipped with AIF- $ω$ .¹⁵

Then, we have several scenarios of the “PKCS#11” model that is distributed with AIF- $ω$ .¹⁵ Scenarios 3 and 7 (PKCS#11_3 and PKCS#11_7) are examples of another flavor of stateful protocols, namely security tokens that can store keys and perform encryption and decryption, and with which the intruder can interact through an application programming interface (API). Generally, modeling such tokens and their APIs works quite well with the set-based abstraction. There is a third scenario (PKCS#11_9) that is marked as correct in the AIF- $ω$ distribution, but that is actually due to a mistake that our attempt to verify it in Isabelle has revealed. We discuss this example in more detail in the Appendix. This illustrates our main point that there can be surprises when one tries to verify in Isabelle the results of automated tools.

With TLS12_auth_simp, we have looked at one protocol that has been inspired by a practical protocol, that is, transport layer security (TLS) 1.2. For our experiments, we simplified the protocol by modeling only one variant of the flow and also simplifying the hashing.

Finally, we modeled a protocol developed by the Danish company Logos and a single sign-on protocol (TLS12_SSO) that composes the TLS key exchange with a custom SSO protocol. We will discuss TLS12_SSO in Section 7.3 and the industrial case study (Logos) in Section 9.

7.2. Evaluation of our benchmark suite

Table 2 shows the fixed point sizes of various example protocols together with measurements of the elapsed real time it takes to generate and verify the Isabelle specifications. All experiments have been conducted on a shared Linux server with an Intel Xeon E5-2640 CPU and 96 GB main memory using PSPSP based on Isabelle 2024. PSPSP provides an option to measure the elapsed time (wall-clock) required for executing individual “top-level” commands (e.g., protocol_security_proof, see Section 8). We only report the times that are specific to the individual protocols using a “pre-compiled” session that contains our generic protocol translator as well as the protocol-independent formalizations and proofs. First, we report the time for translating the protocol specifications into Isabelle/HOL (translation), the time for showing that the given protocol is an instance of the formal protocol model (setup), and the time for computing the fixed point and its size. [This includes the time for parsing the trac specification and, more importantly, the generation of the conservative HOL definitions.] In the next six columns, we report the run-time of four different strategies for the security proof that we will explain in the following. The last column reports the run-time of a heuristic that aims to select the fasted strategy automatically. We will explain the details of this heuristic later.

In the safe configuration, all proof steps are checked by Isabelle’s LCF-style kernel; internally, this makes use of the simplifier configuration called code-simp of Isabelle’s simplifier. NBE employs normalization by evaluation, a technique that uses a partially symbolic evaluation approach that, to a limited extent, relies on Isabelle’s code generator. Finally, eval is an approach that directly employs the code generator and internally uses the proof method eval. In general, the configurations NBE and eval require the user to trust the code generator. From a correctness perspective, the main difference is that the configuration of the code generator used by NBE is very small and cannot be changed by Isabelle users. Hence, this configuration can be easily audited manually and, moreover, is thoroughly tested. In contrast, eval uses a user-configurable configuration of the code generator and, hence, is hard to audit, and any theory our work depends on could, potentially, have modified this configuration. While Isabelle’s code generator is thoroughly tested, it is not formally verified. While, at the end, it is up to the user to decide which approach to use, we consider NBE to be a trustworthy configuration. [Interested users should consult²⁹ to understand the software stack that needs to be trusted for each configuration.] Furthermore, a pragmatic approach is to use eval during the development (specification) of the protocol and only after no attacks are found, switching to NBE or safe for a higher level of trust.

For the first three strategies, we report the time of our default version of the coverage check (Default), which implements the improvements described in Section 6 up to and including Section 6.2. We also report the time of our alternative version of the coverage check (Receive), which also implements these improvements in addition to the further restriction of the number of abstraction substitutions described in Section 6.3. There is a fourth strategy, called Heuristic, that automatically selects the faster coverage check in the configuration Safe. We will explain its details at the end of this section.

For all our examples, verification times, using the eval check (i.e., making full use of Isabelle’s code generator), are at most 1 1/2 minutes. [We do not report runtimes for protocols with an attack. After the fixed point computation, checking for an attack takes less than a second, as we only need to check for the presence of the $a t t a c k$ constant. We will discuss the presentation of attack traces for such protocols in Section 8.] This makes this configuration ideal for interactive development, for example, while refining a protocol specification. In contrast, the verification using only Isabelle’s simplifier can take more than 12 hours (we record runtimes of more than 12 hours as $- - : - - : - -$ ) for our example protocols. Thus, in most cases, this configuration will be used in “batch-mode” after the protocol has been checked using the configuration employing the code generator. For most protocols, NBE provides a good middle ground, bringing the verification times down to under a minute for most examples, and below 40 minutes for all examples using the fastest variant of the coverage check.

Furthermore, the Receive coverage check introduced in Section 6.3 significantly reduces the safe verification time for TLS12_auth_simp and Logos in safe mode from over 12 hours to around 4 1/2 (TLS12_auth_simp) and around 11 hours (Logos). For NBE, it reduces the runtime for both protocols from around 1 1/2 hours to 3 minutes (TLS12_auth_simp), respectively, and around 40 minutes (Logos). For the configuration fully relying on code generation (eval), the improvements are minor.

Comparing the runtime of the two coverage checks for all examples shows that the relative runtime behavior of the two coverage checks seems not to depend on the simplification strategy (i.e., eval, NBE, and safe). This motivated us to implement a heuristic that, first, runs the security proof for NBE for both coverage checks in parallel, measures their runtime, and then runs the Safe strategy using the coverage check that, for the given protocol, was faster for NBE. We have chosen NBE as the basis, as the runtimes for eval for both coverage checks are often very similar and, hence, cannot provide a solid base measurement. In theory, this heuristic should show a runtime behavior that roughly is the maximum of the runtime of the two coverage checks for NBE, plus the runtime for the faster coverage check in a safe configuration. Our measurements (last column in Table 2) do confirm this behavior for our example protocols. This makes our heuristic a reliable way for automatically selecting the faster coverage check.

Finally, as mentioned at the beginning of this section, we report the elapsed time in Table 2 and not the total CPU time. On average, the security proof using the default coverage check can run certain parts in parallel, resulting (in our benchmark suite) on an average speedup of 2.5. The Receive coverage check cannot be parallelized that well (having an average speedup of 1.3).

7.3. An example of protocol composition

Table 3 shows the runtimes for an example of a protocol composition, implementing a TLS-based single sign-on (TLS12_SSO). Note that the format of the table differs from Table 2: we report the runtimes for the three different verification checks (safe, NBE, and eval) on three separate lines. For each of these checks, we report the running time for the initialization and the fixed point computation (as well as its size) for each subprotocol (i.e., TLS and SSO). These aspects are the same for all three verification checks, as their implementation does not make use of the optimizations provided by the code generator. Next, we report the runtimes (as in Table 2 for both coverage checks) for the individual verification of the two subprotocols. The final column reports the runtime for the proof that the composition of the two sub-protocols is secure. Here, “-- : -- : --” denotes that the check takes more than 12 hours. Notably, the security verification of the individual protocols takes significantly longer than the proof that the composition of the two protocols is secure. For instance, the security proof for SSO takes several hours using the NBE check (the safe check takes more than 12 hours), while the proof that the composition of the two protocols (TLS and SSO) is secure only takes a few seconds.

Table 3.
Runtime measurements (time format: hh:mm:ss) for the composed protocol TLS12_SSO.

Verification

Initialization Fixed point (TLS) Fixed point (SSO) TLS SSO

Check Trans. Setup Comp. |FP| |TI| Comp. |FP| |TI| Default Receive Default Receive Composition

Safe check 00:00:13 00:00:30 00:00:05 25 16 00:07:57 202 38 00:04:57 00:10:24 -- : -- : -- -- : -- : -- -- : -- : --

NBE check 00:00:13 00:00:30 00:00:05 25 16 00:07:57 202 38 00:00:41 00:00:46 02:18:27 01:59:03 00:00:12

Eval check 00:00:13 00:00:30 00:00:05 25 16 00:07:57 202 38 00:00:20 00:00:15 00:00:18 00:00:10 00:00:04

			Verification
Safe check	00:00:13	00:00:30	00:00:05	25	16	00:07:57	202	38	00:04:57	00:10:24	-- : -- : --	-- : -- : --	-- : -- : --
NBE check	00:00:13	00:00:30	00:00:05	25	16	00:07:57	202	38	00:00:41	00:00:46	02:18:27	01:59:03	00:00:12
Eval check	00:00:13	00:00:30	00:00:05	25	16	00:07:57	202	38	00:00:20	00:00:15	00:00:18	00:00:10	00:00:04

TLS: transport layer security; SSO: Single-Sign-On.

More importantly, the total runtime of the fastest NBE configuration is roughly two hours, compared to 3 h 15 min 25 s for directly verifying the monolithic TLS12_SSO protocol model using the default coverage check (cf. Table 2). The compositional verification takes only 2 h 8 min 41 s in total using the default coverage check for the TLS component and the receive coverage check for the SSO component (see Table 3). [Using the receive coverage check for both components increases the total runtime only by 5 s.]

Finally, note that the TLS protocol used in this composition case study focuses only on the core of TLS: the key exchange. In contrast, TLS12_auth_simp in Table 2 also includes the password authentication and the transmission of some dummy data. This explains the difference in runtimes (and fixed point sizes) between these two versions of TLS.

8. Isabelle/PSPSP

We implemented our approach on top of the Isabelle framework,³⁰ resulting in a tool called Isabelle/PSPSP,¹⁸ which is now part of the AFP [As part of the AFP, PSPSP will be maintained and, for instance, ported to the latest official release of Isabelle.] This includes a formalization of the protocol model in Isabelle/HOL, a data type package that provides a domain-specific language (called trac) for specifying security protocols, and fully automated proof support.

8.1. The architecture of Isabelle/PSPSP

For our implementation of Isabelle/PSPSP, we make use of the fact that Isabelle is not only an interactive theorem prover; it also provides an extensible framework for developing formal methods tools.³¹

Figure 1 shows an overview of the Isabelle architecture, highlighting in green the additions provided by Isabelle/PSPSP. In particular:

Protocol formalization: PSPSP is built on, and re-uses, our stateful protocol formalization (and its typing results) formalized in Isabelle/HOL. This part is available as a stand-alone AFP entry,³² consisting of $\sim 20, 000$ lines of code. The formalization presented in this paper, formalizing the presented method for the automated verification of security protocols, adds another $25, 000$ lines of code.¹⁸ Note that these formalizations (proofs and definitions) are reusable, that is, independent of any concrete security protocol.

Automated proof support (PSPSP methods): We developed several proof methods using both Isabelle’s high-level proof development language Eisbach³³ and the Isabelle/ML interface. Isabelle/ML is Isabelle’s programming API that allows one to extend Isabelle using the SML³⁴ programming language. We use this, in particular, for computing fixed point that builds the backbone of our automation.

Support for trac: To improve the user-friendliness of PSPSP, we defined a trace-based specification language for security protocols, called trac. By supporting trac as input language, we allow users to use PSPSP without the need to understand all the details of our protocol formalization. Actually, users of PSPSP mostly need to understand trac, and our new Isabelle commands for verifying security protocols. Supporting trac requires a parser for trac (implemented in Isabelle/ML) and implementing an encoder (or datatype package) that translates trac into the corresponding HOL definitions. Furthermore, the trac datatype package also proves automatically a number of basic properties that are used within the actual security proof.

It is noteworthy that all our additions have been implemented in a logically safe way, that is, a bug in our implementation cannot result in an insecure protocol being successfully verified: any bug could only result in PSPSP not being able to verify a secure protocol.

Figure 1.

The system architecture of Isabelle and Isabelle/PSPSP.

8.2. Isabelle/PSPSP—A guided tour

Figure 2 shows the Isabelle IDE (called Isabelle/jEdit). The upper part of the window is the input area that works similarly to a programming IDE, that is, supporting auto completion, syntax highlighting, and automated proof generation and interactive proof development. The lower part shows the current output (response) with respect to the cursor position. In more detail, Figure 2 shows the specification and the fully automated verification of a toy keyserver protocol:

The protocol is specified using the domain-specific language trac that, for example, could also be used by a security protocol model checker (lines 8–58). Our implementation automatically translates this specification into a family of formal HOL definitions. Moreover, basic properties of these definitions are also already proven automatically (i.e., without any user interaction): for this simple example, already over 350 theorems are automatically generated.

Next (line 61), our implementation automatically shows that the protocol satisfies the requirement of our model (technically, this is done by instantiating several Isabelle locales, resulting in another 1750 theorems “for free”).

In line 62, we compute the fixed point. We can use Isabelle’s value command (line 74) to inspect its size.

After these steps, all definitions and auxiliary lemmas for the security proof are available. We can now perform a fully automated proof (line 64). The top-level command protocol_security_proof proves automatically a theorem showing the security of the defined protocol. This successful proof took

\sim 48

s (see lower part of the Isabelle/jEdit window).

Figure 2.

Using Isabelle/PSPSP for verifying a keyserver protocol (KS2_ $2$ _ $1$ ).

Moreover, for the security proofs, we have also manual variants (e.g., manual_protocol_setup, manual_protocol_security_proof, or manual_protocol_composition_proof) of the automated proof commands that only create a proof obligation (i.e., establish the proof state) allowing the user to do an interactive proof utilizing the full power of Isabelle, instead of using the automated proof methods provided by us. [The commands still allow the user to copy the automated proof script, using “point-and-click” in the same way as the default sledgehammer tool, into the theory file.] This is potentially useful for introducing protocol-specific optimizations or for inspecting what the automated proof methods do.

In case of an insecure protocol, that is, the fixed point containing the $a t t a c k$ constant, Isabelle/PSPSP can support the protocol developer with an attack trace: optionally, while computing the fixed point, the computed traces are bound to a logical constant, which can then be printed in a user-friendly way. Figure 3 shows an example for the protocol PKCS#11_3: the proof that the $a t t a c k$ constant is contained in the fixed point (line 95) usually takes only a few seconds. The Isar top-level command print_attack_trace (line 98) then prints an attack trace (lower part of the window in Figure 3) showing the steps executed until an attack event is created.

Figure 3.

An example attack trace (for the protocol PKCS#11_3).

8.3. Compositionality

PSPSP is part of a larger Isabelle infrastructure for security protocols that also allows for compositionality,¹ that is, for a result of the form: if two or more protocols are secure in isolation and satisfy certain requirements, then also their composition is secure, that is, when they run in parallel sharing the same network and even some sets. Especially the support for shared sets allows us to consider also complex interactions between two protocols, for instance, where one protocol negotiates keys and another protocol uses them.

The compositionality framework uses the same specification language (trac) as PSPSP. One can thus specify a set of component protocols, use PSPSP to prove the security of each of them in isolation, and use the compositionality framework to check that they fulfill the requirements for compositionality and then obtain an Isabelle proof that the composed system is secure.

As an example, we have modeled in Hess et al.,¹ a composition of TLS 1.2 and security assertion markup language (SAML) Single-Sign-On (SSO): TLS establishes a secure channel between a client and a server where the client is not yet authenticated. SSO then uses such a channel between a client and the identity provider to first authenticate the client to the identity provider (e.g., using a password); the identity provider then provides a credential for the client that the client can use to authenticate another TLS channel with a relying party. More in detail, the TLS protocol stores any exchanged keys that a client $A$ has negotiated with server $B$ in a set $c l i e n t K e y s (A, B)$ on the client side, and in the set $s e r v e r K e y s (B)$ on the server side. The latter set of keys is only parameterized over the agent name $B$ , since $A$ is not authenticated. Each of these sets reflects the local point of view of each agent, and it is part of the verification that, for instance, the intruder does not find out a key between two honest agents $A$ and $B$ . Finally, the SSO protocol can just retrieve and use these keys, both to authenticate the connection between client and server, as well as between client and identity provider (where the password is transmitted). The composed protocol is specified in the trac specification language (see Figure 4, until line 299). We compute the $S M P$ common between both protocols (lines 305–309, see Hess et al.¹ for more details) and fixed points (lines 312 and 313) for both protocols “in isolation.” These are used to prove the security of each of the two subprotocols (lines 315–318). Then we prove the security of the composition: we compute the shared secrets (line 321) and then use an automated proof method for the protocol composition proof (lines 323–237). Finally, we show the security of the composition (lines 329—340) with a simple proof “by auto.”

Figure 4.

Using Isabelle/PSPSP for verifying the composition of TLS 1.2 and SAML. TLS: transport layer security; SAML: security assertion markup language.

Note that the run time (recall Tables 2 and 3) for the TLS component of the composition is much smaller than the runtime of TLS12_auth_simp, because it is purely the key-exchange while all authentication and data-transmission is “outsourced” to the SSO protocol. Thus, in general, verification can be improved by using compositional reasoning, if one can split a complex system into smaller components.

The compositionality framework supports strictly more protocols than PSPSP; most importantly, it allows for composed messages in sets. In these cases, one cannot use PSPSP to verify the respective components, but of course, one can also consider compositions where a subset of the components is proved by PSPSP and the others are verified manually.

9. Case study: Logos

We had the opportunity to use PSPSP to formally verify a protocol by the Danish company Logos. This protocol stems from the area of reader terminals for a travel card solution, namely, to establish a secure connection between a terminal and the Logos server. The particular challenge here is that this should work after a terminal has been in storage for years and all public keys of the servers have been updated in the meantime; we do want to model the possibility that an intruder obtains old private keys—after all that is the reason for updating them regularly. Such a protocol, even though its messages are fairly simple, can be a challenge for verification tools as it requires mutable long-term states at its core. With some simplifications, we have built a model in PSPSP and found a security flaw. We then verified the protocol with PSPSP under a minor modification. Logos has applied this modification and has thus an Isabelle-verified product, one might say, although this should of course be taken with a grain of salt, given that we only verified a simplified model of the protocol (and in a black-box model of cryptography). The protocol is summarized in Figure 5, and we discuss it together with the PSPSP model of every step in the following.

Figure 5.

The Logos system in Alice-and-Bob notation.

9.1. Epochs

The abstract interpretation approach of PSPSP was originally inspired by ProVerif; both approaches essentially discard the notion of time to arrive at an overapproximation of everything that the intruder can ever know without the normal state explosion and restriction to bounded sessions. That, however, makes it challenging to model any aspect of time, such as injective agreement. However, the only aspect of time that we really need in the model of the Logos protocols is a distinction between past and present events, for example, distinguish nonces that were generated a long time ago from nonces that are fresh. More precisely, we divide the timeline into two epochs $e p o c h = {e 1, e 2}$ . We do not care about the order of events in each epoch: as a notion of time, the model only distinguishes between events that happened in $e 1$ and those that happened in $e 2$ . In this model, all events of $e 1$ happen before all events of $e 2$ .

9.2. Key generation and revocation

First, we define that the intruder can generate public–private key pairs. Note that when no epochs are mentioned, the rule can uniformly be applied in all epochs: The Logos server has a public–private key pair that is updated regularly. [In fact, there are several kinds of keys for different purposes; for simplicity, we consider only one kind of key.] We model this in PSPSP by the following two rules that can be applied in either epoch $E$ : Disregarding the epochs briefly, this simply means that the server can at every time point generate a new public–private key pair (publishing the public key) and at any time revoke one. (Like in the keyserver examples before, the knowledge of the corresponding private key $i n v (P K L)$ is implicit for honest agents like the Logos server.) In this model, the server may thus have any number of public keys at the same time; this is just an overapproximation. The fact that the set $s e r v e r_k e y s$ is parameterized over the epoch $E$ means that no key generated in the first epoch is available in the second and vice versa. Thus, the “cut” between the two epochs coincides with a key update, reflecting our intention that $e 1$ represents events that happened longer in the past while $e 2$ represents recent events.

When a batch of terminals is manufactured, each gets a unique hardware-id in $h w_i d$ . Since some sets will be parameterized over this hardware id, we need to give a finite enumeration, and we limit ourselves to two hardware-ids $h w_i d = {t 1, t 2}$ . During manufacturing, all terminals of a batch have the same public–private key pair, called the batch key, which is registered also with the Logos server, so the terminals can authenticate themselves as legitimate terminals to the Logos server later. We assume here that batch generation happens only in epoch $e 1$ , because with $e 2$ we want to model only what happens long after manufacture. Before terminals can be manufactured, we first need to create a public/private key pair, and like for the Logos server, we allow for arbitrary such events and revocation at any point as an overapproximation of several manufacturing batches that can happen in $e 1$ : Again, the corresponding private key $i n v (P K B a t c h)$ is implicit, since only the manufactured terminals would have it and are assumed to be honest. When manufactured, the terminals also have the current public key of the Logos server. This is the starting state for the Logos protocol of Figure 5.

9.3. The bootstrap protocol

Each terminal is required to run a bootstrap protocol with the server in order to establish an individual key $B K P$ . This must happen within 30 days after manufacture. We assume here that this is still within epoch $e 1$ . (Failure to run it is modeled here by the fact that the batch and/or server key can be revoked, and thus the terminal cannot do any transactions.) In the bootstrap protocol, the terminal creates a fresh key pair, consisting of the bootstrap public key $B K P$ , and the corresponding private key $i n v (B K P)$ . For now, even the public key $B K P$ is kept secret between the terminal and server. This later allows the server to send messages to the terminal that can only come from the server. This is an unusual way to employ a public key; a more conventional solution would probably be a shared symmetric key instead. However, this is how the protocol works, and we have not found a principal security problem with it (other than the attack reported below that is independent of this). This rule corresponds to sending the first message in Figure 5. Here we have modeled that the terminal knows the batch key pair and the public key of the Logos server simply by looking them up in the respective sets. We have drastically simplified the bilaterally authenticated TLS session between terminal and server, by encryption of the message with the public key $P K L$ of the server and signing by the private key of the entire batch of terminals $i n v (P K B a t c h)$ . The terminal remembers its bootstrap key $B K P$ (and implicitly the private key) in the set $b k p (T)$ . The server receives the public key $B K P$ in the following transaction and stores it in $k e y s (T)$ : This corresponds to the reception of the first message in Figure 5. The server expects a message that is encrypted with its current public key $P K L$ (and thus discards the message if decryption with the current private key failed), and then checks that the content is a signature that verifies with (one of) the current batch public keys $P K B a t c h$ (and discard the message if signature verification fails). The signed message is expected to be a pair where the first is interpreted as a hardware-id $T$ and the second as the bootstrap public key $B K P$ which the server stores in the $k e y s (T)$ , so that later a secure connection with $T$ can be established using $B K P$ . Note again that this bootstrap protocol can only be executed in epoch $e 1$ as demanded by the parameters of the server and batch key sets, but it can happen for arbitrarily many batches and updates of the server keys in $e 1$ .

9.4. The truststore protocol

The second part of the Logos protocol, in Figure 5 separated by the dotted lines, is the truststore protocol. This protocol may be executed by a terminal after it was many years in storage. This is possible in both epochs. To initiate, the terminal sends its unique hardware ID and a fresh nonce $N$ : For simplicity, we omit that this is also done via TLS: since in general neither the terminal nor the Logos server can verify the certificate of the other, this is not much better than plaintext, and so we do not bother with modeling TLS here. Also, the nonce $N$ is inserted into an epoch-specific set, in order to express the property that the terminal would not accept an answer in epoch $e 2$ with a nonce it has generated in epoch $e 1$ .

The server now receives the request, looks up the $B K P$ of the claimed $T$ , and constructs a so-called truststore message, that is, a message with the current public key of the Logos server that the terminal can verify. To this end, the server generates a new shared key $S K$ , which is inserted into a set of current shared keys $s k_k e y s$ , encrypts it with the $B K P$ of the terminal, and then authenticates the trust-store by MACing it (and the nonce $N$ ) with the $S K$ : Here, the unary function $s k$ is just a format to distinguish this message from other kinds of encrypted messages. This is the version for the case that the transaction is executed in $e 1$ . Here we actually require that $N n o t i n n o n c e (e 2)$ . This does not correspond to a check that the server does, but our model that everything in epoch $e 1$ happens before $e 2$ , and this constraint reflects that $N$ cannot come from the future.

When this transaction is happening, however, in $e 2$ , we cannot exclude that the nonce was generated in $e 1$ (e.g., the intruder replaying an old request). Thus, we have a variant of the previous rule for $e 2$ : We have also in both rules the insertion of $P K$ into the set $w i t n e s s (T, \cdot)$ . This is just for formulating the authentication goal below.

To conclude the truststore protocol, the terminal receives the truststore message from the server: Actually, we do not model here further the store of the terminal, but we have authentication goals as discussed below.

9.5. Goals

We formulate several goals by specifying again what would be an attack. First, for secrecy goals: the $B K P$ (both public and private key) are secrets, and so is the $S K$ and the private key of the terminal batch: For the receiving of the truststore, we have that it is an attack (noninjective agreement) if the terminal accepts a truststore $P K$ that was not sent like this from the Logos server (in any epoch): The injective aspect now needs the formulation with epochs: it is an attack if the terminal accepts a message in epoch $e 2$ that the server did not send in epoch $e 2$ : Together with the $n o n i n j a u t h_s e r v e r_k e y s$ , we have a goal close to injective agreement. Standard injective agreement³⁵ in this case means that, on top of the noninjective agreement, it is an attack if the terminal accepts $P K$ more often than it was sent by the server. In PSPSP, we would express this by using another set $r e q u e s t (T, E)$ and when the terminal accepts a $P K$ that is already in the set $r e q u e s t (T, E)$ , then it is an attack; otherwise, it is added to the set $r e q u e s t (T, E)$ . Thus, this means it is an attack if the same $P K$ is accepted more than once. This way of defining the goal is not suitable in this case, because during the validity of a single $P K$ it is allowed to run the truststore protocol several times, and then it is correct that the terminal in each run receives the same value $P K$ . It is in fact a limitation of our abstraction approach that we cannot really define the existence of an injective function between events.

The formulation with epochs solves this: it is an attack if the terminal accepts a value $P K$ in epoch $e 2$ that was not sent by the server in epoch $e 2$ .

9.6. The attack

Observe that in the protocol in Figure 5, we have highlighted the nonce $N$ in red. This is in fact the fixed version; the original version did not have this nonce. The goal $r e p l a y_s e r v e r_k e y s$ (without the constraint $N \in n o n c e (e 2)$ ) is the one we found violated in the original protocol. The attack on the version without nonce $N$ is the following replay attack: a terminal gets manufactured, runs bootstrap, and sometime later it runs the truststore protocol with the intruder in the middle, who records the truststore message from the server. The terminal for some reason goes into storage and then later in epoch $e 2$ it runs the truststore protocol again, where the intruder just acts as the Logos server and replies with the old truststore messages from $e 1$ , so the terminal is made to accept the old Logos keys that are long revoked and possibly compromised by the intruder.

We note that this attack is not easy for the intruder to mount, but also not unrealistic, and invalidates exactly what the protocol should achieve, the reliable update of keys. The fix with the nonce is not very expensive, and in this version, all goals of the protocol are satisfied, including the subsequent server certification of new keys generated by the terminal, which we do not show here.

The PSPSP tool can verify this specification in about a minute with the eval strategy—see Table 2.

10. Conclusion and related work

The research into automated verification of security protocols resulted in a large number of tools (e.g., Blanchet,⁶ Boichut et al.,³⁶ Chevalier and Vigneron,³⁷ Basin et al.,³⁸ and Cremers⁸). The implementation of these tools usually focuses on efficiency, often resulting in very involved verification algorithms. The question of the correctness of the implementation is not easy to answer and this is in fact one motivation for research in using LCF-style theorem provers for verifying protocols (e.g., Paulson,² Bella,³ Hess and Mödersheim²³ Butin,³⁹ Bella et al.,⁴⁰ and Bella et al.¹⁹). While these works provide a high level of assurance into the correctness of the verification result, they are usually interactive,that is, the verification requires a lot of expertise and time.

This tradeoff between the trustworthiness of verification tools and the degree of automation inspired research of combining both approaches.^5,7,20 Goubault-Larrecq⁵ considers a setting where the protocol and goal are given as a set $S$ of Horn clauses; the tool output is a set $S_{\infty}$ of Horn clauses that are in some sense saturated and such that the protocol has an attack iff a contradiction is derivable. His tool is able to generate proof scripts that can be checked by Rocq⁴¹ from $S_{\infty}$ . Meier⁷ developed Scyther-proof,⁴² an extension to the backward-search used by Scyther,⁸ which is able to generate proof scripts that can be checked by Isabelle/HOL.⁴³ Brucker and Mödersheim²⁰ integrate an external automated tool, OFMC,³⁹ into Isabelle/HOL. OFMC generates a witness for the correctness of the protocol that is used within an automated proof tactic of Isabelle.

Our work generalizes on these existing approaches for automatically obtaining proofs in an LCF-style theorem prover, first and foremost by the support for stateful protocols and thus a significantly larger range of protocols—moving away from simple isolated sessions to distributed systems with databases, or devices that have a long-term storage.

We achieve this by employing the abstraction-based verification technique of AIF,⁹ but with an important modification. The method of AIF produces a set of Horn clauses that is then analyzed with ProVerif⁶ (or SPASS⁴⁴), and the same holds true also for several similar methods for stateful protocol verification, namely StatVerif,¹⁰ Set- $π$ ,¹⁶ AIF- $ω$ ,¹⁵ and GSVerif.¹¹ Note that a set of definite Horn clauses (i.e., Horn clauses with exactly one positive literal) in first-order predicate logic always has a trivial model, because one can simply interpret all predicates as true for all arguments. Thus, if we have modeled an attack by the truth of some predicate $a t t a c k$ , then there is trivially a model of the Horn clauses where $a t t a c k$ is true. Instead, one wants to check that $a t t a c k$ does not hold true in one particular model, namely the least model corresponding to the free algebra interpretation of terms and being true for the least number of ground predicates. This least model is uniquely defined in the case of Horn clauses. This is achieved in ProVerif (and SPASS) by checking whether the Horn clauses imply $a t t a c k$ : If they do, then the attack predicate is true also in the free model. If they do not, that is, if the Horn clauses are consistent with the negation of the attack predicate, then the attack predicate is not true in all models, and in particular not in the least model. Thus, in a positive verification, the result from ProVerif is a consistent saturated set of Horn clauses. As first remarked by Goubault-Larrecq,⁵ this is not a very promising basis for a proof, as one does not get a derivation of a formula (the way SPASS for instance is often used in combination with Isabelle) but rather a failure to conclude a proof goal. The only thing one can do to verify the result is to compute it again and compare the results. Therefore, Goubault-Larrecq⁵ uses a different idea: showing that the Horn clauses and the negation of the attack predicate are consistent by trying to find some finite model and, if found, then using this finite model to generate a proof in Rocq that the Horn clauses are consistent with the negation of the attack predicate.

The limitation of Goubault-Larrecq⁵ is that it checks the protocol proofs only on the Horn clause level, that is, after a nontrivial abstraction has been applied. In order to obtain Isabelle proofs for the original unabstracted stateful protocols, we use therefore another approach: rather than Horn clauses, we directly generate a fixed point of abstract facts that occur in any reachable state. This would in fact normally not terminate on most protocols due to the intruder deduction; however, we employ here the typing result we have formalized in Isabelle¹⁴ to ensure that the fixed point is always finite, and our method is in fact guaranteed to terminate. This fixed point, if it does not contain the attack predicate, is the core of a correctness proof for the given protocol, namely as an invariant that the fixed point covers everything that can happen, and we essentially have to check that this invariant indeed is preserved by every transition rule of the protocol.

An interesting difference to previous approaches is that we do not rely on an external tool for the generation of the proof witness, but it is implemented within Isabelle itself. The reason is more of a practical than a principle matter: Computing the fixed point in Isabelle is actually not difficult and—thanks to Isabelle’s code generation—without much of a performance penalty; however, the fact that we do not rely on an external tool for the generation of the proof witness reduces the chances of synchronization and update problems (e.g., with new Isabelle versions). In fact, this work is part of the AFP (see https://www.isa-afp.org), a collection of Isabelle proofs that are kept up to date with each new version of Isabelle. This means that for each protocol that works in today’s version, it is highly likely that the proof works in future versions, because the proofs of all theorems of our (protocol-independent) Isabelle theory will be updated, and the fixed point and the checks about it do not have to change. Thus, we will also automatically benefit from all advances of Isabelle.

Another difference from previous approaches is that we do not directly generate proof scripts that Isabelle has to then check. Rather, we have a fixed set of (protocol-independent) theorems that imply that any protocol is secure if we have computed a fixed point representation that gives an upper bound of what (supposedly) can happen, and this representation passes a number of checks. These checks can either be done by generated code or entirely within Isabelle’s simplifier. Especially with the generated code, we have a substantial performance advantage, while using Isabelle’s simplifier gives the highest level of assurance since we only rely on the correctness of the Isabelle kernel. Many small practical advantages arise from the integration: We do not have an overhead of parsing proof scripts (which can be substantial for a larger fixed point). By using the internal API of Isabelle, we avoid the need for the Isabelle front-end parser to parse and type-check the fixed point (as we can directly generate a typed fixed point on the level of the abstract syntax tree). Parsing and type-checking (on the concrete syntax level) of large generated theories (as, e.g., those containing the generated fixed point) is, in fact, slow in Isabelle.²⁰

Another point is that there exists a number of protocol verification methods and results that use slightly different models. Here we actually seamlessly integrate a verification method into a rich Isabelle theory of protocols without any semantic gaps: We provide here a method that is integrated into a large framework of Isabelle theories for protocols (approximately 25,000 lines of code), in particular a typing and compositionality result. This allows, for instance, to prove manually (in the typed model) the correctness of a protocol, use our automated method to prove the correctness of a different protocol, and then compose the proof to obtain the correctness of the composition in an untyped model. This seamless integration of results without semantic gaps between tools we considered as an important benefit of this approach. Even though many protocol models are not substantially different from each other, bridging over the small differences can be very hard to do, especially in a theorem prover that prevents one from glossing over details. Our deep integration into the existing formalization of security protocols in Isabelle ensures that the same protocol model (same semantics) is used—which would otherwise require additional work (e.g., to ensure that the semantics of the protocol specified in a tool such as Scyther-proof is faithfully represented in the generated Isabelle theory).

It is, in general, desirable to have proofs that are not only machine-checked but also human-readable. A reason is that, for instance, mistakes in the specification itself (e.g., a mistake in a sent message so that it cannot be received by anybody) may lead to trivial security proofs that a human may notice when trying to understand the proof. Here, Scyther-proof has the benefit that it produces very readable Isar-style proofs; in our case, there is, however, something that is also accessible: the fixed point that was computed is actually a high-level proof idea that is often quite readable as well (see, for instance, our running example). Moreover, the entire set of protocol-independent theorems is hand-written Isar-style proofs. [To avoid trivial security proofs, one may check if all transactions can be executed. While this is a useful technique, it is, unfortunately, in general not sufficient to avoid trivial security proofs. Consider, for example, a protocol with two variants of a transaction where a participant sends out an encrypted message. In one variant, it is sent by the attacker who also adds the plain text to his knowledge, and in another variant, it is sent by an honest agent only in the encrypted form. Now, say that only the attacker’s version is wrongly specified. In this case, all rules of the protocol may be executable except for the final attack rule, but the protocol is nonetheless trivially secure because the attacker is sending out a wrong message. Thus, checking for the executability of rules is not sufficient in general to discover trivial security proofs; however, inspecting the Scyther proofs or the fixed point may save the day.]

Furthermore, our work shares a lot of conceptual similarities with Tamarin,¹² which can also be regarded as a kind of theorem prover. In fact, it was inspired by the mentioned work of Meier⁴³ that generates Isabelle proofs from the Scyther tool, but Tamarin is not based on Isabelle and has instead a specialized proving environment based on a sound and complete constraint solver. This in principle shares two very nice features of Isabelle: that there are less limitations in what can be modeled, and that a user can supply proof ideas, but it also shares the disadvantage of Isabelle: that most of the interesting proofs are not automatic. There is work on improving this situation, that is, finding more proofs automatically for Tamarin.⁴⁵ In contrast, PSPSP is, with respect to attacks on the abstract level, a complete decision procedure, assuming that users provide reasonable analysis rules that do not lead to nontermination. One concession in order to achieve this is indeed the abstraction. It ensures that protocols proved secure on the abstract level are also secure on the concrete level, but it may deem some protocols to be not secure on the abstract level due to a spurious attack. While we consider having this kind of decision procedure a selling point of PSPSP, it is worth remarking that, in practice, PSPSP may time out. Another main difference is that PSPSP is entirely formalized in Isabelle, and, as explained, does not rely on the correctness of any external tools. Also, the core of Isabelle is so well studied and used in so many projects that it can be considered more trustworthy than the specialized prover of Tamarin. On the other hand, Tamarin can support algebraic properties that we cannot at this point.

Finally, another approach that, such as Tamarin, is very much related to performing actual proofs of security protocols automatically and semiautomatically is CPSA.^46,47 Also here it might be possible to make a connection to a theorem prover, such as, Isabelle; however, the approach is even further away from our approach than Tamarin, because CPSA does not necessarily assume a closed world of transactions. Rather, it performs an enrich-by-need analysis, obtaining all ways to complete a particular scenario and thereby yielding the strongest security goals a given system would satisfy (even in the presence of other transactions). We believe it is even more challenging to integrate this kind of reasoning into a theorem prover such as Isabelle, but achievable. We like to investigate this as future work, as it could give interesting ways for an analyst to interact with the proving process and inject proof ideas.

Footnotes

Acknowledgments

For the purpose of open access, the author has applied a Creative Commons Attribution (CC BY) licence to any Author Accepted Manuscript version arising from this submission.

ORCID iD

Achim D Brucker

Funding

The authors disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was partially supported by the Horizon Europe project Trustworthy And Resilient Decentralised Intelligence For Edge Systems (TaRDIS) and the Industriens Fond project Security by Design in Digital Denmark (Sb3D).

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Appendix A. A problem with the AIF- ω specification 09-lost_key_att_countered.aifom

When we tried to model this specification from the AIF- $ω$ distribution, which is classified as secure by the AIF- $ω$ tool, we failed to prove it secure with our approach in Isabelle, and in fact, our fixed point generation was generating the $a t t a c k$ constant. Going back to the AIF- $ω$ verification, we noticed that there was a problem with the public functions, in this case, symmetric encryption and hashing. They were declared as public in the AIF- $ω$ specification, but the intruder seemed unable to make use of them and get to the attack we had obtained.

In fact, the problem was that AIF- $ω$ does not generate intruder rules for the function symbols that are declared as public, so unless the user explicitly states rules like “if the intruder knows $x$ then he also knows $h (x)$ ),” the function symbol is like a private one that the intruder cannot apply himself. When we add appropriate rules for all public function symbols to the specification, also AIF- $ω$ finds the attack.

One could argue that this is a problem of the specification (the modeler was in fact aware of this behavior); however, it can be considered a bug of AIF- $ω$ , since the keyword “public” for a function symbol at least suggests that the composition rule would be automatically included. In this sense, our Isabelle verification has revealed a mistake, in particular, one that has led to an erroneous “verification” of a flawed protocol by an automated tool. In fact, the attack is not a false positive (i.e., the original specification also has an attack).

References

Hess

Mödersheim

Brucker

. Stateful protocol composition in Isabelle/HOL. ACM Trans Privacy Sec 2023; 26: 1–36.

Paulson

. The inductive approach to verifying cryptographic protocols. J Comput Sec 1998; 6: 85–128.

Bella

. Formal correctness of security protocols. Information security and cryptography. Berlin, Heidelberg: Springer, 2007.

Paulson

. Inductive analysis of the internet protocol TLS. ACM Trans Inform Syst Sec 1999; 2: 332–351.

Goubault-Larrecq

. Towards producing formally checkable security proofs, automatically. In: 2008 21st IEEE computer security foundations symposium, Pittsburgh, PA, USA, 2008, pp. 224–238.

Blanchet

. An efficient cryptographic protocol verifier based on Prolog rules. In: Computer Proceedings. 14th IEEE Computer security foundations workshop, 2001, Cape Breton, NS, Canada, 2001, pp.82–96.

Meier

Cremers

Basin

. Efficient construction of machine-checked symbolic protocol security proofs. J Comput Sec 2013; 21: 41–87.

Cremers

. Scyther: Semantics and verification of security protocols. PhD Thesis, Eindhoven University of Technology, 2006.

Mödersheim

. Abstraction by set-membership: verifying security protocols and web services with databases. In: Proceedings of the 17th ACM conference on computer and communications security (CCS'10), 2010, pp. 351–360. New York, NY: Association for Computing Machinery.

10.

Arapinis

Phillips

Ritter

, et al. Statverif: Verification of stateful processes. J Comput Sec 2014; 22: 743–821.

11.

Cheval

Cortier

Turuani

. A little more conversation, a little less action, a lot more satisfaction: Global states in ProVerif. In: 2018 IEEE 31st Computer security foundations symposium (CSF), Oxford, UK, 2018, pp.344–358.

12.

Meier

Schmidt

Cremers

, et al. The TAMARIN prover for the symbolic analysis of security protocols. In: Computer aided verification, 2013, pp.696–701.

13.

Hess

Mödersheim

Brucker

. Stateful protocol composition. In: Lopez J, Zhou J, Soriano M, eds. Computer security. ESORICS 2018. Lecture Notes in Computer Science, vol 11098. Cham: Springer, 2018.

14.

Hess

Mödersheim

. A typing result for stateful protocols. In: 2018 IEEE 31st computer security foundations symposium (CSF), Oxford, UK, 2018, pp.374–388.

15.

Mödersheim

Bruni

. AIF-

ω

: set-based protocol abstraction with countable families. In: Piessens F and Viganò L (eds) Principles of security and trust. POST 2016. Lecture Notes in Computer Science, vol 9635. Berlin, Heidelberg: Springer, 2016.

16.

Bruni

Mödersheim

Nielson

, et al. Set-

π

: set membership p-calculus. In: Proceedings of the 2015 IEEE 28th computer security foundations symposium (CSF'15), USA, 2015, pp.185–198. IEEE Computer Society.

17.

Hess

Mödersheim

Brucker

, et al. Performing security proofs of stateful protocols. In: 2021 IEEE 34th computer security foundations symposium (CSF), Dubrovnik, Croatia, 2021, pp. 1–16.

18.

Hess

Mödersheim

Brucker

, et al. Automated stateful protocol verification. Archive of Formal Proofs, Formal Proof Development, http://isa-afp.org/entries/Automated_Stateful_Protocol_Verification.html (2020), accessed 18 July 2025.

19.

Bella

Massacci

Paulson

. Verifying the SET purchase protocols. J Auto Reason 2006; 36: 5–37.

20.

Brucker

Mödersheim

. Integrating automated and interactive protocol verification. In: Formal aspects in security and trust, 2009, pp.248–262.

21.

Chrétien

Cortier

Dallon

, et al. Typing messages for free in security protocols. ACM Trans Comput Logic 2020; 21: 1:1–1:52.

22.

Almousa

Mödersheim

Modesti

, et al. Typing and compositionality for security protocols: A generalization to the geometric fragment. In: Pernul G, Y A Ryan P, Weippl E (eds) Computer security – ESORICS 2015. Lecture Notes in Computer Science, vol 9327. Cham: Springer.

23.

Hess

Mödersheim

. Formalizing and proving a typing result for security protocols in Isabelle/HOL. In: IEEE 30th computer security foundations symposium (CSF), Santa Barbara, CA, USA, 2017, pp.451–463.

24.

Heather

Lowe

Schneider

. How to prevent type flaw attacks on security protocols. J Comput Sec 2003; 11: 217–244.

25.

Arapinis

Duflot

. Bounding messages for free in security protocols - extension to various security properties. Inform Comput 2014; 239: 182–215.

26.

Delaune

Hirschi

. A survey of symbolic methods for establishing equivalence-based properties in cryptographic protocols. J Log Algebraic Methods Programm 2017; 87: 127–144.

27.

Comon-Lundh

Cortier

. Security properties: Two agents are sufficient. In: Programming languages and systems, 12th European symposium on programming, ESOP 2003 held as part of the joint European conferences on theory and practice of software, ETAPS 2003 (ed. P Degano), Warsaw, Poland, April 7–11, 2003, proceedings, lecture notes in computer science, vol. 2618, 2003, pp.99–113. Berlin: Springer.

28.

Comon-Lundh

Cortier

. Security properties: two agents are sufficient. Sci Comput Program 2004; 50: 51–71.

29.

Haftmann

Bulwahn

. Code generation from Isabelle/HOL theories. http://isabelle.in.tum.de/doc/codegen.pdf (2020, accessed 18 July 2025).

30.

Paulson

Nipkow

Wenzel

. From LCF to Isabelle/HOL. Formal Aspects Comput 2019; 31: 675–698.

31.

Wenzel

Wolff

. Building formal method tools in the Isabelle/Isar framework. In: Schneider K and Brandt J (eds) TPHOLs 2007. Lecture notes in computer science, vol. 4732, Berlin: Springer, 2007, pp.352–367.

32.

Hess

Mödersheim

Brucker

. Stateful protocol composition and typing. Archive of formal proofs. Formal proof development, https://isa-afp.org/entries/Stateful_Protocol_Composition_and_Typing.html (2020, accessed 18 July 2025).

33.

Matichuk

Murray

Wenzel

. Eisbach: A proof method language for Isabelle. J Auto Reason 2016; 56: 261–282.

34.

Paulson

. ML for the working programmer. 2nd ed. Cambridge, MA: USA: Cambridge University Press, 1996.

35.

Lowe

. A hierarchy of authentication specifications. In: Proceedings 10th computer security foundations workshop, Rockport, MA, USA, 1997, pp.31–44.

36.

Boichut

Héam

Kouchnarenko

, et al. Improvements on the Genet and Klay technique to automatically verify security protocols. In: Proceedings of the 3rd international workshop on automated verification of infinite states systems (AVIS'04), 2004, pp.1–11.

37.

Chevalier

Vigneron

. Automated unbounded verification of security protocols. In: Brinksma E and Larsen KG (eds) Computer aided verification. CAV 2002. Lecture Notes in Computer Science, vol 2404. Berlin, Heidelberg: Springer, 2002.

38.

Basin

Mödersheim

Viganò

. OFMC: A symbolic model checker for security protocols. Int J Inform Sec 2005; 4: 181–208.

39.

Butin

. Inductive analysis of security protocols in Isabelle/HOL with applications to electronic voting. PhD Thesis, Dublin City University, 2012.

40.

Bella

Butin

Gray

. Holistic analysis of mix protocols. In: 2011 7th international conference on information assurance and security (IAS), Melacca, Malaysia, 2011, pp.338–343.

41.

Bertot

Castéran

. interactive theorem proving and program development. Coq’Art: The calculus of inductive constructions. Texts in theoretical computer science. An EATCS series, Berlin, Heidelberg: Springer-Verlag, 2004.

42.

Meier

Cremers

Basin

. Strong invariants for the efficient construction of machine-checked protocol security proofs. In: 2010 23rd IEEE computer security foundations symposium, Edinburgh, UK, 2010, pp.231–245.

43.

Nipkow

Paulson

Wenzel

. Isabelle/HOL – A proof assistant for higher-order logic. Lecture notes in computer science. Berlin, Heidelberg: Springer-Verlag, 2002.

44.

Weidenbach

Dimova

Fietzke

, et al. SPASS version 3.5. In: Conference on automated deduction, 2009, pp.140–145.

45.

Cortier

Delaune

Dreier

, et al. Automatic generation of sources lemmas in TAMARIN: towards automatic proofs of security protocols. J Comput Sec 2022; 30: 573–598.

46.

Doghmi

Guttman

Thayer

. Searching for shapes in cryptographic protocols. In: Grumberg O and Huth M. (eds) Tools and algorithms for the construction and analysis of systems. TACAS 2007, Lecture Notes in Computer Science, vol 4424. Berlin, Heidelberg: Springer.

47.

Rowe

Guttman

Liskov

. Measuring protocol strength with security goals. Int J Inform Sec 2016; 15: 575–596.

						Verification
	Initialization		Fixed point			Safe check		NBE check		Eval check
Protocol	Transl.	Setup	Comp.	\|FP\|	\|TI\|	Default	Receive	Default	Receive	Default	Receive	Heuristic
KS_ $2$ _ $1$	00:00:03	00:00:27	00:00:03	13	28	00:00:28	00:01:07	00:00:19	00:00:15	00:00:14	00:00:12	00:00:46
KS_ $3$ _ $1$	00:00:04	00:00:26	00:00:03	17	41	00:00:40	00:03:02	00:00:21	00:00:18	00:00:16	00:00:12	00:01:01
KS_ $4$ _ $1$	00:00:04	00:00:26	00:00:03	21	54	00:01:29	00:07:58	00:00:20	00:00:26	00:00:14	00:00:13	00:01:52
KS2_ $2$ _ $1$	00:00:04	00:00:27	00:00:03	11	5	00:00:30	00:00:29	00:00:17	00:00:15	00:00:13	00:00:13	00:00:46
KS2_ $3$ _ $1$	00:00:04	00:00:28	00:00:04	14	7	00:00:43	00:00:40	00:00:19	00:00:16	00:00:16	00:00:13	00:01:00
KS2_ $4$ _ $1$	00:00:04	00:00:28	00:00:03	17	9	00:00:55	00:01:05	00:00:20	00:00:18	00:00:15	00:00:15	00:01:14
KS_Comp_ $2$ _ $1$	00:00:05	00:00:27	00:00:04	22	108	00:07:35	00:47:07	00:00:50	00:01:52	00:00:16	00:00:14	00:07:49
KS_Comp_ $3$ _ $1$	00:00:05	00:00:27	00:00:06	29	156	00:33:57	03:16:32	00:02:13	00:06:13	00:00:19	00:00:14	00:33:21
KS_Comp_ $4$ _ $1$	00:00:05	00:00:25	00:00:10	36	204	01:44:22	10:18:07	00:06:08	00:16:19	00:00:26	00:00:16	01:45:54
NSLclassic	00:00:03	00:00:26	00:00:03	35	6	00:03:15	00:03:06	00:00:20	00:00:18	00:00:32	00:00:14	00:03:28
NSPKclassic	00:00:04	00:00:28	00:00:03	16	6	attack	attack	attack	attack	attack	attack	attack
PKCS#11_3	00:00:06	00:00:36	00:00:08	8	4	attack	attack	attack	attack	attack	attack	attack
PKCS#11_7	00:00:06	00:00:37	00:00:26	13	30	attack	attack	attack	attack	attack	attack	attack
PKCS#11_9	00:00:05	00:00:37	00:00:12	40	20	attack	attack	attack	attack	attack	attack	attack
TLS12_auth_simp	00:00:08	00:00:34	00:00:07	40	20	-- : -- : --	04:23:08	01:31:14	00:03:05	00:00:38	00:00:30	04:30:37
Logos	00:00:07	00:00:37	00:00:14	48	31	-- : -- : --	11:01:55	01:38:56	00:36:29	00:01:23	00:01:07	11:13:23
TLS12_SSO	00:00:13	00:00:26	00:15:25	359	35	-- : -- : --	-- : -- : --	02:58:21	04:49:35	00:00:37	00:00:23	-- : -- : --

									Verification
	Initialization		Fixed point (TLS)			Fixed point (SSO)			TLS		SSO
Check	Trans.	Setup	Comp.	\|FP\|	\|TI\|	Comp.	\|FP\|	\|TI\|	Default	Receive	Default	Receive	Composition
Safe check	00:00:13	00:00:30	00:00:05	25	16	00:07:57	202	38	00:04:57	00:10:24	-- : -- : --	-- : -- : --	-- : -- : --
NBE check	00:00:13	00:00:30	00:00:05	25	16	00:07:57	202	38	00:00:41	00:00:46	02:18:27	01:59:03	00:00:12
Eval check	00:00:13	00:00:30	00:00:05	25	16	00:07:57	202	38	00:00:20	00:00:15	00:00:18	00:00:10	00:00:04

PSPSP: A tool for automated verification of stateful protocols in Isabelle/HOL

Abstract

Keywords

1. Introduction

Contributions

New contributions in this journal paper

2. Preliminaries

2.1. Terms and substitutions

3. Transactions

3.1. A keyserver protocol

3.2. Protocol model

4. Set-based abstraction

Definition 4 (Term transformation)

Definition 5 (Term implication closure)

Definition 6 (Fixed point)

(1) F P is a finite and ground set of terms over T ( Σ ∖ V , ∅ ) . (2) T I is a term implication graph: T I ⊆ A × A . 4.2. Limitations

4.3. Example of a fixed point computation

5. Computing fixed points and checking fixed point coverage

5.1. Automatically checking for fixed point coverage

Definition 7 (Fixed point coverage: preconditions)

Definition 9 (Fixed point coverage: post-conditions)

6.1. Intruder deduction modulo term implications

Lemma 2 c l T I ( M ) ⊢ c t iff M ⊩ c T I t . Next, we show how to reduce the intruder deduction problem ⊢ to the restricted variant ⊢ c . 6.2. Analyzed intruder knowledge

Definition 12 (Analyzed term)

7.1. Our benchmark suite

7.3. An example of protocol composition

8.1. The architecture of Isabelle/PSPSP

9.2. Key generation and revocation

9.3. The bootstrap protocol

9.4. The truststore protocol

9.5. Goals

9.6. The attack

10. Conclusion and related work

Footnotes

Acknowledgments

ORCID iD

Funding

Declaration of conflicting interests

Appendix A. A problem with the AIF- ω specification 09-lost_key_att_countered.aifom

References

(1)
$F P$ is a finite and ground set of terms over $T (Σ ∖ V, \emptyset)$ .
(2)
$T I$ is a term implication graph: $T I \subseteq A \times A$ .

4.2. Limitations

Lemma 2
${c l}_{T I} (M) ⊢_{c} t iff M ⊩_{c}^{T I} t$ .

Next, we show how to reduce the intruder deduction problem $⊢$ to the restricted variant $⊢_{c}$ .
6.2. Analyzed intruder knowledge