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

このコミットは、Go言語の標準ライブラリ compress/flate パッケージにおける、不正なデータが与えられた際に発生する無限ループのバグを修正するものです。具体的には、Huffmanデコーダが不正な入力に遭遇した際に、適切なエラー処理が行われず、デコード処理が停止しなくなる問題に対処しています。この修正は、compress/gzip パッケージを介して発見された問題に対応しており、テストケースも追加されています。

コミット

commit 8ba6deb1ec6cc48b54e98cb97de5e907e7901c58
Author: Russ Cox <rsc@golang.org>
Date:   Wed Oct 9 08:37:06 2013 -0400

    compress/flate: fix infinite loop on malformed data
    
    Test using compress/gzip, because that's how the
    data arrived.
    
    Fixes #6550.
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/14441051

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

https://github.com/golang/go/commit/8ba6deb1ec6cc48b54e98cb97de5e907e7901c58

元コミット内容

compress/flate: fix infinite loop on malformed data

このコミットは、compress/flate パッケージが不正なデータを処理する際に発生する無限ループを修正します。この問題は compress/gzip を使用している際に発見されたため、compress/gzip を用いたテストが追加されています。

このコミットは、Issue #6550 を修正します。

変更の背景

この変更の背景には、Go言語の compress/flate パッケージが、特定の形式の不正な圧縮データを受け取った際に、デコード処理が無限ループに陥るという深刻なバグが存在していました。このような無限ループは、サービス拒否（DoS）攻撃の脆弱性につながる可能性があり、システムの安定性とセキュリティを著しく損なうものです。

具体的には、compress/flate パッケージは、DEFLATEアルゴリズム（ZIP、gzip、PNGなどで広く使われている圧縮アルゴリズム）の実装を提供しています。DEFLATEは、ハフマン符号化とLZ77アルゴリズムを組み合わせてデータを圧縮します。デコード処理中に、ハフマンツリーの探索が不正な入力によって予期せぬ状態に陥り、無限にループしてしまうケースがあったと考えられます。

この問題は、compress/gzip パッケージを介して、つまりgzip形式の不正な圧縮ファイルを解凍しようとした際に顕在化したようです。そのため、修正の検証には compress/gzip を用いたテストケースが追加されています。

前提知識の解説

DEFLATEアルゴリズム

DEFLATEは、データ圧縮のためのロスレスデータ圧縮アルゴリズムです。RFC 1951で定義されており、主に以下の2つの技術を組み合わせています。

1. LZ77アルゴリズム: 繰り返し出現するバイト列（文字列）を、以前に出現した同じバイト列への「参照」（オフセットと長さ）で置き換えることで圧縮します。これにより、冗長なデータを効率的に削減できます。
2. ハフマン符号化 (Huffman Coding): 出現頻度の高いシンボルには短いビット列を、出現頻度の低いシンボルには長いビット列を割り当てることで、データの平均ビット長を短縮します。DEFLATEでは、リテラル/長さシンボルと距離シンボルの2種類のハフマンツリーが使用されます。

ハフマン符号化とデコード

ハフマン符号化は、可変長符号化の一種です。デコード時には、ビットストリームを読み込み、ハフマンツリーを辿ってシンボルを特定します。ハフマンツリーは通常、二分木として表現され、各ノードはビット（0または1）に対応し、葉ノードが実際のシンボルを表します。

デコード処理は、入力ビットストリームからビットを読み込み、ハフマンツリーの根から始めて、読み込んだビットに応じて左右の枝を辿っていきます。葉ノードに到達すると、対応するシンボルがデコードされたと判断されます。

無限ループの発生メカニズム（推測）

このコミットで修正された無限ループは、ハフマンデコード処理中に発生したと考えられます。一般的なハフマンデコーダは、入力ビットストリームがハフマンツリーの有効なパスに対応しない場合、つまり不正なビット列が与えられた場合に、エラーを検出して処理を停止する必要があります。

