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

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

このコミットは、Go言語の標準ライブラリ compress/flate パッケージにおける、Deflate圧縮処理中の境界外アクセス（out of bounds error）バグを修正するものです。具体的には、ハッシュテーブルへのインデックス挿入処理において、d.index が d.maxInsertIndex を超える場合に発生する可能性のある不正なメモリアクセスを防ぎます。この修正により、Deflate圧縮の安定性と信頼性が向上します。

コミット

commit b1ae728d19b0fdc6576823dbe682d453d8f59e01
Author: Ivan Krasin <krasin@golang.org>
Date:   Mon Dec 12 18:25:32 2011 -0500

    compress/flate: fix out of bounds error
    
    Fixes #2508.
    
    R=rsc, krasin
    CC=golang-dev
    https://golang.org/cl/5449115

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

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

元コミット内容

compress/flate: fix out of bounds error

Fixes #2508.

R=rsc, krasin
CC=golang-dev
https://golang.org/cl/5449115

変更の背景

この変更は、Go言語のIssue 2508「compress/flate: out of bounds error」を修正するために行われました。このバグは、compress/flate パッケージのDeflateエンコーダが、特定の条件下で d.window スライスに対して境界外アクセスを行う可能性があるというものでした。

具体的には、Deflateアルゴリズムにおいて、非常に長い一致（マッチ）が見つかった場合、その一致の長さ分だけ d.index を進めます。その後、次のハッシュ値を計算するために d.window[d.index] と d.window[d.index+1] にアクセスしようとします。しかし、d.index が d.maxInsertIndex を超えてしまうと、d.window の有効な範囲外にアクセスしようとしてしまい、結果としてパニック（runtime error: index out of range）が発生していました。

この問題は、特に大量のデータや特定のパターンを持つデータを圧縮しようとした際に顕在化し、プログラムのクラッシュを引き起こす可能性がありました。そのため、Deflate圧縮の堅牢性を確保するために、この境界外アクセスを防止する修正が必要とされました。

前提知識の解説

compress/flate パッケージ

compress/flate はGo言語の標準ライブラリの一部で、Deflate圧縮アルゴリズムの実装を提供します。Deflateは、LZ77アルゴリズムとハフマン符号化を組み合わせたロスレスデータ圧縮アルゴリズムであり、ZIP、gzip、PNGなどの多くのファイル形式やプロトコルで広く使用されています。

Deflateアルゴリズムの概要

Deflateアルゴリズムは、主に以下の2つのステップで構成されます。

  1. LZ77ベースの圧縮: 入力データ内で繰り返されるバイトシーケンス（文字列）を検出し、それらを「長さ-距離ペア」（length-distance pair）に置き換えます。
    • 長さ（Length）: 繰り返されるシーケンスの長さ。
    • 距離（Distance）: 以前に出現した同じシーケンスが、現在の位置からどれだけ前に存在するかを示すオフセット。 このプロセスでは、効率的な検索のためにハッシュテーブルや辞書（window）が使用されます。
  2. ハフマン符号化: LZ77ステップで生成されたリテラルバイト（圧縮されなかったバイト）と長さ-距離ペアを、可変長ビットコードに変換してさらに圧縮します。出現頻度の高いシンボルには短いコードを割り当て、出現頻度の低いシンボルには長いコードを割り当てることで、全体のデータサイズを削減します。

ハッシュテーブル（または辞書/ウィンドウ）

Deflate圧縮では、過去のデータ（ウィンドウ）を保持し、その中で現在の入力データと一致するパターンを検索します。この検索を高速化するために、ハッシュテーブルが利用されます。ハッシュテーブルは、データの短いシーケンス（通常は2バイトまたは3バイト）をハッシュ値にマッピングし、そのハッシュ値に対応する位置のリストを保持します。これにより、特定のシーケンスが過去のどこに出現したかを効率的に見つけることができます。

