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

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

このコミットは、Go言語の標準ライブラリ compress/flate パッケージにおける、不正な入力データによって引き起こされる2つのパニック（ランタイムエラー）を修正するものです。具体的には、ハフマンデコーダの初期化処理において、提供されたビット列が不正な場合に発生する配列の範囲外アクセスを防ぐための変更が加えられています。

コミット

commit df1eeeba4a991a10f6b8e992d7d1b6ac87c23f7b
Author: Pieter Droogendijk <pieter@binky.org.uk>
Date:   Thu Aug 1 15:20:01 2013 -0700

    compress/flate: Fixed two panics on bad data
    
    I used just enough of the data provided by Matt in Issue 5915 to trigger
    issue 5915. As luck would have it, using slightly less of it triggered
    issue 5962.
    
    Fixes #5915.
    Fixes #5962.
    
    R=golang-dev, bradfitz
    CC=golang-dev
    https://golang.org/cl/12288043

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

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

元コミット内容

compress/flate: Fixed two panics on bad data

このコミットは、不正なデータが与えられた際に発生する2つのパニックを修正します。 Issue 5915でMattによって提供されたデータの一部を使用することで、Issue 5915がトリガーされました。偶然にも、そのデータの一部を少し減らしたところ、Issue 5962がトリガーされました。 これにより、Issue #5915 と Issue #5962 が修正されます。

変更の背景

この変更は、Go言語の compress/flate パッケージが、DEFLATE圧縮ストリームの不正なヘッダー情報やメタデータ（特にハフマン符号のビット長情報）を処理する際に、パニックを引き起こす可能性があった問題に対処するために行われました。

DEFLATE形式では、圧縮されたデータブロックの前に、そのブロックで使用されるハフマン符号の構造を定義するメタデータが含まれます。このメタデータには、各シンボルに対応するビット長の情報が含まれており、デコーダはこの情報に基づいてハフマンツリー（またはそれに相当するルックアップテーブル）を構築します。

報告されたIssue #5915とIssue #5962は、このハフマン符号のビット長情報が不正であったり、予期せぬ値を含んでいたりした場合に、huffmanDecoder の初期化ロジックが配列の範囲外アクセス（out-of-bounds access）を引き起こし、結果としてプログラムがパニックに陥るというものでした。このようなパニックは、悪意のある、または破損した圧縮データが入力された場合に、サービス拒否（DoS）攻撃やプログラムの異常終了につながる可能性があるため、セキュリティと堅牢性の観点から修正が必須でした。

コミットメッセージにあるように、Mattが提供した特定の不正データがIssue 5915を再現させ、そのデータをわずかに変更したものがIssue 5962を再現させたことから、これらの問題が密接に関連しており、ハフマンデコーダの初期化ロジックにおける類似の脆弱性を示唆していました。

前提知識の解説

DEFLATE圧縮アルゴリズム

DEFLATEは、LZ77アルゴリズムとハフマン符号化を組み合わせた可逆圧縮アルゴリズムです。Zlib、gzip、PNGなどの多くの一般的な圧縮形式で利用されています。

  • LZ77 (Lempel-Ziv 1977): 繰り返し出現するバイト列（シーケンス）を、以前に出現した同じシーケンスへの「参照」（オフセットと長さ）で置き換えることでデータを圧縮します。
  • ハフマン符号化 (Huffman Coding): LZ77によって生成されたリテラルバイト（非参照データ）と参照（オフセットと長さ）を、出現頻度に基づいて可変長のビット列に符号化します。出現頻度の高いシンボルには短いビット列を、低いシンボルには長いビット列を割り当てることで、全体のデータ量を削減します。

ハフマンデコーダの役割

DEFLATEのデコードプロセスにおいて、ハフマンデコーダは非常に重要な役割を担います。圧縮ストリームから読み込んだビット列を、ハフマンツリー（またはルックアップテーブル）を使って元のシンボル（リテラルバイト、参照の長さ、参照のオフセット）に変換します。

huffmanDecoder.init メソッド

このメソッドは、ハフマンデコーダが実際にデコードを行う前に、ハフマンツリーを構築するための内部テーブルを初期化する役割を担っています。入力として bits []int を受け取ります。この bits スライスは、各シンボルに対応するハフマン符号のビット長（例: シンボルAは3ビット、シンボルBは5ビットなど）を定義するものです。

