### A Verification Framework for

### Stateful Security Protocols

Li Li1, Naipeng Dong2, Jun Pang3, Jun Sun1, Guangdong Bai2, Yang Liu4, and Jin Song Dong2,5

1

Singapore University of Technology and Design, 2National University of Singapore,

3

University of Luxembourg, 4Nanyang Technological University, 5Griffith University

Abstract. A long-standing research problem is how to efficiently verify security protocols with tamper-resistant global states, especially when the global states evolve unboundedly. We propose a protocol specification framework, which fa-cilitates explicit modeling of states and state transformations. On the basis of that, we develop an algorithm for verifying security properties of protocols with unbounded state-evolving, by tracking state transformation and checking the va-lidity of the state-evolving traces. We prove the correctness of the verification algorithm, implement both of the specification framework and the algorithm, and evaluate our implementation using a number of stateful security protocols. The experimental results show that our approach is both feasible and practically effi-cient. Particularly, we have found a security flaw on the digital envelope protocol, which cannot be detected with existing security protocol verifiers.

### 1

### Introduction

Automatic formal verification is shown to be extremely useful in analyzing security pro-tocols. Many security protocol verifiers have been developed, for instance, ProVerif [1], AVISPA [2] and Maude-NPA [3]. However, such verifiers fail in analyzing security pro-tocols with shared objects such as databases, registers and memory locations [4]. Real-world examples include protocols involving security devices like IBM’s 4758 CCA secure coprocessor platform and trusted platform module (TPM) [5] and protocols in-volving databases for websites and key servers [6].

As these shared objects must be maintained externally w.r.t. sessions, the objects are abstracted as global states; and protocols with these shared objects are refereed to as stateful protocols. The global states have three properties: (1) mutable: the value of a state can be updated, (2) unbounded evolving: the value updating of a state can be unbounded, and (3) tamper-resistant: the value of a state can only be updated by legitimate users. For instance, the following example is a simple stateful protocol, where the security device is a shared object, i.e., a global state.

i.e., a sequence of three values_{hm}f, sl, sri asymmetrically encrypted by SD’s public

key pub, SD decrypts it. According to SD’s current memory valuem, it continues as follows: ifm = h(mf, left), SD sends out sl; ifm = h(mf, right), SD sends out sr,

where left and right are two publicly known constants. Suppose Bob, a legitimate user, generates two secrets sl and sr, reads the memory of SD asmf and sends a ciphertext

enca(hmf, sl, sri, pub) to SD. The SD ensures that a malicious Bob or any other

attack-ers can never know both ‘sl’ and ‘sr’ at the same time, since SD cannot be configured

as both ‘h(mf, left)’ and ‘h(mf, right)’ in one execution.

Verification of stateful protocols has been noticed as important and necessary but challenging [5] even for a simple protocol as Example 1. In particular, ProVerif – one of the popular and widely used verifier (e.g., used in [7–10]), reports false attacks for some stateful protocols such as Example 1. Recently, an extension StatVerif is proposed, which is specialized in verifying stateful protocols [6]. However, StatVerif can produce false attacks when the state-value mutates (e.g., when the security device in Example 1 reboots) and cannot terminate when the state-value mutates unboundedly (e.g., when the protocol in Example 1 keeps running).

We improve the Horn clause based verification (used in ProVerif and StatVerif) for analyzing stateful protocols with unbounded global state evolving (i.e., unbounded evolving steps with potentially unbounded values of a state). Horn clause reasoning is inherently monotonic – once an event (the basic element in Horn clause) is true, it cannot be set to false anymore, and thus does not work well for state-value mutation in ProVerif and StatVerif [4]. Therefore, we propose to distinguish global states from events. In particular, we explicitly model global states and their evolving transforma-tions in specification. More importantly, on each step of reasoning in verification, we record the state-evolving constraints; and when a target event is derived, we instantiate a state-evolving trace satisfying the constraints in the derivation, i.e., the global states can evolve following the trace such that the derivation could happen. In such a way, we reduce the false attacks caused by global states’ unbounded evolving.

For example, we model the security device as a global state SD( ), which consists of two parts: the name of the object (SD ) used to distinguish different objects and its pre-defined fields (‘ ’) used to distinguish attributes of the same object (the field ‘ ’ in-dicates the memory of the security device). Each field is filled with a concrete value of the attribute at any time, e.g., the memory field can be filled with ‘init ’, h(mf, left), or

h(mf, right). Hence, SD(init), SD(h(mf, left)), and SD(h(mf, right)) are the

pos-sible instantiations of the global state SD( ). A particular instantiation of a global state may be visited multiple times in one trace of the global state’s evolving. To distinguish each appearance of an instantiation, we additionally add a distinct indexai to the

in-stantiation, and require all indexes in a trace to have chronological orders. We name an instantiation of a global state and its index a snapshot. The snapshots of a global state must form an evolving trace starting from an initial instantiation, based on the index’s chronological order. We allow variables to appear in the snapshot to represent a set of snapshots, and name the snapshot with variables a snapshot pattern.

In verification, we explicitly validate the evolving traces of the snapshots. Suppose the adversary obtains messagem1andm2at the following snapshot pattern respectively

