Hi! >> Lets [try] to quantify the probability of reaching the collision limit C > with a hashtable of size N and assuming a random hash distribution. The > upper bound for this should be (N choose C) * (1/N)^(C-1), with (1/N)^(C-1) > being the probability that C elements hash to one value and (N over C) the > number of C element subsets of an N element set. For large N and N >> C we > approximate (N choose C) to (e*N/C)^C / sqrt(2pi*C). As such our upper > bound becomes N * (e/C)^C / sqrt(2pi*C). Choosing N = 2^31 (largest > possible hashtable) we get for C = 20 probability 8.9E-10 and for C = 100 > probability 2.3E-149. The patch uses C = 1000.
I assume you're talking here about per-hashtable limit? Here I notice two things: 1. Hash keys are not really random. Which can both improve and make it worse, but we have a lot of keys named "key" and not a lot of keys named "\x07\xF5\xDD". 2. This does not account for the fact that if we have two keys used by app colliding, we'll probably see this collision a lot. Of course, if we're counting per-hashtable, that would make is somewhat less, but still. To validate this theory, I applied the following patch: https://gist.github.com/smalyshev/2c3c085998ba81d6c163a27386aaacd8 And run composer update on one of my projects. I got these lines: Destroyed hash with coll = 48454 Destroyed hash with coll = 41871 Destroyed hash with coll = 41828 Destroyed hash with coll = 40535 Destroyed hash with coll = 32774 Destroyed hash with coll = 22782 Destroyed hash with coll = 21381 Destroyed hash with coll = 15232 Destroyed hash with coll = 14745 Destroyed hash with coll = 12216 Destroyed hash with coll = 11742 Destroyed hash with coll = 11625 Destroyed hash with coll = 8916 Destroyed hash with coll = 6820 Destroyed hash with coll = 5911 Destroyed hash with coll = 5429 Destroyed hash with coll = 3390 Destroyed hash with coll = 1188 I.e. there were 18 hashes with more than 1000 collisions on the course of the run. Is there something wrong with my count or am I counting wrong things (I didn't see the patch for limiting counts so maybe I'm still counting wrong things). > In other words, it is extremely unlikely that you hit the collision limit > by accident, with non-malicious data. So no, the user does not have to > discriminate normal from malicious causes. If the limit triggers, it's > malicious. I'm not so sure of this now - unless, again, I misunderstand what we're counting. -- Stas Malyshev smalys...@gmail.com -- PHP Internals - PHP Runtime Development Mailing List To unsubscribe, visit: http://www.php.net/unsub.php
