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

このコミットは、Goランタイムのハッシュ関数のテストに関連する変更です。具体的には、src/pkg/runtime/hash_test.go ファイルが修正され、ハッシュ関数のアバランシェテストにおける許容範囲が調整されました。変更は3行の追加と3行の削除から構成されています。

コミット

• Author: Keith Randall khr@golang.org
• Date: Fri May 9 15:50:57 2014 -0700
• Commit Hash: 711d1ad7eebc4aecfb3a326f16af206b7b99ff6c

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

https://github.com/golang/go/commit/711d1ad7eebc4aecfb3a326f16af206b7b99ff6c

元コミット内容

runtime: be a lot more lenient on smhasher avalanche test.

Fixes #7943

LGTM=bradfitz
R=golang-codereviews, bradfitz
CC=golang-codereviews
https://golang.org/cl/98170043

変更の背景

このコミットの主な目的は、Goランタイムのハッシュ関数が使用するsmhasherのアバランシェテストにおいて、より寛容な（"more lenient"）基準を適用することです。コミットメッセージにあるFixes #7943は、特定の課題を解決することを示唆していますが、公開されているGoのIssueトラッカーではこの番号のIssueは見つかりませんでした。これは、内部的なバグトラッカーの参照であるか、あるいはテストの厳しさが原因で継続的インテグレーション（CI）が頻繁に失敗していたなどの問題があった可能性が考えられます。

ハッシュ関数のアバランシェ効果をテストする際、過度に厳密な統計的基準を設定すると、実際には十分に機能し、実用上問題のないハッシュ関数であっても、わずかな統計的ばらつきによってテストに失敗する「偽陽性（false positive）」が発生することがあります。このような状況は、開発プロセスを妨げ、不必要な修正作業を引き起こす可能性があります。このコミットは、テストの信頼性を維持しつつ、現実的なハッシュ関数の振る舞いをより適切に許容するために、テストの閾値を調整する必要があったことを示しています。

前提知識の解説

ハッシュ関数 (Hash Function)

ハッシュ関数は、任意の長さの入力データ（メッセージ、ファイル、文字列など）を受け取り、それを固定長の短い出力（ハッシュ値、ハッシュコード、ダイジェストなどと呼ばれる）に変換するアルゴリズムです。ハッシュ関数は、データの検索（ハッシュテーブル）、データの整合性チェック、デジタル署名、パスワードの保存など、多岐にわたる用途で利用されます。良いハッシュ関数は、以下の特性を持つべきです。

• 決定性: 同じ入力に対しては常に同じハッシュ値を生成する。
• 高速性: ハッシュ値の計算が効率的である。
• 衝突耐性: 異なる入力から同じハッシュ値が生成されること（衝突）が非常に稀である。
• 原像計算困難性: ハッシュ値から元の入力を復元することが困難である。
• 第二原像計算困難性: ある入力とそのハッシュ値が与えられたとき、同じハッシュ値を持つ別の入力を発見することが困難である。

アバランシェ効果 (Avalanche Effect)

アバランシェ効果は、理想的なハッシュ関数（および暗号学的アルゴリズム全般）が持つべき重要な特性の一つです。これは、入力データのごくわずかな変化（例えば、1ビットの反転）が、出力されるハッシュ値の約半分に大きな変化（ビットの反転）を引き起こす現象を指します。この効果により、入力と出力の間に予測不可能な関係が生まれ、ハッシュ値の衝突を意図的に引き起こすことが非常に困難になります。アバランシェ効果が弱いハッシュ関数は、入力の変化に対して出力が予測可能になりやすく、セキュリティ上の脆弱性やハッシュテーブルの性能低下につながる可能性があります。

SMHasher

SMHasherは、非暗号学的ハッシュ関数の品質を評価するために設計された包括的なテストスイートです。ハッシュ関数の性能、分布、衝突耐性、そしてアバランシェ効果など、様々な側面を評価するためのテストが含まれています。SMHasherは、ハッシュ関数の設計者がその関数の品質を客観的に測定し、改善点を見つけるための重要なツールとして利用されます。

