WebAssembly Spec 2.0 DraftからみるLeb128デコーディングの落とし穴
どーも、ちょびえです。WebAssembly AdvendCalendarの４日目の記事では仕様書をからめつつValidationのことについて書いておりました。が、Leb128をいい加減にデコードしていたら大量のテストを直す羽目になりました。(ﾉω・)ﾃﾍ
ということで今日はこの問題についてメモ書きををしておきます。7日目ということで！
WebAsembly Spec 2.0のleb128 Decodeで何が問題となるのか
WebAssemblyのバイナリフォーマットのInteger系統は基本的にLeb128形式を使っています。ProtocolBufferなどでよく使われるvarint、可変長のInteger的なものです。実際に値としてバイナリエンコードをする際には4byte〜8byteをすべてのケースで使うことはなく、数バイトで表現できる値を利用することが多いことから、データサイズを減らしたい場合によく使われている形式です。
WebAssemblyの仕様ではLeb128の仕様に追加の制約として、型が想定するサイズ(ceil(Nbit/7))までは表現をしても良いという制約があります。u32であれば5バイト(ceil(32bit/7))の範囲まではデータを使うことが許容されています。u8であれば2バイト(ceil(8/7))となります。
WebAssemblyのleb128ではこの制約があるため、デコードをするコンテキスト(u8なのかu32なのか)によっては同じデータでもエラーとして扱わなければいけなくなります。
ふつうのLeb128で出てくる冗長表現
Leb128では継続のために1バイト中の最上位ビットが立っている場合 (0b1000_0000) は継続とみなします。WebAssemblyの仕様で明示されている制約がない場合は0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80,......0x00という表現が許容されてしまいます。
理由となる背景をきちんと追っていませんが、制約あったほうがいいよねというのと、型ごとにceil(bit width/7)という制限については特に異論はないと思います。WebAssemblyでは前述した制約外の冗長表現はエラーとします。許容バイト数内であればOKです。ということになっています。
具体的な問題例
先も例示しましたが0x00という値をエンコードする場合、Leb128では冗長なエンコードをすることができます。0x80, 0x00のように冗長な表現も可能です。leb128はある程度割り切った仕様なので仕方がない部分です。とはいえ、デコード側からすると正しく処理を行わないと全体でデコードがずれてしまうので大問題です。データと型をもとに説明していきます。
0x00をエンコードする場合、u32は5バイトまで(ceil(32/7))使えるため次のような表現が可能です。
0x80, 0x80, 0x80, 0x80, 0x00
u8の場合は2バイトまで(ceil(8bit/7))なので上記データはエラーとなります。u8では許容される表現としては
0x80, 0x00までとなります。
仕様上の型を気にせずにleb128のデコードをしているとこの差異が判定できません。Spec Testを通す際に問題として表面化します。
どういう実装で問題になるのか
WebAssemblyの仕様書を見つつ、leb128のデコーダーを作っていれば基本的に大丈夫です。汎用leb128のデコーダーを使っている場合はWebAssemblyの仕様に準拠していない場合もあるので注意が必要です。
基本的に型やビット幅を指定出来ないタイプのleb128デコーダーでは不十分だと思います。というか、ceil(bitwidth/7)というwebassemblyの仕様が入っているとは限らないので多分WebAssemblyの仕様に通したものを作る場合は自作が必要だと思います。
WebAssembly 2.0 specのテストではbinary-leb128.wastで主にleb128のテストが行われています。wastだけだと使いづらいので次のコードブロックは適当に抽出したテストケースです。だいたい似たような値が出てくるので網羅的ではありませんが、雑にこれを通しつつ、仕様書を眺めて型に応じたデコードをしていれば問題にはならないと思います。
// 網羅的じゃないけれどだいたいはわかると思う
// byte列, expected, エラー文言
//
// u8からOKな表現
// (new byte[] { 0x82, 0x00 }, "2", null),
// (new byte[] { 0x80, 0x00 }, "0", null),
// (new byte[] { 0x88, 0x00 }, "8", null),
// (new byte[] { 0x81, 0x00 }, "1", null),
// (new byte[] { 0x8a, 0x00 }, "10", null),
// u32からOKな表現(u8ではサイズ上限を超えるのでエラー)
// (new byte[] { 0x82, 0x80, 0x80, 0x80, 0x00 }, "2", null),
// u32の場合は5byteを超えるのでエラーとして扱う(u64であればok)
// (new byte[] { 0x83, 0x80, 0x80, 0x80, 0x80, 0x00 }, null, "integer representation too long"),
// (new byte[] { 0x80, 0x80, 0x80, 0x80, 0x80, 0x00 }, null, "integer representation too long"),
// (new byte[] { 0x82, 0x80, 0x80, 0x80, 0x80, 0x00 }, null, "integer representation too long"),
// 0x80で継続されるとshiftが大きくなるのでそれ由来のエラー判定
// (new byte[] { 0x82, 0x80, 0x80, 0x80, 0x70 }, null, "integer too large"),
// (new byte[] { 0x82, 0x80, 0x80, 0x80, 0x40 }, null, "integer too large"),
// (new byte[] { 0x80, 0x80, 0x80, 0x80, 0x10 }, null, "integer too large"),
// (new byte[] { 0x80, 0x80, 0x80, 0x80, 0x00 }, "0", null),
// i32
// (new byte[] { 0xff, 0xff, 0xff, 0xff, 0x7f }, "-1", null),
// u32の制約である5byteを超える表現
// (new byte[] { 0x82, 0x80, 0x80, 0x80, 0x80, 0x10 }, null, "integer too large"),
// 64用
// (new byte[] { 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x00 }, "0", null),
// i64用
// (new byte[] { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f }, "-1", null)
私は型をあんまりよく見ないでleb128のデコードをしていたので書き直しました。
余談ですが、公式のテストを通す場合はwast側をちゃんと読むとコメントが書かれているので問題発生時に解決がしやすいと思います。jsonやwasm側だけを見るとコメントが落ちちゃっているので何が問題か分かりづらい…
Discussion
テストの解釈は難しい。
このテストをどう解釈すればいいかよくわからないなーと思ってて悩んでいたのでIssue投げてみたところ
エンコードされたバイナリが間違っていないかという確認のためのテストということだった。
func typeは
0x60なんだけれども、0x60を符号付きLEB128でエンコードすると0xe0 0x7fになる。0x60ではないのでデコードの処理でエラーになるよ（ということでエンコードが間違っていないという確認）らしい。仕様書記載は単一バイトの
0x60である、ということだけれども実装上data[index]で読むかLeb128で読むかでエラー判定方法が変わるのでお悩みポイントだった。
Leb128で読むのでも
integer representation too longなのかinteger too largeどちらを出すかで順序が変わるんだけれど実装者の好みでいいということなので自分の実装ではinteger too large系のエラーを実際には吐くけれどテスト用に帳尻合わせをする方向にした。