Transcript Powerpoint

Query-Flood DoS Attacks
in Gnutella
by Andreas Legrum
based upon a paper by
Neil Daswani and Hector Garcia-Molina
1
Overview
What does DoS mean?
How does Gnutella work? (simplified)
Policies to select queries
What is a good/malicious node?
How to measure the damage inflicted?
Examples for network topologies
Which policies/topologies work best?
Summary
Questions
2
What does DoS mean?
DoS: abbreviation for Denial of Service
Normally done by flooding a PC with
(useless) requests in order to cut CPU
time for the other running processes
including GUI. The PC seems to be
frozen although he’s only trying to cope
with the incoming data and so he’s no
longer offering any useful service.
3
How does Gnutella work? (simplified)
Network of supernodes
Clients send their queries
to the node they are
connected to
Nodes forward incoming
queries to their neighbors
and clients
Queries have a TTL
specifying
the
max.
number of nodes to travel
4
Policies to select queries
Reservation Ratio
Incoming Allocation Strategy (IAS)
Drop Strategy (DS)
Reservation Ratio
A fractal defining how many percent of a nodes
query processing capacity is reserved for local peers.
If there aren’t enough queries from local peers, left
over capacity is used for remote peer’s queries
(queries received from other supernodes).
5
Policies to select queries
Incoming Allocation Strategy (IAS)
Weighted IAS
Nodes sending more queries will be given more
processing capacity. So each connected node will
have approximately the same percentage of queries
served.
Fractional IAS
The available capacity is equally distributed among
among all connected nodes, no matter how many
queries they’ve sent.
Leftover capacity is distributed by reapplying the
strategy.
6
Policies to select queries
Drop Strategy (DS)
Queries are grouped by same source IP and TTL
Proportional
Each group has the same percentage of queries
served.
Equal
Each group has the same amount of queries served.
OrderByTTL (PreferHighTTL / PreferLowTTL)
Queries with high/low TTL are served first.
Again, leftover capacity is redistributed by reapplying.
7
What is a good/malicious node?
The model presented is simple enough to be modeled.
To do so, we have to specify two kinds of nodes.
Characteristics of a good node:
Most nodes in the network are good nodes
Trying to maximize the networks service by setting its
reservation ratio close to the optimal value
Modeled as a normal node; all good nodes are modeled having
the same processing capacity and using the best average
reservation ratio
Characteristics of a malicious node:
not serving / forwarding incoming queries -> structural damage
sending out lots of useless queries -> flooding damage
Best modeled by setting the reservation ratio to 1 and having
the node generate as much queries possible
8
How to measure the damage inflicted?
The damage of query-flood DoS attacks
is mainly a reduction of the amount of
remote service the network is offering.
To measure this damage, the service
capacity has to be calculated before and
after turning a good into a malicious
node.
9
Examples for network topologies
10
Which policies/topologies work best?
In order to test the effectiveness of the policies,
tests had been run on simulated networks of 1416 nodes at worst-case conditions.
This table shows the percentage loss in service
after a node was turned into a malicious one:
It’s easy to see that fractional/equal has the lowest11loss.
Which policies/topologies work best?
When
comparing
fractional/equal
with
weighted/proportional while the malicious node is
at the worst possible point in the network, you
see that the better policies might be up to 4.4
times better than worse ones.
12
Which policies/topologies work best?
It also can be seen that the complete (K) topology takes
the lowest damage when using the best policies.
Unfortunately it may not be practically used in networks
with thousands of clients.
Also, malicious nodes at center positions may inflict higher
damage then those at the borders of the network.
13
Summary
It’s impossible to save an open network
from malicious nodes, but by using
efficient query selection policies the
damage dealt may be reduced.
Also some of the damage might be
prevented by selecting an optimal topology
and not having these nodes easily take a
center position in the network.
14
Questions?
Are there any questions?
15