# On Formal and Automatic Security Verification of WSN Transport Protocols

Authors: Vinh Thong Ta; Levente Buttyán; Amit Dvir
Journal: ISRN Sensor Networks
 (2014)

---

## Abstract

We address the problem of formal and automated security verification of transport protocols for wireless sensor networks (WSN) that may perform cryptographic operations. The verification of this class of protocols is difficult because they typically consist of complex behavioral characteristics, such as real-time, probabilistic, and cryptographic operations. To solve this problem, we propose a probabilistic timed calculus for cryptographic protocols and demonstrate how to use this formal language for proving security or vulnerability of protocols. The main advantage of the proposed language is that it supports an expressive syntax and semantics, allowing for studying real-time, probabilistic, and cryptographic issues at the same time. Hence, it can be used to verify systems that involve these three properties in a convenient way. In addition, we propose an automatic verification method, based on the well-known PAT process analysis toolkit, for this class of protocols. For demonstration purposes, we apply the proposed manual and automatic proof methods for verifying the security of DTSN and SDTP, which are two of the recently proposed WSN transport protocols.


---

## Body

## 1. Introduction

Numerous transport protocols have been proposed specifically designed for applications of wireless sensor networks (WSN), requiring particularly reliable delivery and congestion control (e.g., multimedia sensor networks) [1]. Two of the latest protocols are the distributed transport for sensor networks (DTSN) [2] and its secured version, the secure distributed transport protocol for sensor networks (SDTP) [3]. In DTSN and SDTP the intermediate nodes can cache the packets with some probability and retransmit them upon request, providing reliable transmission, energy efficiency, and distributed functionality.Unfortunately, existing transport protocols for WSNs (including DTSN) do not include sufficient security mechanisms or totally ignore the security issue. Hence, many attacks have been found against existing WSN transport protocols [4]. Broadly speaking, these attacks can be classified into two groups: attacks against reliability and energy depleting attacks. Reliability attacks aim to mislead the nodes so that loss of a data packet remains undetected. In the case of energy depleting attacks, the goal of the attacker is to perform energy-intensive operations in order to deplete the nodes’ batteries [4]. In particular, using a fake or altered acknowledgment message, an attacker can give the sender the impression that data packets arrived safely when they may actually have been lost. Similarly, forging or altering negative acknowledgment packets to trigger unnecessary retransmission can lead to faster draining of the node’s batteries. While futile retransmissions do not directly harm the reliability of service, they are still undesirable. Systematic mathematical and automated methods are needed for finding the weaknesses in these protocols; however, this is a very hard task due to their complexity. This served as a motivation and challenge for our work, to which we proposed solutions.In this paper, we address the problem of formal and automated security verification of WSN transport protocols, which typically consist of the following behavioral characteristics: (b1) storing data packets in the buffer of intermediate sensor nodes; (b2) probabilistic and real-time behavior; (b3) performing cryptographic operations such as one-way hashing, computing message authentication codes (MACs); and so on. We propose a formal and an automated verification method, based on the application of process algebra and a model checking framework, respectively. For demonstration purposes, we apply the proposed methods for specifying and verifying the security of the DTSN and the SDTP protocols, which are representative in the sense that DTSN involve the first two behavioral characteristics (b1-b2), while SDTP covers all of the three points (b1–b3). Specifically, the main contributions of this paper are the followings.(i)
We propose a probabilistic timed calculus, calledc
r
y
p
t
t
i
m
e
p
r
o
b, for cryptographic protocols. To the best of our knowledge, this is the first of its kind in the sense that it combines the following three features: (i) it supports formal syntax and semantics for cryptographic primitives and operations; (ii) it supports time constructs similar to the concept of timed automata that enables us to verify real-time systems; (iii) it also includes the syntax and semantics of probabilistic constructs for analysing systems that perform probabilistic behavior. The basic concept of c
r
y
p
t
t
i
m
e
p
r
o
b is inspired by previous pieces of work [5–7] proposing solutions separately for each of the three discussed points. In particular, c
r
y
p
t
t
i
m
e
p
r
o
b is derived from the applied π-calculus [5], which defines an expressive syntax and semantics supporting cryptographic primitives to analyse security protocols; a probabilistic extension of the applied π-calculus [6]; and a process calculus for timed automata proposed in [7].
We note that, although in this paper the proposedc
r
y
p
t
t
i
m
e
p
r
o
b calculus is used for analysing WSN transport protocols, it is also suitable for reasoning about other systems that include cryptographic operations, as well as real-time and probabilistic behavior.
(ii)
Usingc
r
y
p
t
t
i
m
e
p
r
o
b we specify the behavior of the DTSN and SDTP protocols. We propose the novel definition of weak probabilistic timed bisimilarity and used it to prove the weaknesses of DTSN and SDTP, as well as the security of SDTP against some attacks.
(iii)
We provide an approach for the automatic security verification of the DTSN and SDTP protocols with the PAT process analysis toolkit [8], which is a powerful general purpose model checking framework. To the best of our knowledge PAT has not been used for this purpose before; however, in this paper we show that the power of PAT can be used to check some interesting security properties defined for these systems/protocols.The structure of the paper is as follows: note that, instead of putting into a separate section, we discuss the related pieces of work inside each section, where we compare them with our methods. In Section2, we start with the introduction of DTSN and SDTP. In Section 3, we discuss the base calculus, c
r
y
p
t, which is a modified variant of the well-known applied π-calculus [5], designed for analysing security protocols. The extension of c
r
y
p
t, called c
r
y
p
t
t
i
m
e
p
r
o
b, with timing and probabilistic modelling elements is given in Section 4. The security analysis of DTSN and SDTP, based on c
r
y
p
t
t
i
m
e
p
r
o
b, is provided in Section 5. The well-known model checking framework PAT and automatic verification of SDTP are given in Section 6. We also verified the DTSN protocol in PAT and found attacks against it; however, due to lack of space we do not discuss it in the paper. Interested readers can find more details in our longer report [11]. Finally, we conclude the paper and give an outlook on future pieces of work in Section 7.


## 2. The DTSN and SDTP Protocols

### 2.1.  DTSN: Distributed Transport for Sensor Networks

DTSN [2] is a reliable transport protocol developed for sensor networks where intermediate nodes between the source and the destination of a data flow cache data packets in a probabilistic manner such that they can retransmit them upon request. The main advantages of DTSN compared to a transport protocol that uses a fully end-to-end retransmission mechanism is that it allows intermediate nodes to cache and retransmit data packets; hence, the average number of hops that a retransmitted data packet must travel is smaller than the length of the route between the source and the destination. Intermediate nodes do not store all packets but only store packets with some probability p, which makes it more efficient. Note that, in the case of a fully end-to-end reliability mechanism, where only the source is allowed to retransmit lost data packets, retransmitted data packets always travel through the entire route from the source to the destination. Thus, DTSN improves the energy efficiency of the network compared to a transport protocol that uses a fully end-to-end retransmission mechanism.DTSN uses special packets to control caching and retransmissions. More specifically, there are three types of such control packets: Explicit Acknowledgment Requests (EARs), Positive Acknowledgments (A
C
K
s), and Negative Acknowledgments (N
A
C
K
s). The source sends an EAR packet after the transmission of a certain number of data packets or when its output buffer becomes full or when the application has not requested the transmission of any data during a predefined timeout period or due to the expiration of the E
A
R timer (EAR_timer).The activity timer and the EAR timer are launched by the source for ensuring that a session will finish in a finite period of time. The activity timer is launched when the source starts to handle the first data packet in a session, and it is reset when a new packet is stored or when an ACK or a NACK has been handled by the source. When the activity timer has expired, depending on the number of unconfirmed data packets, the session will be terminated or reset. The EAR timer is launched whenever an EAR packet or a data packet with the EAR bit set is sent.AnE
A
R may take the form of a bit flag piggybacked on the last data packet or an independent control packet. An E
A
R is also sent by an intermediate node or the source after retransmission of a series of data packets, piggybacked on the last retransmitted data packet [2]. Upon receipt of an EAR packet the destination sends an A
C
K or a N
A
C
K packet, depending on the existence of gaps in the received data packet stream. An A
C
K refers to a data packet sequence number n, and it should be interpreted such that all data packets with sequence number smaller than or equal to n were received by the destination. A N
A
C
K refers to a base sequence number n and it also contains a bitmap, in which each bit represents a different sequence number starting from the base sequence number n. A N
A
C
K should be interpreted such that all data packets with sequence number smaller than or equal to n were received by the destination and the data packets corresponding to the set bits in the bitmap are missing.Within a session, data packets are sequentially numbered. The Acknowledgment Window (AW) is defined as the number of data packets that the source transmits before generating and sending an EAR. The output buffer at the sender works as a sliding window, which can span more than one AW. Its size depends on the specific scenario, namely, the memory constraints of individual nodes.In DTSN, besides the source, intermediate nodes also processA
C
K and N
A
C
K packets. When an A
C
K packet with sequence number n is received by an intermediate node, it deletes all data packets with sequence number smaller than or equal to n from its cache and passes the A
C
K packet on to the next node on the route towards the source. When a N
A
C
K packet with base sequence number n is received by an intermediate node, it deletes all data packets with sequence number smaller than or equal to n from its cache and, in addition, it retransmits those missing data packets that are indicated in the N
A
C
K packet and stored in the cache of the intermediate node. The bits that correspond to the retransmitted data packets are cleared in the N
A
C
K packet, which is then passed on to the next node on the route towards the source. If all bits are cleared in the N
A
C
K, then the N
A
C
K packet essentially becomes an A
C
K referring to the base sequence number, and it is processed accordingly. In addition, the intermediate node sets the EAR flag in the last retransmitted data packet. The source manages its cache and retransmissions in the same way as the intermediate nodes, without passing on any A
C
K and N
A
C
K packets.Security Issues in DTSN. Upon receiving an A
C
K packet, intermediate nodes delete from their cache the stored messages whose sequence number is less than or equal to the sequence number in the A
C
K packet, because the intermediate nodes believe that acknowledged packets have been delivered successfully. Therefore, an attacker may cause permanent loss of some data packets by forging or altering A
C
K packets. This may put the reliability service provided by the protocol in danger. Moreover, an attacker can trigger unnecessary retransmission of the corresponding data packets by either setting bits in the bit map of the N
A
C
K packets or forging/altering N
A
C
K packets. Any unnecessary retransmission can lead to energy consumption and interference. Note that unnecessary retransmissions do not directly harm the reliability, but it is clear that such inefficiency is still undesirable.The destination sendsA
C
K or N
A
C
K packets upon reception of an E
A
R. Therefore, attacks aiming at replaying or forging E
A
R information, where the attacker always sets the EAR flag to 0 or 1, can have a harmful effect. Always setting the EAR flag to 0 prevents the destination from sending an A
C
K or N
A
C
K packet, while always setting it to 1 forces the destination to send control packets unnecessarily.


### 2.2. SDTP: A Secure Distributed Transport Protocol for WSNs

SDTP is a security extension of DTSN aiming at patching the security holes in DTSN. SDTP ensures that an intermediate node can verify if an acknowledgment or negative acknowledgment information has really been issued by the destination, if and only if the intermediate node actually has in its cache the data packet referred to by the ACK or NACK. Forged control information can propagate in the network but only until it hits an intermediate node that cached the corresponding data packet; this node can detect the forgery and drop the forged control packet.In particular, the security solution of SDTP works as follows [3]: each data packet is extended with an A
C
K MAC and a N
A
C
K MAC, which are computed over the whole packet with two different keys, an ACK key (K
A
C
K) and a N
A
C
K key (K
N
A
C
K). Both keys are known only to the source and the destination and are specific to the data packet; hence, these keys are referred to as per-packet keys.When the destination receives a data packet, it can check the authenticity and integrity of each received data packet by verifying the two MAC values. Upon receipt of anE
A
R packet, the destination sends an A
C
K or a N
A
C
K packet, depending on the gaps in the received data buffer. If the destination sends an A
C
K referring to a data packet with sequence number n, the destination reveals (included in the A
C
K packet) the corresponding A
C
K key; similarly, when it wants to signal that this data packet is missing, the destination reveals the corresponding N
A
C
K key by including it in the N
A
C
K packet. Any intermediate node that stores the packets in question can verify if the A
C
K or N
A
C
K message that it receives is authentic by checking if the appropriate MAC in the stored data packet verifies correctly the A
C
K key included in the A
C
K packet. In case of successful verification, the intermediate node deletes the corresponding data packets (whose sequence number is smaller than or equal to n) from its cache.When an ACK packet is received by an intermediate node or the source, the node first checks if it has the corresponding data packet. If not, then the ACK packet is simply passed on to the next node towards the source. Otherwise, the node uses the ACK key obtained from the ACK packet to verify the ACK MAC value in the data packet. If this verification is successful, then the data packet can be deleted from the cache and the ACK packet is passed on to the next node towards the source. If the verification of the MAC is not successful, then the ACK packet is silently dropped.When a NACK packet is received by an intermediate node or the source, the node processes the acknowledgment part of the NACK packet as described above. In addition, it also checks if it has any of the data packets that correspond to the set bits in the bitmap of the NACK packet. If it does not have any of those data packets, it passes on the NACK without modification. Otherwise, for each data packet that it has and that is marked as missing in the NACK packet, it verifies the NACK MAC of the data packet with the corresponding NACK key obtained from the NACK packet. If this verification is successful, then the data packet is scheduled for retransmission, the corresponding bit in the NACK packet is cleared, and the NACK key is removed from the NACK packet. After these modifications, the NACK packet is passed on to the next node towards the source.TheA
C
K and N
A
C
K key generation and management in SDTP are as follows. The source and the destination share a secret which we call the session master key, and we denote it by K. From this, both the source and destination derive an A
C
K master key K
A
C
K and a N
A
C
K master key K
N
A
C
K for a given session as follows:
(1)
K
A
C
K
=
PRF
(
K
;
“
A
C
K
master
key”
;
SessionID
)
,
K
N
A
C
K
=
PRF
(
K
;
“
N
A
C
K
master
key”
;
SessionID
)
,
where PRF is a pseudorandom function [9] and SessionID is a session identifier.SDTP assumes a preestablished shared secret value, such as a node key shared by the node and the base station, which can be configured manually in the node before its deployment. Denoting the shared secret byS, the session master key K is then derived as follows:
(2)
K
=
PRF
(
S
;
“session
master
key”
;
SessionID
)
.The ACK keyK
A
C
K
(
n
) and the NACK key K
N
A
C
K
(
n
) for the nth packet (i.e., whose sequence number is n) are computed as follows:
(3)
K
A
C
K
(
n
)
=
PRF
(
K
A
C
K
;
“per
packet
A
C
K
key”
;
n
)
,
K
N
A
C
K
(
n
)
=
PRF
(
K
N
A
C
K
;
“per
packet
N
A
C
K
key”
;
n
)
.Note that both the source and the destination can compute all these keys as they both possess the session master keyK. Moreover, PRF is a one-way function; therefore, when the ACK and NACK keys are revealed, the master keys cannot be computed from them; and consequently, as yet unrevealed ACK and NACK keys remain secrets too.Security Issues in SDTP. The rationality behind this security solution is that the shared secret S is never leaked, and hence only the source and the destination can produce the right ACK and NACK master keys and per-packet keys. Since the source never reveals these keys, the intermediate node can be sure that the control information has been sent by the destination. In addition, because the per-packet keys are computed by a one-way function, when the ACK and NACK keys are revealed, the master keys cannot be computed from them; hence, the yet unrevealed ACK and NACK keys cannot be derived. These issues give the protocol designers an impression that SDTP is secure; however, we will formally prove that SDTP is still vulnerable and showing a tricky attack against it.


## 2.1.  DTSN: Distributed Transport for Sensor Networks

DTSN [2] is a reliable transport protocol developed for sensor networks where intermediate nodes between the source and the destination of a data flow cache data packets in a probabilistic manner such that they can retransmit them upon request. The main advantages of DTSN compared to a transport protocol that uses a fully end-to-end retransmission mechanism is that it allows intermediate nodes to cache and retransmit data packets; hence, the average number of hops that a retransmitted data packet must travel is smaller than the length of the route between the source and the destination. Intermediate nodes do not store all packets but only store packets with some probability p, which makes it more efficient. Note that, in the case of a fully end-to-end reliability mechanism, where only the source is allowed to retransmit lost data packets, retransmitted data packets always travel through the entire route from the source to the destination. Thus, DTSN improves the energy efficiency of the network compared to a transport protocol that uses a fully end-to-end retransmission mechanism.DTSN uses special packets to control caching and retransmissions. More specifically, there are three types of such control packets: Explicit Acknowledgment Requests (EARs), Positive Acknowledgments (A
C
K
s), and Negative Acknowledgments (N
A
C
K
s). The source sends an EAR packet after the transmission of a certain number of data packets or when its output buffer becomes full or when the application has not requested the transmission of any data during a predefined timeout period or due to the expiration of the E
A
R timer (EAR_timer).The activity timer and the EAR timer are launched by the source for ensuring that a session will finish in a finite period of time. The activity timer is launched when the source starts to handle the first data packet in a session, and it is reset when a new packet is stored or when an ACK or a NACK has been handled by the source. When the activity timer has expired, depending on the number of unconfirmed data packets, the session will be terminated or reset. The EAR timer is launched whenever an EAR packet or a data packet with the EAR bit set is sent.AnE
A
R may take the form of a bit flag piggybacked on the last data packet or an independent control packet. An E
A
R is also sent by an intermediate node or the source after retransmission of a series of data packets, piggybacked on the last retransmitted data packet [2]. Upon receipt of an EAR packet the destination sends an A
C
K or a N
A
C
K packet, depending on the existence of gaps in the received data packet stream. An A
C
K refers to a data packet sequence number n, and it should be interpreted such that all data packets with sequence number smaller than or equal to n were received by the destination. A N
A
C
K refers to a base sequence number n and it also contains a bitmap, in which each bit represents a different sequence number starting from the base sequence number n. A N
A
C
K should be interpreted such that all data packets with sequence number smaller than or equal to n were received by the destination and the data packets corresponding to the set bits in the bitmap are missing.Within a session, data packets are sequentially numbered. The Acknowledgment Window (AW) is defined as the number of data packets that the source transmits before generating and sending an EAR. The output buffer at the sender works as a sliding window, which can span more than one AW. Its size depends on the specific scenario, namely, the memory constraints of individual nodes.In DTSN, besides the source, intermediate nodes also processA
C
K and N
A
C
K packets. When an A
C
K packet with sequence number n is received by an intermediate node, it deletes all data packets with sequence number smaller than or equal to n from its cache and passes the A
C
K packet on to the next node on the route towards the source. When a N
A
C
K packet with base sequence number n is received by an intermediate node, it deletes all data packets with sequence number smaller than or equal to n from its cache and, in addition, it retransmits those missing data packets that are indicated in the N
A
C
K packet and stored in the cache of the intermediate node. The bits that correspond to the retransmitted data packets are cleared in the N
A
C
K packet, which is then passed on to the next node on the route towards the source. If all bits are cleared in the N
A
C
K, then the N
A
C
K packet essentially becomes an A
C
K referring to the base sequence number, and it is processed accordingly. In addition, the intermediate node sets the EAR flag in the last retransmitted data packet. The source manages its cache and retransmissions in the same way as the intermediate nodes, without passing on any A
C
K and N
A
C
K packets.Security Issues in DTSN. Upon receiving an A
C
K packet, intermediate nodes delete from their cache the stored messages whose sequence number is less than or equal to the sequence number in the A
C
K packet, because the intermediate nodes believe that acknowledged packets have been delivered successfully. Therefore, an attacker may cause permanent loss of some data packets by forging or altering A
C
K packets. This may put the reliability service provided by the protocol in danger. Moreover, an attacker can trigger unnecessary retransmission of the corresponding data packets by either setting bits in the bit map of the N
A
C
K packets or forging/altering N
A
C
K packets. Any unnecessary retransmission can lead to energy consumption and interference. Note that unnecessary retransmissions do not directly harm the reliability, but it is clear that such inefficiency is still undesirable.The destination sendsA
C
K or N
A
C
K packets upon reception of an E
A
R. Therefore, attacks aiming at replaying or forging E
A
R information, where the attacker always sets the EAR flag to 0 or 1, can have a harmful effect. Always setting the EAR flag to 0 prevents the destination from sending an A
C
K or N
A
C
K packet, while always setting it to 1 forces the destination to send control packets unnecessarily.


## 2.2. SDTP: A Secure Distributed Transport Protocol for WSNs

SDTP is a security extension of DTSN aiming at patching the security holes in DTSN. SDTP ensures that an intermediate node can verify if an acknowledgment or negative acknowledgment information has really been issued by the destination, if and only if the intermediate node actually has in its cache the data packet referred to by the ACK or NACK. Forged control information can propagate in the network but only until it hits an intermediate node that cached the corresponding data packet; this node can detect the forgery and drop the forged control packet.In particular, the security solution of SDTP works as follows [3]: each data packet is extended with an A
C
K MAC and a N
A
C
K MAC, which are computed over the whole packet with two different keys, an ACK key (K
A
C
K) and a N
A
C
K key (K
N
A
C
K). Both keys are known only to the source and the destination and are specific to the data packet; hence, these keys are referred to as per-packet keys.When the destination receives a data packet, it can check the authenticity and integrity of each received data packet by verifying the two MAC values. Upon receipt of anE
A
R packet, the destination sends an A
C
K or a N
A
C
K packet, depending on the gaps in the received data buffer. If the destination sends an A
C
K referring to a data packet with sequence number n, the destination reveals (included in the A
C
K packet) the corresponding A
C
K key; similarly, when it wants to signal that this data packet is missing, the destination reveals the corresponding N
A
C
K key by including it in the N
A
C
K packet. Any intermediate node that stores the packets in question can verify if the A
C
K or N
A
C
K message that it receives is authentic by checking if the appropriate MAC in the stored data packet verifies correctly the A
C
K key included in the A
C
K packet. In case of successful verification, the intermediate node deletes the corresponding data packets (whose sequence number is smaller than or equal to n) from its cache.When an ACK packet is received by an intermediate node or the source, the node first checks if it has the corresponding data packet. If not, then the ACK packet is simply passed on to the next node towards the source. Otherwise, the node uses the ACK key obtained from the ACK packet to verify the ACK MAC value in the data packet. If this verification is successful, then the data packet can be deleted from the cache and the ACK packet is passed on to the next node towards the source. If the verification of the MAC is not successful, then the ACK packet is silently dropped.When a NACK packet is received by an intermediate node or the source, the node processes the acknowledgment part of the NACK packet as described above. In addition, it also checks if it has any of the data packets that correspond to the set bits in the bitmap of the NACK packet. If it does not have any of those data packets, it passes on the NACK without modification. Otherwise, for each data packet that it has and that is marked as missing in the NACK packet, it verifies the NACK MAC of the data packet with the corresponding NACK key obtained from the NACK packet. If this verification is successful, then the data packet is scheduled for retransmission, the corresponding bit in the NACK packet is cleared, and the NACK key is removed from the NACK packet. After these modifications, the NACK packet is passed on to the next node towards the source.TheA
C
K and N
A
C
K key generation and management in SDTP are as follows. The source and the destination share a secret which we call the session master key, and we denote it by K. From this, both the source and destination derive an A
C
K master key K
A
C
K and a N
A
C
K master key K
N
A
C
K for a given session as follows:
(1)
K
A
C
K
=
PRF
(
K
;
“
A
C
K
master
key”
;
SessionID
)
,
K
N
A
C
K
=
PRF
(
K
;
“
N
A
C
K
master
key”
;
SessionID
)
,
where PRF is a pseudorandom function [9] and SessionID is a session identifier.SDTP assumes a preestablished shared secret value, such as a node key shared by the node and the base station, which can be configured manually in the node before its deployment. Denoting the shared secret byS, the session master key K is then derived as follows:
(2)
K
=
PRF
(
S
;
“session
master
key”
;
SessionID
)
.The ACK keyK
A
C
K
(
n
) and the NACK key K
N
A
C
K
(
n
) for the nth packet (i.e., whose sequence number is n) are computed as follows:
(3)
K
A
C
K
(
n
)
=
PRF
(
K
A
C
K
;
“per
packet
A
C
K
key”
;
n
)
,
K
N
A
C
K
(
n
)
=
PRF
(
K
N
A
C
K
;
“per
packet
N
A
C
K
key”
;
n
)
.Note that both the source and the destination can compute all these keys as they both possess the session master keyK. Moreover, PRF is a one-way function; therefore, when the ACK and NACK keys are revealed, the master keys cannot be computed from them; and consequently, as yet unrevealed ACK and NACK keys remain secrets too.Security Issues in SDTP. The rationality behind this security solution is that the shared secret S is never leaked, and hence only the source and the destination can produce the right ACK and NACK master keys and per-packet keys. Since the source never reveals these keys, the intermediate node can be sure that the control information has been sent by the destination. In addition, because the per-packet keys are computed by a one-way function, when the ACK and NACK keys are revealed, the master keys cannot be computed from them; hence, the yet unrevealed ACK and NACK keys cannot be derived. These issues give the protocol designers an impression that SDTP is secure; however, we will formally prove that SDTP is still vulnerable and showing a tricky attack against it.


