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

このコミットは、Goコンパイラの型チェックフェーズにおいて、スライス式における配列境界のオーバーフローを検出するための修正を導入しています。具体的には、固定長配列をスライスする際に、指定されたインデックスが配列の実際の境界を超えていないかをコンパイル時にチェックするようになります。

コミット

commit 72bf3bc1763cd8dd07c511919ca86577720fc163
Author: Ian Lance Taylor <iant@golang.org>
Date:   Tue Nov 6 11:35:58 2012 -0800

    cmd/gc: check for array bounds overflow in slice expression
    
    The test for this is test/index.go, which is not run by
    default.  That test does not currently pass even after this is
    applied, due to issue 4348.
    
    Fixes #4344.
    
    R=golang-dev, daniel.morsing, rsc
    CC=golang-dev
    https://golang.org/cl/6815085

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

https://github.com/golang/go/commit/72bf3bc1763cd8dd07c511919ca86577720fc163

元コミット内容

cmd/gc: check for array bounds overflow in slice expression

このコミットは、スライス式における配列境界のオーバーフローをチェックします。

このためのテストは test/index.go にありますが、これはデフォルトでは実行されません。この修正を適用しても、Issue 4348のため、そのテストは現在もパスしません。

Issue 4344を修正します。

レビュー担当者: golang-dev, daniel.morsing, rsc CC: golang-dev コードレビューリンク: https://golang.org/cl/6815085

変更の背景

この変更は、Go言語のコンパイラ（cmd/gc）におけるバグ修正の一環として行われました。具体的には、Go Issue 4344「cmd/gc: array bounds overflow in slice expression」で報告された問題に対処しています。

Go言語では、配列やスライスに対して a[low:high] のようなスライス式を使用して、元のデータの一部を参照する新しいスライスを作成できます。この際、low や high のインデックスが元の配列やスライスの有効な範囲内にあることが期待されます。しかし、Go 1.0.xのコンパイラには、固定長配列をスライスする際に、コンパイル時にインデックスが配列の境界を超えていることを適切に検出できないという脆弱性がありました。

例えば、[3]int{1, 2, 3} のような3要素の配列に対して a[0:4] のようにインデックス4を指定した場合、これは配列の範囲外であり、コンパイル時にエラーとして検出されるべきです。しかし、このバグにより、このような無効なスライス式がコンパイルを通過し、実行時に予期せぬ動作やパニックを引き起こす可能性がありました。

このコミットは、このようなコンパイル時の境界チェックの欠陥を修正し、より堅牢な型チェックを実現することを目的としています。

前提知識の解説

Go言語のスライスと配列

• 配列 (Array): Go言語の配列は、固定長で同じ型の要素のシーケンスです。宣言時に長さが決定され、その長さは変更できません。例: var a [3]int (3つの整数を格納できる配列)。
• スライス (Slice): スライスは、配列のセグメント（一部）を参照するデータ構造です。スライスは長さと容量を持ち、動的にサイズを変更できます（ただし、基になる配列の容量を超えない範囲で）。スライスは、Go言語で最も一般的に使用される可変長シーケンスの型です。
• スライス式: a[low:high] の形式で、配列や既存のスライスから新しいスライスを作成します。low は開始インデックス（含む）、high は終了インデックス（含まない）です。low が省略された場合は0、high が省略された場合は元の長さがデフォルト値となります。

Goコンパイラ (cmd/gc) と型チェック

• cmd/gc: Go言語の公式コンパイラの一つで、Goソースコードを機械語に変換します。Go 1.5以降はGo言語自体で書かれていますが、このコミットが作成された2012年当時はC言語で書かれていました。
• 型チェック (Type Checking): コンパイラの重要なフェーズの一つで、プログラムがGo言語の型システム規則に準拠しているかを確認します。これには、変数の型が正しいか、関数の引数が正しい型であるか、そして今回のケースのように、配列やスライスのインデックスが有効な範囲内にあるかどうかのチェックが含まれます。型チェックは、実行時エラーを未然に防ぎ、プログラムの信頼性を高めるために非常に重要です。
• src/cmd/gc/typecheck.c: このファイルは、Goコンパイラの型チェックロジックを実装しているC言語のソースファイルです。AST (Abstract Syntax Tree) を走査し、各ノード（式、文など）の型を検証します。

