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

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

このコミットは、Go言語の標準ライブラリである compress/bzip2 パッケージに対するものです。compress/bzip2 パッケージは、Bzip2圧縮形式のデータを読み書きするための機能を提供します。Bzip2は、Burrows-Wheeler変換とMove-to-Front変換、ランレングス符号化、ハフマン符号化を組み合わせたブロックソートベースの可逆データ圧縮アルゴリズムです。このパッケージは、Bzip2形式で圧縮されたストリームをデコードし、元のデータを復元する役割を担っています。

コミット

commit c12c5dba9c9d81242569f4108b707c6c16dfa066
Author: Adam Langley <agl@golang.org>
Date:   Tue Jul 15 18:44:33 2014 -0700

    compress/bzip2: fix panics on malformed input.
    
    Fixes 8363.
    
    LGTM=bradfitz
    R=bradfitz
    CC=golang-codereviews
    https://golang.org/cl/114810043

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

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

元コミット内容

compress/bzip2: fix panics on malformed input.

このコミットは、compress/bzip2 パッケージが不正な入力データを受け取った際に発生するパニック（panic）を修正することを目的としています。具体的には、Go issue 8363で報告された問題に対応しています。

変更の背景

Go言語の compress/bzip2 パッケージにおいて、不正なBzip2形式の入力データが与えられた場合に、プログラムが予期せぬパニックを起こすという問題が報告されていました（Go issue 8363）。パニックは、プログラムの実行が停止し、スタックトレースが出力されるGo言語のランタイムエラーの一種です。通常、パニックは回復不能なエラーやプログラマの論理エラーを示すものであり、堅牢なアプリケーションでは避けるべき挙動です。

この問題は、bzip2 デコンプレッサが入力ストリームの特定の構造的制約を適切に検証せずに処理を進めていたために発生しました。特に、ハフマンツリーのシンボル数、セレクタインデックスの範囲、およびセレクタインデックスの不足といった、Bzip2フォーマットの仕様に反するデータが与えられた際に、配列の範囲外アクセスなどが発生し、パニックにつながっていました。

このコミットは、これらの不正な入力に対する堅牢性を高め、パニックではなく適切なエラー（StructuralError）を返すようにすることで、ライブラリの安定性と信頼性を向上させることを目的としています。

前提知識の解説

Bzip2圧縮アルゴリズム

Bzip2は、主に以下のステップでデータを圧縮します。

  1. ブロックソート (Burrows-Wheeler Transform, BWT): 入力データを固定サイズのブロックに分割し、各ブロック内でBWTを適用します。BWTは、データを並べ替えることで、同じ文字が連続して出現する傾向を高めます。これにより、後続の圧縮ステップで高い圧縮率が得られます。
  2. Move-to-Front (MTF) 変換: BWTの出力は、同じ文字が連続する部分が多くなりますが、MTF変換はこれをさらに効率化します。MTFは、最近出現した文字を小さな数値にマッピングすることで、ランレングス符号化に適したデータに変換します。
  3. ランレングス符号化 (Run-Length Encoding, RLE): MTF変換の出力には、同じ数値が連続する部分が多く含まれます。RLEは、これらの連続する数値を「数値とその繰り返し回数」という形式で表現することで、データをさらに圧縮します。
  4. ハフマン符号化 (Huffman Coding): RLEの出力に対して、ハフマン符号化を適用します。ハフマン符号化は、出現頻度の高いシンボルには短いビット列を、出現頻度の低いシンボルには長いビット列を割り当てることで、全体のデータサイズを削減する可逆圧縮手法です。Bzip2では、複数のハフマンツリーを使用して、ブロック内のデータの特性に応じて最適なツリーを選択します。

Go言語におけるパニック (Panic)

Go言語において「パニック」は、プログラムの実行中に回復不能なエラーが発生した際に、現在のゴルーチン（goroutine）の実行を停止させるメカニズムです。パニックが発生すると、通常の制御フローは中断され、defer 関数が実行された後、プログラムはスタックトレースを出力して終了します。

パニックは、以下のような状況で発生することがあります。

  • ランタイムエラー: 配列の範囲外アクセス、nilポインタのデリファレンス、ゼロ除算など。
  • プログラマによる明示的な呼び出し: panic() 関数を呼び出すことで、意図的にパニックを発生させることができます。

