Robust Detection of Malicious Nodes in Mobile Sensor Networks Using Software Attestation

Abstract

In ad hoc and sensor networks, reputation-based trust management schemes have been widely used to identify the malicious nodes. These schemes leverage each node's behaviors for malicious node detection and thus require a certain amount of time to observe the behaviors of nodes. In mobile sensor networks, however, malicious nodes frequently move to different locations, and thus it is likely difficult to collect enough evidence for them. Moreover, when reputation-based schemes are employed, it is not easy to revoke the malicious nodes due to the risk of false positives. To mitigate these limitations of reputation-based schemes, we propose mobile malicious node detection schemes based on software attestation technique, which virtually fulfills zero false positives. In particular, we propose a probabilistic detection scheme in which each node attests its neighboring node with a certain probability. In order to reduce the attestation overhead of the probabilistic detection scheme, we also propose the SPRT (Sequential Probability Ratio Test) based detection scheme that uses the SPRT to determine when to perform the attestations. Through analysis and simulation, we show that our proposed schemes detect mobile malicious nodes through software attestations in robust and efficient manner.

1. Introduction

In mobile sensor networks, the attacker may capture sensor nodes and subvert them to be malicious. With these mobile malicious nodes, he can distort the various operations of the mobile sensor networks. For instance, in order to disrupt data collection operation of the base station, the attacker can launch false data injection attacks by having mobile malicious nodes send false data into the base station. He can also make mobile malicious nodes ruin the local operations such as routing, localization, and clustering by contacting many benign nodes. To diminish this damage incurred by mobile malicious nodes, it is imperative to detect and revoke them as quickly as possible. To meet this need, many researchers have proposed a variety of malicious node detection schemes in the context of ad hoc and sensor networks [1–10].

Reputation-based trust management schemes have been proposed to deal with an individual nodes trust in accordance with its behaviors [2, 4, 8]. Although malicious nodes can be identified in these schemes, they are not easily revoked due to the risk of false positives. Moreover, mobile malicious nodes can control their movements in such a way to make it difficult for their malicious behaviors to be observed. Another approach to deal with the malicious node detection in sensor networks is software attestation [1, 3, 5–7, 9, 10]. In this approach, attester (the base station or a node) performs attestations against the software running on attestee (a node) to verify whether it matches the expected software image; subverted image codes can then be detected. From perspective that this approach achieves virtually zero false positives and does not require any node behavior knowledge, it is more suitable than reputation approach for mobile malicious node detection. However, the previous works on software attestation did not describe how frequently each node needs to be attested even though they proposed several attestation methodologies.

To efficiently and effectively perform software attestations against mobile nodes, we first devise a probabilistic attestation scheme in which each mobile node is probabilistically attested. We then improve the performance of the probabilistic scheme by developing a scheme based on the SPRT (Sequential Probability Ratio Test) [11]. We apply the SPRT to determine the frequency of attestations per mobile node in such a way that highly mobile nodes are more frequently attested than lowly mobile nodes, leading to fast detection of highly mobile malicious nodes. Our analytical results show that both schemes achieves high mobile malicious node detection capability at the reasonable attestation overhead. We also evaluate the proposed schemes by using ns-2 simulator. Our simulation results demonstrate that the SPRT-based scheme outperforms the probabilistic scheme in terms of the attestation overhead while incurring reasonable malicious node detection time. Moreover, our proposed schemes catch out the malicious nodes with at least 99.74% detection rate. This indicates that almost all malicious nodes are detected by our proposed schemes (a preliminary version of this paper was presented in [12]).

The rest of paper is organized as follows. Section 2 presents the relevant work of malicious node detection. Section 3 describes the network assumptions and attacker models for our proposed schemes. Section 4 proposes mobile malicious node detection schemes and analyzes the proposed schemes. Section 5 presents the evaluation results of our proposed schemes. Finally, Section 6 concludes the paper.

2. Related Work

In this section, we present the related work for malicious node detection in wireless sensor networks.