AST (Abstract Syntax Tree)

コンパイラは、ソースコードを直接解析するのではなく、まずソースコードを抽象構文木（AST）というツリー構造に変換します。ASTはプログラムの構造を抽象的に表現したもので、コンパイラの各フェーズ（構文解析、型チェック、最適化、コード生成など）はこのASTを操作します。

• n->left, n->right, n->right->left, n->right->right: これらはASTノードのポインタであり、スライス式 a[low:high] の場合、n はスライス式全体を表すノード、n->left はスライスされる対象（配列やスライス a）、n->right はインデックス部分を表すノード、n->right->left は low インデックス、n->right->right は high インデックスに対応します。
• OLITERAL: ASTノードの操作コード（opcode）の一つで、そのノードがリテラル値（定数）を表すことを示します。
• mpgetfix(val.u.xval): 多倍長整数を扱うための関数で、リテラル値の実際の数値を取得します。

Go Issue 4348

このコミットのメッセージで言及されているGo Issue 4348は、「cmd/gc: slice of array with constant index out of bounds」という別のバグです。これは、定数インデックスを持つ配列のスライスが境界外である場合に、コンパイラが誤ったエラーメッセージを出すか、または検出できないという問題でした。このコミットがIssue 4344を修正しても、Issue 4348が未解決であったため、関連するテストケース test/index.go が完全にパスしなかったと説明されています。

技術的詳細

このコミットの主要な目的は、Goコンパイラの型チェックフェーズにおいて、固定長配列に対するスライス操作のインデックスが、コンパイル時に配列の境界を越えていないかを厳密にチェックすることです。

変更は src/cmd/gc/typecheck.c ファイルの typecheck 関数内、特にスライス式 (OINDEX オペレーション) を処理する部分に集中しています。

以前のバージョンでは、スライスインデックスが負の値でないかどうかのチェックは行われていましたが、インデックスが配列の最大長を超えていないかどうかのチェックは不十分でした。

このコミットでは、以下の主要な変更が導入されています。

1. スライス対象の型情報の早期取得と利用:

   • スライス式の左辺 (n->left) の型情報を表す l 変数が導入され、その型 (t) が文字列、ポインタ、固定長配列、またはスライスであるかに基づいて、スライス操作のタイプ (OSLICESTR, OSLICEARR など) が早期に決定されます。
   • 特に重要なのは、スライス対象が固定長配列である場合 (isptr[t->etype] && isfixedarray(t->type)) に、その配列の型情報 (tp = t->type) が取得され、tp->bound に配列の要素数（境界）が格納される点です。この tp 変数が、後続の境界チェックで利用されます。

2. 配列境界オーバーフローのチェックの追加:

   • スライス式の low インデックス (n->right->left) と high インデックス (n->right->right) がリテラル値 (OLITERAL) である場合に、新しい境界チェックが追加されました。

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

     else if(tp != nil && tp->bound > 0 && mpgetfix(n->right->left->val.u.xval) > tp->bound)
         yyerror("invalid slice index %N (out of bounds for %d-element array)", n->right->left, tp->bound);
     

     この条件は、以下の全てが真である場合にエラーを報告します。

     • tp != nil: スライス対象が固定長配列である（tp が設定されている）。
     • tp->bound > 0: 固定長配列のサイズが0より大きい（有効な配列である）。
     • mpgetfix(n->right->left->val.u.xval) > tp->bound: スライスインデックスの数値が、基になる配列の要素数（境界）を超えている。

   • このチェックは low インデックスと high インデックスの両方に適用されます。これにより、例えば [3]int{}[0:4] のような high インデックスが配列の境界を超えるケースや、[3]int{}[4:5] のような low インデックスが境界を超えるケースもコンパイル時に検出できるようになります。

これらの変更により、Goコンパイラは、固定長配列に対するスライス式において、コンパイル時にインデックスが配列の有効な範囲内にあることをより厳密に検証し、無効なスライス操作を早期にエラーとして報告できるようになりました。

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

変更は src/cmd/gc/typecheck.c ファイルにあります。

