06-02-2013, 02:52 PM
Distributed Detection of Clone Attacks in Wireless Sensor Networks
[attachment=49846]
Abstract
Wireless sensor networks (WSNs) are often deployed
in hostile environments where an adversary can physically
capture some of the nodes, first re-program and then replicate
them in a large number of clones, easily taking over the network.
A few distributed solutions to address this fundamental problem
have been recently proposed. However, these solutions are not
satisfactory. First, they are energy and memory demanding:
A serious drawback for any protocol to be used in the WSN
resource constrained environment. Further, they are vulnerable
to specific adversary models introduced in this paper. The contributions
of this work are threefold. First, we analyze the desirable
properties of a distributed mechanism for the detection of node
replication attacks. Second, we show that the known solutions for
this problem do not completely meet our requirements. Third, we
propose a new self-healing, randomized, efficient, and distributed
protocol (RED) for the detection of node replication attacks, and
we show that it satisfies the introduced requirements. Finally,
extensive simulations show that our protocol: Is highly efficient
in communication, memory, and computation; is much more
effective that competing solutions in the literature; is resistant
to the new kind of attacks introduced in this paper, while other
solutions are not.
INTRODUCTION
AWireless Sensor Network (WSN) is a collection of sensors
with limited resources that collaborate to achieve a common
goal. WSNs can be deployed in harsh environments to fulfil
both military and civil applications [1]. Due to their operating
nature, they are often unattended, hence prone to different
kinds of novel attacks. For instance, an adversary could eavesdrop
all network communications; further, an adversary could
capture nodes acquiring all the information stored therein
—sensors are commonly assumed to be not tamper proof.
Therefore, an adversary may replicate captured sensors and
deploy them in the network to launch a variety of malicious
activities. This attack is referred to as the clone attack [53],
[11], [34]. Since a clone has legitimate information (code
and cryptographic material), it may participate in the network
operations in the same way as a non-compromised node; hence
cloned nodes can launch a variety of attacks.
RELATED WORK
One of the first solutions for the detection of clone attacks
relies on a centralized Base Station (BS) [33]. In this solution,
each node sends a list of its neighbors and their locations
(that is the geographical coordinates of each node) to a BS.
The same node ID in two lists with inconsistent locations will
result in a clone detection. Then, the BS revokes the clones.
This solution has several drawbacks, such as the presence of a
single point of failure (the BS) and high communication cost
due to the large number of messages. Further, nodes close to
the BS will be required to route much more messages than
other nodes, hence shortening their operational life.
Another centralized clone detection protocol has been recently
proposed in [6]. This solution assumes that a random
key pre-distribution security scheme is implemented in the
sensor network. That is, each node is assigned a set of k
symmetric keys, randomly selected from a larger pool of
keys [33]. For the detection, each node constructs a counting
Bloom filter from the keys it uses for communication. Then,
each node sends its own filter to the BS. From all the reports,
the BS counts the number of times each key is used in the
network. The keys used too often (above a threshold) are
considered cloned and a corresponding revocation procedure
is raised.
THE THREAT MODEL
We define a simple yet powerful adversary: It can compromise
a certain fixed amount of nodes and replicate one or
more into multiple copies (the clones). In general, to cope
with this threat it could be possible to assume that nodes are
tamper-proof. However, tamper proof hardware is expensive
and energy demanding [2], [1]. Therefore, consistently with a
large part of the literature, we will assume that the nodes do
not have tamper proof components. The adversary goal is to
prevent clones from being detected by the detection protocol
used in the network. Hence, we assume that the adversary, to
reach its goal, also tries to subvert the nodes that will possibly
act as witnesses.
Witness distribution
Due to randomization, it is straightforward to verify that
both LSM and RED are ID-oblivious. In both protocols the IDs
of the witnesses are randomly selected among all the nodes
in the network. To assess area-obliviousness, we study the
witness distribution as follows: We select increasing sub-areas
of the network, and for each sub-area we count the number
of witnesses present in the area after a run of the detection
protocol. Each sub-area from the center of the unit-square
towards the external border provides an increment of 5% of
the total area. Hence, 20 sub-areas are considered.
CONCLUDING REMARKS
In this paper we presented and justified a few basic requirements
an ideal protocol for distributed detection of node
replicas should have. In particular, we have introduced the
preliminary notion of ID-obliviousness and area-obliviousness
that convey a measure of the quality of the node replicas
detection protocol; that is, its resilience to a smart adversary.
Moreover, we have indicated that the overhead of such a
protocol should be not only small, but also evenly distributed
among the nodes, both in computation and memory. Further,
we have introduced new adversary threat models. However,
a major contribution of this paper is the proposal of a selfhealing,
randomized, efficient, and distributed protocol (RED)
to detect node replication attacks. We analytically compared
RED with the state of the art solution (LSM) and proved that
the overhead introduced by RED is low and almost evenly
balanced among the nodes; RED is both ID-oblivious and
area-oblivious; furthermore, RED outperforms LSM in terms
of efficiency and effectiveness.
[attachment=49846]
Abstract
Wireless sensor networks (WSNs) are often deployed
in hostile environments where an adversary can physically
capture some of the nodes, first re-program and then replicate
them in a large number of clones, easily taking over the network.
A few distributed solutions to address this fundamental problem
have been recently proposed. However, these solutions are not
satisfactory. First, they are energy and memory demanding:
A serious drawback for any protocol to be used in the WSN
resource constrained environment. Further, they are vulnerable
to specific adversary models introduced in this paper. The contributions
of this work are threefold. First, we analyze the desirable
properties of a distributed mechanism for the detection of node
replication attacks. Second, we show that the known solutions for
this problem do not completely meet our requirements. Third, we
propose a new self-healing, randomized, efficient, and distributed
protocol (RED) for the detection of node replication attacks, and
we show that it satisfies the introduced requirements. Finally,
extensive simulations show that our protocol: Is highly efficient
in communication, memory, and computation; is much more
effective that competing solutions in the literature; is resistant
to the new kind of attacks introduced in this paper, while other
solutions are not.
INTRODUCTION
AWireless Sensor Network (WSN) is a collection of sensors
with limited resources that collaborate to achieve a common
goal. WSNs can be deployed in harsh environments to fulfil
both military and civil applications [1]. Due to their operating
nature, they are often unattended, hence prone to different
kinds of novel attacks. For instance, an adversary could eavesdrop
all network communications; further, an adversary could
capture nodes acquiring all the information stored therein
—sensors are commonly assumed to be not tamper proof.
Therefore, an adversary may replicate captured sensors and
deploy them in the network to launch a variety of malicious
activities. This attack is referred to as the clone attack [53],
[11], [34]. Since a clone has legitimate information (code
and cryptographic material), it may participate in the network
operations in the same way as a non-compromised node; hence
cloned nodes can launch a variety of attacks.
RELATED WORK
One of the first solutions for the detection of clone attacks
relies on a centralized Base Station (BS) [33]. In this solution,
each node sends a list of its neighbors and their locations
(that is the geographical coordinates of each node) to a BS.
The same node ID in two lists with inconsistent locations will
result in a clone detection. Then, the BS revokes the clones.
This solution has several drawbacks, such as the presence of a
single point of failure (the BS) and high communication cost
due to the large number of messages. Further, nodes close to
the BS will be required to route much more messages than
other nodes, hence shortening their operational life.
Another centralized clone detection protocol has been recently
proposed in [6]. This solution assumes that a random
key pre-distribution security scheme is implemented in the
sensor network. That is, each node is assigned a set of k
symmetric keys, randomly selected from a larger pool of
keys [33]. For the detection, each node constructs a counting
Bloom filter from the keys it uses for communication. Then,
each node sends its own filter to the BS. From all the reports,
the BS counts the number of times each key is used in the
network. The keys used too often (above a threshold) are
considered cloned and a corresponding revocation procedure
is raised.
THE THREAT MODEL
We define a simple yet powerful adversary: It can compromise
a certain fixed amount of nodes and replicate one or
more into multiple copies (the clones). In general, to cope
with this threat it could be possible to assume that nodes are
tamper-proof. However, tamper proof hardware is expensive
and energy demanding [2], [1]. Therefore, consistently with a
large part of the literature, we will assume that the nodes do
not have tamper proof components. The adversary goal is to
prevent clones from being detected by the detection protocol
used in the network. Hence, we assume that the adversary, to
reach its goal, also tries to subvert the nodes that will possibly
act as witnesses.
Witness distribution
Due to randomization, it is straightforward to verify that
both LSM and RED are ID-oblivious. In both protocols the IDs
of the witnesses are randomly selected among all the nodes
in the network. To assess area-obliviousness, we study the
witness distribution as follows: We select increasing sub-areas
of the network, and for each sub-area we count the number
of witnesses present in the area after a run of the detection
protocol. Each sub-area from the center of the unit-square
towards the external border provides an increment of 5% of
the total area. Hence, 20 sub-areas are considered.
CONCLUDING REMARKS
In this paper we presented and justified a few basic requirements
an ideal protocol for distributed detection of node
replicas should have. In particular, we have introduced the
preliminary notion of ID-obliviousness and area-obliviousness
that convey a measure of the quality of the node replicas
detection protocol; that is, its resilience to a smart adversary.
Moreover, we have indicated that the overhead of such a
protocol should be not only small, but also evenly distributed
among the nodes, both in computation and memory. Further,
we have introduced new adversary threat models. However,
a major contribution of this paper is the proposal of a selfhealing,
randomized, efficient, and distributed protocol (RED)
to detect node replication attacks. We analytically compared
RED with the state of the art solution (LSM) and proved that
the overhead introduced by RED is low and almost evenly
balanced among the nodes; RED is both ID-oblivious and
area-oblivious; furthermore, RED outperforms LSM in terms
of efficiency and effectiveness.