Reputation-based trust management schemes have been proposed to evaluate each node's trust based on its activities [2, 4, 8]. In particular, Ganeriwal and Srivastava [2] used a Bayesian formulation for trust management. Sun et al. [8] applied information theoretic frameworks for trust evaluation. Li and Wu [4] utilized node mobility to reduce an uncertainty in trust computation and facilitate trust convergence. However, the mobile malicious nodes are not easily revoked because of the risk of false positives when these trust management schemes are used. Furthermore, mobile malicious nodes can evade these schemes by adopting high mobility strategy for their malicious actions not to be observed.

Software-attestation based schemes have been proposed to discern the subverted software images of sensor nodes [1, 3, 5–7, 9, 10]. In particular, the base station checks whether the flash image codes have been maliciously corrupted by performing attestations against randomly chosen parts of image codes or the entire codes [5–7]. Yang et al. [9] propose a localized attestation process in which each node collaborates with its neighbors for node attestations. Tamer et al. [1] propose a group-based software attestation scheme in wireless sensor networks. In this scheme, the attestation process is localized and performed without the aid of the base station. Jin et al. [3] use dynamic node attestation chains to reduce checksum computation time required for node attestation in mobile sensor networks. Zhang and Liu [10] propose a dynamic software attestation scheme in sensor networks. The proposed scheme employs software attestation technique to detect the corrupted program data in run time.

3. Models

In this section, we first state the network assumptions and then present an adversary models.

We assume a mobile sensor network where sensor nodes freely roam throughout the network. Since every sensor node is mobile, for simplicity, sensor node or node will be used to indicate mobile sensor node in the rest of the paper. We also assume that the sensor nodes could directly or indirectly communicate with the base station. The base station is assumed to be a trusted entity. This is a reasonable assumption in the sense that the entire network operations are controlled by the base station, and thus the network operator will fail to correctly run the networks if the base station is compromised.

Attacker is able to capture a certain amount of sensor nodes and make them malicious. He then exerts the malicious nodes to mount a variety of attacks while keeping moving them to different locations. For example, they can launch denial of service attacks such as jamming and flooding to damage various services provided in mobile sensor networks. They can also inject fake data into the network, and thus the network operator will gather the false information from the network. Moreover, the attacker could make malicious nodes contact many benign nodes and undermine the normal operations such as routing, clustering, and localization executed by these benign nodes.

4. Robust Detection of Mobile Malicious Nodes through the Software Attestation

This section presents the details of our schemes to detect and revoke the malicious nodes using software attestation. We start with a probabilistic approach and then show how to reduce the attestation overhead with the SPRT.

4.1. Scheme I: The Probabilistic Approach

A straightforward attestation approach is that a node attests its neighboring nodes whenever it meets them. Although this approach quickly detects malicious nodes, it will incur a large amount of attestation overheads, leading to the delay in processing the network operations. To reduce this attestation overhead, we propose a probabilistic attestation scheme (Scheme I) in which node attestation is probabilistically performed. We first describe the details of Scheme I and present an analysis of it.

4.1.1. Protocol Description

(a) Phase I: Predeployment. Before deployment, the network operator generates a secret key shared between a sensor node and the base station and installs it into each node.

(b) Phase II: Attestation. After deployment, each time every attester u meets every attestee v within its communication vicinity while moving in the network, and it performs software attestation against v with probability $\mathrm{\hspace{0.17em}\hspace{0.17em}}{p}_a$ . This probabilistic attestation is attempted only once while v is in the vicinity of u. Any techniques in [5–7, 10] can be used for software attestation on v. By leveraging the fact that the sensor nodes typically run homogeneous flash image codes, these techniques examine whether the images codes executing on a node coincide with the original image codes and identify the subverted image codes.

(c) Phase III: Postdetection. Once u determines v as malicious node, it generates a malicious node alert message on v, MNA $=\{u\parallel v\parallel t_m\parallel {\text{MAC}}_{K_u}[u\parallel v\parallel t_m]\}$ , where MAC stands for message authentication code, $K_u$ is the shared secret key between u and the base station, and $t_m$ is a timestamp representing the generation time of MNA. The timestamp $t_m$ is used to prevent the replay attacks. Attester u then sends MNA message to the base station. After receiving MNA from u, the base station performs software attestation against v to verify whether v is really malicious. If MNA is valid, the base station revokes v from the network.

4.1.2. Analysis

