Transcript Security Issues in AntNet

Security Issues in Ant Routing
Weilin Zhong
Outline




Swarm Intelligence
AntNet Routing Algorithm
Security Issues in AntNet
Possible Solutions
Swarm Intelligence

Biology Swarms


Social Insect
Characteristics




Complex Group Behaviors
Simple Individual Behaviors
Local Communication and Interaction
No Leader or Coordinator
Swarm Intelligence

Complex Group Behaviors

Nest Building
Wasp Nets
Swarm Intelligence

Complex Group Behavior - Ant Forage Model
Swarm Intelligence

How can simple individuals achieve complex
group behaviors?
--The Intelligence of biological swarm lies on its
interaction network
Swarm Intelligence

Two Kinds of Interactions


Locally Direct Interaction
A member interacts with its neighbors
Indirection Interaction -- Stigmergy
 Interaction intermediate by the common environment
Swarm Computing Model

Computing Swarm



Computing Swarm is a collection of large number of small
computational members
Examples: Sensor Networks, Multi-agent System, Amorphous
Computer
System Characteristics





Myriad numbers of elements.
Decentralized control
Autonomous members
Sophisticated global behaviors
Adaptive and self-organized
AntNet Routing Algorithm

Swarm Intelligence In General Network
Routing Problems


Learn from the Ant Forage Model
AntNet Routing Algorithm



A Distributed Adaptive Routing Algorithm
Mobile Multi-agent Systems
Inspired by the stigmergy model in ant colonies
AntNet Routing - Agents

Two kinds of Agents(Ant Packets)


Forward Ant
 explores the network and collects information
 when reaches the destination, changes into backward ant
Backward Ant
 goes back in the same path as forward ant
 update routing tables for all the nodes in the path
AntNet Routing --- Agents

Agents behaviors
(N1,T1)
(N2,T2)
(N1,T1)
Forward Ant
1
Backward Ant
(N1, T1)
Forward Ant
2
Backward Ant
(N1,T1)
(N2,T2)
(N2,T2)
(N3,T3)
(N3,T3)
Forward Ant
(N4, T4)
Forward Ant
3
Backward Ant
4
Backward Ant
AntNet Routing- Router

Probabilistic Routing Table
Port/ N1
dest
1
P11

N2
…
Nn
P12
…
P1n
2
P21
P22
…
P2n
3
P31
P32
…
P3n
1
1
3
Local Statistics Model
N1
Stat1
N2
Stat2
…
…
2
Nn
Statn
AntNet Routing - Router

AntNet Router Structure
Forward_ANT
Data Packet
Lookup and
forwarding
P\N
1
2
…
3
Backward_ANT
N1
P11
P21
…
P31
N2
P12
P22
…
P32
…
…
…
…
…
Updating
N3
P13
P23
…
P33
Out[ ]
Buffer
Port1
FIFO1
Schedule
r
FIFO2
Port2
FIFO1
Schedule
r
FIFO2
Port N
FIFO1
FIFO2
Schedule
r
AntNet Routing

Measure Trip Time
(N2,T2)
(N1,T1)
Forward Ant
1
Backward Ant
(N1, T1)
Forward Ant
2
Backward Ant
(N1,T1)
(N1,T1)
(N2,T2)
(N2,T2)
(N3,T3)
(N3,T3)
Forward Ant
(N4, T4)
Forward Ant
3
Backward Ant
VT1 = VT2
VT2 = VT3
VT3 = VT4
+ Local_VT
+ Local_VT
+ Local_VT
4
Backward Ant
VT4 = 0
Local_VT = Channel_Tran_Prop_delay + Load_Dependent_Processing_Delay
AntNet Routing Algorithms

Updating Routing Table



Reinforcement Factor
r = C1 * ( Wbest/T) + C2 * Var
Increase the probability of the channel that backward ant
comes from
P’ = P + r * (1 - P)
Decrease the probability of the other channels
P’ = P * ( 1 - r)
AntNet Routing Algorithm

A Simple Network Example
1
0
1
3
2
0
0
0
4
1
1
0
1
1
2
3
2
2
0
Security Issues in AntNet

Threats



untrustworthy hosts
Malicious Agents
Attack Goals



increase the packet latency
--- mislead packets to a longer path
Break down a critical node
--- mislead packets to a certain node to overload it
Drop Data Packets
--- mislead packets to a malicious node
Security Issues

Untrustworthy Hosts
forward data packet to a wrong direction
 delay data packet
 generate a bursts of ant packets to reinforce
bad path
 generate false ant packets to make good path
bad
Malicious Agents
 carried false trip time information


Possible Solutions

Authentication Mechanism




problem: expensive
Time Stamp or Sequence Number on Agent
Better Adaptive Model for quick recovery
form the impact of malicious agent
Other solutions?...