Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: Re: Re: Re: hash collision DOS

by BrowserUk (Pope)
on Jun 03, 2003 at 06:05 UTC ( #262576=note: print w/ replies, xml ) Need Help??


in reply to Re: Re: Re: hash collision DOS
in thread hash collision DOS

perl spends a lot of its time doing hash lookups

True, but my (unstated) thought was that such 'hash quality' check would only need to be done at STORE time, not FETCH time. As such, the costs would be a significantly smaller proportion of the overall operation than with the FETCH, as it would be along side the memory allocation, bucket shuffling etc.?


Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller



Comment on Re: Re: Re: Re: hash collision DOS
Re: Re: Re: Re: Re: hash collision DOS
by tilly (Archbishop) on Jun 03, 2003 at 06:20 UTC
    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...

      What about a hybrid solution, like a hash whose lists (or some lists) are B-Trees?
        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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://262576]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (3)
As of 2014-07-24 02:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (156 votes), past polls