Jim Jewett wrote:
> 
> Jim Jewett <jimjjewett@gmail.com> added the comment:
> 
> On Mon, Feb 6, 2012 at 8:12 AM, Marc-Andre Lemburg
> <report@bugs.python.org> wrote:
>>
>> Marc-Andre Lemburg <mal@egenix.com> added the comment:
>>
>> Antoine Pitrou wrote:
>>>
>>> The simple collision counting approach leaves a gaping hole open, as
>>> demonstrated by Frank.
> 
>> Could you elaborate on this ?
> 
>> Note that I've updated the collision counting patch to cover both
>> possible attack cases I mentioned in http://bugs.python.org/issue13703#msg150724.
>> If there's another case I'm unaware of, please let me know.
> 
> The problematic case is, roughly,
> 
> (1)  Find out what N will trigger collision-counting countermeasures.
> (2)  Insert N-1 colliding entries, to make it as slow as possible.
> (3)  Keep looking up (or updating) the N-1th entry, so that the
> slow-as-possible-without-countermeasures path keeps getting rerun.

Since N is constant, I don't see how such an "attack" could be used
to trigger the O(n^2) worst-case behavior. Even if you can create n sets
of entries that each fill up N-1 positions, the overall performance
will still be O(n*N*(N-1)/2) = O(n).

So in the end, we're talking about a regular brute force DoS attack,
which requires different measures than dictionary implementation
tricks :-)

BTW: If you set the limit N to e.g. 100 (which is reasonable given
Victor's and my tests), the time it takes to process one of those
sets only takes 0.3 ms on my machine. That's hardly usable as basis
for an effective DoS attack.