Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic

Re: Re: Re: hash collision DOS

by tilly (Archbishop)
on Jun 03, 2003 at 04:37 UTC ( #262565=note: print w/replies, xml ) Need Help??

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

I would have to examine the hash function in some detail to tell whether or not that would work as a fix (at a minimal performance loss and the space overhead of having to store the initial value for each hashing function in the hash).

Deep recursion checks in the list traversal logic is exactly the solution that I thought was likely to slow things down. Perl spends a lot of its time doing hash lookups, and any overhead (eg having to use up an extra register to track how deep the list went) is likely to show performance problems.

But thinking about the issue, I am not sure that a clever person couldn't manage to add such a check in some way that didn't cause significant performance problems. I simply have not worked close enough to the metal enough to have a sense of that. If you could add the performance check, though, there is no reason that you couldn't just fall back into a more complex and robust data structure instead of a linked list. The immediate algorithmic overhead is paid for by the fact that you only use it when you really need it.

Replies are listed 'Best First'.
Re: Re: Re: Re: hash collision DOS
by BrowserUk (Pope) on Jun 03, 2003 at 06:05 UTC

    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

      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?

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://262565]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (6)
As of 2018-01-16 10:40 GMT
Find Nodes?
    Voting Booth?
    How did you see in the new year?

    Results (177 votes). Check out past polls.