# Intrusion Detection Algorithm Based on Change Rates of Multiple Attributes for WSN

Authors: Hongying Bai; Xiaotong Zhang; Fangjie Liu
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

Intrusion detection system (IDS) is a second line of the security mechanism for the wireless sensor network (WSN), and it has a great influence on confidentiality, integrity, and availability. However, many existing IDS only detect single attack or multiple known attacks. In this paper, a novel intrusion detection algorithm based on change rates of multiple attributes (CRMA) is proposed, which can detect multiple attacks including known and unknown types simultaneously. The change rates of multiple attributes for sensor nodes usually reflect the running states of WSN over a period of time. First, the Observed Change Rate of attributes at different times is obtained by observing multiple attributes of different sensor nodes. Then, the convex optimization is alternately used to obtain the Normal Change Rate and corresponding weights by minimizing the distance between the Observed Change Rate and the Normal Change Rate of each attribute. Finally, the WSN is considered to be attacked when the weighted deviation of the Observed Change Rate and Normal Change Rate is beyond the corresponding threshold. Experimental results show that the CRMA can detect multiple attacks including known and unknown types simultaneously and has a fast convergence rate. The average true positive rates (TPR) of CRMA are high, and the average false positive rates (FPR) of CRMA are low. The detection performance of CRMA is superior to that of the ARMA and NeTMids algorithms.


---

## Body

## 1. Introduction

Due to the characteristics of flexibility, low cost, wireless communication, and self-organization ability, the wireless sensor network (WSN) plays an important role in healthcare [1, 2], the military [3], industry [4], and many other fields, for instance, traffic monitoring, smart home system, medical facilities, and so on [5, 6]. However, the WSN is vulnerable to be attacked because sensor nodes are usually deployed in the unmanned environment. Therefore, the security issue is the main challenge to construct a robust and reliable WSN [7].Researchers have paid attention to encryption, decryption, identification, authentication, key management, and secure routing of the WSN. But such security measures cannot provide a wide range of protection against a variety of attacks and threats in the WSN. The intrusion detection system (IDS) is one possible solution to address a wide range of security attacks in the WSN [8]. The main tasks of an ID are to detect intruders trying to disrupt the WSN network [9, 10] and to monitor the security of WSN and identify vulnerability to guarantee the accurate network performance [11–13].The key intrusion detection technology of the WSN has attracted a lot of attention in recent years. Misuse detection does very well in detecting known attacks, but it works badly in detecting attacks which are unknown or undefined [14]. Mehmood et al. proposed a knowledge-based context-aware approach for handling the intrusions generated by malicious nodes [15]. Ghosal and Halder proposed a survey on energy efficient intrusion detection in wireless sensor networks [16]. A hybrid anomaly detection method for misdirection and black hole attacks employing the K-medoid customized clustering technique is proposed in [17].A lot of existing intrusion detection schemes of the WSN detects some known attacks. Hu et al. detect selective forwarding attacks in WSN by monitoring the loss rate of the packet and construct a trusted mechanism [18]. Motamedi and Yazdani use UAV to detect black hole attacks in WSN [19]. Gara et al. proposed a mobile WSN intrusion detection system based on IPv6, which specifically detects selective forwarding attacks in the network [20]. Many papers present IDS for WSN which only detect one kind of attack, such as the DoS attack [21, 22], selective forwarding attack [23], and sinkhole attack [24].Some intrusion detection algorithms detect attacks by predicting attributes of network flow, such as using the Autoregressive Moving Average (ARMA) or Markov model to predict traffic. It indicates that an attack occurring in the network when the normal flow value is significantly different from the predicted flow value [25]. Although the ARMA intrusion detection algorithm has higher detection accuracy, it only detects attacks related to the selected flow value, and it cannot detect multiple attack types at the same time.Few intrusion detection algorithms can detect multiple attacks simultaneously. Sajjad et al. proposed IDS based on the trustworthiness of neighbor nodes. Each node in the intrusion detection system analyzes the trust level of its neighbor nodes by analyzing the statistical data in the network and calculates the credibility value, thus determining the credibility of neighbor nodes. It can detect hello flood attacks, blocking attacks, and selective forwarding attacks. The intrusion detection system uses a lightweight intrusion detection algorithm NeTMids [26]. The NeTMids algorithm applies a variety of attributes to intrusion detection and analysis of nodes in the network and can detect multiple attack types at the same time. However, the accuracy of detection of NeTMids is not very high.According to the above circumstances, there are many problems in IDS for WSN as follows:(a)
The detection accuracy of some intrusion detection systems is low(b)
Many IDS only detect known attack types and cannot detect unknown attack types(c)
Many IDS only detect one or two attack types at the same time and cannot detect multiple attacks simultaneouslyTherefore, we should design or improve the intrusion detection algorithm for the WSN to improve current intrusion detection technology.Aiming at detecting a variety of internal attacks of the WSN, a novel change rates of multiple attributes (CRMA) intrusion detection algorithm is proposed in this paper, which can detect multiple intrusion attacks including known and unknown types simultaneously. In CRMA, we obtain the Observed Change Rate of attributes through observing the values of different attributes of different nodes over a period of time. The Normal Change Rates of attributes are calculated by minimizing the weighted deviation between the Observed and Normal Change Rates by convex optimization. The IDS considered to be attacked when the Observed Change Rate deviates from the Normal Change Rate beyond the corresponding threshold.This paper is organized as follows. Section2 gives the IDS model and multiple attributes of the WSN. In Section 3, we describe the CRMA intrusion detection algorithm and discuss some issues in the algorithm. In Section 4, we offer experimental analysis and performance evaluation of the IDS. In the final section, the conclusion is given.


## 2. IDS Model and Multiple Attributes of WSN

In this section, we introduce the IDS model, attributes of the WSN, and symbol representations of CRMA.


### 2.1. IDS Model

The model of the intrusion detection system designed in this paper is shown in Figure1. The IDS agents perform intrusion detection and data transmission. We assume that the IDS agents are trusted nodes and have sufficient energy. IDS agents interact with sensor nodes and base stations (BS). IDS agents will perform deep packet inspection on the ID and attributes of nodes. We assume encrypted traffic by default and IDS agents know the keys of the detected nodes in advance. The IDS agents can decrypt received data and perform deep packet inspection.Figure 1
IDS model of WSN.The deployment principle of IDS agents is to make IDS agents cover as many nodes as possible and reduce the area of overlap. IDS agents should be deployed in the monitoring region and as far as possible to cover the entire WSN.


### 2.2. Attributes of WSN

The sensor nodes of the WSN have some characteristic attributes that can be utilized by intrusion detection algorithms. In [27], the attributes of the WSN are divided into two types. One is the audit data in local detection which includes the packet collision rate, the waiting time of transmission, the number of neighbors, the energy consumption rate, and the rate of sensor reading report. Second, the audit data based on packets in the network includes the packet type, RSSI, arrival rate of sensor data, and packet loss rate.The WSN attributes may be affected by different types of attacks. We find that the more attributes you choose, the more they reflect the WSN situation. However, due to the limited resources of the WSN, it is necessary to select several different attributes to participate in the intrusion detection calculation according to the situation.


### 2.3. Symbolic Representations

Some symbols which would be used in the CRMA intrusion detection and the explanations of what they represent are shown in Table1.Table 1
Symbol representations.
SymbolRepresentationmThemth attribute of sensor node of WSN. The total number of multiple attributes is M,m∈1,⋯,M.vnt,mThe value ofmth attribute of nth sensor node at moment t. The total number of nodes is N,n∈1,⋯,N.vnt‐1,mThe value ofmth attribute of nth node at moment t−1. The t−1 is previous adjacent time of t. The total number of nodes is N,n∈1,⋯,N.Δvnt,mThe “Observed Change Rate” of mth attribute of nth node between time t and t−1.Δvn∗,mThe “Normal Change Rate” of mth attribute of nth node in the period of interval time i~j. The i and j are not adjacent times.ΔVn∗A set ofΔvn∗,m. At every interval time i~j, the attribute vector comprises a fixed number of Normal Change Rates of all attributes ΔVn∗=Δvn∗,m;n=1,⋯,N;m=1,⋯,M.ωntThe parameterωnt is the weight of nth node at time t.ΩnThe weights ofnth node in the period of i~j. Ωn=ωni,ωni+1,⋯,ωnj.D-valueThe difference value of the two adjacent iterations.ωnt,mThe weight ofmth dimension attribute of nth node at moment t.


