Improving Robustness of a Popular Probabilistic Clustering Algorithm Against Insider Attacks

Abstract

Many clustering algorithms for mesh, ad hoc and Wireless Sensor Networks have been proposed. Probabilistic approaches are a popular class of such algorithms. However, it is essential to analyze their robustness against security compromise. We study the robustness of EEHCA, a popular energy efficient clustering algorithm as an example of probabilistic class in terms of security compromise. In this paper, we investigate attacks on EEHCA through analysis and experimental simulations. We analytically characterize two different attack models. In the first attack model, the attacker aims to gain control over the network by stealing network traffic, or by disrupting the data aggregation process (integrity attack). In the second attack model, the inducement of the attacker is to abridge the network lifetime (denial of service attack). We assume the clustering algorithm is running periodically and propose a detection solution by exploiting Bernoulli CUSUM charts.

Appendices

A Proof of Theorem 1

Proof

Suppose a realization of the random point process $\varPhi _b$ with number of nodes equal to $N=n$ is given. Arbitrarily compromise m nodes independent of location and each other under attack model 1. One can consider compromising nodes as a p-thinning operation with $p_r = 1- \frac{m}{n}$. As a result, legitimate nodes and malicious nodes are distributed independently according to a homogeneous spatial Poisson point processes (PPP):

$$\begin{aligned} PPP_{leg}: \lambda _{leg} = p_r \lambda _b \end{aligned}$$

(12)

$$\begin{aligned} PPP_{mal}: \lambda _{mal} = (1-p_r)\lambda _b \end{aligned}$$

(13)

Legitimate nodes become volunteer clusterheads with probability of $p_{opt}$. Hence, legitimate clusterheads and legitimate ordinary nodes are distributed as independent homogeneous spatial Poisson point processes:

$$\begin{aligned} PPP_{CH,leg}: \lambda _{CH,leg} = p_{opt} \lambda _{leg} \end{aligned}$$

(14)

$$\begin{aligned} PPP_{Ord,leg}: \lambda _{Ord,leg} = (1-p_{opt}) \lambda _{leg} \end{aligned}$$

(15)

Malicious nodes become volunteer clusterheads with probability of $p_m$ and therefore, malicious clusterheads are distributed as a homogeneous spatial Poisson point process:

$$\begin{aligned} PPP_{CH,mal}: \lambda _{CH,mal} = p_m\lambda _{mal} \end{aligned}$$

(16)

It should be noted that $PPP_{mal}$ and $PPP_{leg}$ are non-overlapping and independent and hence, $PPP_{CH,mal}$ and $PPP_{CH,leg}$ are independent non-overlapping point processes. Consequently, one can apply the Superposition operation and define:

$$\begin{aligned} PPP_{CH} = PPP_{CH,leg} \cup PPP_{CH,mal} \end{aligned}$$

(17)

which is a spatial Poisson point process with intensity of:

$$\begin{aligned} \lambda _{CH}&= \lambda _{CH,leg} + \lambda _{CH,mal} = p_{opt}(1- \frac{m}{n})\lambda _b + p_m \frac{m}{n} \lambda _b \end{aligned}$$

(18)

Similarly, one can derive the intensity of $PPP_{Ord,leg}$ as

$$\begin{aligned} \lambda _{Ord,leg} = (1-p_{opt})(1- \frac{m}{n}) \lambda _b \end{aligned}$$

(19)

Denoting the number of $PPP_{Ord,leg}$ process points in each Voronoi cell by the random variable $N_{Ord,leg}$ and applying the results of [5], we get:

$$\begin{aligned} \mathbb {E}[N_{Ord,leg}|N=n]&\approx \mathbb {E}[N_{Ord,leg}] = \frac{\lambda _{Ord,leg}}{\lambda _{CH} } =\frac{(1-p_{opt})(n-m) }{ p_{opt}(n-m) + mp_m} \end{aligned}$$

(20)

where $\mathbb {E}$ denotes expected value operation.

Since there are m malicious nodes and each of them becomes a clusterhead with probability $p_m$, there are on expectation $mp_m$ cells having a malicious clusterhead. As a result, the expected number of legitimate ordinary nodes belonging to clusters with a malicious clusterhead is:

$$\begin{aligned} L_m = mp_m\mathbb {E}[N_{Ord,leg}|N=n] \end{aligned}$$

(21)

On the other hand, there are a total of $L_{leg} = (n-m)(1-p_{opt})$ legitimate ordinary nodes on expectation. Hence, one can compute the percentage of legitimate ordinary nodes served by a malicious clusterhead under attack model 1 from:

$$\begin{aligned} q_{affected} = \frac{L_m}{L_{leg}} = \frac{mp_m }{ p_{opt}(n-m) + mp_m} \end{aligned}$$

(22)

From (22), more than $50\%$ of legitimate ordinary nodes would belong to clusters with malicious clusterheads if the fraction of the compromised nodes satisfies:

$$\begin{aligned} \frac{m}{n} \ge \frac{p_{opt}}{p_m+p_{opt}} \end{aligned}$$

(23)

Alternatively, for a given n and m, an adversary causes more than $50\%$ of legitimate ordinary nodes to belong to clusters with malicious clusterheads if it sets its probability of becoming volunteer clusterhead to:

