# Optimized Scheme to Secure IoT Systems Based on Sharing Secret in Multipath Protocol

Authors: Fatna El Mahdi; Ahmed Habbani; Zaid Kartit; Bachir Bouamoud
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

Internet of Things (IoT) is a hot and emerging topic nowadays. In the world of today, all kinds of devices are supposed to be connected and all types of information are exchanged. This makes human daily life easier and much more intelligent than before. However, this life mode is vulnerable to several security threats. In fact, the mobile networks, by nature, are more exposed to malicious attacks that may read confidential information and modify or even drop important data. This risk should be taken in consideration prior to any construction of mobile networks especially in the coming 5G technology. The present paper aims to provide a contribution in securing such kinds of environment by proposing a new protocol that can be implemented in ad hoc networks.


---

## Body

## 1. Introduction

The IoT concept is based on connecting different and heterogeneous devices. This connection aims to make human life easier and more efficient, by automating some tasks and making communication faster and better especially in some important fields such as health service, industry, agriculture, transportation, education, or even our domestic daily life as shown in Figure1. In smart homes, for example, we could switch on air conditioning before arriving home or unlock door for a visiting friend. We can even switch on or off light while we are kilometers away from home. With smart home applications, users can save time, energy, and money and win more life efficiency and comfort. Smart city surveillance, smart transportation, smart energy systems, smart water distribution, and security systems are all examples of IoT applications for smart cities. The collected data in the IoT environment would be analyzed in order to make right decisions at the right moments. However, in such systems, many challenges encounter the normal functioning, especially security challenge, which is by the way our focus in this paper. In fact, wireless mobile networks, which are the communication platform of IoT systems, are vulnerable to different security threats. These security risks can threaten the network in terms of confidentiality, integrity, availability, and other aspects. Thus, improving security and making these systems reliable become more and more mandatory in research field. Scientists and researchers are invited to perform studies in order to secure IoT especially in critical areas such as military domains or medical services. In addition, the IoT has raised public safety concerns, like cyberattacks and organized crimes which can be a serious risk for organizations and people’s private life. In different places of the world, many serious attacks on IoT systems have been detected. On 27 June 2019, the US Food and Drug Administration (FDA) issued an alert about some insulin pumps manufactured by Medtronic that are vulnerable to be remotely accessed and controlled by hackers [1]. The same organization (FDA) confirmed, in 2017, that the implantable cardiac devices in St. Jude Medical could be easily hacked and controlled [2]. These devices are used to supervise patients’ heart functioning and prevent or help in case of heart attacks. Nevertheless, hackers are able to access the device, control shocks, manage heartbeat, and give incorrect commands, due to some transmitter vulnerabilities. In April 2017, a malware named BrickerBot was discovered [3]. It attempted to definitively destroy IoT objects by executing harmful commands to delete their data and disable them. In 2016, a certain hacker called Anna Senpai created a malware, called Mirai [4], which gains the access and take control of vulnerable connected objects such as routers and surveillance cameras, and create massive distributed denial of service attacks (DDos). Mirai transforms the infected objects into autonomous and intelligent bots controlled remotely. All these examples and many others show clearly that security issue is an urgent and crucial subject and its development is even more important than the development of IoT itself.Figure 1
Example of communication domains in a smart environment.In our research, we focus on security requirement for mobile ad hoc networks (MANETs) which are widely used in IoT environments, thanks to their advantages like ease of implementation ease, being infrastructure-less, being self-organized, and dynamic topology. These advantages in terms of implementation and performance can also be seen as a weakness in terms of security and reliability, because of many factors, especially the lack of centralized infrastructure and the difficult implementation of control mechanisms. This character is our main motivation in this research. This paper is organized as follows: The next section presents some related studies in this security field. Section3 will be dedicated to describing our architecture inspired from sharing a secret approach to secure communication in MANETs; this new algorithm is called Secure Protocol based on Identification, Detection, and Location and Isolation (SPIDLI) steps. This architecture provides a great solution against black hole, eavesdropping, and message tampering attacks. Section 4 is dedicated to discuss the schema example as a proof of concept. In Section 5, we will analyze some of the simulation results. The last section will conclude this paper.


## 2. Related Work

Complex network is based on graph theory and social sciences concepts and can be considered as a set of several connected nodes that interact in different ways [5]. The IoT concept is based on connecting different and heterogeneous devices [6]. The information exchanged in these networks varies according to the used context. It can be medical, military, agriculture, education, transport. or simply everyday home information [7]. Since this technology interacts with human activity especially in some sensitive domains, such as military or health service, it is necessary to guarantee that the shared information is highly secure [8].Wang et al. in [9] presents a new metric called RNMI to assess the robustness of the complex network based on standardized mutual information. Next, a simulated annealing algorithm is designed to reduce the damage. In order to improve the balance between attacks and errors, the authors propose a weighted metric to design connecting process RNMIw and a series of solutions focusing on attacks and errors.Another study proposed by Wang and Liu in [10] focuses on resisting intentional attacks and cascading failures in complex networks, by proposing a framework called MAGA-NetR to improve the overall performance. This technique takes advantage of the fact that the robustness measures which evaluate the tolerance of the networks are not correlated with each other; therefore, this study proposes a standardized robustness measure Rn and this measure is validated to be effective in the experiments.In order to facilitate the administration of public key certification, Shamir proposed the identity-based cryptosystem approach in [11], and later, Boneh and Franklin concretized this approach using Weil coupling to provide an ID-based encryption scheme in [12]. As its name indicates, the ID-based cryptosystems are based on the identity information; therefore, each node in the network can use its identity as a public key instead of extracting it from a certificate generated by a certificate authority (CA) [13].Shamir [14] and Blakley [15] are the first to introduce the notion of secret sharing scheme using t,n threshold. This scheme is based on two main steps as follows:(i)
Dividing step where the secret message is divided inton fragments, and then, each fragment is given to an authorized member(ii)
Rebuilding step where the collector tries to reconstruct the initial secret if and only if he combines at leastk fragment received [16]Zhou et al. proposed in [17] the combination between multipath routing and secret sharing to distribute the CA to multiple servers. Later, Kong et al. were interested in improving operations such as the signing of a certificate so that they can be done locally by the neighbors of the requesting node, distributing the servers more evenly over the network [18].In the same context, and in order to diminish the effects of frequent topological changes, Tsirigos and Haas [19] proposed the application of concurrent multipath routing at the same time with diversity coding. Lou et al. [20] proposed a protocol named SPREAD to ensure data confidentiality and availability in order to strengthen network security. This method is based on four methods: directional transmission, controlling transmission power, shortest-distance routing, and controlling correlation factor. All concurrent multipath routes between any two nodes are considered in this method, but the limitation resides in the fact that active attacks cannot be detected. Through a multipath routing strategy, this protocol enhances the security and performance of an ad hoc network by providing an invented solution based on network coding techniques and the public key cryptosystem. This solution, however, assumes that a routing or multipath protocol is already implemented, so no study of specific routing algorithm has been carried out. In other words, SPREAD relies on multiple simultaneous paths between the source and the destination in MANET but cannot detect the positions of malicious nodes.So our goal in this paper is not only to use multipath and secret sharing to improve availability and privacy but also to check the integrity of exchanged messages, in addition to locate the nodes suspected to be malicious.


