# Spatiotemporal Access Model Based on Reputation for the Sensing Layer of the IoT

Authors: Yunchuan Guo; Lihua Yin; Chao Li; Junyan Qian
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Access control is a key technology in providing security in the Internet of Things (IoT). The mainstream security approach proposed for the sensing layer of the IoT concentrates only on authentication while ignoring the more general models. Unreliable communications and resource constraints make the traditional access control techniques barely meet the requirements of the sensing layer of the IoT. In this paper, we propose a model that combines space and time with reputation to control access to the information within the sensing layer of the IoT. This model is called spatiotemporal access control based on reputation (STRAC). STRAC uses a lattice-based approach to decrease the size of policy bases. To solve the problem caused by unreliable communications, we propose both nondeterministic authorizations and stochastic authorizations. To more precisely manage the reputation of nodes, we propose two new mechanisms to update the reputation of nodes. These new approaches are the authority-based update mechanism (AUM) and the election-based update mechanism (EUM). We show how the model checker UPPAAL can be used to analyze the spatiotemporal access control model of an application. Finally, we also implement a prototype system to demonstrate the efficiency of our model.


---

## Body

## 1. Introduction

As a dynamic global ubiquitous network, the Internet of Things (IoT) links physical and virtual objects by integrating sensors, smart terminals, and global positioning systems (GPSs). Authoritative institutes predicate that the IoT will create hundreds of billions of dollars in savings and productivity gains for businesses, governments, and households: Cisco believes that the IoT will create a US$14.4 trillion business opportunity in 2020 (http://www.eetimes.com/document.asp?doc_id=1263115) and Groupe Speciale Mobile Association (GSMA) predicts that, in 2020, the connected life (one part of the IoT) will bring a US$4.5-trillion global impact on people and businesses (http://www.gsma.com/newsroom/gsma-announces-the-business-impact-of-connected-devices-could-be-worth-us4-5-trillion-in-2020/).Along with the increasingly rapid development of the IoT, security issues have also become increasingly serious, especially when industrial controllers are either directly or indirectly connected to IoT. A typical example of this type of security compromise is the worm Stuxnet. Known as the first cyber-warfare weapon, Stuxnet was used to attack the Natanz uranium enrichment facility in Iran and is believed to have caused its production to drop by 15% in 2009 [1]. Obviously, security problems will cause a serious impact to the IoT.As one of the key technologies involved in providing security, access control—determiningwho is allowed access,when access is permitted, andwhere access takes place—has been widely studied [2]. Access control models, which have been widely used, include role-based access control (RBAC) and usage control (UCON) [3, 4], Internet content control (ICCON) [5], Attribute-based access control [6], and user-driven access control [7].Although these models succeed in the traditional Internet and operating systems, the IoT has raised several new and challenging issues surrounding the use of digital resources and its following critical characteristics make the above models not efficient any more. (1) Uncontrollable environments: sensors could be deployed in unattended environments, where physical nodes are more likely lost and false messages are more easily injected and transmitted. (2) Sensor-node resource constraints: computing and storage resources for sensor nodes are usually very limited, thereby severely constraining their ability to store and process the sensed data. Therefore high-weight access control models for the Internet should be revised for the sensing layer of the IoT. (3) Unreliable communications: the wireless communication adopted by the sensor nodes is often unreliable and unstable; therefore nodes may not receive the authorization in time. As a result, security in the IoT becomes more severe.To minimize these threats, we proposed spatiotemporal access control based on reputation (STRAC), which considers time, location, and reputation as key elements in deciding whether access is granted or not. STRAC uses a lattice structure to decrease the storage complexity of policy bases. To reduce the risk caused by unreliable communications, we proposed nondeterministic authorizations (i.e., pessimistic, optimistic, and trade-off authorizations) and stochastic authorization. We demonstrate that pessimistic and trade-off authorizations are secure and that optimistic and stochastic authorizations can improve the QoS. In order to correctly update the reputation of nodes, we propose two novel policies (authority-based updates and election-based updates), based on the “group” characteristics of the sensing layer, and we prove that our proposed policies are secure. Our experiments show the efficiency of our model.


## 2. Related Work

Research about access control for the sensing layer can be divided into two general categories: access control algorithms (ACAs) and access control models (ACMs). ACAs mainly focus on new node addition. New node addition algorithms prevent malicious nodes from joining the sensor network. For example, [8] uses the self-certified elliptic curve Diffie-Hellman protocol to establish a pairwise key between new sensor nodes and the controller node, which launches a two-way authentication with the new nodes. However, in this scheme, all nodes share a network-wide key. Once one node is compromised, the secret key for all nodes must be updated, thereby causing huge losses. In order to solve this problem, [9, 10] proposes a new dynamic access control protocol, which uses hash functions to reduce computations and communications between two nodes.In ACMs, much effort is spent on extending RBAC for pervasive computing. Reference [11] proposes a dynamic role-based access control (DRBAC) model, which provides context aware access control by dynamically adjusting role assignments and permission assignments based on context information. However, important features of the IoT (i.e., location and time) are not considered. In order to make RBAC more pervasive, many researchers extend RBAC by introducing time and location [12–15], where [12, 14] imposes spatiotemporal constraints on user-role assignments and permission assignments, and [15] introduces the concept of spatiotemporal zones and allows spatiotemporal constraints to be specified with prerequisite constraints. In addition, [16] adopts RBAC-based (role-based access control) authorization method using the thing’s particular role(s) and application(s) in the associated IoT network. Reference [17] designs a capability-based access control delegation model for the federated IoT network. Reference [18] focuses on a minimal use of computation, energy, and storage resources at wireless sensors and proposes a novel access control solution for wireless network services in Internet of Things scenarios.Although RBAC is often extended for pervasive computing, these extensions cannot be widely adopted for the sensing layer of the IoT because of the PSPACE-completeness [19] of RBAC.Other spatiotemporal models that are not based on RBAC are also proposed. Reference [20] uses composition algebra to regulate access to patient data and balances the rigorous nature of traditional access control systems with the “delivery of care comes first” principle. Recently, reputation has been incorporated into models of access control for cyber-physical systems as in [21, 22]; however, these particular models do not deal with the loss of nodes.Our work differs from the above solutions in several ways. First, we consider reputation, rather than roles, as a fundamental factor of access control for the sensing layer of the IoT, because the behavior of selfish nodes can be directly modeled by reputation but not easily modeled by roles. Such a change is nontrivial. If a node becomes selfish, then we are only required to assign a lower reputation to it. Therefore, reputation is more suitable than roles in controlling access to the sensing layer.Second, the existing access control models do not efficiently handle the problem caused by unreliable communications. We propose nondeterministic authorizations and stochastic authorizations to solve this problem. Our method reduces the security risks of security-critical systems when failing to receive the key authorization instructions.Finally, the existing models for the IoT do not consider the group characteristics of the sensing layer. In our work, node’s reputation is cooperatively updated based on the group characteristics, thereby simplifying the reputation-update process.


## 3. Formalizing Time, Space, and Reputation

In order to construct a spatiotemporal access model based on reputation, we first formally define time, space, and reputation.


### 3.1. Reputation Description

Due to the limitations of storage and the computing resources, some nodes do not cooperate with others and demonstrateselfishness. In order to obtain more benefits, some nodes may attack others and demonstratemisbehavior. Because reputation (the opinion of one entity regarding another) can reflect both selfishness and misbehavior in interactions, it is adopted in modeling the behavior of nodes in our study.Generally, from the aspect of reputation obtainment, reputation includes direct reputation (DR) and indirect reputation (IR), where DR and IR, respectively, refer reputation estimated by estimators based on their first-hand and second-hand experiences. From the aspect of goal, individual reputation should be distinguished with group reputation. Reference [23] surveys notions of reputation. In this paper, we only focus on individual and direct reputation, as follows.We define reputationR
E
P to have different ratings, and thus it can be denoted by a finite set; that is, R
E
P
=
{
r
e
p
1
,
…
,
r
e
p
n
}, where r
e
p
i is a reputation rating (
1
≤
i
n
). Given any r
e
p
x and r
e
p
y in R
E
P, they are mutually comparable, that is, r
e
p
x
⪯
r
e
p
y or r
e
p
y
⪯
r
e
p
x. Thus, R
E
P is a total order set. For a given node, its reputation is formed and ≤ updated through direct observations of its behavior and through feedback provided by other nodes. In this paper, we concentrate on general access models and do not discuss the methods of computing reputation in detail.


### 3.2. Time Description

In order to describe operations that can only be executed within a given time period, the notion of a calendar is adopted [24, 25]. A calendar consists of a countable set of contiguous intervals, for example, years, months, and days. Because two calendars can have different granularities, a subcalendar relationship can be established among them. That is, given two calendars c
1 and, is a subcalendar of (written as c
1
⊑
c
2), if and only if there exists a natural number, such that c
2
=
i
×
c
1. For example, days are a representative subcalendar of months. Obviously, ⊑ is a partial order relation. A calendar base C
B represents a set of calendars and generally changes with different contexts. For example, if a school curriculum is comprised of years, semesters, and weeks, then its C
B is {years, semesters, weeks}.Definition 1 (calendar time).
GivenC
B
=
{
c
1
,
…
,
c
n
}, calendar time c
t is defined as c
t
=
∑
i
=
1
n
n
i
·
c
i, where, n
i
∈
N and for all 2
≤
i
≤
n, one has c
i
⊑
c
i
-
1.LetC
T be a set of calendar times. Generally, any two calendar times are always comparable. That is, for any c
t
x and c
t
y in C
T, one can have c
t
x
≤
c
t
y or c
t
y
≤
c
t
x (≤ is the total order relation). In the IoT, different types of time constraints exist, such as the earliest access time (e
a
t), the latest access time (l
f
t), the earliest finish time, and the latest finish time. In our study, e
a
t and l
f
t are adopted.Definition 2 (time constraints).
Time constraintT
C
⊆
C
T
×
C
T is a set of two-dimensional vectors of calendar times, where the first dimension and the second dimension represent e
a
t and l
f
t, respectively. Time constraints must satisfy the following condition: for any (
c
t
1
,
c
t
2
)
∈
T
C, c
t
1
≤
c
t
2.Example 3.
GivenT
C
=
{
(
c
t
11
,
c
t
12
), (
c
t
21
,
c
t
22
)
}, and an event satisfies T
C, if access time (from start time to end time) of the event falls entirely within the time range from c
t
11 to c
t
12, or within the time range from c
t
21 to c
t
22.
A time constraint with overlapping ranges{
(
1,3
)
,
(
2
,
4
)
} can be reduced to {
(
1
,
4
)
}, based on the following definition.Definition 4 (simplest time constraints).
A time constraintT
C is the simplest, if for any (
c
t
11
,
c
t
12
) and (
c
t
21
,
c
t
22
)
∈
T
C, min
⁡
{
c
t
12, c
t
22
}
<
max
⁡
{
c
t
11, c
t
21
}.
Henceforth, one assumes that time constraints are always the simplest. Given two time constraintst
c
1 and t
c
2 shown in Figure 1, where (1) c
t
11—e
a
t of t
c
1—is greater than or equal to that of t
c
2 and (2) c
t
12—l
f
t of t
c
1—is less than or equal to that of t
c
2. If an event satisfies t
c
1, then it will satisfy t
c
2; this means that t
c
1 is stricter than t
c
2. Thus, one has Definition 5.Figure 1
Time constraints.Definition 5 (order relation⪯ on T
C).
Givent
c
1 and t
c
2 in T
C, t
c
2
⪯
t
c
1 (meaning that t
c
1 is stricter than t
c
2), if and only if c
t
21
≤
c
t
11 and c
t
12
≤
c
t
22, where t
c
1
=
(
c
t
11
,
c
t
12
) and t
c
2
=
(
c
t
21
,
c
t
22
).Proposition 6.
⪯ on T
C is a partial order.Definition 7 (order relation⪯ on 2
T
C).
Given anyT
C
1 and T
C
2, T
C
1
⪯
T
C
2  (meaning that T
C
2 is stricter than T
C
1), if and only if, for any t
c
x
∈
T
C
2, there exists t
c
y
∈
T
C
1 with t
c
y
⪯
t
c
x.Proposition 8.
⪯ on 2
T
C is a partial order.In the real environment, time constraints can be constructed by way of union or intersection of some constraints. One defines the intersection and the union as follows.Definition 9 (intersection).
Intersection⊙
:
2
T
C
×
2
T
C
→
2
T
C is a function from 2
T
C
×
2
T
C to 2
T
C defined as
(1)
T
C
1
⊙
T
C
2
=
{
t
c
x
⊙
T
C
t
c
y
∣
t
c
x
∈
T
C
1
∧
t
c
y
∈
T
C
2
}
,
where
(2)
t
c
x
⊙
T
C
t
c
y
=
{
(
x
,
y
)
if
x
≤
y
⌀
otherwise
,
t
c
x
=
(
c
t
x
1
,
c
t
x
2
)
,
t
c
y
=
(
c
t
y
1
,
c
t
y
2
)
,
x
=
max
⁡
(
c
t
x
1
,
c
t
y
1
)
,
y
=
min
⁡
(
c
t
x
2
,
c
t
y
2
)
.Definition 10 (union).
Union⊕
:
2
T
C
×
2
T
C
→
2
T
C is a function from 2
T
C
×
2
T
C to 2
T
C defined as T
C
1
⊕
T
C
2
=
{
t
c
∣
t
c
∈
T
C
1
∨
t
c
∈
T
C
2
}.
Because the time constraints obtained by computingT
C
1
⊕
T
C
2 are not always the simplest, one reduces them to the simplest form as follows. Given a time constraint T
C, if there exists (
c
t
11, c
t
12
), (
c
t
21, c
t
22
)
∈
T
C with max
⁡
{
c
t
11, c
t
21
}
<
min
⁡
{
c
t
12, c
t
22
}, then both (
c
t
11, c
t
12
) and (c
t
21, c
t
22) are deleted from T
C and (
min
⁡
{
c
t
11, c
t
2
l
t
1
1
}, max
⁡
{
c
t
12, c
t
22
}
) are inserted into T
C. Obviously, the original T
C is semantically equivalent to the modified T
C. Henceforth, one assumes that the intersection and the union of time constraints are always the simplest.Proposition 11.
Given anyt
c
1 and t
c
2 in T
C, if T
C is closed under ⊙ and ⊕, then t
c
1
⊙
t
c
2 and t
c
1
⊕
t
c
2 are the supremum and the infimum of {
t
c
1
,
t
c
2
}, respectively.
The definitions above concentrate on physical time. However, in some cases, logical time (such as work time or class time) is more important.Definition 12.
t
i
m
e
A
s
s
i
g
n
e
d: L
T
→
2
T
C
/
{
⌀
} is a function mapping L
T to the nonempty power set of T
C, where L
T
=
{
l
t
1
,
…
,
l
t
n
} represents a set of names of logical time.Definition 13 (order relation⪯ on L
T).
Given anyl
t
1 and l
t
2 in L
T, l
t
1
⪯
l
t
2 if and only if t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
1
)
⪯
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
2
).Proposition 14.
⪯ on L
T is a partial order.Definition 15 (intersection onL
T).
(Here, we do not differentiate the⊙ of Definition 9 from the ⊙ of Definition 15, because they are easily distinguished; Similarly, we also do not differentiate ⊕ of Definition 10 and ⊕ of Definition 16). ⊙
:
L
T
×
L
T
→
L
T is an intersection function mapping L
T
×
L
T to L
T, defined as l
t
1
⊙
l
t
2
=
l
t, where t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
)
=
{
x
⊙
y
∣
x
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
1
) and y
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
2
)
}.Definition 16 (union onL
T).
⊕
:
L
T
×
L
T
→
L
T is a union function mapping L
T
×
L
T to L
T, defined as l
t
1, where
(3)
⋃
x
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
1
)
y
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
2
)
x
⊕
y
.Proposition 17.
For anyl
t
1 and l
t
2 in L
T, if L
T is closed under ⊙ and ⊕, then l
t
1
⊙
l
t
2 and l
t
1
⊕
l
t
2 are the supremum and the infimum of {
l
t
1
,
l
t
2
}, respectively.
Proof that the supremum of{
l
t
1
,
l
t
2
} is l
t
1
⊙
l
t
2: from Definition 15, we have l
t
1
⪯
l
t
1
⊙
l
t
2 and l
t
2
⪯
⊙
l
t
2; therefore, l
t
1
⊙
l
t
2 is the upper boundary of {
l
t
1
,
l
t
2
}. Next, we prove that l
t
1
⊙
l
t
2 is the least element of the upper boundary of {
l
t
1
,
l
t
2
}. Let l
t
1
⪯
l
t and l
t
2
⪯
l
t; then, for any x
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
), there exists y
1
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
1
) and y
2
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
2
), such that y
1
⪯
x and y
2
⪯
x. According to Proposition 11, y
1
⊙
y
2
⪯
x. According to Definition 15, l
t
1
⊙
l
t
2
⪯
l
t; therefore, so l
t
1
⊙
l
t
2 is the supremum of {
l
t
1
,
l
t
2
}.