## 3.c
r
y
p
t: The Calculus for Cryptographic Protocols

c
r
y
p
t is the base calculus for specifying and analysing cryptographic protocols, without supporting real-time and probabilistic systems. c
r
y
p
t can be seen as a modified variant of the applied π-calculus [5], designed for analysing security protocols and proving their security properties in a convenient way. Our goal is to extend c
r
y
p
t with time and probabilistic modelling elements adopting the concept of timed and probabilistic automata, and to do this, we need to modify the applied π-calculus in some points. Namely, we replace process replication with recursive process invocation; we add definition for positive integers and comparison rules for them; we also define syntax for cache/buffer entry.


### 3.1. Syntax and Semantics

We assume an infinite set ofnames  𝒩 and variables  𝒱, where 𝒩
∩
𝒱
=
∅. Further, we define a set of distinguished variables ℰ that model the cache entries for entities that store data. In the set 𝒩, we distinguish channel names, and other kinds of data. Channel names are denoted by c
i with different indices such that c
i
≠
c
j, i
≠
j. The set of nonnegative integers is denoted by ℐ, and its elements range over i
n
t
i with different indices that are corresponding to the numbers 0, 1, 2, and so forth.Further, we let the remaining data be denoted bym
i, n
i, and k
i. The variables are denoted by x
i, y
i, z
i, and the cache entries by e
i with different indices. The names and variables with different indices are different. We let ℱ be the set of function symbols. To verify security protocols, in our case, the function symbols capture the cryptographic primitives such as hash, encryption, and MAC function. Finally, we assume the type system of the terms as in the case of the applied π-calculus.We define a set of terms as(4)
t
:
:
=
c
i
∣
i
n
t
i
∣
n
i
,
m
i
,
k
i
∣
x
i
,
y
i
,
z
i
∣
e
i
∣
f
(
t
1
,
…
,
t
k
)
,
where ∣ represents “or." In particular, a term can be the following.(i)
c
i models a communication channel between honest parties.
(ii)
n
i, m
i, and k
i are names and are used to model some data.
(iii)
x
i, y
i, and z
i are variables that can represent any term; that is, any term can be bound to variables, similarly as in case of the applied π-calculus [5].
(iv)
e
i is a cache entry.
(v)
Finally,f is a function with arity k and is used to construct terms and to model cryptographic primitives and messages. Complex messages are modelled by the function tuple with k terms: tuple(t
1
,
…
,
t
k), which we abbreviate as (t
1
,
…
,
t
k). The function symbol with arity zero is a constant.
For example, digital signature, encryption, and message authentication code (MAC) can be modelled by the functionss
i
g
n
(
m
,
k
), e
n
c
(
m
,
k
), and M
A
C
(
m
,
k
), where m models the message to be signed, to be encrypted, and to be MAC-ed, respectively, and k models the secret key. Verification of signatures and MACs, as well as decryption, is modelled by equations. For instance, the equation d
e
c
(
e
n
c
(
m
,
k
)
,
k
)
=
m says that, if we decrypt the encryption enc(m, k) with the right key, then we will get the message as a result. If incorrect key is used for decryption then the process will get stuck and will not continue to run.
(vi)
i
n
t
i ranges over special functions for modelling nonnegative integers. Formally, let 0 be the base element of set ℐ and is formally defined as the function named by 0. Each further integer is defined as a constructor function named by 1, 2, and so forth. Let the function i
n
c
(
i
n
t
i
) be the function that increases the integer i
n
t
i by one. Numbers 1
,
2
,
…, are modelled by functions i
n
c
(
0
), i
n
c
(
1
),…, respectively. The relation between these integers is defined by i
n
t
i
<
i
n
c
(
i
n
t
i
) and i
n
t
i
=
i
n
t
i.The internal operation of communication entities in the system is modelled byprocesses. Processes can be specified with the following syntax and inductive definition:
(5)
P
,
Q
,
R
:
:
=
P
r
o
c
e
s
s
e
s
c
¯
〈
t
〉
·
P
|
c
(
x
)
·
P
|
(
P
∣
Q
)
|
P
[
]
Q
|
ν
n
·
P
∣
I
(
y
1
,
…
,
y
n
)
∣
[
t
i
=
t
j
]
P
else
Q
∣
[
i
n
t
i
≥
i
n
t
j
]
P
else
Q
∣
[
i
n
t
i
>
i
n
t
j
]
P
else
Q
∣
[
t
i
=
t
j
]
P
∣
[
i
n
t
i
≥
i
n
t
j
]
P
∣
[
i
n
t
i
>
i
n
t
j
]
P
∣
n
i
l
∣
let
(
x
=
t
)
in
P
,
let
(
e
=
t
)
in
P
.
(i)
The processc
¯
〈
t
〉
·
P represents the sending of message t on channel c, followed by the execution of P. Process c
(
x
)
·
P represents the receiving of some message, which is bound to x in P.
(ii)
In the compositionP
∣
Q, processes P and Q run in parallel. Each may interact with the other on channels known to both or with the outside world, independently of the other. For example, the communication between the sending process c
¯
〈
t
〉
·
P and receiving process c
(
x
)
·
P can be described as the parallel composition c
¯
〈
t
〉
·
P
∣
c
(
x
)
·
Q. The communication can be described as a reduction step of the parallel composition, namely, c
¯
〈
t
〉
·
P
∣
c
(
x
)
·
Q
→
P
∣
Q
{
t
/
x
}. In the resulted process, c
¯
〈
t
〉
·
P proceeds to P (meaning that t has been sent), while c
(
x
)
·
Q proceeds to Q
{
t
/
x
} (meaning that t has been received and now it can be used in Q for further computations).
(iii)
A choiceP
[
]
Q can behave as either P or Q depending on the first visible/invisible action of P and Q. If the first action of P is enabled but the first action of Q’s is not then P is chosen, and vice versa. In case that both actions are enabled the behavior is the same as a nondeterministic choice.
(iv)
A restrictionν
n
·
P is a process that makes a new, private (restricted) name n and then behaves as P. The scope of n is restricted to P and is available only for the process within its scope. A private channel c restricted to P is defined by ν
c
·
P, which does not allow the attackers to eavesdrop on the channel.
(v)
A typical way of specifying infinite behavior is by using parametric recursive definitions, like in theπ-calculus [10]. Here I
(
y
1
,
…
,
y
n
) is an identifier (or invocation) of arity n. We assume that every such identifier has a unique, possibly recursive, definition I
(
x
1
,
…
,
x
n
)
=
d
e
f
P, where x
i’s are pairwise distinct. The intuition is that I
(
y
1
,
…
,
y
n
) behaves as P with each x
i replaced by y
i, respectively.
(vi)
In processes[
t
i
=
t
j
]
P  else
Q; [
i
n
t
i
≥
i
n
t
j
]
P  else
Q; and [
i
n
t
i
>
i
n
t
j
]
P  else
Q: if (
t
i
=
t
j
), (
i
n
t
i
≥
i
n
t
j
) and (
i
n
t
i
>
i
n
t
j
), respectively, then process P is “activated”; else they behave as Q. When Q is the nil process, we simply remove the else-branch from the processes.
(vii)
The processnil does nothing and is used to model the termination of a process behavior.
(viii)
Finally,l
e
t
(
x
=
t
)
i
n
P (or let
(
e
=
t
)
i
n
P) mean that every occurrence of x (or e) in P is bound to t. We adopt the notion of environment, well-known in process algebra, which is used to model the attacker(s) who can obtain the (publicly) exchanged messages and can modify them. Moreover, we adopt the notation of the extended process and active substitution in the applied π-calculus [5] to model the information that the attacker(s) (or the environment) is getting to know during the system run. The definition of the extended process is as follows:
(6)
A
,
B
,
C
:
:
=
P
|
(
A
∣
B
)
|
ν
n
·
A
|
ν
x
·
A
|
{
t
x
}
.
(i)
P is a plain network that we already discussed above.
(ii)
A
∣
B is a parallel composition of two extended process.
(iii)
ν
n
·
A is a restriction of the name n to A.
(iv)
ν
x
·
A is a restriction of the variable x to A.
(v)
{
t
/
x
} means that the binding of t to x, denoted by {
t
/
x
}, is applied to any process that is in parallel composition with {
t
/
x
}. Intuitively, the binding applies to any process that comes into contact with it. To restrict the binding {
t
/
x
} to a process P, we use the variable restriction ν
x over (
{
t
/
x
}
∣
P
), namely, ν
x
·
(
{
t
/
x
}
∣
P
). Using this, the equivalent definition of process c
¯
〈
t
〉
·
P can be given by ν
x
·
(
c
¯
〈
x
〉
·
P
∣
{
t
/
x
}). Active substitutions are always assumed to be cycle-free.
We definef
v
(
A
), b
v
(
A
), f
n
(
A
), and b
n
(
A
) for the sets of free and bound variables and free and bound names of A, respectively. These sets are defined as follow:
(7)
f
v
(
{
t
x
}
)
=
d
e
f
f
v
(
t
)
∪
{
x
}
,
f
n
(
{
t
x
}
)
=
d
e
f
f
n
(
t
)
.
b
v
(
{
t
x
}
)
=
d
e
f
∅
,
b
n
(
{
t
x
}
)
=
d
e
f
b
n
(
t
)
.
The concept of bound and free values is similar to local and global scope in programming languages. The scope of names and variables is delimited by bindersc
(
x
) (i.e., input) and ν
n or ν
x (i.e., restriction). The set of bound names b
n
(
A
) contains every name n which is under the restriction ν
n inside A. The set of bound variables b
v
(
A
) consists of all those variables x occurring in A that are bound by restriction ν
x or input c
(
x
). Further, we define the set of free names and the set of free variables. The set of free names in A, denoted by f
n
(
A
), consists of those names n occurring in A that are not restricted names. The set of free variables f
v
(
A
) contains the variables x occurring in A which are not restricted variables (ν
x) or input variable (c
(
x
)). A plain process P is closed if it contains no free variable. An extended process is closed when every variable x is either bound or defined by an active substitution.As in the appliedπ-calculus, a frame (φ) is an extended process built up from the nil process and active substitutions of the form {
t
/
x
} by parallel composition and restrictions. Formally, the frame φ
(
A
) of the extended process, A
=
ν
n
1
⋯
n
k
(
{
t
1
/
x
1
}
|
⋯
|
{
t
n
/
x
n
}
∣
P
), is ν
n
1
…
n
k
(
{
t
1
/
x
1
}
|
⋯
|
{
t
n
/
x
n
}
). The domain of the frame φ
(
A
) (denoted by d
o
m
(
A
)) is the set {
x
1
,
…
,
x
n
}.Intuitively, the frameφ
(
A
) accounts for the static knowledge exposed by A to its environment but not for dynamic behavior. The frame allows access to terms that the environment cannot construct. For instance, after the term t (not available for the environment) is output in P resulting in P
′
∣
{
t
/
x
}, t becomes available for the environment. Finally, let σ range over substitutions (i.e., variable bindings). We write σ
t for the result of applying σ to the variables in t.


#### 3.1.1. Labeled Transition System (→
α)

The operational semantics for processes is defined as a labeled transition system(
𝒫
,
𝒢
,
→
) where 𝒫 represents a set of extended processes, 𝒢 is a set of labels, and →
⊆
𝒫
×
𝒢
×
𝒫.Specifically, the labeled semantics defines a ternary relation, written asA
→
α
B, where α is a label of the form τ, c
(
t
), c
¯
〈
x
〉, ν
x
·
c
¯
〈
x
〉 where x is a variable of base type and t is a term. The transition A
→
τ
B represents a silent move that is used to model the internal operation/computation of processes. These internal operations, such as the verification steps made on the received data, are not visible for the outside world and, hence, to the attacker(s). The transition A
→
c
(
t
)
B means that the process A performs an input of the term t from the environment on the channel c and the resulting process is B. The label c
¯
〈
x
〉 is for output action of a free variable x. Finally, the label α is ν
x
·
c
¯
〈
x
〉 when a term is output on c. In the following, we give some examples for labeled transitions.Silent Transition (Internal Computations/Verification) Rules for Processes
(Let)
letx
=
t
in
P
→
τ
P
{
t
/
x
}; let e
=
t
in
P
→
τ
P
{
t
/
e
}.
(If1)
[
t
i
=
t
j
]
P
else
Q
→
τ
P
;
[
t
i
=
t
j
]
P
→
τ
P
(
if
t
i
=
t
j
).
(If2)
[
t
i
=
t
j
]
P
else
Q
→
τ
Q
;
[
t
i
=
t
j
]
P
→
τ  nil  (
if
t
i
≠
t
j
).
(If3)
[
i
n
t
i
>
i
n
t
j
]
P
else
Q
→
τ
P
;
[
i
n
t
i
>
i
n
t
j
]
P
→
τ
P
(
if
i
n
t
i
>
i
n
t
j
).
(If4)
[
i
n
t
i
>
i
n
t
j
]
P
else
Q
→
τ
Q
;
[
i
n
t
i
>
i
n
t
j
]
P
→
τ  nil  (
if
i
n
t
i
≤
i
n
t
j
).Action Transition (Message Input/Output) Rules for Processes
(In)c
(
x
)
·
P
→
c
(
t
)
P
{
t
/
x
};
(Open)if
A
→
c
¯
〈
u
〉
A
′
,
u
≠
c
then
ν
u
·
A
→
ν
u
.
c
¯
〈
u
〉
A
′.
Let binds a variable to a term in a process; rules If1–If4 check the relation of two terms or integers. Rule (In) says that, when a term t is received, it is bound to every occurrence of x in P. Rule (Open) defines the output of a restricted name. Note that these rules are examples from the full list of rules, which can be found in [11]. From rule (Open) and the fact that ν
x
·
(
c
¯
〈
x
〉
·
P
|
{
t
/
x
}
) is equivalent to c
¯
〈
t
〉
·
P, we have two additional output rules(Out-1)
c
¯
〈
t
〉
·
P
→
ν
x
·
c
¯
〈
x
〉
{
t
/
x
}
∣
P,
(Out-2)
ν
n
·
(
c
¯
〈
t
〉
·
P
)
→
ν
x
.
c
¯
〈
x
〉
ν
n
·
(
{
t
/
x
}
∣
P
).For instance, based on the labeled transition system, we have the following transitions:(8)
c
¯
〈
t
1
〉
·
c
¯
〈
t
2
〉
·
P
→
ν
x
1
·
c
¯
〈
x
1
〉
{
t
1
x
1
}
∣
c
¯
〈
t
2
〉
·
P
→
ν
x
2
·
c
¯
〈
x
2
〉
{
t
1
x
1
}
∣
{
t
2
x
2
}
∣
P
.After sending the termst
1 and t
2 on public channel c (modeled by action transitions →
ν
x
1
·
c
¯
〈
x
1
〉 and →
ν
x
2
·
c
¯
〈
x
2
〉, resp.), t
1 and t
2 become available for the environment (attacker), whose fact is specified by the active substitutions {
t
1
/
x
1
} and {
t
2
/
x
2
}.Similarly as in [5], we define an equational theory
E
q, that is, a set of equations of the form t
1
=
t
2. This allows us to define cryptographic primitives and operations, such as one-way hash function and MAC computation. For instance, the function Tuple models a tuple of n terms t
1
,
t
2
,
…
,
t
n, and its inverse function i returns the ith element of a tuple of n elements, where i
∈
{
1
,
…
,
n
}. We abbreviate the tuple as (
t
1
,
t
2
,
…
,
t
n
) in rest of the paper:
(9)
T
u
p
l
e
(
t
1
,
t
2
,
…
,
t
n
)
;
i
(
t
1
,
t
2
,
…
,
t
n
)
=
t
i
.We model the keyed hash or MAC function with symmetric keyK with the binary function MAC. The MAC verification is defined in the form of the following equation:
(10)
M
A
C
(
t
,
K
)
;
C
h
e
c
k
M
A
C
(
M
A
C
(
t
,
K
)
,
K
)
=
o
kFunctionM
A
C computes the message authentication code of message t using secret key K. The shared key between node l
i and node l
j is modelled by function K
(
l
i
,
l
j
). The MAC verification defined by the function C
h
e
c
k
M
A
C is successful (returns a special name o
k) if the keys match each other.We can also model many other cryptographic operations and primitives such as symmetric and asymmetric encryption, digital signature, and one-way hash function. However, in this paper we omit to detail them because we do not use these operations. An interested reader can find more details in our longer report [11].


## 3.1. Syntax and Semantics