パニックは、通常、プログラムの論理的な欠陥や、予期せぬ不正な状態を示します。ライブラリの文脈では、不正な入力によってパニックが発生することは、そのライブラリが堅牢でないことを意味し、呼び出し元が入力の正当性を常に保証しなければならないという負担を強いることになります。そのため、ライブラリは可能な限りパニックを避け、エラー値を返すことで、呼び出し元がエラーを適切に処理できるようにすべきです。

技術的詳細

このコミットは、src/pkg/compress/bzip2/bzip2.go ファイル内の readBlock 関数に、不正な入力データに対する複数のチェックを追加することで、パニックを防止しています。readBlock 関数は、Bzip2ストリームから単一の圧縮ブロックを読み込み、デコードする主要なロジックを含んでいます。

追加されたチェックは以下の通りです。

  1. シンボル数の検証 (numSymbols == 0): Bzip2のブロックには、少なくとも1つのEOF（End-of-File）シンボルが含まれている必要があります。readBlock 関数は、デコードされるシンボルの総数 numSymbols を計算しますが、これが0である場合、入力が不正であると判断し、StructuralError("no symbols in input") を返します。これにより、後続の処理でシンボルが存在しないことを前提とした操作が行われることによるパニックを防ぎます。

  2. ハフマンツリーのコード長デコードループの修正: 以前のコードでは、ハフマンツリーのコード長をデコードするループが for i := 0; i < numHuffmanTrees; i++ と for j := 0; j < numSymbols; j++ のように、固定のインデックスで回っていました。これが for i := range huffmanTrees と for j := range lengths に変更されました。この変更自体はパニックの直接的な修正というよりは、Goのイディオムに合わせた改善ですが、lengths スライスが numSymbols のサイズで作成されているため、numSymbols が不正な値であった場合に、lengths の範囲外アクセスを防ぐ間接的な効果も期待できます。

  3. セレクタインデックスの存在チェック (len(treeIndexes) == 0): Bzip2のブロックは、ハフマンツリーを切り替えるためのセレクタインデックスのリスト treeIndexes を含んでいます。このリストが空である場合、デコード処理中にどのハフマンツリーを使用すべきか判断できなくなり、パニックにつながる可能性があります。このチェックでは、treeIndexes が空であれば StructuralError("no tree selectors given") を返します。

  4. セレクタインデックスの範囲チェック (int(treeIndexes[0]) >= len(huffmanTrees)): treeIndexes の最初の要素（treeIndexes[0]）は、最初に選択されるハフマンツリーのインデックスを示します。このインデックスが、実際に存在するハフマンツリーの数 len(huffmanTrees) 以上である場合、存在しないツリーにアクセスしようとしてパニックが発生します。このチェックでは、インデックスが有効な範囲内にあることを確認し、範囲外であれば StructuralError("tree selector out of range") を返します。

  5. デコード中のセレクタインデックスの不足チェック (selectorIndex >= numSelectors): ブロックのデコード中に、50シンボルごとにハフマンツリーが切り替わります。この切り替えのために、selectorIndex をインクリメントして次のセレクタインデックスを使用しますが、selectorIndex が利用可能なセレクタの総数 numSelectors を超えてしまうと、treeIndexes の範囲外アクセスが発生しパニックにつながります。このチェックでは、selectorIndex が numSelectors の範囲内にあることを確認し、不足していれば StructuralError("insufficient selector indices for number of symbols") を返します。

  6. デコード中のセレクタインデックスの範囲チェック (int(treeIndexes[selectorIndex]) >= len(huffmanTrees)): 上記と同様に、デコード中に次のハフマンツリーを選択する際、treeIndexes[selectorIndex] が示すインデックスが len(huffmanTrees) の範囲外である場合、パニックが発生します。このチェックでは、このインデックスが有効な範囲内にあることを確認し、範囲外であれば StructuralError("tree selector out of range") を返します。

これらのチェックは、Bzip2の仕様に準拠しない不正な入力データが与えられた場合に、早期にエラーを検出し、パニックではなく明確なエラーを返すことで、ライブラリの堅牢性を大幅に向上させています。

また、src/pkg/compress/bzip2/bzip2_test.go には、TestOutOfRangeSelector という新しいテストケースが追加されています。このテストは、Go issue 8363で報告された特定の不正な入力データ（outOfRangeSelector バイト配列）を使用して、デコンプレッサがパニックを起こさずに適切にエラーを返すことを検証します。

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

