SEPD: An Access Control Model for Resource Sharing in an IoT Environment

Abstract

In an open Internet-of-Things (IoT) environment, the chance encounters of smart devices have made it difficult to articulate access control policies for complete strangers. Based on the metaphor of public sphere, the access control model SEPD is proposed to ease policy administration and facilitate trust inspiration for IoT devices. We articulate a system architecture for SEPD, and offer an in-depth study of its access control policies, known as presence policies. In particular, we characterize when presence policies are resilient against half-truth attacks, devise a policy language based on Temporal Constraint Networks, and empirically profile the efficiency of constructing proofs of compliance for presence policies.

Appendices

A Temporal Constraint Networks

Allen identifies 13 basic relations between any two time intervals [2, 26]. Those relations are precedes (p), meets (m), overlaps (o), starts (s), during (d), finishes (f), and their respective converse relations (i.e., preceded by [si], met by [mi], overlapped by [o], started by [si], contains [di], and finished by [fi]), as well as equality (eq). Table 1 gives the definition of these relations. These 13 basic relations capture all the possible relations between two intervals.

Let $\mathbf B = \{p, pi, m, mi, o, oi, s, si, d, di, f, fi, eq\}$ be the set of all basic relations. $\mathbf B$ is called the universal relation. We write $X \mathbf{r } Y$ to assert that interval X is related to interval Y in the basic relation $\mathbf{r }$. Given $X, Y \in \mathsf {Int}$, there exists exactly one basic relation $\mathbf{r } \in \mathbf B$ such that $X \mathbf{r } Y$. Given $\mathbf{R } \subseteq \mathbf B$, we write $X \mathbf{R } Y$ to assert that there exists $\mathbf{r } \in \mathbf{R }$ such that $X \mathbf{r } Y$. The set $\mathbf{R }$ is called a disjunctive relation.

A temporal constraint network (TCN) is an edge-labeled, complete, directed graph $\varTheta = (N, C)$, so that each directed edge $(u, v) \in N \times N$ is associated with a disjunctive relation $C(u, v) \subseteq \mathbf B$. An instantiation of $\varTheta$ is a function $m : N \rightarrow \mathsf {Int}$. Instantiation m satisfies $\varTheta$ if and only if $m(u) \,C(u, v)\, m(v)$ for every edge $(u, v) \in N \times N$. We say that $\varTheta$ is consistent if and only if there exists an instantiation that satisfies $\varTheta$.

Table 1. Allen’s 13 basic relations between intervals $X = [x_1, x_2]$ and $Y = [y_1, y_2]$.

B Proofs

1.1 B.1 Proof of Theorem 1

Statement (1): Suppose $P$ is semantically monotonic. Consider $\varPi , \varPi ' \in \mathsf {PoC}$ and $t \in \mathbb {R}$. If $\varPi \sqsubseteq _R \varPi '$ via the function $f : \varPi \rightarrow \varPi '$, then we have the following containment:

$$ \cup \varPi = \bigcup _{I \in \varPi } I \subseteq \bigcup _{I \in \varPi } f(I) \subseteq \bigcup _{I ' \in \varPi '} I ' \subseteq \cup \varPi ' $$