We assume an infinite set ofnames  𝒩 and variables  𝒱, where 𝒩
∩
𝒱
=
∅. Further, we define a set of distinguished variables ℰ that model the cache entries for entities that store data. In the set 𝒩, we distinguish channel names, and other kinds of data. Channel names are denoted by c
i with different indices such that c
i
≠
c
j, i
≠
j. The set of nonnegative integers is denoted by ℐ, and its elements range over i
n
t
i with different indices that are corresponding to the numbers 0, 1, 2, and so forth.Further, we let the remaining data be denoted bym
i, n
i, and k
i. The variables are denoted by x
i, y
i, z
i, and the cache entries by e
i with different indices. The names and variables with different indices are different. We let ℱ be the set of function symbols. To verify security protocols, in our case, the function symbols capture the cryptographic primitives such as hash, encryption, and MAC function. Finally, we assume the type system of the terms as in the case of the applied π-calculus.We define a set of terms as(4)
t
:
:
=
c
i
∣
i
n
t
i
∣
n
i
,
m
i
,
k
i
∣
x
i
,
y
i
,
z
i
∣
e
i
∣
f
(
t
1
,
…
,
t
k
)
,
where ∣ represents “or." In particular, a term can be the following.(i)
c
i models a communication channel between honest parties.
(ii)
n
i, m
i, and k
i are names and are used to model some data.
(iii)
x
i, y
i, and z
i are variables that can represent any term; that is, any term can be bound to variables, similarly as in case of the applied π-calculus [5].
(iv)
e
i is a cache entry.
(v)
Finally,f is a function with arity k and is used to construct terms and to model cryptographic primitives and messages. Complex messages are modelled by the function tuple with k terms: tuple(t
1
,
…
,
t
k), which we abbreviate as (t
1
,
…
,
t
k). The function symbol with arity zero is a constant.
For example, digital signature, encryption, and message authentication code (MAC) can be modelled by the functionss
i
g
n
(
m
,
k
), e
n
c
(
m
,
k
), and M
A
C
(
m
,
k
), where m models the message to be signed, to be encrypted, and to be MAC-ed, respectively, and k models the secret key. Verification of signatures and MACs, as well as decryption, is modelled by equations. For instance, the equation d
e
c
(
e
n
c
(
m
,
k
)
,
k
)
=
m says that, if we decrypt the encryption enc(m, k) with the right key, then we will get the message as a result. If incorrect key is used for decryption then the process will get stuck and will not continue to run.
(vi)
i
n
t
i ranges over special functions for modelling nonnegative integers. Formally, let 0 be the base element of set ℐ and is formally defined as the function named by 0. Each further integer is defined as a constructor function named by 1, 2, and so forth. Let the function i
n
c
(
i
n
t
i
) be the function that increases the integer i
n
t
i by one. Numbers 1
,
2
,
…, are modelled by functions i
n
c
(
0
), i
n
c
(
1
),…, respectively. The relation between these integers is defined by i
n
t
i
<
i
n
c
(
i
n
t
i
) and i
n
t
i
=
i
n
t
i.The internal operation of communication entities in the system is modelled byprocesses. Processes can be specified with the following syntax and inductive definition:
(5)
P
,
Q
,
R
:
:
=
P
r
o
c
e
s
s
e
s
c
¯
〈
t
〉
·
P
|
c
(
x
)
·
P
|
(
P
∣
Q
)
|
P
[
]
Q
|
ν
n
·
P
∣
I
(
y
1
,
…
,
y
n
)
∣
[
t
i
=
t
j
]
P
else
Q
∣
[
i
n
t
i
≥
i
n
t
j
]
P
else
Q
∣
[
i
n
t
i
>
i
n
t
j
]
P
else
Q
∣
[
t
i
=
t
j
]
P
∣
[
i
n
t
i
≥
i
n
t
j
]
P
∣
[
i
n
t
i
>
i
n
t
j
]
P
∣
n
i
l
∣
let
(
x
=
t
)
in
P
,
let
(
e
=
t
)
in
P
.
(i)
The processc
¯
〈
t
〉
·
P represents the sending of message t on channel c, followed by the execution of P. Process c
(
x
)
·
P represents the receiving of some message, which is bound to x in P.
(ii)
In the compositionP
∣
Q, processes P and Q run in parallel. Each may interact with the other on channels known to both or with the outside world, independently of the other. For example, the communication between the sending process c
¯
〈
t
〉
·
P and receiving process c
(
x
)
·
P can be described as the parallel composition c
¯
〈
t
〉
·
P
∣
c
(
x
)
·
Q. The communication can be described as a reduction step of the parallel composition, namely, c
¯
〈
t
〉
·
P
∣
c
(
x
)
·
Q
→
P
∣
Q
{
t
/
x
}. In the resulted process, c
¯
〈
t
〉
·
P proceeds to P (meaning that t has been sent), while c
(
x
)
·
Q proceeds to Q
{
t
/
x
} (meaning that t has been received and now it can be used in Q for further computations).
(iii)
A choiceP
[
]
Q can behave as either P or Q depending on the first visible/invisible action of P and Q. If the first action of P is enabled but the first action of Q’s is not then P is chosen, and vice versa. In case that both actions are enabled the behavior is the same as a nondeterministic choice.
(iv)
A restrictionν
n
·
P is a process that makes a new, private (restricted) name n and then behaves as P. The scope of n is restricted to P and is available only for the process within its scope. A private channel c restricted to P is defined by ν
c
·
P, which does not allow the attackers to eavesdrop on the channel.
(v)
A typical way of specifying infinite behavior is by using parametric recursive definitions, like in theπ-calculus [10]. Here I
(
y
1
,
…
,
y
n
) is an identifier (or invocation) of arity n. We assume that every such identifier has a unique, possibly recursive, definition I
(
x
1
,
…
,
x
n
)
=
d
e
f
P, where x
i’s are pairwise distinct. The intuition is that I
(
y
1
,
…
,
y
n
) behaves as P with each x
i replaced by y
i, respectively.
(vi)
In processes[
t
i
=
t
j
]
P  else
Q; [
i
n
t
i
≥
i
n
t
j
]
P  else
Q; and [
i
n
t
i
>
i
n
t
j
]
P  else
Q: if (
t
i
=
t
j
), (
i
n
t
i
≥
i
n
t
j
) and (
i
n
t
i
>
i
n
t
j
), respectively, then process P is “activated”; else they behave as Q. When Q is the nil process, we simply remove the else-branch from the processes.
(vii)
The processnil does nothing and is used to model the termination of a process behavior.
(viii)
Finally,l
e
t
(
x
=
t
)
i
n
P (or let
(
e
=
t
)
i
n
P) mean that every occurrence of x (or e) in P is bound to t. We adopt the notion of environment, well-known in process algebra, which is used to model the attacker(s) who can obtain the (publicly) exchanged messages and can modify them. Moreover, we adopt the notation of the extended process and active substitution in the applied π-calculus [5] to model the information that the attacker(s) (or the environment) is getting to know during the system run. The definition of the extended process is as follows:
(6)
A
,
B
,
C
:
:
=
P
|
(
A
∣
B
)
|
ν
n
·
A
|
ν
x
·
A
|
{
t
x
}
.
(i)
P is a plain network that we already discussed above.
(ii)
A
∣
B is a parallel composition of two extended process.
(iii)
ν
n
·
A is a restriction of the name n to A.
(iv)
ν
x
·
A is a restriction of the variable x to A.
(v)
{
t
/
x
} means that the binding of t to x, denoted by {
t
/
x
}, is applied to any process that is in parallel composition with {
t
/
x
}. Intuitively, the binding applies to any process that comes into contact with it. To restrict the binding {
t
/
x
} to a process P, we use the variable restriction ν
x over (
{
t
/
x
}
∣
P
), namely, ν
x
·
(
{
t
/
x
}
∣
P
). Using this, the equivalent definition of process c
¯
〈
t
〉
·
P can be given by ν
x
·
(
c
¯
〈
x
〉
·
P
∣
{
t
/
x
}). Active substitutions are always assumed to be cycle-free.
We definef
v
(
A
), b
v
(
A
), f
n
(
A
), and b
n
(
A
) for the sets of free and bound variables and free and bound names of A, respectively. These sets are defined as follow:
(7)
f
v
(
{
t
x
}
)
=
d
e
f
f
v
(
t
)
∪
{
x
}
,
f
n
(
{
t
x
}
)
=
d
e
f
f
n
(
t
)
.
b
v
(
{
t
x
}
)
=
d
e
f
∅
,
b
n
(
{
t
x
}
)
=
d
e
f
b
n
(
t
)
.
The concept of bound and free values is similar to local and global scope in programming languages. The scope of names and variables is delimited by bindersc
(
x
) (i.e., input) and ν
n or ν
x (i.e., restriction). The set of bound names b
n
(
A
) contains every name n which is under the restriction ν
n inside A. The set of bound variables b
v
(
A
) consists of all those variables x occurring in A that are bound by restriction ν
x or input c
(
x
). Further, we define the set of free names and the set of free variables. The set of free names in A, denoted by f
n
(
A
), consists of those names n occurring in A that are not restricted names. The set of free variables f
v
(
A
) contains the variables x occurring in A which are not restricted variables (ν
x) or input variable (c
(
x
)). A plain process P is closed if it contains no free variable. An extended process is closed when every variable x is either bound or defined by an active substitution.As in the appliedπ-calculus, a frame (φ) is an extended process built up from the nil process and active substitutions of the form {
t
/
x
} by parallel composition and restrictions. Formally, the frame φ
(
A
) of the extended process, A
=
ν
n
1
⋯
n
k
(
{
t
1
/
x
1
}
|
⋯
|
{
t
n
/
x
n
}
∣
P
), is ν
n
1
…
n
k
(
{
t
1
/
x
1
}
|
⋯
|
{
t
n
/
x
n
}
). The domain of the frame φ
(
A
) (denoted by d
o
m
(
A
)) is the set {
x
1
,
…
,
x
n
}.Intuitively, the frameφ
(
A
) accounts for the static knowledge exposed by A to its environment but not for dynamic behavior. The frame allows access to terms that the environment cannot construct. For instance, after the term t (not available for the environment) is output in P resulting in P
′
∣
{
t
/
x
}, t becomes available for the environment. Finally, let σ range over substitutions (i.e., variable bindings). We write σ
t for the result of applying σ to the variables in t.


### 3.1.1. Labeled Transition System (→
α)

The operational semantics for processes is defined as a labeled transition system(
𝒫
,
𝒢
,
→
) where 𝒫 represents a set of extended processes, 𝒢 is a set of labels, and →
⊆
𝒫
×
𝒢
×
𝒫.Specifically, the labeled semantics defines a ternary relation, written asA
→
α
B, where α is a label of the form τ, c
(
t
), c
¯
〈
x
〉, ν
x
·
c
¯
〈
x
〉 where x is a variable of base type and t is a term. The transition A
→
τ
B represents a silent move that is used to model the internal operation/computation of processes. These internal operations, such as the verification steps made on the received data, are not visible for the outside world and, hence, to the attacker(s). The transition A
→
c
(
t
)
B means that the process A performs an input of the term t from the environment on the channel c and the resulting process is B. The label c
¯
〈
x
〉 is for output action of a free variable x. Finally, the label α is ν
x
·
c
¯
〈
x
〉 when a term is output on c. In the following, we give some examples for labeled transitions.Silent Transition (Internal Computations/Verification) Rules for Processes
(Let)
letx
=
t
in
P
→
τ
P
{
t
/
x
}; let e
=
t
in
P
→
τ
P
{
t
/
e
}.
(If1)
[
t
i
=
t
j
]
P
else
Q
→
τ
P
;
[
t
i
=
t
j
]
P
→
τ
P
(
if
t
i
=
t
j
).
(If2)
[
t
i
=
t
j
]
P
else
Q
→
τ
Q
;
[
t
i
=
t
j
]
P
→
τ  nil  (
if
t
i
≠
t
j
).
(If3)
[
i
n
t
i
>
i
n
t
j
]
P
else
Q
→
τ
P
;
[
i
n
t
i
>
i
n
t
j
]
P
→
τ
P
(
if
i
n
t
i
>
i
n
t
j
).
(If4)
[
i
n
t
i
>
i
n
t
j
]
P
else
Q
→
τ
Q
;
[
i
n
t
i
>
i
n
t
j
]
P
→
τ  nil  (
if
i
n
t
i
≤
i
n
t
j
).Action Transition (Message Input/Output) Rules for Processes
(In)c
(
x
)
·
P
→
c
(
t
)
P
{
t
/
x
};
(Open)if
A
→
c
¯
〈
u
〉
A
′
,
u
≠
c
then
ν
u
·
A
→
ν
u
.
c
¯
〈
u
〉
A
′.
Let binds a variable to a term in a process; rules If1–If4 check the relation of two terms or integers. Rule (In) says that, when a term t is received, it is bound to every occurrence of x in P. Rule (Open) defines the output of a restricted name. Note that these rules are examples from the full list of rules, which can be found in [11]. From rule (Open) and the fact that ν
x
·
(
c
¯
〈
x
〉
·
P
|
{
t
/
x
}
) is equivalent to c
¯
〈
t
〉
·
P, we have two additional output rules(Out-1)
c
¯
〈
t
〉
·
P
→
ν
x
·
c
¯
〈
x
〉
{
t
/
x
}
∣
P,
(Out-2)
ν
n
·
(
c
¯
〈
t
〉
·
P
)
→
ν
x
.
c
¯
〈
x
〉
ν
n
·
(
{
t
/
x
}
∣
P
).For instance, based on the labeled transition system, we have the following transitions:(8)
c
¯
〈
t
1
〉
·
c
¯
〈
t
2
〉
·
P
→
ν
x
1
·
c
¯
〈
x
1
〉
{
t
1
x
1
}
∣
c
¯
〈
t
2
〉
·
P
→
ν
x
2
·
c
¯
〈
x
2
〉
{
t
1
x
1
}
∣
{
t
2
x
2
}
∣
P
.After sending the termst
1 and t
2 on public channel c (modeled by action transitions →
ν
x
1
·
c
¯
〈
x
1
〉 and →
ν
x
2
·
c
¯
〈
x
2
〉, resp.), t
1 and t
2 become available for the environment (attacker), whose fact is specified by the active substitutions {
t
1
/
x
1
} and {
t
2
/
x
2
}.Similarly as in [5], we define an equational theory
E
q, that is, a set of equations of the form t
1
=
t
2. This allows us to define cryptographic primitives and operations, such as one-way hash function and MAC computation. For instance, the function Tuple models a tuple of n terms t
1
,
t
2
,
…
,
t
n, and its inverse function i returns the ith element of a tuple of n elements, where i
∈
{
1
,
…
,
n
}. We abbreviate the tuple as (
t
1
,
t
2
,
…
,
t
n
) in rest of the paper:
(9)
T
u
p
l
e
(
t
1
,
t
2
,
…
,
t
n
)
;
i
(
t
1
,
t
2
,
…
,
t
n
)
=
t
i
.We model the keyed hash or MAC function with symmetric keyK with the binary function MAC. The MAC verification is defined in the form of the following equation:
(10)
M
A
C
(
t
,
K
)
;
C
h
e
c
k
M
A
C
(
M
A
C
(
t
,
K
)
,
K
)
=
o
kFunctionM
A
C computes the message authentication code of message t using secret key K. The shared key between node l
i and node l
j is modelled by function K
(
l
i
,
l
j
). The MAC verification defined by the function C
h
e
c
k
M
A
C is successful (returns a special name o
k) if the keys match each other.We can also model many other cryptographic operations and primitives such as symmetric and asymmetric encryption, digital signature, and one-way hash function. However, in this paper we omit to detail them because we do not use these operations. An interested reader can find more details in our longer report [11].


## 3.1.1. Labeled Transition System (→
α)

The operational semantics for processes is defined as a labeled transition system(
𝒫
,
𝒢
,
→
) where 𝒫 represents a set of extended processes, 𝒢 is a set of labels, and →
⊆
𝒫
×
𝒢
×
𝒫.Specifically, the labeled semantics defines a ternary relation, written asA
→
α
B, where α is a label of the form τ, c
(
t
), c
¯
〈
x
〉, ν
x
·
c
¯
〈
x
〉 where x is a variable of base type and t is a term. The transition A
→
τ
B represents a silent move that is used to model the internal operation/computation of processes. These internal operations, such as the verification steps made on the received data, are not visible for the outside world and, hence, to the attacker(s). The transition A
→
c
(
t
)
B means that the process A performs an input of the term t from the environment on the channel c and the resulting process is B. The label c
¯
〈
x
〉 is for output action of a free variable x. Finally, the label α is ν
x
·
c
¯
〈
x
〉 when a term is output on c. In the following, we give some examples for labeled transitions.Silent Transition (Internal Computations/Verification) Rules for Processes
(Let)
letx
=
t
in
P
→
τ
P
{
t
/
x
}; let e
=
t
in
P
→
τ
P
{
t
/
e
}.
(If1)
[
t
i
=
t
j
]
P
else
Q
→
τ
P
;
[
t
i
=
t
j
]
P
→
τ
P
(
if
t
i
=
t
j
).
(If2)
[
t
i
=
t
j
]
P
else
Q
→
τ
Q
;
[
t
i
=
t
j
]
P
→
τ  nil  (
if
t
i
≠
t
j
).
(If3)
[
i
n
t
i
>
i
n
t
j
]
P
else
Q
→
τ
P
;
[
i
n
t
i
>
i
n
t
j
]
P
→
τ
P
(
if
i
n
t
i
>
i
n
t
j
).
(If4)
[
i
n
t
i
>
i
n
t
j
]
P
else
Q
→
τ
Q
;
[
i
n
t
i
>
i
n
t
j
]
P
→
τ  nil  (
if
i
n
t
i
≤
i
n
t
j
).Action Transition (Message Input/Output) Rules for Processes
(In)c
(
x
)
·
P
→
c
(
t
)
P
{
t
/
x
};
(Open)if
A
→
c
¯
〈
u
〉
A
′
,
u
≠
c
then
ν
u
·
A
→
ν
u
.
c
¯
〈
u
〉
A
′.
Let binds a variable to a term in a process; rules If1–If4 check the relation of two terms or integers. Rule (In) says that, when a term t is received, it is bound to every occurrence of x in P. Rule (Open) defines the output of a restricted name. Note that these rules are examples from the full list of rules, which can be found in [11]. From rule (Open) and the fact that ν
x
·
(
c
¯
〈
x
〉
·
P
|
{
t
/
x
}
) is equivalent to c
¯
〈
t
〉
·
P, we have two additional output rules(Out-1)
c
¯
〈
t
〉
·
P
→
ν
x
·
c
¯
〈
x
〉
{
t
/
x
}
∣
P,
(Out-2)
ν
n
·
(
c
¯
〈
t
〉
·
P
)
→
ν
x
.
c
¯
〈
x
〉
ν
n
·
(
{
t
/
x
}
∣
P
).For instance, based on the labeled transition system, we have the following transitions:(8)
c
¯
〈
t
1
〉
·
c
¯
〈
t
2
〉
·
P
→
ν
x
1
·
c
¯
〈
x
1
〉
{
t
1
x
1
}
∣
c
¯
〈
t
2
〉
·
P
→
ν
x
2
·
c
¯
〈
x
2
〉
{
t
1
x
1
}
∣
{
t
2
x
2
}
∣
P
.After sending the termst
1 and t
2 on public channel c (modeled by action transitions →
ν
x
1
·
c
¯
〈
x
1
〉 and →
ν
x
2
·
c
¯
〈
x
2
〉, resp.), t
1 and t
2 become available for the environment (attacker), whose fact is specified by the active substitutions {
t
1
/
x
1
} and {
t
2
/
x
2
}.Similarly as in [5], we define an equational theory
E
q, that is, a set of equations of the form t
1
=
t
2. This allows us to define cryptographic primitives and operations, such as one-way hash function and MAC computation. For instance, the function Tuple models a tuple of n terms t
1
,
t
2
,
…
,
t
n, and its inverse function i returns the ith element of a tuple of n elements, where i
∈
{
1
,
…
,
n
}. We abbreviate the tuple as (
t
1
,
t
2
,
…
,
t
n
) in rest of the paper:
(9)
T
u
p
l
e
(
t
1
,
t
2
,
…
,
t
n
)
;
i
(
t
1
,
t
2
,
…
,
t
n
)
=
t
i
.We model the keyed hash or MAC function with symmetric keyK with the binary function MAC. The MAC verification is defined in the form of the following equation:
(10)
M
A
C
(
t
,
K
)
;
C
h
e
c
k
M
A
C
(
M
A
C
(
t
,
K
)
,
K
)
=
o
kFunctionM
A
C computes the message authentication code of message t using secret key K. The shared key between node l
i and node l
j is modelled by function K
(
l
i
,
l
j
). The MAC verification defined by the function C
h
e
c
k
M
A
C is successful (returns a special name o
k) if the keys match each other.We can also model many other cryptographic operations and primitives such as symmetric and asymmetric encryption, digital signature, and one-way hash function. However, in this paper we omit to detail them because we do not use these operations. An interested reader can find more details in our longer report [11].


## 4.c
r
y
p
t
t
i
m
e
p
r
o
b: Extending c
r
y
p
t with Timed and Probabilistic Syntax and Semantics

We propose a time and probabilistic extension toc
r
y
p
t, denoted by c
r
y
p
t
t
i
m
e
p
r
o
b. Our calculus is tailored for the verification of security protocols, especially for verifying protocols that need to cache data, such as transport protocols for wireless sensor networks. This is a new probabilistic timed calculus for cryptographic protocols and, to the best of our knowledge, the first of its kind. The design methodology of c
r
y
p
t
t
i
m
e
p
r
o
b is based on the terminology proposed in previous works, it can be seen as the modification and extension of them and contains some novelties.Namely, the timed extension ofc
r
y
p
t is based on the timed calculus proposed in [7, 12], and it is also based on the syntax and semantics of the well-known timed automata. The probabilistic extension is inspired by the syntax and semantics of the probabilistic extension of the applied π-calculus proposed in [6] and the probabilistic automata in [7]. The main difference between our work and the related methods is that we focus on extending c
r
y
p
t, which is different from the calculus used in those works. In addition, we combine both timed and probabilistic elements at the same time. Finally, we also propose a new definition called weak probabilistic timed bisimilarity for proving the existence of the attacks against security protocols.The concept ofc
r
y
p
t
t
i
m
e
p
r
o
b is based on the concept of probabilistic timed automata; hence, the correctness of c
r
y
p
t
t
i
m
e
p
r
o
b comes from the correctness of the automata because the semantics of c
r
y
p
t
t
i
m
e
p
r
o
b is equivalent to the semantics of the probabilistic timed automata, and we show that each process in c
r
y
p
t
t
i
m
e
p
r
o
b has an associated probabilistic timed automaton.Basic Time Concepts. First of all, we provide some notations related to clocks and time constructs, borrowed from the concept of timed automata. Assume a set 𝒞 of nonnegative real valued variables called clocks. A clock valuation over 𝒞 is a mapping v
:
𝒞
↦
ℝ
≥
0 assigning nonnegative real values to clocks. For a time value d
∈
ℝ
≥
0 let v
+
d denote the clock valuation such that (
v
+
d
)
(
x
c
)
=
v
(
x
c
)
+
d, for each clock x
c
∈
𝒞.The setΦ
(
C
) of clock constraints is generated by the following grammar:
(11)
ϕ
:
:
=
t
r
u
e
∣
f
a
l
s
e
∣
x
c
~
N
∣
ϕ
1
∧
ϕ
2
∣
¬
ϕ
,
where ϕ ranges over Φ
(
C
), x
c
∈
𝒞, N is a real number, and ~
∈
{
<
,
≤
,
≥
,
>
}. We write v
⊨
ϕ when the valuation v satisfies the constraint ϕ. Formally, v
⊨
t
r
u
e; v
⊨
x
c
~
N if and only if v
(
x
c
)
~
N; v
⊨
ϕ
1
∧
ϕ
2 if and only if v
⊨
ϕ
1
∧
v
⊨
ϕ
2.


### 4.1. Syntax