SD (h(h(x1, x2), left )), a1, SD(h(h(h(init, right), x

0

Type Expression

Message(m) a[], b[], A[], B[], ⊥ (name) [n], [k], [N ], [K] (nonce)

x, y, z, X, Y, Z (variable) f(m1, m2, ..., mn) (function)

Guard(g) m16 m2 (@σ, m1· σ = m2) m16= m2 (inequivalence)

Event(e) know (m) (knowledge) new ([n], l []) (generation)

init (m1, · · · , mn) (initialization) accept (m1, · · · , mn) (acceptance)

leak (m) (leakage)

State(s) name(id1, · · · , ids, m1, · · · , mn) (state)

Table 1: Syntax Hierarchy

where variablesx1,x2andx01can be arbitrary values,a1anda2are indexes of the two

snapshots (any ordering is possible). In order to conduct the attack that the adversary obtains bothm1andm2, the adversary tries to find an instantiation of the variablesx1,

x2andx01such that a valid trace exists for the security device to evolve from its initial

snapshot(SD(init), a0) to the above snapshots. We can see that the following evolving

trace exists, whenx1= h(init, right), and x2= x01can be an arbitrary value,

SD (init ) → SD (h(init, right )) → SD (h(h(init , right ), x2))

→ SD(h(h(h(init , right ), x2), left )).

That is, the adversary tries to guide the protocol to perform the above global state transformation, and then obtains bothm1 andm2at the last snapshot. However, if an

additional snapshot SD(h(init, left)), a3) exists e.g., for the adversary to obtain m3,

then no valid evolving trace exists for the adversary to obtainm1,m2andm3, since the

device memory cannot be set to SD(h(init, left)) and SD(h(init, right)) (contained in the snapshot with indexa2) no matter in which order in a single trace. Hence, the attack

is infeasible for obtaining all three pieces of information.

We introduce the formal modeling of global states and their transformations in the subsequent section, then propose our verification algorithm in Section 3, and finally present our experimental results in Section 4 and discuss related works in Section 5.

### 2

### Protocol Specification

To verify whether a protocol satisfies a security property, an analyzer needs to formally specify the protocol (without states in Section 2.1) and the property (Section 2.3). The key part is how the global states and state transformations are formalized (Section 2.2).

2.1 Preliminary – Specification Syntax without States

As in most verifiers, messages – the basic elements in protocols, are modeled by names, nonces, variables and functions (first row in Table 1). Names model constants; nonces are freshly generated random numbers; variables represent memory locations for hold-ing messages, and functions can be applied to a sequence of messages. All messages are assumed to be well-typed and variables can be instantiated only once.

variablesx1,· · · , xnwith the messagesm1,· · · , mnrespectively. Given two messages

m1 andm2, when there exists a substitutionσ such that m1· σ = m2, we say that

m1 is unified tom2, denoted asm1 σ m2. Whenm1 should not be unified tom2,

we writem1 6 m2. For instance, when a messagem should not be a tuple, we write

m_{6 hm}1, m2i. Given two messages m1andm2, if there exists a substitutionσ such

thatm1· σ = m2· σ, we say m1andm2are unifiableandσ is a unifier of m1andm2,

denoted asm1=σ m2. Ifm1andm2are unifiable, the most general unifier ofm1and

m2is a unifierσ such that for any unifier σ0ofm1andm2there exists a substitutionσ00

such thatσ0 _{= σ}_{· σ}00_{. When}_{m}

1andm2should not be unifiable (a.k.a., inequivalence),

we writem1 6= m2. For instance, if the current branch condition is that the protocol

responderr is not Bob, we write r6= Bob. m16 m2andm16= m2form the guarding

conditions (second row in Table 1) i.e., whether an rule (defined later) can be applied. Based on the above definitions, a protocol is modeled as a set of logical rules, similar as in ProVerif [1] and Tamarin [11]. The basic elements of a rule are events. An event is applying a predicate to a message sequence. The following two events are used in the protocol specification:

– event know(m) means that the adversary knows the message m; and the

– event new([n], l[]) models that a nonce [n] (the concrete value of the nonce) is freshly generated at the locationl[] (symbolic value used to distinguish the nonce from other nonces in a specification) by a legitimate protocol participant. Note that nonce[n1] . . . [nk] with the same location l[] are k concrete generation of the same

nonce specification ink different sessions.

The intuition is that a protocol and its involved cryptographic primitives can be treated as oracles accessible to the adversary. The adversary having the required messages ob-tains the corresponding outputs. Once receiving an input, the oracle generates nonces, processes messages and outputs messages according to its specification. Each oracle is modeled as a rule[ G ] H −[ ]→ e, where G is a set of guard conditions, H is a set of premise events, ande is a conclusion event, meaning that if the guard conditions in G and the premise events inH are satisfied, then the conclusion event in e is satisfiable. Cryptographic primitives. The premises of a cryptographic primitive are a set of know events specifying the input parameters, and the conclusion is one know event repre-senting the generated result, e.g., the asymmetric encryption and decryption used in Example 1 is modeled as follows, wherem, pub and sk are variables.

know (m), know (pub) −[ ]→ know (enca(m, pub)) (1)

know (enca(m, pk(sk ))), know (sk ) −[ ]→ know (m) (2)

Protocol. A pair of the message input and the subsequent output of a participant are specified as an oracle as well. The difference is that we need to additionally consider the nonce generation and potential guard conditions. Whenever a nonce at positionl[] is generated in a protocol, we model the nonce generation by adding a new([d], l[]) event toH of the oracle. Whenever m1 6= m2or m1 6 m2conditions are required

(which rarely happen in protocol specification) in the current execution branch, we add the conditions intoG. For example, bob’s behavior in Example 1 can be modeled as

new ([bobl], lsl[]), new ([bobr], lsr[]), know (mf) −[ ]→

2.2 Protocol Specification with States

As addressed in the introduction, we explicitly model the global states of a protocol as well as their transformations. There are two ways that the states are involved. First, we use snapshots to represent at which state a rule can be applied. Second, we use a rule to model how the state transforms.

For the first case, we introduce a set of snapshots S into the rule to denote the involved states, useM to record at which snapshot each event happens (each element inM is of the form ei:: ajwithei∈ H and ajbeing the index of a snapshot inS), and

useO to denote the constraints on chronically orders between snapshots (each element inO is of the form aiR aj withaiandajbeing indexes of snapshots inS). We define

three types of ordering relations between two snapshotsaiandaj inR: (1) ai ≤ aj

means thataiappears earlier thanaj; (2)ailajmeans that the shared object is modified

once betweenaiandaj; (3)ai ∼ aj means that the shared object remains unchanged

betweenai andaj. A rule now is of the form[ G ] H : M −[ S : O ]→ e where e is

an event. We name such rules as state consistent rules. For example, depending on the configuration, the SD repliesslorsrin Example 1, and the behavior of replyingslis

modeled as follows:

know (enca(hmf, sl, sri, pk(sksd []))))1 : {1 :: a1} −[ SD(init []), a0,

SD (h(mf, left [])), a1 : {a0 ≤ a1} ]→ know (sl) (4)

where 1 is a reference to the corresponding premise event inH, so that we do not need

to repeat the entire event inM , in order to save space and have a clearer presentation. The rule describes that if (1) the SD reads in a ciphertext enca(hmf, sl, sri, pk(sksd[])))