ハフマン符号の仕様では、ビット長は特定の制約（例: 最大ビット長、各ビット長を持つシンボルの数など）を満たす必要があります。もし入力された bits データがこれらの制約を満たさない場合、または内部テーブルのサイズ計算やインデックスアクセスが不適切である場合、パニックが発生する可能性があります。

パニック (Panic)

Go言語におけるパニックは、プログラムの通常の実行フローを停止させるランタイムエラーです。これは通常、回復不可能なエラー（例: nilポインタのデリファレンス、配列の範囲外アクセス、ゼロ除算など）が発生した場合に引き起こされます。本件では、不正な入力データが原因で、内部配列へのアクセスが不正なインデックスで行われ、パニックが発生していました。

技術的詳細

このコミットは、compress/flate パッケージ内の inflate.go ファイルにある huffmanDecoder 構造体の init メソッドに焦点を当てています。このメソッドは、DEFLATEストリームから読み取られたハフマン符号のビット長情報に基づいて、デコード用のルックアップテーブルを構築します。

問題は、不正な bits データが init メソッドに渡された場合に、内部の h.links スライスや h.chunks スライスへのアクセスが範囲外となり、パニックを引き起こす可能性があった点です。

具体的には、以下の2つの箇所で修正が行われました。

  1. h.links スライスの make 呼び出し前のチェック: huffmanDecoder.init メソッド内で、h.links スライスを make で初期化する前に、link 変数の値が huffmanNumChunks を超えていないかどうかのチェックが追加されました。 link は、ハフマンツリーの構築中に計算されるオフセット値であり、これが huffmanNumChunks（内部テーブルのチャンク数）よりも大きい場合、make([][]uint32, huffmanNumChunks-link) の計算結果が負になり、パニックを引き起こす可能性がありました。この修正により、不正な link 値が検出された場合は即座に false を返して初期化を失敗させることで、パニックを回避します。

  2. h.links スライスへのアクセス前のインデックスチェック: huffmanDecoder.init メソッドの別の箇所で、h.links スライスから linktab を取得する際に、計算されたインデックス value が h.links スライスの有効な範囲内にあるかどうかのチェックが追加されました。 以前のコードでは、h.links[h.chunks[reverse&(huffmanNumChunks-1)]>>huffmanValueShift] のように直接アクセスしていましたが、h.chunks から取得した値がシフトされた結果の value が h.links の長さを超える可能性がありました。この修正により、if value >= uint32(len(h.links)) { return false } というチェックが追加され、不正なインデックスアクセスを防ぎ、初期化を安全に失敗させます。

これらの変更は、ハフマンデコーダの初期化ロジックにおける堅牢性を高め、不正な入力データに対する耐性を向上させるものです。これにより、GoプログラムがDEFLATE圧縮データを処理する際に、予期せぬパニックによってクラッシュするリスクが低減されます。

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

src/pkg/compress/flate/flate_test.go

--- a/src/pkg/compress/flate/flate_test.go
+++ b/src/pkg/compress/flate/flate_test.go
@@ -24,3 +24,26 @@ func TestUncompressedSource(t *testing.T) {
 		t.Errorf("output[0] = %x, want 0x11", output[0])
 	}
 }
+
+// The following test should not panic.
+func TestIssue5915(t *testing.T) {
+	bits := []int{4, 0, 0, 6, 4, 3, 2, 3, 3, 4, 4, 5, 0, 0, 0, 0, 5, 5, 6,
+		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 8, 6, 0, 11, 0, 8, 0, 6, 6, 10, 8}
+	h := new(huffmanDecoder)
+	ok := h.init(bits)
+	if ok == true {
+		t.Fatalf("Given sequence of bits is bad, and should not succeed.")
+	}
+}
+
+// The following test should not panic.
+func TestIssue5962(t *testing.T) {
+	bits := []int{4, 0, 0, 6, 4, 3, 2, 3, 3, 4, 4, 5, 0, 0, 0, 0,
+		5, 5, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11}
+	h := new(huffmanDecoder)
+	ok := h.init(bits)
+	if ok == true {
+		t.Fatalf("Given sequence of bits is bad, and should not succeed.")
+	}
+}

src/pkg/compress/flate/inflate.go