In this section, we will first discuss the possible attack strategies on Scheme I and the corresponding countermeasures. We will then explore the malicious node detection capability of Scheme I. Finally, we will compute the attestation overhead.

We consider false alert injection attack in which malicious nodes inject false malicious node alert (MNA) messages into the base station. In particular, a malicious node $\mathrm{\hspace{0.17em}\hspace{0.17em}}w\mathrm{\hspace{0.17em}\hspace{0.17em}}$ could create false MNA message on benign node z and send it to the base station. However, the base station will see that $\mathrm{\hspace{0.17em}\hspace{0.17em}}z\mathrm{\hspace{0.17em}\hspace{0.17em}}$ is not malicious through attesting on z, and thus there will be no harm on z. Rather, malicious node $\mathrm{\hspace{0.17em}\hspace{0.17em}}w\mathrm{\hspace{0.17em}\hspace{0.17em}}$ will be revoked due to fake alert injection. Hence, although the base station needs to perform attestations against on benign nodes, there will be little benefit for malicious nodes from launching false alert injection attack.

Next, we consider more severe attack, denial of attestation attack in which malicious nodes deny participating in attestation process and thus evade being detected. More specifically, an attestee v rejects the attestation attempts performed by an attester $\mathrm{\hspace{0.17em}\hspace{0.17em}}u\mathrm{\hspace{0.17em}\hspace{0.17em}}$ and flees to other regions. By maintaining this attack strategy whenever meeting other nodes, $\mathrm{\hspace{0.17em}\hspace{0.17em}}v\mathrm{\hspace{0.17em}\hspace{0.17em}}$ will avoid being detected. A straightforward countermeasure against this attack is to let the base station know that v escapes from being attested, to have the base station perform the attestation against v and revoke it from the network. More specifically, when v refuses $\mathrm{\hspace{0.17em}\hspace{0.17em}}u$ 's attestation attempts, $\mathrm{\hspace{0.17em}\hspace{0.17em}}u\mathrm{\hspace{0.17em}\hspace{0.17em}}$ generates denial of attestation notification message on $\mathrm{\hspace{0.17em}\hspace{0.17em}}v$ , DAN $\mathrm{\hspace{0.17em}\hspace{0.17em}}=\{u\parallel v\parallel t_d\parallel {\text{MAC}}_{K_u}[u\parallel v\parallel t_d]\}$ , where $t_d$ is a timestamp indicating the generation time of DAN. $\mathrm{\hspace{0.17em}\hspace{0.17em}}u\mathrm{\hspace{0.17em}\hspace{0.17em}}$ then sends DAN message to the base station. Upon receiving DAN message, the base station makes an attempt to attest v. If $\mathrm{\hspace{0.17em}\hspace{0.17em}}v\mathrm{\hspace{0.17em}\hspace{0.17em}}$ accepts to be attested, the base station will revoke v in case that it is malicious. Otherwise, the base station will isolate $\mathrm{\hspace{0.17em}\hspace{0.17em}}v\mathrm{\hspace{0.17em}\hspace{0.17em}}$ from the network; thus, $v\mathrm{\hspace{0.17em}\hspace{0.17em}}$ will not be allowed to participate in any network operations. Even though malicious nodes could send the base station fake DAN messages on benign nodes, the base station will discern that they are actually benign nodes through attestations, but rather the malicious nodes will be revoked from the network. As a result, the attacker will take little merit from mounting denial of attestation attack.

Next, we compute an average number of attestations that are performed by $\mathrm{\hspace{0.17em}\hspace{0.17em}}{N}_a\mathrm{\hspace{0.17em}\hspace{0.17em}}$ attesters. Since each attester independently performs attestation with probability $\mathrm{\hspace{0.17em}\hspace{0.17em}}{p}_a$ , $N_a$ attesters performing $p_a\times N_a$ attestations on an average.

Finally, we investigate the probability that malicious nodes are detected.

Lemma 1.

Let one denote $\mathrm{\hspace{0.17em}\hspace{0.17em}}N\mathrm{\hspace{0.17em}\hspace{0.17em}}$ as the total number of nodes in the network. Let one also denote $N_m$ as the total number of malicious nodes in the network ( $N_m<N$ ). Moreover, one denotes $N_a$ by the total number of attesters that are encountered by $N_m$ malicious nodes. One defines $p_d$ as the probability that at least one malicious node is detected by $N_a$ attesters. The probability $p_d$ is bounded from below by $\mathrm{1}-e^{-((p_a\times N_m\times N_a)/N)}$ .