at snapshota1, which is denoted by an event know(enca(hmf, sl, sri, pk(sksd[])))),

and the mapping between the event and a set of snapshots 1 :: {a_{1}} where 1 refers

to the know event; and (2) snapshota1is reachable, i.e., there should be a valid trace

from the initial state SD(init[]) to the current state SD(h(mf, left[])), which is denoted

by the two snapshots SD(init[]), a0, SD(h(mf, left[])), a1 and their ordering

con-straints_{{a}0≤ a1}, meaning that a0needs to appear earlier thana1in a trace; then (3)

the SD returnssl, since the current configuration is h(mf, left[]). Another type of state

consistent rule is that the adversary may be able to obtain information from the states, e.g., the reading operation in Example 1 can be modeled as

−[ SD(init []), a0), SD (m), a2 : {a0≤ a2} ]→ know (m) (5)

meaning that ifa2is reachable (denoted by SD(init[]), a0), SD(m), a2 : {a0 ≤

a2} with a0being the initial state), then the adversary can read the current value in the

memory, modeled as know(m).

For the second case, we introduce the state transferring rules of the form[ G ] H :
M _{−[ S : O ]→ T where T is a set of state transformations (a sequence of two}
snapshots). For example, the SD can be updated in Example 1, which is modeled as

know (x)2 : {2 :: a3} −[ SD(init []), a0, SD(m), a3 : {a0≤ a3} ]→

h SD(m), a3, SD(h(m, x)), a4)i (6)

meaning that the adversary who hasx at state SD(m) can update the SD to be h(m, x),
where_{h SD(m), a}3, SD(h(m, x)), a4)i models the transformation of SD from

2.3 Security Properties

We focus on two types of security properties: authentication and secrecy. To formalize authentication properties, we add the following two events: When the protocol initiator starts a protocol run, we add a corresponding init event (defined in Table 1) intoH; when the protocol responder accepts a protocol run, we add a corresponding accept event (defined in Table 1) intoC. Then authentication is modeled as correspondence between the init and accept events (as in most verifiers such as ProVerif and StatVerif). Definition 1 (Authentication). In a security protocol, an authentication property holds, i.e., correspondence between anaccept event and an init event with agreed arguments holds, if and only if for every occurrence of eventaccept(m1,· · · , mn), the

correspond-inginit(m1,· · · , mn) event must be engaged before, and all the required snapshots

form a valid evolving trace, denoted asaccept(m1,· · · , mn)⇐ init(m1,· · · , mn).

The secrecy property specifies that the adversary cannot obtain certain secret mes-sages. It is defined by introducing a rule with the leak event (defined in Table 1) as the conclusion. If secrecy is preserved in a protocol, the leak event should not be reachable. Definition 2 (Secrecy). In a protocol, secrecy holds for a message m if and only if leak(m) is not reachable after adding new1,· · · , newn, know (m) −[ ]→ leak(m),

wherenew1,· · · , newnare the nonce generation events for all nonces inm.

Intuitively, if the adversary knows the message know(m), the message m is leaked; and the new events are used to accurately specify the nonces inm.

As commonly assumed, we consider an active network attacker who can intercept all communications, compute new messages, generate new nonces and send the mes-sages he obtained. For computation, he can use all the publicly available functions, e.g., encryption, decryption and concatenation. He can also designate honest participants to initiate new protocol runs and to take part in the protocol whenever he needs to.

### 3

### Verification Algorithm

Given a set of rules_{B}initspecifying a protocol (including stateless rules, state consistent

rules and state transferring rules) and a property as described in Section 2, the
verifi-cation aims to find the derivations of the target event specified in the property (accept
event for authentication andleak for secrecy) using the rules in_{B}init, and then check

whether a derivation contradicts the specified property.

To derive a target event using a set of rules, directly reasoning on the rules would not terminate, e.g., repeatedly applying Rule (1) leads to increasingly complex terms [1, 6]. To improve efficiency and help termination, we follow the approach in [1, 6] – provid-ing an algorithm to guide the reasonprovid-ing. Hence, similar to [1], we construct a rule base B, in the first phase, by combining pairs of rules in Binit, which may infer new rules.

with complex premise events, because whenever the rule with complex premises is used
in the reasoning, it can be replaced with an alternative rule (often generated by
compo-sition) with all premise events in_{N . In addition, when a new rule is inferred by rule}
composition, rule implication operation is applied to check whether this rule is
neces-sary to be added to_{B. If the new rule is implied by existing rules then it is not necessary}
to add it. These two operations are shown to be efficient in avoiding complex terms and
accelerating the verification process in ProVerif.

We generally follow the above procedure as proposed in ProVerif, but we need to add snapshot trace validation in rule composition and rule implication. Intuitively, rule composition applies one rule after another. Thus, regarding states, we ensure that (1) the snapshot ordering constraints in both rules are still preserved and (2) the ordering between the two rules are added to the ordering constraints in the resulting new rule. For rule implication, regarding states, we need to define that the ordering constraints of snapshots in a rule is less than the constraints in another one, i.e., whenever the second rule is applicable, the first rule is also applicable.