which, by semantic monotonicity, implies $P ( \varPi ) \rightarrow P ( \varPi ' )$. $P$ is therefore R-resilient.

Statement (2): We begin by proving that R-resiliency implies syntactic monotonicity. Suppose $P$ is R-resilient. Consider $\varPi , \varPi ' \in \mathsf {PoC}$ where $\varPi \subseteq \varPi '$. Construct $f : \varPi \rightarrow \varPi '$ so that $f(I) = I$. Thus $\varPi \sqsubseteq _R \varPi '$. By the R-resiliency of $P$, we have $P ( \varPi ) \rightarrow P ( \varPi ' )$ as required by syntactic monotonicity.

Next, we demonstrate that R-resiliency implies R-reducibility. Suppose $P$ is R-resilient. Consider $\varPi \in \mathsf {PoC}$ where there exists distinct intervals $I _1, I _2 \in \varPi$ such that $I _1 \subseteq _R I _2$. Construct $f : \varPi \rightarrow \varPi \setminus \{ I _1 \}$ so that:

$$ f( I) = {\left\{ \begin{array}{ll} I _2 &{} \text {if } I = I _1 \\ I &{} \text {otherwise} \end{array}\right. } $$

Function f thus witnesses to the fact that $\varPi \sqsubseteq _R \varPi \setminus \{ I _1 \}$. By R-resiliency, we know that $P ( \varPi ) \rightarrow P ( \varPi \setminus \{ I _1 \} )$.

So far, we have demonstrated that R-resiliency implies the conjunction of syntactic monotonicity and R-reducibility. We complete the proof of Statement (1) by showing that syntactic monotonicity and R-reducibility jointly imply R-resiliency. Suppose $P$ is both syntactically monotonic and R-reducible. Consider $\varPi , \varPi ' \in \mathsf {PoC}$. If $\varPi \sqsubseteq _R \varPi '$ via the function $f : \varPi \rightarrow \varPi '$, then the following implication holds:

1.2 B.2 Proof of Theorem 2

Let $\chi = (\mathsf {wd}, \mathsf {ad}, \mathsf {ag})$, and $\mathcal {P} ^\chi = \{ P _t \}_{t \in \mathbb {R}}$. Suppose $\varPi \sqsubseteq _R \varPi '$ via the function $f : \varPi \rightarrow \varPi '$. We show in the three steps below that $P _t (\varPi ) \rightarrow P _t (\varPi ')$.

Step 1. We show that $\varPi /W \sqsubseteq _R \varPi '/W$ for every $W \in \mathsf {Int}$. To this end, we construct a function $g : \varPi /W \rightarrow \varPi '/W$ so that $X \subseteq _R g(X)$ for every $X \in \varPi /W$.

Consider an interval $I \in \varPi$. Since $I \subseteq _R f(I)$, we know the following two facts: (1) If $I \cap W \ne \emptyset$, then $f(I) \cap W \ne \emptyset$. (2) $I \cap W \subseteq _R f(I) \cap W$. Therefore, by having g maps $I \cap W$ to $f(I) \cap W$ when $I \cap W \ne \emptyset$, the requirement of $X \subseteq _R g(X)$ will be satisfied.

The problem with the above construction is that the resulting mapping g may not be functional. The latter happens when there are distinct intervals $I _1, I _2 \in \varPi$ for which $I _1 \cap W = I _2 \cap W$. To correct this, observe that if $X \subseteq _R Y _1$ and $X \subseteq _R Y _2$, then either $Y _1 \subseteq _R Y _2$ or $Y _2 \subseteq _R Y _1$, and thus we have (a) $X \subseteq _R Y _1 \cup Y _2$, and (b) either $Y _1 = Y _1 \cup Y _2$ or $Y _2 = Y _1 \cup Y _2$. We therefore define g as follows:

$$ g(X) = \bigcup _{I \in \varPi ,\,I \cap W = X} f(I) \cap W $$

The function g witnesses to the fact that $\varPi /W \sqsubseteq _R \varPi '/W$.

Step 2. We demonstrate that $admissible ( \varPi , t) \subseteq admissible ( \varPi ', t )$. By definition, a window $W$ belongs to $admissible ( \varPi , t )$ whenever $\mathsf {ad} (\varPi /W)$. But we showed in Step 1 that $\varPi /W \sqsubseteq _R \varPi '/W$. Therefore, by the R-resiliency of $\mathsf {ad}$, we also have $\mathsf {ad}(\varPi '/W)$ as a result, meaning $W \in admissible ( \varPi ', t )$. Consequently, every member of $admissible ( \varPi , t)$ is also a member of $admissible ( \varPi ', t )$.

Step 3. We can now conclude that $P _t (\varPi ) \rightarrow P _t (\varPi ')$, because the syntactic monotonicity of $\mathsf {ag}$ guarantees that $\mathsf {ag}( admissible ( \varPi , t) ) \rightarrow \mathsf {ag}( admissible ( \varPi ', t) )$.

1.3 B.3 Proof of Theorem 3

That is in $\mathsf {NP}$ is obvious. We demonstrate $\mathsf {NP}$-hardness by a reduction from graph k-colorability [17]. Given an instance $G = (V, E)$ of graph k-colorability, the reduction produces an instance $(\varTheta , DB )$ of , where $DB$ contains k distinct intervals, and $\varTheta$ is the ETCN $(V, V, \emptyset , \emptyset , C, \emptyset , \emptyset )$, such that $C(u, v) = \mathbf B \setminus \{ eq \}$ if $uv \in E$, but $C(u, v) = \mathbf B$ if $uv \not \in E$. It is easy to see that G is k-colorable if and only if .