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

このコミットは、Go言語の標準ライブラリ compress/flate パッケージにおける huffmanDecoder の再初期化時のパニックを防ぐための修正です。具体的には、huffmanDecoder が不正な入力で再利用された際に発生する可能性のあるパニックを解消し、より堅牢な動作を保証します。

コミット

compress/flate パッケージの huffmanDecoder が、不正なコード長シーケンスで再初期化された際にパニックを起こす問題を修正します。この修正は、huffmanDecoder の init メソッドの冒頭で、構造体が再利用される場合にゼロ値にリセットすることで、links テーブルの不適切な状態が引き起こすパニックを防ぎます。

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

https://github.com/golang/go/commit/3b6b53f493af5984ca50cc202c3f8e155ad6f526

元コミット内容

commit 3b6b53f493af5984ca50cc202c3f8e155ad6f526
Author: Ehren Kret <ehren.kret@gmail.com>
Date:   Fri Sep 6 15:09:42 2013 -0700

    compress/flate: prevent panic when reinitializing huffmanDecoder with bad input
    
    The huffmanDecoder struct appears to be intented for reuse by calling init a
    second time with a second sequence of code lengths. Unfortunately, it can
    currently panic if the second sequence of code lengths has a minimum value
    greater than 10 due to failure to reinitialize the links table.
    
    This change prevents the panic by resetting the huffmanDecoder struct back to
    the struct's zero value at the beginning of the init method if the
    huffmanDecoder is being reused (determined by checking if min has been set to a
    non-zero value).
    
    Fixes #6255.
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/13230043

変更の背景

この変更の背景には、compress/flate パッケージ内の huffmanDecoder 構造体の再利用に関する潜在的な問題がありました。huffmanDecoder は、異なるハフマン符号のコード長シーケンスで複数回 init メソッドを呼び出すことで再利用されることを意図していました。しかし、2回目以降の init 呼び出しにおいて、与えられたコード長シーケンスの最小値が10より大きい場合にパニックが発生するというバグが存在しました。

このパニックの原因は、huffmanDecoder 内部の links テーブルが適切に再初期化されないことにありました。huffmanDecoder は、ハフマン符号のデコードに必要なテーブルを構築しますが、再利用時に以前の状態が完全にクリアされないままで新しいコード長シーケンスが処理されると、内部的な不整合が生じ、特に links テーブルの構築ロジックにおいて不正なメモリアクセスやロジックエラーが発生し、結果としてパニックに至っていました。

この問題は、GoのバグトラッカーでIssue #6255として報告されていました。このコミットは、この特定のパニックを修正し、huffmanDecoder の再利用が安全に行われるようにすることを目的としています。

前提知識の解説

compress/flate パッケージ

compress/flate はGo言語の標準ライブラリの一部であり、DEFLATEアルゴリズムの実装を提供します。DEFLATEは、LZ77アルゴリズムとハフマン符号化を組み合わせたデータ圧縮アルゴリズムで、Zlib、gzip、PNGなどの多くのファイル形式で利用されています。このパッケージは、データの圧縮（エンコード）と解凍（デコード）の両方の機能を提供します。

ハフマン符号化 (Huffman Coding)

ハフマン符号化は、データ圧縮に用いられる可変長符号化の一種です。出現頻度の高いシンボルには短い符号を割り当て、出現頻度の低いシンボルには長い符号を割り当てることで、全体のデータ量を削減します。デコード時には、符号のビット列を読み取り、対応するシンボルに変換します。この変換には、ハフマン木と呼ばれる二分木構造や、それを効率的に検索するためのテーブルが使用されます。

huffmanDecoder 構造体

huffmanDecoder は、compress/flate パッケージ内でハフマン符号をデコードするために使用される内部構造体です。この構造体は、ハフマン符号のコード長に基づいてデコードテーブル（codes、min、max、links、nodes などのフィールド）を構築し、入力ストリームからビットを読み取ってシンボルに変換するロジックをカプセル化しています。