### 3.3. Location Description

In the IoT, physical locations are often distinguished from logical locations. Physical locations are divided into two classes: hierarchical (topological, descriptive, or symbolic), such as a room, and Cartesian (coordinate, metric, or geometric), such as GPS position [12, 14, 26]. Logical locations represent the boundaries of the logical space that corresponds to the physical space.LetP
L
O
C
=
{
p
l
o
c
1,…,p
l
o
c
n
} be a set of physical locations, where p
l
o
c
i  (
1
≤
i
≤
n
) is a specific physical location, such as a 50 × 50 unit square area. Let L
L
O
C
=
{
l
l
o
c
1,…,l
l
o
c
n
} represent the set of logical locations, where each in L
L
O
C denotes the notion for one or more physical locations. Generally, relations between physical and logical locations are illustrated as a many-to-many map, denoted by L
P
⊆
P
L
O
C
×
L
L
O
C.Definition 18.
A functionL
l
o
c
T
o
P
l
o
c: L
L
O
C
→
2
P
L
O
C maps L
L
O
C to the power set of P
L
O
C, returning all physical locations assigned to a given logical location. In other words, c
(
l
l
o
c
)
=
{
p
l
o
c
∣
(
p
l
o
c
,
l
l
o
c
)
∈
L
P
}.Definition 19.
A functionP
l
o
c
T
o
L
l
o
c: P
L
O
C
→
2
L
L
O
C maps P
L
O
C to the power set of L
L
O
C, returning all assigned logical locations of a given physical location. In other words, c
(
p
l
o
c
)
=
{
l
l
o
c
∣
(
p
l
o
c
,
l
l
o
c
)
∈
L
P
}.
Given two logical locations, a containment relation may exist. This is defined as follows.Definition 20.
A logical locationl
l
o
c
i is contained in another logical location l
l
o
c
j, written as l
l
o
c
i
⊆
l
l
o
c
j, if and only if L
l
o
c
T
o
P
l
o
c
(
l
l
o
c
i
)
⊆
L
l
o
c
T
o
P
l
o
c
(
l
l
o
c
j
).Generally, physical locations of a given logical location are unchanged within a period; therefore, for simplicity, a logical location is used to denote its corresponding physical location. Similarly, one can define intersection∩ and union ∪ based on logical locations, but one does not discuss them.


## 3.1. Reputation Description

Due to the limitations of storage and the computing resources, some nodes do not cooperate with others and demonstrateselfishness. In order to obtain more benefits, some nodes may attack others and demonstratemisbehavior. Because reputation (the opinion of one entity regarding another) can reflect both selfishness and misbehavior in interactions, it is adopted in modeling the behavior of nodes in our study.Generally, from the aspect of reputation obtainment, reputation includes direct reputation (DR) and indirect reputation (IR), where DR and IR, respectively, refer reputation estimated by estimators based on their first-hand and second-hand experiences. From the aspect of goal, individual reputation should be distinguished with group reputation. Reference [23] surveys notions of reputation. In this paper, we only focus on individual and direct reputation, as follows.We define reputationR
E
P to have different ratings, and thus it can be denoted by a finite set; that is, R
E
P
=
{
r
e
p
1
,
…
,
r
e
p
n
}, where r
e
p
i is a reputation rating (
1
≤
i
n
). Given any r
e
p
x and r
e
p
y in R
E
P, they are mutually comparable, that is, r
e
p
x
⪯
r
e
p
y or r
e
p
y
⪯
r
e
p
x. Thus, R
E
P is a total order set. For a given node, its reputation is formed and ≤ updated through direct observations of its behavior and through feedback provided by other nodes. In this paper, we concentrate on general access models and do not discuss the methods of computing reputation in detail.


## 3.2. Time Description

In order to describe operations that can only be executed within a given time period, the notion of a calendar is adopted [24, 25]. A calendar consists of a countable set of contiguous intervals, for example, years, months, and days. Because two calendars can have different granularities, a subcalendar relationship can be established among them. That is, given two calendars c
1 and, is a subcalendar of (written as c
1
⊑
c
2), if and only if there exists a natural number, such that c
2
=
i
×
c
1. For example, days are a representative subcalendar of months. Obviously, ⊑ is a partial order relation. A calendar base C
B represents a set of calendars and generally changes with different contexts. For example, if a school curriculum is comprised of years, semesters, and weeks, then its C
B is {years, semesters, weeks}.Definition 1 (calendar time).
GivenC
B
=
{
c
1
,
…
,
c
n
}, calendar time c
t is defined as c
t
=
∑
i
=
1
n
n
i
·
c
i, where, n
i
∈
N and for all 2
≤
i
≤
n, one has c
i
⊑
c
i
-
1.LetC
T be a set of calendar times. Generally, any two calendar times are always comparable. That is, for any c
t
x and c
t
y in C
T, one can have c
t
x
≤
c
t
y or c
t
y
≤
c
t
x (≤ is the total order relation). In the IoT, different types of time constraints exist, such as the earliest access time (e
a
t), the latest access time (l
f
t), the earliest finish time, and the latest finish time. In our study, e
a
t and l
f
t are adopted.Definition 2 (time constraints).
Time constraintT
C
⊆
C
T
×
C
T is a set of two-dimensional vectors of calendar times, where the first dimension and the second dimension represent e
a
t and l
f
t, respectively. Time constraints must satisfy the following condition: for any (
c
t
1
,
c
t
2
)
∈
T
C, c
t
1
≤
c
t
2.Example 3.
GivenT
C
=
{
(
c
t
11
,
c
t
12
), (
c
t
21
,
c
t
22
)
}, and an event satisfies T
C, if access time (from start time to end time) of the event falls entirely within the time range from c
t
11 to c
t
12, or within the time range from c
t
21 to c
t
22.
A time constraint with overlapping ranges{
(
1,3
)
,
(
2
,
4
)
} can be reduced to {
(
1
,
4
)
}, based on the following definition.Definition 4 (simplest time constraints).
A time constraintT
C is the simplest, if for any (
c
t
11
,
c
t
12
) and (
c
t
21
,
c
t
22
)
∈
T
C, min
⁡
{
c
t
12, c
t
22
}
<
max
⁡
{
c
t
11, c
t
21
}.
Henceforth, one assumes that time constraints are always the simplest. Given two time constraintst
c
1 and t
c
2 shown in Figure 1, where (1) c
t
11—e
a
t of t
c
1—is greater than or equal to that of t
c
2 and (2) c
t
12—l
f
t of t
c
1—is less than or equal to that of t
c
2. If an event satisfies t
c
1, then it will satisfy t
c
2; this means that t
c
1 is stricter than t
c
2. Thus, one has Definition 5.Figure 1
Time constraints.Definition 5 (order relation⪯ on T
C).
Givent
c
1 and t
c
2 in T
C, t
c
2
⪯
t
c
1 (meaning that t
c
1 is stricter than t
c
2), if and only if c
t
21
≤
c
t
11 and c
t
12
≤
c
t
22, where t
c
1
=
(
c
t
11
,
c
t
12
) and t
c
2
=
(
c
t
21
,
c
t
22
).Proposition 6.
⪯ on T
C is a partial order.Definition 7 (order relation⪯ on 2
T
C).
Given anyT
C
1 and T
C
2, T
C
1
⪯
T
C
2  (meaning that T
C
2 is stricter than T
C
1), if and only if, for any t
c
x
∈
T
C
2, there exists t
c
y
∈
T
C
1 with t
c
y
⪯
t
c
x.Proposition 8.
⪯ on 2
T
C is a partial order.In the real environment, time constraints can be constructed by way of union or intersection of some constraints. One defines the intersection and the union as follows.Definition 9 (intersection).
Intersection⊙
:
2
T
C
×
2
T
C
→
2
T
C is a function from 2
T
C
×
2
T
C to 2
T
C defined as
(1)
T
C
1
⊙
T
C
2
=
{
t
c
x
⊙
T
C
t
c
y
∣
t
c
x
∈
T
C
1
∧
t
c
y
∈
T
C
2
}
,
where
(2)
t
c
x
⊙
T
C
t
c
y
=
{
(
x
,
y
)
if
x
≤
y
⌀
otherwise
,
t
c
x
=
(
c
t
x
1
,
c
t
x
2
)
,
t
c
y
=
(
c
t
y
1
,
c
t
y
2
)
,
x
=
max
⁡
(
c
t
x
1
,
c
t
y
1
)
,
y
=
min
⁡
(
c
t
x
2
,
c
t
y
2
)
.Definition 10 (union).
Union⊕
:
2
T
C
×
2
T
C
→
2
T
C is a function from 2
T
C
×
2
T
C to 2
T
C defined as T
C
1
⊕
T
C
2
=
{
t
c
∣
t
c
∈
T
C
1
∨
t
c
∈
T
C
2
}.
Because the time constraints obtained by computingT
C
1
⊕
T
C
2 are not always the simplest, one reduces them to the simplest form as follows. Given a time constraint T
C, if there exists (
c
t
11, c
t
12
), (
c
t
21, c
t
22
)
∈
T
C with max
⁡
{
c
t
11, c
t
21
}
<
min
⁡
{
c
t
12, c
t
22
}, then both (
c
t
11, c
t
12
) and (c
t
21, c
t
22) are deleted from T
C and (
min
⁡
{
c
t
11, c
t
2
l
t
1
1
}, max
⁡
{
c
t
12, c
t
22
}
) are inserted into T
C. Obviously, the original T
C is semantically equivalent to the modified T
C. Henceforth, one assumes that the intersection and the union of time constraints are always the simplest.Proposition 11.
Given anyt
c
1 and t
c
2 in T
C, if T
C is closed under ⊙ and ⊕, then t
c
1
⊙
t
c
2 and t
c
1
⊕
t
c
2 are the supremum and the infimum of {
t
c
1
,
t
c
2
}, respectively.
The definitions above concentrate on physical time. However, in some cases, logical time (such as work time or class time) is more important.Definition 12.
t
i
m
e
A
s
s
i
g
n
e
d: L
T
→
2
T
C
/
{
⌀
} is a function mapping L
T to the nonempty power set of T
C, where L
T
=
{
l
t
1
,
…
,
l
t
n
} represents a set of names of logical time.Definition 13 (order relation⪯ on L
T).
Given anyl
t
1 and l
t
2 in L
T, l
t
1
⪯
l
t
2 if and only if t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
1
)
⪯
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
2
).Proposition 14.
⪯ on L
T is a partial order.Definition 15 (intersection onL
T).
(Here, we do not differentiate the⊙ of Definition 9 from the ⊙ of Definition 15, because they are easily distinguished; Similarly, we also do not differentiate ⊕ of Definition 10 and ⊕ of Definition 16). ⊙
:
L
T
×
L
T
→
L
T is an intersection function mapping L
T
×
L
T to L
T, defined as l
t
1
⊙
l
t
2
=
l
t, where t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
)
=
{
x
⊙
y
∣
x
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
1
) and y
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
2
)
}.Definition 16 (union onL
T).
⊕
:
L
T
×
L
T
→
L
T is a union function mapping L
T
×
L
T to L
T, defined as l
t
1, where
(3)
⋃
x
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
1
)
y
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
2
)
x
⊕
y
.Proposition 17.
For anyl
t
1 and l
t
2 in L
T, if L
T is closed under ⊙ and ⊕, then l
t
1
⊙
l
t
2 and l
t
1
⊕
l
t
2 are the supremum and the infimum of {
l
t
1
,
l
t
2
}, respectively.
Proof that the supremum of{
l
t
1
,
l
t
2
} is l
t
1
⊙
l
t
2: from Definition 15, we have l
t
1
⪯
l
t
1
⊙
l
t
2 and l
t
2
⪯
⊙
l
t
2; therefore, l
t
1
⊙
l
t
2 is the upper boundary of {
l
t
1
,
l
t
2
}. Next, we prove that l
t
1
⊙
l
t
2 is the least element of the upper boundary of {
l
t
1
,
l
t
2
}. Let l
t
1
⪯
l
t and l
t
2
⪯
l
t; then, for any x
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
), there exists y
1
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
1
) and y
2
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
2
), such that y
1
⪯
x and y
2
⪯
x. According to Proposition 11, y
1
⊙
y
2
⪯
x. According to Definition 15, l
t
1
⊙
l
t
2
⪯
l
t; therefore, so l
t
1
⊙
l
t
2 is the supremum of {
l
t
1
,
l
t
2
}.


## 3.3. Location Description

In the IoT, physical locations are often distinguished from logical locations. Physical locations are divided into two classes: hierarchical (topological, descriptive, or symbolic), such as a room, and Cartesian (coordinate, metric, or geometric), such as GPS position [12, 14, 26]. Logical locations represent the boundaries of the logical space that corresponds to the physical space.LetP
L
O
C
=
{
p
l
o
c
1,…,p
l
o
c
n
} be a set of physical locations, where p
l
o
c
i  (
1
≤
i
≤
n
) is a specific physical location, such as a 50 × 50 unit square area. Let L
L
O
C
=
{
l
l
o
c
1,…,l
l
o
c
n
} represent the set of logical locations, where each in L
L
O
C denotes the notion for one or more physical locations. Generally, relations between physical and logical locations are illustrated as a many-to-many map, denoted by L
P
⊆
P
L
O
C
×
L
L
O
C.Definition 18.
A functionL
l
o
c
T
o
P
l
o
c: L
L
O
C
→
2
P
L
O
C maps L
L
O
C to the power set of P
L
O
C, returning all physical locations assigned to a given logical location. In other words, c
(
l
l
o
c
)
=
{
p
l
o
c
∣
(
p
l
o
c
,
l
l
o
c
)
∈
L
P
}.Definition 19.
A functionP
l
o
c
T
o
L
l
o
c: P
L
O
C
→
2
L
L
O
C maps P
L
O
C to the power set of L
L
O
C, returning all assigned logical locations of a given physical location. In other words, c
(
p
l
o
c
)
=
{
l
l
o
c
∣
(
p
l
o
c
,
l
l
o
c
)
∈
L
P
}.
Given two logical locations, a containment relation may exist. This is defined as follows.Definition 20.
A logical locationl
l
o
c
i is contained in another logical location l
l
o
c
j, written as l
l
o
c
i
⊆
l
l
o
c
j, if and only if L
l
o
c
T
o
P
l
o
c
(
l
l
o
c
i
)
⊆
L
l
o
c
T
o
P
l
o
c
(
l
l
o
c
j
).Generally, physical locations of a given logical location are unchanged within a period; therefore, for simplicity, a logical location is used to denote its corresponding physical location. Similarly, one can define intersection∩ and union ∪ based on logical locations, but one does not discuss them.


## 4. STRAC Framework

