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

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

このコミットは、Goランタイムにおけるマップのハッシュ関数の品質を評価するために、Smhasherテストを導入するものです。特に、Goのマップが使用するハッシュ関数が、様々な入力パターンに対して均一なハッシュ値を生成し、衝突を最小限に抑えるように設計されているかを検証します。

コミット

commit 78338d8c667d7798209132a6c206051db98de83c
Author: Keith Randall <khr@golang.org>
Date:   Fri Sep 6 16:23:46 2013 -0700

    runtime: Smhasher tests of our map hash function.
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/13436045
---
 src/pkg/runtime/alg.c          |  26 +++
 src/pkg/runtime/export_test.go |  12 +
 src/pkg/runtime/hash_test.go   | 512 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 550 insertions(+)

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

https://github.com/golang/go/commit/78338d8c667d7798209132a6c206051db98de83c

元コミット内容

Goランタイムのマップハッシュ関数に対するSmhasherテスト。

変更の背景

Goのマップ（map型）は、キーと値のペアを効率的に格納・検索するためのデータ構造であり、内部的にはハッシュテーブルとして実装されています。ハッシュテーブルの性能は、使用されるハッシュ関数の品質に大きく依存します。ハッシュ関数が異なる入力に対して均一にハッシュ値を分散させないと、ハッシュ衝突が頻繁に発生し、マップの操作（挿入、検索、削除）のパフォーマンスが著しく低下する可能性があります。

このコミットの背景には、Goのマップハッシュ関数の堅牢性と衝突耐性を検証する必要性がありました。特に、悪意のある入力や特定のパターンを持つ入力によってハッシュ衝突が意図的に引き起こされ、サービス拒否（DoS）攻撃につながる可能性も考慮されます。Smhasherは、ハッシュ関数の品質を厳密にテストするためのベンチマークスイートであり、様々なエッジケースや攻撃パターンをシミュレートすることで、ハッシュ関数の弱点を特定するのに役立ちます。

このコミットは、Goランタイムのハッシュ関数が、AES命令セット拡張（AES-NI）を利用した高速なハッシュ関数（AESハッシュ）と、それがない場合のフォールバックハッシュ関数の両方で、高い品質を維持していることを確認するために導入されました。特に、AESハッシュが利用可能な場合にのみ、より厳密なSmhasherテストが実行されるように設計されています。これは、フォールバックハッシュ関数がSmhasherの全てのテストに合格するほど強力ではない可能性があるためです。

前提知識の解説

ハッシュ関数とハッシュテーブル

ハッシュ関数は、任意のサイズの入力データ（キー）を受け取り、固定サイズの出力（ハッシュ値）を生成する関数です。理想的なハッシュ関数は、異なる入力に対して異なるハッシュ値を生成し、ハッシュ値が均一に分布するように設計されています。

ハッシュテーブルは、ハッシュ関数を使用してキーをハッシュ値に変換し、そのハッシュ値を配列のインデックスとして使用して値を格納するデータ構造です。これにより、平均的にはO(1)の高速な検索、挿入、削除が可能になります。しかし、異なるキーが同じハッシュ値にマッピングされる「ハッシュ衝突」が発生すると、性能が低下します。衝突解決には、チェイニング（同じハッシュ値を持つ要素をリンクリストでつなぐ）やオープンアドレス法（空いている次のスロットを探す）などの手法が用いられます。

Smhasher

Smhasherは、GoogleのAustin Applebyによって開発された、ハッシュ関数の品質をテストするための包括的なベンチマークスイートです。Smhasherは、以下のような様々なテストを通じて、ハッシュ関数の弱点や衝突耐性を評価します。

  • Sanity Checks: ハッシュ値がキーの外部のバイトやアライメントに依存しないことを確認します。
  • Appended Zeros: キーの末尾にゼロを追加した場合に、ハッシュ値が適切に変化するかをテストします。
  • Small Keys: 短いキー（0〜3バイト）が全て異なるハッシュ値を持つことを確認します。
  • Zeros: 全てゼロの異なる長さのキーが異なるハッシュ値を持つことを確認します。
  • Two Nonzero: 2つ以下の非ゼロバイトを持つキーが全て異なるハッシュ値を持つことを確認します。
  • Cyclic: "abcdabcdabcd..." のような繰り返しパターンを持つキーに対するハッシュ関数の挙動をテストします。
  • Sparse: 疎なデータ（少数のビットのみがセットされている）に対するハッシュ関数の挙動をテストします。
  • Permutation: 特定のブロックの組み合わせに対するハッシュ関数の挙動をテストします。
  • Avalanche: 入力キーの1ビットを反転させたときに、出力ハッシュ値のビットが約50%の確率で反転するか（アバランシェ効果）をテストします。これは、ハッシュ関数の入力に対する感度と、出力のランダム性を評価する重要な指標です。
  • Windowed: キーのビットを回転させた場合に、ハッシュ値が適切に変化するかをテストします。
  • Text: テキストデータ（英数字の組み合わせ）に対するハッシュ関数の挙動をテストします。
  • Seed: 異なるシード値が異なるハッシュ値を生成することを確認します。