d.window は、Deflateエンコーダが過去のデータを保持するバイトスライス（または配列）です。d.index は、現在処理している d.window 内のインデックスを示します。

境界外アクセス（Out of Bounds Error）

プログラミングにおいて、配列やスライスなどのデータ構造にアクセスする際に、そのデータ構造の有効なインデックス範囲外のメモリ位置にアクセスしようとすることを「境界外アクセス」と呼びます。Go言語では、スライスや配列の境界外アクセスはランタイムパニック（runtime error: index out of range）を引き起こし、プログラムが異常終了します。これは、メモリ破壊やセキュリティ脆弱性につながる可能性があるため、避けるべき重要なエラーです。

Go言語のスライスとインデックス

Go言語のスライスは、配列のセグメントを参照するデータ構造です。スライスは、内部的にポインタ、長さ、容量の3つの要素を持ちます。スライス要素へのアクセスは slice[index] の形式で行われ、index は 0 から len(slice)-1 の範囲でなければなりません。この範囲外のインデックスにアクセスしようとすると、Goランタイムがこれを検出し、パニックを発生させます。

技術的詳細

このバグは、compress/flate パッケージの deflate.go ファイル内の deflate 構造体の deflate メソッド（または関連する圧縮ループ）で発生していました。

Deflateアルゴリズムでは、長い一致が見つかった場合、その一致の長さ分だけ d.index を進めます。これは、既に圧縮された部分をスキップし、次の未圧縮データから処理を再開するためです。

// For matches this long, we don't bother inserting each individual
// item into the table.
d.index += d.length

この行の直後、次のハッシュ値を計算するために、d.window スライスから2バイトを読み取ろうとします。

d.hash = (int(d.window[d.index])<<hashShift + int(d.window[d.index+1]))

問題は、d.index が d.length だけ増加した結果、d.window の末尾近く、特に d.maxInsertIndex を超える位置に到達した場合に発生しました。d.maxInsertIndex は、ハッシュテーブルに新しいエントリを挿入できる d.window 内の最大インデックスを示します。このインデックスを超えて d.window[d.index+1] にアクセスしようとすると、d.window の有効な範囲外にアクセスすることになり、境界外エラーが発生していました。

修正は、このハッシュ値の計算を行う前に、d.index が d.maxInsertIndex の範囲内にあるかどうかを確認する条件を追加することです。

if d.index < d.maxInsertIndex {
    d.hash = (int(d.window[d.index])<<hashShift + int(d.window[d.index+1]))
}

この条件により、d.index が d.maxInsertIndex 以上である場合（つまり、ハッシュテーブルにこれ以上エントリを挿入する必要がない、または挿入できない位置にいる場合）、ハッシュ値の計算とそれに伴う d.window へのアクセスをスキップします。これにより、境界外アクセスが防止され、プログラムの安定性が確保されます。

テストケース TestRegression2508 は、このバグを再現するために設計されました。大量のゼロバイト（131072バイト）をDeflateライターに書き込むことで、非常に長い一致が頻繁に発生し、d.index が急速に増加して境界外アクセスを引き起こす状況をシミュレートしています。このテストがパニックせずに正常に完了することで、修正が正しく適用されたことを確認できます。

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

--- a/src/pkg/compress/flate/deflate.go
+++ b/src/pkg/compress/flate/deflate.go
@@ -319,7 +319,9 @@ Loop:
 				// For matches this long, we don't bother inserting each individual
 				// item into the table.
 				d.index += d.length
-				d.hash = (int(d.window[d.index])<<hashShift + int(d.window[d.index+1]))
+				if d.index < d.maxInsertIndex {
+					d.hash = (int(d.window[d.index])<<hashShift + int(d.window[d.index+1]))
+				}
 			}
 			if d.ti == maxFlateBlockTokens {
 				// The block includes the current character
--- a/src/pkg/compress/flate/deflate_test.go
+++ b/src/pkg/compress/flate/deflate_test.go
@@ -318,3 +318,15 @@ func TestWriterDict(t *testing.T) {
 		t.Fatalf("writer wrote %q want %q", b1.Bytes(), b.Bytes())
 	}
 }
