On Sat, Sep 25, 1999 at 11:17:14PM +0400, A.N.Kuznetsov wrote:
> + * Such an implementation has been chosen not just for fun. It's a way to
> + * prevent easy and efficient DoS attacks by creating hash collisions. A huge
> + * amount of long living nodes in a single hash slot would significantly delay
> + * lookups performed with disabled BHs.
>
> Though you managed to prove me that all this issue is not paranoia.
>
> This bullet is yet. The easiest and the most efficient attack
> is to congest your peer cache and to kill all the IP then.
> As I see AVL just increases size of entry twice, so that you made
> it twice worse rather than better.
There are several attack directions:
- force system into out-of-memory condition and kill the system completely;
the protection - upper limit for the number of entries;
- force lookups to take too much time; plain hash table allows attacker to
place all nodes in a single list; walking through the list of about 65000
elements from BH kills the whole system;
- use upper limit for number of entries (implemented to solve #1) to block
creation of new nodes; it doesn't kill the system, it doesn't kill IP -
only new peers will be denied to communicate.
AVL tree helps attackers to implement #3 a bit faster. But it saves the
whole system. I definitely don't want anyone to crash my system.
And your word "twice" is a overestimation :-)
For AVL needs I keep 2 pointers instead of 1 - it increases the structure
size by 14 percents.
>
> Please, think about removing it. 8)8)
The thing which may be removed without big troubles is a list of unused
entries introduced to make entry expiration more cheap.
But it requires some new ideas how to do cleanup() efficiently.
May be random walk over the tree and removing the too old nodes?
Best wishes
Andrey
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/