In addition, we try to concretize the snapshot traces in a rule if possible, to narrow
the possible traces satisfying the ordering constraints in the rule, since it is sufficient as
long as one trace exists to reach the conclusion event. To do so, we introduce two
addi-tional operations: state unification and state transformation. The intuition is as follows:
Any two snapshots appear in a rule may have three kinds of relations: (1) they are from
different objects; (2) they are of the same object, and the object is not modified between
two snapshots; (3) they are of the same object, and the object is modified between the
two snapshots. In the first case, we do not need to search for a valid trace between the
two snapshots. In the second case, we try to unify them to the same value, i.e., state
unification. In the third case, we try to find the transformations between them, i.e., state
transformation. Note that these two operations only need to be applied to rules (1) with
its premise events in _{N , since those with premise event not in N will be eventually}
removed; and (2) with their conclusion events beleak event or accept event, since they
are the query goals.

3.1 Preliminary Definitions

We first define the set_{N as the following three types of events, similar to ProVerif: (1)}
initializing a new protocol (an init event), (2) generating a fresh nonce (a new event),
(3) knowing an arbitrary value (a know(x) event where x is a variable).

Recall that a rule may contain a set of ordering constraintsO specified using relation R defined in Section 2, we define O as closed if the following properties hold.

ail aj, aj∼ ak∈ O ⇒ ail ak∈ O ail aj, ak∼ aj∈ O ⇒ ail ak∈ O ai∼ aj, ajl ak∈ O ⇒ ail ak∈ O aj∼ ai, ajl ak∈ O ⇒ ail ak∈ O ail aj∈ O ⇒ ai≤ aj∈ O ai∼ aj∈ O ⇒ ai≤ aj∈ O ai∼ aj, aj∼ ak∈ O ⇒ ai∼ ak∈ O ai≤ aj, aj≤ ak∈ O ⇒ ai≤ ak∈ O

In verification, we first ensure theO in every rule is closed using the above definition.
Given two sets of ordering constraintsO and O0_{, we use}_{O}_{] O}0_{to denote their closed}

LetR = [ G ] H : M _{−[ S : O ]→ V and R}0 _{= [ G}0 _{]H}0 _{: M}0_{−[ S}0 _{: O}0 _{]}_{→ V}0_{be}

two rules. (1) ‘R having less restricted mappings than R0_{’}_{means that if some premise}

events inR are required to be satisfied at a snapshot (s, aj), the same premise events

need to be satisfied at an earlier snapshot(s0, ai) in R0(ai≤ aj). This indicates thatR0

has more restrictions on the satisfaction of the premises thanR. This requirement can
be formally captured by the joint operator ‘_{∗’.}

M ∗ O = {hei, aji | ei:: ak∈ M ∧ aj≤ ak∈ O}

For every eventei,M∗O captures all the snapshots later than the snapshot at which the

event should be satisfied. The larger the setM ∗ O is, the earlier the event eineeds to

be satisfied. Hence,(M_{∗ O) ⊆ (M}0_{∗ O}0_{) captures that R has less restricted mappings.}

(2) ‘R having more organized ordering than R0_{’}_{means that for every two snapshots}

(s1, ai) and (s2, aj) appearing in both R and R0, the ordering of the two snapshots inR

is more concrete (less uncertain) than inR0_{. Since,}_{a}

il ajorai∼ ajis more concrete

thanai≤ aj, given an orderingO, we measure its uncertainty (less concrete) with

δ(O) = {ai≤ aj| ai≤ aj∈ O} − {at≤ ak|atl ak∈ O ∨ at∼ ak∈ O}.

O is more organized than O0if and only ifδ(O)⊆ δ(O0_{). δ(O) captures the uncertain}

ordering relations between every two snapshots in the snapshot setO. The larger the set δ(O0) is, the more uncertain the ordering O0is, and hence the less organizedR0is. 3.2 Rule Operations

Similar to ProVerif, when the premise of a rule contains an event not in_{N , we try to}
fulfill/unify the event with a conclusion of other state consistent rules whose premises
are in_{N by rule composition.}

Definition 3 (Rule Composition). LetR = [ G ] H : M −[ S : O ]→ e be a state
consistent rule andR0 _{= [ G}0_{] H}0 _{: M}0 _{−[ S}0 _{: O}0 _{]}_{→ V be either a state consistent}

rule or a state transferring rule. If there existse0∈ H0such thate =σe0, thenR with

R0_{can be composed on the event}_{e}

0, and the newly composed rule is defined as

R ◦e0R

0

= [ G ∪ G0](H ∪ (H0− {e0})) : M ∪ M0∪ M0

−[ (S ∪ S0) : O ] O0] O0]→ V · σ,

M0= {ei:: ak|ei∈ H, e0:: ak∈ M0}, O0= {ai≤ aj| (s, ai) ∈ S, e0 :: aj∈ M0}.

In the resulting rule R ◦e0 R

0_{, the guard condition} _{G} _{∪ G}0_{, premise events}_{H} _{∪}

(H0− {e0}) and conclusion event V are straightforward, following the same idea as

in ProVerif. Regarding states,S∪ S0_{,}_{M} _{∪ M}0_{and}_{O}_{] O}0_{capture that the snapshots,}

event-snapshot mapping and ordering constraints in both rules need to be satisfied in the resulting rule. For event-snapshot mapping, we additionally require that any event ei∈ H needs to map to the snapshots of e0(i.e.ak), such thatR can be applied at state

ak. Otherwise even ife and e0are unifiable, after applyingR, R0cannot be applicable,

due to that the state ofe0is not satisfied. This requirement is captured byM0. For the

snapshot ordering, we additionally require that any snapshot inS should appear before the snapshot ofe0, capturing thatR is applied before R0in order to obtaine (or e0), and

Given two rulesR and R0_{, if}_{R (1) has the same conclusion as R}0 _{but requires less}