Smhasherは、ハッシュ関数の「雪崩効果」（入力のわずかな変化が出力に大きな変化をもたらすこと）や、特定の入力パターンに対する脆弱性を検出するのに非常に効果的です。

Goのランタイムとハッシュ関数

Goのランタイムは、Goプログラムの実行を管理する低レベルのコンポーネントです。これには、ガベージコレクタ、スケジューラ、そしてマップのハッシュ関数などが含まれます。Goのマップは、内部的にキーの型に基づいて適切なハッシュ関数を選択します。文字列、バイトスライス、整数型など、様々な組み込み型に対して専用のハッシュ関数が提供されています。

Go 1.1以降、Goのマップは、特定のCPUアーキテクチャで利用可能なAES命令セット拡張（AES-NI）を利用したハッシュ関数を使用するようになりました。AES-NIは、暗号化処理をハードウェアレベルで高速化するための命令セットですが、その特性を利用して高速で高品質な非暗号学的ハッシュ関数を実装することも可能です。AESハッシュは、高いパフォーマンスと優れた衝突耐性を提供します。AES-NIが利用できない環境では、Goはソフトウェアベースのフォールバックハッシュ関数を使用します。

技術的詳細

このコミットは、Goランタイムのハッシュ関数をSmhasherのテストスイートで評価するためのGoテストコードを追加しています。

src/pkg/runtime/alg.c の変更

このファイルには、Goランタイムの低レベルなアルゴリズムがC言語で実装されています。追加されたコードは、Goのテストコードからランタイムのハッシュ関数を呼び出すためのアダプター関数です。

  • runtime·haveGoodHash(bool res): 現在の環境でAESハッシュが利用可能かどうかを返す関数。
  • runtime·stringHash(String s, uintptr seed, uintptr res): 文字列のハッシュ値を計算するアダプター。
  • runtime·bytesHash(Slice s, uintptr seed, uintptr res): バイトスライスのハッシュ値を計算するアダプター。
  • runtime·int32Hash(uint32 i, uintptr seed, uintptr res): 32ビット整数のハッシュ値を計算するアダプター。
  • runtime·int64Hash(uint64 i, uintptr seed, uintptr res): 64ビット整数のハッシュ値を計算するアダプター。

これらの関数は、GoのテストコードからC言語で実装されたランタイムのハッシュ関数を呼び出すための橋渡しをします。FLUSH(&res) は、コンパイラが最適化によって結果をレジスタに保持するのを防ぎ、メモリに書き出すことを保証するためのものです。

src/pkg/runtime/export_test.go の変更

このファイルは、ランタイムの内部関数をテスト目的でGoのテストコードにエクスポートするためのものです。上記のalg.cで定義されたアダプター関数に対応するGoの関数宣言が追加されています。

  • func haveGoodHash() bool
  • func stringHash(s string, seed uintptr) uintptr
  • func bytesHash(b []byte, seed uintptr) uintptr
  • func int32Hash(i uint32, seed uintptr) uintptr
  • func int64Hash(i uint64, seed uintptr) uintptr

これらの宣言により、runtime_testパッケージからこれらの関数を呼び出すことが可能になります。

src/pkg/runtime/hash_test.go の追加

