Python3.6のdictキー順維持と、hash randomizeによるDoS回避の関係について¶
注釈
2017/3/20 修正: DDoS -> DoS
2018/7/1 追記: Python-3.7でdictキー順維持が言語仕様化
Python-3.3で導入された、Hash Randomizeについて間違って理解していたようなので、考えを整理してそれの理解が正しいかTeratailに質問をしたところ、的確な回答をもらえて解決できました。
Python - Python3.6でのdictのキー順維持と、hash randomizeによるDDoS回避の関係について(69286)｜teratail
（Teratailで質問したいと思えることが今までなくて、今回やっと質問できました。Q&Aサイトで質問すると流れずに残るのが良いですね）
Python3.6でのdictのキー順維持と、hash randomizeによるDDoS回避の関係について¶
注釈
質問サイトにDDoSって書いちゃったのでそのまま引用しますが、実際には DoS です
以下、質問を引用します。
前提
Pythonは以前からdictのキーの順番は不定、とされてきました。 しかし、見た目上は何らかの固定の順番でdictのキーを取り出せていました。（不定だけど一定） --(A)
Python3.3では、 hash randomizeが導入されました 。 導入された目的は、 object.__hash__のドキュメント に書いてあったので以下に引用します:
> この目的は、慎重に選ばれた入力で辞書挿入の最悪性能 O(n^2) 計算量を悪用することで引き起こされるサービス妨害 (denial-of-service, DoS) に対する保護です。 詳細は http://www.ocert.org/advisories/ocert-2011-003.html を参照してください。この導入によって、dictのキーの順番がインタプリタ起動毎に不定になりました。 --(B)
そしてPython3.6でdictの実装が変わり、dictが省メモリになり、キーの順番が維持されるようになりました。 ref: Python 3.6 の（個人的に）注目の変更点 - methaneのブログ --(C)
検証したこと
Python2.7.13 で文字列のhash値を取得((B) の確認):
$ python2.7 -c "print(hex(hash('abc')))" 0x142a6050a093d0a3 $ python2.7 -c "print(hex(hash('abc')))" 0x142a6050a093d0a3 $ python2.7 -c "print(hex(hash('abc')))" 0x142a6050a093d0a3Python3.5.2 で文字列のhash値を取得((B) の確認):
$ python3.5 -c "print(hex(hash('abc')))" 0x53a97f418e279642 $ python3.5 -c "print(hex(hash('abc')))" -0x745a06d34cd5d4ed $ python3.5 -c "print(hex(hash('abc')))" 0x29736bbb038652f5Python3.6.0 で文字列のhash値を取得((B) の確認):
$ python3.6 -c "print(hex(hash('abc')))" 0x11108253ed4a023b $ python3.6 -c "print(hex(hash('abc')))" -0x5dc778080cb917cd $ python3.6 -c "print(hex(hash('abc')))" -0x687164debf8ee240Python2.7.13 で辞書のキー順を取得((A) の確認):
$ python2.7 -c "print(list(dict.fromkeys(list('abcdefg'))))" ['a', 'c', 'b', 'e', 'd', 'g', 'f'] $ python2.7 -c "print(list(dict.fromkeys(list('abcdefg'))))" ['a', 'c', 'b', 'e', 'd', 'g', 'f'] $ python2.7 -c "print(list(dict.fromkeys(list('abcdefg'))))" ['a', 'c', 'b', 'e', 'd', 'g', 'f']Python3.5.2 で辞書のキー順を取得((B) の確認):
$ python3.5 -c "print(list(dict.fromkeys(list('abcdefg'))))" ['e', 'd', 'f', 'a', 'b', 'c', 'g'] $ python3.5 -c "print(list(dict.fromkeys(list('abcdefg'))))" ['e', 'f', 'g', 'b', 'a', 'c', 'd'] $ python3.5 -c "print(list(dict.fromkeys(list('abcdefg'))))" ['d', 'e', 'a', 'g', 'b', 'f', 'c']Python3.6.0 で辞書のキー順を取得((C) の確認):
$ python3.6 -c "print(list(dict.fromkeys(list('abcdefg'))))" ['a', 'b', 'c', 'd', 'e', 'f', 'g'] $ python3.6 -c "print(list(dict.fromkeys(list('abcdefg'))))" ['a', 'b', 'c', 'd', 'e', 'f', 'g'] $ python3.6 -c "print(list(dict.fromkeys(list('abcdefg'))))" ['a', 'b', 'c', 'd', 'e', 'f', 'g']質問
Python3.6では、セキュリティ上安全で、これまでOrderedDictを使っていたプログラムをdictで一部置き換え可能と考えてよいでしょうか？ 複数の要素が絡み合っていそうなので、質問を以下の3つに分けます。
(B) で、DDoS回避のためにdictキー順をランダム化したかった訳ではなく、 object.__hash__ がランダム化された副作用でdictキー順が起動毎にランダムになった、という理解であってますか？
Python3.6未満でも、 PYTHONHASHSEED環境変数 を指定すれば、起動毎には変化しない以前の挙動を復活させる方法がありますが、これをやるとDDoS回避の実装を無効化することになるという理解であってますか？
(C) で、dictのキー順が維持されるようになりましたが、これはキー順が object.__hash__ の結果に依存しなくなった、という理解で合っていますか？ DSAS開発者の部屋:Python に現在実装中の Compact dict の紹介 からそのように読み解きました。
質問1にあるように、当初「DoS回避のためにdictキー順をランダム化したかった」のだと理解していましたが、そうではなかった、というのが回答をもらって確認できました。
回答全文は質問したサイト(teratail)で確認できます。 https://teratail.com/questions/69286#reply-109601 ここでは、教えてもらったリンクについてちょっとだけ紹介します。
python - Why is the order in dictionaries and sets arbitrary? - Stack Overflow¶
Why is the order in dictionaries and sets arbitrary? での質問は、なぜdictとsetのキー順が不定なのか？というものです。 その回答がとても丁寧で分かりやすく書かれていました。
hashの仕組みが実際にどのようにPythonのdictに対して作用しているかを実際のコードを通して説明しています。 実際のコードの部分を自分でもPython3.5でやってみました。
まず、'foo', 'bar', 'baz' の3つの文字列それぞれのhash値を確認します。
>>> hash('foo')
4779196005625627760
>>> hash('bar')
-7134697388611392496
>>> hash('baz')
-5250136657472905660
上記の数値を8で割ったあまりは以下のようになります（Python3.5のhashテーブルサイズは初期は8、という前提がありそうです（未確認））
>>> hash('foo') % 8
0
>>> hash('bar') % 8
0
>>> hash('baz') % 8
4
これを見ると、'foo'と'bar'は8の剰余(mod 8)が0で一緒です。つまりhashテーブルが8つの状況では'foo'と'bar'とでhash collisionが発生していることになります。 StackOverflowの回答には、CPythonでの実装はオープンアドレス法だと書かれているので、hash collisionが起きた場合、hashテーブルの当該エントリは早い者勝ちで決まり、collisionを起こしたキーは次のテーブルの空きを探して再計算されます。 （collisionによる再計算が大量に発生すると計算負荷が上がってDoSが可能になります）
実際にPythonの辞書のキー順でみてみます。まず、mod 8が異なる'foo'と'baz'で確認します。
>>> {'foo': None, 'baz': None}
{'foo': None, 'baz': None}
>>> {'baz': None, 'foo': None}
{'foo': None, 'baz': None}
dict定義としてfooとbazの順番を変えて2パターン書いてみましたが、結果は常にfooが先に表示されました。 （mod 8の値が小さい順に並んでいるという訳ではなさそうです）
次に、mod 8が同じ、'foo'と'bar'で確認します。
>>> {'foo': None, 'bar': None}
{'foo': None, 'bar': None}
>>> {'bar': None, 'foo': None}
{'bar': None, 'foo': None}
先ほどのfoo,bazと異なり、今回は定義した順に表示されました。
'foo'と'baz'の場合、fooが常に先にきたのは hash('foo') % 8 が0で hash('baz') % 8 の4よりも小さいから、・・・ということではなさそうです。実際に mod 8 の結果が異なる8つのキーで試してみました:
>>> import string
>>> d = dict(zip([hash(c)%8 for c in string.ascii_letters], string.ascii_letters))
>>> d
{0: 'X', 1: 'R', 2: 'Y', 3: 'U', 4: 'N', 5: 't', 6: 'Z', 7: 'S'}
>>> dict([(v,k) for k, v in d.items()])
{'X': 0, 'Y': 2, 'Z': 6, 'R': 1, 'U': 3, 'N': 4, 't': 5, 'S': 7}
なるほどー。
なおPython3.6では、辞書のキー順を維持するので、hash値がどうであっても結果は固定化されます。
まとめ¶
teratailで回答をもらったことと、上記のStackOverflowの回答を読んだことで、自分の理解は次ようになりました。
object.__hash__ のhash collisionによるDoS攻撃を回避するために、Python3.3で起動毎にhashをランダム化した
これによって、hashテーブルの順番で並んでいた特定のdictキー列も、起動毎にランダム化された（副作用）
Python3.6の CPython実装 で、dictキーを挿入順で維持するキー列をhashテーブルtとは別に持つようになったため、キー順が object.__hash__ の結果に依存しなくなった（これは1のDoS回避と反しない）
Pythonの言語仕様は変わっていないので、dictキーを挿入順で維持するかどうかはPython実装に依存している
#python3.6 news: OrderedDict is dead. Long live dicts that are ordered.
— Raymond Hettinger (@raymondh) 2016年9月8日
Regular dicts are ordered and more compact: https://t.co/du4P4M4LFN
Pythonコアデベロッパーが "OrdereDictは死んだ" って言ってるけど、CPython3.6以外だとやっぱりOrderedDict使わなきゃだめなんじゃね？
2017/3/20 修正¶
@methane からツッコミをもらいました。ありがとうございます！
@shimizukawa まず、hashdosはDDoSじゃなくて単なるDoSですね。少数のリクエストで攻撃できるので。
— INADA Naoki (@methane) 2017年3月20日
（もちろん分散させてもいいですが。）
はい。 分散(Distributed)じゃなくても攻撃できるということで、DDoSじゃなくてDoSでした。
@shimizukawa あと、他のPython実装が効率やスレッド対応のために別の方法でdict実装できるように、言語仕様としてはキーワード引数と名前空間だけが順序維持でそれ以外は不定です。
— INADA Naoki (@methane) 2017年3月20日
「言語仕様としてはキーワード引数と名前空間だけが順序維持」
キーワード引数の順序維持
> docker run -it --rm python:3.5.2
Python 3.5.2 (default, Aug 31 2016, 03:01:41)
[GCC 4.9.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> def func(**kwargs):
... return kwargs
...
>>> func(a=1, b=2, c=3)
{'c': 3, 'b': 2, 'a': 1}
3.5まではキーワード引数は順序が不定(hash値依存)だった。
> docker run -it --rm python:3.6
Python 3.6.0 (default, Jan 18 2017, 02:51:38)
[GCC 4.9.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> def func(**kwargs):
... return kwargs
...
>>> func(a=1, b=2, c=3)
{'a': 1, 'b': 2, 'c': 3}
3.6では言語仕様として、キーワード引数の順序が維持される。
言語仕様で保障される、Python名前空間の順序維持
> docker run -it --rm python:3.5.2
Python 3.5.2 (default, Aug 31 2016, 03:01:41)
[GCC 4.9.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> class C:
... a = 1
... b = 2
... c = 3
...
>>> C.__dict__.keys()
dict_keys(['__dict__', '__doc__', 'b', 'c', '__module__', 'a', '__weakref__'])
3.5までは名前空間（この例ではクラス属性）の順序が不定(hash値依存)だった。
> docker run -it --rm python:3.6
Python 3.6.0 (default, Jan 18 2017, 02:51:38)
[GCC 4.9.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> class C:
... a = 1
... b = 2
... c = 3
...
>>> C.__dict__.keys()
dict_keys(['__module__', 'a', 'b', 'c', '__dict__', '__weakref__', '__doc__'])
3.6では言語仕様として、名前空間の順序が維持される。
モジュールの場合も同様.
3.5の場合:
> docker run -it --rm python:3.5.2 python -c "import os; print(list(os.__dict__.keys())[-5:])"
['ttyname', 'system', 'minor', 'read', '_Environ']
> docker run -it --rm python:3.5.2 python -c "import os; print(list(os.__dict__.keys())[-5:])"
['SEEK_HOLE', 'O_NOCTTY', 'umask', 'fchdir', 'SCHED_OTHER']
3.6の場合:
> docker run -it --rm python:3.6 python -c "import os; print(list(os.__dict__.keys())[-5:])"
['popen', '_wrap_close', 'fdopen', '_fspath', 'PathLike']
> docker run -it --rm python:3.6 python -c "import os; print(list(os.__dict__.keys())[-5:])"
['popen', '_wrap_close', 'fdopen', '_fspath', 'PathLike']
2018/7/1 追記¶
Python-3.7.0 （2018/6/27リリース）で、dictキーの順番維持が言語仕様化されました。
公式ドキュメントのリリースノートに以下の様に記載されています。
What’s New In Python 3.7
the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec.
これで、Python-3.7以降を実装する全てのPython実装系で、辞書のキー順序維持が保障されることになります。