### 2.1. System Model

Our architecture (totally invented by the author under patent N 42357 OMPIC, Casablanca, Morocco) is based on three essential steps to ensureavailability, confidentiality, and integrity. These three steps are Identification, Detection, Localization and Isolation and come after a substep of initializing variables.


#### 2.1.1. Initialization

This step is explained in Algorithm1.Algorithm 1:Initialization steps.
(i)
Step 1: source node S marks n paths to the destination D. Let Pn be the set of paths between S and D.
The value ofn varies from one node to another according to the neighborhood of each node.
(ii)
Step 2: S divides the message M using Shamir secret sharing scheme to n fragments F1,F2,…,Fn
(iii)
Step 3: the source then chooses one threshold k of the Shamir method k≤n,
k also varies according ton and the number of the node-disjoint paths
(iv)
Step 4: S encapsulates each fragment Fi in a packet and then sends it in a path Pi from Pn.
(v)
Step 5: the destination D receives r packets r≤n. Let Pr be the set of paths where D received r packets.
(vi)
Step 6: S receives r acknowledgments; let us suppose that a path is bidirectionally trusted/untrusted.


#### 2.1.2. Identification

As described, the destination will receiver fragments of the message. Each combination of k fragments is a version of the message M. In this step (Figure 2), we will consider a metric called black hole coefficient (BH) that will be assigned to each node in the network based on its observed behavior during transmission. This coefficient will be initialized by 0 for all NEs and will be increased and decreased based on our own algorithm defined in the SPIDLI method as explained below. This coefficient will be used later to detect and isolate malicious nodes (Algorithm 2).Figure 2
Organizational chart of identification step.Algorithm 2:Identification steps.
Step 1: in this step, destination D reconstructs the message M from the received fragments. Let Vm be the set of all possible versions of M. Let us discuss the possible scenarios:
(i)
If 0≤r<k, the destination cannot reconstruct the message M sent by S; Vm=∅. The source resends the missing fragments in the paths where the acknowledgments are received. In order to optimize the process for future transmission, the source returns to the initialization step and recalculates n and k so that n becomes equal to r. Let Pbh be the set of paths that may contain black holes.
In the casePbh=Pn−Pr, the source S assigns the value 1 to the black hole coefficient to all the nodes that constitute these paths.
∀
P
i
∈
P
b
h
,
∀
N
∈
P
i
,
B
H
N
=
1
(ii)
If r=k, the destination D can reconstruct one version of the message M using the Shamir method. In the case cardVm=1 and Pbh=Pn−Pr, the source S assigns the value 1 to the black hole coefficient to all the nodes that constitute these paths.
∀
P
i
∈
P
b
h
,
∀
N
∈
P
i
,
B
H
N
=
1
(iii)
If k+1≤r≤n, the destination, using Lagrange polynomial (Shamir method), can reconstruct many versions of the message. The associated Lagrange polynomial is written as follows:
L
0
=
∑
j
=
0
k
−
1
f
x
j
∐
m
=
0
,
m
≠
j
k
−
1
x
m
/
x
m
−
x
jThe destination can compare the reconstructed versions of the message using the following combination algorithm to ensure integrity.Combination Algorithm. The total number of possible combinations is as follows:(1)Crk=Arkk!=0,ifk>r,r!k!r−k!,if0≤k≤r.In practice, computing all combinations is a waste of time and resources. Thus, to optimize the computation process, we propose a minimal numberα of combinations that sweep all received fragments. The idea to achieve this is to put α=Roundupr/k which is the next smallest integer that is larger than r/k. Let Prl and Purl be the set of reliable paths and unreliable paths, respectively. Let Crli be the reliable combination number i and Csspo the suspicious combination number o 1≤i,o≤α (Algorithm 3).Algorithm 3: Combination algorithm.
Step 1: destination calculates the possible combinations that cover all the elements of our set F1,F2,…Fr
C
1
=
L
F
1
,
...
F
k
C
2
=
L
F
k
+
1
,
...
F
2
k
C
3
=
L
F
2
k
+
1
,
...
F
3
k
…
C
α
=
L
F
α
−
1
k
+
1
,
…
,
F
α
k
,
if,
r
is multiple of
k
L
The last
k
fragments
,
else
V
m
=
C
1
,
C
2
,
…
,
C
α
(i)
If ∀i,j∈1,αCi=Cj:
So all the pathsPj1≤j≤r are reliable paths, and the initial message sent by the source is equal to Ci,
∀
i
,
1
≤
i
≤
α
,
C
i
=
M
,
P
u
r
l
=
∅,
P
r
l
=
P
1
,
P
2
,
...
,
P
r
(ii)
If there are different combinations, and at least two equal combinations: So the equal combinations Crli (1 ≤ i ≤ α) are correct combinations equal to the message M. Therefore, the fragments which constitute these reliable combinations are necessarily all reliable fragments Frlij (1 ≤ j ≤ k). And the different combinations Csspo are suspect combinations constituted by suspicious fragments Fsspot (1 ≤ t ≤ k), that is why our method will proceed to the second step to locate the unreliable fragments that have been modified during transmission generating different combinations.So the equal combinationsCrli1≤i≤α are correct combinations equal to the message M. Therefore, the fragments which constitute these reliable combinations are necessarily all reliable fragments Frlij 1≤j≤k. And the different combinations Csspo1≤o≤α are suspect combinations constituted by suspicious fragments Fsspot1≤t≤k; this is why our method will proceed to the second step to locate the unreliable fragments that have been modified during transmission generating different combinations.