しかし、このバグでは、不正な入力が与えられた際に、デコーダがハフマンツリーの探索を完了できず、かつエラーも発生させずに、ツリーの特定のノード間を無限に往復するような状態に陥った可能性があります。これは、ツリーの構造や探索ロジックに、不正な入力に対するエッジケースの考慮漏れがあったことを示唆しています。例えば、huffmanChunkBits や huffmanValueShift といった内部的なビット操作が、不正な入力によって予期せぬ値を生み出し、それが無限ループの条件を満たしてしまったなどが考えられます。

技術的詳細

このコミットの技術的詳細は、compress/flate パッケージの inflate.go ファイル内の huffSym メソッドに焦点を当てています。huffSym メソッドは、ハフマン符号化されたシンボルをデコードする役割を担っています。

DEFLATEのハフマンデコードは、効率化のために「チャンク」と呼ばれる手法を用いることがあります。これは、ハフマンツリー全体を一度に探索するのではなく、入力ビットストリームの最初の数ビット（チャンク）を使って、デコードの候補を絞り込むものです。もしチャンクでシンボルが特定できない場合、さらにビットを読み込んでツリーを深く探索します。

問題は、このチャンクベースの探索において、不正な入力が与えられた際に発生しました。元のコードでは、チャンクから得られた情報 chunk を基に、次の探索ステップを決定していました。この際、n という変数が、デコードされたビット数または次の探索に必要なビット数を示します。

修正前のコードでは、n が 0 になる可能性が考慮されていませんでした。n が 0 になるということは、ハフマンツリーの探索が進行しない、あるいは不正な状態に陥っていることを意味します。このような状況でループが継続すると、デコーダは無限に同じ状態を繰り返すことになり、結果として無限ループが発生します。

修正は、この n == 0 のケースを明示的にチェックし、その場合に CorruptInputError を発生させることで、無限ループを回避しています。これにより、不正な入力に対してデコーダが適切にエラーを返し、処理を終了するようになります。

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

src/pkg/compress/flate/inflate.go

