Transcript foils by Hagai

Path identification
by hagay avraham the
third
Composers :
Abraham
Yaar,Adrian Perrig
and Dawn Song
problem :

Distributed Denial of Service
(DDoS) attacks continue to
plague the Internet. Defense
against these attacks is
complicated
by spoofed source IP addresses,
which make it difficult to
determine a packet’s true origin.
soloution
We propose Pi:
 (short for Path Identifier), a new
packet marking approach in which a
path fingerprint is embedded in
each packet, enabling
a victim to identify packets
traversing the same paths
through the Internet on a per packet
basis, regardless of
source IP address spoofing.
Example
on October 21, 2002, an attacker
flooded the root DNS servers with
traffic in an effort to deprive
the Internet of the DNS name lookup
service (which would have paralyzed
the majority of Internet
applications).
Only five out of thirteen root
servers were able to withstand
the attack.
The traceback mechanism
The routers mark information on 
packets.
The path information is used to 
install filters.
The assumption here is that we 
need to reconstract the exact path
to the attacker.
Hence the shortcomings are :
The victim must receive large 
numbers of packets before it is able
to reconstract the path that they are
taking
Routers and/or victims need to 
perform non trivial operations in
marking packets or in reconstructing
paths.
Network filtering is done on a per- 
flow or per network basis using
coarse identification criteria rather
on a per- packet basis.
The victim has to rely on upstream 
routers to perform packet
filtering,even once the attack
paths have been identified
A new approach for defending
against Ddos attacks
Reconstructing the exact path is not 
necessary – a particular path is
enough.
The victim classify a single packet as 
malicious in order to filter out all
subsequent packets with the same
marking.
The main difference between
the methods :
Our packet marking is deterministic. 
all the other marking methods are 
probabilistic in nature – the victim
needs to collect a large number of
packets to reconstruct the path.
The advantages are :
The scheme is light-weight,for the 
routers for marking .
for the victims for decoding and 
filtering.
Differend Ddos attacks :
Network resourse attack. 
Server resourse attack. 
Server memory attack. 
The new approach is based on the 
idea that the packets arriving at the
victim have some distinctive
marking.
The victim can overcome the attack 
easily.
Distinctive marking
We take the Internet as a complete 
binary tree.
The root is the server,the nodes are 
the leaves.
Therefore we have a lot of paths 
between the victim and the attacker.
We propose the path identifier to 
be embedded by routers in the IP
identification field of every packet
they forward.
The path identifier will act as the 
distinctive marking which the victim
can use to filter incoming packets.
Because every router has only local 
knowledge (last and next hop) of a
particular path,the marking for an
entire path in the PI is not
guaranteed to be globally uniqe.
However the benefits of the single 
packet deterministic marking allows
the victim to develop a packet filter
to protect itself during such attack.
The basic PI marking
scheme
In its simplest form,we propose an 
n-bit scheme where a router marks
the last n bits of its IP address in the
IP identification field of the packets
it forwards.
To determine the location within the 
field to mark the bits,we break the
field into [16/n] different marking
sections,and use the value of the
packet’s TTL,modulo [16/n] as an
index into the section of the field
mark.
Ip address hashing
We find that the distribution of the 
last bits of the IP addresses of the
routers from our sample internet
data is highly skewed.
This is problematic because if,for 
example,ISPs tended to designate
router IP addresses with the last
byte as 0.
Then many of our packet markings 
would be zero,which would make the
PI markings for different paths less
likely to be distinguishable from
each other.
Idealy,we would like to maximize 
the entropy of the bits that we mark
with,to reduce the likelihood of
marking,collisions
(where two different paths have the 
same PI marking).
To solve this problem,we have 
routers mark packets using the last
n bits from the hash of their ip
addresses,
Rather than from their ip addresses 
alone.
Edge marking in PI
We now describe a mechanism to 
increase the entropy in an individual
router’s marking.Consider the fan-in
topology shown in figure 4 :
We compute the probability that the 
victim cannot distinguish the
markings of a packet that traverses
routers R1 and R3 from the
markings of a packet that traverses
rrouters R2 and R3.
P[M(R1) = M(R2)] = 1/2^n 
The probability that the two paths 
have the same marking now
becomes :
P[(M(Ri -> R1) = M(Rj ->R2))&& 
(M(R1-> R3)= M(R2->R3))] = 
1/2^n*1/2^n = 1/2^2n
Edge marking decreases the 
probability that the two paths have
the same marking by a factor of
2^n.
Suppressing nearby router
markings
The limited space in the ip identification
field causes routers close to the victim to
overwrite the markings of routers farther
away.
A simple mechanism to achieve this
would be to have a router not mark a
packet if the destination ip addresses of
that packet matches a route obtained
through an interior Gateway
protocol(IGP).


The use of BGP has the effect of 
keeping routing tables small at lower
tier ISP networks,which only need to
know internal routes and a single
route to all external addresses.
The basic filter scheme
The victim can record the marking of 
identified attack packets and drop
subsequent incoming packets
matching any of those markings.
Advantages
The reaction time is fast 
A little memory resourses 
But it limits the victims flexibility. 
TTL unwrapping
In order to make the attack more 
effective the attacker can modify its
TTL of its packets in order to have
the first hop router start marking in
anyone of the sections of the ip
identification field.
Threshold filtering
There is another attack on our filtering
strategy,which we call a marking
saturation attack.
In this attack,a large number of attackers
spread throughout the internet all send
packets to a single victim in the hope of
having the victim classify every marking
as an attacker marking,and thus drop all
incoming packets.


This attack requires an attacker of 
immense means,since it requires at
least 2^16 zombie nodes,distributed
in such a way that each attacker has
a differing PI marking.
Advanced filters
The PI mechanism can also be used 
to detect spoofed ip addresses,with
an appropriate filter.
The victim need only build a table 
correlating the PI mark of a packet
to its source ip addresses,during
non-attack time.
When under attack,the victim can 
check to see if the source ip
addresses of incoming packets
match against the ip addresses of
their PI marks from the table.
Reflector attack
There are many potential uses for a 
PI filter that detects spoofed ip
addresses.
In a particular type of DDOS 
attack,known as a reflector
attack,attackers send request
packets to various services whose
responses are of far larger size than
the requests themselves. (e.g DNS).
Reflector
A PI filter capable of detecting 
spoofed ip addresses running on on
the reflectr’s server would
immediately detect the spoofed
source ip addresses of the requests
and refrain from sending a
response,thus halting the attack.
Traceroutes
The ip spoofed detection filter can 
also be used for a limited form of
traditional ip traceback – given a PI
mark,the victim can check the list of
ip addresses from the table that
match the mark and simply perform
traceroutes to those ip addresses.
Filtering in the network
The PI marking scheme can also support
other antiDDOS systems.
For example,the Pushback system uses
downstream routers that identify
aggregates(packets from one or more
flows hat have certain characteristic,such
source or destination addresses) And
send rate-limit requests to upstream
routers,along with an aggregate identifier.


Pushback
The PI marking can also be used to move
Pushback filters closer to the attacker,as
the marking is an identifier of the path
towards the attacker.
However,the pushback router needs to
consider that the PI markings are not
unique,as multiple paths may exhibit the
same marking.


Thank you very much
Do not forget to tip 
Hagay avraham the 3rd. 