#### 2.1.3. Detection

LetFrl (reliable fragments) be the set of fragments Frlij (1≤i≤α and 1≤j≤k with Frlij=Frli−1k+j) which constitute equal and reliable combinations Crli 1≤i≤α. Let Fssp (suspicious fragments) be the set of fragments Fsspot (1≤o≤α and 1≤t≤k with Fsspot=Fsspo−1k+t) which give different combinations Csspo 1≤o≤α of suspect combination and then eliminate from Fssp all the reliable fragments which belong to Frl in order to have always Frl∩Fssp=∅.In this step (Figure3), we will consider a metric called unreliable coefficient (URL) that will be assigned to each node in the network based on its observed behavior during transmission. This coefficient will be initialized by 0 for all NEs and will be increased and decreased based on our own algorithm defined in the SPIDLI method as explained below. This coefficient will be used later to detect and isolate malicious nodes (Algorithm 4).Figure 3
Organizational chart of detection step.Algorithm 4:Detection steps.
Begin
Step 1: the destination performs permutations of one, and only one, suspect fragment Fsspoj∈Fssp, with a reliable fragment Frlij∈Frl. The permutation gives two combinations
C
p
1
=
L
F
r
l
i
1
,
…
,
F
s
s
p
o
j
,
…
,
F
r
l
i
k
C
p
2
=
L
F
s
s
p
o
1
,
...
,
F
r
l
i
j
,
…
.
,
F
s
s
p
o
k
,
1
≤
i
,
o
≤
α
Step 2: each time, the destination compares the computed combinations Cp1 and Cp2 with one of the reliable combinations Crli so
(i)
If Cp1≠Crli and Cp2≠Crli,Fsspoj is an unreliable fragment, because it gives an incorrect combination with a set of only reliable fragments. The destination, thus, updates the two sets Furl and Fssp; it eliminates the unreliable fragment Fsspoj from the set Fssp and puts it in the set Furl; it returns to step (1) to apply the permutation to the fragments remaining suspects in Cp2.
(ii)
If Cp1≠Crli and Cp2=Crli,Fsspoj is an unreliable fragment and all Cp2 fragments are reliable fragments The destination, thus, updates the sets Frl, Furl, and Fssp; it eliminates the unreliable fragment Fsspoj from the set Fssp and put it in the set of unreliable fragments Furl, and it eliminates all suspicious fragments of Cp2 from Fssp and put them in the set of reliable fragments Frl.
(iii)
If Cp1=Crli and Cp2≠Crli, Fsspoj is a reliable fragment, because it gives a correct combination with a set of only reliable fragments. The destination, thus, updates the two sets Frl and Fssp; it eliminates the unreliable fragment Fsspoj from the set Fssp and puts it in the set Frl; it returns to step (1) to apply the permutation to the fragments remaining suspects in Cp2.
Step 3: D checks if all suspicious fragments of Fssp are swept until Fssp=∅.
Step 4: In all previous cases, Pbh=Pn−Pr; the source S assigns the value 1 to the black hole coefficient to all the nodes that constitute these paths.
∀
P
i
∈
P
b
h
,
∀
N
∈
P
i
,
B
H
N
=
1
The destinationD assigns also the value 1 to the coefficient of unreliability URL to all the nodes which constitute the unreliable paths Purl. Then, S and D exchange this information.
∀
P
j
∈
P
u
r
l
,
∀
N
∈
P
j
,
U
R
L
N
=
1
END


#### 2.1.4. Location and Isolation