First, we provide an overview of the framework of our model. As shown in Figure2, STRAC consists of two core components: the access request component (ARC) and the reference monitor component (RMC). The ARC of a node creates an access request, which has two forms: the first form includes five elements: the node’s I
D, the accessed object o, the expected operation o
p to be performed on o, the node’s current location p
l
o
c (generally, a node’s location information may come from GPSs or wifi), and the node’s reputation r
e
p; the second form includes three elements: the node’s I
D, the accessed object o, the expected operation o
p to be performed on o, and the node’s current location p
l
o
c. In the first form, each node locally stores its reputation and physical location; in the second form, the reputation of each node is centrally stored in PEP (see the next paragraph for PEP) and its physical location is tracked by PEP.Figure 2
Framework of STRAC.RMC includes two modules: policy enforcement point (PEP) and policy decision point (PDP). The PEP module receives the user request, consults with the PDP module about the user authorization, and ensures that all access requests go through the PDP module. PEP is comprised of two submodules (access request extractor (ARE) and authorization token requester (ATR)) and two access tables which map the current time and physical locations to the logical time and the logical location, respectively (the two tables are called ID-RTL table in Figure2). When the PEP module receives an access request from a user, ARE executes two steps: (1) it accepts the request and extracts the encapsulated location, I
D, o, r
e
p, o
p, and p
l
o
c if the first type of access requests is adopted; it extracts I
D, o, and p
l
o
c if the second type is used, and (2) it queries the access database and returns the I
D’s logical location l
l
o
c and logical time l
t (in addition to the three elements, it returns the reputation of node I
D if the second type of access requests is used). ATR encapsulatesthis information (
r
e
p, l
t, l
l
o
c, o
p, and o
) and sends it to the PDPmodule to request an authorization token (AT). Once this request is granted, an AT will be returned, and the user can access the target resources using this AT. PEP maintains a list of users’ ATs, and this list is updated at a specified interval. AT will be revoked when the user deactivates the task or when the location and time associated with the use are out of the allowed scope.The PDP module, comprised of one submodule (Authorization Token Granter (ATG)) and one policy base, makes the authorization decision based on a set of rules or policies. When PDP receives an AT request, it extracts the information(
r
e
p, l
t, l
l
o
c, o
p, and o
) from the request and consults the security policies. If the polices denote that a node with reputation r
e
p at the time period l
t in the location l
l
o
c has the right to perform the operation o
p on the target o, then ATG grants A
T to access request.The source of authority (SOA) is administrator or a group of administrators, who define the policies. SOA can also update the policy at runtime if necessary. In some cases, group nodes may also cooperatively update the node’s reputation and make access decisions based on stochastic information (stochastic authorization in Figure2).Our model can be implemented with two alternative modes: ACI and AII. ACI focuses on authorization when complete information is available, while AII deals with authorization having only incomplete information. The precondition for ACI is that decision makers always can obtain authorization information in time. In other word, ACI requires a stable communication. Contrarily, this precondition is not necessary in AII. AII is very useful because unstable communications in the IoT are considered to be persuasive phenomenon. Generally, while in the ACI mode both PEP and PDP are mounted in the gateway and ARC is integrated into terminal nodes. Contrarily, to implement the AII mode, ARC and two lightweight modules, PEP and PDP, are mounted into terminal nodes.


## 5. STRAC Model

### 5.1. Basic Components of STRAC

The basic STRAC model is comprised of the following components:I
D
=
{
i
d
1,…,i
d
n
} is a set of node IDs;
R
E
P
=
{
r
e
p
1,…,r
e
p
n
} is a set of reputations; for example, R
E
P
=
{
g
o
l
d
r
e
p
u
t
a
t
i
o
n, s
i
l
v
e
r
r
e
p
u
t
a
t
i
o
n
};
L
T
=
{
l
t
1,…,l
t
n
} is a set of logical time constraints;
L
L
O
C
=
{
l
l
o
c
1,…,l
l
o
c
n
} is a set of logical locations; for example, L
L
O
C
=
{
a
d
m
i
n
i
s
t
r
a
t
o
r
r
o
o
m, m
e
e
t
r
o
o
m
};
O
P
=
{
o
p
1,…,o
p
n
} is a set of operations; for example, OP
=
{
o
p
e
n, c
l
o
s
e
};
O
=
{
o
1,…,o
n
} is a set of target objects; for example, O
=
{
T
V, M
i
c
r
o
w
a
v
e
};
P
E
R
M
⊆
O
P
×
O is a set of permissions, where (
o
p,o
)
∈
P
E
R
M means that o
p is performed on o. For example, if P
E
R
M
=
{
(
o
p
e
n, T
V
)
} is assigned to device i
d, then the device owns the permission to open T
V;
A
c
c
Z
o
n
e
⊆
R
E
P
×
L
T
×
L
L
O
C is a set of a
c
c
e
s
s
z
o
n
e
s, where each access zone is a triple (
r
e
p, l
t, l
l
o
c
);
P
A
⊆
P
E
R
M
×
A
c
c
Z
o
n
e is a many-to-many map of connections between permissions and access zones. (
x, y
)
∈
P
A means that any node with y has permission x. For example, (
(
o
p
,
o
)
,
(
r
e
p
1
,
l
t
1
,
l
l
o
c
1
)
)
∈
P
A denotes that a node satisfying the constraint of l
t
1 with reputation r
e
p
1 at location l
l
o
c
1 can execute operation o
p on object o;
A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d: P
E
R
M
→
2
A
c
c
Z
o
n
e assigns a permission level to access zones, where A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
p
e
r
m
)
=
{
A
c
c
Z
o
n
e
∣
(
p
e
r
m, A
c
c
Z
o
n
e
)
∈
P
A
}; that is, given a p
e
r
m, function A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d returns all access zones which the p
e
r
m can access. For example, if P
A
=
{
(
(
o
p
1, o
2
), (
r
e
p
2, l
t
1, l
l
o
c
2
)
), (
(
o
p
2, o
1
), (
r
e
p
2, l
t
2, l
l
o
c
2
)
), (
(
o
p
1, o
2
), (
r
e
p
2, l
t
3, l
l
o
c
1
)
)
}, then A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
1, o
2
)
)
=
{
(
r
e
p
2, l
t
1, l
l
o
c
2
), (
r
e
p
2, l
t
3, l
l
o
c
1
)
};
p
e
r
m
A
s
s
i
g
n
e
d: A
c
c
Z
o
n
e
→
2
P
E
R
M assigns an access zone to permissions, where p
e
r
m
A
s
s
i
g
n
e
d
(
A
c
c
Z
o
n
e
)
=
{
p
e
r
m
∣
(
p
e
r
m, A
c
c
Z
o
n
e
)
∈
P
A
}; that is, given an a
c
c
z
o
n
e, function p
e
r
m
A
s
s
i
g
n
e
d returns all permissions by which the a
c
c
z
o
n
e can be accessed. For example, in the example of A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d, p
e
r
m
A
s
s
i
g
n
e
d
(
(
r
e
p
2, l
t
1, l
l
o
c
2
)
)
=
{
(
o
p
1, o
2
), (
o
p
2, o
1
)
};
A
c
c
e
s
s
R
e
q
u
e
s
t: I
D
×
O
P
×
O
→
{
t
r
u
e, f
a
l
s
e
} is a predicate; if it returns true, then node i
d requests permission to execute o
p on o. Recall that the storage of r
e
p is either distributed or centralized. To model the two cases, we remove r
e
p from access requests; for simplicity, we also remove the ID’s location and reputation from access requests and encapsulate the three elements into the function C
u
r
r
e
n
t
R
T
L (we will discuss it next);
A
l
l
o
w
R
e
q
u
e
s
t: I
D
×
O
P
×
O
→
{
t
r
u
e, f
a
l
s
e
} is a predicate; if it returns true, then node i
d is allowed to o
p on o;
D
e
n
y
R
e
q
u
e
s
t: I
D
×
O
P
×
O
→
{
t
r
u
e, f
a
l
s
e
} is a predicate; if it returns true, then node i
d is not allowed to execute o
p on o;
R
e
v
o
k
e
R
e
q
u
e
s
t: I
D
×
O
P
×
O
→
{
t
r
u
e, f
a
l
s
e
} is a predicate; if it returns true, then the permission that node i
d executes o
p on o will be revoked;
C
u
r
r
e
n
t
R
T
L: I
D
→
R
E
P
×
C
T
×
2
L
L
O
C is a function and returns i
d’s current reputation, its logical time, and logical locations (a node may be located in many different logical locations).In order to return the logical locations of a node, its physical location must be first obtained, and then its logical locations can be computed using the functionP
l
o
c
T
o
L
l
o
c. Because a physical location can be associated with many logical areas, C
u
r
r
e
n
t
R
T
L returns a set of logical locations.


### 5.2. Mechanism for Authorization and Revocation

Intuitively, if a node located in an appropriate area has an acceptable reputation and satisfies the given time constraints, its requests to execute some operations on an object should be allowed. In order to avoid using too many symbols, we overload the notation∈, as follows.Giveni
d, o
p, and o, let C
u
r
r
e
n
t
R
T
L
(
i
d
)
=
{
r
e
p
i
d
,
c
t
i
d
,
{
l
l
o
c
i
d
1
,
…
,
l
l
o
c
i
d
n
}
} and A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
,
o
)
) = {
(
r
e
p
1
,
l
t
1
,
l
l
o
c
1
)
,
…
,
(
r
e
p
n
,
l
t
n
,
l
l
o
c
n
)
}; C
u
r
r
e
n
t
R
T
L
(
i
d
)
∈
A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
,
o
)
) if and only if there exists (
r
e
p
i
,
l
t
i
,
l
l
o
c
i
)
∈
A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
,
o
)
) with r
e
p
i
d
=
r
e
p
i,  c
t
i
d
∈
l
t
i (c
t
i
d
∈
l
t
i if and only if (
c
t
1
,
c
t
2
)
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
i
) holds, where c
t
1
≤
c
t
i
d
≤
c
t
2) and l
l
o
c
i
∈
{
l
l
o
c
i
d
1
,
…
,
l
l
o
c
i
d
n
}. The authorization schemes are as follows:(1)
A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
∧
C
u
r
r
e
n
t
R
T
L
(
i
d
)
∈
A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
,
o
)
)
→
A
l
l
o
w
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
(2)
A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
∧
C
u
r
r
e
n
t
R
T
L
(
i
d
)
∉
A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
,
o
)
)
→
D
e
n
y
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
(3)
A
l
l
o
w
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
∧
C
u
r
r
e
n
t
R
T
L
(
i
d
)
∉
A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
,
o
)
)
→
R
e
v
o
k
e
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
).Formulas (1) and (2) show the following: (1) if the nodei
d requests permission to execute o
p on o, and if C
u
r
r
e
n
t
R
T
L
(
i
d
) (the current reputation, access time, and location of i
d) satisfies the conditions to execute o
p on o, then the request will be allowed; (2) if the node i
d requests permission to execute o
p on o, but C
u
r
r
e
n
t
R
T
L
(
i
d
) does not satisfy the conditions to execute o
p on o, then the request will be denied. Formula (3) suggests that if node i
d has received the permission of executing o
p on o and C
u
r
r
e
n
t
R
T
L
(
i
d
) no longer satisfies the conditions to execute o
p on o longer, the permission will be revoked.


## 5.1. Basic Components of STRAC

The basic STRAC model is comprised of the following components:I
D
=
{
i
d
1,…,i
d
n
} is a set of node IDs;
R
E
P
=
{
r
e
p
1,…,r
e
p
n
} is a set of reputations; for example, R
E
P
=
{
g
o
l
d
r
e
p
u
t
a
t
i
o
n, s
i
l
v
e
r
r
e
p
u
t
a
t
i
o
n
};
L
T
=
{
l
t
1,…,l
t
n
} is a set of logical time constraints;
L
L
O
C
=
{
l
l
o
c
1,…,l
l
o
c
n
} is a set of logical locations; for example, L
L
O
C
=
{
a
d
m
i
n
i
s
t
r
a
t
o
r
r
o
o
m, m
e
e
t
r
o
o
m
};
O
P
=
{
o
p
1,…,o
p
n
} is a set of operations; for example, OP
=
{
o
p
e
n, c
l
o
s
e
};
O
=
{
o
1,…,o
n
} is a set of target objects; for example, O
=
{
T
V, M
i
c
r
o
w
a
v
e
};
P
E
R
M
⊆
O
P
×
O is a set of permissions, where (
o
p,o
)
∈
P
E
R
M means that o
p is performed on o. For example, if P
E
R
M
=
{
(
o
p
e
n, T
V
)
} is assigned to device i
d, then the device owns the permission to open T
V;
A
c
c
Z
o
n
e
⊆
R
E
P
×
L
T
×
L
L
O
C is a set of a
c
c
e
s
s
z
o
n
e
s, where each access zone is a triple (
r
e
p, l
t, l
l
o
c
);
P
A
⊆
P
E
R
M
×
A
c
c
Z
o
n
e is a many-to-many map of connections between permissions and access zones. (
x, y
)
∈
P
A means that any node with y has permission x. For example, (
(
o
p
,
o
)
,
(
r
e
p
1
,
l
t
1
,
l
l
o
c
1
)
)
∈
P
A denotes that a node satisfying the constraint of l
t
1 with reputation r
e
p
1 at location l
l
o
c
1 can execute operation o
p on object o;
A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d: P
E
R
M
→
2
A
c
c
Z
o
n
e assigns a permission level to access zones, where A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
p
e
r
m
)
=
{
A
c
c
Z
o
n
e
∣
(
p
e
r
m, A
c
c
Z
o
n
e
)
∈
P
A
}; that is, given a p
e
r
m, function A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d returns all access zones which the p
e
r
m can access. For example, if P
A
=
{
(
(
o
p
1, o
2
), (
r
e
p
2, l
t
1, l
l
o
c
2
)
), (
(
o
p
2, o
1
), (
r
e
p
2, l
t
2, l
l
o
c
2
)
), (
(
o
p
1, o
2
), (
r
e
p
2, l
t
3, l
l
o
c
1
)
)
}, then A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
1, o
2
)
)
=
{
(
r
e
p
2, l
t
1, l
l
o
c
2
), (
r
e
p
2, l
t
3, l
l
o
c
1
)
};
p
e
r
m
A
s
s
i
g
n
e
d: A
c
c
Z
o
n
e
→
2
P
E
R
M assigns an access zone to permissions, where p
e
r
m
A
s
s
i
g
n
e
d
(
A
c
c
Z
o
n
e
)
=
{
p
e
r
m
∣
(
p
e
r
m, A
c
c
Z
o
n
e
)
∈
P
A
}; that is, given an a
c
c
z
o
n
e, function p
e
r
m
A
s
s
i
g
n
e
d returns all permissions by which the a
c
c
z
o
n
e can be accessed. For example, in the example of A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d, p
e
r
m
A
s
s
i
g
n
e
d
(
(
r
e
p
2, l
t
1, l
l
o
c
2
)
)
=
{
(
o
p
1, o
2
), (
o
p
2, o
1
)
};
A
c
c
e
s
s
R
e
q
u
e
s
t: I
D
×
O
P
×
O
→
{
t
r
u
e, f
a
l
s
e
} is a predicate; if it returns true, then node i
d requests permission to execute o
p on o. Recall that the storage of r
e
p is either distributed or centralized. To model the two cases, we remove r
e
p from access requests; for simplicity, we also remove the ID’s location and reputation from access requests and encapsulate the three elements into the function C
u
r
r
e
n
t
R
T
L (we will discuss it next);
A
l
l
o
w
R
e
q
u
e
s
t: I
D
×
O
P
×
O
→
{
t
r
u
e, f
a
l
s
e
} is a predicate; if it returns true, then node i
d is allowed to o
p on o;
D
e
n
y
R
e
q
u
e
s
t: I
D
×
O
P
×
O
→
{
t
r
u
e, f
a
l
s
e
} is a predicate; if it returns true, then node i
d is not allowed to execute o
p on o;
R
e
v
o
k
e
R
e
q
u
e
s
t: I
D
×
O
P
×
O
→
{
t
r
u
e, f
a
l
s
e
} is a predicate; if it returns true, then the permission that node i
d executes o
p on o will be revoked;
C
u
r
r
e
n
t
R
T
L: I
D
→
R
E
P
×
C
T
×
2
L
L
O
C is a function and returns i
d’s current reputation, its logical time, and logical locations (a node may be located in many different logical locations).In order to return the logical locations of a node, its physical location must be first obtained, and then its logical locations can be computed using the functionP
l
o
c
T
o
L
l
o
c. Because a physical location can be associated with many logical areas, C
u
r
r
e
n
t
R
T
L returns a set of logical locations.


## 5.2. Mechanism for Authorization and Revocation

