Re: Re: Re: Re: Re: hash collision DOS

[tilly]

That is a good point which I wasn't thinking about. A warning does only have to slow down the stores.

A switch to a smarter data structure has to slow down both reads and stores.

Still I, as an application programmer, wouldn't care for a warning. It wouldn't, after all, help me any when I am writing my vulnerable application. And while my server is being beaten down, knowing how I am being DOSed isn't going to help me fix it unless I do more work than I am willing to do...

[ikegami]

What about a hybrid solution, like a hash whose lists (or some lists) are B-Trees?

[tilly]

I thought about suggesting that.

The problem is that you get guaranteed worst-case behaviour at the cost of extra code along what should be a fast path, and this is going constantly be executed. I suspect that you'd find a measureable slowdown in perl. Which is why I personally prefer the solution that was chosen, which is to vary the hashing function so that its performance characteristics are unaltered but there is no predictable DOS target to go against.

However don't let my back-of-the-envelope guess deter you from trying to implement that solution. It may be that there is no significant performance penalty, in which case the improved worst-case performance would be very worthwhile.

[demerphq]

Its interesting that this thread resurfaced now, as just yesterday I posted a patch to p5p to change the hash function that we use from the "OneAtATime" function to the "SuperFastHash" by Paul Hsieh. Details of both can be found in an updated version of Bob Jenkins hash article from DrDobs. The SFH is signifigantly faster than OneAtATime on modern machines, with SFH running about 3 times as fast as OneAtATime.

Anyway, id be curious if you have any tools or scripts that can be used to do some analysis on how the two functions perform. I plan to instrument a version of perl so I can do chain length histograms and things like that, but anything you might think of would be appreciated.