In this step (Figure4), broadcasting the information of the coefficients obtained in the previous steps allows the network to identify and locate black holes and unreliable nodes (Algorithm 5).Figure 4
Organizational chart of location and isolation step.Algorithm 5:Location and isolation steps.
Begin
Step 1: as long as there are intersections between paths containing black holes, several nodes will vote that the intersection node is a black hole; then, its BH≠0 and BH is higher than a specified threshold that will be fixed in advance. So all the nodes of the network will isolate this node and consider it as black hole.
Step 2: by the same process, the nodes suspected to be unreliable will be located and isolated too.
We initialize at all nodes of the network the coefficients black holeBH and unreliable URL to 0
∀ N is the node of the network BH (N) = 0 and URL (N) = 0
ENDProof of Concept.
Letn=12, k=4, and r=11 as shown in Figure 5.
The source divides the messageM on n=12 fragments, F1′,…F12′, with a threshold k=4 and sends each fragment Fi in a path Pi (Figure 5):(2)Pn=P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,P12.
The destination receivesr=11 fragments, F1,F2,..,F11:(3)Pr=P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,α=rounduprk,=roundup11/4=roundup2,75=3,C1=LF1,F2,F3,F4,C2=LF5,F6,F7,F8,C3=LF8,F9,F10,F11,where C1 and C2 are two correct combinations equal to the original message M sent by the source, but the combination C3 is not correct. Then,(4)Frl=F1,F2,F3,F4,F5,F6,F7,F8,Fssp=F8,F9,F10,F11,Furl=∅.
SinceF8∈Frl, Fssp=F9,F10,F11.
SwapF9 from incorrect combination C3 with F2 from the correct combination C1:(5)C1=LF1,F2,F3,F4,Cp1=LF1,F9,F3,F4,C3=LF8,F9,F10,F11,Cp1′=LF8,F2,F10,F11.
C
p
1
≠
C
1. So we are sure that the fragment F9 was modified during the transmission.
So,Frl=F1,F2,F3,F4,F5,F6,F7,F8, Furl=F9, and Fssp=F10,F11.
C
p
1
′
≠
C
1. So we are not sure if two fragments F10 and F11 are both unreliable or one of them; therefore, we will repeat another permutation of F10 of the new combination Cp1′ with F3 of C1:(6)C1=LF1,F2,F3,F4,Cp2=LF1,F2,F10,F4,Cp1′=LF8,F2,F10,F11,Cp2′=LF8,F2,F3,F11.
C
p
2
=
C
1. So we are sure that the fragment F10 was not modified during the transmission; thus, F10 is correct.
Then,Frl=F1,F2,F3,F4,F5,F6,F7,F8,F10, Furl=F9, and Fssp=F11.
C
p
2
′
≠
C
1. So we are sure that the fragment F11 has been modified during the transmission.
Then,Frl=F1,F2,F3,F4,F5,F6,F7,F8,F10, Furl=F9,F11, and Fssp=∅.Figure 5
Example scenario of the SPIDLI protocol.


## 2.1. System Model

Our architecture (totally invented by the author under patent N 42357 OMPIC, Casablanca, Morocco) is based on three essential steps to ensureavailability, confidentiality, and integrity. These three steps are Identification, Detection, Localization and Isolation and come after a substep of initializing variables.


### 2.1.1. Initialization

This step is explained in Algorithm1.Algorithm 1:Initialization steps.
(i)
Step 1: source node S marks n paths to the destination D. Let Pn be the set of paths between S and D.
The value ofn varies from one node to another according to the neighborhood of each node.
(ii)
Step 2: S divides the message M using Shamir secret sharing scheme to n fragments F1,F2,…,Fn
(iii)
Step 3: the source then chooses one threshold k of the Shamir method k≤n,
k also varies according ton and the number of the node-disjoint paths
(iv)
Step 4: S encapsulates each fragment Fi in a packet and then sends it in a path Pi from Pn.
(v)
Step 5: the destination D receives r packets r≤n. Let Pr be the set of paths where D received r packets.
(vi)
Step 6: S receives r acknowledgments; let us suppose that a path is bidirectionally trusted/untrusted.


### 2.1.2. Identification

As described, the destination will receiver fragments of the message. Each combination of k fragments is a version of the message M. In this step (Figure 2), we will consider a metric called black hole coefficient (BH) that will be assigned to each node in the network based on its observed behavior during transmission. This coefficient will be initialized by 0 for all NEs and will be increased and decreased based on our own algorithm defined in the SPIDLI method as explained below. This coefficient will be used later to detect and isolate malicious nodes (Algorithm 2).Figure 2
Organizational chart of identification step.Algorithm 2:Identification steps.
Step 1: in this step, destination D reconstructs the message M from the received fragments. Let Vm be the set of all possible versions of M. Let us discuss the possible scenarios:
(i)
If 0≤r<k, the destination cannot reconstruct the message M sent by S; Vm=∅. The source resends the missing fragments in the paths where the acknowledgments are received. In order to optimize the process for future transmission, the source returns to the initialization step and recalculates n and k so that n becomes equal to r. Let Pbh be the set of paths that may contain black holes.
In the casePbh=Pn−Pr, the source S assigns the value 1 to the black hole coefficient to all the nodes that constitute these paths.
∀
P
i
∈
P
b
h
,
∀
N
∈
P
i
,
B
H
N
=
1
(ii)
If r=k, the destination D can reconstruct one version of the message M using the Shamir method. In the case cardVm=1 and Pbh=Pn−Pr, the source S assigns the value 1 to the black hole coefficient to all the nodes that constitute these paths.
∀
P
i
∈
P
b
h
,
∀
N
∈
P
i
,
B
H
N
=
1
(iii)
If k+1≤r≤n, the destination, using Lagrange polynomial (Shamir method), can reconstruct many versions of the message. The associated Lagrange polynomial is written as follows:
L
0
=
∑
j
=
0
k
−
1
f
x
j
∐
m
=
0
,
m
≠
j
k
−
1
x
m
/
x
m
−
x
jThe destination can compare the reconstructed versions of the message using the following combination algorithm to ensure integrity.Combination Algorithm. The total number of possible combinations is as follows:(1)Crk=Arkk!=0,ifk>r,r!k!r−k!,if0≤k≤r.In practice, computing all combinations is a waste of time and resources. Thus, to optimize the computation process, we propose a minimal numberα of combinations that sweep all received fragments. The idea to achieve this is to put α=Roundupr/k which is the next smallest integer that is larger than r/k. Let Prl and Purl be the set of reliable paths and unreliable paths, respectively. Let Crli be the reliable combination number i and Csspo the suspicious combination number o 1≤i,o≤α (Algorithm 3).Algorithm 3: Combination algorithm.
Step 1: destination calculates the possible combinations that cover all the elements of our set F1,F2,…Fr
C
1
=
L
F
1
,
...
F
k
C
2
=
L
F
k
+
1
,
...
F
2
k
C
3
=
L
F
2
k
+
1
,
...
F
3
k
…
C
α
=
L
F
α
−
1
k
+
1
,
…
,
F
α
k
,
if,
r
is multiple of
k
L
The last
k
fragments
,
else
V
m
=
C
1
,
C
2
,
…
,
C
α
(i)
If ∀i,j∈1,αCi=Cj:
So all the pathsPj1≤j≤r are reliable paths, and the initial message sent by the source is equal to Ci,
∀
i
,
1
≤
i
≤
α
,
C
i
=
M
,
P
u
r
l
=
∅,
P
r
l
=
P
1
,
P
2
,
...
,
P
r
(ii)
If there are different combinations, and at least two equal combinations: So the equal combinations Crli (1 ≤ i ≤ α) are correct combinations equal to the message M. Therefore, the fragments which constitute these reliable combinations are necessarily all reliable fragments Frlij (1 ≤ j ≤ k). And the different combinations Csspo are suspect combinations constituted by suspicious fragments Fsspot (1 ≤ t ≤ k), that is why our method will proceed to the second step to locate the unreliable fragments that have been modified during transmission generating different combinations.So the equal combinationsCrli1≤i≤α are correct combinations equal to the message M. Therefore, the fragments which constitute these reliable combinations are necessarily all reliable fragments Frlij 1≤j≤k. And the different combinations Csspo1≤o≤α are suspect combinations constituted by suspicious fragments Fsspot1≤t≤k; this is why our method will proceed to the second step to locate the unreliable fragments that have been modified during transmission generating different combinations.


