11-10-2016, 11:36 AM
1458578905-CatchingPacketDroppersandModifiers.pdf (Size: 386.02 KB / Downloads: 6)
Abstract—Packet dropping and modification are common attacks that can be launched by an adversary to disrupt communication in
wireless multihop sensor networks. Many schemes have been proposed to mitigate or tolerate such attacks, but very few can
effectively and efficiently identify the intruders. To address this problem, we propose a simple yet effective scheme, which can identify
misbehaving forwarders that drop or modify packets. Extensive analysis and simulations have been conducted to verify the
effectiveness and efficiency of the scheme.
INTRODUCTION
I
N a wireless sensor network, sensor nodes monitor the
environment, detect events of interest, produce data, and
collaborate in forwarding the data toward a sink, which
could be a gateway, base station, storage node, or querying
user. Because of the ease of deployment, the low cost of
sensor nodes and the capability of self-organization, a
sensor network is often deployed in an unattended and
hostile environment to perform the monitoring and data
collection tasks. When it is deployed in such an environment,
it lacks physical protection and is subject to node
compromise. After compromising one or multiple sensor
nodes, an adversary may launch various attacks [1] to
disrupt the in-network communication. Among these
attacks, two common ones are dropping packets and modifying
packets, i.e., compromised nodes drop or modify the
packets that they are supposed to forward.
To deal with packet droppers, a widely adopted countermeasure
is multipath forwarding [2], [3], [4], [5], in which
each packet is forwarded along multiple redundant paths
and hence packet dropping in some but not all of these
paths can be tolerated. To deal with packet modifiers, most
of existing countermeasures [6], [7], [8], [9] aim to filter
modified messages en-route within a certain number of
hops. These countermeasures can tolerate or mitigate the
packet dropping and modification attacks, but the intruders
are still there and can continue attacking the network
without being caught.
To locate and identify packet droppers and modifiers, it
has been proposed that nodes continuously monitor the forwarding behaviors of their neighbors [10], [11], [12], [13],
[14], [15] to determine if their neighbors are misbehaving,
and the approach can be extended by using the reputationbased
mechanisms to allow nodes to infer whether a
nonneighbor node is trustable [16], [17], [18], [19]. This
methodology may be subject to high-energy cost incurred
by the promiscuous operating mode of wireless interface;
moreover, the reputation mechanisms have to be exercised
with cautions to avoid or mitigate bad mouth attacks and
others. Recently, Ye et al. proposed a probabilistic nested
marking (PNM) scheme [20]. But with the PNM scheme,
modified packets should not be filtered out en route
because they should be used as evidence to infer packet
modifiers; hence, it cannot be used together with existing
packet filtering schemes.
In this paper, we propose a simple yet effective scheme
to catch both packet droppers and modifiers. In this scheme,
a routing tree rooted at the sink is first established. When
sensor data are transmitted along the tree structure toward
the sink, each packet sender or forwarder adds a small
number of extra bits, which is called packet marks, to the
packet. The format of the small packet marks is deliberately
designed such that the sink can obtain very useful
information from the marks. Specifically, based on the
packet marks, the sink can figure out the dropping ratio
associated with every sensor node, and then runs our
proposed node categorization algorithm to identify nodes that
are droppers/modifiers for sure or are suspicious droppers/modifiers.
As the tree structure dynamically changes
every time interval, behaviors of sensor nodes can be
observed in a large variety of scenarios. As the information
of node behaviors has been accumulated, the sink periodically
runs our proposed heuristic ranking algorithms to
identify most likely bad nodes from suspiciously bad
nodes. This way, most of the bad nodes can be gradually
identified with small false positive.
Our proposed scheme has the following features: 1) being
effective in identifying both packet droppers and modifiers,
2) low communication and energy overheads, and 3) being
compatible with existing false packet filtering schemes; that
is, it can be deployed together with the false packet filtering schemes, and therefore it cannot only identify intruders but
also filter modified packets immediately after the modification
is detected. Extensive simulation on ns-2 simulator has
been conducted to verify the effectiveness and efficiency of
the proposed scheme in various scenarios.
In the rest of the paper, Section 2 defines the system model.
Section 3 describes the proposed scheme and Section 4
reports the evaluation results. Section 5 discusses the related
work, and Section 6 concludes the paper.
2 SYSTEM MODEL
2.1 Network Assumptions
We consider a typical deployment of sensor networks,
where a large number of sensor nodes are randomly
deployed in a two dimensional area. Each sensor node
generates sensory data periodically and all these nodes
collaborate to forward packets containing the data toward a
sink. The sink is located within the network. We assume all
sensor nodes and the sink are loosely time synchronized
[21], which is required by many applications. Attackresilient
time synchronization schemes, which have been
widely investigated in wireless sensor networks [22], [23],
can be employed. The sink is aware of the network
topology, which can be achieved by requiring nodes to
report their neighboring nodes right after deployment.
2.2 Security Assumptions and Attack Model
We assume the network sink is trustworthy and free of
compromise, and the adversary cannot successfully compromise
regular sensor nodes during the short topology
establishment phase after the network is deployed. This
assumption has been widely made in existing work [8], [24].
After then, the regular sensor nodes can be compromised.
Compromised nodesmay or may not collude with each other.
A compromised node can launch the following two attacks:
. Packet dropping. A compromised node drops all or
some of the packets that is supposed to forward. It
may also drop the data generated by itself for some
malicious purpose such as framing innocent nodes.
. Packet modification. A compromised node modifies
all or some of the packets that is supposed to forward.
It may also modify the data it generates to protect
itself from being identified or to accuse other nodes.
3 THE PROPOSED SCHEME
Our proposed scheme consists of a system initialization
phase and several equal-duration rounds of intruder
identification phases.
. In the initialization phase, sensor nodes form a
topology which is a directed acyclic graph (DAG). A
routing tree is extracted from the DAG. Data reports
follow the routing tree structure.
. In each round, data are transferred through the
routing tree to the sink. Each packet sender/
forwarder adds a small number of extra bits to
the packet and also encrypts the packet. When one
round finishes, based on the extra bits carried in the
received packets, the sink runs a node categorization
algorithm to identify nodes that must be bad (i.e., packet droppers or modifiers) and nodes that
are suspiciously bad (i.e., suspected to be packet
droppers and modifiers).
. The routing tree is reshaped every round. As a
certain number of rounds have passed, the sink will
have collected information about node behaviors in
different routing topologies. The information includes
which nodes are bad for sure, which nodes
are suspiciously bad, and the nodes’ topological
relationship. To further identify bad nodes from the
potentially large number of suspiciously bad nodes,
the sink runs heuristic ranking algorithms.
In the following sections, we first present the algorithm
for DAG establishment and packet transmission, which is
followed by our proposed categorization algorithm, tree
structure reshaping algorithm, and heuristic ranking algorithms.
To ease the presentation, we first concentrate on
packet droppers and assume no node collusion. After that,
we present how to extend the presented scheme to handle
node collusion and detect packet modifiers, respectively.
3.1 DAG Establishment and Packet Transmission
All sensor nodes form a DAG and extract a routing tree
from the DAG. The sink knows the DAG and the routing
tree, and shares a unique key with each node. When a node
wants to send out a packet, it attaches to the packet a
sequence number, encrypts the packet only with the key
shared with the sink, and then forwards the packet to its
parent on the routing tree. When an innocent intermediate
node receives a packet, it attaches a few bits to the packet to
mark the forwarding path of the packet, encrypts the
packet, and then forwards the packet to its parent. On the
contrary, a misbehaving intermediate node may drop a
packet it receives. On receiving a packet, the sink decrypts
it, and thus finds out the original sender and the packet
sequence number. The sink tracks the sequence numbers of
received packets for every node, and for every certain time
interval, which we call a round, it calculates the packet
dropping ratio for every node. Based on the dropping ratio
and the knowledge of the topology, the sink identifies
packet droppers based on rules we derive. In detail, the
scheme includes the following components, which are
elaborated in the following.
3.1.1 System Initialization
The purpose of system initialization is to set up secret
pairwise keys between the sink and every regular sensor
node, and to establish the DAG and the routing tree to
facilitate packet forwarding from every sensor node to the
sink.
Preloading keys and other system parameters. Each
sensor node u is preloaded the following information:
. Ku: a secret key exclusively shared between the node
and the sink.
. Lr: the duration of a round.
. Np: the maximum number of parent nodes that
each node records during the DAG establishment
procedure.
. Ns: the maximum packet sequence number. For each
sensor node, its first packet has sequence number 0,
the Nsth packet is numbered Ns 1, the ðNs þ 1Þth
packet is numbered 0, and so on and so forth.
Topology establishment. After deployment, the sink
broadcasts to its one-hop neighbors a 2-tuple h0; 0i. In the 2-
tuple, the first field is the ID of the sender (we assume the
ID of sink is 0) and the second field is its distance in hop
from the sender to the sink. Each of the remaining nodes,
assuming its ID is u, acts as follows:
1. On receiving the first 2-tuple hv; dvi, node u sets its
own distance to the sink as du ¼ dv þ 1.
2. Node u records each node w (including node v) as its
parent on the DAG if it has received hw; dwi where
dw ¼ dv. That is, node u records as its parents on the
DAG the nodes whose distance (in hops) to the sink
is the same and the distance is one hop shorter than
its own. If the number of such parents is greater than
Np, only Np parents are recorded while others are
discarded. The actual number of parents it has
recorded is denoted by np;u.
3. After a certain time interval,1 node u broadcasts 2-
tuple hu; dui to let its downstream one-hop neighbors
to continue the process of DAG establishment.
Then, among the recorded parents on the DAG,
node u randomly picks one (whose ID is denoted as
Pu) as its parent on the routing tree. Node u also
picks a random number (which is denoted as Ru)
between 0 and Np 1. As to be elaborated later,
random number Ru is used as a short ID of node u to
be attached to each packet node u forwards, so that
the sink can trace out the forwarding path. Finally,
node u sends Pu, Ru and all recorded parents on the
DAG to the sink.
After the above procedure completes, a DAG and a
routing tree rooted at the sink is established. The routing
tree is used by the nodes to forward sensory data until the
tree changes later; when the tree needs to be changed, the
new structure is still extracted from the DAG.
The lifetime of the network is divided into rounds, and
each round has a time length of Lr. After the sink has
received the parent lists from all sensor nodes, it sends out a
message to announce the start of the first round, and the
message is forwarded hop by hop to all nodes in the network.
Note that, each sensor node sends and forwards data via a
routing tree which is implicitly agreed with the sink in each
round, and the routing tree changes in each round via our
tree reshaping algorithm presented in Section 3.3.
3.1.2 Packet Sending and Forwarding
Each node maintains a counter Cp which keeps track of the
number of packets that it has sent so far. When a sensor
node u has a data item D to report, it composes and sends
the following packet to its parent node Pu:
hPu; fRu; u; Cp MOD Ns; D; padu;0gKu
; padu;1i;
where Cp MOD Ns is the sequence number of the packet. Ru
(0 Ru Np 1) is a random number picked by node u
during the system initialization phase, and Ru is attached to
the packet to enable the sink to find out the path along
which the packet is forwarded. fXgY represents the result
of encrypting X using key Y .
Paddings padu;0 and padu;1 are added to make all packets
equal in length, such that forwarding nodes cannot tell
packet sources based on packet length. Meanwhile, the sink
can still decrypt the packet to find out the actual content. To
satisfy these two objectives simultaneously, the paddings
are constructed as follows:
. For a packet sent by a node which is h hops away
from the sink, the length of padu;1 is logðNpÞðh 1Þ
bits. As to be described later, when a packet is
forwarded for one hop, logðNpÞ bits information will
be added and meanwhile, logðNpÞ bits will be
chopped off.
. Let the maximum size of a packet be Lp bits, a node
ID be Lid bits and data D be LD bits. padu;0 should
b e Lp Lid 2 logðNpÞ h logðNsÞ LD bits,
where Lid 2 bits are for Pu and u fields in the
packet, field Ru is logðNpÞ bits long, field padu;1 is
logðNpÞðh 1Þ bits long, and Cp MOD Ns is logðNsÞ
bits long. Setting padu;0 to this value ensures that all
packets in the network have the same length Lp.
When a sensor node v receives packet hv; mi, it composes
and forwards the following packet to its parent node Pv:
hPv; fRv; m0
gKv
i;
where m0 is obtained by trimming the rightmost logðNpÞ bits
off m. Meanwhile, Rv, which has log Np bits, is added to the
front of m0
. Hence, the size of the packet remains unchanged.
Suppose on a routing tree, node u is the parent of node v and
v is a parent of node w. When u receives a packet from v, it
cannot differentiate whether the packet is originally sent by v
or w unless nodes u and v collude. Hence, the above packet
sending and forwarding scheme results in the difficulty to
launch selective dropping, which is leveraged in locating
packet droppers. We take special consideration for the
collusion scenarios, which are to be elaborated later.
3.1.3 Packet Receiving at the Sink
We use node 0 to denote the sink. When the sink receives a
packet h0; m0
i, it conducts the following steps:
1. Initialization. Two temporary variables u and m are
introduced. Let u ¼ 0 and m ¼ m0 initially.
2. The sink attempts to find out a child of node u,
denoted as v, such that decðKv; mÞ results in a string
starting with Rv, where decðKv; mÞ means the result
of decrypting m with key Kv.
3. If the attempt fails for all children nodes of node u,
the packet is identified as have been modified and
thus should be dropped.
4. If the attempt succeeds, it indicates that the packet
was forwarded from node v to node u. Now, there
are two cases:
a. If decðKv; mÞ starts with hRv; vi, it indicates that
node v is the original sender of the packet. The
sequence number of the packet is recorded for
further calculation and the receipt procedure
completes.