このファイルは、SmhasherテストスイートのGoへの移植版であり、Goのマップハッシュ関数の品質を評価するための主要なテストが含まれています。

  • SmhasherSanity: ハッシュ値がキーの外部のバイトやアライメントに依存しないことを確認します。
  • HashSet構造体とメソッド: ハッシュ衝突を検出・カウントするためのヘルパー構造体です。addメソッドでハッシュ値を追加し、checkメソッドで統計的に期待される衝突数と比較して、ハッシュ関数の品質を評価します。
    • collisions := s.n - len(s.m): s.nは追加されたハッシュの総数、len(s.m)はユニークなハッシュの数なので、その差が衝突数になります。
    • expected := float64(pairs) / math.Pow(2.0, float64(hashSize)): 誕生日のパラドックスに基づいて、ランダムなハッシュ関数で期待される衝突数を計算します。
    • SLOPとstddevを用いた統計的評価: 実際の衝突数が期待値から大きく外れていないかを標準偏差を用いて確認します。
  • TestSmhasherAppendedZeros: キーの末尾にゼロを追加した場合のハッシュ挙動をテストします。
  • TestSmhasherSmallKeys: 短いキー（1〜3バイト）に対するハッシュ衝突をテストします。
  • TestSmhasherZeros: 全てゼロの異なる長さのキーに対するハッシュ衝突をテストします。
  • TestSmhasherTwoNonzero: 2つ以下の非ゼロバイトを持つキーに対するハッシュ衝突をテストします。
  • TestSmhasherCyclic: 繰り返しパターンを持つキーに対するハッシュ衝突をテストします。このテストは、HaveGoodHash()（AESハッシュが利用可能か）がtrueの場合にのみ実行されます。これは、フォールバックハッシュ関数がこの種の厳しいテストに耐えられない可能性があるためです。
  • TestSmhasherSparse: 疎なデータ（少数のビットのみがセットされている）に対するハッシュ衝突をテストします。
  • TestSmhasherPermutation: 特定のブロックの組み合わせに対するハッシュ衝突をテストします。これもHaveGoodHash()がtrueの場合にのみ実行されます。
  • Keyインターフェースと実装（BytesKey, Int32Key, Int64Key）: 様々な型のキーに対するアバランシェテストを汎用的に実行するためのインターフェースと、そのバイトスライス、32ビット整数、64ビット整数に対する実装です。
  • TestSmhasherAvalanche: アバランシェ効果をテストします。入力キーの1ビットを反転させたときに、出力ハッシュ値の各ビットが約50%の確率で反転するかを統計的に評価します。これもHaveGoodHash()がtrueの場合にのみ実行されます。
    • grid[i][j]は、入力ビットiの反転が出力ビットjに影響を与えた回数をカウントします。
    • 結果は統計的に期待される値（REP/2）と比較され、許容範囲外であればエラーが報告されます。
  • TestSmhasherWindowed: キーのビットを回転させた場合のハッシュ挙動をテストします。
  • TestSmhasherText: テキストデータ（英数字の組み合わせ）に対するハッシュ衝突をテストします。
  • TestSmhasherSeed: 異なるシード値が異なるハッシュ値を生成することを確認します。
  • hashSize定数: ハッシュ出力のビットサイズ（32ビットまたは64ビット）を定義します。
  • ベンチマーク関数: BenchmarkHash関数群は、異なる長さの文字列に対するハッシュ計算のパフォーマンスを測定します。

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

このコミットのコアとなる変更は、主にsrc/pkg/runtime/hash_test.goの新規追加です。このファイルには、Goのマップハッシュ関数の品質を検証するためのSmhasherテストスイートが実装されています。

具体的には、以下のテスト関数とヘルパー関数が追加されています。

  • TestSmhasherSanity
  • HashSet 構造体とそのメソッド (newHashSet, add, addS, addB, addS_seed, check)
  • TestSmhasherAppendedZeros
  • TestSmhasherSmallKeys
  • TestSmhasherZeros
  • TestSmhasherTwoNonzero
  • twoNonZero
  • TestSmhasherCyclic
  • TestSmhasherSparse
  • sparse
  • setbits
  • TestSmhasherPermutation
  • permutation
  • genPerm
  • Key インターフェース
  • BytesKey, Int32Key, Int64Key 構造体とそのメソッド
  • TestSmhasherAvalanche
  • avalancheTest1
  • TestSmhasherWindowed
  • windowed
  • TestSmhasherText
  • text
  • TestSmhasherSeed
  • hashSize 定数
  • randBytes
  • benchmarkHash
  • BenchmarkHash5, BenchmarkHash16, BenchmarkHash64, BenchmarkHash1024, BenchmarkHash65536

また、src/pkg/runtime/alg.c には、Goのテストからランタイムのハッシュ関数を呼び出すためのC言語アダプター関数が追加され、src/pkg/runtime/export_test.go には、これらのアダプター関数に対応するGoの関数宣言が追加されています。

コアとなるコードの解説

src/pkg/runtime/alg.c のアダプター関数

// Testing adapters for hash quality tests (see hash_test.go)
void runtime·haveGoodHash(bool res) {
	res = use_aeshash;
	FLUSH(&res);
}
void runtime·stringHash(String s, uintptr seed, uintptr res) {
	runtime·algarray[ASTRING].hash(&seed, sizeof(String), &s);
	res = seed;
	FLUSH(&res);
}
// ... (bytesHash, int32Hash, int64Hashも同様)