### 2.1.3. Detection

LetFrl (reliable fragments) be the set of fragments Frlij (1≤i≤α and 1≤j≤k with Frlij=Frli−1k+j) which constitute equal and reliable combinations Crli 1≤i≤α. Let Fssp (suspicious fragments) be the set of fragments Fsspot (1≤o≤α and 1≤t≤k with Fsspot=Fsspo−1k+t) which give different combinations Csspo 1≤o≤α of suspect combination and then eliminate from Fssp all the reliable fragments which belong to Frl in order to have always Frl∩Fssp=∅.In this step (Figure3), we will consider a metric called unreliable coefficient (URL) that will be assigned to each node in the network based on its observed behavior during transmission. This coefficient will be initialized by 0 for all NEs and will be increased and decreased based on our own algorithm defined in the SPIDLI method as explained below. This coefficient will be used later to detect and isolate malicious nodes (Algorithm 4).Figure 3
Organizational chart of detection step.Algorithm 4:Detection steps.
Begin
Step 1: the destination performs permutations of one, and only one, suspect fragment Fsspoj∈Fssp, with a reliable fragment Frlij∈Frl. The permutation gives two combinations
C
p
1
=
L
F
r
l
i
1
,
…
,
F
s
s
p
o
j
,
…
,
F
r
l
i
k
C
p
2
=
L
F
s
s
p
o
1
,
...
,
F
r
l
i
j
,
…
.
,
F
s
s
p
o
k
,
1
≤
i
,
o
≤
α
Step 2: each time, the destination compares the computed combinations Cp1 and Cp2 with one of the reliable combinations Crli so
(i)
If Cp1≠Crli and Cp2≠Crli,Fsspoj is an unreliable fragment, because it gives an incorrect combination with a set of only reliable fragments. The destination, thus, updates the two sets Furl and Fssp; it eliminates the unreliable fragment Fsspoj from the set Fssp and puts it in the set Furl; it returns to step (1) to apply the permutation to the fragments remaining suspects in Cp2.
(ii)
If Cp1≠Crli and Cp2=Crli,Fsspoj is an unreliable fragment and all Cp2 fragments are reliable fragments The destination, thus, updates the sets Frl, Furl, and Fssp; it eliminates the unreliable fragment Fsspoj from the set Fssp and put it in the set of unreliable fragments Furl, and it eliminates all suspicious fragments of Cp2 from Fssp and put them in the set of reliable fragments Frl.
(iii)
If Cp1=Crli and Cp2≠Crli, Fsspoj is a reliable fragment, because it gives a correct combination with a set of only reliable fragments. The destination, thus, updates the two sets Frl and Fssp; it eliminates the unreliable fragment Fsspoj from the set Fssp and puts it in the set Frl; it returns to step (1) to apply the permutation to the fragments remaining suspects in Cp2.
Step 3: D checks if all suspicious fragments of Fssp are swept until Fssp=∅.
Step 4: In all previous cases, Pbh=Pn−Pr; the source S assigns the value 1 to the black hole coefficient to all the nodes that constitute these paths.
∀
P
i
∈
P
b
h
,
∀
N
∈
P
i
,
B
H
N
=
1
The destinationD assigns also the value 1 to the coefficient of unreliability URL to all the nodes which constitute the unreliable paths Purl. Then, S and D exchange this information.
∀
P
j
∈
P
u
r
l
,
∀
N
∈
P
j
,
U
R
L
N
=
1
END


### 2.1.4. Location and Isolation