In the following, we turn to define probabilistic timed processes forc
r
y
p
t
t
i
m
e
p
r
o
b:
(12)
A
p
t
:
:
=
A
∣
α
*
≺
π
A
p
t
∣
ϕ
↪
A
p
t
∣
∥
C
R
∥
A
p
t
∣
A
p
t
1
[
]
A
p
t
2
∣
A
p
t
1
⊕
p
A
p
t
2
∣
(
A
p
t
1
∣
A
p
t
2
)
∣
X
p
t
.We will discuss the meaning ofc
r
y
p
t
t
i
m
e
p
r
o
b processes by showing the connection between the modeling elements of a probabilistic timed automata and c
r
y
p
t
t
i
m
e
p
r
o
b. For this purpose, we recall the definition of probabilistic timed automaton [12]: a probabilistic timed automaton Aut is defined by the tuple (ℒ, l
0, ∑
‍, 𝒞, ℐ
n
v, κ, E, Π), where(i)
ℒ is a finite set of locations and l
0 is the initial location;
(ii)
∑
‍ is a set of actions that range over act;
(iii)
𝒞 is a finite set of clocks;
(iv)
ℐ
n
v: ℒ
↦
Φ
(
𝒞
) is a function that assigns location to a formula, called a location invariant, that must hold at a given location;
(v)
κ: ℒ
↦
2
𝒞 is the set of clock resets to be performed at the given locations;
(iv)
E
⊆
ℒ
×
∑
×
Φ
(
𝒞
)
×
ℬ
×
ℒ is the set of edges; we write l
→
a
c
t
,
ϕ
l
′ when (l, act, ϕ, B, l
′) ∈
E, where act, ϕ are the action and the time constraint defined on the edge and B is the set of the clocks to be reset at l
′;
(iiv)
Π
=
{
π
1
,
…
,
π
n
} is a finite set of probability distributions; each π
i is a function π
i
:
E
↦
[
0,1
] for any i
=
{
1
,
…
,
n
}, where π
i(g) is the probability of an edge g according to distribution π
i and the sum of the edges from a given location l is 1.Let us denote the set of processes inc
r
y
p
t
t
i
m
e
p
r
o
b by A
t
i
m
e
p
r
o
b, and we let A
p
t
l range over processes in A
t
i
m
e
p
r
o
b. In c
r
y
p
t
t
i
m
e
p
r
o
b, each probabilistic timed process A
p
t
l corresponds to a location l in an automaton, such that there is an initial process A
p
t
l
0 for location l
0. The set of actions ∑
‍ corresponds to the set of actions known in c
r
y
p
t. The set of clocks to be reset at a given location l, κ
(
l
), is defined by the corresponding c
r
y
p
t
t
i
m
e
p
r
o
b process ∥
C
R
∥
A
p
t
l. The clock invariant at the location l corresponds to the process ϕ
⊳
A
p
t
l, and the edge guard can be defined by ϕ
↪
A
p
t
l. More specifically,(i)
A
p
t can be an extended process A without any time construct;
(ii)
α
*
≺
π
A
p
t performs α
* as the first (not timed) action with the distribution π, at any time, and then it behaves like A
p
t; note that α
* can be ν
x
.
c
¯
〈
x
〉, c
¯
〈
u
〉, c
(
t
), and the silent action τ; for instance, if A
p
t is c
(
t
)
.
P, where P is the plain process in c
r
y
p
t, then α
* is c
(
t
); this process corresponds to the automaton edge l
→
α
*
,
t
r
u
e
π
l
′, where α
*
≺
π
A
p
t and A
p
t corresponds to locations l and l
′, respectively;
(iii)
ϕ
↪
A
p
t represents a time guard of an action and says that the first action α
* of A
p
t is performed if the guard (time constraint) ϕ holds; this process intends to model the edge l
⟶
π
α
*
,
ϕ
l
′ in the automaton syntax, where A
p
t corresponds to l, while the explicit appearance of the target location l
′ is omitted in the process; in the transition, the action α
* is performed according to the distribution π; when an action has a time guard true it means that the action can be performed at any time;
(iv)
ϕ
⊳
A
p
t represents a clock invariant over A
p
t; this process corresponds to the location invariant in an automaton; like in timed automaton, this means that the system cannot “stay” in process A
p
t once the time constraint ϕ becomes invalid; if it cannot move from this process via any transition, then it is a deadlock situation; invariants can be used to model timeout;
(v)
in the timed process∥
C
R
∥
A
p
t, first, the clocks in the set C
R are reset and then it behaves like A
p
t with the reset clock values;
(vi)
A
p
t
1
[
]
A
p
t
2 and A
p
t
1
∣
A
p
t
2 describe the first-action choice and the parallel composition of two processes, respectively; process A
p
t
1
⊕
p
A
p
t
2 behaves like A
p
t
1 with probability p, and it behaves as A
p
t
2 with (1
-
p); A
p
t
1
[
]
A
p
t
2 corresponds to a location l from which two edges start, and they are chosen based on the first enable action of A
p
t
1 and A
p
t
2; for parallel composition, we define A
p
t
1
∣
A
p
t
2 as a location, instead of the parallel composition of two automata; process A
p
t
1
⊕
p
A
p
t
2 corresponds to a location l from which two edges start: l
⟶
p
α
*
,
ϕ
l
1 and l
→
α
*
,
ϕ
1
-
p
l
2, where l
1 and l
2 correspond to A
p
t
1 and A
p
t
2, respectively;
(vii)
X
p
t is a process variable to which one of the timed processes ϕ
↪
A
p
t, ϕ
⊳
A
p
t, and ∥
C
R
∥
A
p
t can be bound; Note that this differs from [10], as for our problem, we restrict process variables (X
p
t) to be only those processes that have time constructs defined on it; the reason we do this is that we want to avoid the recursive process invocation for extended processes, which may lead to an infinite invocation cycle (e.g., A
=
{
t
/
x
}
|
A, where the process variable is bound to A); hence it is not well-defined.Definition 1.
We extend the definition of free and bound variables in Section3 with the set of clock variables. The set of free variables and bound variables of A
p
t, denoted by f
v
c
(
A
p
t
) and b
v
c
(
A
p
t
), respectively, are as follows. (i)
f
v
c
(
ϕ
↪
A
p
t
)
=
clock
(
ϕ
)
∪
f
v
c
(
A
p
t
): edge guards contains free clock variables.
(ii)
f
v
c
(
ϕ
⊳
A
p
t
)
=
clock
(
ϕ
)
∪
f
v
c
(
A
p
t
): invariant contains free clock variables.
(iii)
b
v
c
(
∥
C
R
∥
A
p
t
)
=
b
v
c
(
A
p
t
)
∪
C
R: clocks to be reset are bound clock variables.
(iv)
f
v
c
(
A
p
t
1
[
]
A
p
t
2
)
=
f
v
c
(
A
p
t
1
)
∪
f
v
c
(
A
p
t
2
); b
v
c
(
A
p
t
1
[
]
A
p
t
2
)
=
b
v
c
(
A
p
t
1
)
∪
b
v
c
(
A
p
t
2
).
(v)
f
v
c
(
A
p
t
1
∣
A
p
t
2
)
=
f
v
c
(
A
p
t
1
)
∪
f
v
c
(
A
p
t
2
); b
v
c
(
A
p
t
1
∣
A
p
t
2
)
=
b
v
c
(
A
p
t
1
)
∪
b
v
c
(
A
p
t
2
).
(iv)
f
v
c
(
A
p
t
1
⊕
p
A
p
t
2
)
=
f
v
c
(
A
p
t
1
)
∪
f
v
c
(
A
p
t
2
); b
v
c
(
A
p
t
1
⊕
p
A
p
t
2
)
=
b
v
c
(
A
p
t
1
)
∪
b
v
c
(
A
p
t
2
).The free and bound clock variables of choices and parallel composition are the union of the free and bound clock variables of each process. The reason that the set of clock variables is divided into bound and free parts is to avoid conflicts of clock valuations. For instance, let us consider the process x
c
≤
8
⊳
(
∥
x
c
∥
A
p
t
), in which the clock x
c is reset, and this affects the invariant x
c
≤
8. Further, in the parallel composition (
∥
x
c
∥
A
p
t
)
|
(
x
c
≤
8
⊳
A
p
t
′
) the clock variable x
c is the shared variable of the two processes; however, the reset of x
c affects the behavior of process (
x
c
≤
8
)
⊳
A
p
t
′. This is undesirable since the operational semantics of a process also depends on the behavior of the environment (which is hard to control).Hence, we define the notion of processes that do not contain any conflict of clock variables, using the following inductive definition and the predicaten
c
v (which refers to "non-conflict of clock variables"):(1)
n
c
v
(
A
);
(2)
n
c
v
(
X
p
t
);
(3)
n
c
v
(
α
*
≺
π
A
p
t
) if and only if n
c
v
(
A
p
t
);
(4)
n
c
v
(
∥
C
R
∥
A
p
t
) if and only if n
c
v
(
A
p
t
);
(5)
n
c
v
(
ϕ
↪
A
p
t
);
(6)
n
c
v
(
ϕ
⊳
A
p
t
)
: in both cases, if and only if n
c
v
(
A
p
t
)
∧
(
c
l
o
c
k
(
ϕ
)
∩
κ
(
A
p
t
)
=
∅
).Rule 1 holds because an extended processA does not include any clock variables. Rule 2 says that the recursive process invocation of plain processes is nonconflict because a plain process does not contain clock variables. Rule 3 comes from the fact that action α
* is free from clock variables. Rule 4 says that the outermost clock resettings do not cause the conflict of variables in process Apt. Rules 5 and 6 say that if guard and invariant constructs are placed outside then their clock variables cannot be reset within A
p
t, to avoid conflict. For the full list of n
c
v rules please check our report [11].In the following, for eachc
r
y
p
t
t
i
m
e
p
r
o
b process we add rules that associate each process with the invariant and resetting functions ∂ and κ, respectively. Note that we only give the two most important rules in this paper; the full list can be found in [11]. Consider the following:(rk) κ
(
∥
C
R
∥
A
p
t
)
=
C
R
∪
κ
(
A
p
t
);
(ri) ∂
(
ϕ
⊳
A
p
t
)
=
∂
(
A
p
t
)
∧
ϕ.Rulerk says that the set of clocks to be reset in κ
(
∥
C
R
∥
A
p
t
) is C
R and the clock resets occur in A
p
t, and rule ri says that the invariant of process ϕ
⊳
A
p
t is the intersection of ϕ and the invariant predicate in A
p
t.


### 4.2. Operational Semantics

The formal semantics ofc
r
y
p
t
t
i
m
e
p
r
o
b follows the semantics of probabilistic timed automata. Namely, a state s is defined by the pair (A
p
t, v), where v is the clock valuation at the location with label A
p
t with the time issues defined at the location. The initial state s
0 consists of the initial process and initial clock valuation (A
p
t
0, v
0). Note that the initial process A
p
t
0 is the initial status of a system behavior, while v
0 typically contains the clocks in the reset state. The operational semantics of c
r
y
p
t
t
i
m
e
p
r
o
b is defined by a probabilistic timed transition system (PTTS).A probabilistic timed transition system can be seen as the labeled transition system extended with time and probabilistic constructs. In our model, we follow the concept of [7, 12], but we also improve them with language elements and a new definition of bisimilarity for proving/refuting the security properties of protocols.Definition 2.
Let∑
‍ be the set of actions. A probabilistic timed transition system is defined as the tuple P
T
T
S
=
(
𝒮
,
∑
‍
×
ℝ
≥
0
×
Π
,
s
0
,
→
P
T
T
S
,
𝒰
,
F
), where (i)
𝒮 is a set of states, and s
0 is an initial state;
(ii)
→
P
T
T
S
⊆
𝒮
×
(
∑
‍
×
ℝ
≥
0
)
×
Π
×
𝒮 is the set of probabilistic timed labeled transitions; a transition is defined between the source and target state, and the label of the transition is composed of the actions, the time stamp (duration), and the probability of the action; when (
α
*
,
d
,
π
)
∈
∑
×
ℝ
≥
0
×
Π we denote the transition from s to s
′ by s
→
α
*
(
d
)
,
π
P
T
T
S
s
′; the appearance of π on the arrow means that the transition is performed with the probability according to the distribution π; the label α
*
(
d
) says that performing either a visible α or invisible (silent) τ action (α
*
=
α
∪
τ) consumes d time units; we interpret d as the time for executing action α
*, and there is no idling time at s before performing an action;
(iii)
𝒰
⊆
ℝ
≥
0
×
𝒮 is the until predicate and is defined at a state s with a time duration d; whenever (
d, s
)
∈
𝒰 we use the notation 𝒰
d;
(iv)
the schedulerF chooses nondeterministically the distribution of action transition steps.The probabilistic timed transition systemP
T
T
S should satisfy the two axioms, Until and Delay (in both cases ⇒ denotes logical implication):(
U
n
t
i
l
) for all d
,
d
′
∈
ℝ
≥
0, 𝒰
d
(
s
)
∧
(
d
′
<
d
)
⇒
𝒰
d
′
(
s
),
(
D
e
l
a
y
) for all d
∈
ℝ
≥
0, s
→
α
*
(
d
)
,
π
P
T
T
S
s
′
for
some
s
′
⇒
𝒰
d
(
s
).These two axioms define formally the meaning of the notions delay and until. Basically, axiomUntil says that if the system stays in state s until d time units then it also stays in this state before d. While the axiom Delay says that if the system performs an action α at time d then it must wait until d. Note that the meaning of until differs from time invariant, because, in case of until, the system waits (stays idled) at least d time units in a given state, whilst time invariant says that the system must leave a given state when d time units have elapsed (if it cannot move from the state then we get deadlock).In addition,𝒰 are the smallest set satisfying the following rules:(u1)
𝒰
d
(
A
,
v
);
(u2)
𝒰
d
(
α
*
≺
π
A
p
t
,
v
);
(u3)
𝒰
d
(
ϕ
↪
A
p
t
,
v
) if 𝒰
d
(
A
p
t
,
v
);
(u4)
𝒰
d
(
∥
C
R
∥
A
p
t
,
v
) if 𝒰
d
(
A
p
t
,
v
[
r
s
t
:
C
R
]
);
(u5)
𝒰
d
(
ϕ
⊳
A
p
t
,
v
) if 𝒰
d
(
A
p
t
,
v
)
∧
⊨
(
v
+
d
)
(
ϕ
);
(u6)
𝒰
d
(
A
p
t
1
[
]
A
p
t
2
,
v
) if 𝒰
d
(
A
p
t
1
,
v
)
∨
𝒰
d
(
A
p
t
2
,
v
);
(u7)
𝒰
d
(
A
p
t
1
∣
A
p
t
2
,
v
) if 𝒰
d
(
A
p
t
1
,
v
)
∨
𝒰
d
(
A
p
t
2
,
v
);
(u8)
𝒰
d
(
A
p
t
1
⊕
p
A
p
t
2
,
v
) if 𝒰
d
(
A
p
t
1
,
v
)
∨
𝒰
d
(
A
p
t
2
,
v
);
(u9)
𝒰
d
(
X
p
t
,
v
) if 𝒰
d
(
P
[
P
/
X
p
t
]
,
v
).Rules (u1-u2) are the Until axioms for the states (A, v) and (α
*
≺
π
A
p
t, v). In u3 the system stays in the state (ϕ
↪
A
p
t, v) until d time units if this is valid to the state (A
p
t, v) as well. Rules (u4-u5) come from the definition of the clock reset and invariant. In rule (u4) v
[
r
s
t
:
C
R
] represents the clock valuation v where the clocks in C
R are reset. Rules (u6–u8) say that the system stays until d time units at the state with A
p
t
1
[
]
A
p
t
2, A
p
t
1
|
A
p
t
2, and A
p
t
1
⊕
p
A
p
t
2 if it stays d time in the state with one of the two processes A
p
t
1 and A
p
t
2. Rule u9 is concerned with the until predicate for (recursive) process variable X
p
t, which comes directly from the definition of recursive process invocation. Note that P is a plain process defined in c
r
y
p
t.We define the satisfaction predicate⊨, ⊨
⊆
Φ
(
𝒞
), on clock constraints. For each ϕ
∈
Φ
(
𝒞
) we use the shorthand ⊨
v
(
ϕ
) if and only if v satisfies ϕ, for all valuation v. The set of past closed constraint, Φ
(
𝒞
)
¯
⊆
Φ
(
𝒞
), is used for defining semantics of location invariant, for all v
∈
𝒱, d
∈
ℝ
≥
0: ⊨
(
v
+
d
)
(
ϕ
)
⇒
⊨
(
v
)
(
ϕ
). Intuitively, this says that if the valuation v
+
d, which is defined as v
(
x
c
)
+
d for all clocks x
c, satisfies the constraint ϕ then so does v. We adopt the variant of time automata used in [7], where location invariant and clock resets are defined as functions ∂ and κ assigning a set of clock constraints Φ
(
𝒞
)
¯ and a set of clocks to be reset ℛ
(
𝒞
), respectively, to a c
r
y
p
t
t
i
m
e
p
r
o
b process.The probabilistic timed transition (action) rules forc
r
y
p
t
t
i
m
e
p
r
o
b are given as follows. We provide the connection of each PTTS transition with the edge syntax well-known in probabilistic timed automata. Consider the following:(a1)
(
α
*
≺
π
A
p
t
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
A
p
t
,
v
+
d
) if α
*
≺
π
A
p
t
→
α
*
,
t
r
u
e
π
A
p
t;
(a2)
(
∥
C
R
∥
A
p
t
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
A
p
t
′
,
v
′
) if (
A
p
t
,
v
[
r
s
t
:
C
R
]
)
→
α
*
(
d
)
,
t
r
u
e
π
(
A
p
t
′
,
v
′
);
(a3)
(
ϕ
↪
A
p
t
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
A
p
t
′
,
v
′
) if (
A
p
t
,
v
)
→
α
*
(
d
)
,
ϕ
π
(
A
p
t
′
,
v
′
)
∧
(
v
+
d
)
(
ϕ
);
(a4)
(
ϕ
⊳
A
p
t
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
A
p
t
′
,
v
′
) if (
A
p
t
,
v
)
→
α
*
(
d
)
,
t
r
u
e
π
(
A
p
t
′
,
v
′
)
∧
(
v
+
d
)
(
ϕ
);
(a5)
(
A
p
t
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
ϕ
⊳
A
p
t
′
,
v
′
) if (
A
p
t
,
v
)
→
α
*
(
d
)
,
t
r
u
e
π
(
A
p
t
′
,
v
′
)
∧
(
v
+
d
)
(
ϕ
);
(a6)
(
A
p
t
1
[
]
A
p
t
2
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
A
p
t
1
′
,
v
′
) if (
A
p
t
1
,
v
)
→
α
*
(
d
)
,
t
r
u
e
π
(
A
p
t
1
′
,
v
′
);
(a
7
/
a)
(
A
p
t
1
⊕
p
A
p
t
2
,
v
)
→
α
*
(
d
)
,
π
(
p
)
P
T
T
S
(
A
p
t
1
′
,
v
′
) if A
p
t
1
⊕
p
A
p
t
2
→
α
*
,
t
r
u
e
π
(
p
)
A
p
t
1
′;
(a
7
/
b)
(
A
p
t
1
⊕
p
A
p
t
2
,
v
)
→
α
*
(
d
)
,
π
(
1
-
p
)
P
T
T
S
(
A
p
t
2
′
,
v
′
) if A
p
t
1
⊕
p
A
p
t
2
→
α
*
(
d
)
,
t
r
u
e
π
(
1
-
p
)
A
p
t
2
′;
(a8)
(
A
p
t
1
∣
A
p
t
2
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
A
p
t
1
′
∣
n
o
r
s
t
(
A
p
t
2
)
,
v
′
) if (
A
p
t
1
,
v
)
→
α
*
(
d
)
,
t
r
u
e
π
(
A
p
t
1
′
,
v
′
);
(a9)
(
X
p
t
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
P
′
,
v
′
) if (
P
[
P
/
X
p
t
]
,
v
)
→
α
*
(
d
)
,
t
r
u
e
π
(
P
′
,
v
′
).In rulea2  v
′
=
v
[
r
s
t
:
C
R
]
+
d and in the rest of the rules v
′
=
v
+
d. v
[
r
s
t
:
C
R
] represents the valuation v where the clocks in C
R are reset. Each rule should be interpreted that the PTTS transition on the left side can be performed if there is an edge in a corresponding automaton. For instance, rule a1 applies if there is an edge α
*
≺
π
A
p
t
→
α
*
,
t
r
u
e
π
A
p
t in the corresponding automaton. Rule a1 says that after performing action α
* with d time units the system gets to the process A
p
t with the clock valuation after d time units elapsed. Rule a2 says that, by the time ∥
C
R
∥
A
p
t proceeds to A
p
t, the clocks in C
R will have been reset. In the rules a3 and a4 the timed transition can be performed if (
v
+
d
)
(
ϕ
) holds, which means that the valuation v
+
d must satisfy the clock guard ϕ. Rules a5-a6 describe the case when process A
p
t
1 is activated (the rules for activating A
p
t
2 are similar). π
(
p
) and π
(
1
-
p
) in rules a7/a-b mean that in distribution π the first and second transitions (edges) are chosen with probabilities p and (1
-
p). In a8, to avoid conflict of clock variables, we require that after performing the transition process A
p
t
2 cannot perform resetting at the beginning. The last rule is the action rule for recursive process variable X
p
t. It can be proven, based on the rules u1–u9 and a1–a9, that probabilistic timed transition system of c
r
y
p
t
t
i
m
e
p
r
o
b satisfies axioms Until and Delay; hence, it is well defined.Theorem 3.
For allc
r
y
p
t
t
i
m
e
p
r
o
b process A
p
t and for all closed valuation v
0, PTTS(A
p
t, v
0, F) is indeed the probabilistic timed transition system defined in probabilistic timed automata.We defined rules for renaming the clock variables and we showed that thencv property is preserved by clock renaming; hence, the restriction we made to process without conflict of clock variables is harmless [7]. Based on the rules of renaming we also added new rules for structural equivalent resulted from renaming. We omit the discussion of these rules in detail because we do not use them, but the reader can find it in our longer report [11].Weak Probabilistic Timed (Prob-Timed) Labeled Bisimulation. We provide a novel bisimilarity definition, called weak prob-timed labeled bisimulation for c
r
y
p
t
t
i
m
e
p
r
o
b, which enables us to prove or refute the security of probabilistic timed systems.Our proposed definition makes use of the definition of static equivalence proposed in the appliedπ-calculus [5], which says that the outputs of static equivalent processes cannot be distinguished by the environment (or attackers). The main advantage of static equivalence is that it only takes into account the static knowledge exposed by two processes to show the behavioral equivalence of them. This method is much easier to use than using the well-known observation equivalence [5], where we have to consider the dynamic behavior of processes.Let the extended processA be {
t
1
/
x
1
}
|
⋯
|
{
t
n
/
x
n
}
∣
P
1
∣
⋯
∣
P
n. The frame
φ of A is the parallel composition {
t
1
/
x
1
}
∣
⋯
∣
{
t
n
/
x
n
} that models all the information that is output so far by the process A, which are t
1
,
…
,
t
n in this case.Definition 4 (static equivalence for extended processes
(
≈
s
)).
Two extended processesA
1 and A
2 are statically equivalent, denoted as A
1
≈
s
A
2, if their frames are statically equivalent. Two frames φ
1 and φ
2 are statically equivalent if they include the same number of active substitutions and the same domain, and any two terms that are equal in φ
1 are equal in φ
2 as well. Intuitively, this means that the outputs of the two processes cannot be distinguished by the environment.In our proposedweak prob-timed labeled bisimulation, we extend the static equivalence with time and probabilistic elements. The meaning of weak is that in this paper we want to examine whether the attackers can distinguish the behavior of two processes, based on the information they can observe. Hence, in weak prob-timed labeled bisimulation, we do not require the equivalence of the probability of two action traces, because practically an observer cannot distinguish if an action is performed with 1/2 or 1/3 probability.Nevertheless, we also proposed the definition ofstrong prob-timed labeled bisimulation in our longer report [11], which we do not discuss in this paper, because we found that, for analysing the security of DTSN and SDTP, it is sufficient to use the weak prob-timed labeled bisimulation. Strong prob-timed labeled bisimulation is stricter, since it also distinguishes two processes based on the probability of their corresponding action traces.Definition 5 (weak prob-timed labeled bisimulation for
c
r
y
p
t
t
i
m
e
p
r
o
b
processes).
LetP
T
T
S
i
(
A
p
t
i
,
v
0
,
F
)
=
(
𝒮
i
,
α
×
ℝ
≥
0
×
Π
,
s
0
i
,
→
P
T
T
S
i
,
𝒰
i
,
F
), and let i
∈
{
1,2
} be two probabilistic timed transition systems for c
r
y
p
t
t
i
m
e
p
r
o
b processes. Weak prob-timed labeled bisimilarity (≈
pt) is the largest symmetric relation ℛ, ℛ
⊆
𝒮
1
×
𝒮
2 with s
0
1
ℛ
s
0
2, where each s
i is the pair of a closed c
r
y
p
t
t
i
m
e
p
r
o
b process and the same initial valuation v
0
∈
𝒱
c, (
A
p
t
i
,
v
0
), such that s
1
ℛ
s
2 implies that (1)
A
1
≈
s
A
2;
(2)
ifs
1
→
τ
(
d
)
,
π
P
T
T
S
1
s
1
′ for a scheduler F, then ∃
s
2
′ such that s
2
⟹
τ
(
∑
‍
d
i
)
,
π
i
P
T
T
S
2
s
2
′ for the same F, with d
=
f
(
∑
d
i
) for some function f, and s
1
′
ℛ
s
2
′;
(3)
ifs
1
→
α
(
d
)
,
π
P
T
T
S
1
s
1
′ for a scheduler F and f
v
(
α
)
⊆
d
o
m
(
A
1
)
∧
b
n
(
α
)
∩
f
n
(
A
2
)
=
∅, then ∃
s
2
′ such that s
2
⟹
α
(
∑
‍
d
j
)
,
π
i
P
T
T
S
2
s
2
′ for the same F, with d
=
f
(
∑
‍
d
j
) for some function f, and s
1
′
ℛ
s
2
′; again, d
o
m
(
A
i
) represents the domain of A
i.
A
1 and A
2 are the extended processes we get by removing all the probabilistic and timed elements from A
p
t
1 and A
p
t
2, respectively.The arrow⇒
α
P
T
T
S is the shorthand of the action trace →
τ
P
T
T
S
*
→
α
P
T
T
S
→
τ
P
T
T
S
*, where →
τ
P
T
T
S
* represents a series (formally, a transitive closure) of sequential transitions →
τ
P
T
T
S. ∑
‍
d
i on ⇒
P
T
T
S is the sum of the time elapsed at each transition and represents the total time elapsed during the sequence of transitions. Note that f
n
(
A
p
t
2
) and d
o
m
(
A
p
t
1
) are the same as f
n
(
A
2
) and d
o
m
(
A
1
), respectively. Moreover, a process A
p
t is closed if its nontimed and “nonprobabilistic” counterpart A is closed.Intuitively, in case thatA
p
t
1 and A
p
t
2 represent two protocols (or two variants of a protocol), then this means that (i) the outputs of the two processes cannot be distinguished by the environment based on their behaviors; (ii) the time that the protocols spend on the performed operations until they reach the corresponding points is in some relationship defined by a function f. Here f depends on the specific definition of the security property; for instance, it can return d itself; hence, the requirement for time consumption would be d
=
∑
d
i. In particular, the first point means that A
p
t
1 and A
p
t
2 are statically equivalent; that is, the environment cannot distinguish the behavior of the two protocols based on their outputs; the second point says that A
p
t
1 and A
p
t
2 remain statically equivalent after silent transition (internal computation) steps. Finally, the third point says that the behavior of the two protocols matches in transition with the action α.