## 2.1. IDS Model

The model of the intrusion detection system designed in this paper is shown in Figure1. The IDS agents perform intrusion detection and data transmission. We assume that the IDS agents are trusted nodes and have sufficient energy. IDS agents interact with sensor nodes and base stations (BS). IDS agents will perform deep packet inspection on the ID and attributes of nodes. We assume encrypted traffic by default and IDS agents know the keys of the detected nodes in advance. The IDS agents can decrypt received data and perform deep packet inspection.Figure 1
IDS model of WSN.The deployment principle of IDS agents is to make IDS agents cover as many nodes as possible and reduce the area of overlap. IDS agents should be deployed in the monitoring region and as far as possible to cover the entire WSN.


## 2.2. Attributes of WSN

The sensor nodes of the WSN have some characteristic attributes that can be utilized by intrusion detection algorithms. In [27], the attributes of the WSN are divided into two types. One is the audit data in local detection which includes the packet collision rate, the waiting time of transmission, the number of neighbors, the energy consumption rate, and the rate of sensor reading report. Second, the audit data based on packets in the network includes the packet type, RSSI, arrival rate of sensor data, and packet loss rate.The WSN attributes may be affected by different types of attacks. We find that the more attributes you choose, the more they reflect the WSN situation. However, due to the limited resources of the WSN, it is necessary to select several different attributes to participate in the intrusion detection calculation according to the situation.


## 2.3. Symbolic Representations

Some symbols which would be used in the CRMA intrusion detection and the explanations of what they represent are shown in Table1.Table 1
Symbol representations.
SymbolRepresentationmThemth attribute of sensor node of WSN. The total number of multiple attributes is M,m∈1,⋯,M.vnt,mThe value ofmth attribute of nth sensor node at moment t. The total number of nodes is N,n∈1,⋯,N.vnt‐1,mThe value ofmth attribute of nth node at moment t−1. The t−1 is previous adjacent time of t. The total number of nodes is N,n∈1,⋯,N.Δvnt,mThe “Observed Change Rate” of mth attribute of nth node between time t and t−1.Δvn∗,mThe “Normal Change Rate” of mth attribute of nth node in the period of interval time i~j. The i and j are not adjacent times.ΔVn∗A set ofΔvn∗,m. At every interval time i~j, the attribute vector comprises a fixed number of Normal Change Rates of all attributes ΔVn∗=Δvn∗,m;n=1,⋯,N;m=1,⋯,M.ωntThe parameterωnt is the weight of nth node at time t.ΩnThe weights ofnth node in the period of i~j. Ωn=ωni,ωni+1,⋯,ωnj.D-valueThe difference value of the two adjacent iterations.ωnt,mThe weight ofmth dimension attribute of nth node at moment t.


## 3. Intrusion Detection Algorithm Based on Change Rates of Multiple Attributes (CRMA)

The basic idea of the CRMA intrusion detection algorithm is as follows:(a)
TheObserved Change RateΔvnt,m of attributes is obtained by observing multiple attributes of different nodes(b)
Convex optimization is alternately used to obtain theNormal Change Rate of attribute Δvn∗,mi<t<j and corresponding weights(c)
When theObserved Change RateΔvnt,mt>j deviates from the Normal Change RateΔvn∗,m beyond the corresponding threshold, the IDS would determine that the WSN is attacked


### 3.1. CRMA Framework

The change rates of attributes are steady or change slowly when the WSN is running normally. For instance, the reduction of energy will follow a regular pattern when the sensor node transmits packets at a certain rate. If the change rates of attributes are abnormal, the network is considered to be under attack. In CRMA, convex optimization is used to obtain theNormal Change Rates of attributes and corresponding weights by minimizing the distance between the Observed Change Rate and the Normal Change Rate of each attribute.


#### 3.1.1. Observed Change Rate

The∣vnt,m−vnt−1,m∣ is the difference between the mth attribute of nth node between time t and the previous time t−1. The range and magnitude of each attribute may be different. We define the relative change rate as the Observed Change Rate Δvnt,m in CRMA.
(1)Δvnt,m=∣vnt,m−vnt−1,m∣vnt−1,m.


#### 3.1.2. Deviation Function

TheΔvn∗,m is the Normal Change Rate of mth attribute of nth node in the period of interval time i~j which can reflect the regular pattern during the stable operation. In CRMA, the deviation functiondΔvn∗,m,Δvnt,m is the square of the distance between the Δvnt,m and Δvn∗,m. The value of the deviation function is small when the Observed Change Rate is close to the Normal Change Rate.
(2)dΔvn∗,m,Δvnt,m=Δvn∗,m−Δvnt,m2.


#### 3.1.3. Constraint Function

The corresponding time weight represents the reliability of the Observed Change Rate in a certain period of time. The parameterωnt is the weight of nth node at time t. A higher ωnt indicates that the Observed Change Rate of the nth node at time t is closer to the Normal Change Rate. The Ωn is set of ωnt, Ωn=ωni,ωni+1,⋯,ωnj, which is the weights of the nth node in the period time of i~j. The constraint functionδΩn specifies the range of time weights which reflects the distributions of weights at different times. The constraint function maps the time weights uniformly to a particular range which can improve the convergence speed and accuracy of the IDS. We define a constraint function and a domain S to make ωnt locate at a certain numerical range. Different constraint functions may have different influences on the result. We set the value of δΩn to be 1 for the sake of simplicity. We choose an exponential function as the constraint function, and the domain of weights expands into 0,+∞.
(3)δΩn=∑t=ije‐ωnt=1,S=0,+∞.


#### 3.1.4. Optimization Problem of CRMA

The intrusion detection algorithm based on the change rates of multiattributes is proposed in this paper. TheΔvnt,m is a known value, and the Δvn∗,m is an unknown value. We construct a convex optimization problem to calculate the Normal Change RateΔvn∗,m of attributes by minimizing the weighted deviation between the Observed Change Rate and the Normal Change Rate. The objective function is shown as follows:
(4)ΔVn∗,ΩnminfΔVn∗,Ωn=∑t=ijωnt∑m=1MdΔvn∗,m,Δvnt,ms.t.δΩn=1Ωn∈S,where the ΔVn∗ is a set of Δvn∗,m. The attribute vector comprises a fixed number of Normal Change Rate of all attributes ΔVn∗=Δvn∗,m∣n=1,⋯,N;m=1,⋯,M. Each node constructs some attribute vector which reflects the operation status of the network in interval time i~j. The ΔVn∗ and Ωn are unknown vectors that correspond to the set of Δvn∗,m and time weights, respectively. For an optimization problem with two unknown vectors, to minimize the objective function, a vector can be fixed and another unknown vector can be found through multiple iterations until the vector converges. This iterative approach, referred to as the block coordinate descent method [28], will gradually reduce the updated value of the objective function until it reaches the minimum value. The ΔVn∗ and Ωn can be obtained by following two iterative convergent procedures.(1) Weight Update. We determine the Ωn by fixing ΔVn∗. With the estimation of the initial the value of ΔVn∗, we can obtain Ωn through minimizing the objective function, as follows:
(5)Ωn←argminΩnfΔVn∗,Ωns.t.δΩn=1Ωn∈S.(2) Normal Change Rate UpdateWe determine theΔVn∗ΔVn∗=Δvn∗,m;n=1,⋯,N;m=1,⋯,M by fixing ΩnΩn=ωni,ωni+1,⋯,ωnj. We obtain the Normal Change Rate minimizing the weighted deviation between the Observed Change Rate and the Normal Change Rate based on the Ωn calculated in the step above.
(6)Δvn∗,m←argminΔvn∗,m∑t=ijωnt⋅dΔvn∗,m,Δvnt,m.TheD-value is the difference in the value of the two adjacent iterations. When the D-value is less than the threshold, the iterative process is stopped. During multiple iterations, the Δvn∗,m gradually converges to a fixed value, which is the Normal Change Rate in time period i~j.There is another CRMA intrusion detection framework. The objective function is shown as (7). The ωnt,m is the weight of the mth dimension attribute of the nth node at moment t. The solving process of (7) is similar to (4). But this form of CRMA intrusion detection assigns weights to each node at each time of the observation phase. Calculating the state of each node separately can improve the accuracy of the IDS. However, it greatly increases the complexity of the algorithm, and larger space is needed to store weights, which is a huge burden for resource-constrained sensor nodes.
(7)ΔVn∗,ΩnminfΔVn∗,Ωn=∑t=ij∑m=1Mωnt,m⋅dΔvn∗,m,Δvnt,ms.t.δΩn=1Ωn∈S.The selection of attributes depends on what type of attack you want to detect. For example, when the WSN is under a flooding attack, the distribution of the packet type would be abnormal immediately and the RSSI would be exceptionally high. In order to detect the flooding attack successfully, the IDS should involve the attributes that would be affected in the detection procedure. On the other hand, if we select multiple attributes properly, we could detect multiple types of attacks at the same time.