--- a/src/pkg/compress/flate/inflate.go
+++ b/src/pkg/compress/flate/inflate.go
@@ -644,6 +644,10 @@ func (f *decompressor) huffSym(h *huffmanDecoder) (int, error) {
 		if n > huffmanChunkBits {
 			chunk = h.links[chunk>>huffmanValueShift][(f.b>>huffmanChunkBits)&h.linkMask]
 			n = uint(chunk & huffmanCountMask)
+			if n == 0 {
+				f.err = CorruptInputError(f.roffset)
+				return 0, f.err
+			}
 		}
 		if n <= f.nb {
 			f.b >>= n

src/pkg/compress/gzip/gunzip_test.go

--- a/src/pkg/compress/gzip/gunzip_test.go
+++ b/src/pkg/compress/gzip/gunzip_test.go
@@ -7,7 +7,10 @@ package gzip
 import (
 	"bytes"
 	"io"
+	"io/ioutil"
+	"os"
 	"testing"
+	"time"
 )
 
 type gunzipTest struct {
@@ -302,3 +305,31 @@ func TestDecompressor(t *testing.T) {
 		}
 	}
 }
+
+func TestIssue6550(t *testing.T) {
+	f, err := os.Open("testdata/issue6550.gz")
+	if err != nil {
+		t.Fatal(err)
+	}
+	gzip, err := NewReader(f)
+	if err != nil {
+		t.Fatalf("NewReader(testdata/issue6550.gz): %v", err)
+	}
+	defer gzip.Close()
+	done := make(chan bool, 1)
+	go func() {
+		_, err := io.Copy(ioutil.Discard, gzip)
+		if err == nil {
+			t.Errorf("Copy succeeded")
+		} else {
+			t.Logf("Copy failed (correctly): %v", err)
+		}
+		done <- true
+	}()
+	select {
+	case <-time.After(1 * time.Second):
+		t.Errorf("Copy hung")
+	case <-done:
+		// ok
+	}
+}

src/pkg/compress/gzip/testdata/issue6550.gz

バイナリファイルが新規追加されています。これは、無限ループを引き起こす不正なgzip圧縮データを含んでいます。

コアとなるコードの解説

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

huffSym メソッド内の変更は、ハフマンデコード処理の核心部分にあります。

			n = uint(chunk & huffmanCountMask)
			if n == 0 {
				f.err = CorruptInputError(f.roffset)
				return 0, f.err
			}

このコードブロックは、ハフマンツリーの探索中に n の値が 0 になった場合に、明示的にエラーを発生させるためのものです。

• chunk = h.links[chunk>>huffmanValueShift][(f.b>>huffmanChunkBits)&h.linkMask]
  • この行は、ハフマンツリーの内部的なリンク構造 h.links を使用して、現在のチャンクと入力ビット f.b に基づいて次の探索ステップ（chunk）を決定しています。huffmanValueShift と h.linkMask は、ビット操作によって適切なインデックスを計算するために使用される定数です。
• n = uint(chunk & huffmanCountMask)
  • 更新された chunk から、デコードされたビット数または次の探索に必要なビット数を示す n を抽出しています。huffmanCountMask は、chunk の下位ビットから n を取り出すためのマスクです。
• if n == 0 { ... }
  • ここが今回の修正の肝です。もし n が 0 になった場合、これはデコード処理が有効なシンボルを見つけられず、かつツリーの探索もこれ以上進められない（または不正な状態に陥っている）ことを意味します。このような状況は、不正な入力データが原因である可能性が非常に高いため、無限ループを避けるためにエラーとして処理する必要があります。
• f.err = CorruptInputError(f.roffset)
  • CorruptInputError は、入力データが破損していることを示すエラータイプです。f.roffset は、エラーが発生した入力ストリーム内のオフセットを示します。
• return 0, f.err
  • エラーを設定した後、デコードされたシンボルとして 0 を返し、エラーオブジェクトを返して huffSym メソッドの実行を終了します。これにより、デコード処理全体が停止し、無限ループが回避されます。

src/pkg/compress/gzip/gunzip_test.go の変更

TestIssue6550 関数は、この無限ループのバグを再現し、修正が正しく機能することを確認するためのテストケースです。

• f, err := os.Open("testdata/issue6550.gz")
  • 無限ループを引き起こすように特別に作成された不正なgzipファイルを読み込みます。
• gzip, err := NewReader(f)
  • compress/gzip パッケージの NewReader を使用して、gzipデコーダを作成します。
• go func() { ... }()
  • io.Copy(ioutil.Discard, gzip) を別のゴルーチンで実行しています。これは、デコード処理が無限ループに陥った場合に、メインのテストゴルーチンがブロックされないようにするためです。ioutil.Discard は、読み込んだデータを破棄する io.Writer です。
• select { case <-time.After(1 * time.Second): ... case <-done: ... }
  • この select ステートメントは、デコード処理がタイムアウトするか、または完了するのを待ちます。
  • time.After(1 * time.Second): もしデコード処理が1秒以内に完了しない場合（つまり無限ループに陥っている場合）、タイムアウトエラーを発生させます。
  • <-done: デコード処理が完了した場合（エラーで終了した場合も含む）、done チャンネルにシグナルが送られ、テストは成功と判断されます。
• if err == nil { t.Errorf("Copy succeeded") } else { t.Logf("Copy failed (correctly): %v", err) }
  • io.Copy がエラーなく成功した場合（不正なデータにもかかわらず無限ループせずに最後まで読み込めてしまった場合）はテスト失敗です。
  • エラーが発生して終了した場合（期待される動作）は、t.Logf でログを出力し、テストは成功と判断されます。

このテストケースは、不正な入力に対する堅牢性を確保するために非常に重要です。

関連リンク

• Go言語の compress/flate パッケージのドキュメント: https://pkg.go.dev/compress/flate
• Go言語の compress/gzip パッケージのドキュメント: https://pkg.go.dev/compress/gzip
• DEFLATEアルゴリズム (RFC 1951): https://www.rfc-editor.org/rfc/rfc1951

参考にした情報源リンク

• Go言語のコミット履歴 (GitHub): https://github.com/golang/go/commits/master
• Go言語のコードレビューシステム (Gerrit): https://go.googlesource.com/go/+/refs/heads/master (コミットメッセージ内の https://golang.org/cl/14441051 はGerritへのリンクです)
• ハフマン符号化に関する一般的な情報源 (例: Wikipedia)
• LZ77アルゴリズムに関する一般的な情報源 (例: Wikipedia)