Intuitively, if a node located in an appropriate area has an acceptable reputation and satisfies the given time constraints, its requests to execute some operations on an object should be allowed. In order to avoid using too many symbols, we overload the notation∈, as follows.Giveni
d, o
p, and o, let C
u
r
r
e
n
t
R
T
L
(
i
d
)
=
{
r
e
p
i
d
,
c
t
i
d
,
{
l
l
o
c
i
d
1
,
…
,
l
l
o
c
i
d
n
}
} and A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
,
o
)
) = {
(
r
e
p
1
,
l
t
1
,
l
l
o
c
1
)
,
…
,
(
r
e
p
n
,
l
t
n
,
l
l
o
c
n
)
}; C
u
r
r
e
n
t
R
T
L
(
i
d
)
∈
A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
,
o
)
) if and only if there exists (
r
e
p
i
,
l
t
i
,
l
l
o
c
i
)
∈
A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
,
o
)
) with r
e
p
i
d
=
r
e
p
i,  c
t
i
d
∈
l
t
i (c
t
i
d
∈
l
t
i if and only if (
c
t
1
,
c
t
2
)
∈
t
i
m
e
A
s
s
i
g
n
e
d
(
l
t
i
) holds, where c
t
1
≤
c
t
i
d
≤
c
t
2) and l
l
o
c
i
∈
{
l
l
o
c
i
d
1
,
…
,
l
l
o
c
i
d
n
}. The authorization schemes are as follows:(1)
A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
∧
C
u
r
r
e
n
t
R
T
L
(
i
d
)
∈
A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
,
o
)
)
→
A
l
l
o
w
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
(2)
A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
∧
C
u
r
r
e
n
t
R
T
L
(
i
d
)
∉
A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
,
o
)
)
→
D
e
n
y
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
(3)
A
l
l
o
w
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
∧
C
u
r
r
e
n
t
R
T
L
(
i
d
)
∉
A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
o
p
,
o
)
)
→
R
e
v
o
k
e
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
).Formulas (1) and (2) show the following: (1) if the nodei
d requests permission to execute o
p on o, and if C
u
r
r
e
n
t
R
T
L
(
i
d
) (the current reputation, access time, and location of i
d) satisfies the conditions to execute o
p on o, then the request will be allowed; (2) if the node i
d requests permission to execute o
p on o, but C
u
r
r
e
n
t
R
T
L
(
i
d
) does not satisfy the conditions to execute o
p on o, then the request will be denied. Formula (3) suggests that if node i
d has received the permission of executing o
p on o and C
u
r
r
e
n
t
R
T
L
(
i
d
) no longer satisfies the conditions to execute o
p on o longer, the permission will be revoked.


## 6. Access Lattice

Because terminal nodes could move into many areas at different times, enumerating all areas and periods of time rapidly increases the size of PA (as shown above, PA connections between permissions and the power set of access zones). As a result, the size of the PA table could exceed the storage capacity. In addition, querying a big table consumes more energy and computing resources, thereby decreasing the efficiency of queries and even reducing a node’s lifetime. Thus, decreasing the size of permission access table is critical. In order to achieve this goal, we adopted the access lattice in this study.We make the following realistic assumptions regarding the sensing layer of the IoT. (1) A node with a high reputation can be granted all permissions of a lower-reputation node. (2) If a task can be executed in a wide area or a longer time period, then it can be also executed in a narrow area or a shorter time period. These assumptions mean that if one node owns two access zonesA and B, where A is stricter than B, then A can be omitted from the set of access zones, because any permission allowed under B is allowed under A. We chose the lattice to decrease the size of the permission access table, because it models the strict relationship among elements. In order to formally describe the access lattice, we first define the order relation.Definition 21 (o
r
d
e
r
r
e
l
a
t
i
o
n
≤
o
n
A
c
c
Z
o
n
e).
Given any(
r
e
p
1
,
l
t
1
,
l
l
o
c
1
) and (
r
e
p
2
,
l
t
2
,
l
l
o
c
2
)
∈
A
c
c
Z
o
n
e, (
r
e
p
1
,
l
t
1
,
l
l
o
c
1
)
≤
(
r
e
p
2
,
l
t
2
,
l
l
o
c
2
), if and only if r
e
p
1
⪯
r
e
p
2, l
t
1
⪯
l
t
2, l
l
o
c
2
⊆
l
l
o
c
1.Theorem 22.
If (1)L
T is closed under ⊙ and ⊕ and (2) L
L
O
C is closed under ∩ and ∪, then (
A
C
C
B
A
S
E
,
≤
) is a lattice.Proof that there exists a supremum and an infimum for any(
r
e
p
1
,
l
t
1
,
l
l
o
c
1
), (
r
e
p
2
,
l
t
2
,
l
l
o
c
2
)
∈
A
C
C
B
A
S
E: if (
r
e
p
1
,
l
t
1
,
l
l
o
c
1
) and (
r
e
p
2
,
l
t
2
,
l
l
o
c
2
) are comparable, then there exists a supremum and an infimum for them. Even if (
r
e
p
1
,
l
t
1
,
l
l
o
c
1
) and (
r
e
p
2
,
l
t
2
,
l
l
o
c
2
) are incomparable, there exists a supremum and an infimum for them. Because ⪯ on R
E
P is a total order, there exists a supremum for {
r
e
p
1
,
r
e
p
2
}; let the supremum be r
e
p
x, because L
T is closed under both ⊙ and ⊕, and L
O
C is closed under ∩ and ∪; therefore, (
r
e
p
x
,
l
t
1
⊙
l
t
2
,
l
l
o
c
1
∩
l
l
o
c
2
) is in A
c
c
Z
o
n
e and is the upper boundary of (
r
e
p
1
,
l
t
1
,
l
l
o
c
1
) and (
r
e
p
2
,
l
t
2
,
l
l
o
c
2
). Let (
r
e
p
,
l
t
,
l
l
o
c
) be another upper boundary of (
r
e
p
1
,
l
t
1
,
l
l
o
c
1
) and (
r
e
p
2
,
l
t
2
,
l
l
o
c
2
), then we have l
o
c
⊆
l
l
o
c
1 and l
o
c
⊆
l
o
c
2; therefore, l
l
o
c
⊆
l
l
o
c
1
∩
l
l
o
c
2. Because r
e
p
x is the supremum of {
r
e
p
1
,
r
e
p
2
}, r
e
p
x
⪯
r
e
p. According to Proposition 17, we have l
t
⪯
l
t
1
⊙
l
t
2. Thus, (
r
e
p
x
,
l
t
1
⊙
l
t
2
,
l
l
o
c
1
∩
l
l
o
c
2
)
⪯
(
r
e
p
,
l
t
,
l
l
o
c
). Therefore, (
r
e
p
x
,
l
t
1
⊙
l
t
2
,
l
l
o
c
1
∩
l
l
o
c
2
) is a supremum of (
r
e
p
1
,
l
t
1
,
l
l
o
c
1
) and (
r
e
p
2
,
l
t
2
,
l
l
o
c
2
). Similarly, (
r
e
p
y
,
l
t
1
⊕
l
t
2
,
l
l
o
c
1
∪
l
l
o
c
2
) is an infimum of (
r
e
p
1
,
l
t
1
,
l
l
o
c
1
) and (
r
e
p
2
,
l
t
2
,
l
l
o
c
2
), where r
e
p
y is an infimum of {
r
e
p
1
,
r
e
p
2
}.We assume thatL
T is closed under ⊙  and ⊕, L
L
O
C is closed under ∩ and ∪. We redefine the permission function under a lattice, as follows:p
e
r
m
A
s
s
i
g
n
e
d
lattice: A
c
c
Z
o
n
e
→
2
P
E
R
M maps the access zones to permissions, and e
r
m
A
s
s
i
g
n
e
d
lattice  (
A
c
c
Z
o
n
e
)
=
{
p
e
r
m
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
A
c
c
Z
o
n
e
x
)
∣
A
c
c
Z
o
n
e
x
⪯
A
c
c
Z
o
n
e
}.BecauseA
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
lattice and A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d are similar and easily distinguished from one another; therefore, A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d is adopted to denote the two functions in the sequel. Similarly, p
e
r
m
A
s
s
i
g
n
e
d is used to denote p
e
r
m
A
s
s
i
g
n
e
d
lattice.Theorem 23.
Given any(
r
e
p
1
,
l
t
1
,
l
l
o
c
1
) and (
r
e
p
2
,
l
t
2
,
l
l
o
c
2
)
∈
A
c
c
Z
o
n
e, if (
r
e
p
1
,
l
t
1
,
l
l
o
c
1
)
⪯
(
r
e
p
2
,
l
t
2
,
l
l
o
c
2
), then p
e
r
m
A
s
s
i
g
n
e
d
(
(
r
e
p
1
,
l
t
1
,
l
l
o
c
1
)
)
⊆
p
e
r
m
A
s
s
i
g
n
e
d
(
(
r
e
p
2
,
l
t
2
,
l
l
o
c
2
)
).Theorem 24.
Consider the following.
IfA
l
l
o
w
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
∧
A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
′
,
o
p
,
o
)
∧
C
u
r
r
e
n
t
R
T
L
(
i
d
)
⪯
C
u
r
r
e
n
t
R
T
L
(
i
d
′
), then A
l
l
o
w
R
e
q
u
e
s
t
(
i
d
′
,
o
p
,
o
).
IfD
e
n
y
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
∧
A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
′
,
o
p
,
o
)
∧
C
u
r
r
e
n
t
R
T
L
(
i
d
′
)
⪯
C
u
r
r
e
n
t
R
T
L
(
i
d
), then D
e
n
y
R
e
q
u
e
s
t
(
i
d
′
,
o
p
,
o
).
IfR
e
v
o
k
e
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
)
∧
A
l
l
o
w
R
e
q
u
e
s
t
(
i
d
′
,
o
p
,
o
)
∧
C
u
r
r
e
n
t
R
T
L
(
i
d
′
)
⪯
C
u
r
r
e
n
t
R
T
L
(
i
d
), then R
e
v
o
k
e
R
e
q
u
e
s
t
(
i
d
′
,
o
p
,
o
).Theorem24 shows (1) if a node with a low reputation can execute o
p on o, then another node with a higher reputation is also able to perform the same operation; (2) if a node with a high reputation is unable to execute operation o
p on o, then a node with a lower reputation is also unable to do so; and (3) if access permissions are revoked from a node with a high reputation, then the corresponding permissions are also revoked from a node with a lower reputation.The following example illustrates that the lattice can efficiently decrease the size of policy bases.Example 25.
LetP
E
R
M
=
{
(
O
p
e
n, M
i
c
r
o
W
a
v
e
), (
S
e
t
P
a
r
a
m
e
t
e
r, M
i
c
r
o
W
a
v
e
), (
c
l
o
s
e, M
i
c
r
o
W
a
v
e
)
}, A
C
C
B
S
E
=
{
(
r
e
p
1
,
l
t
1
,
l
l
o
c
1
), (
r
e
p
2
,
l
t
2
,
l
l
o
c
2
), (
r
e
p
3
,
l
t
3
,
l
l
o
c
3
), (
r
e
p
4
,
l
t
4
,
l
l
o
c
4
)
}. The access base for each permission is as follows: A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
c
l
o
s
e, M
i
c
r
o
W
a
v
e
)
)
=
{
(
r
e
p
1
,
l
t
1
,
l
l
o
c
1
), (
r
e
p
2
,
l
t
2
,
l
l
o
c
2
), (
r
e
p
3
,
l
t
3
,
l
l
o
c
3
), (
r
e
p
4
,
l
t
4
,
l
l
o
c
4
)
}, A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
S
e
t
P
a
r
a
m
e
t
e
r, M
i
c
r
o
W
a
v
e
)
)
=
{
(
r
e
p
3
,
l
t
3
,
l
l
o
c
3
), (
r
e
p
4
,
l
t
4
,
l
l
o
c
4
)
} and A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
O
p
e
n, M
i
c
r
o
W
a
v
e
)
)
=
{
(
r
e
p
4
,
l
t
4
,
l
l
o
c
4
)
}. From above, the cardinality of A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
C
l
o
s
e, M
i
c
r
o
W
a
v
e
)
), A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
S
e
t
P
a
r
a
m
e
t
e
r, M
i
c
r
o
W
a
v
e
)
), and A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
O
p
e
n, M
i
c
r
o
W
a
v
e
)
) is 4, 2, and 1, respectively.
Assuming that a lattice can be formed from these access zones as shown in Figure3, then the access base for each permission could be changed as follows: A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
c
l
o
s
e, M
i
c
r
o
W
a
v
e
)
)
=
{
(
r
e
p
1
,
l
t
1
,
l
l
o
c
1
)
}, A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
S
e
t
P
a
r
a
m
e
t
e
r, M
i
c
r
o
W
a
v
e
)
)
=
{
(
r
e
p
3
,
l
t
3
,
l
l
o
c
3
)
}, and A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d
(
(
O
p
e
n, M
i
c
r
o
W
a
v
e
)
)
=
{
(
r
e
p
4
,
l
t
4
,
l
l
o
c
4
)
}. This means that the cardinality of all three bases is 1. Given an access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d, C
l
o
s
e, M
i
c
r
o
W
a
v
e
) from node i
d with reputation r
e
p
3 and assuming that node i
d is at the location l
l
o
c
3 and the current time satisfies l
t
3, then A
l
l
o
w
R
e
q
u
e
s
t
(
i
d, C
l
o
s
e, M
i
c
r
o
W
a
v
e
) will be true, because (
r
e
p
1
,
l
t
1
,
l
l
o
c
1
)
⪯
(
r
e
p
3
,
l
t
3
,
l
l
o
c
3
). From this example, we can deduce that the size of policy bases can be decreased using an access lattice.
Regarding the example given in the beginning of this section, if the above lattice is used, the storage complexity and the computing complexity are reduced ton and 1, respectively.Figure 3
An access lattice.


## 7. Authorization under Incomplete Information

In the above discussion, we mainly focused on authorization with complete information available (ACI), which is also called deterministic authorization. In other words, decision makers have the ability to obtain authorization information in time. However, this is not always the case. For example, when a node moves into a location where communication is unstable, it may not be able to obtain complete authorization information in time. In this case, decision makers have to choose whether to grant authorization or not, based on their own knowledge, such as historical experiences. This is related to authorization with incomplete information (AII). Lack of complete information presents the following challenges: (1) designing a secure authorization policy and (2) balancing security with QoS. To address these two challenges, we propose both nondeterministic authorizations and stochastic authorizations.


### 7.1. Nondeterministic Authorization

