netdev - Re: [PATCH] net: implement emergency route cache rebulds when gc

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20080930184249.GC6496@hmsreliant.think-freely.org>
Date:	Tue, 30 Sep 2008 14:42:49 -0400
From:	Neil Horman <nhorman@...driver.com>
To:	Eric Dumazet <dada1@...mosbay.com>
Cc:	David Miller <davem@...emloft.net>, netdev@...r.kernel.org,
	kuznet@....inr.ac.ru, pekkas@...core.fi, jmorris@...ei.org,
	yoshfuji@...ux-ipv6.org, kaber@...sh.net,
	Evgeniy Polyakov <johnpol@....mipt.ru>
Subject: Re: [PATCH] net: implement emergency route cache rebulds when
	gc_elasticity is exceeded

On Tue, Sep 30, 2008 at 07:16:50PM +0200, Eric Dumazet wrote:
> David Miller a écrit :
>> From: Eric Dumazet <dada1@...mosbay.com>
>> Date: Tue, 30 Sep 2008 08:02:44 +0200
>>
>>> When a machine is targeted by a DDOS attack, about all slots of the
>>> hash table are fully loaded (ie chain length >= elasticity). We dont
>>> need to invalidate the cache, but find an equilibrium, with small
>>> adjustements.
>>
>> Sure, but it is possible to determine that some hash chains
>> are unevenly growing out of control compared to others,
>> and that is the algorithm that Neil is trying to discover.
>>
>>
>
> No problem, but my suggestion to use a separate threshold than elasticity
> was apparently not taken into consideration.
>
> I ran an experiment on a big stable machine with 2^19 rtcache slots,
> scanning all chains and found *many* of them having length > elasticity,
> maximum being 13. I am sure its allowed by statistics laws.
>
> (average chain length : 3.55)
>
> In order to avoid unecessary cache invalidation, we need some  
> calculation from a statistics expert.
>
> Given rt_hash_size and elasticity (or rt_max_size), compute the "maximum 
> reasonable" chain length, ie some X number where probability(chain_length 
> < X) > 0.9999
>
I think what you're looking for here is a simple standard deviation, isn't it?
Compute the mean chain legnth, sum the squares of the deviations of each chain
and take the square root.  Any individual chain longer than the mean chain
length + 1 standard deviation can be considered an 'outlier' and therefore
trigger a rebuild of the table for that net namespace.

I full well realize that thats easier said than done, but does that seem about
right?  If so, I can start working on trying to build something to accomplish
that.

Regards
Neil


-- 
/****************************************************
 * Neil Horman <nhorman@...driver.com>
 * Software Engineer, Red Hat
 ****************************************************/
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html