### 3.2. Parameter Setting and Performance Analysis of CRMA

#### 3.2.1. Initial Value of the Normal Change Rate

TheNormal Change RateΔvn∗,m is obtained by solving the convex optimization problem by minimizing the weighted distance between the Observed Change Rate and solving the Normal Change Rate of each attribute. However, we need to set the initial value of Δvn∗,m at first which is crucial to solving the convex optimization problem efficiently. In theory, if the optimization problem is convex, the initial value of Δvn∗,m would not affect the final optimal solution. But good initial values make the algorithm converge quickly and save computing resources. The selecting principle of the initial value of Normal Change Rate Δvninit∗,m is that the chosen value is close to actuality. In CRMA, we use the average method to set the initial value of the Normal Change Rate.
(8)Δvninit∗,m=Δvnm¯=∑t=iiΔvnt,mj−i+1n=1,⋯,N,m=1,⋯,M.


#### 3.2.2. Threshold Setting

The threshold setting is related to the accuracy of the intrusion detection. There are two methods that can be used to set the threshold according to the actual situation to improve the accuracy of the detection.(1)
In the training phase of the intrusion detection algorithm, the average and standard deviation of each attribute are calculated by collecting and analyzing data of each node in the time periodi~j. The value of average attribute is as shown in (8). The standard deviation is calculated as shown in(9)σnm=1j−i+1∑t=ijΔvnt,m‐Δvnm¯2.Theα is the parameter determined during the experiment. For any t>j,m∈1,M,n∈1,N, if Δvnt,m−Δvn∗,m≤ασnm, it can be judged that there are no intrusion attacks in the WSN. Otherwise, it can be judged that the network is attacked. The corresponding parameters in different environments of the WSN may be different
(2)
If the multiple attributes are independent, the joint judgment will increase the false negative rate. If the multiple attributes are related to each other, the joint judgment will get a higher true positive rate. The value of the average attribute is shown in (10). The standard deviation is shown in (11). The average Normal Change Rate of multiple attributes of the node is calculated as shown in (12).(10)Δvn¯=∑t=ij∑m=1MΔvnt,mj−i+1M,(11)σn=1j−i+1M∑t=ij∑m=1MΔvnt,m−Δvn¯2,(12)Δvn∗¯=∑m=1MΔvn∗,mM.Similarly, ifΔvn−Δvn∗¯≤ασn, it can be judged that there are no intrusion attacks in the WSN. Otherwise, it can be judged that there are intrusion attacks in the WSN. The α is the parameter determined during the experimentThe computational complexity of (11) is much greater than (9). We can decide which judgment to choose according to the actual situation.Based on the above description, the flow chart of the CRMA intrusion detection algorithm is shown in Figure2.
(a)
The Observed Change RateΔvnt,m of attributes at different times obtained by observing the values of different attributes of sensor nodes over a period of time. We set the initial value of the Normal Change Rate as Δvninit∗,m(b)
Convex optimization is used to obtain the normal attribute change rateΔvn∗,m by minimizing the weighted distance between the rate of the Observed Change Rate and the normal change of each attribute. When the D-value is less than the threshold, the iterative process of convex optimization is stopped(c)
The IDS would turn on the alarm when the Observed Change Rate deviates from the Normal Change Rate beyond the corresponding threshold. IfΔvn−Δvn∗¯≤ασn (or Δvnt,m−Δvn∗,m≤ασnm), it can be judged that there are no intrusion attacks in the WSN. Otherwise, it can be judged that there are intrusion attacks in the WSNFigure 2
Flow chart of CRMA intrusion detection algorithm.


#### 3.2.3. Proof of Convexity

Based on the CRMA intrusion detection algorithm described above, the following theorems are given.Theorem 1.
The constraint function (3) and the optimization problem (4) constitute a convex optimization problem when ΔVn∗ is fixed.Proof.
According to constraint condition (3), the change domain of ωnt is 0,+∞ which is a convex set. So, the domain of the objective function in (4) is a convex set. When ΔVn∗ is fixed, the objective function is a linear affine function for ωnt.
For any0≤θ≤1,x,y∈i,j,
(13)fθx+1−θy=∑t=ijθxnt+1−θynt∑m=1MdΔvn∗,m,Δvnt,m=θ∑t=ijxnt∑m=1MdΔvn∗,m,Δvnt,m+1−θ∑t=ijynt∑m=1MdΔvn∗,m,Δvnt,m=θfx+1−θfy.
It satisfies the definition of a convex functionfθx+1−θy≤θfx+1−θfy. Therefore, the objective function is a convex function. The constraint function (3) and optimization problem (4) constitute a convex optimization problem involving equality and inequality constraints, which can be solved by the convex optimization solution method. We use the Lagrangian multiplier λ to solve Ωn.
Letφ=−e‐ωnt, then, ∑t=ijφ=1,S=0,+∞.
The optimization problem is converted to(14)LΩn,λ=∑t=ijlnφ∑m=1MdΔvn∗,m,Δvnt,m+λ1−∑t=ijφ.
Let the partial derivative ofφ be 0, and get
(15)λφ=−∑m=1MdΔvn∗,m,Δvnt,m.
Obtained by the constraint∑t=ijφ=1,
(16)λ=−∑t=ij∑m=1MdΔvn∗,m,Δvnt,m.
Combine withφ=e‐ωnt and obtain
(17)ωnt=−ln∑m=1MdΔvn∗,m,Δvnt,m∑t′=ij∑m=1MdΔvn∗,m,Δvnt′,m.It is obvious that the weight is inversely proportional to the deviation between the observation and the actuality which means the weight is greater when the Observed Change Rate is closer to the Normal Change Rate.Theorem 2.
The change rate (1), deviation function (2), constraint function (3), and optimization problem (4) constitute a convex optimization problem whenΩn is fixed.Proof.
The change rate (1) limits the value range of the property change rate to the real number domainR, so the set of the definition domain of the independent variable Δvnt,m of the deviation function dΔvn∗,m,Δvnt,m is a convex set.
For any0≤θ≤1,x,y∈1,M,
(18)dθΔvnx,m+1−θΔvny,m,Δvnt,m>θdΔvnx,m,Δvnt,m+1−θdΔvny,m,Δvnt,m.
Namely,(19)θΔvnx,m+1−θΔvny,m−Δvnt,m2>θΔvnx,m−Δvnt,m2+1−θΔvny,m−Δvnt,m2.
We get that(20)θθ−1Δvnx,m−Δvny,m2>0.
Due to0≤θ≤1, the above formula is obviously wrong. So, we get that
(21)dθΔvnx,m+1−θΔvny,m,Δvnt,m≤θdΔvnx,m,Δvnt,m+1−θdΔvny,m,Δvnt,m.According to the definition of the convex function, the deviation function is a convex function. The constraint function (3) combined withωnt is nonnegative, and the objective function (6) is a nonnegative linear combination of convex functions. According to the nature of the convex function, the objective function of the optimization problem is also a convex function. So, (1), (2), (3), and (4) constitute an unconstrained convex optimization problem. There is only one optimal solution, and the locally optimal solution is also the global optimal solution when the optimization problem is a convex optimization problem [28].According to (2) and (6), we get that
(22)Δvn∗,m←argmin∑t=ijωnt⋅dΔvn∗,m,Δvnt,m=argmin∑t=ijωnt⋅Δvn∗,m−Δvnt,m2.Let the partial derivative with respect toΔvk∗,m be equal to 0, and then, we derive the solution of Normal Change Rate Δvn∗,m.
(23)Δvn∗,m←∑t=ijωnt⋅Δvnt,m∑t=ijωnt.Therefore, the CRMA intrusion detection algorithm will converge to fixed value during the iterative process.


