In case it isn't clear, I don't think such drastic changes could ever hope to be done in a reasonable time frame for Clojure 1.6.0. Probably better to have a different thread for this if there is interest in discussing it.
Andy On Thu, Mar 20, 2014 at 10:03 AM, Andy Fingerhut <andy.finger...@gmail.com>wrote: > Regarding Michal's comment of using BST (binary search tree)-based > dictionaries, Clojure does already have sorted-maps and sorted-sets that do > this, for comparable keys/elements. > > A nice hybrid of the nearly-O(1) typical case of hash maps/sets, and > simultaneously protecting against the cases where there are many hash > collisions, is to have the 'leaves' of the current hash maps/sets be binary > search trees, rather than linked lists. > > That requires the keys/element to be comparable, but today's > clojure.core/compare cannot compare all pairs of things, and perhaps there > is no practical way to try to include "everything" in a more general > compare function so that everything hashable (i.e. every Java object) is > also comparable. Would it be easier to create a 'universal compare' > function for all Clojure values, assuming they only contained Clojure > values inside of them? > > Andy > > > On Thu, Mar 20, 2014 at 9:56 AM, Michał Marczyk > <michal.marc...@gmail.com>wrote: > >> We're vulnerable to this problem anyway as long as hashing is >> deterministic, which is why I think it would be cool to use some >> universal-hashing-like scheme... >> >> I think Murmur3 actually uses a seed that could be randomized? Not >> really "safe" in the cryptographic sense of the word, but would make >> this sort of attack more challenging. >> >> The way to avoid the problem completely is to use BST-based >> dictionaries -- slower, but free from pathological edge cases. >> >> Murmuring a short initial fragment could still be cool, just because >> we'd probably get a better hash. >> >> Cheers, >> Michał >> >> >> On 20 March 2014 17:40, Tim McCormack <group-cloj...@brainonfire.net> >> wrote: >> > On Wednesday, March 19, 2014 4:14:38 PM UTC-4, Alex Miller wrote: >> >> Rich just pushed a change to the String hashing to address this. We're >> >> going to grab the string hashcode (which is cached after first call) >> and >> >> murmur the result of that. This gives us constant time hashcode after >> first >> >> call with better distribution for combinations in nested collections. >> Will >> >> be in presumed RC2. >> > >> > (Discussion continued from IRC and Github.) >> > >> > This does make PHM vulnerable to "hashDoS" attacks again -- ["AaAa" >> "BBBB" >> > "AaBB" "BBAa"] will all hash to the same value, so an attacker can pass >> a >> > ton of these colliding strings to a webapp as a querystring or POST >> body and >> > really bog down the machine. Best article I could find on this attack: >> > >> http://cryptanalysis.eu/blog/2011/12/28/effective-dos-attacks-against-web-application-plattforms-hashdos/ >> > >> > Is there some compromise we can make between caching and good hashing? >> > >> > My naïve thought would be to combine the native String hashCode with a >> > Murmur hash of a fixed chunk of the string, then possibly run that >> > combination through Murmur. This avoids hashing unbounded data more than >> > once, and would be effective against basic hashDoS. (Intelligently >> picking >> > the fixed chunk of the string would be essential for protecting against >> an >> > adaptive hashDoS attack.) >> > >> > - Tim McCormack >> > >> > -- >> > You received this message because you are subscribed to the Google >> > Groups "Clojure" group. >> > To post to this group, send email to clojure@googlegroups.com >> > Note that posts from new members are moderated - please be patient with >> your >> > first post. >> > To unsubscribe from this group, send email to >> > clojure+unsubscr...@googlegroups.com >> > For more options, visit this group at >> > http://groups.google.com/group/clojure?hl=en >> > --- >> > You received this message because you are subscribed to the Google >> Groups >> > "Clojure" group. >> > To unsubscribe from this group and stop receiving emails from it, send >> an >> > email to clojure+unsubscr...@googlegroups.com. >> > For more options, visit https://groups.google.com/d/optout. >> >> -- >> You received this message because you are subscribed to the Google >> Groups "Clojure" group. >> To post to this group, send email to clojure@googlegroups.com >> Note that posts from new members are moderated - please be patient with >> your first post. >> To unsubscribe from this group, send email to >> clojure+unsubscr...@googlegroups.com >> For more options, visit this group at >> http://groups.google.com/group/clojure?hl=en >> --- >> You received this message because you are subscribed to the Google Groups >> "Clojure" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to clojure+unsubscr...@googlegroups.com. >> For more options, visit https://groups.google.com/d/optout. >> > > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