統計的テストと誤差関数 (Error Function, Erf)

ハッシュ関数のアバランシェ効果を定量的に評価するためには、統計的な手法が用いられます。理想的なアバランシェ効果を持つハッシュ関数では、入力の1ビットが反転すると、出力の各ビットが独立に50%の確率で反転すると期待されます。多数のビットについてこの現象を観察すると、ビット反転の総数は二項分布に従い、試行回数が十分に大きい場合には正規分布に近似できます。

誤差関数 (Error Function, erf(x)) は、確率論や統計学で用いられる特殊関数で、正規分布の累積分布関数と密接に関連しています。具体的には、平均0、分散1/2の正規分布において、ある値xまでの確率を計算するために使用されます。このコミットのテストコードでは、ハッシュ値のビット反転が正規分布に従うと仮定し、特定の範囲内に収まる確率を計算するためにmath.Erf関数が利用されています。

技術的詳細

src/pkg/runtime/hash_test.go内のavalancheTest1関数は、ハッシュ関数のアバランシェ効果を統計的に検証しています。このテストの核心は、入力キーのわずかな変更（1ビットの反転）が、ハッシュ出力のビットの約半分を反転させるという理想的な挙動が、統計的に許容される範囲内にあるかどうかを確認することです。

テストでは、以下の統計的アプローチが取られています。

1. 総ビット数 N の計算: N := n * hashSize は、テスト対象となるハッシュビットの総数を表します。ここで、nはテストケースの数、hashSizeはハッシュ値のビット数です。
2. 許容スラック係数 c の探索:
   • for c = 0.0; math.Pow(math.Erf(c/math.Sqrt(2)), float64(N)) < .99; c += .1 { ... } (変更前)
   • for c = 0.0; math.Pow(math.Erf(c/math.Sqrt(2)), float64(N)) < .9999; c += .1 { ... } (変更後) このループは、N個の独立した試行（各ハッシュビットの反転）がすべて、平均値からc標準偏差の範囲内に収まる確率が、特定の閾値（変更前は99%、変更後は99.99%）を超えるような最小のcの値を探索します。math.Erf(c/math.Sqrt(2))は、正規分布において平均からc標準偏差の範囲内に値が収まる確率を示します。この確率をN乗することで、すべてのビットがこの条件を満たす複合確率を計算しています。
3. 許容スラックの調整:
   • c *= 2.0 (変更前)
   • c *= 4.0 (変更後) 探索されたcの値にさらに係数を乗じることで、最終的な許容範囲を決定します。このcは、ハッシュビットの反転数が平均値からどれだけ離れても許容されるかを示す「許容スラック（allowed slack）」の係数として機能します。値が大きいほど、より広いばらつきが許容されます。
4. 平均と標準偏差の計算:
   • mean := .5 * REP
   • stddev := .5 * math.Sqrt(REP) これらは、ハッシュビットの反転が二項分布に従うことを前提とした平均と標準偏差の計算です。REPは各テストケースでの試行回数（おそらくハッシュ値のビット数）を指します。理想的には、各ビットが50%の確率で反転するため、平均はREP/2となります。
5. 許容範囲 low と high の定義:
   • low := int(mean - c*stddev)
   • high := int(mean + c*stddev) これらの値は、ハッシュビット反転数の許容される下限と上限を定義します。テストでは、実際のビット反転数がこの範囲内に収まることを期待します。

このコミットは、これらの統計的パラメータを調整することで、テストの厳密さと実用性のバランスを取ろうとしています。

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