## 4.1. Syntax

In the following, we turn to define probabilistic timed processes forc
r
y
p
t
t
i
m
e
p
r
o
b:
(12)
A
p
t
:
:
=
A
∣
α
*
≺
π
A
p
t
∣
ϕ
↪
A
p
t
∣
∥
C
R
∥
A
p
t
∣
A
p
t
1
[
]
A
p
t
2
∣
A
p
t
1
⊕
p
A
p
t
2
∣
(
A
p
t
1
∣
A
p
t
2
)
∣
X
p
t
.We will discuss the meaning ofc
r
y
p
t
t
i
m
e
p
r
o
b processes by showing the connection between the modeling elements of a probabilistic timed automata and c
r
y
p
t
t
i
m
e
p
r
o
b. For this purpose, we recall the definition of probabilistic timed automaton [12]: a probabilistic timed automaton Aut is defined by the tuple (ℒ, l
0, ∑
‍, 𝒞, ℐ
n
v, κ, E, Π), where(i)
ℒ is a finite set of locations and l
0 is the initial location;
(ii)
∑
‍ is a set of actions that range over act;
(iii)
𝒞 is a finite set of clocks;
(iv)
ℐ
n
v: ℒ
↦
Φ
(
𝒞
) is a function that assigns location to a formula, called a location invariant, that must hold at a given location;
(v)
κ: ℒ
↦
2
𝒞 is the set of clock resets to be performed at the given locations;
(iv)
E
⊆
ℒ
×
∑
×
Φ
(
𝒞
)
×
ℬ
×
ℒ is the set of edges; we write l
→
a
c
t
,
ϕ
l
′ when (l, act, ϕ, B, l
′) ∈
E, where act, ϕ are the action and the time constraint defined on the edge and B is the set of the clocks to be reset at l
′;
(iiv)
Π
=
{
π
1
,
…
,
π
n
} is a finite set of probability distributions; each π
i is a function π
i
:
E
↦
[
0,1
] for any i
=
{
1
,
…
,
n
}, where π
i(g) is the probability of an edge g according to distribution π
i and the sum of the edges from a given location l is 1.Let us denote the set of processes inc
r
y
p
t
t
i
m
e
p
r
o
b by A
t
i
m
e
p
r
o
b, and we let A
p
t
l range over processes in A
t
i
m
e
p
r
o
b. In c
r
y
p
t
t
i
m
e
p
r
o
b, each probabilistic timed process A
p
t
l corresponds to a location l in an automaton, such that there is an initial process A
p
t
l
0 for location l
0. The set of actions ∑
‍ corresponds to the set of actions known in c
r
y
p
t. The set of clocks to be reset at a given location l, κ
(
l
), is defined by the corresponding c
r
y
p
t
t
i
m
e
p
r
o
b process ∥
C
R
∥
A
p
t
l. The clock invariant at the location l corresponds to the process ϕ
⊳
A
p
t
l, and the edge guard can be defined by ϕ
↪
A
p
t
l. More specifically,(i)
A
p
t can be an extended process A without any time construct;
(ii)
α
*
≺
π
A
p
t performs α
* as the first (not timed) action with the distribution π, at any time, and then it behaves like A
p
t; note that α
* can be ν
x
.
c
¯
〈
x
〉, c
¯
〈
u
〉, c
(
t
), and the silent action τ; for instance, if A
p
t is c
(
t
)
.
P, where P is the plain process in c
r
y
p
t, then α
* is c
(
t
); this process corresponds to the automaton edge l
→
α
*
,
t
r
u
e
π
l
′, where α
*
≺
π
A
p
t and A
p
t corresponds to locations l and l
′, respectively;
(iii)
ϕ
↪
A
p
t represents a time guard of an action and says that the first action α
* of A
p
t is performed if the guard (time constraint) ϕ holds; this process intends to model the edge l
⟶
π
α
*
,
ϕ
l
′ in the automaton syntax, where A
p
t corresponds to l, while the explicit appearance of the target location l
′ is omitted in the process; in the transition, the action α
* is performed according to the distribution π; when an action has a time guard true it means that the action can be performed at any time;
(iv)
ϕ
⊳
A
p
t represents a clock invariant over A
p
t; this process corresponds to the location invariant in an automaton; like in timed automaton, this means that the system cannot “stay” in process A
p
t once the time constraint ϕ becomes invalid; if it cannot move from this process via any transition, then it is a deadlock situation; invariants can be used to model timeout;
(v)
in the timed process∥
C
R
∥
A
p
t, first, the clocks in the set C
R are reset and then it behaves like A
p
t with the reset clock values;
(vi)
A
p
t
1
[
]
A
p
t
2 and A
p
t
1
∣
A
p
t
2 describe the first-action choice and the parallel composition of two processes, respectively; process A
p
t
1
⊕
p
A
p
t
2 behaves like A
p
t
1 with probability p, and it behaves as A
p
t
2 with (1
-
p); A
p
t
1
[
]
A
p
t
2 corresponds to a location l from which two edges start, and they are chosen based on the first enable action of A
p
t
1 and A
p
t
2; for parallel composition, we define A
p
t
1
∣
A
p
t
2 as a location, instead of the parallel composition of two automata; process A
p
t
1
⊕
p
A
p
t
2 corresponds to a location l from which two edges start: l
⟶
p
α
*
,
ϕ
l
1 and l
→
α
*
,
ϕ
1
-
p
l
2, where l
1 and l
2 correspond to A
p
t
1 and A
p
t
2, respectively;
(vii)
X
p
t is a process variable to which one of the timed processes ϕ
↪
A
p
t, ϕ
⊳
A
p
t, and ∥
C
R
∥
A
p
t can be bound; Note that this differs from [10], as for our problem, we restrict process variables (X
p
t) to be only those processes that have time constructs defined on it; the reason we do this is that we want to avoid the recursive process invocation for extended processes, which may lead to an infinite invocation cycle (e.g., A
=
{
t
/
x
}
|
A, where the process variable is bound to A); hence it is not well-defined.Definition 1.
We extend the definition of free and bound variables in Section3 with the set of clock variables. The set of free variables and bound variables of A
p
t, denoted by f
v
c
(
A
p
t
) and b
v
c
(
A
p
t
), respectively, are as follows. (i)
f
v
c
(
ϕ
↪
A
p
t
)
=
clock
(
ϕ
)
∪
f
v
c
(
A
p
t
): edge guards contains free clock variables.
(ii)
f
v
c
(
ϕ
⊳
A
p
t
)
=
clock
(
ϕ
)
∪
f
v
c
(
A
p
t
): invariant contains free clock variables.
(iii)
b
v
c
(
∥
C
R
∥
A
p
t
)
=
b
v
c
(
A
p
t
)
∪
C
R: clocks to be reset are bound clock variables.
(iv)
f
v
c
(
A
p
t
1
[
]
A
p
t
2
)
=
f
v
c
(
A
p
t
1
)
∪
f
v
c
(
A
p
t
2
); b
v
c
(
A
p
t
1
[
]
A
p
t
2
)
=
b
v
c
(
A
p
t
1
)
∪
b
v
c
(
A
p
t
2
).
(v)
f
v
c
(
A
p
t
1
∣
A
p
t
2
)
=
f
v
c
(
A
p
t
1
)
∪
f
v
c
(
A
p
t
2
); b
v
c
(
A
p
t
1
∣
A
p
t
2
)
=
b
v
c
(
A
p
t
1
)
∪
b
v
c
(
A
p
t
2
).
(iv)
f
v
c
(
A
p
t
1
⊕
p
A
p
t
2
)
=
f
v
c
(
A
p
t
1
)
∪
f
v
c
(
A
p
t
2
); b
v
c
(
A
p
t
1
⊕
p
A
p
t
2
)
=
b
v
c
(
A
p
t
1
)
∪
b
v
c
(
A
p
t
2
).The free and bound clock variables of choices and parallel composition are the union of the free and bound clock variables of each process. The reason that the set of clock variables is divided into bound and free parts is to avoid conflicts of clock valuations. For instance, let us consider the process x
c
≤
8
⊳
(
∥
x
c
∥
A
p
t
), in which the clock x
c is reset, and this affects the invariant x
c
≤
8. Further, in the parallel composition (
∥
x
c
∥
A
p
t
)
|
(
x
c
≤
8
⊳
A
p
t
′
) the clock variable x
c is the shared variable of the two processes; however, the reset of x
c affects the behavior of process (
x
c
≤
8
)
⊳
A
p
t
′. This is undesirable since the operational semantics of a process also depends on the behavior of the environment (which is hard to control).Hence, we define the notion of processes that do not contain any conflict of clock variables, using the following inductive definition and the predicaten
c
v (which refers to "non-conflict of clock variables"):(1)
n
c
v
(
A
);
(2)
n
c
v
(
X
p
t
);
(3)
n
c
v
(
α
*
≺
π
A
p
t
) if and only if n
c
v
(
A
p
t
);
(4)
n
c
v
(
∥
C
R
∥
A
p
t
) if and only if n
c
v
(
A
p
t
);
(5)
n
c
v
(
ϕ
↪
A
p
t
);
(6)
n
c
v
(
ϕ
⊳
A
p
t
)
: in both cases, if and only if n
c
v
(
A
p
t
)
∧
(
c
l
o
c
k
(
ϕ
)
∩
κ
(
A
p
t
)
=
∅
).Rule 1 holds because an extended processA does not include any clock variables. Rule 2 says that the recursive process invocation of plain processes is nonconflict because a plain process does not contain clock variables. Rule 3 comes from the fact that action α
* is free from clock variables. Rule 4 says that the outermost clock resettings do not cause the conflict of variables in process Apt. Rules 5 and 6 say that if guard and invariant constructs are placed outside then their clock variables cannot be reset within A
p
t, to avoid conflict. For the full list of n
c
v rules please check our report [11].In the following, for eachc
r
y
p
t
t
i
m
e
p
r
o
b process we add rules that associate each process with the invariant and resetting functions ∂ and κ, respectively. Note that we only give the two most important rules in this paper; the full list can be found in [11]. Consider the following:(rk) κ
(
∥
C
R
∥
A
p
t
)
=
C
R
∪
κ
(
A
p
t
);
(ri) ∂
(
ϕ
⊳
A
p
t
)
=
∂
(
A
p
t
)
∧
ϕ.Rulerk says that the set of clocks to be reset in κ
(
∥
C
R
∥
A
p
t
) is C
R and the clock resets occur in A
p
t, and rule ri says that the invariant of process ϕ
⊳
A
p
t is the intersection of ϕ and the invariant predicate in A
p
t.


## 4.2. Operational Semantics

The formal semantics ofc
r
y
p
t
t
i
m
e
p
r
o
b follows the semantics of probabilistic timed automata. Namely, a state s is defined by the pair (A
p
t, v), where v is the clock valuation at the location with label A
p
t with the time issues defined at the location. The initial state s
0 consists of the initial process and initial clock valuation (A
p
t
0, v
0). Note that the initial process A
p
t
0 is the initial status of a system behavior, while v
0 typically contains the clocks in the reset state. The operational semantics of c
r
y
p
t
t
i
m
e
p
r
o
b is defined by a probabilistic timed transition system (PTTS).A probabilistic timed transition system can be seen as the labeled transition system extended with time and probabilistic constructs. In our model, we follow the concept of [7, 12], but we also improve them with language elements and a new definition of bisimilarity for proving/refuting the security properties of protocols.Definition 2.
Let∑
‍ be the set of actions. A probabilistic timed transition system is defined as the tuple P
T
T
S
=
(
𝒮
,
∑
‍
×
ℝ
≥
0
×
Π
,
s
0
,
→
P
T
T
S
,
𝒰
,
F
), where (i)
𝒮 is a set of states, and s
0 is an initial state;
(ii)
→
P
T
T
S
⊆
𝒮
×
(
∑
‍
×
ℝ
≥
0
)
×
Π
×
𝒮 is the set of probabilistic timed labeled transitions; a transition is defined between the source and target state, and the label of the transition is composed of the actions, the time stamp (duration), and the probability of the action; when (
α
*
,
d
,
π
)
∈
∑
×
ℝ
≥
0
×
Π we denote the transition from s to s
′ by s
→
α
*
(
d
)
,
π
P
T
T
S
s
′; the appearance of π on the arrow means that the transition is performed with the probability according to the distribution π; the label α
*
(
d
) says that performing either a visible α or invisible (silent) τ action (α
*
=
α
∪
τ) consumes d time units; we interpret d as the time for executing action α
*, and there is no idling time at s before performing an action;
(iii)
𝒰
⊆
ℝ
≥
0
×
𝒮 is the until predicate and is defined at a state s with a time duration d; whenever (
d, s
)
∈
𝒰 we use the notation 𝒰
d;
(iv)
the schedulerF chooses nondeterministically the distribution of action transition steps.The probabilistic timed transition systemP
T
T
S should satisfy the two axioms, Until and Delay (in both cases ⇒ denotes logical implication):(
U
n
t
i
l
) for all d
,
d
′
∈
ℝ
≥
0, 𝒰
d
(
s
)
∧
(
d
′
<
d
)
⇒
𝒰
d
′
(
s
),
(
D
e
l
a
y
) for all d
∈
ℝ
≥
0, s
→
α
*
(
d
)
,
π
P
T
T
S
s
′
for
some
s
′
⇒
𝒰
d
(
s
).These two axioms define formally the meaning of the notions delay and until. Basically, axiomUntil says that if the system stays in state s until d time units then it also stays in this state before d. While the axiom Delay says that if the system performs an action α at time d then it must wait until d. Note that the meaning of until differs from time invariant, because, in case of until, the system waits (stays idled) at least d time units in a given state, whilst time invariant says that the system must leave a given state when d time units have elapsed (if it cannot move from the state then we get deadlock).In addition,𝒰 are the smallest set satisfying the following rules:(u1)
𝒰
d
(
A
,
v
);
(u2)
𝒰
d
(
α
*
≺
π
A
p
t
,
v
);
(u3)
𝒰
d
(
ϕ
↪
A
p
t
,
v
) if 𝒰
d
(
A
p
t
,
v
);
(u4)
𝒰
d
(
∥
C
R
∥
A
p
t
,
v
) if 𝒰
d
(
A
p
t
,
v
[
r
s
t
:
C
R
]
);
(u5)
𝒰
d
(
ϕ
⊳
A
p
t
,
v
) if 𝒰
d
(
A
p
t
,
v
)
∧
⊨
(
v
+
d
)
(
ϕ
);
(u6)
𝒰
d
(
A
p
t
1
[
]
A
p
t
2
,
v
) if 𝒰
d
(
A
p
t
1
,
v
)
∨
𝒰
d
(
A
p
t
2
,
v
);
(u7)
𝒰
d
(
A
p
t
1
∣
A
p
t
2
,
v
) if 𝒰
d
(
A
p
t
1
,
v
)
∨
𝒰
d
(
A
p
t
2
,
v
);
(u8)
𝒰
d
(
A
p
t
1
⊕
p
A
p
t
2
,
v
) if 𝒰
d
(
A
p
t
1
,
v
)
∨
𝒰
d
(
A
p
t
2
,
v
);
(u9)
𝒰
d
(
X
p
t
,
v
) if 𝒰
d
(
P
[
P
/
X
p
t
]
,
v
).Rules (u1-u2) are the Until axioms for the states (A, v) and (α
*
≺
π
A
p
t, v). In u3 the system stays in the state (ϕ
↪
A
p
t, v) until d time units if this is valid to the state (A
p
t, v) as well. Rules (u4-u5) come from the definition of the clock reset and invariant. In rule (u4) v
[
r
s
t
:
C
R
] represents the clock valuation v where the clocks in C
R are reset. Rules (u6–u8) say that the system stays until d time units at the state with A
p
t
1
[
]
A
p
t
2, A
p
t
1
|
A
p
t
2, and A
p
t
1
⊕
p
A
p
t
2 if it stays d time in the state with one of the two processes A
p
t
1 and A
p
t
2. Rule u9 is concerned with the until predicate for (recursive) process variable X
p
t, which comes directly from the definition of recursive process invocation. Note that P is a plain process defined in c
r
y
p
t.We define the satisfaction predicate⊨, ⊨
⊆
Φ
(
𝒞
), on clock constraints. For each ϕ
∈
Φ
(
𝒞
) we use the shorthand ⊨
v
(
ϕ
) if and only if v satisfies ϕ, for all valuation v. The set of past closed constraint, Φ
(
𝒞
)
¯
⊆
Φ
(
𝒞
), is used for defining semantics of location invariant, for all v
∈
𝒱, d
∈
ℝ
≥
0: ⊨
(
v
+
d
)
(
ϕ
)
⇒
⊨
(
v
)
(
ϕ
). Intuitively, this says that if the valuation v
+
d, which is defined as v
(
x
c
)
+
d for all clocks x
c, satisfies the constraint ϕ then so does v. We adopt the variant of time automata used in [7], where location invariant and clock resets are defined as functions ∂ and κ assigning a set of clock constraints Φ
(
𝒞
)
¯ and a set of clocks to be reset ℛ
(
𝒞
), respectively, to a c
r
y
p
t
t
i
m
e
p
r
o
b process.The probabilistic timed transition (action) rules forc
r
y
p
t
t
i
m
e
p
r
o
b are given as follows. We provide the connection of each PTTS transition with the edge syntax well-known in probabilistic timed automata. Consider the following:(a1)
(
α
*
≺
π
A
p
t
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
A
p
t
,
v
+
d
) if α
*
≺
π
A
p
t
→
α
*
,
t
r
u
e
π
A
p
t;
(a2)
(
∥
C
R
∥
A
p
t
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
A
p
t
′
,
v
′
) if (
A
p
t
,
v
[
r
s
t
:
C
R
]
)
→
α
*
(
d
)
,
t
r
u
e
π
(
A
p
t
′
,
v
′
);
(a3)
(
ϕ
↪
A
p
t
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
A
p
t
′
,
v
′
) if (
A
p
t
,
v
)
→
α
*
(
d
)
,
ϕ
π
(
A
p
t
′
,
v
′
)
∧
(
v
+
d
)
(
ϕ
);
(a4)
(
ϕ
⊳
A
p
t
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
A
p
t
′
,
v
′
) if (
A
p
t
,
v
)
→
α
*
(
d
)
,
t
r
u
e
π
(
A
p
t
′
,
v
′
)
∧
(
v
+
d
)
(
ϕ
);
(a5)
(
A
p
t
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
ϕ
⊳
A
p
t
′
,
v
′
) if (
A
p
t
,
v
)
→
α
*
(
d
)
,
t
r
u
e
π
(
A
p
t
′
,
v
′
)
∧
(
v
+
d
)
(
ϕ
);
(a6)
(
A
p
t
1
[
]
A
p
t
2
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
A
p
t
1
′
,
v
′
) if (
A
p
t
1
,
v
)
→
α
*
(
d
)
,
t
r
u
e
π
(
A
p
t
1
′
,
v
′
);
(a
7
/
a)
(
A
p
t
1
⊕
p
A
p
t
2
,
v
)
→
α
*
(
d
)
,
π
(
p
)
P
T
T
S
(
A
p
t
1
′
,
v
′
) if A
p
t
1
⊕
p
A
p
t
2
→
α
*
,
t
r
u
e
π
(
p
)
A
p
t
1
′;
(a
7
/
b)
(
A
p
t
1
⊕
p
A
p
t
2
,
v
)
→
α
*
(
d
)
,
π
(
1
-
p
)
P
T
T
S
(
A
p
t
2
′
,
v
′
) if A
p
t
1
⊕
p
A
p
t
2
→
α
*
(
d
)
,
t
r
u
e
π
(
1
-
p
)
A
p
t
2
′;
(a8)
(
A
p
t
1
∣
A
p
t
2
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
A
p
t
1
′
∣
n
o
r
s
t
(
A
p
t
2
)
,
v
′
) if (
A
p
t
1
,
v
)
→
α
*
(
d
)
,
t
r
u
e
π
(
A
p
t
1
′
,
v
′
);
(a9)
(
X
p
t
,
v
)
→
α
*
(
d
)
,
π
P
T
T
S
(
P
′
,
v
′
) if (
P
[
P
/
X
p
t
]
,
v
)
→
α
*
(
d
)
,
t
r
u
e
π
(
P
′
,
v
′
).In rulea2  v
′
=
v
[
r
s
t
:
C
R
]
+
d and in the rest of the rules v
′
=
v
+
d. v
[
r
s
t
:
C
R
] represents the valuation v where the clocks in C
R are reset. Each rule should be interpreted that the PTTS transition on the left side can be performed if there is an edge in a corresponding automaton. For instance, rule a1 applies if there is an edge α
*
≺
π
A
p
t
→
α
*
,
t
r
u
e
π
A
p
t in the corresponding automaton. Rule a1 says that after performing action α
* with d time units the system gets to the process A
p
t with the clock valuation after d time units elapsed. Rule a2 says that, by the time ∥
C
R
∥
A
p
t proceeds to A
p
t, the clocks in C
R will have been reset. In the rules a3 and a4 the timed transition can be performed if (
v
+
d
)
(
ϕ
) holds, which means that the valuation v
+
d must satisfy the clock guard ϕ. Rules a5-a6 describe the case when process A
p
t
1 is activated (the rules for activating A
p
t
2 are similar). π
(
p
) and π
(
1
-
p
) in rules a7/a-b mean that in distribution π the first and second transitions (edges) are chosen with probabilities p and (1
-
p). In a8, to avoid conflict of clock variables, we require that after performing the transition process A
p
t
2 cannot perform resetting at the beginning. The last rule is the action rule for recursive process variable X
p
t. It can be proven, based on the rules u1–u9 and a1–a9, that probabilistic timed transition system of c
r
y
p
t
t
i
m
e
p
r
o
b satisfies axioms Until and Delay; hence, it is well defined.Theorem 3.
For allc
r
y
p
t
t
i
m
e
p
r
o
b process A
p
t and for all closed valuation v
0, PTTS(A
p
t, v
0, F) is indeed the probabilistic timed transition system defined in probabilistic timed automata.We defined rules for renaming the clock variables and we showed that thencv property is preserved by clock renaming; hence, the restriction we made to process without conflict of clock variables is harmless [7]. Based on the rules of renaming we also added new rules for structural equivalent resulted from renaming. We omit the discussion of these rules in detail because we do not use them, but the reader can find it in our longer report [11].Weak Probabilistic Timed (Prob-Timed) Labeled Bisimulation. We provide a novel bisimilarity definition, called weak prob-timed labeled bisimulation for c
r
y
p
t
t
i
m
e
p
r
o
b, which enables us to prove or refute the security of probabilistic timed systems.Our proposed definition makes use of the definition of static equivalence proposed in the appliedπ-calculus [5], which says that the outputs of static equivalent processes cannot be distinguished by the environment (or attackers). The main advantage of static equivalence is that it only takes into account the static knowledge exposed by two processes to show the behavioral equivalence of them. This method is much easier to use than using the well-known observation equivalence [5], where we have to consider the dynamic behavior of processes.Let the extended processA be {
t
1
/
x
1
}
|
⋯
|
{
t
n
/
x
n
}
∣
P
1
∣
⋯
∣
P
n. The frame
φ of A is the parallel composition {
t
1
/
x
1
}
∣
⋯
∣
{
t
n
/
x
n
} that models all the information that is output so far by the process A, which are t
1
,
…
,
t
n in this case.Definition 4 (static equivalence for extended processes
(
≈
s
)).
Two extended processesA
1 and A
2 are statically equivalent, denoted as A
1
≈
s
A
2, if their frames are statically equivalent. Two frames φ
1 and φ
2 are statically equivalent if they include the same number of active substitutions and the same domain, and any two terms that are equal in φ
1 are equal in φ
2 as well. Intuitively, this means that the outputs of the two processes cannot be distinguished by the environment.In our proposedweak prob-timed labeled bisimulation, we extend the static equivalence with time and probabilistic elements. The meaning of weak is that in this paper we want to examine whether the attackers can distinguish the behavior of two processes, based on the information they can observe. Hence, in weak prob-timed labeled bisimulation, we do not require the equivalence of the probability of two action traces, because practically an observer cannot distinguish if an action is performed with 1/2 or 1/3 probability.Nevertheless, we also proposed the definition ofstrong prob-timed labeled bisimulation in our longer report [11], which we do not discuss in this paper, because we found that, for analysing the security of DTSN and SDTP, it is sufficient to use the weak prob-timed labeled bisimulation. Strong prob-timed labeled bisimulation is stricter, since it also distinguishes two processes based on the probability of their corresponding action traces.Definition 5 (weak prob-timed labeled bisimulation for
c
r
y
p
t
t
i
m
e
p
r
o
b
processes).
LetP
T
T
S
i
(
A
p
t
i
,
v
0
,
F
)
=
(
𝒮
i
,
α
×
ℝ
≥
0
×
Π
,
s
0
i
,
→
P
T
T
S
i
,
𝒰
i
,
F
), and let i
∈
{
1,2
} be two probabilistic timed transition systems for c
r
y
p
t
t
i
m
e
p
r
o
b processes. Weak prob-timed labeled bisimilarity (≈
pt) is the largest symmetric relation ℛ, ℛ
⊆
𝒮
1
×
𝒮
2 with s
0
1
ℛ
s
0
2, where each s
i is the pair of a closed c
r
y
p
t
t
i
m
e
p
r
o
b process and the same initial valuation v
0
∈
𝒱
c, (
A
p
t
i
,
v
0
), such that s
1
ℛ
s
2 implies that (1)
A
1
≈
s
A
2;
(2)
ifs
1
→
τ
(
d
)
,
π
P
T
T
S
1
s
1
′ for a scheduler F, then ∃
s
2
′ such that s
2
⟹
τ
(
∑
‍
d
i
)
,
π
i
P
T
T
S
2
s
2
′ for the same F, with d
=
f
(
∑
d
i
) for some function f, and s
1
′
ℛ
s
2
′;
(3)
ifs
1
→
α
(
d
)
,
π
P
T
T
S
1
s
1
′ for a scheduler F and f
v
(
α
)
⊆
d
o
m
(
A
1
)
∧
b
n
(
α
)
∩
f
n
(
A
2
)
=
∅, then ∃
s
2
′ such that s
2
⟹
α
(
∑
‍
d
j
)
,
π
i
P
T
T
S
2
s
2
′ for the same F, with d
=
f
(
∑
‍
d
j
) for some function f, and s
1
′
ℛ
s
2
′; again, d
o
m
(
A
i
) represents the domain of A
i.
A
1 and A
2 are the extended processes we get by removing all the probabilistic and timed elements from A
p
t
1 and A
p
t
2, respectively.The arrow⇒
α
P
T
T
S is the shorthand of the action trace →
τ
P
T
T
S
*
→
α
P
T
T
S
→
τ
P
T
T
S
*, where →
τ
P
T
T
S
* represents a series (formally, a transitive closure) of sequential transitions →
τ
P
T
T
S. ∑
‍
d
i on ⇒
P
T
T
S is the sum of the time elapsed at each transition and represents the total time elapsed during the sequence of transitions. Note that f
n
(
A
p
t
2
) and d
o
m
(
A
p
t
1
) are the same as f
n
(
A
2
) and d
o
m
(
A
1
), respectively. Moreover, a process A
p
t is closed if its nontimed and “nonprobabilistic” counterpart A is closed.Intuitively, in case thatA
p
t
1 and A
p
t
2 represent two protocols (or two variants of a protocol), then this means that (i) the outputs of the two processes cannot be distinguished by the environment based on their behaviors; (ii) the time that the protocols spend on the performed operations until they reach the corresponding points is in some relationship defined by a function f. Here f depends on the specific definition of the security property; for instance, it can return d itself; hence, the requirement for time consumption would be d
=
∑
d
i. In particular, the first point means that A
p
t
1 and A
p
t
2 are statically equivalent; that is, the environment cannot distinguish the behavior of the two protocols based on their outputs; the second point says that A
p
t
1 and A
p
t
2 remain statically equivalent after silent transition (internal computation) steps. Finally, the third point says that the behavior of the two protocols matches in transition with the action α.