Proof.

Let us define $\mathrm{\hspace{0.17em}\hspace{0.17em}}{p}_{nd}\mathrm{\hspace{0.17em}\hspace{0.17em}}$ as the probability that any of $N_m$ malicious nodes are not detected by $N_a$ attesters. $N_m/N$ is the probability that a node is malicious in the network, and the attestation probability is $p_a$ . Also, the malicious node is detected once it is attested. Thus, $\mathrm{1}-((p_a\times N_m)/N)$ is calculated as the probability that a malicious node is not detected by one attester. As a consequence, $\mathrm{\hspace{0.17em}\hspace{0.17em}}{p}_{nd}\mathrm{\hspace{0.17em}\hspace{0.17em}}$ is computed as ${(\mathrm{1}-((p_a\times N_m)/N))}^{N_a}$ . By using the property that $(\mathrm{1}+x)\le e^x$ , we compute the lower bound of $p_d$ as follows:

$$\begin{array}{l}{p}_d=\mathrm{1}-p_{nd}\\ \phantom{p_d}=\mathrm{1}-{\left(\mathrm{1}-\frac{p_a\times N_m}{N}\right)}^{N_a}\\ \phantom{p_d}\ge \mathrm{1}-e^{-\left(\left(p_a\times N_m\times N_a\right)/N\right)}.\end{array}$$

(1)

We now investigate how the lower bound of $\mathrm{\hspace{0.17em}\hspace{0.17em}}{p}_d\mathrm{\hspace{0.17em}\hspace{0.17em}}$ is affected by $N_m$ and $p_a\hspace{0.17em}\hspace{0.17em}\times \hspace{0.17em}\hspace{0.17em}{N}_a$ . For this study, we set $N=\mathrm{100}$ . Note that $p_a\times N_a$ is an average number of attestations performed in the network. As shown in Figure 1, the lower bound of $p_d$ exceeds 0.99 when $N_m$ is above 4. This means that our proposed scheme achieves very high detection capability even when there are a small number of malicious nodes in the network. Moreover, as an average number of attestations increases under $N_m\le \mathrm{4}$ , the lower bound of $p_d$ tends to increase. This indicates that an increase in the number of attestations results in the enhancement of malicious node detection capability.

Figure 1

Affects of the number of malicious nodes ( $N_m$ ) and an average number of attestations ( $p_a\times N_a$ ) on the lower bound of $\mathrm{\hspace{0.17em}\hspace{0.17em}}{p}_d$ .

4.2. Scheme II: The SPRT-Based Approach

Although the attestation overhead of Scheme I is reasonable, it could be reduced by using the attestation probability configured in line with nodes’ mobility rates, rather than using the same attestation probability. To do this, we propose the SPRT-based attestation approach (Scheme II) which adapts the SPRT to determine the attestation probability in accordance with nodes’ mobility rates. Note that SPRT [11] is a statistical decision process that reaches a decision with a few number of samples while maintaining low error rates. We start with the detailed description of Scheme II and then provide an analysis of it.

4.2.1. Protocol Description

The predeployment phase is the same as the one in Scheme I, and the attestation phase is described as follows.

Let us first consider the scenario that every node $\mathrm{\hspace{0.17em}\hspace{0.17em}}u\mathrm{\hspace{0.17em}\hspace{0.17em}}$ meets every other node v more than once within its communication vicinity while roaming in the network. In this scenario, we denote a series of meeting time between u and $\mathrm{\hspace{0.17em}\hspace{0.17em}}v\mathrm{\hspace{0.17em}\hspace{0.17em}}$ by $T_{\mathrm{1}},T_{\mathrm{2}},\dots$ . We also define $T_{i+\mathrm{1}}-\hspace{0.17em}{T}_i\mathrm{\hspace{0.17em}\hspace{0.17em}}$ ( $i\ge \mathrm{1}$ ) as intermeeting time between u and v. Let δ be an intermeeting time threshold that is used to determine whether intermeeting time is short or not. Putting it in differently, δ is regarded as a mobility threshold to decide whether node u frequently encounters node v or not. Let $M_i$ denote a Bernoulli random variable that is defined as

