<br><br><div class="gmail_quote">On 17 January 2012 10:14, Tim Delaney <span dir="ltr"><<a href="mailto:timothy.c.delaney@gmail.com">timothy.c.delaney@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="gmail_quote"><div class="im">On 17 January 2012 09:23, Paul McMillan <span dir="ltr"><<a href="mailto:paul@mcmillan.ws" target="_blank">paul@mcmillan.ws</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>This is why the "simply throw an error" solution isn't a complete fix.</div>
Making portions of an interface unusable for regular users is clearly<br>
a bad thing, and is clearly applicable to other types of poisoned data<br>
as well. We need to detect collisions and work around them<br>
transparently.</blockquote><div><br></div></div><div>What if in a pathological collision (e.g. > 1000 collisions), we increased the size of a dict by a small but random amount? Should be transparent, have neglible speed penalty, maximal reuse of existing code, and should be very difficult to attack since the dictionary would change size in a (near) non-deterministic manner when being attacked (i.e. first attack causes non-deterministic remap, next attack should fail).</div>
<div><br></div><div>It should also have near-zero effect on existing tests and frameworks since we would only get the non-deterministic behaviour in pathological cases, which we would presumably need new tests for.</div>
<div>
<br></div><div>Thoughts?</div></div></blockquote><div><br></div><div>And one thought I had immediately after hitting send is that there could be an attack of the form "build a huge dict, then hit it with something that causes it to rehash due to >1000 collisions". But that's not really going to be any worse than just building a huge dict and hitting a resize anyway.</div>
<div><br></div><div>Tim Delaney </div></div>