In this step (Figure4), broadcasting the information of the coefficients obtained in the previous steps allows the network to identify and locate black holes and unreliable nodes (Algorithm 5).Figure 4
Organizational chart of location and isolation step.Algorithm 5:Location and isolation steps.
Begin
Step 1: as long as there are intersections between paths containing black holes, several nodes will vote that the intersection node is a black hole; then, its BH≠0 and BH is higher than a specified threshold that will be fixed in advance. So all the nodes of the network will isolate this node and consider it as black hole.
Step 2: by the same process, the nodes suspected to be unreliable will be located and isolated too.
We initialize at all nodes of the network the coefficients black holeBH and unreliable URL to 0
∀ N is the node of the network BH (N) = 0 and URL (N) = 0
ENDProof of Concept.
Letn=12, k=4, and r=11 as shown in Figure 5.
The source divides the messageM on n=12 fragments, F1′,…F12′, with a threshold k=4 and sends each fragment Fi in a path Pi (Figure 5):(2)Pn=P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,P12.
The destination receivesr=11 fragments, F1,F2,..,F11:(3)Pr=P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,α=rounduprk,=roundup11/4=roundup2,75=3,C1=LF1,F2,F3,F4,C2=LF5,F6,F7,F8,C3=LF8,F9,F10,F11,where C1 and C2 are two correct combinations equal to the original message M sent by the source, but the combination C3 is not correct. Then,(4)Frl=F1,F2,F3,F4,F5,F6,F7,F8,Fssp=F8,F9,F10,F11,Furl=∅.
SinceF8∈Frl, Fssp=F9,F10,F11.
SwapF9 from incorrect combination C3 with F2 from the correct combination C1:(5)C1=LF1,F2,F3,F4,Cp1=LF1,F9,F3,F4,C3=LF8,F9,F10,F11,Cp1′=LF8,F2,F10,F11.
C
p
1
≠
C
1. So we are sure that the fragment F9 was modified during the transmission.
So,Frl=F1,F2,F3,F4,F5,F6,F7,F8, Furl=F9, and Fssp=F10,F11.
C
p
1
′
≠
C
1. So we are not sure if two fragments F10 and F11 are both unreliable or one of them; therefore, we will repeat another permutation of F10 of the new combination Cp1′ with F3 of C1:(6)C1=LF1,F2,F3,F4,Cp2=LF1,F2,F10,F4,Cp1′=LF8,F2,F10,F11,Cp2′=LF8,F2,F3,F11.
C
p
2
=
C
1. So we are sure that the fragment F10 was not modified during the transmission; thus, F10 is correct.
Then,Frl=F1,F2,F3,F4,F5,F6,F7,F8,F10, Furl=F9, and Fssp=F11.
C
p
2
′
≠
C
1. So we are sure that the fragment F11 has been modified during the transmission.
Then,Frl=F1,F2,F3,F4,F5,F6,F7,F8,F10, Furl=F9,F11, and Fssp=∅.Figure 5
Example scenario of the SPIDLI protocol.


## 2.1.1. Initialization

This step is explained in Algorithm1.Algorithm 1:Initialization steps.
(i)
Step 1: source node S marks n paths to the destination D. Let Pn be the set of paths between S and D.
The value ofn varies from one node to another according to the neighborhood of each node.
(ii)
Step 2: S divides the message M using Shamir secret sharing scheme to n fragments F1,F2,…,Fn
(iii)
Step 3: the source then chooses one threshold k of the Shamir method k≤n,
k also varies according ton and the number of the node-disjoint paths
(iv)
Step 4: S encapsulates each fragment Fi in a packet and then sends it in a path Pi from Pn.
(v)
Step 5: the destination D receives r packets r≤n. Let Pr be the set of paths where D received r packets.
(vi)
Step 6: S receives r acknowledgments; let us suppose that a path is bidirectionally trusted/untrusted.


## 2.1.2. Identification

As described, the destination will receiver fragments of the message. Each combination of k fragments is a version of the message M. In this step (Figure 2), we will consider a metric called black hole coefficient (BH) that will be assigned to each node in the network based on its observed behavior during transmission. This coefficient will be initialized by 0 for all NEs and will be increased and decreased based on our own algorithm defined in the SPIDLI method as explained below. This coefficient will be used later to detect and isolate malicious nodes (Algorithm 2).Figure 2
Organizational chart of identification step.Algorithm 2:Identification steps.
Step 1: in this step, destination D reconstructs the message M from the received fragments. Let Vm be the set of all possible versions of M. Let us discuss the possible scenarios:
(i)
If 0≤r<k, the destination cannot reconstruct the message M sent by S; Vm=∅. The source resends the missing fragments in the paths where the acknowledgments are received. In order to optimize the process for future transmission, the source returns to the initialization step and recalculates n and k so that n becomes equal to r. Let Pbh be the set of paths that may contain black holes.
In the casePbh=Pn−Pr, the source S assigns the value 1 to the black hole coefficient to all the nodes that constitute these paths.
∀
P
i
∈
P
b
h
,
∀
N
∈
P
i
,
B
H
N
=
1
(ii)
If r=k, the destination D can reconstruct one version of the message M using the Shamir method. In the case cardVm=1 and Pbh=Pn−Pr, the source S assigns the value 1 to the black hole coefficient to all the nodes that constitute these paths.
∀
P
i
∈
P
b
h
,
∀
N
∈
P
i
,
B
H
N
=
1
(iii)
If k+1≤r≤n, the destination, using Lagrange polynomial (Shamir method), can reconstruct many versions of the message. The associated Lagrange polynomial is written as follows:
L
0
=
∑
j
=
0
k
−
1
f
x
j
∐
m
=
0
,
m
≠
j
k
−
1
x
m
/
x
m
−
x
jThe destination can compare the reconstructed versions of the message using the following combination algorithm to ensure integrity.Combination Algorithm. The total number of possible combinations is as follows:(1)Crk=Arkk!=0,ifk>r,r!k!r−k!,if0≤k≤r.In practice, computing all combinations is a waste of time and resources. Thus, to optimize the computation process, we propose a minimal numberα of combinations that sweep all received fragments. The idea to achieve this is to put α=Roundupr/k which is the next smallest integer that is larger than r/k. Let Prl and Purl be the set of reliable paths and unreliable paths, respectively. Let Crli be the reliable combination number i and Csspo the suspicious combination number o 1≤i,o≤α (Algorithm 3).Algorithm 3: Combination algorithm.
Step 1: destination calculates the possible combinations that cover all the elements of our set F1,F2,…Fr
C
1
=
L
F
1
,
...
F
k
C
2
=
L
F
k
+
1
,
...
F
2
k
C
3
=
L
F
2
k
+
1
,
...
F
3
k
…
C
α
=
L
F
α
−
1
k
+
1
,
…
,
F
α
k
,
if,
r
is multiple of
k
L
The last
k
fragments
,
else
V
m
=
C
1
,
C
2
,
…
,
C
α
(i)
If ∀i,j∈1,αCi=Cj:
So all the pathsPj1≤j≤r are reliable paths, and the initial message sent by the source is equal to Ci,
∀
i
,
1
≤
i
≤
α
,
C
i
=
M
,
P
u
r
l
=
∅,
P
r
l
=
P
1
,
P
2
,
...
,
P
r
(ii)
If there are different combinations, and at least two equal combinations: So the equal combinations Crli (1 ≤ i ≤ α) are correct combinations equal to the message M. Therefore, the fragments which constitute these reliable combinations are necessarily all reliable fragments Frlij (1 ≤ j ≤ k). And the different combinations Csspo are suspect combinations constituted by suspicious fragments Fsspot (1 ≤ t ≤ k), that is why our method will proceed to the second step to locate the unreliable fragments that have been modified during transmission generating different combinations.So the equal combinationsCrli1≤i≤α are correct combinations equal to the message M. Therefore, the fragments which constitute these reliable combinations are necessarily all reliable fragments Frlij 1≤j≤k. And the different combinations Csspo1≤o≤α are suspect combinations constituted by suspicious fragments Fsspot1≤t≤k; this is why our method will proceed to the second step to locate the unreliable fragments that have been modified during transmission generating different combinations.