#### 3.2.4. Time Complexity

The time complexity of the CRMA intrusion detection algorithm will vary when using a different deviation function, constraint function, and objective function. If (2), (3), and (4) are used, the time complexity of CRMA is shown as follows:
(24)Tn=OT×N×M,where T is the time range and T=j−i+1, N is the number of sensor nodes, and M is the number of attributes of the nodes.If the squared deviation function (2), (3), and (7) is used, the time complexity of CRMA is (25).
(25)Tn=OT2×N×M.In (7), the CRMA intrusion detection assigns weights to each node at each time of the observation phase. Calculating the state of each node separately can improve the accuracy of the IDS. But, it greatly increases the complexity of the algorithm.


## 3.1. CRMA Framework

The change rates of attributes are steady or change slowly when the WSN is running normally. For instance, the reduction of energy will follow a regular pattern when the sensor node transmits packets at a certain rate. If the change rates of attributes are abnormal, the network is considered to be under attack. In CRMA, convex optimization is used to obtain theNormal Change Rates of attributes and corresponding weights by minimizing the distance between the Observed Change Rate and the Normal Change Rate of each attribute.


### 3.1.1. Observed Change Rate

The∣vnt,m−vnt−1,m∣ is the difference between the mth attribute of nth node between time t and the previous time t−1. The range and magnitude of each attribute may be different. We define the relative change rate as the Observed Change Rate Δvnt,m in CRMA.
(1)Δvnt,m=∣vnt,m−vnt−1,m∣vnt−1,m.


### 3.1.2. Deviation Function

TheΔvn∗,m is the Normal Change Rate of mth attribute of nth node in the period of interval time i~j which can reflect the regular pattern during the stable operation. In CRMA, the deviation functiondΔvn∗,m,Δvnt,m is the square of the distance between the Δvnt,m and Δvn∗,m. The value of the deviation function is small when the Observed Change Rate is close to the Normal Change Rate.
(2)dΔvn∗,m,Δvnt,m=Δvn∗,m−Δvnt,m2.


### 3.1.3. Constraint Function

The corresponding time weight represents the reliability of the Observed Change Rate in a certain period of time. The parameterωnt is the weight of nth node at time t. A higher ωnt indicates that the Observed Change Rate of the nth node at time t is closer to the Normal Change Rate. The Ωn is set of ωnt, Ωn=ωni,ωni+1,⋯,ωnj, which is the weights of the nth node in the period time of i~j. The constraint functionδΩn specifies the range of time weights which reflects the distributions of weights at different times. The constraint function maps the time weights uniformly to a particular range which can improve the convergence speed and accuracy of the IDS. We define a constraint function and a domain S to make ωnt locate at a certain numerical range. Different constraint functions may have different influences on the result. We set the value of δΩn to be 1 for the sake of simplicity. We choose an exponential function as the constraint function, and the domain of weights expands into 0,+∞.
(3)δΩn=∑t=ije‐ωnt=1,S=0,+∞.


### 3.1.4. Optimization Problem of CRMA

The intrusion detection algorithm based on the change rates of multiattributes is proposed in this paper. TheΔvnt,m is a known value, and the Δvn∗,m is an unknown value. We construct a convex optimization problem to calculate the Normal Change RateΔvn∗,m of attributes by minimizing the weighted deviation between the Observed Change Rate and the Normal Change Rate. The objective function is shown as follows:
(4)ΔVn∗,ΩnminfΔVn∗,Ωn=∑t=ijωnt∑m=1MdΔvn∗,m,Δvnt,ms.t.δΩn=1Ωn∈S,where the ΔVn∗ is a set of Δvn∗,m. The attribute vector comprises a fixed number of Normal Change Rate of all attributes ΔVn∗=Δvn∗,m∣n=1,⋯,N;m=1,⋯,M. Each node constructs some attribute vector which reflects the operation status of the network in interval time i~j. The ΔVn∗ and Ωn are unknown vectors that correspond to the set of Δvn∗,m and time weights, respectively. For an optimization problem with two unknown vectors, to minimize the objective function, a vector can be fixed and another unknown vector can be found through multiple iterations until the vector converges. This iterative approach, referred to as the block coordinate descent method [28], will gradually reduce the updated value of the objective function until it reaches the minimum value. The ΔVn∗ and Ωn can be obtained by following two iterative convergent procedures.(1) Weight Update. We determine the Ωn by fixing ΔVn∗. With the estimation of the initial the value of ΔVn∗, we can obtain Ωn through minimizing the objective function, as follows:
(5)Ωn←argminΩnfΔVn∗,Ωns.t.δΩn=1Ωn∈S.(2) Normal Change Rate UpdateWe determine theΔVn∗ΔVn∗=Δvn∗,m;n=1,⋯,N;m=1,⋯,M by fixing ΩnΩn=ωni,ωni+1,⋯,ωnj. We obtain the Normal Change Rate minimizing the weighted deviation between the Observed Change Rate and the Normal Change Rate based on the Ωn calculated in the step above.
(6)Δvn∗,m←argminΔvn∗,m∑t=ijωnt⋅dΔvn∗,m,Δvnt,m.TheD-value is the difference in the value of the two adjacent iterations. When the D-value is less than the threshold, the iterative process is stopped. During multiple iterations, the Δvn∗,m gradually converges to a fixed value, which is the Normal Change Rate in time period i~j.There is another CRMA intrusion detection framework. The objective function is shown as (7). The ωnt,m is the weight of the mth dimension attribute of the nth node at moment t. The solving process of (7) is similar to (4). But this form of CRMA intrusion detection assigns weights to each node at each time of the observation phase. Calculating the state of each node separately can improve the accuracy of the IDS. However, it greatly increases the complexity of the algorithm, and larger space is needed to store weights, which is a huge burden for resource-constrained sensor nodes.
(7)ΔVn∗,ΩnminfΔVn∗,Ωn=∑t=ij∑m=1Mωnt,m⋅dΔvn∗,m,Δvnt,ms.t.δΩn=1Ωn∈S.The selection of attributes depends on what type of attack you want to detect. For example, when the WSN is under a flooding attack, the distribution of the packet type would be abnormal immediately and the RSSI would be exceptionally high. In order to detect the flooding attack successfully, the IDS should involve the attributes that would be affected in the detection procedure. On the other hand, if we select multiple attributes properly, we could detect multiple types of attacks at the same time.


## 3.1.1. Observed Change Rate

The∣vnt,m−vnt−1,m∣ is the difference between the mth attribute of nth node between time t and the previous time t−1. The range and magnitude of each attribute may be different. We define the relative change rate as the Observed Change Rate Δvnt,m in CRMA.
(1)Δvnt,m=∣vnt,m−vnt−1,m∣vnt−1,m.


