3 ms·

One advantage to randomization, and why various languages did it in the first place, is that it prevents miscreants from DoSing your service if they know its im

One advantage to randomization, and why various languages did it in the first place, is that it prevents miscreants from DoSing your service if they know its implementation. Say you're operating a service and you share its source on GitHub such that anyone can see it. Your language doesn't randomize hash values. Hashes are O(1), right? Well, not if a clever attacker can send you a set of values where they know each one will hash into the same bucket. The you end up with like 9 empty buckets and 1 with 100,000 items in it. Oops! Old Python pre-randomization had a dict.items() method that would yield all the keys in order, conceptually kind of like: for bucket in self._buckets: for item in bucket: yield item The order of those buckets would be repeatable between runs, so bucket foo would always come first, then bucket bar. Then Python added hash randomization so that the resulting hash key was something like hash(salt+key) instead of just hash(key). Now there's no way to tell in advance which bucket an item would get filed into, and the buckets would end up more or less balanced in size. Newer Pythons (since 3.6? 3.7?) do something altogether different, and I can't explain exactly how their ordered dicts work, except to say I sat through a presentation on them and thought it was freaking genius even if I could re-implement it myself without sitting down with their docs.

quelltext 2y ago
> and I can't explain exactly how their ordered dicts work Traditionally you simply use a doubly linked list approach on the entries (each entry maintains two additional references to the previous and next entry) for that like LinkedHashMap: https://docs.oracle.com/javase//8/docs/api/java/util/LinkedHashMap.html https://docs.oracle.com/javase//8/docs/api/java/util/LinkedH... https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/LinkedHashMap.java#L318 https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/... Which is also what Python seems to be doing: https://stackoverflow.com/a/34496644 https://stackoverflow.com/a/34496644 It's fairly intuitive. Do their new default (now also ordered?) dics do this differently?
- kstrauser 2y ago
  Note that OrderedDict is an implementation in Python. CPython's dict has a different implementation. There's more about it at https://docs.python.org/3.6/whatsnew/3.6.html#new-dict-implementation https://docs.python.org/3.6/whatsnew/3.6.html#new-dict-imple... and https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... .
  - quelltext 2y ago
    This implementation was used from 3.6, right? It's interesting that the idea mail mentions that nothing changes about the implementation (including order) but the memory layout. Which would imply insertion order was already preserved in older versions (not the case IIRC) or the idea underwent a few more changes that did in fact impact order. EDIT: I couldn't quite find an answer but https://softwaremaniacs.org/blog/2020/02/05/dicts-ordered/ https://softwaremaniacs.org/blog/2020/02/05/dicts-ordered/ mentions the behavior happens since then because the implementation only tracks indices in the hash table itself and relies on maintaining entries separately in a second array that gets expanded in insertion order. This would also seem straightforward but it raises a few questions such as how deletion is implemented (efficiently). EDIT2: Okay, the talk (https://youtu.be/p33CVV29OG8 https://youtu.be/p33CVV29OG8) mentions they just leave holes until the next resize (at around 42:00). Raymond also mentions there that his original idea didn't preserve ordering but happened due to an additional compacting optimization? Should probably watch the whole thing some time to get the history. Sounds like a fun talk.
    - kstrauser 2y ago
      Oh! Yeah, that was the talk, but repeated at PyCon. It’s a very clever design that wasn’t at all obvious to me.
o11c 2y ago
Note that this relies on all the object classes having correct hash implementation (which is actually quite difficult); it's not really a property of the container. That said, the attack is almost always on builtin types, so ...

quelltext 2y ago

> and I can't explain exactly how their ordered dicts work Traditionally you simply use a doubly linked list approach on the entries (each entry maintains two additional references to the previous and next entry) for that like LinkedHashMap: https://docs.oracle.com/javase//8/docs/api/java/util/LinkedHashMap.html https://docs.oracle.com/javase//8/docs/api/java/util/LinkedH... https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/LinkedHashMap.java#L318 https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/... Which is also what Python seems to be doing: https://stackoverflow.com/a/34496644 https://stackoverflow.com/a/34496644 It's fairly intuitive. Do their new default (now also ordered?) dics do this differently?

kstrauser 2y ago
Note that OrderedDict is an implementation in Python. CPython's dict has a different implementation. There's more about it at https://docs.python.org/3.6/whatsnew/3.6.html#new-dict-implementation https://docs.python.org/3.6/whatsnew/3.6.html#new-dict-imple... and https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... .
- quelltext 2y ago
  This implementation was used from 3.6, right? It's interesting that the idea mail mentions that nothing changes about the implementation (including order) but the memory layout. Which would imply insertion order was already preserved in older versions (not the case IIRC) or the idea underwent a few more changes that did in fact impact order. EDIT: I couldn't quite find an answer but https://softwaremaniacs.org/blog/2020/02/05/dicts-ordered/ https://softwaremaniacs.org/blog/2020/02/05/dicts-ordered/ mentions the behavior happens since then because the implementation only tracks indices in the hash table itself and relies on maintaining entries separately in a second array that gets expanded in insertion order. This would also seem straightforward but it raises a few questions such as how deletion is implemented (efficiently). EDIT2: Okay, the talk (https://youtu.be/p33CVV29OG8 https://youtu.be/p33CVV29OG8) mentions they just leave holes until the next resize (at around 42:00). Raymond also mentions there that his original idea didn't preserve ordering but happened due to an additional compacting optimization? Should probably watch the whole thing some time to get the history. Sounds like a fun talk.
  - kstrauser 2y ago
    Oh! Yeah, that was the talk, but repeated at PyCon. It’s a very clever design that wasn’t at all obvious to me.

o11c 2y ago

Note that this relies on all the object classes having correct hash implementation (which is actually quite difficult); it's not really a property of the container. That said, the attack is almost always on builtin types, so ...