--- a/src/pkg/compress/flate/inflate.go
+++ b/src/pkg/compress/flate/inflate.go
@@ -125,6 +125,9 @@ func (h *huffmanDecoder) init(bits []int) bool {
 		if i == huffmanChunkBits+1 {
 			// create link tables
 			link := code >> 1
+			if huffmanNumChunks < link {
+				return false
+			}
 			h.links = make([][]uint32, huffmanNumChunks-link)
 			for j := uint(link); j < huffmanNumChunks; j++ {
 				reverse := int(reverseByte[j>>8]) | int(reverseByte[j&0xff])<<8
@@ -154,7 +157,11 @@ func (h *huffmanDecoder) init(bits []int) bool {
 			h.chunks[off] = chunk
 		} else {
-			linktab := h.links[h.chunks[reverse&(huffmanNumChunks-1)]>>huffmanValueShift]
+			value := h.chunks[reverse&(huffmanNumChunks-1)] >> huffmanValueShift
+			if value >= uint32(len(h.links)) {
+				return false
+			}
+			linktab := h.links[value]
 			reverse >>= huffmanChunkBits
 			for off := reverse; off < numLinks; off += 1 << uint(n-huffmanChunkBits) {
 				linktab[off] = chunk

コアとなるコードの解説

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

このファイルには、TestIssue5915 と TestIssue5962 という2つの新しいテスト関数が追加されています。これらのテストは、それぞれ特定の不正な bits シーケンス（ハフマン符号のビット長情報）を huffmanDecoder.init メソッドに渡します。

  • bits スライスは、ハフマン符号のビット長を表す整数値の配列です。
  • h := new(huffmanDecoder) で新しいデコーダインスタンスを作成します。
  • ok := h.init(bits) でデコーダの初期化を試みます。
  • テストの目的は、これらの不正な bits シーケンスがパニックを引き起こさず、かつ h.init メソッドが false を返す（初期化が失敗したことを示す）ことを確認することです。if ok == true の条件が真になった場合、つまり初期化が成功してしまった場合は t.Fatalf でテストを失敗させます。これは、与えられたビットシーケンスが不正であるため、初期化が成功してはならないという意図に基づいています。

これらのテストは、修正が正しく機能し、以前パニックを引き起こした特定の不正データパターンが安全に処理されることを保証するためのものです。

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

このファイルには、huffmanDecoder.init メソッド内の2つの重要な変更が含まれています。

  1. h.links スライス作成前の境界チェック:

    			link := code >> 1
			if huffmanNumChunks < link {
				return false
			}
			h.links = make([][]uint32, huffmanNumChunks-link)

    huffmanDecoder.init メソッドのこの部分は、ハフマンデコーダの内部ルックアップテーブルの一部である h.links スライスを初期化しています。link 変数は、ハフマンツリーの構築中に計算されるオフセット値です。 以前のコードでは、link の値が huffmanNumChunks（内部テーブルのチャンク数）よりも大きくなる可能性が考慮されていませんでした。もし link が huffmanNumChunks を超えると、huffmanNumChunks-link の結果が負になり、make 関数に負のサイズが渡されることでパニックが発生していました。 追加された if huffmanNumChunks < link { return false } という行は、この潜在的なパニックを防ぎます。link が不正に大きい場合は、即座に false を返して初期化を中止し、安全にエラーを処理します。

  2. h.links スライスアクセス前のインデックス境界チェック:

    		} else {
			value := h.chunks[reverse&(huffmanNumChunks-1)] >> huffmanValueShift
			if value >= uint32(len(h.links)) {
				return false
			}
			linktab := h.links[value]

    このコードブロックは、ハフマンデコーダがルックアップテーブルを構築する際に、h.links スライスから特定の linktab を取得する部分です。 以前のコードでは、h.links[h.chunks[reverse&(huffmanNumChunks-1)]>>huffmanValueShift] のように、h.chunks から取得した値を直接インデックスとして使用していました。しかし、h.chunks から取得した値がシフトされた結果の value が、h.links スライスの実際の長さ len(h.links) を超える可能性がありました。このような場合、配列の範囲外アクセスが発生し、パニックを引き起こしていました。 追加された if value >= uint32(len(h.links)) { return false } という行は、この問題を解決します。value が h.links の有効なインデックス範囲外である場合、初期化を中止し false を返すことで、パニックを回避します。

これらの変更は、不正な入力データがハフマンデコーダの内部状態を破壊し、パニックを引き起こすことを防ぐための防御的なプログラミングの例です。これにより、compress/flate パッケージの堅牢性が大幅に向上しました。

関連リンク

参考にした情報源リンク