## 2.1.3. Detection

LetFrl (reliable fragments) be the set of fragments Frlij (1≤i≤α and 1≤j≤k with Frlij=Frli−1k+j) which constitute equal and reliable combinations Crli 1≤i≤α. Let Fssp (suspicious fragments) be the set of fragments Fsspot (1≤o≤α and 1≤t≤k with Fsspot=Fsspo−1k+t) which give different combinations Csspo 1≤o≤α of suspect combination and then eliminate from Fssp all the reliable fragments which belong to Frl in order to have always Frl∩Fssp=∅.In this step (Figure3), we will consider a metric called unreliable coefficient (URL) that will be assigned to each node in the network based on its observed behavior during transmission. This coefficient will be initialized by 0 for all NEs and will be increased and decreased based on our own algorithm defined in the SPIDLI method as explained below. This coefficient will be used later to detect and isolate malicious nodes (Algorithm 4).Figure 3
Organizational chart of detection step.Algorithm 4:Detection steps.
Begin
Step 1: the destination performs permutations of one, and only one, suspect fragment Fsspoj∈Fssp, with a reliable fragment Frlij∈Frl. The permutation gives two combinations
C
p
1
=
L
F
r
l
i
1
,
…
,
F
s
s
p
o
j
,
…
,
F
r
l
i
k
C
p
2
=
L
F
s
s
p
o
1
,
...
,
F
r
l
i
j
,
…
.
,
F
s
s
p
o
k
,
1
≤
i
,
o
≤
α
Step 2: each time, the destination compares the computed combinations Cp1 and Cp2 with one of the reliable combinations Crli so
(i)
If Cp1≠Crli and Cp2≠Crli,Fsspoj is an unreliable fragment, because it gives an incorrect combination with a set of only reliable fragments. The destination, thus, updates the two sets Furl and Fssp; it eliminates the unreliable fragment Fsspoj from the set Fssp and puts it in the set Furl; it returns to step (1) to apply the permutation to the fragments remaining suspects in Cp2.
(ii)
If Cp1≠Crli and Cp2=Crli,Fsspoj is an unreliable fragment and all Cp2 fragments are reliable fragments The destination, thus, updates the sets Frl, Furl, and Fssp; it eliminates the unreliable fragment Fsspoj from the set Fssp and put it in the set of unreliable fragments Furl, and it eliminates all suspicious fragments of Cp2 from Fssp and put them in the set of reliable fragments Frl.
(iii)
If Cp1=Crli and Cp2≠Crli, Fsspoj is a reliable fragment, because it gives a correct combination with a set of only reliable fragments. The destination, thus, updates the two sets Frl and Fssp; it eliminates the unreliable fragment Fsspoj from the set Fssp and puts it in the set Frl; it returns to step (1) to apply the permutation to the fragments remaining suspects in Cp2.
Step 3: D checks if all suspicious fragments of Fssp are swept until Fssp=∅.
Step 4: In all previous cases, Pbh=Pn−Pr; the source S assigns the value 1 to the black hole coefficient to all the nodes that constitute these paths.
∀
P
i
∈
P
b
h
,
∀
N
∈
P
i
,
B
H
N
=
1
The destinationD assigns also the value 1 to the coefficient of unreliability URL to all the nodes which constitute the unreliable paths Purl. Then, S and D exchange this information.
∀
P
j
∈
P
u
r
l
,
∀
N
∈
P
j
,
U
R
L
N
=
1
END


## 2.1.4. Location and Isolation