$$\begin{array}{cc}& M_i=\{\begin{array}{cc}\mathrm{0},\hfill & \text{if}\hspace{0.5em}{T}_{i+\mathrm{1}}-T_i>\delta ,\hfill \\ \mathrm{1},\hfill & \text{if}\hspace{0.5em}{T}_{i+\mathrm{1}}-T_i\le \delta .\hfill \end{array}\end{array}$$

(2)

The success probability $\mathrm{\Psi }$ of Bernoulli distribution is defined as $\text{Pr}(M_i=\mathrm{1})=\mathrm{1}-\text{Pr}(M_i=\mathrm{0})=\mathrm{\Psi }$ .

If $\mathrm{\Psi }$ is not larger than a predefined threshold ${\mathrm{\Psi }}^{\prime }$ , it is likely that node u infrequently contacts node v. Otherwise, it is likely that node u frequently contacts node v. The problem of deciding whether u frequently contacts v or not can be formulated as a hypothesis testing problem with null and alternate hypotheses of $\mathrm{\Psi }\le {\mathrm{\Psi }}_{\mathrm{0}}$ and $\mathrm{\Psi }\ge {\mathrm{\Psi }}_{\mathrm{1}}$ , respectively, such that ${\mathrm{\Psi }}_{\mathrm{0}}<{\mathrm{\Psi }}_{\mathrm{1}}$ .

Under this formulation, we present how node u performs the SPRT to make a decision on node v from the observed n samples, $\mathrm{\hspace{0.17em}\hspace{0.17em}}{M}_{\mathrm{1}},M_{\mathrm{2}},\dots ,M_n$ . We define null hypothesis $H_{\mathrm{0}}$ and alternate one $H_{\mathrm{1}}$ as follows: $H_{\mathrm{0}}$ is the hypothesis that u infrequently encounters v and $H_{\mathrm{1}}$ is the hypothesis that u frequently encounters v. We then define $L_n$ as the log-probability ratio on n samples, given as

$$\begin{array}{cc}& L_n=\ln \frac{\text{Pr}\left(M_{\mathrm{1}},\dots ,M_n\mid H_{\mathrm{1}}\right)}{\text{Pr}\left(M_{\mathrm{1}},\dots ,M_n\mid H_{\mathrm{0}}\right)}.\end{array}$$

(3)

Assume that $M_i$ is independent and identically distributed. This assumption is reasonable in the sense that both u and v independently move in the network and accordingly the intermeeting time between u and v is also independent. Then, $L_n$ can be rewritten as

$$\begin{array}{cc}& L_n=\ln \frac{{\prod }_{i=\mathrm{1}}^n\text{Pr}\left(M_i\mid H_{\mathrm{1}}\right)}{{\prod }_{i=\mathrm{1}}^n\text{Pr}\left(M_i\mid H_{\mathrm{0}}\right)}=\sum _{i=\mathrm{1}}^n‍\ln \frac{\text{Pr}\left(M_i\mid H_{\mathrm{1}}\right)}{\text{Pr}\left(M_i\mid H_{\mathrm{0}}\right)}.\end{array}$$

(4)

Let ${\tau }_n$ denote the number of times that $M_i=\mathrm{1}$ in the n samples. Thus, we have

$$\begin{array}{cc}& L_n={\tau }_n\ln \frac{{\mathrm{\Psi }}_{\mathrm{1}}}{{\mathrm{\Psi }}_{\mathrm{0}}}+\left(n-{\tau }_n\right)\hspace{0.17em}\ln \frac{\mathrm{1}-{\mathrm{\Psi }}_{\mathrm{1}}}{\mathrm{1}-{\mathrm{\Psi }}_{\mathrm{0}}},\end{array}$$

(5)

where ${\mathrm{\Psi }}_{\mathrm{0}}=\text{Pr}(M_i=\mathrm{1}\mid H_{\mathrm{0}})$ , ${\mathrm{\Psi }}_{\mathrm{1}}=\text{Pr}(M_i=\mathrm{1}\mid H_{\mathrm{1}})$ .

The rationale behind the configuration of ${\mathrm{\Psi }}_{\mathrm{0}}$ and ${\mathrm{\Psi }}_{\mathrm{1}}$ is as follows. On the one hand, ${\mathrm{\Psi }}_{\mathrm{0}}$ should be configured in accordance with the likelihood that node with insufficient mobility is determined to be frequently encountered. On the other hand, ${\mathrm{\Psi }}_{\mathrm{1}}$ should be configured to consider the likelihood that node with sufficient mobility is determined to be frequently encountered. Since the former likelihood is smaller than the latter one, ${\mathrm{\Psi }}_{\mathrm{0}}$ should be set to smaller than ${\mathrm{\Psi }}_{\mathrm{1}}$ .

The SPRT for $H_{\mathrm{0}}$ against $H_{\mathrm{1}}$ is given as follows.

• (i)

  ${\tau }_n\le {\gamma }_{\mathrm{0}}(n)$ : accept $\mathrm{\hspace{0.17em}\hspace{0.17em}}{H}_{\mathrm{0}}\mathrm{\hspace{0.17em}\hspace{0.17em}}$ and terminate the test.

• (ii)

  ${\tau }_n\ge {\gamma }_{\mathrm{1}}(n)$ : accept $\mathrm{\hspace{0.17em}\hspace{0.17em}}{H}_{\mathrm{1}}\mathrm{\hspace{0.17em}\hspace{0.17em}}$ and terminate the test.

• (iii)

  ${\gamma }_{\mathrm{0}}(n)<{\tau }_n<{\gamma }_{\mathrm{1}}(n)$ : continue the test process with another observation,

where

$$\begin{array}{cc}& {\gamma }_{\mathrm{0}}\left(n\right)=\frac{\ln \left({\beta }^{\prime }/\left(\mathrm{1}-{\alpha }^{\prime }\right)\right)+n\ln \left(\left(\mathrm{1}-{\mathrm{\Psi }}_{\mathrm{0}}\right)/\left(\mathrm{1}-{\mathrm{\Psi }}_{\mathrm{1}}\right)\right)}{\ln \left({\mathrm{\Psi }}_{\mathrm{1}}/{\mathrm{\Psi }}_{\mathrm{0}}\right)-\ln \left(\left(\mathrm{1}-{\mathrm{\Psi }}_{\mathrm{1}}\right)/\left(\mathrm{1}-{\mathrm{\Psi }}_{\mathrm{0}}\right)\right)},\\ {\gamma }_{\mathrm{1}}\left(n\right)=\frac{\ln \left(\left(\mathrm{1}-{\beta }^{\prime }\right)/{\alpha }^{\prime }\right)+n\ln \left(\left(\mathrm{1}-{\mathrm{\Psi }}_{\mathrm{0}}\right)/\left(\mathrm{1}-{\mathrm{\Psi }}_{\mathrm{1}}\right)\right)}{\ln \left({\mathrm{\Psi }}_{\mathrm{1}}/{\mathrm{\Psi }}_{\mathrm{0}}\right)-\ln \left(\left(\mathrm{1}-{\mathrm{\Psi }}_{\mathrm{1}}\right)/\left(\mathrm{1}-{\mathrm{\Psi }}_{\mathrm{0}}\right)\right)},\end{array}$$

(6)

${\alpha }^{\prime }$ (resp., ${\beta }^{\prime }$ ) is a user-configured false positive (resp., negative) error probability that a user desires to achieve in terms of the SPRT's decision.

When the SPRT terminates in the acceptance of $H_{\mathrm{0}}$ (resp., $\mathrm{\hspace{0.17em}\hspace{0.17em}}{H}_{\mathrm{1}}$ ), u attests the software images of v with probability of ${\tau }_n/n$ (resp., 1). u then restarts the SPRT on v with newly incoming samples. If u decides that the software images of v are maliciously modified, u performs the same postdetection phase as in Scheme I.

4.2.2. Analysis

In order to defend against the false alert injection and denial of attestation attacks, the same countermeasures are used as in Scheme I.

In this section, we first compute an average number of the attestations that an attester u performs against an attestee v. We then calculate the probability that u detects v when v is malicious.

Assume that u makes $\mathrm{\hspace{0.17em}\hspace{0.17em}}k\mathrm{\hspace{0.17em}\hspace{0.17em}}$ decisions on v while meeting with v in its vicinity. Moreover, assume that $\mathrm{\hspace{0.17em}\hspace{0.17em}}(\mathrm{1}-\omega )k\mathrm{\hspace{0.17em}\hspace{0.17em}}$ and $\mathrm{\hspace{0.17em}\hspace{0.17em}}\omega k\mathrm{\hspace{0.17em}\hspace{0.17em}}$ decisions are made in the acceptance of $H_{\mathrm{0}}$ and $H_{\mathrm{1}}$ , respectively. Let us denote the number of samples required to make the ith $H_{\mathrm{0}}$ decision by $n_i$ . Note that the attestation probability for the $\mathrm{\hspace{0.17em}\hspace{0.17em}}i$ th $H_{\mathrm{0}}$ (resp., $\mathrm{\hspace{0.17em}\hspace{0.17em}}{H}_{\mathrm{1}}$ ) decision is $\mathrm{\hspace{0.17em}\hspace{0.17em}}{\tau }_{n_i}/n_i$ (resp., 1). An average number of attestations performed by u is calculated as ${\sum }_{i=\mathrm{1}}^{(\mathrm{1}-\omega )k}‍({\tau }_{n_i}/n_i)+\omega k$ . If $\omega >\mathrm{0}$ holds, the detection probability will be 1 because u attests v with probability 1 in case of $H_{\mathrm{1}}$ decision. If $\omega =\mathrm{0}$ holds, the SPRT in u always accepts $H_{\mathrm{0}}$ per decision. Thus, ${\prod }_{i=\mathrm{1}}^k‍(\mathrm{1}-({\tau }_{n_i}/n_i))$ is the probability that u fails to detect a malicious v after making k consecutive $H_{\mathrm{0}}$ decisions. As a consequence, $\mathrm{1}-{\prod }_{i=\mathrm{1}}^k‍(\mathrm{1}-({\tau }_{n_i}/n_i))$ is the probability that a malicious v is detected after k consecutive $H_{\mathrm{0}}$ decisions.

5. Simulation Study

We use the ns-2 network simulator to evaluate the proposed schemes in a mobile sensor network. In our simulation, 100 mobile sensor nodes are placed within a square area of 500 m × 500 m. Moreover, we use the Random Waypoint Mobility (RWM) model to set up node movement patterns. In particular, we use the RWM model with the steady-state distribution provided by the Random Trip Mobility (RTM) model [13] for accurate performance evaluation. In the RWM model, each node moves to a randomly selected location with a randomly chosen speed between predefined minimum and maximum speeds. After coming to that location, it pauses there for a predefined time. After the pause time, each node then randomly chooses another location and moves to the selected location. This random movement process is repeated throughout the simulation period. We create a steady-state version of RWM model with the program codes of [14].

All simulations were performed for 1000 simulation seconds. We fixed a pause time of 10 simulation seconds and a minimum moving speed of 1 m/s of each node. Each node uses IEEE 802.11 as the medium access control protocol in which the transmission range is 50 m. We set ${\alpha }^{\prime }={\beta }^{\prime }=\mathrm{0.01}$ . We also configure ${\mathrm{\Psi }}_{\mathrm{0}}=\mathrm{0.1}$ and ${\mathrm{\Psi }}_{\mathrm{1}}=\mathrm{0.9}$ . The rationale behind the general configurations of ${\mathrm{\Psi }}_{\mathrm{0}}$ and ${\mathrm{\Psi }}_{\mathrm{1}}$ is discussed in Section 4.2.

To study how node mobility affects the proposed schemes, we vary each node's maximum speed ( $V_{\max }$ ) in the range of 10, 20, 40, 60, and 80 m/s. We also configure the attestation probability $p_a=\mathrm{0.1}$ and set a mobility threshold δ in accordance with node mobility. In low node mobility ( $V_{\max }\mathrm{\hspace{0.17em}\hspace{0.17em}}$ = 10, 20 m/s), we configure $\delta =\mathrm{40}$ simulation seconds. In high node mobility ( $V_{\max }\mathrm{\hspace{0.17em}\hspace{0.17em}}$ = 40, 60, 80 m/s), we configure $\delta =\mathrm{20}$ simulation seconds. The rational behind these settings is that the higher node mobility leads to the shorter intermeeting time, and accordingly, the smaller value of δ needs to be configured. In order to investigate how the fraction of malicious nodes ( $f_m$ ) affects the proposed schemes, we consider low fraction of malicious nodes ( $f_m=\mathrm{0.1}$ ) and high fraction of malicious nodes ( $f_m=\mathrm{0.5}$ ).

5.1. Simulation Results

We use the following metrics to evaluate the performance of our scheme.

• (i)

  Malicious Node Detection Time is an average time required to detect all malicious nodes in the network. Note that this time is represented in simulation seconds.

• (ii)

  Number of Attestations is the number of attestations that are performed in the network.

• (iii)

  False Negative is the error probability that a malicious node is not detected.

For each execution, we obtain each metric as the average of the results of the SPRTs that are repeated. The average of the results of 100 executions is presented as follows.

First, we found no false negatives except the case that $f_m=\mathrm{0.5}\mathrm{\hspace{0.17em}\hspace{0.17em}}$ and $V_{\max }$ = 10 m/s in Scheme II. In this case, the false negative is measured as 0.0026. This means that Scheme I always detects malicious nodes and Scheme II performs malicious node detection with probability 0.9974. Hence, our proposed schemes catch out almost all malicious nodes.

Second, as shown in Figures 2 and 3, Scheme I requires less malicious node detection time than Scheme II irrespective of the values of $V_{\max }$ and $f_m$ . This indicates that Scheme I performs attestations more frequently than Scheme II and thus identifies malicious nodes more quickly than Scheme II. We observe that malicious node detection time tends to decrease as $V_{\max }$ increases. This is because sufficient node mobility increases the chance that malicious nodes are attested and detected, leading to diminishing malicious node detection time. In both Schemes I and II, we also see that malicious node detection time when $f_m=\mathrm{0.1}$ is less than the one when $f_m=\mathrm{0.5}$ . This indicates that it does not take substantial time to catch out all malicious nodes when a small number of malicious nodes are in the network.

Figure 2

Malicious node detection time versus $V_{\max }$ when the fraction of malicious nodes is 0.1.

Figure 3

Malicious node detection time versus $V_{\max }\mathrm{\hspace{0.17em}\hspace{0.17em}}$ when the fraction of malicious nodes is 0.5.

Finally, as shown in Figures 4 and 5, the number of attestations tends to increase as $V_{\max }$ rises in both Schemes I and II. This indicates that sufficient node mobility expedites to node-to-node contacts, and thus nodes are more often attested. We also see that the number of attestations performed in Scheme I is larger than the one in Scheme II regardless of the values of $V_{\max }$ and $f_m$ . This means that Scheme II performs attestations less frequently than Scheme I. Furthermore, we notice that the number of attestations when $f_m=\mathrm{0.1}$ is more than the one when $f_m=\mathrm{0.5}$ in both Schemes I and II. This indicates that substantial numbers of attestations are required to detect all malicious nodes when a small number of malicious nodes are in the network. By comparing Figures 2 and 3 to Figures 4 and 5, we see that the more number of attestations leads to the less malicious node detection time.

Figure 4

Number of attestations versus $V_{\max }\mathrm{\hspace{0.17em}\hspace{0.17em}}$ when the fraction of malicious nodes is 0.1.

Figure 5

Number of attestations versus $V_{\max }\mathrm{\hspace{0.17em}\hspace{0.17em}}$ when the fraction of malicious nodes is 0.5.

6. Conclusions

In this paper, we propose malicious node detection schemes in mobile sensor networks. In particular, we first develop a probabilistic approach in which nodes are probabilistically attested. Moreover, we devise the SPRT-based approach to enhance the performance of probabilistic approach. Our analytical results show that the proposed schemes fulfill the robust detection capability at the reasonable software attestation overhead. Furthermore, our simulation results demonstrate that the SPRT-based approach detects malicious nodes within reasonable time while reducing the attestation overhead of the probabilistic approach.