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

本コミットは、GoランタイムがLinux ARM環境において、プロセスの補助ベクトル（auxiliary vector, auxv）から乱数シード、ハードウェア機能、プラットフォーム情報を取得するように変更するものです。特に、ハッシュテーブルの初期化に使用されるプロセスごとの乱数シードの取得に焦点を当てています。

コミット

commit a642ca49309b129e77ba15a066fbf8e7c4b69b79
Author: Shenghou Ma <minux.ma@gmail.com>
Date:   Sat May 5 01:59:14 2012 +0800

    runtime: get per-process random number from auxv for hash table
    Decode AT_RANDOM, AT_HWCAP, and AT_PLATFORM.
    This CL only make use of AT_RANDOM, but future CLs will make use of the others.
    
    R=dave, rsc
    CC=golang-dev
    https://golang.org/cl/5978051

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

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

元コミット内容

runtime: get per-process random number from auxv for hash table
Decode AT_RANDOM, AT_HWCAP, and AT_PLATFORM.
This CL only make use of AT_RANDOM, but future CLs will make use of the others.

変更の背景

Go言語のハッシュテーブル（マップ）は、悪意のある入力によってサービス拒否攻撃（DoS攻撃）を受ける可能性があるという脆弱性を持っていました。これは、特定の入力シーケンスがハッシュ衝突を大量に引き起こし、ハッシュテーブルの操作（挿入、検索など）のパフォーマンスを著しく低下させることで発生します。この問題を緩和するためには、ハッシュテーブルの初期化に予測不可能な乱数シードを使用し、攻撃者がハッシュ関数を予測して衝突を意図的に引き起こすことを困難にする必要があります。

Linuxシステムでは、カーネルがプロセスの起動時に補助ベクトル（auxiliary vector, auxv）を通じて様々な情報をユーザー空間に渡します。この情報の中には、AT_RANDOMというエントリがあり、これはカーネルが提供する高品質な乱数データへのポインタを含んでいます。この乱数を利用することで、Goランタイムは各プロセスに対してユニークで予測不可能なハッシュシードを生成できるようになり、ハッシュ衝突攻撃に対する耐性を向上させることができます。

また、将来的な拡張性として、AT_HWCAP（ハードウェア機能）やAT_PLATFORM（プラットフォーム情報）といった他のauxvエントリもデコードできるように準備されています。これらは、特定のCPU機能の利用や、プラットフォーム固有の最適化に役立つ可能性があります。

前提知識の解説

1. Linux Auxiliary Vector (auxv)

Linuxカーネルは、プログラムの実行時に、環境変数やコマンドライン引数に加えて、追加の情報を「補助ベクトル（auxiliary vector）」という形式でユーザー空間に渡します。これは、ELF（Executable and Linkable Format）バイナリの実行時に、スタックの最上位に配置されるデータ構造です。auxvは、Elf32_auxv_tまたはElf64_auxv_t構造体の配列として表現され、各エントリはタイプ（a_type）と値（a_val）のペアで構成されます。

主要なauxvエントリには以下のようなものがあります。

• AT_NULL (0): auxvリストの終端を示すマーカー。
• AT_PLATFORM (15): 現在のプロセッサのプラットフォーム文字列へのポインタ。例えば、ARMアーキテクチャでは"v5l", "v6l", "v7l"などの文字列が含まれることがあります。
• AT_HWCAP (16): CPUのハードウェア機能を示すビットマスク。例えば、浮動小数点ユニット（FPU）の有無、特定の命令セット拡張のサポートなどが示されます。
• AT_RANDOM (25): カーネルが提供する16バイトの乱数データへのポインタ。これは、予測不可能なシードを必要とするアプリケーション（例: ハッシュテーブル、セキュリティ関連の乱数生成）にとって非常に有用です。この乱数は、/dev/urandomなどから取得されるものと同様に、高品質なエントロピー源から生成されます。

プログラムは、main関数の引数（argc, argv, envp）の後に続くスタック上のデータからauxvを解析することで、これらの情報を取得できます。

2. ハッシュテーブルとDoS攻撃

ハッシュテーブル（またはハッシュマップ、連想配列）は、キーと値のペアを格納するためのデータ構造です。キーをハッシュ関数に通してハッシュ値（インデックス）を計算し、そのインデックスに対応するメモリ位置に値を格納します。

理想的なハッシュ関数は、異なるキーに対して均一にハッシュ値を分散させ、衝突（異なるキーが同じハッシュ値になること）を最小限に抑えます。しかし、ハッシュ関数が予測可能である場合、攻撃者は意図的に大量の衝突を引き起こすようなキーのセットを作成できます。これにより、ハッシュテーブルの操作が最悪の場合、O(N)（Nは要素数）の計算量に劣化し、CPUリソースを大量に消費することでサービス拒否攻撃（DoS攻撃）を引き起こすことが可能になります。

