イカれたCBORのデコード - Python編

created: 2019/01/20 00:19

前回はPHPのCBORのデコーダーを見たので、今回はPythonにおけるCBORのデコーダーを見ていこうと思います。
(わざわざデコーダーの実装を見るモチベーションや「イカれたCBOR」についても、PHP編に書いています。)

http://cbor.io/impls.htmlにはPythonのCBORデコーダーが4つ記載されています。
どれもpipでインストールできるため、全て手元で動かし、イカれたCBORを与えてみることにします。
ちなみに環境はPHP編を試した時のものと同じ、ConoHaで借りたメモリが512MBのVPSで、
Pythonはバージョン3.6.7を用いています。
事前に以下のコマンドで4つ全てのデコーダーをインストールしています。

pip3 install flynn
pip3 install flunn
pip3 install cbor
pip3 install cbor2

入力として与えるCBORは、PHP編と同じ9A 0F FF FF FFです。
これは要素数が268435455の配列の開始を表現しているだけの不正なCBORです。

Flynn, Flunn

cbor.ioに列挙されているデコーダーのうちの2つです。
FlunnFlynnからforkしている実装のようなので、一緒くたに見ていきます。
まずはFlynnにイカれたCBORをブチ込みます。

$ time python3 -c "import flynn; flynn.loads(b'\x9A\x0F\xFF\xFF\xFF')"
Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/local/lib/python3.6/dist-packages/flynn/decoder.py", line 176, in loads
    return cls(io.BytesIO(data), *args, **kwargs).decode()
  File "/usr/local/lib/python3.6/dist-packages/flynn/decoder.py", line 36, in decode
    return decoder(mtype, ainfo)
  File "/usr/local/lib/python3.6/dist-packages/flynn/decoder.py", line 88, in decode_list
    res[n] = self.decode()
  File "/usr/local/lib/python3.6/dist-packages/flynn/decoder.py", line 31, in decode
    mtype, ainfo = self._decode_ibyte()
  File "/usr/local/lib/python3.6/dist-packages/flynn/decoder.py", line 146, in _decode_ibyte
    byte = self._read(1)[0]
  File "/usr/local/lib/python3.6/dist-packages/flynn/decoder.py", line 169, in _read
    raise InvalidCborError("Expected {} bytes, got {} bytes instead".format(n, len(m)))
flynn.decoder.InvalidCborError: Expected 1 bytes, got 0 bytes instead

real    2m45.898s
user    0m17.702s
sys 0m18.349s

(◞‸◟)

例外は意図したものが出ているように見えますが、それまでになかなかの時間を使います。
Flunnはどうでしょうか?

$ time python3 -c "import flunn; flunn.loads(b'\x9A\x0F\xFF\xFF\xFF')"
Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/local/lib/python3.6/dist-packages/flunn/decoder.py", line 198, in loads
    return cls(io.BytesIO(data), *args, **kwargs).decode()
  File "/usr/local/lib/python3.6/dist-packages/flunn/decoder.py", line 38, in decode
    return decoder(mtype, ainfo)
  File "/usr/local/lib/python3.6/dist-packages/flunn/decoder.py", line 90, in decode_list
    res[n] = self.decode()
  File "/usr/local/lib/python3.6/dist-packages/flunn/decoder.py", line 33, in decode
    mtype, ainfo = self._decode_ibyte()
  File "/usr/local/lib/python3.6/dist-packages/flunn/decoder.py", line 148, in _decode_ibyte
    byte = self._read(1)[0]
  File "/usr/local/lib/python3.6/dist-packages/flunn/decoder.py", line 171, in _read
    raise InvalidCborError("Expected {} bytes, got {} bytes instead".format(n, len(m)))
flunn.decoder.InvalidCborError: Expected 1 bytes, got 0 bytes instead

real    2m48.122s
user    0m18.844s
sys 0m18.205s

(◞‸◟)

同じですね。
どちらもたった5バイトの不正なCBORが入力されると、何十秒もの時間を消費します。

実装を見て見ましょう。
実装を見る限り、Flunnはforkしているだけあって原因はおそらくFlynnと同じものです。
そのためFlynnの実装のみを見ます。

https://github.com/fritz0705/flynn/blob/b8658daa3fae97c27d12847d571cc70d2e4aec66/flynn/decoder.py#L86

結構分かりやすく、Flynn及びFlunnでは配列長を読み込んだ時点で、その読み込んだ配列長分のリストを作成します。
CBORに含まれている実際の要素数に関係なく初期化を行なっているため、このあたりがボトルネックになっているようです。
topコマンドで簡単に見てみると、スワップをかなり使用しているように見えたので、
ここまで時間がかかるのはメモリが512MBしかないVPS上で確認していることも影響しているのかもしれません。
が、いずれにしてもそこまでリソースの消費が激しいことは問題でしょう。

cbor

次はcborを試してみます。

$ time python3 -c "import cbor; cbor.loads(b'\x9A\x0F\xFF\xFF\xFF')"
Traceback (most recent call last):
  File "<string>", line 1, in <module>
LookupError: buffer exhausted

real    0m2.645s
user    0m2.387s
sys 0m0.256s

ちょっと微妙なライン。
実装を確認しようと思ったのですが、cborはC拡張を用いており、
具体的に問題のある実装かどうかを判断するのは自分では困難でした。

cbor2

次はcbor2

$ time python3 -c "import cbor2; cbor2.loads(b'\x9A\x0F\xFF\xFF\xFF')"
Traceback (most recent call last):
  File "/usr/local/lib/python3.6/dist-packages/cbor2/decoder.py", line 390, in decode
    initial_byte = byte_as_integer(self.fp.read(1))
  File "/usr/local/lib/python3.6/dist-packages/cbor2/compat.py", line 44, in byte_as_integer
    return bytestr[0]
IndexError: index out of range

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/local/lib/python3.6/dist-packages/cbor2/decoder.py", line 431, in loads
    return CBORDecoder(fp, **kwargs).decode()
  File "/usr/local/lib/python3.6/dist-packages/cbor2/decoder.py", line 399, in decode
    return decoder(self, subtype, shareable_index)
  File "/usr/local/lib/python3.6/dist-packages/cbor2/decoder.py", line 79, in decode_array
    item = decoder.decode()
  File "/usr/local/lib/python3.6/dist-packages/cbor2/decoder.py", line 395, in decode
    .format(self.fp.tell(), e))
cbor2.decoder.CBORDecodeError: error reading major type at index 5: index out of range

real    0m0.148s
user    0m0.126s
sys 0m0.021s

良さそう。無駄なリソースを使っている雰囲気はなさそうです。
実装はどうでしょうか。

https://github.com/agronholm/cbor2/blob/master/cbor2/decoder.py#L78

cbor2は巨大な配列長を読み込んだとしても、その分だけのリストを初期化したりするようなことはしないようです。
そうではなく、実際に後続のバイト列を読み込み、正しくデコードできた分だけをリストに追加していくという実装ですね。
今回入力しているような不正なCBORは配列長が巨大であるように見せかけることはできても、
実際のデータを保持しているわけではないので、cbor2はこのようなCBORを不正なCBORと認識してくれます。
良い実装ですね。

終わりに

GitHubを覗いてみると、FlunnFlynnは数年前からコミットが無いような状態だったので、
このような意地悪な入力をするのは少し可哀想だったかもしれません。

cbor2は最近もちゃんとメンテナンスされているようですし、
安心できる実装をしている良いデコーダーだと思います。