--- a/src/cmd/gc/typecheck.c
+++ b/src/cmd/gc/typecheck.c
@@ -905,7 +905,8 @@ reswitch:
  		defaultlit(&n->left, T);
  		defaultlit(&n->right->left, T);
  		defaultlit(&n->right->right, T);\n-\t\tif(isfixedarray(n->left->type)) {\n+\t\tl = n->left;\n+\t\tif(isfixedarray(l->type)) {\
  		\tif(!islvalue(n->left)) {\
  		\t\tyyerror("invalid operation %N (slice of unaddressable value)", n);\
  		\t\tgoto error;\
@@ -913,6 +914,26 @@ reswitch:
  		\tn->left = nod(OADDR, n->left, N);\
  		\tn->left->implicit = 1;\
  		\ttypecheck(&n->left, Erv);\
+\t\t\tl = n->left;\
+\t\t}\
+\t\tif((t = l->type) == T)\
+\t\t\tgoto error;\
+\t\ttp = nil;\
+\t\tif(istype(t, TSTRING)) {\
+\t\t\tn->type = t;\
+\t\t\tn->op = OSLICESTR;\
+\t\t} else if(isptr[t->etype] && isfixedarray(t->type)) {\
+\t\t\ttp = t->type;\
+\t\t\tn->type = typ(TARRAY);\
+\t\t\tn->type->type = tp->type;\
+\t\t\tn->type->bound = -1;\
+\t\t\tdowidth(n->type);\
+\t\t\tn->op = OSLICEARR;\
+\t\t} else if(isslice(t)) {\
+\t\t\tn->type = t;\
+\t\t} else {\
+\t\t\tyyerror("cannot slice %N (type %T)", l, t);\
+\t\t\tgoto error;\
  		}\
  		if(n->right->left != N) {\
  		\tif((t = n->right->left->type) == T)\
@@ -921,8 +942,12 @@ reswitch:
  		\t\tyyerror("invalid slice index %N (type %T)", n->right->left, t);\
  		\t\tgoto error;\
  		\t}\
-\t\t\tif(n->right->left->op == OLITERAL && mpgetfix(n->right->left->val.u.xval) < 0)\n-\t\t\t\tyyerror("invalid slice index %N (index must be non-negative)", n->right->left);\
+\t\t\tif(n->right->left->op == OLITERAL) {\
+\t\t\t\tif(mpgetfix(n->right->left->val.u.xval) < 0)\
+\t\t\t\t\tyyerror("invalid slice index %N (index must be non-negative)", n->right->left);\
+\t\t\t\telse if(tp != nil && tp->bound > 0 && mpgetfix(n->right->left->val.u.xval) > tp->bound)\
+\t\t\t\t\tyyerror("invalid slice index %N (out of bounds for %d-element array)", n->right->left, tp->bound);\
+\t\t\t}\
  		}\
  		if(n->right->right != N) {\
  		\tif((t = n->right->right->type) == T)\
@@ -931,31 +956,14 @@ reswitch:
  		\t\tyyerror("invalid slice index %N (type %T)", n->right->right, t);\
  		\t\tgoto error;\
  		\t}\
-\t\t\tif(n->right->right->op == OLITERAL && mpgetfix(n->right->right->val.u.xval) < 0)\n-\t\t\t\tyyerror("invalid slice index %N (index must be non-negative)", n->right->right);\
-\t\t}\
-\t\tl = n->left;\
-\t\tif((t = l->type) == T)\n-\t\t\tgoto error;\
-\t\t\tif(istype(t, TSTRING)) {\
-\t\t\t\tn->type = t;\
-\t\t\t\tn->op = OSLICESTR;\
-\t\t\t\tgoto ret;\
-\t\t}\
-\t\tif(isptr[t->etype] && isfixedarray(t->type)) {\
-\t\t\t\tn->type = typ(TARRAY);\
-\t\t\t\tn->type->type = t->type->type;\
-\t\t\t\tn->type->bound = -1;\
-\t\t\t\tdowidth(n->type);\
-\t\t\t\tn->op = OSLICEARR;\
-\t\t\t\tgoto ret;\
-\t\t}\
-\t\tif(isslice(t)) {\
-\t\t\t\tn->type = t;\
-\t\t\t\tgoto ret;\
+\t\t\tif(n->right->right->op == OLITERAL) {\
+\t\t\t\tif(mpgetfix(n->right->right->val.u.xval) < 0)\
+\t\t\t\t\tyyerror("invalid slice index %N (index must be non-negative)", n->right->right);\
+\t\t\t\telse if(tp != nil && tp->bound > 0 && mpgetfix(n->right->right->val.u.xval) > tp->bound)\
+\t\t\t\t\tyyerror("invalid slice index %N (out of bounds for %d-element array)", n->right->right, tp->bound);\
+\t\t\t}\
  		}\n-\t\tyyerror("cannot slice %N (type %T)", l, t);\n-\t\tgoto error;\