この脆弱性に対処するためには、ハッシュテーブルの初期化時に、予測不可能なランダムなシードを使用することが一般的な対策です。これにより、攻撃者がハッシュ関数の挙動を予測し、衝突を意図的に引き起こすことが極めて困難になります。

3. ARMアーキテクチャとGoランタイム

ARM（Advanced RISC Machine）は、モバイルデバイスや組み込みシステムで広く使用されているCPUアーキテクチャです。Go言語は、ARMを含む様々なアーキテクチャをサポートしており、それぞれのアーキテクチャに特化したランタイムコード（アセンブリ言語で記述された部分など）を持っています。

Goランタイムは、プログラムの実行環境を管理する低レベルのコードの集合体です。これには、スケジューラ、ガベージコレクタ、メモリ管理、システムコールインターフェースなどが含まれます。特定のアーキテクチャ（例: ARM）に特化したランタイムコードは、そのアーキテクチャのレジスタ、命令セット、システムコール規約に合わせて最適化されています。

runtime·cputicks関数は、Goランタイム内で使用される擬似乱数生成器の一部であり、ハッシュテーブルのシードなど、予測不可能な値が必要な場面で利用されます。この関数は、CPUのティックカウントやその他のエントロピー源を利用して乱数を生成しようとしますが、本コミットではAT_RANDOMから取得した乱数を主要なエントロピー源として利用するように変更されています。

技術的詳細

本コミットの主要な目的は、Linux ARM環境において、Goランタイムがカーネルから提供される高品質な乱数シードをAT_RANDOM auxvエントリを通じて取得し、ハッシュテーブルの初期化に利用することです。

変更点は以下の通りです。

1. runtime·setup_auxv関数の追加:

   • src/pkg/runtime/signal_linux_arm.cにruntime·setup_auxvという新しいC言語関数が追加されました。
   • この関数は、argcとargv_list（main関数の引数に相当）を受け取り、スタック上の環境変数リストをスキップしてauxvリストの開始位置を特定します。
   • auxvリストを走査し、AT_NULLに到達するまで各エントリを解析します。
   • AT_RANDOM: このエントリが見つかった場合、その値（乱数データへのポインタ）から4バイトオフセットした位置の32ビット値をruntime·randomNumberグローバル変数に格納します。これは、カーネルが提供する16バイトの乱数データの一部を利用しています。
   • AT_PLATFORM: このエントリが見つかった場合、その値（プラットフォーム文字列へのポインタ）から1バイトオフセットした位置の文字を読み取り、それが'5'から'7'の範囲であれば、runtime·armArchグローバル変数にその数値を格納します。これはARMv5, ARMv6, ARMv7といったアーキテクチャバージョンを識別するために使用されます。デフォルト値はARMv6 (6) です。
   • AT_HWCAP: このエントリが見つかった場合、その値（ハードウェア機能ビットマスク）をruntime·hwcapグローバル変数に格納します。
   • この関数は、#pragma textflag 7ディレクティブによって、特定のセクションに配置されることを示唆しています。

2. _rt0_arm_linuxからのruntime·setup_auxv呼び出し:

   • src/pkg/runtime/rt0_linux_arm.sの_rt0_arm_linux（GoプログラムのLinux ARMにおけるエントリポイント）に、runtime·setup_auxvの呼び出しが追加されました。
   • SUB $4, R13とADD $4, R13は、runtime·setup_auxvのために一時的なスタックフレームを偽装するためのアセンブリ命令です。これにより、C関数が期待するスタックレイアウトが提供されます。
   • この変更により、Goプログラムが起動する際に、カーネルから提供されるauxv情報が初期化フェーズで解析されるようになります。

3. runtime·cputicks関数の変更:

   • src/pkg/runtime/signal_linux_arm.cに、新しいruntime·cputicks関数のC言語実装が追加されました。
   • 以前のsrc/pkg/runtime/asm_arm.sにあったアセンブリ言語のスタブ実装は削除されました。
   • 新しいruntime·cputicksは、runtime·randomNumberグローバル変数を利用して擬似乱数を生成します。これは、runtime.cのfastrand1関数からコピーされたロジックであり、Xorshiftのような単純な線形合同法に基づいています。
   • 生成された32ビット乱数xを元に、((int64)x) << 32 | xという形式で64ビットの値を返します。これは、ハッシュテーブルのシードとして使用されることを意図しています。