$$\begin{aligned} p_m \ge (\frac{n}{m}-1)p_{opt} \end{aligned}$$

(24)

B Proof of Theorem 2

Proof

Before any attack has been launched (i.e. nodes become clusterhead with probability of $p_{opt}$), clusterheads and ordinary nodes form two homogeneous, independent, non-overlapping spatial Poisson point processes with intensities of $p_{opt}\lambda _b$ and $(1-p_{opt})\lambda _b$, respectively. Consequently, one can derive the expected number of ordinary nodes in each cluster in an attack-free system from [5]:

$$\begin{aligned} \mathbb {E}[N_{Ord,Afree}|N=n] \approx \frac{\lambda _{Ord,Afree}}{\lambda _{CH,Afree} }= \frac{(1-p_{opt})}{ p_{opt}} \end{aligned}$$

(25)

Now consider a system under attack model 2. Similar to the analysis presented in Appendix A, legitimate clusterheads form a spatial Poisson process:

$$\begin{aligned} PPP_{CH,leg}: \lambda _{CH,leg} = p_{opt} (1- \frac{m}{n})\lambda _{b} \end{aligned}$$

(26)

Legitimate ordinary nodes and malicious ordinary nodes are two independent non-overlapping point processes, and hence, their union is also a spatial Poisson point process, $PPP_{ord}$:

$$\begin{aligned} PPP_{ord} = PPP_{ord,leg} \cup PPP_{ord,mal} \end{aligned}$$

(27)

And hence:

$$\begin{aligned} \lambda _{Ord} = \lambda _{ord,leg} + \lambda _{ord,mal} = (1-p_{opt})(1- \frac{m}{n})\lambda _b + (1- p_m) \frac{m}{n} \lambda _b \end{aligned}$$

(28)

Denote the number of ordinary nodes in each cluster under attack model 2 by the random variable $N_{Ord,Amodel2}$. Then:

$$\begin{aligned} \mathbb {E}[N_{Ord,Amodel2}|N=n] \approx \frac{\lambda _{Ord}}{\lambda _{CH,leg} }= \frac{(1-p_{opt})(n-m)+(1-p_m)m}{ p_{opt}(n-m)} \end{aligned}$$

(29)

Therefore, the ratio is computed from:

$$\begin{aligned} \frac{\mathbb {E}[N_{Ord,Amodel2}|N=n]}{ \mathbb {E}[N_{Ord,Afree}|N=n] }= \frac{(n-m)+(1-p_m)m}{(n-m)} \end{aligned}$$

(30)

According to [6], $p_{opt}$ is very small for networks with density higher than 10. Since the attacker selects a $p_m$ even smaller than $p_{opt}$ under attack model 2, one can approximate this ratio by:

$$\begin{aligned} \frac{\mathbb {E}[N_{Ord,Amodel2}|N=n]}{ \mathbb {E}[N_{Ord,Afree}|N=n] }\approx \frac{1}{(1-\frac{m}{n})}, \quad m\ne n \end{aligned}$$

(31)

C Proof of Theorem 3

Proof

By applying the results of [6], the total energy to send 1 unit of data to the clusterhead by ordinary nodes of a Voronoi cell in an attack-free system ($C_1^{Afree}$) is computed from:

$$\begin{aligned} \mathbb {E}[C_1^{Afree}|N=n] \approx \frac{\lambda _{Ord,Afree}}{2r\lambda _{CH,Afree}^{3/2}} = \frac{(1-p_{opt})}{2rp_{opt}^{3/2}\lambda _b^{1/2}} \end{aligned}$$

(32)

Likewise, for a system under attack model 2, one can calculate the expected value of the total energy spent by legitimate ordinary nodes in a cluster to send a unit of data to the clusterhead, $C_1^{Amodel2}$ by:

$$\begin{aligned} \mathbb {E}[C_1^{Amodel2}|N=n] \approx \frac{\lambda _{Ord,leg}}{2r\lambda _{CH}^{3/2}} = \frac{(1-p_{opt})(1-\frac{m}{n})}{2r(p_{opt}(1-\frac{m}{n}) + p_m\frac{m}{n})^{3/2}\lambda _b^{1/2}} \end{aligned}$$

(33)

By assuming $p_m$ is much smaller than $p_{opt}$, we approximate the total energy spent by legitimate ordinary nodes in a cluster under attack model 2 by:

$$\begin{aligned} \mathbb {E}[C_1^{Amodel2}|N=n] \approx \frac{(1-p_{opt})}{2rp_{opt}^{3/2}[(1-\frac{m}{n})\lambda _b]^{1/2}} \end{aligned}$$

(34)

Hence, the ratio of $\mathbb {E}[C_1^{Amodel2}|N=n]$ to $\mathbb {E}[C_1^{Afree}|N=n]$ is computed from:

$$\begin{aligned} \frac{\mathbb {E}[C_1^{Amodel2}|N=n]}{ \mathbb {E}[C_1^{Afree}|N=n]} \approx \frac{1}{(1-\frac{m}{n})^{1/2}}, \quad m\ne n \end{aligned}$$

(35)