## 3.1.2. Deviation Function

TheΔvn∗,m is the Normal Change Rate of mth attribute of nth node in the period of interval time i~j which can reflect the regular pattern during the stable operation. In CRMA, the deviation functiondΔvn∗,m,Δvnt,m is the square of the distance between the Δvnt,m and Δvn∗,m. The value of the deviation function is small when the Observed Change Rate is close to the Normal Change Rate.
(2)dΔvn∗,m,Δvnt,m=Δvn∗,m−Δvnt,m2.


## 3.1.3. Constraint Function

The corresponding time weight represents the reliability of the Observed Change Rate in a certain period of time. The parameterωnt is the weight of nth node at time t. A higher ωnt indicates that the Observed Change Rate of the nth node at time t is closer to the Normal Change Rate. The Ωn is set of ωnt, Ωn=ωni,ωni+1,⋯,ωnj, which is the weights of the nth node in the period time of i~j. The constraint functionδΩn specifies the range of time weights which reflects the distributions of weights at different times. The constraint function maps the time weights uniformly to a particular range which can improve the convergence speed and accuracy of the IDS. We define a constraint function and a domain S to make ωnt locate at a certain numerical range. Different constraint functions may have different influences on the result. We set the value of δΩn to be 1 for the sake of simplicity. We choose an exponential function as the constraint function, and the domain of weights expands into 0,+∞.
(3)δΩn=∑t=ije‐ωnt=1,S=0,+∞.


## 3.1.4. Optimization Problem of CRMA

The intrusion detection algorithm based on the change rates of multiattributes is proposed in this paper. TheΔvnt,m is a known value, and the Δvn∗,m is an unknown value. We construct a convex optimization problem to calculate the Normal Change RateΔvn∗,m of attributes by minimizing the weighted deviation between the Observed Change Rate and the Normal Change Rate. The objective function is shown as follows:
(4)ΔVn∗,ΩnminfΔVn∗,Ωn=∑t=ijωnt∑m=1MdΔvn∗,m,Δvnt,ms.t.δΩn=1Ωn∈S,where the ΔVn∗ is a set of Δvn∗,m. The attribute vector comprises a fixed number of Normal Change Rate of all attributes ΔVn∗=Δvn∗,m∣n=1,⋯,N;m=1,⋯,M. Each node constructs some attribute vector which reflects the operation status of the network in interval time i~j. The ΔVn∗ and Ωn are unknown vectors that correspond to the set of Δvn∗,m and time weights, respectively. For an optimization problem with two unknown vectors, to minimize the objective function, a vector can be fixed and another unknown vector can be found through multiple iterations until the vector converges. This iterative approach, referred to as the block coordinate descent method [28], will gradually reduce the updated value of the objective function until it reaches the minimum value. The ΔVn∗ and Ωn can be obtained by following two iterative convergent procedures.(1) Weight Update. We determine the Ωn by fixing ΔVn∗. With the estimation of the initial the value of ΔVn∗, we can obtain Ωn through minimizing the objective function, as follows:
(5)Ωn←argminΩnfΔVn∗,Ωns.t.δΩn=1Ωn∈S.(2) Normal Change Rate UpdateWe determine theΔVn∗ΔVn∗=Δvn∗,m;n=1,⋯,N;m=1,⋯,M by fixing ΩnΩn=ωni,ωni+1,⋯,ωnj. We obtain the Normal Change Rate minimizing the weighted deviation between the Observed Change Rate and the Normal Change Rate based on the Ωn calculated in the step above.
(6)Δvn∗,m←argminΔvn∗,m∑t=ijωnt⋅dΔvn∗,m,Δvnt,m.TheD-value is the difference in the value of the two adjacent iterations. When the D-value is less than the threshold, the iterative process is stopped. During multiple iterations, the Δvn∗,m gradually converges to a fixed value, which is the Normal Change Rate in time period i~j.There is another CRMA intrusion detection framework. The objective function is shown as (7). The ωnt,m is the weight of the mth dimension attribute of the nth node at moment t. The solving process of (7) is similar to (4). But this form of CRMA intrusion detection assigns weights to each node at each time of the observation phase. Calculating the state of each node separately can improve the accuracy of the IDS. However, it greatly increases the complexity of the algorithm, and larger space is needed to store weights, which is a huge burden for resource-constrained sensor nodes.
(7)ΔVn∗,ΩnminfΔVn∗,Ωn=∑t=ij∑m=1Mωnt,m⋅dΔvn∗,m,Δvnt,ms.t.δΩn=1Ωn∈S.The selection of attributes depends on what type of attack you want to detect. For example, when the WSN is under a flooding attack, the distribution of the packet type would be abnormal immediately and the RSSI would be exceptionally high. In order to detect the flooding attack successfully, the IDS should involve the attributes that would be affected in the detection procedure. On the other hand, if we select multiple attributes properly, we could detect multiple types of attacks at the same time.


## 3.2. Parameter Setting and Performance Analysis of CRMA

### 3.2.1. Initial Value of the Normal Change Rate

TheNormal Change RateΔvn∗,m is obtained by solving the convex optimization problem by minimizing the weighted distance between the Observed Change Rate and solving the Normal Change Rate of each attribute. However, we need to set the initial value of Δvn∗,m at first which is crucial to solving the convex optimization problem efficiently. In theory, if the optimization problem is convex, the initial value of Δvn∗,m would not affect the final optimal solution. But good initial values make the algorithm converge quickly and save computing resources. The selecting principle of the initial value of Normal Change Rate Δvninit∗,m is that the chosen value is close to actuality. In CRMA, we use the average method to set the initial value of the Normal Change Rate.
(8)Δvninit∗,m=Δvnm¯=∑t=iiΔvnt,mj−i+1n=1,⋯,N,m=1,⋯,M.


### 3.2.2. Threshold Setting

The threshold setting is related to the accuracy of the intrusion detection. There are two methods that can be used to set the threshold according to the actual situation to improve the accuracy of the detection.(1)
In the training phase of the intrusion detection algorithm, the average and standard deviation of each attribute are calculated by collecting and analyzing data of each node in the time periodi~j. The value of average attribute is as shown in (8). The standard deviation is calculated as shown in(9)σnm=1j−i+1∑t=ijΔvnt,m‐Δvnm¯2.Theα is the parameter determined during the experiment. For any t>j,m∈1,M,n∈1,N, if Δvnt,m−Δvn∗,m≤ασnm, it can be judged that there are no intrusion attacks in the WSN. Otherwise, it can be judged that the network is attacked. The corresponding parameters in different environments of the WSN may be different
(2)
If the multiple attributes are independent, the joint judgment will increase the false negative rate. If the multiple attributes are related to each other, the joint judgment will get a higher true positive rate. The value of the average attribute is shown in (10). The standard deviation is shown in (11). The average Normal Change Rate of multiple attributes of the node is calculated as shown in (12).(10)Δvn¯=∑t=ij∑m=1MΔvnt,mj−i+1M,(11)σn=1j−i+1M∑t=ij∑m=1MΔvnt,m−Δvn¯2,(12)Δvn∗¯=∑m=1MΔvn∗,mM.Similarly, ifΔvn−Δvn∗¯≤ασn, it can be judged that there are no intrusion attacks in the WSN. Otherwise, it can be judged that there are intrusion attacks in the WSN. The α is the parameter determined during the experimentThe computational complexity of (11) is much greater than (9). We can decide which judgment to choose according to the actual situation.Based on the above description, the flow chart of the CRMA intrusion detection algorithm is shown in Figure2.
(a)
The Observed Change RateΔvnt,m of attributes at different times obtained by observing the values of different attributes of sensor nodes over a period of time. We set the initial value of the Normal Change Rate as Δvninit∗,m(b)
Convex optimization is used to obtain the normal attribute change rateΔvn∗,m by minimizing the weighted distance between the rate of the Observed Change Rate and the normal change of each attribute. When the D-value is less than the threshold, the iterative process of convex optimization is stopped(c)
The IDS would turn on the alarm when the Observed Change Rate deviates from the Normal Change Rate beyond the corresponding threshold. IfΔvn−Δvn∗¯≤ασn (or Δvnt,m−Δvn∗,m≤ασnm), it can be judged that there are no intrusion attacks in the WSN. Otherwise, it can be judged that there are intrusion attacks in the WSNFigure 2
Flow chart of CRMA intrusion detection algorithm.