これらの変更により、Goランタイムは起動時にカーネルから提供される高品質な乱数を取得し、それをハッシュテーブルのシードとして利用することで、ハッシュ衝突攻撃に対する耐性を向上させています。また、ハードウェア機能やプラットフォーム情報の取得も将来の最適化のために準備されています。

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

src/pkg/runtime/asm_arm.s

--- a/src/pkg/runtime/asm_arm.s
+++ b/src/pkg/runtime/asm_arm.s
@@ -375,16 +375,6 @@ TEXT runtime·getcallersp(SB),7,$-4
 TEXT runtime·emptyfunc(SB),0,$0
  	RET
  
-// int64 runtime·cputicks(), so really
-// void runtime·cputicks(int64 *ticks)
-// stubbed: return int64(0)
-TEXT runtime·cputicks(SB),7,$0
-	MOVW    0(FP), R1
-	MOVW	$0, R0
-	MOVW    R0, 0(R1)
-	MOVW    R0, 4(R1)
-	RET
-
 TEXT runtime·abort(SB),7,$-4
  	MOVW	$0, R0
  	MOVW	(R0), R1

• runtime·cputicksのアセンブリスタブが削除されました。これは、C言語で新しい実装が提供されるためです。

src/pkg/runtime/rt0_linux_arm.s

--- a/src/pkg/runtime/rt0_linux_arm.s
+++ b/src/pkg/runtime/rt0_linux_arm.s
@@ -37,6 +37,10 @@ TEXT _rt0_arm_linux(SB),7,$-4
  	MOVW	$174, R7 // sys_sigaction
  	SWI	$0 // restore signal handler
  	ADD	$32, R13
++
++	SUB	$4, R13 // fake a stack frame for runtime·setup_auxv
++	BL	runtime·setup_auxv(SB)
++	ADD	$4, R13
  	B	_rt0_arm(SB)
  
  TEXT bad_abi<>(SB),7,$-4

• _rt0_arm_linuxのエントリポイントで、runtime·setup_auxv関数が呼び出されるようになりました。スタックフレームを調整するためのアセンブリ命令も追加されています。

src/pkg/runtime/signal_linux_arm.c

--- a/src/pkg/runtime/signal_linux_arm.c
+++ b/src/pkg/runtime/signal_linux_arm.c
@@ -141,3 +141,60 @@ runtime·setsig(int32 i, void (*fn)(int32, Siginfo*, void*, G*), bool restart))
  	sa.sa_handler = fn;
  	runtime·rt_sigaction(i, &sa, nil, 8);
  }\n
++
++#define AT_NULL		0
++#define AT_PLATFORM	15 // introduced in at least 2.6.11
++#define AT_HWCAP	16 // introduced in at least 2.6.11
++#define AT_RANDOM	25 // introduced in 2.6.29
++static uint32 runtime·randomNumber;
++uint32 runtime·hwcap;
++uint8 runtime·armArch = 6; // we default to ARMv6
++
++#pragma textflag 7
++void
++runtime·setup_auxv(int32 argc, void *argv_list)
++{
++	byte **argv = &argv_list;
++	byte **envp;
++	uint32 *auxv;
++	uint32 t;
++
++	// skip envp to get to ELF auxiliary vector.
++	for(envp = &argv[argc+1]; *envp != nil; envp++)
++		;
++	envp++;
++	
++	for(auxv=(uint32*)envp; auxv[0] != AT_NULL; auxv += 2) {
++		switch(auxv[0]) {
++		case AT_RANDOM: // kernel provided 16-byte worth of random data
++			if(auxv[1])
++				runtime·randomNumber = *(uint32*)(auxv[1] + 4);
++			break;
++		case AT_PLATFORM: // v5l, v6l, v7l
++			if(auxv[1]) {
++				t = *(uint8*)(auxv[1]+1);
++				if(t >= '5' && t <= '7')
++					runtime·armArch = t - '0';
++			}
++			break;
++		case AT_HWCAP: // CPU capability bit flags
++			runtime·hwcap = auxv[1];
++			break;
++		}
++	}
++}
++
++#pragma textflag 7
++int64
++runtime·cputicks() {
++	// copied from runtime.c:/^fastrand1
++	uint32 x;
++
++	x = runtime·randomNumber;
++	x += x;
++	if(x & 0x80000000L)
++		x ^= 0x88888eefUL;
++	runtime·randomNumber = x;
++
++	return ((int64)x) << 32 | x;
++}

• AT_NULL, AT_PLATFORM, AT_HWCAP, AT_RANDOMのマクロ定義が追加されました。
• runtime·randomNumber, runtime·hwcap, runtime·armArchのグローバル変数が宣言されました。
• runtime·setup_auxv関数が追加され、auxvを解析して乱数、ハードウェア機能、プラットフォーム情報を取得します。
• runtime·cputicks関数の新しいC言語実装が追加され、runtime·randomNumberを利用して擬似乱数を生成します。