Nondeterministic authorization includes three alternative policies: pessimistic, optimistic, and compromise authorizations. Nodes run under the lowest permission levels in a pessimistic authorization, thus, providing only the most basic security.Policy 1 (pessimistic authorization).
Given a access lattice formed byA
c
c
Z
o
n
e and an access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
), if (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
g
l
b
(
A
c
c
Z
o
n
e
)
), then the request is allowed, where g
l
b
(
A
c
c
Z
o
n
e
) represents the greatest lower bound of set A
c
c
Z
o
n
e
(i.e., the smallest elements of A
c
c
Z
o
n
e
).In order to execute Policy1, all elements in p
e
r
m
A
s
s
i
g
n
e
d
(
g
l
b
(
A
c
c
Z
o
n
e
)
) must be locally stored. Although additional storage space is required by Policy 1, because both the greatest lower bounds of a lattice are unique, the storage complexity of the access rule table in Policy 1 is |
o
p
|
×
|
o
|; therefore, it is acceptable for the majority of weak-resources devices. Because glb(A
c
c
Z
o
n
e) is granted to the lowest permissions, Policy 1 is always secure (see Theorem 27 for the proof); however, this policy might have a lower QoS. For example, if the least permission is ϕ (empty), then any request will be automatically denied.Contrary to pessimistic authorization, optimistic authorization concentrates on QoS while ignoring security. In this policy, nodes are granted the highest allowable permissions. From Theorem22, l
u
b
(
A
c
c
Z
o
n
e
) is the largest element of A
c
c
Z
o
n
e, where l
u
b
(
A
c
c
Z
o
n
e
) represents the least upper boundary of A
c
c
Z
o
n
e. Thus, the greatest permissions are granted to l
u
b
(
A
c
c
Z
o
n
e
).Policy 2 (optimistic authorization).
Given an access lattice formed byA
c
c
Z
o
n
e and an access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
), if (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
l
u
b
(
A
c
c
Z
o
n
e
)
), then the request is allowed.As with Policy1, all elements of p
e
r
m
A
s
s
i
g
n
e
d
(
l
u
b
(
A
c
c
Z
o
n
e
)
) must be locally stored. Because any node in this policy is granted the greatest permissions, Policy 2 is not considered to be secure (see Example 28 for an example). However, this policy can efficiently improve QoS. For example, if the number of nodes with access to a film in digital rights management (DRM) is only optionally counted, any node can access this film anytime and anywhere, even when communications have been interrupted. If the film is stored locally, Policy 2 should be adopted, because security is not as much of an issue; if Policy 1 was used, the benefits surrounding optionally counting accesses cannot be achieved. Thus, Policy 2 has a higher QoS.In many cases, security and QoS are needed to be balanced. To achieve this goal, we propose three compromise authorization policies: (1) trade-off authorization based on reputation(
T
A
B
R
), (2) trade-off authorization based on space (
T
A
B
S
), and (
3
) trade-off authorization based on time (
T
A
B
T
). We first discuss T
A
B
R.Letc
o
m
p
_
r
e
p: R
E
P
→
A
c
c
Z
o
n
e be a function from R
E
P to A
c
c
Z
o
n
e, defined as c
o
m
p
_
r
e
p
(
r
e
p
)
=
g
l
b
{
(
r
e
p
x
,
l
t
,
l
l
o
c
)
∈
A
c
c
Z
o
n
e
∣
r
e
p
x
=
r
e
p
}, representing the greatest lower boundary of access zones accessed by a node with reputation r
e
p.Policy 3 (T
A
B
R).
Given an access lattice formed byA
c
c
Z
o
n
e and an access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
) in A
I
I, if (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
c
o
m
p
_
r
e
p
(
r
e
p
)
), where r
e
p is the reputation of node i
d, then the request is allowed.Similarly, letc
o
m
p
_
l
o
c: L
L
O
C
→
A
c
c
Z
o
n
e map from logical locations to A
c
c
Z
o
n
e, defined as c
o
m
p
_
l
o
c
(
l
l
o
c
)
=
g
l
b
{
(
r
e
p
,
l
t
,
l
l
o
c
x
)
A
c
c
Z
o
n
e
∣
l
l
o
c
x
=
l
l
o
c
}, representing the greatest lower boundary of access zones accessed by a node in logical location l
l
o
c.Policy 4 (T
A
B
S).
Given an access lattice formed byA
c
c
Z
o
n
e and access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
) in A
I
I, if (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
c
o
m
p
_
l
o
c
(
l
l
o
c
)
), where l
l
o
c is the current logical location of node i
d, then the request is allowed.Letc
o
m
p
_
l
t: L
T
→
A
c
c
Z
o
n
e be a function from L
T to A
c
c
Z
o
n
e, defined as c
o
m
p
_
l
t
(
l
t
)
=
g
l
b
{
(
r
e
p
x
,
l
t
,
l
l
o
c
)
∈
A
c
c
Z
o
n
e
∣
l
t
x
=
l
t
}, representing the greatest lower boundary of access zones accessed by a node satisfying time constraint l
t.Policy 5 (T
A
B
T).
Given an access lattice formed byA
c
c
Z
o
n
e and an access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
) in A
I
I, if (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
c
o
m
p
_
l
t
(
l
t
)
), where c
t
(
)
∈
l
t  (function c
t: ϕ
→
C
B returns the current time), then the request is allowed.Because Policies1–5 are related to incomplete information, their security must be formally analyzed.Definition 26 (security underA
I
I).
A policy is secure underA
I
I if for any access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
), A
l
l
o
w
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
) under A
I
I is the same as A
l
l
o
w
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
) under A
C
I.Theorem 27.
Policy1 and Policies 3–5 are secure.Proof that Policy1 is secure: given node id with reputation r
e
p and an access request (
i
d
,
o
p
,
o
), because (
i
d
,
o
p
,
o
) is allowed under Policy 1, we have (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
l
u
b
(
A
c
c
Z
o
n
e
)
). Let (
r
e
p
,
c
t
(
)
,
l
l
o
c
) be the reputation, the current time, and the logical location of node i
d under A
C
I, where (
r
e
p
,
l
t
,
l
l
o
c
) exists with (
r
e
p
,
c
t
(
)
,
l
l
o
c
)
∈
(
r
e
p
,
l
t
,
l
l
o
c
) (
(
r
e
p
1
,
c
t
(
)
,
l
l
o
c
1
)
∈
(
r
e
p
2
,
l
t
,
l
l
o
c
2
), if r
e
p
1
=
r
e
p
2 and c
t
(
)
∈
l
t and l
l
o
c
1
=
l
l
o
c
2
). Because g
l
b
(
A
c
c
Z
o
n
e
) is the least element of A
c
c
Z
o
n
e, we have g
l
b
(
A
c
c
Z
o
n
e
)
⪯
(
r
e
p
,
l
t
,
l
l
o
c
). According to Policy 1 and Theorem 23, we have (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
g
l
b
(
A
c
c
Z
o
n
e
)
)
⊆
p
e
r
m
A
s
s
i
g
n
e
d
(
(
r
e
p
,
l
t
,
l
l
o
c
)
); therefore, (
r
e
p
,
l
t
,
l
l
o
c
)
∈
A
c
c
Z
o
n
e
s
s
i
g
n
e
d
(
(
o
p
,
o
)
), A
l
l
o
w
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
) under A
C
I is true. That is, Policy 1 is secure.Although Policy1 and Policies 3–5 are secure, Policy 2 is insecure. An example is as follows.Example 28.
LetA
c
c
Z
o
n
e
=
(
r
e
p
,
l
t
,
l
o
c
) with (
r
e
p
,
l
t
,
l
o
c
)
≺
l
u
b
(
A
c
c
Z
o
n
e
). According to Theorem 23, there exists (
o
p
,
o
) with (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
l
u
b
(
A
c
c
Z
o
n
e
)
)-p
e
r
m
A
s
s
i
g
n
e
d
(
(
r
e
p
,
l
t
,
l
o
c
)
). A
c
c
e
s
s
R
e
q
u
e
s
t (
i
d
,
o
p
,
o
) will be allowed if Policy 2 is adopted; however, this request will be denied under A
C
I. This means that Policy 2 is insecure. Because security obeys the “leaky bucket” principle, Policy 2 is not suitable for security-critical systems.


### 7.2. Stochastic Authorization

In some cases, authorization may be considered to be stochastic. For example, when an automatically driven car arrives at crossroads, its central controller selects the road with the most gains (including both time and fuel-saving gains) by computing the distance to the destination and forecasting the probability of road congestion. In this case, road congestion is stochastic; as a result, the authorization is stochastic. Although stochastic authorization is actual requirement in the IoT, no efforts are spent on it in existing studies. In our study, we propose the (to the best of our knowledge) expectation-based authorization (EBA), where decision makers evaluate access requests by analyzing its potential gains in the successor states that would occur if the authorizations were granted. If the potential gains of the request are greater than or equal to a given threshold, it will be allowed.E
B
A includes the following elements besides the components mentioned in Section 5.1:(1)
S
=
{
s
1
,
…
,
s
n
} is a set of states representing the potential successor states which the systems can arrive to after authorization.
(2)
f: S
→
R is a gain function, and f
(
s
) represents the gain of decision makers in state s, w
h
e
r
e
R is a real number.
(3)
p: S
→
R is a probability distribution of state set S, and p
(
s
) denotes the probability that systems would reach state s.
(4)
Thresholdr.The authorization rule is as follows: for any Access Request(
i
d
,
o
p
,
o
), if ∑
s
=
1
S
p
(
s
)
×
f
(
s
)
≥
r, then this request is granted. If several access requests exist and only one is allowed, then the request with the maximum gain is granted permission. Additionally, if multiple requests could have the maximum gain, then the decision maker randomly chooses among those requests.As with Policy2, expectation authorization improves the QoS. In the above example of automatic-driving systems, pessimistic authorization would deny any access request to each road, whereas optimistic authorization would allow all access requests for all roads. This is unacceptable for the automatic-driving systems. Thus, nondeterministic authorization (pessimistic/optimistic authorization) is unsuitable for automatic-driving systems. Conversely, because both the road environment and the historical experiences are taken into consideration to ensure that only the request with the maximum gain is allowed, stochastic authorization is suitable for automatic-driving systems.


## 7.1. Nondeterministic Authorization

Nondeterministic authorization includes three alternative policies: pessimistic, optimistic, and compromise authorizations. Nodes run under the lowest permission levels in a pessimistic authorization, thus, providing only the most basic security.Policy 1 (pessimistic authorization).
Given a access lattice formed byA
c
c
Z
o
n
e and an access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
), if (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
g
l
b
(
A
c
c
Z
o
n
e
)
), then the request is allowed, where g
l
b
(
A
c
c
Z
o
n
e
) represents the greatest lower bound of set A
c
c
Z
o
n
e
(i.e., the smallest elements of A
c
c
Z
o
n
e
).In order to execute Policy1, all elements in p
e
r
m
A
s
s
i
g
n
e
d
(
g
l
b
(
A
c
c
Z
o
n
e
)
) must be locally stored. Although additional storage space is required by Policy 1, because both the greatest lower bounds of a lattice are unique, the storage complexity of the access rule table in Policy 1 is |
o
p
|
×
|
o
|; therefore, it is acceptable for the majority of weak-resources devices. Because glb(A
c
c
Z
o
n
e) is granted to the lowest permissions, Policy 1 is always secure (see Theorem 27 for the proof); however, this policy might have a lower QoS. For example, if the least permission is ϕ (empty), then any request will be automatically denied.Contrary to pessimistic authorization, optimistic authorization concentrates on QoS while ignoring security. In this policy, nodes are granted the highest allowable permissions. From Theorem22, l
u
b
(
A
c
c
Z
o
n
e
) is the largest element of A
c
c
Z
o
n
e, where l
u
b
(
A
c
c
Z
o
n
e
) represents the least upper boundary of A
c
c
Z
o
n
e. Thus, the greatest permissions are granted to l
u
b
(
A
c
c
Z
o
n
e
).Policy 2 (optimistic authorization).
Given an access lattice formed byA
c
c
Z
o
n
e and an access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
), if (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
l
u
b
(
A
c
c
Z
o
n
e
)
), then the request is allowed.As with Policy1, all elements of p
e
r
m
A
s
s
i
g
n
e
d
(
l
u
b
(
A
c
c
Z
o
n
e
)
) must be locally stored. Because any node in this policy is granted the greatest permissions, Policy 2 is not considered to be secure (see Example 28 for an example). However, this policy can efficiently improve QoS. For example, if the number of nodes with access to a film in digital rights management (DRM) is only optionally counted, any node can access this film anytime and anywhere, even when communications have been interrupted. If the film is stored locally, Policy 2 should be adopted, because security is not as much of an issue; if Policy 1 was used, the benefits surrounding optionally counting accesses cannot be achieved. Thus, Policy 2 has a higher QoS.In many cases, security and QoS are needed to be balanced. To achieve this goal, we propose three compromise authorization policies: (1) trade-off authorization based on reputation(
T
A
B
R
), (2) trade-off authorization based on space (
T
A
B
S
), and (
3
) trade-off authorization based on time (
T
A
B
T
). We first discuss T
A
B
R.Letc
o
m
p
_
r
e
p: R
E
P
→
A
c
c
Z
o
n
e be a function from R
E
P to A
c
c
Z
o
n
e, defined as c
o
m
p
_
r
e
p
(
r
e
p
)
=
g
l
b
{
(
r
e
p
x
,
l
t
,
l
l
o
c
)
∈
A
c
c
Z
o
n
e
∣
r
e
p
x
=
r
e
p
}, representing the greatest lower boundary of access zones accessed by a node with reputation r
e
p.Policy 3 (T
A
B
R).
Given an access lattice formed byA
c
c
Z
o
n
e and an access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
) in A
I
I, if (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
c
o
m
p
_
r
e
p
(
r
e
p
)
), where r
e
p is the reputation of node i
d, then the request is allowed.Similarly, letc
o
m
p
_
l
o
c: L
L
O
C
→
A
c
c
Z
o
n
e map from logical locations to A
c
c
Z
o
n
e, defined as c
o
m
p
_
l
o
c
(
l
l
o
c
)
=
g
l
b
{
(
r
e
p
,
l
t
,
l
l
o
c
x
)
A
c
c
Z
o
n
e
∣
l
l
o
c
x
=
l
l
o
c
}, representing the greatest lower boundary of access zones accessed by a node in logical location l
l
o
c.Policy 4 (T
A
B
S).
Given an access lattice formed byA
c
c
Z
o
n
e and access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
) in A
I
I, if (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
c
o
m
p
_
l
o
c
(
l
l
o
c
)
), where l
l
o
c is the current logical location of node i
d, then the request is allowed.Letc
o
m
p
_
l
t: L
T
→
A
c
c
Z
o
n
e be a function from L
T to A
c
c
Z
o
n
e, defined as c
o
m
p
_
l
t
(
l
t
)
=
g
l
b
{
(
r
e
p
x
,
l
t
,
l
l
o
c
)
∈
A
c
c
Z
o
n
e
∣
l
t
x
=
l
t
}, representing the greatest lower boundary of access zones accessed by a node satisfying time constraint l
t.Policy 5 (T
A
B
T).
Given an access lattice formed byA
c
c
Z
o
n
e and an access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
) in A
I
I, if (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
c
o
m
p
_
l
t
(
l
t
)
), where c
t
(
)
∈
l
t  (function c
t: ϕ
→
C
B returns the current time), then the request is allowed.Because Policies1–5 are related to incomplete information, their security must be formally analyzed.Definition 26 (security underA
I
I).
A policy is secure underA
I
I if for any access request A
c
c
e
s
s
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
), A
l
l
o
w
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
) under A
I
I is the same as A
l
l
o
w
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
) under A
C
I.Theorem 27.
Policy1 and Policies 3–5 are secure.Proof that Policy1 is secure: given node id with reputation r
e
p and an access request (
i
d
,
o
p
,
o
), because (
i
d
,
o
p
,
o
) is allowed under Policy 1, we have (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
l
u
b
(
A
c
c
Z
o
n
e
)
). Let (
r
e
p
,
c
t
(
)
,
l
l
o
c
) be the reputation, the current time, and the logical location of node i
d under A
C
I, where (
r
e
p
,
l
t
,
l
l
o
c
) exists with (
r
e
p
,
c
t
(
)
,
l
l
o
c
)
∈
(
r
e
p
,
l
t
,
l
l
o
c
) (
(
r
e
p
1
,
c
t
(
)
,
l
l
o
c
1
)
∈
(
r
e
p
2
,
l
t
,
l
l
o
c
2
), if r
e
p
1
=
r
e
p
2 and c
t
(
)
∈
l
t and l
l
o
c
1
=
l
l
o
c
2
). Because g
l
b
(
A
c
c
Z
o
n
e
) is the least element of A
c
c
Z
o
n
e, we have g
l
b
(
A
c
c
Z
o
n
e
)
⪯
(
r
e
p
,
l
t
,
l
l
o
c
). According to Policy 1 and Theorem 23, we have (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
g
l
b
(
A
c
c
Z
o
n
e
)
)
⊆
p
e
r
m
A
s
s
i
g
n
e
d
(
(
r
e
p
,
l
t
,
l
l
o
c
)
); therefore, (
r
e
p
,
l
t
,
l
l
o
c
)
∈
A
c
c
Z
o
n
e
s
s
i
g
n
e
d
(
(
o
p
,
o
)
), A
l
l
o
w
R
e
q
u
e
s
t
(
i
d
,
o
p
,
o
) under A
C
I is true. That is, Policy 1 is secure.Although Policy1 and Policies 3–5 are secure, Policy 2 is insecure. An example is as follows.Example 28.
LetA
c
c
Z
o
n
e
=
(
r
e
p
,
l
t
,
l
o
c
) with (
r
e
p
,
l
t
,
l
o
c
)
≺
l
u
b
(
A
c
c
Z
o
n
e
). According to Theorem 23, there exists (
o
p
,
o
) with (
o
p
,
o
)
∈
p
e
r
m
A
s
s
i
g
n
e
d
(
l
u
b
(
A
c
c
Z
o
n
e
)
)-p
e
r
m
A
s
s
i
g
n
e
d
(
(
r
e
p
,
l
t
,
l
o
c
)
). A
c
c
e
s
s
R
e
q
u
e
s
t (
i
d
,
o
p
,
o
) will be allowed if Policy 2 is adopted; however, this request will be denied under A
C
I. This means that Policy 2 is insecure. Because security obeys the “leaky bucket” principle, Policy 2 is not suitable for security-critical systems.