### 3.2.3. Proof of Convexity

Based on the CRMA intrusion detection algorithm described above, the following theorems are given.Theorem 1.
The constraint function (3) and the optimization problem (4) constitute a convex optimization problem when ΔVn∗ is fixed.Proof.
According to constraint condition (3), the change domain of ωnt is 0,+∞ which is a convex set. So, the domain of the objective function in (4) is a convex set. When ΔVn∗ is fixed, the objective function is a linear affine function for ωnt.
For any0≤θ≤1,x,y∈i,j,
(13)fθx+1−θy=∑t=ijθxnt+1−θynt∑m=1MdΔvn∗,m,Δvnt,m=θ∑t=ijxnt∑m=1MdΔvn∗,m,Δvnt,m+1−θ∑t=ijynt∑m=1MdΔvn∗,m,Δvnt,m=θfx+1−θfy.
It satisfies the definition of a convex functionfθx+1−θy≤θfx+1−θfy. Therefore, the objective function is a convex function. The constraint function (3) and optimization problem (4) constitute a convex optimization problem involving equality and inequality constraints, which can be solved by the convex optimization solution method. We use the Lagrangian multiplier λ to solve Ωn.
Letφ=−e‐ωnt, then, ∑t=ijφ=1,S=0,+∞.
The optimization problem is converted to(14)LΩn,λ=∑t=ijlnφ∑m=1MdΔvn∗,m,Δvnt,m+λ1−∑t=ijφ.
Let the partial derivative ofφ be 0, and get
(15)λφ=−∑m=1MdΔvn∗,m,Δvnt,m.
Obtained by the constraint∑t=ijφ=1,
(16)λ=−∑t=ij∑m=1MdΔvn∗,m,Δvnt,m.
Combine withφ=e‐ωnt and obtain
(17)ωnt=−ln∑m=1MdΔvn∗,m,Δvnt,m∑t′=ij∑m=1MdΔvn∗,m,Δvnt′,m.It is obvious that the weight is inversely proportional to the deviation between the observation and the actuality which means the weight is greater when the Observed Change Rate is closer to the Normal Change Rate.Theorem 2.
The change rate (1), deviation function (2), constraint function (3), and optimization problem (4) constitute a convex optimization problem whenΩn is fixed.Proof.
The change rate (1) limits the value range of the property change rate to the real number domainR, so the set of the definition domain of the independent variable Δvnt,m of the deviation function dΔvn∗,m,Δvnt,m is a convex set.
For any0≤θ≤1,x,y∈1,M,
(18)dθΔvnx,m+1−θΔvny,m,Δvnt,m>θdΔvnx,m,Δvnt,m+1−θdΔvny,m,Δvnt,m.
Namely,(19)θΔvnx,m+1−θΔvny,m−Δvnt,m2>θΔvnx,m−Δvnt,m2+1−θΔvny,m−Δvnt,m2.
We get that(20)θθ−1Δvnx,m−Δvny,m2>0.
Due to0≤θ≤1, the above formula is obviously wrong. So, we get that
(21)dθΔvnx,m+1−θΔvny,m,Δvnt,m≤θdΔvnx,m,Δvnt,m+1−θdΔvny,m,Δvnt,m.According to the definition of the convex function, the deviation function is a convex function. The constraint function (3) combined withωnt is nonnegative, and the objective function (6) is a nonnegative linear combination of convex functions. According to the nature of the convex function, the objective function of the optimization problem is also a convex function. So, (1), (2), (3), and (4) constitute an unconstrained convex optimization problem. There is only one optimal solution, and the locally optimal solution is also the global optimal solution when the optimization problem is a convex optimization problem [28].According to (2) and (6), we get that
(22)Δvn∗,m←argmin∑t=ijωnt⋅dΔvn∗,m,Δvnt,m=argmin∑t=ijωnt⋅Δvn∗,m−Δvnt,m2.Let the partial derivative with respect toΔvk∗,m be equal to 0, and then, we derive the solution of Normal Change Rate Δvn∗,m.
(23)Δvn∗,m←∑t=ijωnt⋅Δvnt,m∑t=ijωnt.Therefore, the CRMA intrusion detection algorithm will converge to fixed value during the iterative process.


### 3.2.4. Time Complexity

The time complexity of the CRMA intrusion detection algorithm will vary when using a different deviation function, constraint function, and objective function. If (2), (3), and (4) are used, the time complexity of CRMA is shown as follows:
(24)Tn=OT×N×M,where T is the time range and T=j−i+1, N is the number of sensor nodes, and M is the number of attributes of the nodes.If the squared deviation function (2), (3), and (7) is used, the time complexity of CRMA is (25).
(25)Tn=OT2×N×M.In (7), the CRMA intrusion detection assigns weights to each node at each time of the observation phase. Calculating the state of each node separately can improve the accuracy of the IDS. But, it greatly increases the complexity of the algorithm.


## 3.2.1. Initial Value of the Normal Change Rate

TheNormal Change RateΔvn∗,m is obtained by solving the convex optimization problem by minimizing the weighted distance between the Observed Change Rate and solving the Normal Change Rate of each attribute. However, we need to set the initial value of Δvn∗,m at first which is crucial to solving the convex optimization problem efficiently. In theory, if the optimization problem is convex, the initial value of Δvn∗,m would not affect the final optimal solution. But good initial values make the algorithm converge quickly and save computing resources. The selecting principle of the initial value of Normal Change Rate Δvninit∗,m is that the chosen value is close to actuality. In CRMA, we use the average method to set the initial value of the Normal Change Rate.
(8)Δvninit∗,m=Δvnm¯=∑t=iiΔvnt,mj−i+1n=1,⋯,N,m=1,⋯,M.


## 3.2.2. Threshold Setting

The threshold setting is related to the accuracy of the intrusion detection. There are two methods that can be used to set the threshold according to the actual situation to improve the accuracy of the detection.(1)
In the training phase of the intrusion detection algorithm, the average and standard deviation of each attribute are calculated by collecting and analyzing data of each node in the time periodi~j. The value of average attribute is as shown in (8). The standard deviation is calculated as shown in(9)σnm=1j−i+1∑t=ijΔvnt,m‐Δvnm¯2.Theα is the parameter determined during the experiment. For any t>j,m∈1,M,n∈1,N, if Δvnt,m−Δvn∗,m≤ασnm, it can be judged that there are no intrusion attacks in the WSN. Otherwise, it can be judged that the network is attacked. The corresponding parameters in different environments of the WSN may be different
(2)
If the multiple attributes are independent, the joint judgment will increase the false negative rate. If the multiple attributes are related to each other, the joint judgment will get a higher true positive rate. The value of the average attribute is shown in (10). The standard deviation is shown in (11). The average Normal Change Rate of multiple attributes of the node is calculated as shown in (12).(10)Δvn¯=∑t=ij∑m=1MΔvnt,mj−i+1M,(11)σn=1j−i+1M∑t=ij∑m=1MΔvnt,m−Δvn¯2,(12)Δvn∗¯=∑m=1MΔvn∗,mM.Similarly, ifΔvn−Δvn∗¯≤ασn, it can be judged that there are no intrusion attacks in the WSN. Otherwise, it can be judged that there are intrusion attacks in the WSN. The α is the parameter determined during the experimentThe computational complexity of (11) is much greater than (9). We can decide which judgment to choose according to the actual situation.Based on the above description, the flow chart of the CRMA intrusion detection algorithm is shown in Figure2.
(a)
The Observed Change RateΔvnt,m of attributes at different times obtained by observing the values of different attributes of sensor nodes over a period of time. We set the initial value of the Normal Change Rate as Δvninit∗,m(b)
Convex optimization is used to obtain the normal attribute change rateΔvn∗,m by minimizing the weighted distance between the rate of the Observed Change Rate and the normal change of each attribute. When the D-value is less than the threshold, the iterative process of convex optimization is stopped(c)
The IDS would turn on the alarm when the Observed Change Rate deviates from the Normal Change Rate beyond the corresponding threshold. IfΔvn−Δvn∗¯≤ασn (or Δvnt,m−Δvn∗,m≤ασnm), it can be judged that there are no intrusion attacks in the WSN. Otherwise, it can be judged that there are intrusion attacks in the WSNFigure 2
Flow chart of CRMA intrusion detection algorithm.


