[インデックス 11562] ファイルの概要
このコミットは、Goランタイムにruntime.cputicks()関数を追加し、それを用いてfastrand（高速乱数生成器）のシードを初期化することで、ハッシュテーブルの実装に対するアルゴリズム的複雑性攻撃（サービス拒否攻撃など）を緩和することを目的としています。具体的には、CPUのタイムスタンプカウンタ（TSC）を利用して、より予測困難な乱数シードを提供します。
コミット
- コミットハッシュ: 8e765da941f4f0649aca2b28234ac31adde45f06
- 作者: Damian Gryski dgryski@gmail.com
- コミット日時: 2012年2月2日 木曜日 14:09:27 -0500
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/8e765da941f4f0649aca2b28234ac31adde45f06
元コミット内容
runtime: add runtime.cputicks() and seed fastrand with it
This patch adds a function to get the current cpu ticks. This is
deemed to be 'sufficiently random' to use to seed fastrand to mitigate
the algorithmic complexity attacks on the hash table implementation.
On AMD64 we use the RDTSC instruction. For 386, this instruction,
while valid, is not recognized by 8a so I've inserted the opcode by
hand. For ARM, this routine is currently stubbed to return a constant
0 value.
Future work: update 8a to recognize RDTSC.
Fixes #2630.
R=rsc
CC=golang-dev
https://golang.org/cl/5606048
変更の背景
この変更の主な背景は、ハッシュテーブルの実装に対する「アルゴリズム的複雑性攻撃（algorithmic complexity attacks）」、特にサービス拒否（DoS）攻撃のリスクを軽減することにあります。
ハッシュテーブルは、キーと値のペアを効率的に格納・検索するためのデータ構造です。多くのプログラミング言語やシステムで広く利用されています。しかし、ハッシュ関数の出力が予測可能であったり、衝突（異なる入力が同じハッシュ値になること）が意図的に引き起こされやすい場合、悪意のある攻撃者が特定の入力シーケンスを生成することで、ハッシュテーブルの性能を著しく低下させることが可能になります。これは、ハッシュテーブルの最悪計算量（通常はO(n)）を引き起こし、結果としてアプリケーションの応答性を奪い、サービス拒否状態に陥らせる可能性があります。
このような攻撃を防ぐためには、ハッシュテーブルの初期化時に使用される乱数シードが予測困難であることが重要です。予測困難なシードを使用することで、攻撃者がハッシュ関数の挙動を事前に推測し、衝突を意図的に引き起こすことを困難にします。
このコミットでは、CPUのタイムスタンプカウンタ（TSC）から得られるCPUティック値をfastrandのシードとして利用することで、この予測困難性を高めようとしています。TSCはCPUが起動してからのサイクル数をカウントするレジスタであり、その値は非常に高速に変化するため、外部から予測することは困難であると見なされます。これにより、ハッシュテーブルの初期化がよりランダムになり、アルゴリズム的複雑性攻撃に対する耐性が向上します。
前提知識の解説
1. ハッシュテーブルとアルゴリズム的複雑性攻撃
- ハッシュテーブル: キーと値のペアを格納するデータ構造で、キーをハッシュ関数に通して得られるハッシュ値に基づいてデータを格納・検索します。平均的にはO(1)の高速な操作が可能ですが、ハッシュ衝突（異なるキーが同じハッシュ値になること）が発生すると性能が低下します。
- ハッシュ衝突: 異なる入力キーがハッシュ関数によって同じハッシュ値にマッピングされる現象です。衝突が発生すると、ハッシュテーブルは連結リストやオープンアドレス法などの方法で衝突を解決しようとしますが、これにより検索や挿入の効率が低下します。
- アルゴリズム的複雑性攻撃（DoS攻撃）: 攻撃者が意図的に多数のハッシュ衝突を引き起こすような入力データを生成し、ハッシュテーブルの操作を最悪計算量（O(n)）に近づけることで、アプリケーションのCPU使用率を急増させ、サービスを停止させる攻撃手法です。これにより、正当なユーザーからのリクエスト処理が遅延または不可能になり、サービス拒否状態に陥ります。
2. 乱数シードとfastrand
- 乱数シード: 擬似乱数生成器（PRNG）が乱数列を生成する際に使用する初期値です。同じシード値からは常に同じ乱数列が生成されるため、予測困難な乱数列を得るためには、予測困難なシード値を使用することが不可欠です。
fastrand: Goランタイム内で使用される高速な擬似乱数生成器です。これは、一般的なmath/randパッケージの乱数生成器よりも高速に動作するように設計されており、主に内部的な用途（例: ハッシュテーブルの初期化、スケジューラのランダムな挙動など）で利用されます。その性質上、暗号学的に安全である必要はなく、高速性が重視されます。しかし、そのシードが予測可能であると、上述のハッシュテーブル攻撃のリスクが高まります。
3. RDTSC命令とCPUティック
RDTSC(Read Time-Stamp Counter): x86アーキテクチャのプロセッサが提供するCPU命令の一つです。この命令を実行すると、プロセッサ内部のタイムスタンプカウンタ（TSC）レジスタの現在値が読み出されます。TSCは、プロセッサが起動してからのCPUサイクル数をカウントする64ビットのレジスタです。- CPUティック:
RDTSC命令によって読み出されるTSCの値、すなわちCPUサイクル数を指します。この値は非常に高速に増加し、通常は予測が困難であるため、高精度な時間計測や、このコミットのように乱数シードの生成源として利用されることがあります。ただし、TSCの値はCPUの周波数変更（省電力機能など）やマルチコア環境での同期の問題など、いくつかの注意点があります。しかし、この文脈では「十分にランダム」であると見なされています。
4. Goのアセンブラ（8a）
8a: Goコンパイラツールチェーンの一部であるアセンブラです。Goのランタイムや標準ライブラリの一部は、パフォーマンスや特定のハードウェア機能へのアクセスを目的として、Goのアセンブラ言語で記述されています。このコミットメッセージにある「8aが認識しない」という記述は、当時の8aアセンブラがRDTSC命令のニーモニックを直接サポートしていなかったことを意味します。そのため、手動で命令のバイトコード（オペコード）を挿入する必要がありました。
技術的詳細
このコミットは、Goランタイムにruntime.cputicks()関数を導入し、各アーキテクチャ（386, AMD64, ARM）でその実装を提供しています。この関数は、CPUのタイムスタンプカウンタ（TSC）の値を読み取り、fastrandのシードとして利用することで、ハッシュテーブルの初期化におけるランダム性を向上させます。
runtime.cputicks()の実装
-
AMD64 (x86-64):
RDTSC命令を直接使用します。この命令は、TSCの低位32ビットをEAXレジスタに、高位32ビットをEDXレジスタに格納します。SHLQ $32, DXでEDXの内容を32ビット左シフトし、ADDQ DX, AXでEAXの内容と加算することで、64ビットのTSC値をAXレジスタ（GoのアセンブラではAXは64ビットレジスタの低位部分を指すことが多いが、ここではAXとDXを組み合わせて64ビット値を構築している）に格納します。最終的にこの64ビット値が関数の戻り値となります。- AMD64では
RDTSC命令がアセンブラによって直接サポートされているため、シンプルに記述されています。
-
386 (x86):
- 当時の
8aアセンブラがRDTSC命令を直接認識しなかったため、手動でそのオペコード（0x0F 0x31）をバイト列として挿入しています。 BYTE $0x0F; BYTE $0x31;がこれに該当します。RDTSC命令実行後、EAXとEDXに格納された32ビット値を組み合わせて64ビット値を構築し、呼び出し元に渡されるポインタ（ret+0(FP)でアクセス）に格納します。
- 当時の
-
ARM:
- ARMアーキテクチャにはx86のような直接的なTSCレジスタが存在しないため、この時点では
runtime.cputicks()はスタブとして実装されています。 - 常に定数
0を返します。これは、ARM環境ではCPUティックを直接取得する手段がなかったか、あるいは実装が複雑であったため、将来の作業として残されたことを示唆しています。このため、ARM環境ではこのコミットによるfastrandのシードのランダム性向上は限定的です。
- ARMアーキテクチャにはx86のような直接的なTSCレジスタが存在しないため、この時点では
fastrandのシードへの適用
src/pkg/runtime/proc.c内のmcommoninit関数（M（マシン）構造体の共通初期化を行う関数）において、m->fastrandの初期化時にruntime.cputicks()の戻り値が加算されるように変更されています。- 変更前:
m->fastrand = 0x49f6428aUL + m->id; - 変更後:
m->fastrand = 0x49f6428aUL + m->id + runtime·cputicks(); - これにより、各M（GoのランタイムにおけるOSスレッドの抽象化）の
fastrandシードが、MのIDと固定値に加えて、CPUティック値によって初期化されるようになり、より予測困難な初期状態が実現されます。
ヘッダーファイルの変更
src/pkg/runtime/runtime.hにint64 runtime·cputicks(void);という関数プロトタイプが追加され、runtime.cputicks()がGoランタイムの他の部分から呼び出せるように宣言されています。
この変更は、Goランタイムのセキュリティと堅牢性を向上させるための重要なステップであり、特にハッシュテーブルを利用するアプリケーションの安定性向上に寄与します。
コアとなるコードの変更箇所
このコミットでは、以下の5つのファイルが変更されています。
src/pkg/runtime/asm_386.s: 32ビットx86アーキテクチャ向けのアセンブリコード。runtime.cputicks()関数の実装が追加されました。src/pkg/runtime/asm_amd64.s: 64ビットx86（AMD64）アーキテクチャ向けのアセンブリコード。runtime.cputicks()関数の実装が追加されました。src/pkg/runtime/asm_arm.s: ARMアーキテクチャ向けのアセンブリコード。runtime.cputicks()関数のスタブ実装が追加されました。src/pkg/runtime/proc.c: Goランタイムのプロセッサ管理に関するCコード。fastrandのシード初期化部分が変更されました。src/pkg/runtime/runtime.h: Goランタイムのヘッダーファイル。runtime.cputicks()関数のプロトタイプ宣言が追加されました。
コアとなるコードの解説
src/pkg/runtime/asm_386.s の変更
+// int64 runtime·cputicks(void), so really
+// void runtime·cputicks(int64 *ticks)
+TEXT runtime·cputicks(SB),7,$0
+\tBYTE\t$0x0F; BYTE $0x31; // RDTSC; not supported by 8a
+\tMOVL\tret+0(FP), DI
+\tMOVL\tAX, 0(DI)
+\tMOVL\tDX, 4(DI)
+\tRET
このセクションでは、32ビットx86（386）アーキテクチャ向けのruntime.cputicks()関数が定義されています。
BYTE $0x0F; BYTE $0x31;: これはRDTSC命令のオペコード（バイト列）を直接挿入しています。当時のGoアセンブラ（8a）がRDTSCニーモニックを直接サポートしていなかったため、このように手動で記述する必要がありました。RDTSC命令は、CPUのタイムスタンプカウンタ（TSC）の値をEDX:EAXレジスタペア（高位32ビットがEDX、低位32ビットがEAX）に読み込みます。MOVL ret+0(FP), DI: 呼び出し元から渡された戻り値のポインタをDIレジスタにロードします。Goのアセンブラでは、関数は戻り値をポインタ経由で受け取ることがあります。MOVL AX, 0(DI):EAXレジスタ（TSCの下位32ビット）の内容を、戻り値ポインタが指すアドレスのオフセット0に格納します。MOVL DX, 4(DI):EDXレジスタ（TSCの上位32ビット）の内容を、戻り値ポインタが指すアドレスのオフセット4に格納します。これにより、64ビットのTSC値がメモリに書き込まれます。RET: 関数から戻ります。
src/pkg/runtime/asm_amd64.s の変更
+// int64 runtime·cputicks(void)
+TEXT runtime·cputicks(SB),7,$0
+\tRDTSC
+\tSHLQ\t$32, DX
+\tADDQ\tDX, AX
+\tRET
このセクションでは、64ビットx86（AMD64）アーキテクチャ向けのruntime.cputicks()関数が定義されています。
RDTSC: AMD64ではRDTSC命令がアセンブラによって直接サポートされています。この命令は、TSCの低位64ビットをRAXレジスタに、高位64ビットをRDXレジスタに格納します（実際にはRDX:RAXで128ビットの値を形成しますが、TSCは64ビットなのでRDXには上位32ビット、RAXには下位32ビットが格納されます）。SHLQ $32, DX:RDXレジスタの内容を32ビット左シフトします。これにより、RDXに格納されていたTSCの上位32ビットが、64ビット値の上位32ビットの位置に移動します。ADDQ DX, AX: シフトされたRDXの内容をRAXレジスタの内容に加算します。これにより、RAXにはTSCの64ビット値全体が格納されます。RET: 関数から戻ります。RAXレジスタに格納された値が関数の戻り値となります。
src/pkg/runtime/asm_arm.s の変更
+// int64 runtime·cputicks(), so really
+// void runtime·cputicks(int64 *ticks)
+// stubbed: return int64(0)
+TEXT runtime·cputicks(SB),7,$0
+\tMOVW 0(FP), R1
+\tMOVW\t$0, R0
+\tMOVW R0, 0(R1)
+\tMOVW R0, 4(R1)
+\tRET
このセクションでは、ARMアーキテクチャ向けのruntime.cputicks()関数が定義されていますが、これはスタブ実装です。
MOVW 0(FP), R1: 呼び出し元から渡された戻り値のポインタをR1レジスタにロードします。MOVW $0, R0:R0レジスタに定数0をロードします。MOVW R0, 0(R1):R0の内容（0）を、戻り値ポインタが指すアドレスのオフセット0に格納します。MOVW R0, 4(R1):R0の内容（0）を、戻り値ポインタが指すアドレスのオフセット4に格納します。これにより、64ビットの0がメモリに書き込まれます。RET: 関数から戻ります。
src/pkg/runtime/proc.c の変更
// ...
mcommoninit(M *m)
{
// ...
m->id = runtime·sched.mcount++;
- m->fastrand = 0x49f6428aUL + m->id;
+ m->fastrand = 0x49f6428aUL + m->id + runtime·cputicks();
m->stackalloc = runtime·malloc(sizeof(*m->stackalloc));
runtime·FixAlloc_Init(m->stackalloc, FixedStack, runtime·SysAlloc, nil, nil);
// ...
}
このCコードの変更は、GoランタイムのM（マシン）構造体の初期化を行うmcommoninit関数内で行われています。
m->fastrand = 0x49f6428aUL + m->id;からm->fastrand = 0x49f6428aUL + m->id + runtime·cputicks();へと変更されています。 この変更により、各Mのfastrandシードが、固定のオフセット値（0x49f6428aUL）とMのユニークなIDに加えて、新しく追加されたruntime.cputicks()の戻り値（CPUティック値）によって初期化されるようになりました。これにより、fastrandの初期シードがより予測困難になり、ハッシュテーブルのアルゴリズム的複雑性攻撃に対する耐性が向上します。
src/pkg/runtime/runtime.h の変更
// ...
void runtime·usleep(uint32);
+int64 runtime·cputicks(void);
// ...
このヘッダーファイルの変更は、runtime.cputicks()関数のプロトタイプ宣言を追加しています。これにより、Goランタイムの他のCコードやGoコードからこの関数を呼び出すことが可能になります。int64は、関数が64ビット整数を返すことを示しています。
関連リンク
- GitHubコミットページ: https://github.com/golang/go/commit/8e765da941f4f0649aca2b28234ac31adde45f06
- Go Issue #2630: https://golang.org/issue/2630 (コミットメッセージに記載されている修正対象のIssue)
- Go Code Review 5606048: https://golang.org/cl/5606048 (コミットメッセージに記載されている変更リストのリンク)
参考にした情報源リンク
- RDTSC (Wikipedia): https://en.wikipedia.org/wiki/RDTSC
- Hash table (Wikipedia): https://en.wikipedia.org/wiki/Hash_table
- Algorithmic complexity attack (Wikipedia): https://en.wikipedia.org/wiki/Algorithmic_complexity_attack
- Go Assembly Language (Go Documentation): https://go.dev/doc/asm (Goのアセンブラに関する一般的な情報)
- Go runtime source code: https://github.com/golang/go/tree/master/src/runtime (Goランタイムのソースコード)
- Go issue tracker: https://github.com/golang/go/issues (GoのIssueトラッカー)
- Go Code Review: https://go.dev/wiki/CodeReview (Goのコードレビュープロセスに関する情報)
- Go's fastrand and its seeding: (具体的な記事は見つかりませんでしたが、Goの内部乱数生成器のシードに関する議論はGoコミュニティで頻繁に行われています。)
- CPU Time-Stamp Counter (Intel/AMD documentation): (特定のリンクは示しませんが、CPUベンダーのプログラマーズマニュアルにはRDTSC命令の詳細が記載されています。)