guard conditions and less premises (the same as in ProVerif), (2) has less snapshots, less
restricted mappings and more organized ordering (additional requirements regarding
states), we say thatR implies R0_{, denoted as}_{R}_{⇒ R}0_{.}

Definition 4 (Rule Implication). LetR = [ G ] H : M _{−[ S : O ]→ V and R}0 _{=}

[ G0 _{]H}0 _{: M}0 _{−[ S}0 _{: O}0 _{]}_{→ V}0 _{be two rules. We define}_{R implies R}0 _{denoted as}

R_{⇒ R}0if and only if_{∃σ,}

(1) (V · σ = V0) ∧ (G · σ ⊆ G0) ∧ (H · σ ⊆ H0)

∧

(2) (S · σ ⊆ S0) ∧ ((M ∗ O) · σ ⊆ (M0∗ O0

)) ∧ (δ(O) · σ ⊆ δ(O0)).

By now, we updated the rule composition and rule implication with additional re-quirements on states. Hereafter we introduce operations to concertize a snapshot trace. Given two snapshots(s1, ai), (s2, aj) of the same object in a rule, if s1 ands2

are unifiable (s1 =σ s2), the simplest trace betweens1 ands2 is to unify them as

one snapshot, capturing the situation where the object is not modified between the two snapshot (formallyai∼ ajoraj ∼ ai).

Definition 5 (State Unification). LetR = [ G ] H : M _{−[ S : O ]→ e be a state}
consistent rule. Assume there exist two distinct snapshots (s1, ai), (s2, aj) ∈ S such

thats1=σ s2, then we can unify the two snapshots in ruleR; and the state unification

ofs1tos2onR is defined as

R[ai∼ aj] = [ G ] H : M −[ S : O ] {ai∼ aj} ]→ e · σ.

Note that ifs1=σ s2, bothR[ai∼ aj] and R[ai ∼ aj] will be generated.

Given a state consistent ruleR = [ G ] H : M −[ S : O ]→ e, if a snapshot (s, ai)∈ S does not have an immediate previous snapshot defined in O, i.e., @(s0, aj)∈

S : ajl ai ∈ O ∨ aj ∼ ai ∈ O, we try to apply a state transferring rule to find an

immediate previous snapshot. Given a ruleR, we use η(S, O) to denote the snapshots inS whose previous snapshots have not been found, i.e.,

η(S, O) = S − {(s, ai) | ajl ai∈ O ∨ aj∼ ai∈ O}.

Definition 6 (State Transformation). LetR = [ G ] H : M _{−[ S : O ]→ T be}
a state transferring rule and R0 = [ G0 ] H0 : M0 −[ S0 _{: O}0 _{]}_{→ e be a state}

consistent rule. Assume there is an injective functionf : T _{→ η(S}0_{, O}0_{), such that}

∀t = h(s, ai), (s0, aj)i ∈ T, s0 =σ s00iff (t) = (s00, ak). The state transformation of

applyingR to R0_{on}_{f is}
R ./fR
0
= [ G ∪ G0] (H ∪ H0) : M ∪ M0−[ (S ∪ S0) : O ] O0] O0] O
00
]→ e · σ,
whereO0 = {ail ak | h(s, ai), (s0, aj)i ∈ T, f(t) = (s00, ak)}, and O00 ={at ≤
ai|at≤ ak∈ O0, t =h(s, ai), (s0, aj)i ∈ T, f(t) = (s00, ak)}.

O0captures that for a state transformationh(s, ai), (s0, aj)i in T and a function f(t) =

(s00, ak)∈ S0,aidid exact one transformation toak, because the snapshot(s0, aj) will

not appear in the new rule, as it is unified with (s00, ak). O00 enforces the snapshots

(e.g.,at) that appear earlier thanakinO0to be also earlier thanaiin the new rule. The

intuition is that there is an immediate concrete transformation fromaitoak (ail ak),

but the relation betweenatandak is rather uncertain; in this case, we try to align the

three snapshots asat≤ ail ak. Note it is sufficient to find one trace amongat,aiand

Definition 7 (Rule Validation). A rule R = [ G ] H : M _{−[ S : O ]→ V is valid}
if and only if (1)V /_{∈ H; (2) O is closed and ∀ a}i ≤ aj ∈ O : aj ≤ ai 6∈ O;

(3) _{∀ know(x), know(y) ∈ H: x 6≡ y, and ∀ init(x), init(y) ∈ H: x 6≡ y, and}
∀ new([n], l[]), new([n0_{], l}0_{[])} _{∈ H: n 6≡ n}0 _{∨ l 6≡ l}0_{; (4)}_{∀ e}

i :: aj ∈ M : ei ∈

H_{∧ ∃(s, a}j)∈ S, and ∀ aiRaj∈ O : ∃(s, ai)∈ S ∧ ∃(s0, aj)∈ S.

The rule validation procedure ofR is denoted as

R ⇓= merge(H) : clear(M ) −[ S : clear(O) ]→ V · σ

where functionmerge removes the duplicated premises, function clear removes refer-ences of non-existing events and snapshots,σ is the most general unifier such that any two redundant events can be merged or unified.

We usex_{6≡ y to denote that x is not syntactically equal to y. The definition says that a}
rule[ G ] H : M _{−[ S : O ]→ V (V is an event e or a set of state transformations T ) is}
valid if and only if it satisfies: (1) IfV is an event, V should not be in H; (2) O should
be closed and contains no contradictory constraints; (3) there is no redundant events
(two events modeling the same thing) inH (redundant events should be unified and
merged); and (4) all mappings inM and all orderings in O do not involve non-existing
events or snapshots (non-existing events or snapshots should be removed).

Heuristics. If provided with a snapshot pattern, we try to instantiate the snapshots in a rule with the pattern to accelerate the process of finding a concrete snapshot trace. Consider a state consistent ruleR = [ G ] H : M −[ S : O ]→ e, where H ⊆ N , e = know (x) and x is a variable. This implies that x does not appear in H; otherwise, the rule is not valid. Hence, x must be originated from S, for example the reading operation supported by the security device in Example 1. Since know(x) ∈ N , we cannot composeR with other rules. To guide the verification, we try to apply the pattern to the states, so thatR can be composed with other rules.

