Transcript 4%20-%20Roosta

The Inherent Security of Routing Protocols
in Ad Hoc and Sensor Networks
Tanya Roosta (EECS, Berkeley)
In Collaboration With:
Sameer Pai (ECE, Cornell)
Phoebus Chen (EECS, Berkeley)
Prof. Shankar Sastry (EECS, Berkeley)
Prof. Stephen Wicker (ECE, Cornell)
April 2, 2008
Outline






Introduction
Problem Setup
Attack Scenarios
Simulation Setup and Parameters
Results
Current/Future Work
2
Introduction

Generally the focus of routing protocols for sensor
networks:
–
–
–

Sensor networks are deployed and left unattended
–
–

Energy-efficiency
Guaranteed throughput
Usually involves a non-adversarial setting
Susceptible to attacks
Must design networks with security in mind
Our work
–
–
Determine the statistical impact of different attacks on sensor
network routing
Determine performance of different families of routing protocols
under particular attack scenarios
3
Problem Setup



We abstract away the details of specific attacks and
specific routing protocols
Instead we focus on characterizing the statistics of
attacks on different classes of routing algorithms
Routing Protocols:
–
–

Single-path & Multi-path routing protocols
Deterministic and Probabilistic routing protocols
Attack Scenarios
–
–
–
Adversary has compromised some number of nodes within the
sensor network and has subverted their normal operations
Mote-class, insider attackers alter the data and forward it as
normal
Attacks differ by the locations of the attackers within the
network topology
4
Single-Path Routing

Deterministic Single-path Routing
–
–
–

Minimum-weight path routing
Edges are assigned weights
Packets sent on path minimizing sum of weights on edges
contained in the path
Probabilistic Single-path Routing
–
–
–
–
Like a directed random walk on a graph
Each node assigns a probability to each neighbor node (e.g.
uniform assignment)
Packet sent to next-hop neighbor chosen based on the
assigned probability
Achieves load-balancing in a statistical sense
5
Multi-path Routing Protocols

Deterministic Multi-path Routing
–
–

k-shortest node-disjoint paths
k-shortest edge-disjoint paths
Probabilistic Multi-path Routing
–
–
Each node in the network broadcasts packets to all
neighbors with some probability
Extreme case is probabilistic flooding
6
Attack Scenarios

Uniformly distributed attack:
–
The attacker compromises a number of k nodes
uniformly at random.
7
Attack Scenarios

Random walk attack:
–
The attacker chooses a node to compromise
uniformly at random and then performs a directed
random walk towards the periphery of the network.
8
Attack Scenarios

Spatial attack:
–
The attacker chooses a node to compromise
uniformly at random and also compromises all
nodes within a set preset radius.
9
Simulator
Secure Sensor Network Routing Simulator
SSNRS
–
–
–
Built in MATLAB to evaluate routing protocols in
the attack scenarios
Discrete packet-time marching simulator
Allows for use of:




Different channel models
Routing topologies
Routing protocols
Attack scenarios
10
Parameters Used in Simulations
11
Baseline Average Energy Expenditure
12
Results: Uniform Attack
13
Results: Directed Random Walk
14
Results: Spatial Attack
15
Results




Routing performance falls sharply with
increasing number of uncooperative nodes
(insider attackers)
The performance degrades for most families
of routing protocols
Single-path routing performs worst with
increasing number of uncooperative nodes
Multi-path routing performs best, but comes
at an increased energy cost
16
Results (cont.)




The uniformly distributed attackers scenario is
most detrimental to successful end-to-end
packet delivery
Spatial attacks are highly clustered, attacking
nodes have a lower probability of being on a
path from the source to the destination
Random walk attacks have performance
degradation results between the other two
attack scenarios
Probabilistic routing protocols are best to
preserve confidentiality.
17
Current and Future Work

Problem: We need a way to mitigate misbehavior in ad
hoc and sensor networks
–
–

Nodes not forwarding data correctly (uncooperative nodes)
during routing can cause major problems
Only those nodes that are behaving correctly (cooperating)
should be authorized to have access to the data
Solution: A trust system for wireless ad hoc and sensor
networks
–
A trust value is a networked node’s belief (probability) in the
ability of other nodes in the network to pass necessary data from
this node while preserving data integrity and confidentiality



A local metric for predicting the future behavior of other networked
nodes
Assists any node in distinguishing reliable forwarding nodes
(cooperative nodes) from unreliable forwarding ones
(uncooperative nodes)
Goal: To develop robust trust systems for wireless ad
hoc and sensor networks
18
References
1.
“The Inherent Security of Routing
Schemes in Ad Hoc and Sensor
Networks”. Tanya Roosta, Sameer Pai,
Phoebus Chen, Shankar Sastry, Stephen
Wicker. In proceedings of the IEEE
Globecom 2007, Washington D.C USA.
19