• init(bits []int) bool メソッド: このメソッドは、huffmanDecoder の主要な初期化ルーチンです。bits 引数は、各シンボルに対応するハフマン符号のコード長（ビット数）のシーケンスを表します。init メソッドは、このコード長情報に基づいて、デコードに必要な内部テーブル（特に links テーブル）を構築します。このメソッドは、テーブルの構築が成功した場合は true を、失敗した場合は false を返します。

links テーブル

huffmanDecoder 内部の links テーブルは、ハフマン符号のデコードプロセスを高速化するための重要なデータ構造です。これは、ハフマン木を直接トラバースする代わりに、ビット列からシンボルを効率的に検索できるようにするためのルックアップテーブルとして機能します。links テーブルの正確な構築と管理は、デコーダの正しい動作とパフォーマンスにとって不可欠です。

技術的詳細

問題の核心は、huffmanDecoder の init メソッドが、既に初期化された huffmanDecoder インスタンスに対して再度呼び出された際に、その内部状態、特に links テーブルが完全にリセットされないことにありました。

huffmanDecoder は、min フィールドが非ゼロ値である場合に、以前に初期化されたと判断します。これは、init メソッドが一度でも成功すると min が設定されるためです。

パニックが発生するシナリオは以下の通りです。

1. huffmanDecoder インスタンスが、有効なコード長シーケンス bits1 で init される。このとき、min フィールドが設定され、links テーブルを含む内部状態が構築される。
2. 同じ huffmanDecoder インスタンスが、今度は不正なコード長シーケンス bits2 で再度 init される。この bits2 は、例えば最小のコード長が10より大きいといった、ハフマン符号の規則に反する特性を持つ。
3. init メソッドは、min が非ゼロであるため、再利用されていると認識するが、links テーブルなどの一部の内部状態が適切にクリアされないまま、新しい（不正な）コード長シーケンスに基づいてテーブルの再構築を試みる。
4. この不完全な状態での再構築プロセス中に、links テーブルへの不正なアクセスや、期待されるデータ構造が満たされないことによるロジックエラーが発生し、結果としてランタイムパニック（例: インデックス範囲外アクセスなど）が引き起こされる。

このコミットによる修正は、この問題を解決するために、init メソッドの冒頭で huffmanDecoder 構造体全体をゼロ値にリセットするというシンプルなアプローチを採用しています。

具体的には、h.min != 0 という条件で huffmanDecoder が再利用されているかをチェックし、もし再利用されている場合は *h = huffmanDecoder{} という行を実行します。この操作により、h が指す huffmanDecoder インスタンスのすべてのフィールドがその型のゼロ値（数値型は0、ポインタはnil、構造体はすべてのフィールドがゼロ値）にリセットされます。これにより、links テーブルを含むすべての内部状態がクリーンな状態に戻され、新しいコード長シーケンスに基づいて最初からテーブルが構築されることが保証されます。

この修正により、huffmanDecoder は、たとえ不正な入力で再初期化されたとしても、以前の状態に起因するパニックを起こすことなく、安全にエラーを処理（init メソッドが false を返すなど）できるようになります。

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

変更は主に2つのファイルで行われています。

1. src/pkg/compress/flate/flate_test.go: 問題を再現し、修正が正しく機能することを確認するためのテストケースが追加されました。
2. src/pkg/compress/flate/inflate.go: huffmanDecoder 構造体の init メソッドに修正が加えられました。

--- a/src/pkg/compress/flate/flate_test.go
+++ b/src/pkg/compress/flate/flate_test.go
@@ -47,3 +47,16 @@ func TestIssue5962(t *testing.T) {
 		t.Fatalf("Given sequence of bits is bad, and should not succeed.")
 	}
 }