+
+// See http://code.google.com/p/go/issues/detail?id=2508
+func TestRegression2508(t *testing.T) {
+	w := NewWriter(ioutil.Discard, 1)
+	buf := make([]byte, 1024)
+	for i := 0; i < 131072; i++ {
+		if _, err := w.Write(buf); err != nil {
+			t.Fatalf("writer failed: %v", err)
+		}
+	}
+	w.Close()
+}

コアとなるコードの解説

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

変更の中心は deflate.go ファイル内の Loop ラベルが付いた圧縮処理ループ内です。

元のコード:

d.index += d.length
d.hash = (int(d.window[d.index])<<hashShift + int(d.window[d.index+1]))

この部分では、非常に長い一致が見つかった後、d.index を一致の長さ分だけ進め、その直後に次のハッシュ値を計算するために d.window[d.index] と d.window[d.index+1] にアクセスしていました。

修正後のコード:

d.index += d.length
if d.index < d.maxInsertIndex {
    d.hash = (int(d.window[d.index])<<hashShift + int(d.window[d.index+1]))
}

追加された if d.index < d.maxInsertIndex 条件が重要です。

  • d.maxInsertIndex は、ハッシュテーブルに新しいエントリを挿入できる d.window 内の最大インデックスを示します。
  • この条件は、d.index が d.window の有効な範囲内であり、かつハッシュテーブルに新しいエントリを挿入する意味がある場合にのみ、ハッシュ値の計算（d.hash = ... の行）を実行するようにします。
  • d.index が d.maxInsertIndex 以上になった場合、それは d.window の末尾に近づいているか、既にハッシュテーブルへの挿入が不要な領域にいることを意味します。この場合、d.window[d.index+1] へのアクセスは境界外エラーを引き起こす可能性があるため、この条件によって安全にスキップされます。

この変更により、d.window の範囲外へのアクセスが防止され、compress/flate パッケージの安定性が向上しました。

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

新しいテスト関数 TestRegression2508 が追加されました。

// See http://code.google.com/p/go/issues/detail?id=2508
func TestRegression2508(t *testing.T) {
	w := NewWriter(ioutil.Discard, 1)
	buf := make([]byte, 1024)
	for i := 0; i < 131072; i++ {
		if _, err := w.Write(buf); err != nil {
			t.Fatalf("writer failed: %v", err)
		}
	}
	w.Close()
}
  • w := NewWriter(ioutil.Discard, 1): Deflateライターを作成します。出力は ioutil.Discard に送られるため、実際の圧縮データは破棄されます。圧縮レベル 1 は最速の圧縮レベルであり、このバグを再現しやすい条件を作り出します。
  • buf := make([]byte, 1024): 1KBのゼロバイトスライスを作成します。
  • for i := 0; i < 131072; i++ { ... }: このループは、1KBのゼロバイトスライスを131072回書き込みます。これにより、合計で約128MBのデータがDeflateライターに供給されます。
  • 大量の同じバイトシーケンス（ゼロバイト）を書き込むことで、Deflateアルゴリズムは非常に長い一致を頻繁に検出します。これにより、d.index が急速に増加し、修正前のコードでは境界外アクセスが発生する可能性のある状況が意図的に作り出されます。
  • if _, err := w.Write(buf); err != nil { ... }: 書き込み中にエラーが発生した場合、テストは失敗します。修正が正しく適用されていれば、このテストはパニックせずに正常に完了するはずです。
  • w.Close(): ライターを閉じ、残りのバッファをフラッシュします。

このテストケースは、Issue 2508で報告された特定のシナリオを再現し、修正がその問題を効果的に解決したことを検証するために不可欠です。

関連リンク

参考にした情報源リンク