Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 13476] ファイルの概要

このコミットは、Go言語の標準ライブラリ compress/flate パッケージにおけるバグ修正です。具体的には、DEFLATE圧縮データストリームの不正な入力（nlit の値が範囲外）が原因で発生するパニック（プログラムの異常終了）を修正し、代わりに CorruptInputError を返すように変更しています。

コミット

commit da4eef402d55b91a3e3ea16a3ff4f8902526eac0
Author: Nigel Tao <nigeltao@golang.org>
Date:   Mon Jul 16 12:01:18 2012 +1000

    compress/flate: fix panic when nlit is out of bounds.
    
    Fixes #3815.
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6352109

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/da4eef402d55b91a3e3ea16a3ff4f8902526eac0

元コミット内容

---
 src/pkg/compress/flate/inflate.go     | 12 +++++++++---\n src/pkg/compress/flate/reader_test.go | 10 ++++++++++\n 2 files changed, 19 insertions(+), 3 deletions(-)\n\ndiff --git a/src/pkg/compress/flate/inflate.go b/src/pkg/compress/flate/inflate.go
index a4be91b6f7..92670126e6 100644
--- a/src/pkg/compress/flate/inflate.go
+++ b/src/pkg/compress/flate/inflate.go
@@ -16,9 +16,10 @@ import (\n const (\n \tmaxCodeLen = 16    // max length of Huffman code\n \tmaxHist    = 32768 // max history required\n-\tmaxLit     = 286\n-\tmaxDist    = 32\n-\tnumCodes   = 19 // number of codes in Huffman meta-code\n+\t// The next three numbers come from the RFC, section 3.2.7.\n+\tmaxLit   = 286\n+\tmaxDist  = 32\n+\tnumCodes = 19 // number of codes in Huffman meta-code\n )\n \n // A CorruptInputError reports the presence of corrupt input at a given offset.\n@@ -306,10 +307,15 @@ func (f *decompressor) readHuffman() error {\n \t\t}\n \t}\n \tnlit := int(f.b&0x1F) + 257\n+\tif nlit > maxLit {\n+\t\treturn CorruptInputError(f.roffset)\n+\t}\n \tf.b >>= 5\n \tndist := int(f.b&0x1F) + 1\n+\t// maxDist is 32, so ndist is always valid.\n \tf.b >>= 5\n \tnclen := int(f.b&0xF) + 4\n+\t// numCodes is 19, so nclen is always valid.\n \tf.b >>= 4\n \tf.nb -= 5 + 5 + 4\n \ndiff --git a/src/pkg/compress/flate/reader_test.go b/src/pkg/compress/flate/reader_test.go\nindex 84cc953ee3..54ed788dbd 100644\n--- a/src/pkg/compress/flate/reader_test.go\n+++ b/src/pkg/compress/flate/reader_test.go\n@@ -9,9 +9,19 @@ import (\n \t\"io\"\n \t\"io/ioutil\"\n \t\"runtime\"\n+\t\"strings\"\n \t\"testing\"\n )\n \n+func TestNlitOutOfRange(t *testing.T) {\n+\t// Trying to decode this bogus flate data, which has a Huffman table\n+\t// with nlit=288, should not panic.\n+\tio.Copy(ioutil.Discard, NewReader(strings.NewReader(\n+\t\t\"\\xfc\\xfe\\x36\\xe7\\x5e\\x1c\\xef\\xb3\\x55\\x58\\x77\\xb6\\x56\\xb5\\x43\\xf4\"+\n+\t\t\t\"\\x6f\\xf2\\xd2\\xe6\\x3d\\x99\\xa0\\x85\\x8c\\x48\\xeb\\xf8\\xda\\x83\\x04\\x2a\"+\n+\t\t\t\"\\x75\\xc4\\xf8\\x0f\\x12\\x11\\xb9\\xb4\\x4b\\x09\\xa0\\xbe\\x8b\\x91\\x4c\")))\n+}\n+\n const (\n \tdigits = iota\n \ttwain\n```

## 変更の背景

このコミットは、Go言語のIssue #3815「`compress/flate: panic when nlit is out of bounds`」を修正するために行われました。このIssueは、不正なDEFLATE圧縮データが `compress/flate` パッケージのデコンプレッサーに与えられた際に、プログラムがパニックを起こして異常終了するというものでした。

DEFLATE形式では、圧縮データのヘッダー部分にハフマン符号のテーブルを記述するための情報が含まれています。この情報の一つに `HLIT` (または `nlit`) という値があり、これはリテラル/長さ符号の数を示します。DEFLATEの仕様（RFC 1951）では、この `HLIT` の値には `257` から `286` までの範囲が定められています。しかし、不正なデータが与えられた場合、この `nlit` の値が `maxLit` (286) を超える可能性がありました。

修正前のコードでは、`nlit` の値が `maxLit` を超えた場合に、その後の配列アクセスで範囲外参照が発生し、結果としてパニックを引き起こしていました。このコミットは、このような不正な入力に対してパニックではなく、より適切なエラー（`CorruptInputError`）を返すようにすることで、デコンプレッサーの堅牢性を向上させています。

## 前提知識の解説

### DEFLATE圧縮アルゴリズム

DEFLATEは、Zlib、gzip、PNGなどのファイル形式で広く使用されているロスレスデータ圧縮アルゴリズムです。ハフマン符号化とLZ77アルゴリズムの組み合わせに基づいています。

*   **LZ77**: 繰り返し出現するバイトシーケンス（文字列）を、以前に出現したシーケンスへの「参照」（長さと距離）に置き換えることでデータを圧縮します。
*   **ハフマン符号化**: 出現頻度の高いシンボルには短いビット列を、出現頻度の低いシンボルには長いビット列を割り当てることで、データをさらに圧縮します。

DEFLATEデータストリームは、ブロックのシーケンスで構成されており、各ブロックは非圧縮、固定ハフマン符号、または動的ハフマン符号のいずれかです。このコミットが関連するのは、動的ハフマン符号ブロックの処理です。

### ハフマン符号とDEFLATEにおけるその役割

DEFLATEでは、リテラルバイト（実際のデータ）とLZ77の長さ/距離ペアを符号化するためにハフマン符号が使用されます。動的ハフマン符号ブロックでは、符号化に使用されるハフマンツリー自体が圧縮データストリーム内に記述されます。

ハフマンツリーの記述には、以下の3種類の符号の数が含まれます。

1.  **リテラル/長さ符号 (Literal/Length codes)**: `HLIT` (または `nlit`) で示され、リテラルバイトとLZ77の長さ符号の数を定義します。RFC 1951では、`257` から `286` の範囲と定められています。
2.  **距離符号 (Distance codes)**: `HDIST` (または `ndist`) で示され、LZ77の距離符号の数を定義します。RFC 1951では、`1` から `32` の範囲と定められています。
3.  **符号長符号 (Code Length codes)**: `HCLEN` (または `nclen`) で示され、リテラル/長さ符号と距離符号のハフマンツリーを記述するための符号長符号の数を定義します。RFC 1951では、`4` から `19` の範囲と定められています。

これらの値は、圧縮データストリームのヘッダー部分から読み取られ、ハフマンツリーを再構築するために使用されます。

### `CorruptInputError`

`CorruptInputError` は、Go言語の `compress/flate` パッケージで定義されているエラー型です。これは、入力データがDEFLATE形式の仕様に準拠していない、つまり破損している場合に返されます。パニックはプログラム全体を終了させるため、ライブラリとしてはパニックではなく、このような特定のエラーを返すことが望ましい挙動です。これにより、呼び出し元のアプリケーションがエラーを捕捉し、適切に処理できるようになります。

## 技術的詳細

`compress/flate` パッケージの `decompressor` 構造体には、`readHuffman` メソッドがあります。このメソッドは、動的ハフマン符号ブロックのヘッダーを読み取り、ハフマンツリーを構築する役割を担っています。

問題となっていたのは、`nlit` の値を読み取る以下の行です。

```go
nlit := int(f.b&0x1F) + 257

ここで f.b はビットバッファから読み取られたデータの一部であり、0x1F (バイナリで 00011111) とのビットAND演算によって下位5ビットが抽出されます。この5ビットの値に 257 を加算することで nlit の値が計算されます。

RFC 1951の仕様では、HLIT の値は 0 から 29 の範囲でエンコードされ、これに 257 を加算することで 257 から 286 の最終的な nlit 値が得られます。しかし、不正な入力データの場合、この5ビットの値が仕様外の大きな値になる可能性がありました。

修正前のコードでは、nlit が maxLit (286) を超える場合でもチェックが行われず、その後のハフマンツリー構築ロジックで、nlit をインデックスとして使用する配列アクセスが発生し、結果として配列の境界外にアクセスしてパニックを引き起こしていました。

このコミットでは、nlit の計算直後に if nlit > maxLit というチェックを追加し、もし nlit が maxLit を超えていれば、即座に CorruptInputError を返すように変更されています。これにより、不正な入力データに対する堅牢性が向上し、パニックが回避されます。

同様に、ndist と nclen についてもコメントが追加され、これらの値が常に有効な範囲内にあることが明示されています。maxDist は32、numCodes は19であり、それぞれの計算式 (int(f.b&0x1F) + 1 と int(f.b&0xF) + 4) から得られる値がこれらの最大値を超えることはないため、追加の範囲チェックは不要であることが示されています。

コアとなるコードの変更箇所

src/pkg/compress/flate/inflate.go

  • maxLit, maxDist, numCodes の定数定義に、RFC 1951のセクション3.2.7から来ていることを示すコメントが追加されました。
  • readHuffman メソッド内で nlit を計算した後、if nlit > maxLit という条件チェックが追加され、maxLit を超える場合は CorruptInputError を返すようになりました。
  • ndist と nclen の計算行に、それぞれの値が常に有効な範囲内にあることを示すコメントが追加されました。

src/pkg/compress/flate/reader_test.go

  • TestNlitOutOfRange という新しいテスト関数が追加されました。
  • このテストは、nlit=288 という不正なハフマンテーブル情報を含む、意図的に破損させたDEFLATEデータを NewReader に与え、それがパニックを起こさないことを確認します。具体的には、io.Copy(ioutil.Discard, NewReader(...)) を実行し、エラーが発生してもパニックしないことを検証しています。

コアとなるコードの解説

inflate.go の変更

 // The next three numbers come from the RFC, section 3.2.7.
 maxLit   = 286
 maxDist  = 32
 numCodes = 19 // number of codes in Huffman meta-code

これらのコメントは、DEFLATEアルゴリズムの仕様を定めたRFC 1951のセクション3.2.7に、これらの定数の値の根拠があることを明示しています。これにより、コードの可読性と保守性が向上します。

 nlit := int(f.b&0x1F) + 257
 if nlit > maxLit {
  return CorruptInputError(f.roffset)
 }

これがこのコミットの主要な修正点です。

  1. nlit は、ビットバッファ f.b から5ビットを読み取り、それに 257 を加算して計算されます。この5ビットは、RFC 1951で HLIT と呼ばれる値に対応します。
  2. 計算された nlit が maxLit (286) を超える場合、それはDEFLATEの仕様に違反する不正な入力データであることを意味します。
  3. この場合、CorruptInputError を返して処理を中断します。f.roffset は、エラーが発生した入力ストリーム内のオフセットを示します。これにより、パニックを回避し、呼び出し元に適切なエラー情報を提供します。
 ndist := int(f.b&0x1F) + 1
 // maxDist is 32, so ndist is always valid.
 f.b >>= 5
 nclen := int(f.b&0xF) + 4
 // numCodes is 19, so nclen is always valid.

これらのコメントは、ndist と nclen の計算結果が、それぞれの最大値 (maxDist と numCodes) を超えることがないため、追加の範囲チェックが不要であることを説明しています。これは、コードの意図を明確にし、将来的な誤解を防ぐためのものです。

reader_test.go の変更

func TestNlitOutOfRange(t *testing.T) {
 // Trying to decode this bogus flate data, which has a Huffman table
 // with nlit=288, should not panic.
 io.Copy(ioutil.Discard, NewReader(strings.NewReader(
  "\xfc\xfe\x36\xe7\x5e\x1c\xef\xb3\x55\x58\x77\xb6\x56\xb5\x43\xf4"+
  "\x6f\xf2\xd2\xe6\x3d\x99\xa0\x85\x8c\x48\xeb\xf8\xda\x83\x04\x2a"+
  "\x75\xc4\xf8\x0f\x12\x11\xb9\xb4\x4b\x09\xa0\xbe\x8b\x91\x4c"))))
}

このテストは、バグ修正の検証のために非常に重要です。

  1. strings.NewReader を使用して、nlit=288 となるように特別に細工された不正なDEFLATEデータを含む io.Reader を作成します。
  2. NewReader は compress/flate パッケージのデコンプレッサーを作成します。
  3. io.Copy(ioutil.Discard, ...) は、デコンプレッサーから読み出されるデータをすべて破棄します。これにより、実際にデータをデコードする処理がトリガーされます。
  4. このテストの目的は、この不正なデータが与えられたときに、プログラムがパニックを起こさずに正常に終了すること（つまり、CorruptInputError が返されること）を確認することです。テストがパニックせずに完了すれば、修正が成功したことを意味します。

関連リンク

参考にした情報源リンク