これらのC関数は、Goのテストコードから直接呼び出せるように、Goの関数シグネチャに合わせたラッパーとして機能します。runtime·algarrayは、Goの様々な型に対するハッシュ関数ポインタの配列です。ASTRING, AMEM, AMEM32, AMEM64は、それぞれ文字列、バイトスライス、32ビット整数、64ビット整数に対応するハッシュ関数を指します。FLUSH(&res)は、結果が確実にメモリに書き込まれるようにするためのGoランタイムの内部マクロです。

src/pkg/runtime/export_test.go のエクスポート宣言

func haveGoodHash() bool
func stringHash(s string, seed uintptr) uintptr
func bytesHash(b []byte, seed uintptr) uintptr
func int32Hash(i uint32, seed uintptr) uintptr
func int64Hash(i uint64, seed uintptr) uintptr

var HaveGoodHash = haveGoodHash
var StringHash = stringHash
var BytesHash = bytesHash
var Int32Hash = int32Hash
var Int64Hash = int64Hash

これらの宣言により、runtime_testパッケージからC言語で実装されたランタイムのハッシュ関数をGoの通常の関数として呼び出すことができます。var宣言は、これらの関数をテストパッケージ内で利用可能にするためのものです。

src/pkg/runtime/hash_test.go のSmhasherテスト

HashSet 構造体と衝突チェック

type HashSet struct {
	m map[uintptr]struct{} // set of hashes added
	n int                  // number of hashes added
}

func (s *HashSet) check(t *testing.T) {
	const SLOP = 10.0
	collisions := s.n - len(s.m)
	pairs := int64(s.n) * int64(s.n-1) / 2
	expected := float64(pairs) / math.Pow(2.0, float64(hashSize))
	stddev := math.Sqrt(expected)
	if float64(collisions) > expected+SLOP*3*stddev {
		t.Errorf("unexpected number of collisions: got=%d mean=%f stddev=%f", collisions, expected, stddev)
	}
}

HashSetは、生成されたハッシュ値を格納し、そのユニークな数と総数から衝突数を計算します。checkメソッドでは、誕生日のパラドックスに基づいて期待される衝突数を計算し、実際の衝突数が統計的に許容範囲内にあるか（期待値からSLOP * 3 * stddevを超えていないか）を検証します。これにより、ハッシュ関数がランダムなハッシュ値を生成しているかを評価します。

TestSmhasherAvalanche

func avalancheTest1(t *testing.T, k Key) {
	const REP = 100000
	r := rand.New(rand.NewSource(1234))
	n := k.bits()

	grid := make([][hashSize]int, n) // grid[i][j] is a count of whether flipping input bit i affects output bit j.

	for z := 0; z < REP; z++ {
		k.random(r)
		h := k.hash()

		for i := 0; i < n; i++ {
			k.flipBit(i)
			d := h ^ k.hash() // XORing hashes to find differing bits
			k.flipBit(i)

			g := &grid[i]
			for j := 0; j < hashSize; j++ {
				g[j] += int(d & 1) // Count if output bit j changed
				d >>= 1
			}
		}
	}

	// Statistical check for each bit
	mean := .5 * REP
	stddev := .5 * math.Sqrt(REP)
	low := int(mean - c*stddev)
	high := int(mean + c*stddev)
	for i := 0; i < n; i++ {
		for j := 0; j < hashSize; j++ {
			x := grid[i][j]
			if x < low || x > high {
				t.Errorf("bad bias for %s bit %d -> bit %d: %d/%d\n", k.name(), i, j, x, REP)
			}
		}
	}
}

このテストは、ハッシュ関数の「雪崩効果」を評価します。入力キーの各ビットを個別に反転させ、その結果のハッシュ値が元のハッシュ値とどれだけ異なるかを調べます。理想的なハッシュ関数では、入力の1ビットの変化が、出力ハッシュ値の約50%のビットを反転させるべきです。grid配列は、入力ビットiの反転が出力ビットjに影響を与えた回数を記録します。最終的に、各grid[i][j]の値が統計的に期待される範囲（REP/2の周辺）にあるかを検証し、ハッシュ関数の品質を評価します。

HaveGoodHash()による条件付きテスト

TestSmhasherCyclic, TestSmhasherPermutation, TestSmhasherAvalancheなどの一部のテストは、if !HaveGoodHash() { t.Skip(...) }という条件でスキップされます。これは、AESハッシュが利用できない環境（use_aeshashがfalseの場合）では、フォールバックハッシュ関数がこれらの厳しいテストに合格しない可能性があるためです。これにより、テストの実行環境に応じて適切なテストが選択され、不必要な失敗が回避されます。

関連リンク

  • Goのマップの内部実装に関するブログ記事やドキュメント
  • Smhasherの公式リポジトリやドキュメント
  • AES-NIとハッシュ関数の関連性に関する技術記事

参考にした情報源リンク