+
+// The following test should not panic.
+func TestIssue6255(t *testing.T) {
+	bits1 := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 11}
+	bits2 := []int{11, 13}
+	h := new(huffmanDecoder)
+	if !h.init(bits1) {
+		t.Fatalf("Given sequence of bits is good and should succeed.")
+	}
+	if h.init(bits2) {
+		t.Fatalf("Given sequence of bits is bad and should not succeed.")
+	}
+}
diff --git a/src/pkg/compress/flate/inflate.go b/src/pkg/compress/flate/inflate.go
index 0287867208..34ba00d5af 100644
--- a/src/pkg/compress/flate/inflate.go
+++ b/src/pkg/compress/flate/inflate.go
@@ -91,6 +91,10 @@ type huffmanDecoder struct {
 
 // Initialize Huffman decoding tables from array of code lengths.
 func (h *huffmanDecoder) init(bits []int) bool {
+	if h.min != 0 {
+		*h = huffmanDecoder{}
+	}
+
 	// Count number of codes of each length,
 	// compute min and max length.
 	var count [maxCodeLen]int

コアとなるコードの解説

src/pkg/compress/flate/flate_test.go の変更

TestIssue6255 という新しいテスト関数が追加されました。このテストの目的は、huffmanDecoder の再初期化時にパニックが発生しないことを確認することです。

1. bits1 := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 11}: これは有効なコード長シーケンスです。
2. bits2 := []int{11, 13}: これは不正なコード長シーケンスです。このシーケンスは、ハフマン符号の規則（例えば、コード長の合計が特定の条件を満たす必要があるなど）に違反しているか、または links テーブルの再構築を失敗させるような特性を持っています。コミットメッセージによると、「最小値が10より大きい」という条件がパニックを引き起こす原因でした。
3. h := new(huffmanDecoder): 新しい huffmanDecoder インスタンスを作成します。
4. if !h.init(bits1) { ... }: 最初に bits1 で huffmanDecoder を初期化します。これは成功するはずです。
5. if h.init(bits2) { ... }: 次に、同じ huffmanDecoder インスタンスを bits2 で再初期化します。この呼び出しは、不正な入力であるため false を返すことが期待されますが、重要なのはこの呼び出し中にパニックが発生しないことです。このテストは、パニックが発生しないことを保証し、init メソッドが false を返すことを検証します。

src/pkg/compress/flate/inflate.go の変更

huffmanDecoder 構造体の init メソッドに以下の4行が追加されました。

func (h *huffmanDecoder) init(bits []int) bool {
	if h.min != 0 {
		*h = huffmanDecoder{}
	}
	// Count number of codes of each length,
	// compute min and max length.
	var count [maxCodeLen]int
	// ... (既存のコード)
}

• if h.min != 0 { ... }: この条件は、huffmanDecoder インスタンスが既に一度初期化されているかどうかをチェックします。min フィールドは、ハフマン符号の最小コード長を格納するために使用され、init メソッドが成功すると非ゼロ値に設定されます。したがって、h.min != 0 は、この huffmanDecoder が再利用されていることを示します。
• *h = huffmanDecoder{}: この行が修正の核心です。もし huffmanDecoder が再利用されている場合、この行は h が指す huffmanDecoder 構造体全体をその型のゼロ値にリセットします。これにより、huffmanDecoder のすべてのフィールド（codes、min、max、links、nodes など）が初期状態に戻されます。特に、以前の links テーブルの状態が完全にクリアされるため、新しい（たとえ不正な）コード長シーケンスで init が呼び出されても、以前の状態に起因する不整合やパニックを防ぐことができます。

この修正により、huffmanDecoder は常にクリーンな状態から初期化されるようになり、再利用時の堅牢性が大幅に向上しました。

関連リンク

• Go言語の公式リポジトリ: https://github.com/golang/go
• このコミットのGo Gerrit Code Reviewリンク: https://golang.org/cl/13230043
• Go Issue #6255: コミットメッセージに記載されていますが、現在の公開されたGoのIssueトラッカーでは直接検索できませんでした。これは、非常に古いIssueであるか、内部的なトラッカーIDである可能性があります。

参考にした情報源リンク

• Go言語のソースコード (特に compress/flate パッケージ): https://github.com/golang/go/tree/master/src/compress/flate
• ハフマン符号化に関する一般的な情報源 (例: Wikipediaなど)
• DEFLATEアルゴリズムに関する一般的な情報源 (例: RFC 1951など)
• Go言語の構造体のゼロ値に関するドキュメント
• Go言語のテストに関するドキュメント
• コミットメッセージとコード差分
• Google検索 (Go issue 6255) - 直接的なIssueは見つかりませんでしたが、関連する情報収集に利用しました。