## 7.2. Stochastic Authorization

In some cases, authorization may be considered to be stochastic. For example, when an automatically driven car arrives at crossroads, its central controller selects the road with the most gains (including both time and fuel-saving gains) by computing the distance to the destination and forecasting the probability of road congestion. In this case, road congestion is stochastic; as a result, the authorization is stochastic. Although stochastic authorization is actual requirement in the IoT, no efforts are spent on it in existing studies. In our study, we propose the (to the best of our knowledge) expectation-based authorization (EBA), where decision makers evaluate access requests by analyzing its potential gains in the successor states that would occur if the authorizations were granted. If the potential gains of the request are greater than or equal to a given threshold, it will be allowed.E
B
A includes the following elements besides the components mentioned in Section 5.1:(1)
S
=
{
s
1
,
…
,
s
n
} is a set of states representing the potential successor states which the systems can arrive to after authorization.
(2)
f: S
→
R is a gain function, and f
(
s
) represents the gain of decision makers in state s, w
h
e
r
e
R is a real number.
(3)
p: S
→
R is a probability distribution of state set S, and p
(
s
) denotes the probability that systems would reach state s.
(4)
Thresholdr.The authorization rule is as follows: for any Access Request(
i
d
,
o
p
,
o
), if ∑
s
=
1
S
p
(
s
)
×
f
(
s
)
≥
r, then this request is granted. If several access requests exist and only one is allowed, then the request with the maximum gain is granted permission. Additionally, if multiple requests could have the maximum gain, then the decision maker randomly chooses among those requests.As with Policy2, expectation authorization improves the QoS. In the above example of automatic-driving systems, pessimistic authorization would deny any access request to each road, whereas optimistic authorization would allow all access requests for all roads. This is unacceptable for the automatic-driving systems. Thus, nondeterministic authorization (pessimistic/optimistic authorization) is unsuitable for automatic-driving systems. Conversely, because both the road environment and the historical experiences are taken into consideration to ensure that only the request with the maximum gain is allowed, stochastic authorization is suitable for automatic-driving systems.


## 8. Mechanism for Updating Reputation

Because nodes of the IoT are easily tampered with, the reputation of the tampered nodes must be updated in time. In this section, we borrow the idea of downgrading in programming languages [27] and propose a new mechanism to update the reputation for the sensing layer of the IoT. In this mechanism, every node is bound to an update policy and any change to a node’s reputation must be consistent with the bound policy; that is, the reputation can be updated, only if a given policy for that node is satisfied. The syntax of the general update mechanism is defined in Table 1.Table 1
Syntax of update policies.
updatep::=
Policies
r
e
p
⊳
c
u
p
d
a
t
e
p
Update policy
ϕ
Empty policy
c::=
Condition
Basic predicate
Basic predicate
T
True
F
False
c
∨
c
Disjunction
¬
c
NegationThe above definitions are based on Backus Normal Form; for example,r
e
p
⊳
c
1
r
e
p
2
⊳
c
2
ϕ is grammatically correct. In Table 1, if the empty policy (
ϕ
) is adopted for a node, then its reputation is preserved. Given ⊳
c
1
u
p
d
a
t
e
p for a node means that if condition c
1 is true, then the reputation of the node will be updated to r
e
p
1, and the successor of the policy is updated to u
p
d
a
t
e
p. The formal semantics of this mechanism are as follows:
(4)
r
u
l
e
g
e
n
e
r
a
l
:
c
i
d
:
r
e
p
⊳
c
u
p
d
a
t
e
p
⟹
i
d
:
u
p
d
a
t
e
p
[
r
e
p
/
c
u
r
r
e
n
t
R
E
P
(
i
d
)
]
r
u
l
e
ϕ
:
i
d
:
⌀
⟹
⌀
,
where i
d
:
r
e
p
⊳
c
u
p
d
a
t
e
p represents the node i
d as bound to r
e
p
⊳
c
p
r
e
n
e
w andfunction c
u
r
r
e
n
t
R
E
P: I
D
→
R
E
P returns the current reputation of a given node. [r
e
p/c
u
r
r
e
n
t
R
E
P
(
i
d
)] denotes that c
u
r
r
e
n
t
R
E
P
(
i
d
) is substituted by r
e
p. r
u
l
e
g
e
n
e
r
a
l indicates that if the predicate c is true, then the current reputation of node i
d will be updated to r
e
p and its new policy is u
p
d
a
t
e
p. r
u
l
e
ϕ stops the update. Specifically, when the update policy for a node is r
e
p
⊳
T
u
p
d
a
t
e
p, then its reputation will be mandatorily updated to r
e
p. In contrary, if the policy is r
e
p
⊳
F
u
p
d
a
t
e
p, then the update will be forbidden.In Table1, basic predicates are coarse-grained and difficult to use. In order to solve this problem, we propose two submechanisms: authority-based update mechanisms (
A
U
M
) and election-based update mechanisms (
E
U
M
).


### 8.1. Authority-Based Update Mechanisms (AUM)

InA
U
M, only the authority node can update the reputation of other nodes. A node is called an authority node if its reputation is greater than or equal to a given threshold r
e
p
a
u
t
h, where r
e
p
a
u
t
h represents the authority reputation. To formally define semantics, we first provide the following definitions.c
u
r
r
e
n
t
T
L: I
D
→
C
B  2
L
L
O
C returns the current time and the set of current logical locations for a given node.U
p
d
a
t
e
T
L
⊆
L
T
×
L
L
O
C is a subset of the product of L
T and L
L
O
C. A node is granted the update permission, only if its current time and one of its current logical locations belong to the set U
p
d
a
t
e
T
L. In other words, node i
d can update the reputation of other nodes, only if c
u
r
r
e
n
t
T
L
(
i
d
)
∈
U
p
d
a
t
e
T
L  (let c
u
r
r
e
n
t
T
L
(
i
d
)
=
(
c
b,{
l
l
o
c
1
,
…
,
l
l
o
c
n
}
) and U
p
d
a
t
e
T
L
=
{
(
l
t
i
1, l
l
o
c
i
1
),…,(
l
t
i
m, l
l
o
c
i
m
)
}, we define c
u
r
r
e
n
t
T
L
(
i
d
)
∈
U
p
d
a
t
e
T
L, if and only if there exists (
l
t
i
l
,
l
l
o
c
i
l
)
∈
U
p
d
a
t
e
T
L such that c
b
∈
l
t
i
l and l
l
o
c
k
=
l
l
o
c
i
l, w
h
e
r
e
1
≤
k
≤
n
).The formal semantics of AUM are as follows:(5)
r
u
l
e
a
u
t
h
o
r
i
t
y
:
c
u
r
r
e
n
t
R
E
P
(
i
d
r
)
=
r
e
p
r
c
u
r
r
e
n
t
T
L
(
i
d
r
)
∈
U
p
d
a
t
e
T
L
r
e
p
,
c
u
r
r
e
n
t
R
E
P
(
i
d
)
≺
r
e
p
t
h
e
r
s
h
h
o
l
d
r
e
p
r
i
d
:
r
e
p
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
⟹
i
d
:
u
p
d
a
t
e
p
[
r
e
p
/
c
u
r
r
e
n
t
R
E
P
(
i
d
)
]
r
u
l
e
ϕ
:
i
d
:
⌀
⟹
⌀
.The predicatea
u
t
h
u
p
d
a
t
e
(
r
e
p
r
) is true, if and only if there exists i
d
∈
I
D with c
u
r
r
e
n
t
R
E
P
(
i
d
r
)
=
r
e
p
r,  c
u
r
r
e
n
t
T
L
(
i
d
r
)
∈
U
p
d
a
t
e
T
L, r
e
p
≺
r
e
p
t
h
e
r
s
h
h
o
l
d, c
u
r
r
e
n
t
R
E
P
(
i
d
)
≺
r
e
p
t
h
e
r
s
h
h
o
l
d, and r
e
p
t
h
e
r
s
h
h
o
l
d
⪯
r
e
p
r. The rule r
u
l
e
a
u
t
h
o
r
i
t
y states that the reputation of node i
d can be updated to r
e
p if the following conditions are satisfied: (1) r
e
p
t
h
e
r
s
h
h
o
l
d
⪯
c
u
r
r
e
n
t
R
E
P
(
i
d
r
); that is, node i
d
r is an authority node. (2)  c
u
r
r
e
n
t
T
L
(
i
d
r
)
∈
U
p
d
a
t
e
T
L; that is, node i
d
r satisfies the temporal and spatial constraint. (3) The current reputation of node i
d and its reputation after update are both greater than or equal to r
e
p
t
h
r
e
s
h
o
l
d.AUM can prevent a node’s reputation from being illegally updated even if authority nodes are lost. For example, the authority nodex in the location l
l
o
c can update the reputation of others. If x is lost, it may not be in the location l
l
o
c. Let x be in the location l
o
c
t
h
e
f
t with l
o
c
t
h
e
f
t
≠
l
l
o
c, therefore, making c
u
r
r
e
n
t
T
L
(
i
d
)
∉
U
p
d
a
t
e
T
L. This means that x no longer has the ability to update the reputation of other nodes.


### 8.2. Election-Based Update Mechanisms (EUM)

AlthoughA
U
M can be used to decrease the risk caused by the loss of nodes, authority nodes are security-critical because of the huge risks involved if they are compromised. In order to solve this problem, we propose E
U
M. In E
U
M, a group of nodes with a lower reputation are able to update the reputation of others through elections. When the majority of voters (nodes) agree on an update, the reputation of a specific node can be updated. In order to precisely define this mechanism, we first define the update function f
:
I
D
×
I
D
×
R
E
P
→
{
0,1
}, which maps I
D
×
I
D
×
R
E
P to {
0,1
}: If a voter i
d requests to update the reputation of candidate i
d
c to r
e
p
c, then f
(
i
d
c
,
i
d
,
r
e
p
c
)
=
1. The formal semantics of E
U
M is as follows:
(6)
r
u
l
e
e
l
e
c
t
i
o
n
:
Y
≥
r
i
d
c
:
r
e
p
c
⊳
Y
≥
r
u
p
d
a
t
e
p
⟹
i
d
:
u
p
d
a
t
e
p
[
r
e
p
c
/
c
u
r
r
e
n
t
R
E
P
(
i
d
c
)
]
,
where Y
=
∑
i
d
I
D
T
L
f
(
i
d
c
,
i
d
,
r
e
p
c
), I
D
T
L
=
{
x
∈
I
D
∣
c
u
r
r
e
n
t
T
L
(
x
)
∈
U
p
d
a
t
e
T
L
c
u
r
r
e
n
t
T
L
(
x
)
∈
U
p
d
a
t
e
T
L
}, and r is a natural number. R
u
l
e
e
l
e
c
t
i
o
n shows that if at least r nodes satisfying the given time constraints in the given areas request to update the reputation of node i
d to r
e
p, then these requests will be approved and id’s reputation will be updated. Because r
u
l
e
e
l
e
c
t
i
o
n can update the reputation of any other node, r must be carefully defined, especially in networks where malicious nodes are dominant. Generally, r could be equal to ⌈
N
/
2
⌉ or ⌈
2
N
/
3
⌉, where N is the number of voters.Example 29.
Let the update policy of nodei
d be r
e
p
0
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
r
e
p
1
⊳
T
ϕ; we have the following results.(1)
If the current reputation ofi
d is greater than r
e
p
t
h
r
e
s
h
o
l
d, then the reputation of x will be preserved.
(2)
If authority nodei
d
r, which is not located in the given areas or does not satisfy the given time constraints (i.e., c
u
r
r
e
n
t
T
L
(
i
d
r
)
∉
U
p
d
a
t
e
T
L), requests to update the reputation of node i
d will be denied and the reputation of i
d will be preserved.
(3)
If the current reputation ofi
d is less than r
e
p
t
h
r
e
s
h
o
d and authority node i
d
x requests to update the reputation of node i
d, where c
u
r
r
e
n
t
T
L
(
i
d
x
)
∈
U
p
d
a
t
e
T
L and r
e
p
0
⪯
r
e
p
x, then this request will be approved and the reputation of i
d will be updated to r
e
p
0.Example 30.
Let the update policy of nodey be r
e
p
0
⊳
Y
≥
10
r
e
p
1
⊳
T
ϕ and let its current reputation be r
e
p
0. In this case, if at least 10 nodes at a given period and location send requests to update the reputation of x to r
e
p
0, then the reputation will be updated.


### 8.3. Order Relation