--- a/src/pkg/runtime/hash_test.go
+++ b/src/pkg/runtime/hash_test.go
@@ -397,10 +397,10 @@ func avalancheTest1(t *testing.T, k Key) {
 	// all sums inside those bounds with 99% probability.
 	N := n * hashSize
 	var c float64
-	// find c such that Prob(mean-c*stddev < x < mean+c*stddev)^N > .99
-	for c = 0.0; math.Pow(math.Erf(c/math.Sqrt(2)), float64(N)) < .99; c += .1 {
+	// find c such that Prob(mean-c*stddev < x < mean+c*stddev)^N > .9999
+	for c = 0.0; math.Pow(math.Erf(c/math.Sqrt(2)), float64(N)) < .9999; c += .1 {
 	}
-	c *= 2.0 // allowed slack - we don't need to be perfectly random
+	c *= 4.0 // allowed slack - we don't need to be perfectly random
 	mean := .5 * REP
 	stddev := .5 * math.Sqrt(REP)
 	low := int(mean - c*stddev)

コアとなるコードの解説

このコミットにおけるコアとなる変更は、avalancheTest1関数内の2つの数値定数の変更です。

1. 確率閾値の変更 (.99 から .9999 へ): 変更前: math.Pow(math.Erf(c/math.Sqrt(2)), float64(N)) < .99 変更後: math.Pow(math.Erf(c/math.Sqrt(2)), float64(N)) < .9999

   この変更は、N個の独立したテストがすべて成功する（つまり、ハッシュビットの反転数が許容範囲内に収まる）複合確率の閾値を、99%から99.99%に引き上げています。これは一見するとテストをより厳しくしているように見えます。テスト全体の信頼水準を向上させ、テストが「誤って成功」する確率を減らそうとしていると解釈できます。

2. 許容スラック係数 c の乗数の変更 (2.0 から 4.0 へ): 変更前: c *= 2.0 // allowed slack - we don't need to be perfectly random 変更後: c *= 4.0 // allowed slack - we don't need to be perfectly random

   この変更は、ハッシュビットの反転数が平均値からどれだけ離れても許容されるかを示す「許容スラック」の係数cを、2倍から4倍に大幅に増やしています。cは標準偏差の倍数として機能するため、この値が大きいほど、平均からの偏差が大きくても許容されるようになります。つまり、ハッシュ関数の出力が完全にランダムでなくても、より広い範囲のばらつきを許容するようになったことを意味します。コメントも「完璧にランダムである必要はない」という意図を強調しています。

総合的な影響:

これらの変更を組み合わせると、テストの意図がより明確になります。

• テスト全体の信頼性向上: 確率閾値を.9999に引き上げたことで、テストスイート全体としての統計的信頼性は向上します。これは、テストがランダムなノイズによって誤って失敗する可能性を減らすことを目的としている可能性があります。
• 個々のテストケースの許容範囲拡大: しかし同時に、許容スラックcを4.0に増やしたことで、個々のハッシュビット反転の分布が、理論上の完璧なランダム性からある程度の逸脱があっても、テストに合格するようになりました。

この調整は、実際のハッシュ関数の振る舞いが、理論上の完璧なランダム性からある程度の逸脱があっても実用上問題ない、という現実的な判断に基づいている可能性が高いです。過度に厳密なテスト基準は、実用的なハッシュ関数が不必要にテストに失敗する原因となるため、この変更はテストの「偽陽性（false positive）」を減らし、CI/CDパイプラインの安定性を向上させることを目的としていると考えられます。特に、smhasherのようなテストスイートは、非常に多くのテストケースを実行するため、わずかな確率の失敗でも全体として頻繁に発生し、開発フローを阻害する可能性があるため、このような調整は実用上重要です。

関連リンク

• GitHubコミット: https://github.com/golang/go/commit/711d1ad7eebc4aecfb3a326f16af206b7b99ff6c
• Go Code Review (CL): https://golang.org/cl/98170043

参考にした情報源リンク

• SMHasher GitHubリポジトリ: https://github.com/aappleby/smhasher
• アバランシェ効果 (Wikipedia): https://en.wikipedia.org/wiki/Avalanche_effect
• 誤差関数 (Wikipedia): https://en.wikipedia.org/wiki/Error_function