コアとなるコードの解説

runtime·setup_auxv関数

この関数は、Linuxカーネルがプロセス起動時にスタックに配置する補助ベクトル（auxv）を解析するためのGoランタイムのC言語実装です。

void
runtime·setup_auxv(int32 argc, void *argv_list)
{
    byte **argv = &argv_list;
    byte **envp;
    uint32 *auxv;
    uint32 t;

    // skip envp to get to ELF auxiliary vector.
    // コマンドライン引数 (argv) の後に環境変数 (envp) が続き、その後に auxv が続くため、envp をスキップする。
    for(envp = &argv[argc+1]; *envp != nil; envp++)
        ;
    envp++; // envp の終端 (nil) の次が auxv の開始位置

    // auxv リストを走査する
    for(auxv=(uint32*)envp; auxv[0] != AT_NULL; auxv += 2) {
        switch(auxv[0]) {
        case AT_RANDOM: // kernel provided 16-byte worth of random data
            // カーネルが提供する16バイトの乱数データへのポインタ (auxv[1]) から4バイトオフセットした位置の32ビット値を乱数シードとして取得
            if(auxv[1])
                runtime·randomNumber = *(uint32*)(auxv[1] + 4);
            break;
        case AT_PLATFORM: // v5l, v6l, v7l
            // プラットフォーム文字列からARMアーキテクチャバージョンを抽出
            if(auxv[1]) {
                t = *(uint8*)(auxv[1]+1); // 例: "v7l" の '7' を取得
                if(t >= '5' && t <= '7')
                    runtime·armArch = t - '0'; // '5', '6', '7' を数値に変換
            }
            break;
        case AT_HWCAP: // CPU capability bit flags
            // ハードウェア機能ビットマスクを取得
            runtime·hwcap = auxv[1];
            break;
        }
    }
}

この関数は、Goプログラムが起動する非常に早い段階で呼び出され、カーネルから提供されるシステムレベルの情報をGoランタイムが利用できるようにします。特にAT_RANDOMから取得される乱数は、ハッシュテーブルのシードとして利用され、セキュリティ上の脆弱性（ハッシュ衝突攻撃）の緩和に貢献します。

runtime·cputicks関数

この関数は、Goランタイム内で擬似乱数を生成するために使用されます。以前はアセンブリ言語のスタブ実装でしたが、本コミットでC言語による実装に置き換えられ、AT_RANDOMから取得した乱数シードを基に乱数を生成するようになりました。

int64
runtime·cputicks() {
    // copied from runtime.c:/^fastrand1
    uint32 x;

    x = runtime·randomNumber; // auxv から取得した乱数シードを初期値とする
    x += x; // x を左シフト (x * 2)
    if(x & 0x80000000L) // 最上位ビットが1の場合 (負の数として扱われる場合)
        x ^= 0x88888eefUL; // 特定の定数とXOR演算を行う (Xorshift の一部)
    runtime·randomNumber = x; // 次の乱数生成のために更新

    return ((int64)x) << 32 | x; // 32ビット乱数 x を使って64ビットの値を生成
}

この擬似乱数生成器は、Xorshiftアルゴリズムに似た単純な線形合同法を使用しています。runtime·randomNumberがAT_RANDOMから初期化されることで、各プロセスのハッシュテーブルのシードが予測不可能になり、ハッシュ衝突攻撃に対する耐性が向上します。

関連リンク

• Go言語のハッシュテーブルDoS脆弱性に関する情報:
  • Go maps in action - The Go Programming Language Blog (このブログ記事は、ハッシュテーブルのランダム化について言及しています)
  • Go issue #4576: runtime: make map iteration order random (ハッシュマップのイテレーション順序のランダム化に関する議論ですが、ハッシュシードのランダム化と関連しています)
• Linux Auxiliary Vector (auxv) の詳細:
  • The Linux Kernel documentation - Auxiliary Vector
  • ELF(5) - Linux man page (ELF形式とauxvに関する情報)

参考にした情報源リンク

• Go CL 5978051: runtime: get per-process random number from auxv for hash table (本コミットのCode Reviewリンク)
• Linux Auxiliary Vector (auxv) - Wikipedia
• Hash table - Wikipedia
• DoS attack - Wikipedia
• Xorshift - Wikipedia
• ARM architecture - Wikipedia
• Go言語のソースコード (特にsrc/runtime/map.goやsrc/runtime/runtime.goなど、ハッシュテーブルや乱数生成に関連する部分)