+\t\tgoto ret;\
  \n  	/*\
  	 * call and call like

コアとなるコードの解説

このコミットの核となる変更は、src/cmd/gc/typecheck.c 内の typecheck 関数におけるスライス式の処理ロジックの再構築と、新しい境界チェックの追加です。

1. スライス対象の正規化と型情報の取得:

   • l = n->left; という行が追加され、スライスされる対象のASTノードが l という変数に格納されます。これにより、コードの可読性が向上し、一貫した参照が可能になります。
   • 以前はスライスインデックスのチェック後にスライス式の型決定ロジックが来ていましたが、新しいコードでは、スライス対象 l の型 (t) に基づいて、スライス式の最終的な型 (n->type) と操作 (n->op) を決定するブロックが、インデックスチェックの前に移動されました。
   • このブロック内で、スライス対象が固定長配列である場合 (isptr[t->etype] && isfixedarray(t->type))、その配列の型情報が tp = t->type; として tp 変数に格納されます。この tp は、基になる配列の要素数（tp->bound）を保持しており、これが新しい境界チェックの基準となります。

2. 新しい境界チェックの導入:

   • n->right->left (lowインデックス) と n->right->right (highインデックス) の両方に対して、リテラル値 (OLITERAL) である場合のチェックが強化されました。
   • 既存の「インデックスが負でないか」というチェック (mpgetfix(...) < 0) に加えて、以下の新しい条件が追加されました。

     else if(tp != nil && tp->bound > 0 && mpgetfix(n->right->left->val.u.xval) > tp->bound)
         yyerror("invalid slice index %N (out of bounds for %d-element array)", n->right->left, tp->bound);
     

     この条件は、以下の論理積で構成されています。
     • tp != nil: スライス対象が固定長配列であり、その型情報が tp に正しく設定されていることを確認します。
     • tp->bound > 0: 基になる配列が有効なサイズを持っていることを確認します（0要素の配列でないこと）。
     • mpgetfix(n->right->left->val.u.xval) > tp->bound: ここが最も重要な部分で、スライスインデックスの数値が、基になる固定長配列の要素数 (tp->bound) を超えているかどうかをチェックします。もし超えていれば、yyerror 関数を呼び出してコンパイルエラーを報告します。エラーメッセージには、無効なインデックスと、配列の要素数が含まれます。

これらの変更により、コンパイラは固定長配列に対するスライス操作のインデックスが、コンパイル時に配列の実際の境界を超えていないかを正確に判断し、開発者に早期にフィードバックできるようになりました。これにより、実行時パニックのリスクが減少し、Goプログラムの堅牢性が向上します。

関連リンク

• Go Issue 4344: https://github.com/golang/go/issues/4344
• Go Issue 4348: https://github.com/golang/go/issues/4348
• Go Code Review 6815085: https://golang.org/cl/6815085

参考にした情報源リンク

• Go言語の公式ドキュメント (スライスと配列): https://go.dev/blog/slices-intro (スライスの紹介)
• Go言語のコンパイラに関する情報 (cmd/gc): https://go.dev/doc/articles/go1.5 (Go 1.5のコンパイラ変更に関する記事など)
• 抽象構文木 (AST) の概念: 一般的なコンパイラ理論の資料
• Go言語のソースコード (特に src/cmd/gc/ ディレクトリ): https://github.com/golang/go
• yyerror 関数: コンパイラにおけるエラー報告メカニズムの一部。
• mpgetfix: Goコンパイラ内部で多倍長整数を扱うための関数。
• isfixedarray, istype, isslice: Goコンパイラ内部で型を判別するためのヘルパー関数。
• TSTRING, TARRAY: Goコンパイラ内部で型を表す定数。
• OLITERAL, OINDEX, OSLICESTR, OSLICEARR: Goコンパイラ内部でASTノードの操作を表す定数。