Marc-Andre Lemburg <m...@egenix.com> added the comment: Jim Jewett wrote: > > Jim Jewett <jimjjew...@gmail.com> added the comment: > > On Mon, Feb 6, 2012 at 8:12 AM, Marc-Andre Lemburg > <rep...@bugs.python.org> wrote: >> >> Marc-Andre Lemburg <m...@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. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue13703> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