## 3.2.3. Proof of Convexity

Based on the CRMA intrusion detection algorithm described above, the following theorems are given.Theorem 1.
The constraint function (3) and the optimization problem (4) constitute a convex optimization problem when ΔVn∗ is fixed.Proof.
According to constraint condition (3), the change domain of ωnt is 0,+∞ which is a convex set. So, the domain of the objective function in (4) is a convex set. When ΔVn∗ is fixed, the objective function is a linear affine function for ωnt.
For any0≤θ≤1,x,y∈i,j,
(13)fθx+1−θy=∑t=ijθxnt+1−θynt∑m=1MdΔvn∗,m,Δvnt,m=θ∑t=ijxnt∑m=1MdΔvn∗,m,Δvnt,m+1−θ∑t=ijynt∑m=1MdΔvn∗,m,Δvnt,m=θfx+1−θfy.
It satisfies the definition of a convex functionfθx+1−θy≤θfx+1−θfy. Therefore, the objective function is a convex function. The constraint function (3) and optimization problem (4) constitute a convex optimization problem involving equality and inequality constraints, which can be solved by the convex optimization solution method. We use the Lagrangian multiplier λ to solve Ωn.
Letφ=−e‐ωnt, then, ∑t=ijφ=1,S=0,+∞.
The optimization problem is converted to(14)LΩn,λ=∑t=ijlnφ∑m=1MdΔvn∗,m,Δvnt,m+λ1−∑t=ijφ.
Let the partial derivative ofφ be 0, and get
(15)λφ=−∑m=1MdΔvn∗,m,Δvnt,m.
Obtained by the constraint∑t=ijφ=1,
(16)λ=−∑t=ij∑m=1MdΔvn∗,m,Δvnt,m.
Combine withφ=e‐ωnt and obtain
(17)ωnt=−ln∑m=1MdΔvn∗,m,Δvnt,m∑t′=ij∑m=1MdΔvn∗,m,Δvnt′,m.It is obvious that the weight is inversely proportional to the deviation between the observation and the actuality which means the weight is greater when the Observed Change Rate is closer to the Normal Change Rate.Theorem 2.
The change rate (1), deviation function (2), constraint function (3), and optimization problem (4) constitute a convex optimization problem whenΩn is fixed.Proof.
The change rate (1) limits the value range of the property change rate to the real number domainR, so the set of the definition domain of the independent variable Δvnt,m of the deviation function dΔvn∗,m,Δvnt,m is a convex set.
For any0≤θ≤1,x,y∈1,M,
(18)dθΔvnx,m+1−θΔvny,m,Δvnt,m>θdΔvnx,m,Δvnt,m+1−θdΔvny,m,Δvnt,m.
Namely,(19)θΔvnx,m+1−θΔvny,m−Δvnt,m2>θΔvnx,m−Δvnt,m2+1−θΔvny,m−Δvnt,m2.
We get that(20)θθ−1Δvnx,m−Δvny,m2>0.
Due to0≤θ≤1, the above formula is obviously wrong. So, we get that
(21)dθΔvnx,m+1−θΔvny,m,Δvnt,m≤θdΔvnx,m,Δvnt,m+1−θdΔvny,m,Δvnt,m.According to the definition of the convex function, the deviation function is a convex function. The constraint function (3) combined withωnt is nonnegative, and the objective function (6) is a nonnegative linear combination of convex functions. According to the nature of the convex function, the objective function of the optimization problem is also a convex function. So, (1), (2), (3), and (4) constitute an unconstrained convex optimization problem. There is only one optimal solution, and the locally optimal solution is also the global optimal solution when the optimization problem is a convex optimization problem [28].According to (2) and (6), we get that
(22)Δvn∗,m←argmin∑t=ijωnt⋅dΔvn∗,m,Δvnt,m=argmin∑t=ijωnt⋅Δvn∗,m−Δvnt,m2.Let the partial derivative with respect toΔvk∗,m be equal to 0, and then, we derive the solution of Normal Change Rate Δvn∗,m.
(23)Δvn∗,m←∑t=ijωnt⋅Δvnt,m∑t=ijωnt.Therefore, the CRMA intrusion detection algorithm will converge to fixed value during the iterative process.


## 3.2.4. Time Complexity

The time complexity of the CRMA intrusion detection algorithm will vary when using a different deviation function, constraint function, and objective function. If (2), (3), and (4) are used, the time complexity of CRMA is shown as follows:
(24)Tn=OT×N×M,where T is the time range and T=j−i+1, N is the number of sensor nodes, and M is the number of attributes of the nodes.If the squared deviation function (2), (3), and (7) is used, the time complexity of CRMA is (25).
(25)Tn=OT2×N×M.In (7), the CRMA intrusion detection assigns weights to each node at each time of the observation phase. Calculating the state of each node separately can improve the accuracy of the IDS. But, it greatly increases the complexity of the algorithm.


## 4. Experiments and Discussion