In this step (Figure4), broadcasting the information of the coefficients obtained in the previous steps allows the network to identify and locate black holes and unreliable nodes (Algorithm 5).Figure 4
Organizational chart of location and isolation step.Algorithm 5:Location and isolation steps.
Begin
Step 1: as long as there are intersections between paths containing black holes, several nodes will vote that the intersection node is a black hole; then, its BH≠0 and BH is higher than a specified threshold that will be fixed in advance. So all the nodes of the network will isolate this node and consider it as black hole.
Step 2: by the same process, the nodes suspected to be unreliable will be located and isolated too.
We initialize at all nodes of the network the coefficients black holeBH and unreliable URL to 0
∀ N is the node of the network BH (N) = 0 and URL (N) = 0
ENDProof of Concept.
Letn=12, k=4, and r=11 as shown in Figure 5.
The source divides the messageM on n=12 fragments, F1′,…F12′, with a threshold k=4 and sends each fragment Fi in a path Pi (Figure 5):(2)Pn=P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,P12.
The destination receivesr=11 fragments, F1,F2,..,F11:(3)Pr=P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,α=rounduprk,=roundup11/4=roundup2,75=3,C1=LF1,F2,F3,F4,C2=LF5,F6,F7,F8,C3=LF8,F9,F10,F11,where C1 and C2 are two correct combinations equal to the original message M sent by the source, but the combination C3 is not correct. Then,(4)Frl=F1,F2,F3,F4,F5,F6,F7,F8,Fssp=F8,F9,F10,F11,Furl=∅.
SinceF8∈Frl, Fssp=F9,F10,F11.
SwapF9 from incorrect combination C3 with F2 from the correct combination C1:(5)C1=LF1,F2,F3,F4,Cp1=LF1,F9,F3,F4,C3=LF8,F9,F10,F11,Cp1′=LF8,F2,F10,F11.
C
p
1
≠
C
1. So we are sure that the fragment F9 was modified during the transmission.
So,Frl=F1,F2,F3,F4,F5,F6,F7,F8, Furl=F9, and Fssp=F10,F11.
C
p
1
′
≠
C
1. So we are not sure if two fragments F10 and F11 are both unreliable or one of them; therefore, we will repeat another permutation of F10 of the new combination Cp1′ with F3 of C1:(6)C1=LF1,F2,F3,F4,Cp2=LF1,F2,F10,F4,Cp1′=LF8,F2,F10,F11,Cp2′=LF8,F2,F3,F11.
C
p
2
=
C
1. So we are sure that the fragment F10 was not modified during the transmission; thus, F10 is correct.
Then,Frl=F1,F2,F3,F4,F5,F6,F7,F8,F10, Furl=F9, and Fssp=F11.
C
p
2
′
≠
C
1. So we are sure that the fragment F11 has been modified during the transmission.
Then,Frl=F1,F2,F3,F4,F5,F6,F7,F8,F10, Furl=F9,F11, and Fssp=∅.Figure 5
Example scenario of the SPIDLI protocol.


## 3. Analytical Results

In order to evaluate our protocol SPIDLI, and their impact on network performances, we have implemented a simulation in the NS2 platform with the objective of evaluating the efficiency of our solution. We have compared our method with standard MPOLSR in a medium size ad hoc network under a random black hole attack. The used parameters are shown in Table1:Table 1
Parameters value.
Parameter
Value
Routing protocol
SPIDLI/MPOLSR
Simulation time
250 seconds
Number of nodes
10, 20, 30, 40, 50, 60, 70, 80, 90, and 100 nodes
Environment area
1000 meter × 1000 meter
MAC protocol
IEEE 802.11
Transport layer
Transmission control protocol (TCP)
Maximum speeds
5 meter/second
Mobility model
Random waypointIn this simulation, we will observe three main metrics: MDR (message delivery ratio), end-to-end delay, and throughput. We will compare the standard MPOLSR and SPIDLI. We used in our simulation the MPOLSR type which is based on load sharing.Figure6 shows the evolution of message delivery ratio with network density in both MPOLSR and SPIDLI in case of a black hole attack average of 20% of nodes number. The simulation result shows clearly that our method improves the MDR comparing with standard MPOLSR. The objective of SPIDLI is to increase the chance of a message to reach the destination node. This objective is achieved according to the simulation result. We can observe also that the MDR increases with network density, which is explained by the fact that having a high number of nodes gives more available routes (high threshold k) to reroute the message from the source to destination.Figure 6
Message delivery ratio graph.In this graph (Figure7), we analyze the average delay evolution according to network density for MPOLSR and SPIDLI protocols with black hole attack. When network density is relatively small, the number of paths in SPIDLI is nearly the same as MPOLSR; thus the threshold k is smaller (equal to 1 or 2). As a result, the calculation processing does not impact the end-to-end delay. However, when the density becomes higher, we observe that the end-to-end delay increases specially in case of SPIDLI. This can be justified by the fact that each node performs extra processing for x or calculation and queuing operations in order to reconstruct the initial message. In addition, the paths selected using SPIDLI may be longer than those selected using standard MPOLSR, which may also generate more delay.Figure 7
End-to-end delay graph.In Figure8 we analyze the evolution of average throughput in function of network density in a simulation of mobile networks with attacks of both MPOLSR and SPIDLI. We can see that throughput in case of SPIDLI is slightly higher than MPOLSR in a network with more than 50 nodes. This behavior can be explained by the fact that SPIDLI generates extra packets more than MPOLSR. In addition, the dropped packets in MPOLSR are retransmitted which affects the throughput.Figure 8
Throughput graph.


## 4. Conclusion

As conclusion, with the emerging IoT and smart cities, the security aspect becomes more and more insisting and research and studies are highly recommended. In this context, we have invented a new method named SPIDLI where we provide a scheme aiming to prevent some security threats especially black holes, message tampering, and eavesdropping attacks putting at risk the availability, integrity, and confidentiality (respectively) of data in ad hoc networks. This security prevention is mandatory in some cases of IoT where the exchanged information is sensitive and confidential. We have implemented our solution in the NS2 simulation environment to compare it with the standard MPOLSR protocol and found some considerable results. As future work, we will try to optimize our solution to enhance the performance in terms of end-to-end delay and evaluate other important KPIs such as energy consumption and jitter.



---

*Source: 1468976-2020-04-04.xml*