## 5. Security Analysis of DTSN and SDTP Usingc
r
y
p
t
t
i
m
e
p
r
o
b

We formally prove the insecurity of the DTSN and SDTP protocols using the weak prob-timed bisimilarity defined inc
r
y
p
t
t
i
m
e
p
r
o
b. We also specified the behavior of the two protocols using the syntax of c
r
y
p
t
t
i
m
e
p
r
o
b; however, since these descriptions are a bit complicated, for shortening and making the paper readable, we only discuss the most important parts. For the detailed descriptions, the reader is referred to our longer research report [11].We assume the network topologyS
-
I
-
D, where “-” represents a bidirectional link, while S, I, and D denote the source, an intermediate node, and the destination node, respectively. We also include the presence of the application that uses DTSN and SDTP, because it sends packet delivery requests to the source and it receives delivered packets. In the rest of the paper we refer to the application as the upper layer. Note that the attack scenarios which can be found and proved in this topology are also valid in other topologies including more intermediate nodes. Moreover, we assume that each node has three cache entries, denoted by e
k
s, e
k
i, and e
k
d, 1
≤
k
≤
3. For brevity we let e
1
–
3
s range over e
s from index 1 to index 3, and the same is true for e
1
–
3
i and e
1
–
3
d. We define symmetric channels between the upper layer and the source, c
s
u
p; the upper layer and the destination, c
d
u
p; the source and intermediate node, c
s
i; the intermediate node and the destination, c
i
d. Moreover, we define additional channels c
e
r
r
o
r and c
s
e
s
s
i
o
n
E
N
D for sending and receiving error and session end signals.We definec
r
y
p
t
t
i
m
e
p
r
o
b processes upLayer, Src, Int, and Dst for specifying the behavior of the upper layer, the source, intermediate, and destination nodes. The DTSN protocol for the given topology is specified by the parallel composition of these four processes:Prot
(
params
)
=
d
e
f
let(
e
1
s
,
e
2
s
,
e
3
s
,
e
1
i
,
e
2
i
,
e
3
i
,
e
1
d
,
e
2
d
,
e
3
d
,
c
n
t
s
q
)
=(
E
,
E
,
E
,
E
,
E
,
E
,
E
,
E
,
E
,
1
) in I
N
I
T
D
T
S
N
(
);
INITDTSN
(
)
=
d
e
f
c
s
u
p
¯
〈
c
n
t
s
q
〉
.
D
T
S
N
(
p
a
r
a
m
s
)
DTSN
(
params
)
=
d
e
f
upLayer
(
i
n
c
r
(
c
n
t
s
q
)
)
∣
{
x
c
a
c
t
≤
T
a
c
t
}
⊳
i
n
i
t
S
r
c
(
s
,
d
,
apID
,
e
1
-
3
s
,
sID
,
earAtmp
)
∣
Int(
e
1
-
3
i
)
∣
D
s
t(e
1
-
3
d, ackNbr, nackNbr, toRTX1, nxtsq).We refer to the tuple of parameters (cntsq, s, d, apID,
e
1
-
3
i
,  sID, earAtmp,
e
1
-
3
i
,
e
1
-
3
d
, ackNbr, nackNbr, toRTX1, nxtsq) by (params). The process Prot(params) describes DTSN with variable initializations. The let construct is used to initialize the value of the cache entries to E and the current sequence number to 1. The unique name E is used to represent the empty content. In the following, we give a brief overview of the main processes in our specification. Each main process is composed of additional subprocesses, which we skip discussing here. The processes are recursively invoked in a way to model replication. Interested readers can find the full description in [11].We introduce two clock variables:x
c
a
c
t for the activity timer and x
c
e
a
r for the ear timer. According to the specification of the DTSN protocol [2], to model timeout we make use of the clock invariant defined on the process Src. The initial state of DTSN for the given topology is specified as the process ∥
x
c
a
c
t
,
x
c
e
a
r
∥
Prot(params), which simply resets the timers at the beginning. We define the time amount of the activity and ear timers by T
a
c
t and T
e
a
r, respectively. We assume that the activity timer is launched after the upper layer has sent the first request for the source, which is specified in INITDTSN().In processINITDTSN(), first of all, the request for sending the first packet with sequence number cntsq is sent. Then, the next request, c
n
t
s
q
+
1, is enqueued in upLayer(incr(cntsq)). The parameters of process Src are the IDs of the source and the destination; the application ID; the three cache entries, the session ID; and the latest number of EAR attempts. Process Int has the content of the three cache entries as parameter. Process Dst includes the cache entries; the A
C
K/N
A
C
K
numbers for composing acknowledgment messages; the packet to be retransmitted; and the next expected packet.The Source Handling the Activity Timer Expiration
InitSrc
(
s
,
d
,
apID
,
e
1
-
3
s
,
sID
,
earAtmp
)
=
d
e
f
c
s
u
p
(
x
s
q
)
·
(
{
x
c
a
c
t
≤
T
a
c
t
}
⊳
i
n
i
t
F
w
d
D
t
(
s
,
apID
,
e
1
-
3
s
,
sID
,
x
s
q
)
[
]
{
x
c
a
c
t
≤
T
a
c
t
}
⊳
i
n
i
t
R
c
v
A
C
K
S
(
s
,
d
,
apID
,
e
1
-
3
s
,
sID
,
earAtmp
)
[
]
{
x
c
a
c
t
≤
T
a
c
t
}
⊳
i
n
i
t
R
c
v
N
A
C
K
S
(
s
,
d
,
e
1
-
3
s
,
apID
,
sID
,
earAtmp
)
)
[
]
{
x
c
a
c
t
≤
T
a
c
t
}
⊳
c
s
e
s
s
i
o
n
E
N
D
(
=
S
E
N
D
)
·
n
i
l
[
]
{
x
c
a
c
t
≤
T
a
c
t
}
⊳
(
x
c
a
c
t
=
T
a
c
t
)
↪
τ
.
a
c
t
T
i
m
e
O
u
t.The processinitSrc specifies the source node starting with the first packet delivery, when the source does not launch the EAR timer yet but only the ACT (activity) timer. This is defined by the clock invariant construct {
x
c
a
c
t
≤
T
a
c
t
}
⊳ before initSrc. The subprocess actTimeOut describes the behavior of the protocol when the ACT timer expires. Similarly, for the EAR timer, we define the process earTimeOut.The three choice options represent the “wait for event” behavior of the source. Each choice option represents a scenario. The last (third) option describes the case when the activity timer has elapsed. The format{
x
c
a
c
t
≤
T
a
c
t
}
⊳
(
x
c
a
c
t
=
T
a
c
t
)
↪
τ.actTimeOut follows the concept of the timed automaton and says that when the time has elapsed the system should proceed with the process τ.actTimeOut, which describes the defined behavior of Src after timeout. τ is a silent step, moving silently to actTimeOut. In this process, we use τ.actTimeOut instead of actTimeOut, because we insist on the semantics of timed automaton. The second choice is for the case when the session is terminated, which happens when the constant SEND has been sent on the private channel c
s
e
s
s
i
o
n
E
n
d. The session end signal (i.e., the constant SEND) is sent on c
s
e
s
s
i
o
n
E
n
d by Src according to [2]. We assume that the session termination cannot be interrupted by the timeouts; basically, it can be seen as an atomic action. When the first option has been chosen, it means that in that step the source received the delivery request from the upper layer and that no session end or timeouts happen during this input action. The choices among the possible actions are repeatedly put into each subprocess initFwdDt, initRcvACKS, and initRcvNACKS. Namely, the session end, activity, and/or E
A
R
timeouts options are placed before the action steps to be performed.Process That Models the Behavior of an Intermediate Node
I
n
t
(
e
1
-
3
i
)
=
d
e
f
c
s
i
(
(
x
s
,
x
d
,
x
a
p
I
D
,
x
s
I
D
,
x
s
q
,
x
e
a
r
,
x
r
t
x
)
).
h
n
d
l
e
D
t
I
(
s
,
d
,
apID
,
sID
,
sq
,
ear
,
rtx
,
e
1
–
3
i
)
[
]
r
c
v
A
C
K
I
(
e
1
–
3
i
)
[
]
r
c
v
N
A
C
K
I
(
e
1
–
3
i
)
[
]
c
s
e
s
s
i
o
n
E
N
D
(
=
S
E
N
D
)
·
n
i
l.In processInt the intermediate node may receive a data packet on channel c
s
i, in which case it handles the received packet according to the definition of DTSN, it can receive and handle an ACK or NACK message, and it can terminate its operation when it gets the session end signal (i.e., the constant SEND).We also add a probabilistic choice in the specification. According to the definition of the DTSN protocol, the probabilistic choice is placed within processInt(e
i
-
3
i), which is the specification of node I. In particular, after receiving a packet, an intermediate node stores the packet in its cache with probability p. To model this behavior, we add the probabilistic choice construct in the subprocess hndleDtI, which is responsible for handling a received data packet. Consider the following
(13)
s
t
r
A
n
d
F
w
I
(
s
,
d
,
apID
,
sID
,
sq
,
ear
,
rtx
,
e
1
-
3
i
)
⊕
p
F
w
I
(
s
,
d
,
apID
,
sID
,
sq
,
ear
,
rtx
,
e
1
-
3
i
)
.
Process strAndFwI, which describes the case when the intermediate node stores (and forwards) the received packet, is chosen with probability p, and process FwI that specifies the only forwarding case is selected with probability 1
-
p.Process That Models the Behavior of the Destination:
D
s
t
(
e
1
-
3
d
,
ackNbr
,
nackNbr
,
toRTX
1
,
nxtsq
)
=
d
e
f
c
i
d
(
(
x
s
,
x
d
,
x
a
p
I
D
,
x
s
I
D
,
x
s
q
,
x
e
a
r
,
x
r
t
x
)
)
·h
n
d
l
e
D
t
D
s
t
[
]
c
s
e
s
s
i
o
n
E
N
D
(
=
S
E
N
D
)
·
n
i
l.For the processDst, the destination can either receive a data packet on channel c
i
d or receive a session end signal. In the first case, Dst proceeds to hndleDtDst, in which the destination performs the verification steps and delivers the packet to the upper layer or sends an ACK or a NACK.To model the cryptographic primitives and operations in SDTP, we add the following equations into the set of equational theories:Functions: K(n, A
C
K
); K(n,
N
A
C
K
);  MAC(t, K(n,
A
C
K
)).
Equations: CheckMac(MAC(t, K(n,
A
C
K
)), K(n,
A
C
K
)) = ok.
CheckMac(MAC(t, K(n,
N
A
C
K
)), K(n,
N
A
C
K
)) = ok,where functions K(n, A
C
K) and K(n, N
A
C
K) specify the A
C
K and N
A
C
K per-packet keys corresponding to the packet with sequence number n. In order to simplify the modelling procedure, without violating the correctness of SDTP, we make an abstraction of the key hierarchy given in [3], where the per-packet keys are computed with a one-way function based on the shared secret unknown to the attacker. Instead, we assume that K(n, A
C
K) and K(n, N
A
C
K) cannot be generated (but can be intercepted) by the attackers. The attackers can only generate keys that differ from these keys. With this, we model the fact that the shared secret will never be revealed during the protocol.To model the SDTP protocol, we extend the specification of the DTSN protocol in the following way. First, the source node extends each packet with an ACK MAC and a NACK MAC and then sends it to nodeI, which is accomplished by the following code part in the processes initSrc and Src.The Source Sends a Data Packet in SDTP
let (ear, rtx, earAtmp) = (val1, val2, val3) in
let (Kack, Knack) = (K(sq, ACK), K(sq, NACK)) in
letACKMAC = MAC((s, d, apID, sID, sq, ear, rtx), Kack) in
letNACKMAC = MAC((s, d, apID, sID, sq, ear, rtx), Knack) in
c
s
i
¯
〈(s, d, apID, sID, sq, ear, rtx, ACKMAC, NACKMAC)〉
.In the first row, the variablesear, rtx, and earAtmp are given some values val1, val2, and val3, respectively. In the second row the ACK/NACK keys Kack and Knack are generated, while in the third and fourth rows the ACK/NACK MACs are computed using the generated ACK/NACK keys. Finally, the following code part in Src (initSrc) models the case when the EAR (ACT) timer is reset (launched) and the source gets back to the idling state. In the two processes (PR1-2), the clock is reset and then the timeout conditions are defined based on clock invariants (in the form {
x
c
a
c
t
≤
T
a
c
t
,
x
c
e
a
r
≤
T
e
a
r
}).Process PR1: Reseting (Launching) the
E
A
R
Timer.Consider the following:∥
x
c
e
a
r
∥
{
x
c
a
c
t
≤
T
a
c
t
,
x
c
e
a
r
≤
T
e
a
r
}
⊳
Src(s, d, apID, e
1
-
3
s, sID, earAtmp).Process PR2: Reseting (Launching) Both the
E
A
R
and ACT Timers.Consider the following:∥
x
c
e
a
r
,
x
c
a
c
t
∥
{
x
c
a
c
t
≤
T
a
c
t, x
c
e
a
r
≤
T
e
a
r
}
⊳
Src(s, d, apID, e
1
-
3
s, sID, earAtmp).In our formal proofs, we apply the proof technique that is usual in process algebras, such as the appliedπ calculi. Namely, we define an ideal version of the protocol run, in which we specify the ideal/secure operation of the real protocol. This ideal operation, for example, can require that honest nodes always know what is the correct message they should receive/send and always follow the protocol correctly, despite the presence of attackers. Then, we examine whether the real and the ideal versions, running in parallel with the same attacker(s), are weak prob-timed bisimilar.Definition 6.
Let the processesProt() and P
r
o
t
i
d
e
a
l() specify the real and ideal versions of some protocol Prot, respectively. We say that Prot is secure (up to the strictness of the ideal version) if Prot() and P
r
o
t
i
d
e
a
l() are probabilistic timed bisimilar: Prot() ≈
p
t
P
r
o
t
i
d
e
a
l().The strictness of the security requirement, which we expect a protocol to fulfill, depends on how ideally/securely we specify the ideal version. Intuitively, Definition6 says that Prot is secure if the attackers, who can observe the output messages on public channels, cannot distinguish the operation of the two instances.The main difference between the ideal and the real systems is that, in the ideal system, honest nodes are always informed about what kind of packets or messages they should receive from the honest sender node. This can be achieved by defining hidden or private channels between honest parties, on which the communication cannot be observed by attacker(s). In Figure1 we show the difference in more detail. In the ideal case, three private channels are defined which are not available to the attacker(s). Src, Int, and Dst denote the processes for the source, the intermediate, and the destination nodes. Channels c
p
r
i
v
S
D, c
p
r
i
v
I
D, and c
p
r
i
v
S
I are defined between processes Src and Dst, Int and Dst, and Src and Int, respectively. In the rest of the paper, we refer to the source, intermediate, and destination nodes as S, I, and D. Whenever S sends a packet pck on public channel c
s
i, it also informs I about what should I receive, by sending at the same time pck directly via private channel c
p
r
i
v
S
I to I, so when I receives a packet via c
s
i it compares the message with pck. The same happens when I sends a packet to D. Whenever, an honest node receives an unexpected data, it interrupts its normal operation. The channels c
p
r
i
v
S
D and c
p
r
i
v
I
D can be used by the destination to inform S and I about the messages to be retransmitted. We recall that the communication via a private channel is not observable by the environment; hence, it can be seen as a silent τ transition. Note that, for simplicity, we omitted to include the upper layer and channel c
s
u
p in the figure, but we put them in our specification. Finally, we also add additional public channels c
e
m
p
t
y
C and c
n
c
k
n
o
t
0 for signalling that the cache has been emptied and that the number of packets to be retransmitted is larger than 0, respectively. These additional channels are defined only for applying bisimilarities in the security proofs, but they do not affect the correctness of the protocol.The difference between the real and ideal version of the DTSN and the SDTP protocols.
(a)
(b)With this definition we ensure that the source and intermediate nodes are not susceptible to the modification or forging of ACK and NACK messages since they make the correct decision either on retransmitting or deleting the stored packets. Namely, this means that the honest nodes only handle the messages received on public channels when they are equal to the expected messages received on private channels.The Attacker Model
ℳ
A. We assume that an attacker can intercept the information output by the honest nodes on public channels and modify them according to its knowledge and computation ability. The attacker’s knowledge consists of the intercepted outputs during the protocol run and the information it can create. The attacker(s) can modify the elements of the plaintexts, such as the base number and the bits of the ACK/NACK messages, the EAR and RTX bits, and sequence number in data packets. The attacker can also create entire data or control packets including data it possesses. Further, attacker(s) can send packets to its neighborhood. We also assume several attackers who can share information with each other.To describe the activity of the attacker(s), we apply the concept of the environment, used in the appliedπ-calculus [5] that models the presence of the attacker(s) in an implicit way. Every message that is output on a public channel is available for the environment; that is, the environment can be seen as a group of attackers who can share information with each other, for instance, via a side channel.


### 5.1. Security Analysis of the DTSN Protocol