It is possible that a single node owns two update policies, with one policy being stricter than the other. In this case, an order relation can be constructed to decrease the consumption of computing resources. Let≤
p denote that is stricter than; that is, if can be adopted, then can be used. ≤
p is recursively defined as follows (note that only r
u
l
e
a
u
t
h
o
r
i
t
y is considered here):
(7)
≤
p
a
1
:
ϕ
≤
p
u
p
d
a
t
e
p
≤
p
a
2
:
r
e
p
1
⪯
r
e
p
2
u
p
d
a
t
e
p
1
≤
p
u
p
d
a
t
e
p
2
r
e
p
1
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
1
≤
p
r
e
p
2
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
2
.≤
p
a
1 shows that the empty policy is the loosest because it can be used anywhere and anytime; ≤
p
a
2 denotes that if (1)  r
e
p
2 is greater than or equal to r
e
p
1 and (2)  u
p
d
a
t
e
p
2 is stricter than u
p
d
a
t
e
p
1, then r
e
p
2
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
2 is stricter than r
e
p
1
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
1.To study the properties of≤
p, we define the necessary function f
i
r
s
t, which maps policy to the reputation, as follows:
(8)
f
i
r
s
t
(
p
r
e
n
e
w
)
=
{
r
e
p
if
p
r
e
n
e
w
≡
r
e
p
⊳
c
p
r
e
n
e
w
′
⌀
otherwise
.Proposition 31.
Ifu
p
d
a
t
e
p
1
≤
p
u
p
d
a
t
e
p
2, then first(
u
p
d
a
t
e
p
1
)
⪯
f
i
r
s
t
(
u
p
d
a
t
e
p
2
).Proposition 32.
Ifu
p
d
a
t
e
p
1
≤
p
u
p
d
a
t
e
p
2 and r
e
p
1
⪯
r
e
p
2, then u
p
d
a
t
e
p
1
[
r
e
p
1/f
i
r
s
t
(
u
p
d
a
t
e
p
1
)
]
≤
p
u
p
d
a
t
e
p
2  [
r
e
p
2/f
i
r
s
t
(
u
p
d
a
t
e
p
2
)
].Theorem 33.
(
P
,
≤
p
) is a total order, where P is a set of policies.Theorem 34.
For any nonempty policiesu
p
d
a
t
e
p
1 and u
p
d
a
t
e
p
2, such that u
p
d
a
t
e
p
1
≤
p
u
p
d
a
t
e
p
2, if there exists a nonempty policy u
p
d
a
t
e
p
x with i
d: u
p
d
a
t
e
p
2
⇒
i
d: u
p
d
a
t
e
p
x, then there also exists a nonempty policy u
p
d
a
t
e
p
y with i
d: u
p
d
a
t
e
p
1
⇒
i
d: u
p
d
a
t
e
p
y and u
p
d
a
t
e
p
y
≤
p
u
p
d
a
t
e
p
x
.Proof.
Letu
p
d
a
t
e
p
2 be p
20
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
x. From i
d
:
u
p
d
a
t
e
p
2
⇒
i
d
:
u
p
d
a
t
e
p
x and ruleauthority, we have i
d
r
∈
I
D with c
u
r
r
e
n
t
R
E
P
(
i
d
r
)
=
r
e
p
r, c
u
r
r
e
n
t
T
L
(
i
d
r
)
∈
U
p
d
a
t
e
T
L, r
e
p
≺
r
e
p
t
h
e
r
s
h
h
o
l
d, c
u
r
r
e
n
t
R
E
P
(
i
d
)
≺
r
e
p
t
h
e
r
s
h
h
o
l
d, and r
e
p
t
h
e
r
s
h
h
o
l
d
⪯
c
u
r
r
e
n
t
R
E
P
(
i
d
r
). Let u
p
d
a
t
e
p
1 be p
10
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
y
i. Because u
p
d
a
t
e
p
1
≤
p
u
p
d
a
t
e
p
2, we have r
e
p
10
⪯
r
e
p
20 and u
p
d
a
t
e
p
y
i
≤
p
u
p
d
a
t
e
p
x. Because r
u
l
e
a
u
t
h
o
r
i
t
y, we have i
d
:
u
p
d
a
t
e
p
1
⇒
i
d
:
u
p
d
a
t
e
p
y
i
[
r
e
p
10
/
c
u
r
r
e
n
t
R
E
P
(
i
d
)
]. From Proposition 32, we have u
p
d
a
t
e
p
y
≤
p
u
p
d
a
t
e
p
x, where u
p
d
a
t
e
p
y
=
u
p
d
a
t
e
p
y
i
[
r
e
p
10
/
c
u
r
r
e
n
t
R
E
P
(
i
d
)
].


## 8.1. Authority-Based Update Mechanisms (AUM)

InA
U
M, only the authority node can update the reputation of other nodes. A node is called an authority node if its reputation is greater than or equal to a given threshold r
e
p
a
u
t
h, where r
e
p
a
u
t
h represents the authority reputation. To formally define semantics, we first provide the following definitions.c
u
r
r
e
n
t
T
L: I
D
→
C
B  2
L
L
O
C returns the current time and the set of current logical locations for a given node.U
p
d
a
t
e
T
L
⊆
L
T
×
L
L
O
C is a subset of the product of L
T and L
L
O
C. A node is granted the update permission, only if its current time and one of its current logical locations belong to the set U
p
d
a
t
e
T
L. In other words, node i
d can update the reputation of other nodes, only if c
u
r
r
e
n
t
T
L
(
i
d
)
∈
U
p
d
a
t
e
T
L  (let c
u
r
r
e
n
t
T
L
(
i
d
)
=
(
c
b,{
l
l
o
c
1
,
…
,
l
l
o
c
n
}
) and U
p
d
a
t
e
T
L
=
{
(
l
t
i
1, l
l
o
c
i
1
),…,(
l
t
i
m, l
l
o
c
i
m
)
}, we define c
u
r
r
e
n
t
T
L
(
i
d
)
∈
U
p
d
a
t
e
T
L, if and only if there exists (
l
t
i
l
,
l
l
o
c
i
l
)
∈
U
p
d
a
t
e
T
L such that c
b
∈
l
t
i
l and l
l
o
c
k
=
l
l
o
c
i
l, w
h
e
r
e
1
≤
k
≤
n
).The formal semantics of AUM are as follows:(5)
r
u
l
e
a
u
t
h
o
r
i
t
y
:
c
u
r
r
e
n
t
R
E
P
(
i
d
r
)
=
r
e
p
r
c
u
r
r
e
n
t
T
L
(
i
d
r
)
∈
U
p
d
a
t
e
T
L
r
e
p
,
c
u
r
r
e
n
t
R
E
P
(
i
d
)
≺
r
e
p
t
h
e
r
s
h
h
o
l
d
r
e
p
r
i
d
:
r
e
p
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
⟹
i
d
:
u
p
d
a
t
e
p
[
r
e
p
/
c
u
r
r
e
n
t
R
E
P
(
i
d
)
]
r
u
l
e
ϕ
:
i
d
:
⌀
⟹
⌀
.The predicatea
u
t
h
u
p
d
a
t
e
(
r
e
p
r
) is true, if and only if there exists i
d
∈
I
D with c
u
r
r
e
n
t
R
E
P
(
i
d
r
)
=
r
e
p
r,  c
u
r
r
e
n
t
T
L
(
i
d
r
)
∈
U
p
d
a
t
e
T
L, r
e
p
≺
r
e
p
t
h
e
r
s
h
h
o
l
d, c
u
r
r
e
n
t
R
E
P
(
i
d
)
≺
r
e
p
t
h
e
r
s
h
h
o
l
d, and r
e
p
t
h
e
r
s
h
h
o
l
d
⪯
r
e
p
r. The rule r
u
l
e
a
u
t
h
o
r
i
t
y states that the reputation of node i
d can be updated to r
e
p if the following conditions are satisfied: (1) r
e
p
t
h
e
r
s
h
h
o
l
d
⪯
c
u
r
r
e
n
t
R
E
P
(
i
d
r
); that is, node i
d
r is an authority node. (2)  c
u
r
r
e
n
t
T
L
(
i
d
r
)
∈
U
p
d
a
t
e
T
L; that is, node i
d
r satisfies the temporal and spatial constraint. (3) The current reputation of node i
d and its reputation after update are both greater than or equal to r
e
p
t
h
r
e
s
h
o
l
d.AUM can prevent a node’s reputation from being illegally updated even if authority nodes are lost. For example, the authority nodex in the location l
l
o
c can update the reputation of others. If x is lost, it may not be in the location l
l
o
c. Let x be in the location l
o
c
t
h
e
f
t with l
o
c
t
h
e
f
t
≠
l
l
o
c, therefore, making c
u
r
r
e
n
t
T
L
(
i
d
)
∉
U
p
d
a
t
e
T
L. This means that x no longer has the ability to update the reputation of other nodes.


## 8.2. Election-Based Update Mechanisms (EUM)

AlthoughA
U
M can be used to decrease the risk caused by the loss of nodes, authority nodes are security-critical because of the huge risks involved if they are compromised. In order to solve this problem, we propose E
U
M. In E
U
M, a group of nodes with a lower reputation are able to update the reputation of others through elections. When the majority of voters (nodes) agree on an update, the reputation of a specific node can be updated. In order to precisely define this mechanism, we first define the update function f
:
I
D
×
I
D
×
R
E
P
→
{
0,1
}, which maps I
D
×
I
D
×
R
E
P to {
0,1
}: If a voter i
d requests to update the reputation of candidate i
d
c to r
e
p
c, then f
(
i
d
c
,
i
d
,
r
e
p
c
)
=
1. The formal semantics of E
U
M is as follows:
(6)
r
u
l
e
e
l
e
c
t
i
o
n
:
Y
≥
r
i
d
c
:
r
e
p
c
⊳
Y
≥
r
u
p
d
a
t
e
p
⟹
i
d
:
u
p
d
a
t
e
p
[
r
e
p
c
/
c
u
r
r
e
n
t
R
E
P
(
i
d
c
)
]
,
where Y
=
∑
i
d
I
D
T
L
f
(
i
d
c
,
i
d
,
r
e
p
c
), I
D
T
L
=
{
x
∈
I
D
∣
c
u
r
r
e
n
t
T
L
(
x
)
∈
U
p
d
a
t
e
T
L
c
u
r
r
e
n
t
T
L
(
x
)
∈
U
p
d
a
t
e
T
L
}, and r is a natural number. R
u
l
e
e
l
e
c
t
i
o
n shows that if at least r nodes satisfying the given time constraints in the given areas request to update the reputation of node i
d to r
e
p, then these requests will be approved and id’s reputation will be updated. Because r
u
l
e
e
l
e
c
t
i
o
n can update the reputation of any other node, r must be carefully defined, especially in networks where malicious nodes are dominant. Generally, r could be equal to ⌈
N
/
2
⌉ or ⌈
2
N
/
3
⌉, where N is the number of voters.Example 29.
Let the update policy of nodei
d be r
e
p
0
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
r
e
p
1
⊳
T
ϕ; we have the following results.(1)
If the current reputation ofi
d is greater than r
e
p
t
h
r
e
s
h
o
l
d, then the reputation of x will be preserved.
(2)
If authority nodei
d
r, which is not located in the given areas or does not satisfy the given time constraints (i.e., c
u
r
r
e
n
t
T
L
(
i
d
r
)
∉
U
p
d
a
t
e
T
L), requests to update the reputation of node i
d will be denied and the reputation of i
d will be preserved.
(3)
If the current reputation ofi
d is less than r
e
p
t
h
r
e
s
h
o
d and authority node i
d
x requests to update the reputation of node i
d, where c
u
r
r
e
n
t
T
L
(
i
d
x
)
∈
U
p
d
a
t
e
T
L and r
e
p
0
⪯
r
e
p
x, then this request will be approved and the reputation of i
d will be updated to r
e
p
0.Example 30.
Let the update policy of nodey be r
e
p
0
⊳
Y
≥
10
r
e
p
1
⊳
T
ϕ and let its current reputation be r
e
p
0. In this case, if at least 10 nodes at a given period and location send requests to update the reputation of x to r
e
p
0, then the reputation will be updated.


## 8.3. Order Relation

It is possible that a single node owns two update policies, with one policy being stricter than the other. In this case, an order relation can be constructed to decrease the consumption of computing resources. Let≤
p denote that is stricter than; that is, if can be adopted, then can be used. ≤
p is recursively defined as follows (note that only r
u
l
e
a
u
t
h
o
r
i
t
y is considered here):
(7)
≤
p
a
1
:
ϕ
≤
p
u
p
d
a
t
e
p
≤
p
a
2
:
r
e
p
1
⪯
r
e
p
2
u
p
d
a
t
e
p
1
≤
p
u
p
d
a
t
e
p
2
r
e
p
1
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
1
≤
p
r
e
p
2
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
2
.≤
p
a
1 shows that the empty policy is the loosest because it can be used anywhere and anytime; ≤
p
a
2 denotes that if (1)  r
e
p
2 is greater than or equal to r
e
p
1 and (2)  u
p
d
a
t
e
p
2 is stricter than u
p
d
a
t
e
p
1, then r
e
p
2
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
2 is stricter than r
e
p
1
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
1.To study the properties of≤
p, we define the necessary function f
i
r
s
t, which maps policy to the reputation, as follows:
(8)
f
i
r
s
t
(
p
r
e
n
e
w
)
=
{
r
e
p
if
p
r
e
n
e
w
≡
r
e
p
⊳
c
p
r
e
n
e
w
′
⌀
otherwise
.Proposition 31.
Ifu
p
d
a
t
e
p
1
≤
p
u
p
d
a
t
e
p
2, then first(
u
p
d
a
t
e
p
1
)
⪯
f
i
r
s
t
(
u
p
d
a
t
e
p
2
).Proposition 32.
Ifu
p
d
a
t
e
p
1
≤
p
u
p
d
a
t
e
p
2 and r
e
p
1
⪯
r
e
p
2, then u
p
d
a
t
e
p
1
[
r
e
p
1/f
i
r
s
t
(
u
p
d
a
t
e
p
1
)
]
≤
p
u
p
d
a
t
e
p
2  [
r
e
p
2/f
i
r
s
t
(
u
p
d
a
t
e
p
2
)
].Theorem 33.
(
P
,
≤
p
) is a total order, where P is a set of policies.Theorem 34.
For any nonempty policiesu
p
d
a
t
e
p
1 and u
p
d
a
t
e
p
2, such that u
p
d
a
t
e
p
1
≤
p
u
p
d
a
t
e
p
2, if there exists a nonempty policy u
p
d
a
t
e
p
x with i
d: u
p
d
a
t
e
p
2
⇒
i
d: u
p
d
a
t
e
p
x, then there also exists a nonempty policy u
p
d
a
t
e
p
y with i
d: u
p
d
a
t
e
p
1
⇒
i
d: u
p
d
a
t
e
p
y and u
p
d
a
t
e
p
y
≤
p
u
p
d
a
t
e
p
x
.Proof.
Letu
p
d
a
t
e
p
2 be p
20
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
x. From i
d
:
u
p
d
a
t
e
p
2
⇒
i
d
:
u
p
d
a
t
e
p
x and ruleauthority, we have i
d
r
∈
I
D with c
u
r
r
e
n
t
R
E
P
(
i
d
r
)
=
r
e
p
r, c
u
r
r
e
n
t
T
L
(
i
d
r
)
∈
U
p
d
a
t
e
T
L, r
e
p
≺
r
e
p
t
h
e
r
s
h
h
o
l
d, c
u
r
r
e
n
t
R
E
P
(
i
d
)
≺
r
e
p
t
h
e
r
s
h
h
o
l
d, and r
e
p
t
h
e
r
s
h
h
o
l
d
⪯
c
u
r
r
e
n
t
R
E
P
(
i
d
r
). Let u
p
d
a
t
e
p
1 be p
10
⊳
a
u
t
h
u
p
d
a
t
e
(
r
e
p
r
)
u
p
d
a
t
e
p
y
i. Because u
p
d
a
t
e
p
1
≤
p
u
p
d
a
t
e
p
2, we have r
e
p
10
⪯
r
e
p
20 and u
p
d
a
t
e
p
y
i
≤
p
u
p
d
a
t
e
p
x. Because r
u
l
e
a
u
t
h
o
r
i
t
y, we have i
d
:
u
p
d
a
t
e
p
1
⇒
i
d
:
u
p
d
a
t
e
p
y
i
[
r
e
p
10
/
c
u
r
r
e
n
t
R
E
P
(
i
d
)
]. From Proposition 32, we have u
p
d
a
t
e
p
y
≤
p
u
p
d
a
t
e
p
x, where u
p
d
a
t
e
p
y
=
u
p
d
a
t
e
p
y
i
[
r
e
p
10
/
c
u
r
r
e
n
t
R
E
P
(
i
d
)
].


## 9. Verification of Security Policy

The STRAC model has many features that could interact with each other, causing conflict and inconsistency between security policies. As a result, security policies must be verified before they are applied. Tediousness and proneness of manual analyses make automatic verification necessary. UPPAAL [28] is an integrated model checker for modeling, validation, and verification of real-time systems modeled as networks of timed automata. In this study, UPPAAL is used to verify whether the policy conforms to security requirements or not. When requirements are violated, the tool pictorially shows how the property has been violated and generates a counterexample to help security designers fix the policy.To illustrate how to formally specify and verify a STRAC policy, we consider smart home applications. We assume the existence of four smart devices in this example: (1) a TV set(
T
V
), (2) an air conditioning (
A
C
) unit, (3) a microwave (
M
W
), and (4) an electric rice cooker (
R
C
). Each of these devices can be remotely controlled using mobile terminals. We also stipulate that parents and their children can use these devices only in the office, school, and home. In order to provide the necessary security for these devices, we make the following security policies: (1) the TV set and the A
C can be closed or opened either remotely or locally because of the low heat produced by such devices; (2) the R
C can only be opened locally but can be closed remotely because of the high degree of heat that it produces; (
3
) the M
W can be opened by parents either remotely or locally but cannot be opened by children remotely, because of the heat produced by the M
W and the need to configure a time parameter, which can be performed only by parents; (
4
) because of the limitations regarding power load, the maximum number of devices that is able to run simultaneously is set to three; (
5
) every device only runs during the specified time.


### 9.1. Model

We integrate the components of STRAC as follows:I
D
=
{
0,1
,
2
} is a set of mobile terminal IDs based on the assumptions that (1) Terminal 0 is owned by children and is used in school and at home, (2) Terminals 1 and 2 are owned by parents and are used in multiple locations (school, office, and home), and (
3
)  R
E
P
=
{
h
i
g
h
R
e
p, l
o
w
R
e
p
}, where h
i
g
h
R
e
p and l
o
w
R
e
p denote high reputation and low reputation, respectively. We assume that the reputation of Terminal 0 is low and the others are high. L
T
=
{
T
V
t
i
m
e, A
C
t
i
m
e, M
W
t
i
m
e, R
C
t
i
m
e
} is a set of logic constraint times, for operating T
V, A
C, M
W, and R
C. L
L
O
C
=
{
h
o
m
e, o
f
f
i
c
e, s
c
h
o
o
l
}, O
P
=
{
o
p
e
n, c
l
o
s
e, c
o
n
f
i
g
}, O
=
{
T
V, A
C, M
W, R
C
}, and P
E
R
M
=
{
o
p
e
n, c
l
o
s
e
}
×
O
∪
{
(
c
o
n
f
i
g, M
W
)
}; A
c
c
Z
o
n
e is the product of R
E
P, L
T, and L
O
C. P
A is a core component determined by control policies, as shown in Table 2. In Table 2, the product of the left and right columns of any row is an element of P
A. For example, {
(
o
p
e
n, T
V
)
}
×
R
E
P
×
{
T
V
t
i
m
e
}
×
L
L
O
C
⊆
P
A. According to Table 2, A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d and p
e
r
m
A
s
s
i
g
n
e
d can be obtained (not discussed in this paper). For any access request, a decision can be made. For example, a child requesting to open M
W in s
c
h
o
o
l will be denied.Table 2
PA of smart home applications.
PERM
Access zones
(open, TV)
R
E
P
×
{
T
V
t
i
m
e
}
×
L
L
O
C
(open, AC)
R
E
P
×
{
A
C
t
i
m
e
}
×
L
L
O
C
(open, MW)
{
h
i
g
h
R
e
p
}
×
{
M
W
t
i
m
e
}
×
L
L
O
C
(config, MW)
{
h
i
g
h
R
e
p
}
×
{
M
W
t
i
m
e
}
×
L
L
O
C
(open, RC)
R
E
P
×
{
R
C
t
i
m
e
}
×
{
h
o
m
e
}
{
c
l
o
s
e
}
×
O
R
E
P
×
L
T
×
L
L
O
C


### 9.2. Policy Verification

In the home applications discussed above, three kinds of entities exist: mobile terminals, RM (as shown in Section, RM denotes reference monitor), and the related devices(
T
V, A
C, M
W, and R
C
). In UPPAAL, these entities are denoted as M
o
b
i
l
e
T
e
r
m, R
M, and D
e
v
i
c
e, respectively. In this scenario, mobile terminals send access requests to the RM. Upon receiving these requests, RM retrieves the stored access rule table, decides whether to approve these requests, and sends the result to the controlled devices.An access request consists of six parameters (as shown in Section3.1, only three parameters are needed; however, in UPPAAL, we cannot get the current time; therefore, the t
i
m
e parameter is necessary. For simplicity, both l
o
c
a
t
i
o
n and t
i
m
e are provided here): t
m
_
r
m
_
i
d (ID of the mobile terminals), t
m
_
r
m
_
l
o
c (location of the mobile terminals), tm_rm_time (current time), t
m
_
r
m
_
d
e
v (target device), t
m
_
r
m
_
o
p (operation to perform on the target device), and t
m
_
r
m
_
M
W
_
t
i
m
e (timer for M
W). Figure 4 gives the timed automata of mobile terminals, where i
d is an input parameter, T
e
r
m
T
o
R
M
[
i
d
] is a channel, and l
o
c
_
t is a set of all locations (
h
o
m
e, s
c
h
o
o
l, and o
f
f
i
c
e
). The remaining variables are similar to l
o
c
_
t.Figure 4
Timed automata of mobile terminals.As shown in Figure5, R
M receives access requests from the channel T
e
r
m
T
o
R
M
[
i
d
], checks the state (busy or free) of the controlled device, and makes a decision according to the reputation and location of the mobile terminals and the current time. This decision is then sent to the corresponding device.Figure 5
Timed automata of RM.Figure6 illustrates the timed automata of controlled devices. The initial state of each device is DevOff. When the instruction o
p
e
n arrives, the corresponding device starts to run. If the instruction c
l
o
s
e arrives, the corresponding device stops running. In M
W, d
e
v
_
c
o
n
f
i
g is used to store the time parameter of the M
W timer.Figure 6
Timed automata of controlled devices.The composition (MobileTerm∥
RM
∥ Device) of the above three timed automata forms a timed automation network, and we can use this network to verify policies. In our studies, three properties are verified: (1) “deadlock must be avoided in smart home applications.” This can be specified as “A[
] not deadlock” by using computation tree logic (CTL); (2) the number of simultaneously running devices is always less than or equal to three. This can be specified as “A[
] not (Device(TV).DevOn and Device(AC).DevOn and Device(RC).Heating and Device(
M
W
).DevOn)”; (3) when the parents open a microwave in office, the microwave would always switch to the R
i
p
e state, which is “(tm_rm_id==1&&tm_rm_loc==office&& tm_rm_time==8&&tm_rm_dev==M
W&& tm_rm_op== open) -->Device(
M
W
).Ripe,” where the reputation of Terminal 1 (belonging to the parents) is high and the current time (m_rm_time==8) is within the work time of M
W.We use UPPAAL to verify the three properties, and the result shows that the first two properties are true. This means that the system is deadlock-free and that the number of simultaneously running devices is always less than or equal to three. Property (3) is proven to be false, meaning that, even when parents start the microwave while in the office, the microwave does not necessarily switch to theR
i
p
e state. A counterexample is as follows: if parents start the microwave and the rice cooker at the same time in the office, the child will not be able to start the air conditioning and watch TV due to the power load limitation. In this case, children could stop the microwave, thus preventing it from switching to the R
i
p
e state.


## 9.1. Model

We integrate the components of STRAC as follows:I
D
=
{
0,1
,
2
} is a set of mobile terminal IDs based on the assumptions that (1) Terminal 0 is owned by children and is used in school and at home, (2) Terminals 1 and 2 are owned by parents and are used in multiple locations (school, office, and home), and (
3
)  R
E
P
=
{
h
i
g
h
R
e
p, l
o
w
R
e
p
}, where h
i
g
h
R
e
p and l
o
w
R
e
p denote high reputation and low reputation, respectively. We assume that the reputation of Terminal 0 is low and the others are high. L
T
=
{
T
V
t
i
m
e, A
C
t
i
m
e, M
W
t
i
m
e, R
C
t
i
m
e
} is a set of logic constraint times, for operating T
V, A
C, M
W, and R
C. L
L
O
C
=
{
h
o
m
e, o
f
f
i
c
e, s
c
h
o
o
l
}, O
P
=
{
o
p
e
n, c
l
o
s
e, c
o
n
f
i
g
}, O
=
{
T
V, A
C, M
W, R
C
}, and P
E
R
M
=
{
o
p
e
n, c
l
o
s
e
}
×
O
∪
{
(
c
o
n
f
i
g, M
W
)
}; A
c
c
Z
o
n
e is the product of R
E
P, L
T, and L
O
C. P
A is a core component determined by control policies, as shown in Table 2. In Table 2, the product of the left and right columns of any row is an element of P
A. For example, {
(
o
p
e
n, T
V
)
}
×
R
E
P
×
{
T
V
t
i
m
e
}
×
L
L
O
C
⊆
P
A. According to Table 2, A
c
c
Z
o
n
e
A
s
s
i
g
n
e
d and p
e
r
m
A
s
s
i
g
n
e
d can be obtained (not discussed in this paper). For any access request, a decision can be made. For example, a child requesting to open M
W in s
c
h
o
o
l will be denied.Table 2
PA of smart home applications.
PERM
Access zones
(open, TV)
R
E
P
×
{
T
V
t
i
m
e
}
×
L
L
O
C
(open, AC)
R
E
P
×
{
A
C
t
i
m
e
}
×
L
L
O
C
(open, MW)
{
h
i
g
h
R
e
p
}
×
{
M
W
t
i
m
e
}
×
L
L
O
C
(config, MW)
{
h
i
g
h
R
e
p
}
×
{
M
W
t
i
m
e
}
×
L
L
O
C
(open, RC)
R
E
P
×
{
R
C
t
i
m
e
}
×
{
h
o
m
e
}
{
c
l
o
s
e
}
×
O
R
E
P
×
L
T
×
L
L
O
C


## 9.2. Policy Verification

In the home applications discussed above, three kinds of entities exist: mobile terminals, RM (as shown in Section, RM denotes reference monitor), and the related devices(
T
V, A
C, M
W, and R
C
). In UPPAAL, these entities are denoted as M
o
b
i
l
e
T
e
r
m, R
M, and D
e
v
i
c
e, respectively. In this scenario, mobile terminals send access requests to the RM. Upon receiving these requests, RM retrieves the stored access rule table, decides whether to approve these requests, and sends the result to the controlled devices.An access request consists of six parameters (as shown in Section3.1, only three parameters are needed; however, in UPPAAL, we cannot get the current time; therefore, the t
i
m
e parameter is necessary. For simplicity, both l
o
c
a
t
i
o
n and t
i
m
e are provided here): t
m
_
r
m
_
i
d (ID of the mobile terminals), t
m
_
r
m
_
l
o
c (location of the mobile terminals), tm_rm_time (current time), t
m
_
r
m
_
d
e
v (target device), t
m
_
r
m
_
o
p (operation to perform on the target device), and t
m
_
r
m
_
M
W
_
t
i
m
e (timer for M
W). Figure 4 gives the timed automata of mobile terminals, where i
d is an input parameter, T
e
r
m
T
o
R
M
[
i
d
] is a channel, and l
o
c
_
t is a set of all locations (
h
o
m
e, s
c
h
o
o
l, and o
f
f
i
c
e
). The remaining variables are similar to l
o
c
_
t.Figure 4
Timed automata of mobile terminals.As shown in Figure5, R
M receives access requests from the channel T
e
r
m
T
o
R
M
[
i
d
], checks the state (busy or free) of the controlled device, and makes a decision according to the reputation and location of the mobile terminals and the current time. This decision is then sent to the corresponding device.Figure 5
Timed automata of RM.Figure6 illustrates the timed automata of controlled devices. The initial state of each device is DevOff. When the instruction o
p
e
n arrives, the corresponding device starts to run. If the instruction c
l
o
s
e arrives, the corresponding device stops running. In M
W, d
e
v
_
c
o
n
f
i
g is used to store the time parameter of the M
W timer.Figure 6
Timed automata of controlled devices.The composition (MobileTerm∥
RM
∥ Device) of the above three timed automata forms a timed automation network, and we can use this network to verify policies. In our studies, three properties are verified: (1) “deadlock must be avoided in smart home applications.” This can be specified as “A[
] not deadlock” by using computation tree logic (CTL); (2) the number of simultaneously running devices is always less than or equal to three. This can be specified as “A[
] not (Device(TV).DevOn and Device(AC).DevOn and Device(RC).Heating and Device(
M
W
).DevOn)”; (3) when the parents open a microwave in office, the microwave would always switch to the R
i
p
e state, which is “(tm_rm_id==1&&tm_rm_loc==office&& tm_rm_time==8&&tm_rm_dev==M
W&& tm_rm_op== open) -->Device(
M
W
).Ripe,” where the reputation of Terminal 1 (belonging to the parents) is high and the current time (m_rm_time==8) is within the work time of M
W.We use UPPAAL to verify the three properties, and the result shows that the first two properties are true. This means that the system is deadlock-free and that the number of simultaneously running devices is always less than or equal to three. Property (3) is proven to be false, meaning that, even when parents start the microwave while in the office, the microwave does not necessarily switch to theR
i
p
e state. A counterexample is as follows: if parents start the microwave and the rice cooker at the same time in the office, the child will not be able to start the air conditioning and watch TV due to the power load limitation. In this case, children could stop the microwave, thus preventing it from switching to the R
i
p
e state.


## 10. Experiments

We develop a prototype (shown in Figure7) that implements STRAC. In our prototype, we use a network topology consisting of 10 terminal nodes (TeNs) uniformly deployed in a × area with TeNs surrounding a sink node (SiN), where Texas Instruments CC2530 chips with 8-KB RAM and 256-KB programmable flash are adopted for the TeNs and an ST Microelectronics STM32 chip with 64-KB RAM and 512-KB programmable flash was used for the SiN (CC2530 and STM32 chips are widely used as wireless transceivers and data processors in industry). The ZigBee protocol is used for communications between the TeNs and the SiN. The ARC component is mounted on the TeNs while RMC components are mounted on the SiN. ARC and RMC are written as traditional C programs.Figure 7
STRAC prototype.Generally, heavyweight database servers, such as MySQL, are not appropriate for terminal nodes because of their limitations in storage and computing resources. To solve this problem, we implement a table query algorithm in our prototype and we also design two database tables: an ID-RTL table that maps node ID to an RTL triple (the reputation of the node, the current logic time, and the current time location) and an access rule table that stores PA (as shown in Section5, PA connects permissions with access zones). The ID-RTL table is integrated into the PEP components and is only accessible by TeNs and PDP, while the access rule table is mounted into PDP components and is only accessible by PEP. Our experiment setup is as follows: (1) reputation is set to 5 ratings, (2) TeNs could move into 100 different areas at 10 logical time periods, and (3) TeNs may perform 3 operations on 50 objects. After P
A is explicitly defined, a series of experiments are conducted. The results reported in this section are averaged over 10 runs.Experiment 1 (correctness of implementation).
To evaluate correctness of implementation, we create two groups (A and B) of access requests in two local files: any request of Group A is in the access rule table; that is, any request from should be approved; all elements in Group are out of the access rule table; that is, any request from should be rejected. Groups A and B allow us to test whether our prototype works as anticipated. The experiment result shows that all requests from group A are approved and all requests from group B are rejected. This fact demonstrates the correctness of our implementation.Experiment 2 (storage resources).
In this experiment, two cases are considered inP
A one is “given one permission, the number of its access zones is randomly generated” (called random scheme); the other is “given one permission, the number of its access zones is constant” (called constant scheme). The experiment result is as follows.Random Scheme
.If PA is compiled with the nonlattice strategy, 7500 access rules occupy 36.5 KB of programmable flash; however, if the lattice strategy is adopted, only 3750 access rules are needed; as a result, 36.62 KB of programmable flash is consumed, which is about 100.3% of memory used by the nonlattice strategy.Constant Scheme. If PA is compiled with the nonlattice strategy, 15000 access rules occupy 73.24 KB of programmable flash; however, if the lattice strategy is adopted, only 3900 access rules are needed; as a result, 30.48 KB of programmable flash is consumed, which is about 41.6% of memory used by the nonlattice strategy.Note. In this experiment, PA is stored via a two-dimensional array. This means that for any two permissions, their consumed storages are the same and equal to s
i
z
e
o
f (a
r
r
a
y)/l
e
n
g
t
h (a
r
r
a
y). As a result, in the random scheme,the storage occupied by the lattice strategy is slightly greater than that of the lattice strategy. If PA is stored via files or pointers, the occupied storage will approach the constant scheme.Experiment 3 (average response time,A
R
T).
To evaluate the response time of our scheme, we add a GroupC of access requests: almost half of the access requests in Group C are in the access rule table. Each TeN continuously sends 1400 access requests to the SeN. The experiments show that the A
R
T, which is the average delay from receiving a request to returning the response, is 21.4 ms if the nonlattice policy is adopted. The A
R
T is reduced to 18.6 ms if the lattice policy is used, which is about 86.9% of the time used by the nonlattice strategy.
Experiments2 and 3 show that the lattice policy is better overall than nonlattice policy and that the storage resource consumed and the response time of our model are acceptable for the sensing layer of the IoT.


## 11. Conclusions

The IoT presents new types of architectures, vulnerabilities, and requirements. Consequently, existing access control models have to be revised to accommodate these changes. Although spatiotemporal access models have been proposed in previous studies, most of them ignore some important characteristics of the sensing layer of the IoT. In this paper, we abstract the basic characteristics of the IoT’s sensing layer and propose a model (called STRAC) that combines space and time with reputation for access control of the IoT’s sensing layer. Our model solves the problem of decidingw
h
e
n and w
h
e
r
e to authorize access requests and w
h
o is able to access information by using spatial/temporal information, and it uses nondeterministic/stochastic authorizations to deal with unstable communications. These methods either provide better security or improve the QoS. In order to more precisely manage the reputation of nodes, we present a novel mechanism to update reputation and demonstrate its security. STRAC overcomes the inadequacies of existing access controls while acting as an access control foundation for the sensing layer of the IoT. In future work, we will design a scheme to find the optimal trade-off between security and QoS.



---

*Source: 671038-2014-08-06.xml*