src/pkg/compress/bzip2/bzip2.go の readBlock 関数における変更点:

--- a/src/pkg/compress/bzip2/bzip2.go
+++ b/src/pkg/compress/bzip2/bzip2.go
@@ -261,6 +261,11 @@ func (bz2 *reader) readBlock() (err error) {
 		}
 	}
 
+	if numSymbols == 0 {
+		// There must be an EOF symbol.
+		return StructuralError("no symbols in input")
+	}
+
 	// A block uses between two and six different Huffman trees.
 	numHuffmanTrees := br.ReadBits(3)
 	if numHuffmanTrees < 2 || numHuffmanTrees > 6 {
@@ -307,10 +312,10 @@ func (bz2 *reader) readBlock() (err error) {
 
 	// Now we decode the arrays of code-lengths for each tree.
 	lengths := make([]uint8, numSymbols)
-	for i := 0; i < numHuffmanTrees; i++ {
+	for i := range huffmanTrees {
 		// The code lengths are delta encoded from a 5-bit base value.
 		length := br.ReadBits(5)
-		for j := 0; j < numSymbols; j++ {
+		for j := range lengths {
 			for {
 				if !br.ReadBit() {
 					break
@@ -333,6 +338,12 @@ func (bz2 *reader) readBlock() (err error) {
 	}
 
 	selectorIndex := 1 // the next tree index to use
+	if len(treeIndexes) == 0 {
+		return StructuralError("no tree selectors given")
+	}
+	if int(treeIndexes[0]) >= len(huffmanTrees) {
+		return StructuralError("tree selector out of range")
+	}
 	currentHuffmanTree := huffmanTrees[treeIndexes[0]]
 	bufIndex := 0 // indexes bz2.buf, the output buffer.
 	// The output of the move-to-front transform is run-length encoded and
@@ -350,6 +361,12 @@ func (bz2 *reader) readBlock() (err error) {
 	decoded := 0 // counts the number of symbols decoded by the current tree.
 	for {
 		if decoded == 50 {
+			if selectorIndex >= numSelectors {
+				return StructuralError("insufficient selector indices for number of symbols")
+			}
+			if int(treeIndexes[selectorIndex]) >= len(huffmanTrees) {
+				return StructuralError("tree selector out of range")
+			}
 			currentHuffmanTree = huffmanTrees[treeIndexes[selectorIndex]]
 			selectorIndex++
 			decoded = 0

src/pkg/compress/bzip2/bzip2_test.go の変更点:

--- a/src/pkg/compress/bzip2/bzip2_test.go
+++ b/src/pkg/compress/bzip2/bzip2_test.go
@@ -208,6 +208,14 @@ func TestBufferOverrun(t *testing.T) {
 	ioutil.ReadAll(decompressor)
 }
 
+func TestOutOfRangeSelector(t *testing.T) {
+	// Tests https://code.google.com/p/go/issues/detail?id=8363.
+	buffer := bytes.NewReader(outOfRangeSelector)
+	decompressor := NewReader(buffer)
+	// This shouldn't panic.
+	ioutil.ReadAll(decompressor)
+}
+
 var bufferOverrunBase64 string = `
 QlpoNTFBWSZTWTzyiGcACMP/////////////////////////////////3/7f3///
 ////4N/fCZODak2Xo44GIHZgkGzDRbFAuwAAKoFV7T6AO6qwA6APb6s2rOoAkAAD
@@ -361,3 +369,13 @@ O0A8s/iua5oFdNZTWvbVI4FUH9sKcLiB3/fIAF+sB4n8q6L+UCfmbPcAo/crQ6b3
 HqhDBMY9J0q/jdz9GNYZ/1fbXdkUqAQKFePhtzJDRBZba27+LPQNMCcrHMq06F1T
 4QmLmkHt7LxB2pAczUO+T2O9bHEw/HWw+dYf2MoRDUw=\n `
+\n+var outOfRangeSelector = []byte{\n+\t0x42, 0x5a, 0x68, 0x39, 0x31, 0x41, 0x59, 0x26,\n+\t0x53, 0x59, 0x4e, 0xec, 0xe8, 0x36, 0x00, 0x00,\n+\t0x02, 0x51, 0x80, 0x00, 0x10, 0x40, 0x00, 0x06,\n+\t0x44, 0x90, 0x80, 0x20, 0x00, 0x31, 0x06, 0x4c,\n+\t0x41, 0x01, 0xa7, 0xa9, 0xa5, 0x80, 0xbb, 0x94,\n+\t0x31, 0x17, 0x72, 0x45, 0x38, 0x50, 0x90, 0x00,\n+\t0x00, 0x00, 0x00,\n+}\n```

## コアとなるコードの解説

このコミットの核心は、`readBlock` 関数における複数の入力検証チェックの追加です。

1.  **`if numSymbols == 0`**:
    このチェックは、Bzip2ブロックのデコードにおいて、シンボルが全く存在しないという不正な状態を検出します。Bzip2の仕様では、各ブロックには必ずEOFシンボルが含まれるため、`numSymbols` が0になることはありません。この条件が真の場合、デコーダはこれ以上処理を続行できず、`StructuralError("no symbols in input")` を返してパニックを回避します。

2.  **`for i := range huffmanTrees` と `for j := range lengths`**:
    これらの変更は、ループのイテレーションを固定の数値ではなく、スライスの実際の長さに基づいて行うように修正しています。これにより、`huffmanTrees` や `lengths` スライスが予期せぬサイズであった場合でも、範囲外アクセスによるパニックを防ぐことができます。特に、`lengths` スライスは `numSymbols` の値に基づいて作成されるため、`numSymbols` が不正な値であった場合に、この変更が堅牢性を高めます。

3.  **`if len(treeIndexes) == 0`**:
    `treeIndexes` は、デコード中に使用するハフマンツリーを切り替えるためのインデックスのリストです。このリストが空であることは、Bzip2の仕様に反する不正な入力です。このチェックにより、リストが空の場合に `StructuralError("no tree selectors given")` を返し、後続の `treeIndexes[0]` へのアクセスによるパニックを防ぎます。

4.  **`if int(treeIndexes[0]) >= len(huffmanTrees)`**:
    最初のハフマンツリーの選択時に、`treeIndexes` の最初の要素が、実際に存在するハフマンツリーの数を超えている場合、存在しないツリーにアクセスしようとしてパニックが発生します。このチェックは、この不正なインデックスを検出し、`StructuralError("tree selector out of range")` を返します。

5.  **`if selectorIndex >= numSelectors`**:
    デコード処理中に、50シンボルごとにハフマンツリーが切り替わります。この切り替えのために `selectorIndex` がインクリメントされますが、これが利用可能なセレクタの総数 `numSelectors` を超えてしまうと、`treeIndexes` の範囲外アクセスが発生します。このチェックは、セレクタインデックスが不足していることを検出し、`StructuralError("insufficient selector indices for number of symbols")` を返します。

6.  **`if int(treeIndexes[selectorIndex]) >= len(huffmanTrees)`**:
    上記と同様に、デコード中に次のハフマンツリーを選択する際、`treeIndexes[selectorIndex]` が示すインデックスが `len(huffmanTrees)` の範囲外である場合、パニックが発生します。このチェックは、この不正なインデックスを検出し、`StructuralError("tree selector out of range")` を返します。

これらの変更は、Bzip2デコーダが不正な入力データに対してより堅牢になるように設計されています。パニックを発生させる代わりに、`StructuralError` を返すことで、呼び出し元がエラーを適切に処理し、プログラム全体の安定性を向上させることができます。

追加された `TestOutOfRangeSelector` テストは、この修正が正しく機能することを確認するためのものです。特定の不正なBzip2データ（`outOfRangeSelector`）をデコードしようとした際に、パニックが発生せず、エラーが返されることを検証します。

## 関連リンク

*   GitHubコミット: [https://github.com/golang/go/commit/c12c5dba9c9d81242569f4108b707c6c16dfa066](https://github.com/golang/go/commit/c12c5dba9c9d81242569f4108b707c6c16dfa066)

## 参考にした情報源リンク

*   Bzip2 (Wikipedia): [https://ja.wikipedia.org/wiki/Bzip2](https://ja.wikipedia.org/wiki/Bzip2)
*   Go言語のpanicとrecoverについて: [https://go.dev/blog/defer-panic-and-recover](https://go.dev/blog/defer-panic-and-recover) (Go公式ブログの関連情報)
*   Go言語のBzip2パッケージのドキュメント: [https://pkg.go.dev/compress/bzip2](https://pkg.go.dev/compress/bzip2)