The security properties we want to check in case of the DTSN protocol is that how secure it is against the manipulation of control and data packets. In particular, can the manipulation of packets prevent DTSN from achieving its design goal? In this section we demonstrate how to formally prove the security or vulnerability of DTSN usingc
r
y
p
t
t
i
m
e
p
r
o
b.First of all, we assume that, in both DTSN and SDTP, each action (verification, sending, and receiving on public channel) takes an equal amount of timed and the function f in Definition 5 returns ∑
‍
d
i. This assumption does not change the correctness of the protocols. We define the ideal version of the process Prot(params), denoted by P
r
o
t
i
d
e
a
l
(params), which contains the ideal version of DTSN(params):/* The Ideal Version of the DTSN Protocol for the Given Topology */
P
r
o
t
i
d
e
a
l
(
p
a
r
a
m
s
)
=
d
e
f
let
(
e
1
s
,
e
2
s
,
e
3
s
,
e
1
i
,
e
2
i
,
e
3
i
,
e
1
d
,
e
2
d
,
e
3
d
,
c
n
t
s
q
)
=
(
E
,
E
,
E
,
E
,
E
,
E
,
E
,
E
,
E
,
1
)
in
I
N
I
T
D
T
S
N
i
d
e
a
l
(
),where process I
N
I
T
D
T
S
N
i
d
e
a
l() contains D
T
S
N
i
d
e
a
l(params) instead of DTSN (params).To prove or refute the bisimilarity relation, we defineProt(params) and P
r
o
t
i
d
e
a
l
(params) such that the source and intermediate nodes output the constants CacheEmptyS and CacheEmptyI on the public channel c
e
m
p
t
y
C, respectively, whenever they have emptied their buffers after processing an ACK or a NACK message. This is defined by the following c
r
y
p
t
t
i
m
e
p
r
o
b code fragment (for i
∈
{
1,2
,
3
}), where process checkEi corresponds to the ith cache entry:checkEi(s, d, apID, e
1
-
3
s, sID, acknum) =
d
e
f
/*Cache entry
e
i
s
is emptied and the number of the empty caches is increased */
let(e
i
s, nbrEcacheS) = (E, inc (nbrEcacheS)) in
…
…
…
…
/*Here we add the resetting of the two timers on process Src */
{
x
c
a
c
t
≤
T
a
c
t
,
x
c
e
a
r
≤
T
e
a
r
}
⊳  let (earAtmp = 0) in
/*If the cache has been emptied (emptycacheS = 3) then CacheEmptyS is output */
[emptycacheS = 3]
c
e
m
p
t
y
C
¯
〈
C
a
c
h
e
E
m
p
t
y
S
〉. ∥
x
c
a
c
t
,
x
c
e
a
r
∥
{
x
c
a
c
t
≤
T
a
c
t
}
⊳
Src(s, d, apID, e
1
-
3
s, sID, earAtmp)
else∥
x
c
a
c
t
,
x
c
e
a
r
∥
{
x
c
a
c
t
≤
T
a
c
t
}
⊳
Src(s, d, apID, e
1
-
3
s, sID, earAtmp).The specification of intermediate node is similar to the case of the source, butnbrEcacheI and CacheEmptyI are used instead of nbrEcacheS and CacheEmptyS, respectively. The constants CacheEmptyS and CacheEmptyI are output whenever the number of the empty cache entries, emptycacheS, emptycacheI, is 3, which means that the buffers of S and I are emptied, respectively.Lemma 7.
With the defined attacker modelℳ
A, the DTSN protocol is insecure against message manipulation attacks.According to Definition5 processes Prot(params) and P
r
o
t
i
d
e
a
l
(params) are not weak prob-timed bisimilar because each point of the definition is violated. The following proof show that DTSN is vulnerable to the manipulation of control packets: in SC-1 the attacker increases the base number in ACK packets causing the stored packets to be deleted from the cache although they should not be, while in SC-2 the attacker forces the destination node to send unnecessary ACKs or NACKs.(i)
Scenario SC-1. This scenario can happen beside the topology S
-
I that includes the attacker A within the transmission range of both S and I. We show that the trace of probabilistic timed transitions in the real system, denoted by P
T
T
R
r
e
a
l
S
C
1, cannot be simulated with any corresponding trace in the ideal system. The trace P
T
T
R
r
e
a
l
S
C
1 describes the scenario where the source sends the first packet (sequence number 1) to the intermediate node on channel c
s
i. Because c
s
i is public, this packet is obtained by the attacker(s) (i.e., the environment), who, instead of forwarding it, sends an ACK with base number 1 to S. S received this message on c
s
i
A
C
K, empties its buffer, and outputs the constant CacheEmptyS on the public channel c
e
m
p
t
y
C. As CacheEmptyS will not be output in P
r
o
t
i
d
e
a
l if node I has not sent anything, the first point of Definition 5 is violated.
(ii)
Scenario SC-2. We prove that DTSN is susceptible to the attacks that cause futile energy consumption, by showing the violation of the second point of Definition 5. This scenario can happen in the topology S
-
I
-
D that includes the attacker A within the transmission range of both I and D. The following trace P
T
T
R
r
e
a
l
S
C
2 in the real system cannot be simulated by the ideal system: I sends a correct packet towards D, which is intercepted by A. Then A forwards the packet to D but setting the EAR bit in it to 1, requiring D to send an A
C
K or a N
A
C
K. Let the series of silent transitions s
→
τ
(
d
)
,
π
P
T
T
S
*
s
′ describe the verification steps made by D after receiving the incorrect packet from A. Although at this time there is not any difference in the message outputs, the ideal system still cannot simulate this silent trace, because in this case D performs only one comparison step, which takes less time units.


### 5.2. Security Analysis of the SDTP Protocol

We define the ideal version of processProtSDTP(params), denoted by P
r
o
t
S
D
T
P
i
d
e
a
l
(params), in the same concept as in P
r
o
t
i
d
e
a
l
(params). The only difference is that, in SDTP, the processes Src and Int are defined such that, whenever the MAC verification made by S and I on the received ACK/NACK message fails or an unexpected message is received, S and I output a predefined constant BadControl via the public channel c
b
a
d
p
c
k. Note that this extension does not affect the correctness of SDTP and only plays a role in the proofs of weak prob-timed bisimilarity.Since the main purpose of SDTP is using cryptographic means to patch the security holes of DTSN, we examine the security of SDTP according to each discussed attack scenario to which DTSN is vulnerable.(i)
Proving SC-1. We prove that SDTP is not vulnerable to the attack scenario (SC-1) by showing that P
r
o
t
S
D
T
P
i
d
e
a
l
(params) can simulate (according to Definition 5) the transition trace produced by ProtSDTP(params). In SDTP the packet sent by S includes the ACK MAC and NACK MAC. Hence, when the attacker A sends the ACK to S, in both the real and the ideal systems, the source node outputs the constant BadControl on the channel c
b
a
d
p
c
k, because either the MAC verification fails (in the real system) or the received packet is not the expected one (ideal system). Recall that the MAC verification fails because the attacker does not possess the ACK/NACK keys of the source.
(ii)
Proving SC-2. Similarly, SDTP is not vulnerable to the attack scenario (SC-2) either. P
r
o
t
S
D
T
P
i
d
e
a
l
(params) can simulate the transition trace produced by ProtSDTP(params). After receiving an incorrect packet with EAR bit set to 1, in both the real and the ideal systems, the destination node outputs the constant BadControl on the channel c
b
a
d
p
c
k, because either the MAC verification fails (in the real system) or the received packet is not the expected one (ideal system). Hence, they consume equal time units.As we can see, with the security extensions SDTP could eliminate the essential weaknesses of DTSN; however, we will prove that it is still vulnerable, by showing a trace in the real systemProtSDTP(params), which cannot be simulated in P
r
o
t
S
D
T
P
i
d
e
a
l
(params).Lemma 8.
The SDTP protocol is insecure besides the attacker modelℳ
A.To prove the vulnerability of SDTP using prob-timed bisimilarity, we relax the definition of the ideal version such that the honest nodes only compare the received ACK/NACK messages with the expected ones. When they receive a data packet they proceed in the same way as the real version, namely, without any comparison with the expected message that it receives on private channels.Proving SC-3. We consider the trace that refers to the topology S
-
A
1
-
I
-
A
2. The trace describes the following scenario: A
1 has received the first packet from S, it replaces the MACs computed by S with the MACs it computes on the same data (denoted by A
C
K
M
A
C
a
t
t, N
A
C
K
M
A
C
a
t
t), and it sends the modified packet to I. Node I forwards the packet to A
2, which, instead of forwarding it to D, sends back the ACK message for this data packet to I, including the corresponding ACK key for the MAC A
C
K
M
A
C
a
t
t. As the result, node I deletes its buffer and outputs the constant CacheEmptyI on the public channel c
e
m
p
t
y
C. This transition cannot be simulated by any corresponding transition trace in P
r
o
t
S
D
T
P
i
d
e
a
l
(params). Because, in this case, the ACK sent by A2 will be received on c
i
d
A
C
K
(
x
r
c
v
); then, node I interrupts its operation. Hence, CacheEmptyI will never be output.Note that we also performed verification and showed other weaknesses of SDTP; the reader can find them in our technical report [11].


## 5.1. Security Analysis of the DTSN Protocol

The security properties we want to check in case of the DTSN protocol is that how secure it is against the manipulation of control and data packets. In particular, can the manipulation of packets prevent DTSN from achieving its design goal? In this section we demonstrate how to formally prove the security or vulnerability of DTSN usingc
r
y
p
t
t
i
m
e
p
r
o
b.First of all, we assume that, in both DTSN and SDTP, each action (verification, sending, and receiving on public channel) takes an equal amount of timed and the function f in Definition 5 returns ∑
‍
d
i. This assumption does not change the correctness of the protocols. We define the ideal version of the process Prot(params), denoted by P
r
o
t
i
d
e
a
l
(params), which contains the ideal version of DTSN(params):/* The Ideal Version of the DTSN Protocol for the Given Topology */
P
r
o
t
i
d
e
a
l
(
p
a
r
a
m
s
)
=
d
e
f
let
(
e
1
s
,
e
2
s
,
e
3
s
,
e
1
i
,
e
2
i
,
e
3
i
,
e
1
d
,
e
2
d
,
e
3
d
,
c
n
t
s
q
)
=
(
E
,
E
,
E
,
E
,
E
,
E
,
E
,
E
,
E
,
1
)
in
I
N
I
T
D
T
S
N
i
d
e
a
l
(
),where process I
N
I
T
D
T
S
N
i
d
e
a
l() contains D
T
S
N
i
d
e
a
l(params) instead of DTSN (params).To prove or refute the bisimilarity relation, we defineProt(params) and P
r
o
t
i
d
e
a
l
(params) such that the source and intermediate nodes output the constants CacheEmptyS and CacheEmptyI on the public channel c
e
m
p
t
y
C, respectively, whenever they have emptied their buffers after processing an ACK or a NACK message. This is defined by the following c
r
y
p
t
t
i
m
e
p
r
o
b code fragment (for i
∈
{
1,2
,
3
}), where process checkEi corresponds to the ith cache entry:checkEi(s, d, apID, e
1
-
3
s, sID, acknum) =
d
e
f
/*Cache entry
e
i
s
is emptied and the number of the empty caches is increased */
let(e
i
s, nbrEcacheS) = (E, inc (nbrEcacheS)) in
…
…
…
…
/*Here we add the resetting of the two timers on process Src */
{
x
c
a
c
t
≤
T
a
c
t
,
x
c
e
a
r
≤
T
e
a
r
}
⊳  let (earAtmp = 0) in
/*If the cache has been emptied (emptycacheS = 3) then CacheEmptyS is output */
[emptycacheS = 3]
c
e
m
p
t
y
C
¯
〈
C
a
c
h
e
E
m
p
t
y
S
〉. ∥
x
c
a
c
t
,
x
c
e
a
r
∥
{
x
c
a
c
t
≤
T
a
c
t
}
⊳
Src(s, d, apID, e
1
-
3
s, sID, earAtmp)
else∥
x
c
a
c
t
,
x
c
e
a
r
∥
{
x
c
a
c
t
≤
T
a
c
t
}
⊳
Src(s, d, apID, e
1
-
3
s, sID, earAtmp).The specification of intermediate node is similar to the case of the source, butnbrEcacheI and CacheEmptyI are used instead of nbrEcacheS and CacheEmptyS, respectively. The constants CacheEmptyS and CacheEmptyI are output whenever the number of the empty cache entries, emptycacheS, emptycacheI, is 3, which means that the buffers of S and I are emptied, respectively.Lemma 7.
With the defined attacker modelℳ
A, the DTSN protocol is insecure against message manipulation attacks.According to Definition5 processes Prot(params) and P
r
o
t
i
d
e
a
l
(params) are not weak prob-timed bisimilar because each point of the definition is violated. The following proof show that DTSN is vulnerable to the manipulation of control packets: in SC-1 the attacker increases the base number in ACK packets causing the stored packets to be deleted from the cache although they should not be, while in SC-2 the attacker forces the destination node to send unnecessary ACKs or NACKs.(i)
Scenario SC-1. This scenario can happen beside the topology S
-
I that includes the attacker A within the transmission range of both S and I. We show that the trace of probabilistic timed transitions in the real system, denoted by P
T
T
R
r
e
a
l
S
C
1, cannot be simulated with any corresponding trace in the ideal system. The trace P
T
T
R
r
e
a
l
S
C
1 describes the scenario where the source sends the first packet (sequence number 1) to the intermediate node on channel c
s
i. Because c
s
i is public, this packet is obtained by the attacker(s) (i.e., the environment), who, instead of forwarding it, sends an ACK with base number 1 to S. S received this message on c
s
i
A
C
K, empties its buffer, and outputs the constant CacheEmptyS on the public channel c
e
m
p
t
y
C. As CacheEmptyS will not be output in P
r
o
t
i
d
e
a
l if node I has not sent anything, the first point of Definition 5 is violated.
(ii)
Scenario SC-2. We prove that DTSN is susceptible to the attacks that cause futile energy consumption, by showing the violation of the second point of Definition 5. This scenario can happen in the topology S
-
I
-
D that includes the attacker A within the transmission range of both I and D. The following trace P
T
T
R
r
e
a
l
S
C
2 in the real system cannot be simulated by the ideal system: I sends a correct packet towards D, which is intercepted by A. Then A forwards the packet to D but setting the EAR bit in it to 1, requiring D to send an A
C
K or a N
A
C
K. Let the series of silent transitions s
→
τ
(
d
)
,
π
P
T
T
S
*
s
′ describe the verification steps made by D after receiving the incorrect packet from A. Although at this time there is not any difference in the message outputs, the ideal system still cannot simulate this silent trace, because in this case D performs only one comparison step, which takes less time units.


## 5.2. Security Analysis of the SDTP Protocol

We define the ideal version of processProtSDTP(params), denoted by P
r
o
t
S
D
T
P
i
d
e
a
l
(params), in the same concept as in P
r
o
t
i
d
e
a
l
(params). The only difference is that, in SDTP, the processes Src and Int are defined such that, whenever the MAC verification made by S and I on the received ACK/NACK message fails or an unexpected message is received, S and I output a predefined constant BadControl via the public channel c
b
a
d
p
c
k. Note that this extension does not affect the correctness of SDTP and only plays a role in the proofs of weak prob-timed bisimilarity.Since the main purpose of SDTP is using cryptographic means to patch the security holes of DTSN, we examine the security of SDTP according to each discussed attack scenario to which DTSN is vulnerable.(i)
Proving SC-1. We prove that SDTP is not vulnerable to the attack scenario (SC-1) by showing that P
r
o
t
S
D
T
P
i
d
e
a
l
(params) can simulate (according to Definition 5) the transition trace produced by ProtSDTP(params). In SDTP the packet sent by S includes the ACK MAC and NACK MAC. Hence, when the attacker A sends the ACK to S, in both the real and the ideal systems, the source node outputs the constant BadControl on the channel c
b
a
d
p
c
k, because either the MAC verification fails (in the real system) or the received packet is not the expected one (ideal system). Recall that the MAC verification fails because the attacker does not possess the ACK/NACK keys of the source.
(ii)
Proving SC-2. Similarly, SDTP is not vulnerable to the attack scenario (SC-2) either. P
r
o
t
S
D
T
P
i
d
e
a
l
(params) can simulate the transition trace produced by ProtSDTP(params). After receiving an incorrect packet with EAR bit set to 1, in both the real and the ideal systems, the destination node outputs the constant BadControl on the channel c
b
a
d
p
c
k, because either the MAC verification fails (in the real system) or the received packet is not the expected one (ideal system). Hence, they consume equal time units.As we can see, with the security extensions SDTP could eliminate the essential weaknesses of DTSN; however, we will prove that it is still vulnerable, by showing a trace in the real systemProtSDTP(params), which cannot be simulated in P
r
o
t
S
D
T
P
i
d
e
a
l
(params).Lemma 8.
The SDTP protocol is insecure besides the attacker modelℳ
A.To prove the vulnerability of SDTP using prob-timed bisimilarity, we relax the definition of the ideal version such that the honest nodes only compare the received ACK/NACK messages with the expected ones. When they receive a data packet they proceed in the same way as the real version, namely, without any comparison with the expected message that it receives on private channels.Proving SC-3. We consider the trace that refers to the topology S
-
A
1
-
I
-
A
2. The trace describes the following scenario: A
1 has received the first packet from S, it replaces the MACs computed by S with the MACs it computes on the same data (denoted by A
C
K
M
A
C
a
t
t, N
A
C
K
M
A
C
a
t
t), and it sends the modified packet to I. Node I forwards the packet to A
2, which, instead of forwarding it to D, sends back the ACK message for this data packet to I, including the corresponding ACK key for the MAC A
C
K
M
A
C
a
t
t. As the result, node I deletes its buffer and outputs the constant CacheEmptyI on the public channel c
e
m
p
t
y
C. This transition cannot be simulated by any corresponding transition trace in P
r
o
t
S
D
T
P
i
d
e
a
l
(params). Because, in this case, the ACK sent by A2 will be received on c
i
d
A
C
K
(
x
r
c
v
); then, node I interrupts its operation. Hence, CacheEmptyI will never be output.Note that we also performed verification and showed other weaknesses of SDTP; the reader can find them in our technical report [11].


## 6. Automated Security Verification Using the PAT Process Analysis Toolkit