Attacks from the internal network are the biggest threats to the WSN. Attacks from the external network only make the attacker become a legitimate node to obtain the network information. However, internal attacks often destroy or modify the network data. In this paper, we hope to find an effective way to detect internal attacks.The parameters to measure the performance of the intrusion detection system are set as (26)–(29). There are four concepts: true positive (TP), false positive (FP), true negative (TN), and false negative (FN). The TP occurs when normal patterns are correctly classified as normal. The FP occurs when abnormal patterns are incorrectly classified as normal. The TN occurs when abnormal patterns are correctly classified as abnormal. The FN occurs when normal patterns are incorrectly classified as abnormal. The true positive rate (TPR) is the probability of successfully detecting the intrusion attacks. The true negative rate (TNR) is the probability that abnormal patterns are incorrectly classified as normal. The false positive rate (FPR) is the probability that attacks will be issued no attacks. The false negative rate (FNR) is the probability that nonattacks will falsely be classified as attacks [29, 30]. The high performance of IDS should achieve a high TPR and low FPR to ensure the efficiency and reliability of the IDS and guarantee the security of the network.
(26)TPR=TPTP+FN,(27)TNR=TNTN+FP,(28)FNR=FNTP+FN=1−TPR,(29)FPR=FPFP+TN=1−TNR.We simulated several typical attacks based on MATLAB; the simulation parameters are given in Table2.Table 2
Simulation parameters.
ParameterValueDeployment field100m×100mNumber of nodes30~190Deployment methodRandomInitial energy of node0.5 JBS position(50 m, 50 m)Eelce50 nJ/bitεfs10 pJ/bit/m2εmp0.0013 pJ/bit/m4EDA5 nJ/bit/signalWe validate our algorithms with several typical internal attacks in the WSN including hello flooding attacks, selective forwarding attacks, DoS attacks, sinkhole attacks, and their hybrid attacks (multiple attacks). Table3 shows the characteristics and impacts of simulated attacks. The multiple attacks are that the above four kinds of attacks exist simultaneously.Table 3
Characteristics and impacts of simulated attacks.
Simulated attacksCharacteristicsImpactsHello flooding attacksThe attacker uses a high-power transmitter to broadcast and send Hello packets every round, so that each node of the network mistakes the attacker for its neighbor node.The energy consumption of the attacked node will increase rapidly. The proportion of Hello packets will increase significantly, and proportion of other data packets will decrease.Selective forwarding attacksThe attacked nodes probabilistically forward or drop specific packets. It has a significant impact on the node with forwarding function.The proportion of sending and receiving packets of the forwarding node will change. The forwarding rate of the node will decrease.DoS attacksThe attacker interferes with or controls user data, causing refusal of service on correct data transmission.The sending rate and forwarding rate of the attacked node will be significantly reduced.Sinkhole attacksThe attacker uses his powerful features to make himself more like a base station, so it can receive more data.The number of packages received by the attacked nodes suddenly increases, and the energy is rapidly reduced due to collection.Multiple attacksThe Hello flooding attacks, Selective forwarding attacks, DoS attacks, and Sinkhole attacks exist simultaneously.A combination of the impacts of the above four kinds of attacks.In the CRMA, we detect the change rate of attributes based on the characteristics and impacts of the simulated attacks. We assume that the base station (BS) and IDS agents are trusted nodes. CRMA can detect multiple attacks simultaneously. Each point in the following figures is the average of the results of hundreds of tests, and each line has been accumulated over thousands of tests in this paper.Figure3 shows that the CRMA has higher true positive rates (TPR) for the four simulated attacks and their hybrid attack (multiple attacks). The TPR for the sinkhole attacks is relatively low. This is because the change rate of the attribute caused by the sinkhole attack is small. So, the CRMA is not good at detecting such attacks. The TPR of the DoS attacks can reach 100% when the number of nodes is large. This is because once the node launches the DoS attacks, the node stops all functions, which will immediately cause the node to change attributes, such as stopping the sending and receiving of data packets, stopping the collection of sensor data, etc. So, the CRMA will more easily detect changes in these attributes.Figure 3
True positive rates of CRMA under different attacks.Figure4 shows that CRMA has lower false positive rates (FPR) for the four types of attacks and their hybrid attacks. When the number of nodes is relatively small, the FPR is relatively high. But as the number of nodes increases, the false positive rate will decrease. In (29), the FP occurs when abnormal patterns are incorrectly classified as normal and the TN occurs when abnormal patterns are correctly classified as abnormal. With the increase of nodes, the number of attributes also increases. The ability of the system to judge what is abnormal becomes stronger.Figure 4
False positive rates of CRMA under different attacks.The performance of networks is significantly affected by the malicious nodes [31]. In this paper, it is divided into three levels according to the percentage of malicious nodes. There is a low percentage of malicious nodes when the number of attack nodes is 5%~10% of the total nodes, and there is a medium percentage of malicious nodes when the number of attack nodes is 10%~30% of the total nodes. When the number of attack nodes is 30%~50% of the total nodes, there is a high percentage of malicious nodes.Figure5 shows the true positive rate (TPR) of CRMA intrusion detection system under different percentages of malicious nodes. The TPR of the system decreases as the percentage of malicious nodes increases.Figure 5
True positive rates of CRMA under different percentages of malicious nodes.Figure6 shows the false positive rate (FPR) of CRMA intrusion detection system under different percentages of malicious nodes. The FPR of the system decreases as the percentage of malicious nodes increases.Figure 6
False positive rates of CRMA under different percentages of malicious nodes.The experimental results show that CRMA has a fast convergence rate. Table4 shows an example of the value of the objective function of each round in the process of iteration. It can be seen that the value of the objective function gradually decreases, and the difference of the value of the objective function is approximately equal to 0.Table 4
Values of objective function in multiround iterations.
RoundrObjective functionfrDifference of objective functionfr−fr−113042.3306603744923041.470557396940.8601029775533041.468912367540.0016450294043041.468907979540.0000043880053041.468907966750.0000000127963041.468907966710.0000000000473041.468907966710.00000000000In this paper, ARMA [25] and NeTMids [26] are compared with CRMA. ARMA predicts the traffic attributes of the WSN and only detects one type of attribute. The packet forwarding rate is selected as an attribute of ARMA. Among the above four intrusion attacks, only the sinkhole attacks will affect the packet forwarding rate. Therefore, the ARMA and CRMA algorithms compare the detection results under sinkhole attacks.Figure7 shows the true positive rates of ARMA and CRMA under sinkhole attacks and the aforementioned hybrid attacks (multiple attacks). It can be seen that the ARMA algorithm has a high TPR when the number of nodes is small and a low TPR when the number of nodes is large. The TPR of CRMA is much higher than that of ARMA under multiple attacks. Therefore, CRMA will be a better choice when there are more nodes or multiple attacks in the WSN.Figure 7
True positive rates of ARMA and CRMA.Figure8 shows the false positive rates of ARMA and CRMA under sinkhole attacks and multiple attacks. When the number of nodes is large, the CRMA intrusion detection algorithm has very low false positive rates for the detection of sinkhole attacks and multiple attacks. In practical applications, the types of attacks are unknown, and the number of nodes maybe very large. At this time, ARMA is not a good choice.Figure 8
False positive rates of ARMA and CRMA.Figure9 shows the false negative rates (FNR) of ARMA and CRMA under sinkhole attacks and multiple attacks which can be obtained by combining Figure 7 with formula (27). Figure 10 shows the true negative rates (TNR) of ARMA and CRMA under sinkhole attacks and multiple attacks which can be obtained by combining Figure 8 with formula (28). The FNR of ARMA is much higher than that of CRMA under multiple attacks.Figure 9
False negative rates of ARMA and CRMA.Figure 10
True negative rates of ARMA and CRMA.The CRMA is compared with the NeTMids [26] intrusion detection algorithm, which uses different attributes of the WSN to detect different attacks. Figure 11 shows the true positive rates of NeTMids and CRMA under the above-mentioned four hybrid attacks (multiple attacks). It can be seen that the true positive rates of NeTMids are significantly lower than those of CRMA.Figure 11
True positive rates of NeTMids and CRMA.Figure12 shows the false positive rates of NeTMids and CRMA under multiple attacks. The NeTMids algorithm has relatively higher false positive rates. Although the NeTMids algorithm is relatively simple and consumes fewer resources, the intrusion detection results are not as good as those of CRMA, and CRMA can detect unknown attacks through the detection of change rates of attributes.Figure 12
False positive rates of NeTMids and CRMA.Packet delivery ratio (PDR) is defined as the ratio of the total data packets received to the number of data packets sent [31]. The performance of the WSN is also studied by analyzing the PDR. Figure 13 illustrates the PDR with CRMA and without IDS. The performance of the PDR without any malicious nodes is also presented for comparison. The PDR dramatically decreases from 92% to 43% in the presence of an attacker in WSN. The use of CRMA improves the delivery performance of the system packet from 43% to 85%.Figure 13
Packet delivery ratio with CRMA and without IDS.The performance of the network is also studied by analyzing the average end-to-end delay (EED). Figure14 illustrates the average EED with CRMA and without IDS. The EED dramatically increases in the presence of attacks. The use of CRMA reduces the EED of the WSN.Figure 14
End-to-end delay with CRMA and without IDS.


## 5. Conclusion

The intrusion detection algorithm based on the change rates of multiple attributes (CRMA) can detect multiple attacks including known and unknown types simultaneously. In CRMA, the Normal Change Rate is calculated by minimizing the weighted deviation between the Observed Change Rate and the normal one through convex optimization. We also give proof that CRMA will converge to a fixed value during the iterative process. Especially in the case where multiple attacks exist simultaneously, the true positive rates of CRMA are 88%~95%. Compared with ARMA and NeTMids, the CRMA has robust detection performance under multiple attacks.Further, we will improve the CRMA intrusion detection algorithm to reduce its computational complexity and storage requirements. How to set the threshold in CRMA and other parameters according to the actual situation is also a research direction.



---

*Source: 8898847-2020-12-02.xml*