Definition 8 (State Instantiation). LetR = [ G ] H : M −[ S : O ]→ e be a state consistent rule. Given a snapshot(s, ai)∈ S and its pattern p such that s =σ p, we

define the state instantiation of the snapshots with its pattern p as follows

R[s 7→ p] = [ G ] H : M −[ S : O ]→ e · σ.

3.3 Rule Base Construction

Using the above rule operations, we develop an algorithm to construct the rule base
(Al-gorithm 1). The al(Al-gorithm guides the verification by selecting proper rules to perform
rule operations. Given an initial set of rules_{B}initas input, the algorithm returns the rule

base_{B as output. In the algorithm, we first add the rules in B}initto the setrules (line

8−11). During this procedure, redundant rules are removed (line 1−6). Then we apply rule operations on the rules inrules and obtain a saturated rule setBv (line13− 35).

The algorithm defines which operation is applied to which types of rules. Finally, we
select those rules in_{B}vwith premises inN and conclusion event being accept or leak

to form_{B. Now we prove the correctness of the algorithm.}

Theorem 1. Any accept or leak evente that is derivable from the initial rules_{B}init if

Algorithm 1: Rule Base Construction

Input : Binit- initial rules

Output: B - knowledge base

1 Procedure add (R, rules)

2 for Rb∈ rules do

3 if Rb⇒ R then return rules;

4 if R ⇒ Rbthen rules = rules − {Rb};

5 end

6 return {R} ∪ rules;

7 Algorithm

8 rules = ∅;

9 for R ∈ Binitdo

10 rules = add (R, rules);

11 end

12 repeat

13 Case 1. Rule Composition

14 Select a state consistent rule R = H −[ S : O ]→ e

15 and a general rule R0= H0−[ S0: O0]→ V from rules such that

16 1. H ⊆ N ; 2. ∃e0∈ H0: e06∈ N ;

17 rules = add ((R ◦e0R

0

) ⇓, rules);

18 Case 2. State Unification

19 Select a state consistent rule R = H −[ S : O ]→ e from rules such that

20 1. H ⊆ N and e is an accept event or a leak event;

21 2. ∃s, s0∈ S, s and s0can be unified;

22 rules = add (R[s ∼ s0] ⇓, rules);

23 Case 3. State Transformation

24 Select a state transferring rule R = H −[ S : O ]→ T

25 and a state consistent rule R0= H0−[ S0: O0]→ e from rules such that

26 1. H ∪ H0⊆ N and e is an accept event or a leak event;

27 2. ∃f, ∀t ∈ T, f (t) = (s, aj), @ail aj∈ S0;

28 rules = add ((R ./f R0) ⇓, rules);

29 Case 4. State Instantiation

30 Select a state consistent rule R = H −[ S : O ]→ e from rules such that

31 1. H ⊆ N , e ∈ N ; 2. ∃s ∈ S, s has pattern p;

32 rules = add (R[s 7→ p] ⇓, rules);

33 until fix-point is reached;

34 Bv= rules;

35 return B = {R = H −[ S : O ]→ e ∈ rules | ∀p ∈ H, p ∈

N ∧ e is an accept event or a leak event};

The basic idea is as follows: Whenever there is an attack using the rules in_{B}init, there

is an attack using the rules in_{B}v, since there is no rule missing. Then we only need

to show that the selected rules (rules in_{B}v) would not miss an attack. To do so, we

R R he1, S, ii he1, S, ii hehe22, S, ii, S, ii hehenn, S, ii, S, ii he, S, ii he, S, ii

(a) State Consistent Rule

R R he1, S, ii he1, S, ii hehe22, S, ii, S, ii hehenn, S, ii, S, ii he, S0, ji he, S0, ji he, S, ii he, S, ii i = j + 1 i = j + 1

(b) State Transferring Rule

Fig. 1: Rule in derivation tree

Definition 9 (Derivation Tree). A closed rule is a rule with its conclusion initiated by
its premises and states. Let_{B}tbe a set of closed rules andetbe an event,etis derivable

from_{B}tif and only if there exists a finite derivation tree satisfying the following.

1. Every edge in the tree is labeled by an evente, a set of snapshots S =_{{(s}1, a1), . . . ,

(sl, al)} and an index i, and ∀(si, ai), (sj, aj)∈ S: ai6∼ aj.

2. Every node is labeled by a rule in_{B}t.

3. If a node is labeled by a state consistent rule R as in Figure 1a, then we have R ⇒ H : M −[ S0∪ S : O ]→ e where H = {e1,· · · , en}, M is defined as

∀e ∈ H : e :: {a1, . . . , al}, O = {a0 ≤ ai|(s0, a0) ∈ S0, (si, ai) ∈ S} with

S0being the set of initial snapshot of each object; and the indexes labeled on the

outgoing edge and incoming edges (Figure 1a) are the same.

4. If a node is labeled by a state transferring ruleR as in Figure 1b, there exists a
set of state transformationT such that R _{⇒ H : M −[ S}0∪ S : O ]→ T where

H = _{{e}1,· · · , en}, M is defined as ∀e ∈ H : e :: {a1, . . . , al}, O = {a0 ≤

ai|(s0, a0) ∈ S0, (si, ai) ∈ S} with S0 being the initial snapshots; letSpre =

{(si, ai)|h(si, ai), (sj, aj)i ∈ T } and Spost ={(sj, aj)|h(si, ai), (sj, aj)i ∈ T },

we haveSpre⊆ S; and in Figure 1b, S0 = S− Spre+ Spost,e can be any event

that is satisfied atS, the indexes labeled on the incoming edges equal to the index labeled on the outgoing edge plus1.

5. Outgoing edge of the root is labeled by the eventetand the index1.

6. Incoming edges of the leaves are only labeled by events in_{N with the same index.}
7. The edges with the same index have the same state.

Then we prove that whenever there is a derivation tree for an accept or a leak event
using rules in_{B}v, there is a derivation for the event using the rule baseB created using

Algorithm 1, and vice versa. The key part in the proof is the following Lemma which demonstrates how to replace two directly connected nodes in the derivation tree with one node labeled by a composite rule with the same state and index. Detailed proofs of the theorem and lemma are available online [12].

Lemma 1. IfRo◦e0 R

0

ois valid,Rt ⇒ Ro andR0t ⇒ R0o, then either there existse0

such thatRt◦e0R0_{t}is valid andR_{t}◦_{e}0R0_{t}⇒ R_{o}◦_{e}
0R
0
o, orR0t⇒ Ro◦e0R
0
o.
3.4 Query Searching

secret(s, pk, p) Phase 1

Phase 2 alice(n)

extend(n) with Encrypted Session

pk and certificate data s encrypted by pkey

tpm(bob, x) tpm(bob, h(x, n)) tpm(bob, p) tpm(bob, h(p, open)) OR tpm(bob, h(p, revoke)) generate key pair <sk, pk>

lock to h(p, open) create secret s Alice Bob create nonce n PCR = p PCR = p option 1: extend(open) read s option 2: extend(revoke) send PCR quote to Alice

Fig. 2: The DEP protocol

Alice Bob

create nonce n

extend(n) with Encrypted Session

PCR = b PCR = b

create bind key <sk, pk> locked to h(b, open) pk and certificate data s encrypted by pk extend(open) read s Phase 1 Phase 2.1 Reboot extend(revoke) send PCR quote to Alice

Reboot

Phase 2.2 create secret s

Fig. 3: An attack on DEP

event is an accept event, while it does not require the corresponding init event in its premises. A rule disproves secrecy when the leak event is reachable.

Definition 10. Authentication Counterexample. A ruleR = [ G ] H : M −[ S : O ]→
e disproves authentication property Qn := accept ⇐ init denoted as Qn 0 R if and
only ifG_{6= false, e and accept are unifiable with the most general unifier σ such that}
∀e0 _{∈ H, e}0 _{∈ N and ∀σ}0 _{: (init}_{· σ · σ}0_{∈ H · σ).}_{/}

Definition 11. Secrecy Contradiction. A rule R = [ G ] H : M −[ S : O ]→ e disproves secrecy propertyQs:= leak (m) denoted as Qs0 R if and only if ∀e0 ∈ H : e0∈ N , G 6= false, ∃σ, leak(x) · σ = e.

If we cannot find any counterexample during the verification, when our algorithm terminates, the protocol satisfies the property. For a detailed proof, see [12].

Theorem 2. Let _{B be the rule base generated in Algorithm 1. When Q is a secrecy}
query or an authentication query, there existsR derivable from_{B}initsuch thatQ 0 R

if and only if there existsR0_{∈ B such that Q 0 R}0_{.}

### 4

### Case Studies

DEP consists of two phases as shown in Figure 2. In the first phase, Alice generates
a secret nonce[n] and uses it to extend a given PCR in Bob’s TPM with an encrypted
session (detailed TPM explanation can be found at [12]). Since the nonce[n] is secret,
Bobcannot re-enter the current state of the TPM if he makes any changes to the given
PCR. In the second phase, Alice and Bob read the value of the given PCR asp and Bob
creates a binding key pair_{h[sk], pk([sk])i locked to the PCR value h(p, open[]) and}
sends the public binding key together with the key certificate to Alice, where open[] is
an agreed constant in the protocol. This means that the generated binding key can be
used only if the value open[] is first extended to the PCR of value p. After checking the
correctness of the certificate, Alice encrypts the data[s] with the public key pk([sk ])
and sends it back to Bob. Later, Bob can either open the digital envelope by extending
the PCR with open[] or revoke his right to open the envelope by extending another
pre-agreed constant revoke[]. If Bob revokes his right, the quote of PCR value h(p, revoke[])
can be used to prove Bob’s revoking action.

Using our approach and the implemented tool, we have found a cold-boot attack for this DEP when the TPM rebooting is allowed (see Figure 3). When the TPM rebooting is allowed, Bob can reboot his TPM immediately after the first phase. Bob can reset the PCR value, e.g., tob. As a consequence, the secret nonce [n] extended to the PCR is lost. When Alice reads the PCR value in the beginning of the second phase, she actually reads a PCR valueb that is unrelated to her previous extending action. Later this new PCR valueb is used in generating key; and the key is used to encrypt Alice’s secret [s]. On receiving Alice’s cipher-text, Bob can open it and read[s] by extending the PCR value by open[]. Since Bob is allowed to reboot, he reboots the TPM, resets the PCR value to b, and extends the PCR value by revoke[]. Now Bob can get a PCR quote proving that he did not open the ciphertext, despite the fact that he has opened it.

The previously DEP verification in [7] fails to detect the above attack, because, in order to use the automatic verification tool ProVerif, which can only handle limited number of TPM steps, the authors made modification to the original DEP protocol – Bobalways performs the TPM reboot before the first phase; and Alice is assumed to have the PCR value h(p, n) without actually reading it, in the beginning of the second phase. As a result, in their model, TPM rebooting can never happen before the second phase. Hence, the modification prevents them from detecting the attack. Since we allow state modeling and unbounded state-evolving, we can remove the assumption made in [7], and thus are able to detect the flaw.

### 5

### Related Works

For verifiers that can handle global states, StatVerif [6] is mostly relevant to our work. As mentioned earlier, StatVerif does not terminate for unbounded involving of global states (see Example 1). In addition, StatVerif still has false attacks due to the monotonicity of Horn clauses, for example, when the security device in [6] (similar protocol to Example 1 which allows the memory to be reset to a value instead of being extended to a value) is first set to either left or right and then set to reboot (the StatVerif code for this scenario and Example 1 can be found at [17]). Our method does not have this problem for the above example protocols. Kremer et al. extended StatVerif with the ability to model unbounded number of global states [4], while our work enables to model and verify unbounded evolving of global states. Hence, our work is orthogonal to the work of Kremer et al. In addition, their work uses Tamarin [11] as its backend verification engine, which is different from the Horn clause based approaches (general comparison is difficult [21]). In general, Tamarin can be used for reasoning on pro-tocols with global states, but its user may need to interact with the verifier [4]. Our verifier, on the other hand, is fully automatic. Furthermore, M¨odersheim developed a verification framework that works with global states [22]. The framework extends the IF language with sets and abstracts messages based on its Set-Membership. However its expressivenss and verification applicability is unclear. Guttman extended the strand space with mutable states to deal with stateful protocols [23, 24], but without tool sup-port for his approach. Most imsup-portantly, none of the above explicitly handles unbounded global state evolving.

### 6

### Conclusions and Future Work

We have presented a new approach for the stateful security protocol verification with unbounded global state evolving. We implemented a tool for our new approach and the verification results of a number of protocols are quite encouraging. For future work, accelerating the redundancy checking would be helpful to improve the tool’s perfor-mance. In addition, analyzing more stateful protocols, and adapting our approach for protocols with physical properties, e.g., time and space, would be interesting directions.

Acknowledgement. This work is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its National Cybersecurity R&D Program (TSUNAMi project, Award No.NRF2014NCR-NCR001-21) and administered by the National Cy-bersecurity R&D Directorate.

### References

1. Blanchet, B.: An efficient cryptographic protocol verifier based on Prolog rules. In: Proc. 14th IEEE Computer Security Foundations Workshop (CSFW), IEEE CS (2001) 82–96 2. Vigan`o, L.: Automated security protocol analysis with the avispa tool. Electronic Notes in

Theoretical Computer Science (ENTCS) 155 (2006) 61–86

4. Kremer, S., K¨unnemann, R.: Automated analysis of security protocols with global state. In: Proc. 24th IEEE Symposium on Security and Privacy (S&P). (2014) 163–178

5. Herzog, J.: Applying protocol analysis to security device interfaces. IEEE Security & Privacy 4(4) (2006) 84–87

6. Arapinis, M., Ritter, E., Ryan, M.D.: StatVerif: Verification of stateful processes. In: Proc. 24th IEEE Computer Security Foundations Symposium (CSF), IEEE CS (2011) 33–47 7. Delaune, S., Kremer, S., Ryan, M.D., Steel, G.: Formal analysis of protocols based on TPM

state registers. In: Proc. 24th IEEE Computer Security Foundations Symposium (CSF), IEEE CS (2011) 66–80

8. Dong, N., Jonker, H., Pang, J.: Challenges in ehealth: From enabling to enforcing privacy. In: Proc. 1st International Symposium on Foundations of Health Informatics Engineering and Systems (FHIES). Volume 7151 of LNCS., Springer (2011) 195–206

9. Dong, N., Jonker, H., Pang, J.: Formal analysis of privacy in an ehealth protocol. In: Proc. 17th European Symposium on Research in Computer Security (ESORICS). Volume 7459 of LNCS., Springer (2012) 325–342

10. Dong, N., Jonker, H.L., Pang, J.: Formal modelling and analysis of receipt-free auction protocols in applied pi. Computers & Security 65 (2017) 405–432

11. Meier, S., Schmidt, B., Cremers, C., Basin, D.A.: The TAMARIN prover for the symbolic analysis of security protocols. In: Proc. 25th International Conference on Computer Aided Verification (CAV). Volume 8044 of LNCS., Springer (2013) 696–701

12. Li, L., Dong, N., Pang, J., Sun, J., Bai, G., Liu, Y., Dong, J.S.: A verification framework for stateful security protocols – full version (2017) Available online at http://www.comp. nus.edu.sg/˜dongnp/sspa.

13. Ables, K., Ryan, M.D.: Escrowed data and the digital envelope. In: Proc. 3rd Interna-tional Conference in Trust and Trustworthy Computing (TRUST). Volume 6101 of LNCS., Springer (2010) 246–256

14. Microsoft: Bitlocker FAQ (2011) Available online at http://technet.microsoft. com/en-us/library/hh831507.aspx.

15. Needham, R.M., Schroeder, M.D.: Using encryption for authentication in large networks of computers. Communication of the ACM 21(12) (1978) 993–999

16. Lowe, G.: An attack on the needham-schroeder public-key authentication protocol. Infor-mation Processing Letters 56 (1995) 131–133

17. Li, L., Dong, N., Pang, J., Sun, J., Bai, G., Liu, Y., Dong, J.S.: SSPA tool, experiment models and evaluation results (2017) Available online at http://lilissun.github.io/r/ sspa.html.

18. Dolev, D., Yao, A.C.C.: On the security of public key protocols. IEEE Transactions on Information Theory 29(2) (1983) 198–207

19. Rusinowitch, M., Turuani, M.: Protocol insecurity with a finite number of sessions, com-posed keys is np-complete. Theoretical Computer Science 299(1-3) (2003) 451–475 20. Durgin, N.A., Lincoln, P., Mitchell, J.C.: Multiset rewriting and the complexity of bounded

security protocols. Journal of Computer Security 12(2) (2004) 247–311

21. Meier, S.: Advancing automated security protocol verification. PhD thesis, ETH (2013) 22. M¨odersheim, S.: Abstraction by set-membership: verifying security protocols and web

ser-vices with databases. In: Proc. 17th ACM Conference on Computer and Communications Security (CCS), ACM (2010) 351–360

23. Guttman, J.D.: Fair exchange in strand spaces. In: Proc. 7th International Workshop on Security Issues in Concurrency (SECCO). Volume 7 of EPTCS. (2009) 46–60