Related Methods. SPIN model checker [14] and UPPAAL [15] are general purpose model checking tools. CPAL-ES [16] and ProVerif [13] are automatic verification tools developed for verifying security protocols. The main drawback of them is that they lack semantics and syntax for defining the systems that include probabilistic and real-time behavior. Hence, they cannot be used to verify WSN transport protocols such as DTSN and SDTP. PRISM model checker [17] supports probabilistic and real-time systems but its limited specification language does not enable us to verify protocols/sytems that may perform complex computations.Our Method. Our method is based on the PAT process analysis toolkit. PAT [8] is a self-contained framework to specify and automatically verify different properties of concurrent (i.e., supporting parallel compositions construct), real-time systems with probabilistic behavior. It provides a user friendly graphical interface, a featured model editor, and an animated simulator for debugging purposes. PAT implements various state-of-the-art model checking techniques for different properties such as reachability, LTL properties with fairness assumptions, refinement checking, and probabilistic model checking. To handle large state spaces, the framework also includes many well-known model checking optimization methods.One of the biggest advantages of PAT compared with other solutions is that it supports probabilistic and timed, CSP-like behavioral syntax and semantics, which are important in our case. Currently it contains eleven modules to deal with problems in different domains including real-time and probabilistic systems. PAT has been used to model and verify a variety of systems, such as distributed algorithms, and real-world systems like multilift and pacemaker systems. However, PAT (so far) does not provide syntax and semantics for specifying cryptographic primitives and operations, such as digital signature, MAC, encryptions and decryptions, and one-way hash function. Hence, we model cryptographic operations used by SDTP in an abstract, simplified way. Note that the simplification has been made in an intuitive way and does not endanger the correctness of the protocol.PAT is basically designed as a general purpose tool not specifically for security protocols. It provides a CSP [18] like syntax, but it is more expressive than CSP because it also includes the language constructs for time and probabilistic issues. PAT also provides programming elements like communication channels, array of variables and channels, similarly to Promela [19] (Process Meta Language), the specification language used by the SPIN [19] model-checker. PAT handles time in a tricky way; namely, instead of modeling clocks and clock resets in an explicit manner, to make the automatic verification more efficient it applies an implicit representation of time (clocks).Next, we briefly introduce the features provided by the main modules of PAT that we use to verify the security of DTSN and SDTP.Communicating Sequential Programs (CSP#) Module. The CSP# module supports a rich modeling language named CSP# (a modified variant of CSP) that features process algebra operators like (conditional or nondeterministic) choices, interrupt, parallel composition, interleaving, hiding, asynchronous message passing channel, and mathematical operators like summation, multiplication.It also provides low-level constructs likearrays, if-then-else, and while. The modeling of communication among processes is based on message passing via communication channels. Communication channels sending and receiving on a channel can be defined with the following syntax:(1)
(declaration of channel channame):
channel channame size;
(2)
(output of the msg tuple (m1,m2,m3) on
channame):channame!m1.m2.m3;
(3)
(input a msg (m1,m2,m3) on the
channel channame): channame?x1.x2.x3;
channel is a keyword for declaring channels only, channame is the channel name, and size is the channel buffer size. It is important that a channel with buffer size 0 sends/receives messages synchronously. A process is a relevant specification element in PAT that is defined as an equation P
(
x
1
,
x
2
,
…
,
x
n
)
= ProcExp, where ProcExp defines the behavior of process P. PAT defines special processes to make coding be more convenient: process Stop is the deadlock process that does nothing; process Skip terminates immediately and then behaves exactly in the same way as Stop.Events are defined in PAT to make debugging more straightforward and to make the returned attack traces more readable. A simple event is a name for representing an observation. Given a processP, the syntax e
v
->
P describes a process which performs e
v first and then behaves as P. An event e
v can be a simple event or can be combined with assignments which update global variables as in the following example: e
v
{
x
=
x
+
1
;
}
-
>
S
t
o
p, where x is a global variable.Asequential composition of two processes P and Q is written as P
;
Q in which P starts first and Q starts only when P has finished. A (general) choice is written as P
[
]
Q, which states that either P or Q may be executed. If P performs an event first, then P takes control. Otherwise, Q takes control. Interleaving represents two processes, which run concurrently, and is denoted by P
|
|
|
Q.Real-Time System (RTS) Module. The RTS module in PAT enables us to specify and analyse real-time systems and verify timing properties. To make the automatic verification more efficient, unlike timed automata that define explicit clock variables and capture real-time constraints by explicitly setting/reseting clock variables, PAT defines several timed behavioral patterns to capture high-level quantitative timing requirements, such as wait, timeout, deadline, waituntil, timed interrupt, and within. For instance, process P
interrupt[t]
Q behaves as P until t time units elapse and then it switches to Q.Probability RTS (PRTS) Module. The PRTS module supports means for analyzing probabilistic real-timed systems by extending the RTS module with probabilistic choices and assertions. The most important extension added by the PRTS module is the probabilistic choice (defined with the keyword pcase):prtsP = pcase{
[
prob
1
]
[prob1]: prtsQ1
[prob2]: prtsQ2
⋯
[probn]: prtsQn
};whereprtsP, prtsQ1,…, prtsQn are PRTS processes which can be normal processes, timed processes, probabilistic processes, or probabilistic timed processes. prtsP can proceed as prtsQ1, prtsQ2,
…
, prtsQn with probabilities prob1, prob2,…, probn, respectively.PAT supports a probabilistic assertion, which is a query about the system’s probabilistic behaviors, namely, the reachabiliy of a defined goal with some probability:#assert prtsP() reaches cond with prob/
pmin/pmax.this returns respectively the probability, the minimal probability, and the maximal probability of the event that processprtsP()reaches a state where the boolean expression cond is true.


### 6.1. On Verifying SDTP Using the PAT Process Analysis Toolkit

We verify SDTP assuming the topologiesTop1: S
-
A
1
-
I
-
D, Top2: S
-
I
-
A
2
-
D, and Top3: S
-
A
1
-
I
-
A
2
-
D. Following the concept in Section 5, we define public (symmetric) channels between each node pair and define additional symmetric channels chASPck, chASAck, chASNack, chASEAR, chADPck, chADAck, chADNack, and chADEAR, between the attacker(s) and its (their) honest neighbors.As already mentioned earlier, PAT does not support language elements for specifying cryptographic primitives and operations in an explicit way. We specify the operation of SDTP with the implicit representation of MACs and ACK/NACK keys. First, recall that in SDTP the per-packet ACK and NACK keys are generated as(14)
K
A
C
K
(
n
)
=
P
R
F
(
K
A
C
K
;
“per
packet
A
C
K
k
e
y
”
;
n
)
,
K
A
C
K
(
n
)
=
PRF
(
K
K
A
C
K
;
“per
packet
N
A
C
K
key”
;
n
)
.Following this concept, in PAT we define the ACK key and NACK key for the packet with sequence numbern by the “pair” n.Kack and n.Knack, respectively. To reduce the verification complexity we made abstraction on the key generation procedure and model the session ACK/NACK master keys by the unique constants Kack and Knack. Then we specify the packets sent by the source node as follows: sq.ear.rtx.sq.sq.Kack.sq.sq.Knack, where the first part sq.ear.rtx contains the packet’s sequence number and the EAR and RTX bits, respectively; the second part sq.sq.Kack and the third part sq.sq.Knack represent the ACK MAC and NACK MAC computed over the packet with sequence number sq without the EAR and RTX bits, using the per-packet ACK and NACK keys sq.Kack and sq.Knack. An ACK message has the following forms: acknbr.acknbr.Kack, where acknbr.Kack is the corresponding ACK key of acknbr. A NACK message has the format acknbr.nckb1.acknbr.Kack.nckb.Knack, where nckb.Knack is the NACK key of the packet to be retransmitted. The NACK message can include more bits, in a similar way.By default, the attackers do not possess the two master keysKack and Knack of honest nodes but only their own key Katt. Because honest nodes are specified to wait for these MACs format, the attackers should compose the MACs in this format as well, namely, sqA.sqA.Katt. The attackers cannot use the master keys to construct the per-packet ACK/NACK keys, and when they obtain a MAC, for example, sq.sq.Kack, they cannot use sq.Kack, only in case they receives sq.Kack.We distinguish the following scenarios and examine the possible ability of the attacker(s). The behaviors of the attackers are defined as the processesprocA1() and procA2(). In our model, by default the attackers have two sequence numbers seqA1 and seqA2 which are the smallest (i.e., 1) and the largest possible sequence numbers, respectively. The attackers can include earA
∈
{
0
,
1
}, rtxA  ∈
{
0
,
1
} in their data packets. The attackers, in addition, possess the predefined values b
A
1
,
…
,
b
A
4 for requiring retransmission in NACK messages.ProcessprocA1(), which defines the behavior of the first attacker A
1, is specified as an external choice among the following four activities (each of them is composed of additional choice options).(1)
Without Receiving Any Message. (i) A
1 sends a data packet, with seqA1.earA.rtxA or seqA2.earA.rtxA, to I; (ii) A
1 sends an ACK, for the packet seqA1 or seqA2, to I or to S; (iii) A
1 sends a NACK, with the ack numbers seqA1 or seqA2, and a combination of b
A
1
,
…
,
b
A
4, to I or to S.
(2)
After Receiving a Data Packet (chSAPck?seq.ear.rtx). (i) A
1 sends a data packet, with the sequence number seq, seqA1, or seqA2, and different values ear/rtx bits, to I; (ii) A
1 sends an ACK, with the ack number seq, seqA1, or seqA2, to I or S; (iii) A
1 sends a NACK, with the ack number seq, seqA1, or seqA2, and a combination of b
A
1
,
…
,
b
A
4, to I or to S.
(3)
After Receiving an
A
C
K (chIAAck?ack). (i) A
1 sends a data packet, with the sequence number ack, seqA1, or seqA2, to I; (ii) A
1 sends an ACK, with the ack number ack, seqA1, or seqA2, to I or to S; (iii) A
1 sends a NACK, with the ack number ack, seqA1, or seqA2, and a combination of b
A
1
,
…
,
b
A
4, to I or to S.
(4)
After Receiving a
N
A
C
K
with 1–4 Bits (chIANack?ack.b1
[
]
chIANack?ack.b1.b2
[
]
chIANack?ack.b1.b2.b3
[
]
chIANack?ack.b1.b2.b3.b4). (i) A
1 sends a data packet, with with the sequence number ack, seqA1, or seqA2, to I; (ii) A
1 sends an ACK, with the sequence number ack, seqA1, or seqA2, and a combination of b
A
1
,
…
,
b
A
4
,
b
1
,
b
2
,
b
3
,
b
4, to I or to S; (iii) A
1 sends a NACK to I or to S. We recall that the attacker, besides the self-generated data, can only use the information in the received messages. Hence, when the attacker receives the NACK ack.b1, it can only use (besides its own data) ack and b1.We denote the attackers with this kind of behavior byℳ
A
P
A
T. The SDTP protocol with the second topology is specified as the parallel compositions of each honest node and the attacker A1:
(15)
SDTPA
1
(
)
=
procS
(
)
|
|
|
procA
1
(
)
|
|
|
procI
(
)
|
|
|
procD
(
)
.Again, each process is recursively called, in such a way that is equivalent to replication of many instances of the processes. For the second topologyS-I-A
2
-D, the scenarios and PAT codes are the same as in the case of the first topology S-A
1
-I-D except that the used channels at each corresponding step are changed as follows. In the first topology, A1 receives data packets from S on chSAPck, which is changed to chIAPck in the second case because now data packets come from I. Similarly, the inputs on chSAAck and chSANack are changed to chDAAack and chDANack, respectively. The outputs by A on chIAPck, chIAAck, chIANack, chSAAck, and chSANack are changed to chDAPck, chDAAck, chDANack, chIAAck, and chIANack, respectively. The attacker process procA2() describing the behavior of A2 is specified in the same way as procA1() but with different channels.The SDTP protocol with the second topology is specified as the following parallel compositions:(16)
SDTPA
2
(
)
=
UpLayer
(
)
|
|
|
procS
(
)
|
|
|
procI
(
)
|
|
|
procA
2
(
)
|
|
|
procD
(
)
.For the third topology S-A1-I-A2-D, we apply the specification of both processes A1 and A2. The SDTP protocol with the third topology is specified as the parallel compositions of each honest node and the two attackers:(17)
SDTPA
1
A
2
(
)
=
UpLayer
(
)
|
|
|
procS
(
)
|
|
|
procA
1
(
)
|
|
|
procI
(
)
|
|
|
procA
2
(
)
|
|
|
procD
(
)
.Assertions. The assertion, denoted by violategoal1, for verifying the provision of reliable delivery of packets, is as follows:#define violategoal1
(
OutBufL
=
=
0
&
&
BufI
=
=
0
&
&
num
N
A
C
K
>
0
),where the (global) variables OutBufL, BufI are the number of the occupied cache entries at the source and intermediate node, respectively, while the variable num
N
A
C
K is the number of those packets that the destination has not received and that require to be retransmitted. Hence, (OutBufL == 0) and (BufI == 0) represent that the cache of S and I are emptied, but at the same time (num
N
A
C
K > 0) means that D has not received all of the packets.The following PAT code is applied for asking if these bad states can be reached in SDTP:(B1)
#assert SDTP() reaches violategoal1p1;
(B2)
#assert SDTP() reaches violategoal1p1 with pmax.For the topologyTop2, we run PAT to model-check (B1) and get the result Not Valid. This means that, in the presence of the defined attacker(s) ℳ
A
P
A
T, SDTP cannot be corrupted such that D has not received some packets and required retransmissions but the buffers of S and I are emptied. Assertion (B2) also results in Not valid.Now let us consider the topologyTop3 that includes two attackers A
1 and A
2. We specify the bad states for SDTP (and DTSN), and we run the model checking to see if these bad states can be reached. The bad states and the verification goals can be defined in PAT’s language in the form of logical formulas and assertions, respectively.Let the number of buffer entries that are freed at nodeI after receiving an ACK/NACK message be freenum, and let the number of packets received in sequence by node D be acknum. The bad state violategoal2 specifies the state where (freenum > acknum) (see Algorithm 1).Algorithm 1
P
AT code:
#define violategoal2 (freenum > acknum)
B5. #assert SDTPsubA1subA2() reaches violategoal2
B6. #assert SDTPA1A2() reaches violategoal2We run the PAT model checker with the attacker processes (see Algorithm2).Algorithm 2
s
ubA1() =
/* A1 sends a data packet to I, without receiving any message, OR */
A1NotRcvSndPck2I()
/* After receiving a data packet on channel chSAPck */
[
]   chSAPck?seq.ear.rtx.seq1.seq2.Kack.seq3.seq4.Knack ->
(
/* A1 sends a data packet to I, OR */
A1RcvPckSndPck2I()
/* A1 forwards the packet unchanged to I */
[
]   chIAPck!seq.ear.rtx.seq1.seq2.Kack.seq3.seq4.Knack -> subA1()
)
subA2() =
/* A2 sends a data packet to I, without receiving any message, OR */
A2NotRcvSndAck2I()
/* After getting a data on channel chIAPck, A2 sends ACK with seqA2 to I */
[
]   chIAPck?seq.ear.rtx.seq1.seq2.Kack.seq3.seq4.Knack -> A2RcvPckSndAck2I()
SDTPsubA1subA2() =
UpLayer()|||
procS()||| subA1() ||| procI() ||| subA2() ||| procD()As a result, the tool returnedValid for the assertions B
5 and B
6 along with the following trace.(1)
A1 sends to I a data pckseqA2.ear.rtx with the corresponding ACK MACs: seqA2.seqA2.Katt and NACK MACs: seqA2.seqA2.Katt.
(2)
I stores this pck and forwards it (unchanged) to A2.
(3)
A2 received this packet and sends to I the ACK for seqA2:seqA2.seqA2.Katt.seqA2.Katt with the 2 keys seqA2.Katt and seqA2.Katt.
(4)
As result, I deletes all the packets stored in its buffer because the keyseqA2.Katt and the MAC seqA2.seqA2.Katt match.In summary, we get the result that both DTSN and SDTP are susceptible for this sandwich style attack scenario. The main reason for this weakness is that in SDTP the intermediate nodes do not verify the origin of the received messages; they only check if the stored ACK/NACK MACs match the received ACK/NACK keys.We also performed verification and showed other weaknesses of SDTP; the reader can find them in our technical report [11].


## 6.1. On Verifying SDTP Using the PAT Process Analysis Toolkit

We verify SDTP assuming the topologiesTop1: S
-
A
1
-
I
-
D, Top2: S
-
I
-
A
2
-
D, and Top3: S
-
A
1
-
I
-
A
2
-
D. Following the concept in Section 5, we define public (symmetric) channels between each node pair and define additional symmetric channels chASPck, chASAck, chASNack, chASEAR, chADPck, chADAck, chADNack, and chADEAR, between the attacker(s) and its (their) honest neighbors.As already mentioned earlier, PAT does not support language elements for specifying cryptographic primitives and operations in an explicit way. We specify the operation of SDTP with the implicit representation of MACs and ACK/NACK keys. First, recall that in SDTP the per-packet ACK and NACK keys are generated as(14)
K
A
C
K
(
n
)
=
P
R
F
(
K
A
C
K
;
“per
packet
A
C
K
k
e
y
”
;
n
)
,
K
A
C
K
(
n
)
=
PRF
(
K
K
A
C
K
;
“per
packet
N
A
C
K
key”
;
n
)
.Following this concept, in PAT we define the ACK key and NACK key for the packet with sequence numbern by the “pair” n.Kack and n.Knack, respectively. To reduce the verification complexity we made abstraction on the key generation procedure and model the session ACK/NACK master keys by the unique constants Kack and Knack. Then we specify the packets sent by the source node as follows: sq.ear.rtx.sq.sq.Kack.sq.sq.Knack, where the first part sq.ear.rtx contains the packet’s sequence number and the EAR and RTX bits, respectively; the second part sq.sq.Kack and the third part sq.sq.Knack represent the ACK MAC and NACK MAC computed over the packet with sequence number sq without the EAR and RTX bits, using the per-packet ACK and NACK keys sq.Kack and sq.Knack. An ACK message has the following forms: acknbr.acknbr.Kack, where acknbr.Kack is the corresponding ACK key of acknbr. A NACK message has the format acknbr.nckb1.acknbr.Kack.nckb.Knack, where nckb.Knack is the NACK key of the packet to be retransmitted. The NACK message can include more bits, in a similar way.By default, the attackers do not possess the two master keysKack and Knack of honest nodes but only their own key Katt. Because honest nodes are specified to wait for these MACs format, the attackers should compose the MACs in this format as well, namely, sqA.sqA.Katt. The attackers cannot use the master keys to construct the per-packet ACK/NACK keys, and when they obtain a MAC, for example, sq.sq.Kack, they cannot use sq.Kack, only in case they receives sq.Kack.We distinguish the following scenarios and examine the possible ability of the attacker(s). The behaviors of the attackers are defined as the processesprocA1() and procA2(). In our model, by default the attackers have two sequence numbers seqA1 and seqA2 which are the smallest (i.e., 1) and the largest possible sequence numbers, respectively. The attackers can include earA
∈
{
0
,
1
}, rtxA  ∈
{
0
,
1
} in their data packets. The attackers, in addition, possess the predefined values b
A
1
,
…
,
b
A
4 for requiring retransmission in NACK messages.ProcessprocA1(), which defines the behavior of the first attacker A
1, is specified as an external choice among the following four activities (each of them is composed of additional choice options).(1)
Without Receiving Any Message. (i) A
1 sends a data packet, with seqA1.earA.rtxA or seqA2.earA.rtxA, to I; (ii) A
1 sends an ACK, for the packet seqA1 or seqA2, to I or to S; (iii) A
1 sends a NACK, with the ack numbers seqA1 or seqA2, and a combination of b
A
1
,
…
,
b
A
4, to I or to S.
(2)
After Receiving a Data Packet (chSAPck?seq.ear.rtx). (i) A
1 sends a data packet, with the sequence number seq, seqA1, or seqA2, and different values ear/rtx bits, to I; (ii) A
1 sends an ACK, with the ack number seq, seqA1, or seqA2, to I or S; (iii) A
1 sends a NACK, with the ack number seq, seqA1, or seqA2, and a combination of b
A
1
,
…
,
b
A
4, to I or to S.
(3)
After Receiving an
A
C
K (chIAAck?ack). (i) A
1 sends a data packet, with the sequence number ack, seqA1, or seqA2, to I; (ii) A
1 sends an ACK, with the ack number ack, seqA1, or seqA2, to I or to S; (iii) A
1 sends a NACK, with the ack number ack, seqA1, or seqA2, and a combination of b
A
1
,
…
,
b
A
4, to I or to S.
(4)
After Receiving a
N
A
C
K
with 1–4 Bits (chIANack?ack.b1
[
]
chIANack?ack.b1.b2
[
]
chIANack?ack.b1.b2.b3
[
]
chIANack?ack.b1.b2.b3.b4). (i) A
1 sends a data packet, with with the sequence number ack, seqA1, or seqA2, to I; (ii) A
1 sends an ACK, with the sequence number ack, seqA1, or seqA2, and a combination of b
A
1
,
…
,
b
A
4
,
b
1
,
b
2
,
b
3
,
b
4, to I or to S; (iii) A
1 sends a NACK to I or to S. We recall that the attacker, besides the self-generated data, can only use the information in the received messages. Hence, when the attacker receives the NACK ack.b1, it can only use (besides its own data) ack and b1.We denote the attackers with this kind of behavior byℳ
A
P
A
T. The SDTP protocol with the second topology is specified as the parallel compositions of each honest node and the attacker A1:
(15)
SDTPA
1
(
)
=
procS
(
)
|
|
|
procA
1
(
)
|
|
|
procI
(
)
|
|
|
procD
(
)
.Again, each process is recursively called, in such a way that is equivalent to replication of many instances of the processes. For the second topologyS-I-A
2
-D, the scenarios and PAT codes are the same as in the case of the first topology S-A
1
-I-D except that the used channels at each corresponding step are changed as follows. In the first topology, A1 receives data packets from S on chSAPck, which is changed to chIAPck in the second case because now data packets come from I. Similarly, the inputs on chSAAck and chSANack are changed to chDAAack and chDANack, respectively. The outputs by A on chIAPck, chIAAck, chIANack, chSAAck, and chSANack are changed to chDAPck, chDAAck, chDANack, chIAAck, and chIANack, respectively. The attacker process procA2() describing the behavior of A2 is specified in the same way as procA1() but with different channels.The SDTP protocol with the second topology is specified as the following parallel compositions:(16)
SDTPA
2
(
)
=
UpLayer
(
)
|
|
|
procS
(
)
|
|
|
procI
(
)
|
|
|
procA
2
(
)
|
|
|
procD
(
)
.For the third topology S-A1-I-A2-D, we apply the specification of both processes A1 and A2. The SDTP protocol with the third topology is specified as the parallel compositions of each honest node and the two attackers:(17)
SDTPA
1
A
2
(
)
=
UpLayer
(
)
|
|
|
procS
(
)
|
|
|
procA
1
(
)
|
|
|
procI
(
)
|
|
|
procA
2
(
)
|
|
|
procD
(
)
.Assertions. The assertion, denoted by violategoal1, for verifying the provision of reliable delivery of packets, is as follows:#define violategoal1
(
OutBufL
=
=
0
&
&
BufI
=
=
0
&
&
num
N
A
C
K
>
0
),where the (global) variables OutBufL, BufI are the number of the occupied cache entries at the source and intermediate node, respectively, while the variable num
N
A
C
K is the number of those packets that the destination has not received and that require to be retransmitted. Hence, (OutBufL == 0) and (BufI == 0) represent that the cache of S and I are emptied, but at the same time (num
N
A
C
K > 0) means that D has not received all of the packets.The following PAT code is applied for asking if these bad states can be reached in SDTP:(B1)
#assert SDTP() reaches violategoal1p1;
(B2)
#assert SDTP() reaches violategoal1p1 with pmax.For the topologyTop2, we run PAT to model-check (B1) and get the result Not Valid. This means that, in the presence of the defined attacker(s) ℳ
A
P
A
T, SDTP cannot be corrupted such that D has not received some packets and required retransmissions but the buffers of S and I are emptied. Assertion (B2) also results in Not valid.Now let us consider the topologyTop3 that includes two attackers A
1 and A
2. We specify the bad states for SDTP (and DTSN), and we run the model checking to see if these bad states can be reached. The bad states and the verification goals can be defined in PAT’s language in the form of logical formulas and assertions, respectively.Let the number of buffer entries that are freed at nodeI after receiving an ACK/NACK message be freenum, and let the number of packets received in sequence by node D be acknum. The bad state violategoal2 specifies the state where (freenum > acknum) (see Algorithm 1).Algorithm 1
P
AT code:
#define violategoal2 (freenum > acknum)
B5. #assert SDTPsubA1subA2() reaches violategoal2
B6. #assert SDTPA1A2() reaches violategoal2We run the PAT model checker with the attacker processes (see Algorithm2).Algorithm 2
s
ubA1() =
/* A1 sends a data packet to I, without receiving any message, OR */
A1NotRcvSndPck2I()
/* After receiving a data packet on channel chSAPck */
[
]   chSAPck?seq.ear.rtx.seq1.seq2.Kack.seq3.seq4.Knack ->
(
/* A1 sends a data packet to I, OR */
A1RcvPckSndPck2I()
/* A1 forwards the packet unchanged to I */
[
]   chIAPck!seq.ear.rtx.seq1.seq2.Kack.seq3.seq4.Knack -> subA1()
)
subA2() =
/* A2 sends a data packet to I, without receiving any message, OR */
A2NotRcvSndAck2I()
/* After getting a data on channel chIAPck, A2 sends ACK with seqA2 to I */
[
]   chIAPck?seq.ear.rtx.seq1.seq2.Kack.seq3.seq4.Knack -> A2RcvPckSndAck2I()
SDTPsubA1subA2() =
UpLayer()|||
procS()||| subA1() ||| procI() ||| subA2() ||| procD()As a result, the tool returnedValid for the assertions B
5 and B
6 along with the following trace.(1)
A1 sends to I a data pckseqA2.ear.rtx with the corresponding ACK MACs: seqA2.seqA2.Katt and NACK MACs: seqA2.seqA2.Katt.
(2)
I stores this pck and forwards it (unchanged) to A2.
(3)
A2 received this packet and sends to I the ACK for seqA2:seqA2.seqA2.Katt.seqA2.Katt with the 2 keys seqA2.Katt and seqA2.Katt.
(4)
As result, I deletes all the packets stored in its buffer because the keyseqA2.Katt and the MAC seqA2.seqA2.Katt match.In summary, we get the result that both DTSN and SDTP are susceptible for this sandwich style attack scenario. The main reason for this weakness is that in SDTP the intermediate nodes do not verify the origin of the received messages; they only check if the stored ACK/NACK MACs match the received ACK/NACK keys.We also performed verification and showed other weaknesses of SDTP; the reader can find them in our technical report [11].


## 7. Conclusion

In this paper, we addressed the problem of formal and automated security verification of WSN transport protocols that may perform cryptographic operations. The verification of this class of protocols is difficult because they typically consist of complex behavioral characteristics, such as real-time, probabilistic, and cryptographic operations. To solve this problem, we proposed a probabilistic timed calculus for cryptographic protocols and demonstrated how to use this formal language for proving security or vulnerability of protocols. To the best of our knowledge, this is the first such process calculus that supports an expressive syntax and semantics, real-time, probabilistic, and cryptographic issues at the same time. Hence, it can be used to verify systems that involve these three properties. In addition, we proposed an automatic verification method, based on the PAT process analysis toolkit for this class of protocols. For demonstration purposes, we apply the proposed manual and automatic proof methods for verifying the security of DTSN and SDTP, which are two of the recently proposed WSN transport protocols, and showed that (i) DTSN is vulnerable to packet manipulation attacks, (ii) SDTP successfully patched some security holes found in DTSN, and (iii) SDTP is still vulnerable to the sandwich type attack.In the future, we focus on improving the automatic security verification for this class of systems/protocols. Currently we found that PAT is the most suitable tool because it enables us to define concurrent, nondeterministic, real-time, and probabilistic behavior of systems in a convenient way. However, in its current form it does not support (or only in a very limited way) cryptographic primitives and operations, as well as the behavior of strong (external or insider) attackers. Finally, we believe that our proposed methods can be applied for verifying other similar systems, which we will show in our follow-up work.



---

*Source: 891467-2014-03-04.xml*