Zend VMの深淵：HashTableの衝突とDJBX33Aハッシュの脆弱性耐性を極限まで解剖する
PHPを単なる「Web用の手軽なスクリプト言語」と認識しているうちは、大規模トラフィックや高度なセキュリティインシデントに直面したとき、必ず足元をすくわれる。PHPの心臓部であるZend Engineは、C言語で書かれた極めて洗練された仮想マシンであり、そのデータ構造の根幹をなすのが `HashTable` だ。
すべての連想配列（Array）、オブジェクトプロパティ、シンボルテーブル、さらには関数・クラスのルックアップに至るまで、PHPのメモリ空間の大部分はこの `HashTable` によって管理されている。
今回は、この `HashTable` の内部実装におけるハッシュ衝突のメカニズム、伝統的な `DJBX33A`（Bernsteinハッシュ） の挙動、そしてそれがもたらす致命的なアルゴリズム計算量攻撃（Hash DoS）に対するZend VMの防御機構を、低レイヤの視点から徹底的に解剖する。
—
1. Zend Engineにおける `HashTable` の物理構造
PHPの配列は、順序付きハッシュマップ（Ordered Hash Table）として実装されている。C言語レベルの構造体（`zend_array` / `_zend_hash_table`）を覗くと、単なるキーバリューの集合ではないことがよくわかる。
typedef struct _zend_hash_table {
uint32_t nTableSize; // バケット数（常に2のN乗に丸められる）
uint32_t nTableMask; // ビットマスク（nTableSize – 1）
uint32_t nNumUsed; // 使用済みバケット数
uint32_t nNumElements; // 実際に格納された要素数
zend_ulong nNextFreeElement; // 自動インデックスの次の値
zend_hash_key arHash; // ハッシュ値キャッシュ用（歴史的経緯）
uint32_t arData; // バケット配列へのポインタ（実際にはBucket構造体の連続領域）
// … (dtor, pInternalPointer 等のメタデータが続く)
} zend_hash_table;
PHPの配列にデータを挿入するとき、Zend VMは以下のステップを踏む。
1. ハッシュ値の計算: キー文字列（または整数）から、ハッシュ関数を用いて32bit/64bitの整数ハッシュを生成する。
2. インデックスの算出: `hash & nTableMask` により、ハッシュテーブルのバケット配列のインデックスを決定する。
3. バケットへの格納: バケット配列の指し示す位置に実データ（`Bucket`構造体）を配置する。
ここで問題になるのが、異なるキーが同一のバケットインデックスを指し示す 「ハッシュ衝突（Collision）」 である。
—
2. DJBX33Aハッシュアルゴリズムと衝突の現実
PHP 7以降（およびPHP 5の後半）で伝統的に使用されてきた文字列ハッシュ関数が `DJBX33A`（Daniel J. Bernstein氏による `times 33 + plus`） だ。
C言語で書かれたそのコアロジックは極めてシンプルかつ高速である。
// Zend Engine内部におけるDJBX33Aの概念実装
zend_ulong zend_inline_hash_func(const char str, size_t len) {
zend_ulong hash = 5381;
for (size_t i = 0; i < len; i++) {
hash = ((hash << 5) + hash) + str[i]; // hash 33 + c
}
return hash;
}
なぜ `33` なのか？
- 処理がビットシフト（`hash << 5` は `hash 32`）と加算で完結するため、CPUパイプラインを阻害せず極めて高速に動作する。
- 奇数であり、ハッシュ値の散らばり（アバランシェ効果）が当時のワークロードに対して十分であったため。
しかし、この「高速性」と「予測可能性」のトレードオフとして、悪意ある攻撃者が意図的に衝突を誘発できるという致命的な弱点を抱えている。
—
3. Hash DoS攻撃メカニズムと `HashTable` の衝突耐性
もし、攻撃者が `DJBX33A` の特性を突いて、まったく同じハッシュ値を生成する数万個の異なるキーをPOSTリクエストなどで送信したらどうなるか？
バケット連結リストの線形探索地獄
衝突が発生した場合、Zend Engineは同一バケット内に複数の `Bucket` をチェイン（連結リスト）で繋ぐか、あるいはリニアプロービングに近い挙動をとる。
正常時のハッシュテーブルのルックアップコストは $O(1)$ だ。しかし、すべてのキーが単一のバケットに集中（最悪のハッシュ衝突）した場合、ルックアップコストは $O(N)$ へと劣化する。
数万件のキーを持つリクエストを処理するだけで、CPU使用率は100%に張り付き、FPMワーカープロセスは完全にロックアップする。これが Hash DoS攻撃（PHPにおけるArray Hash Collision Vulnerability） の本質である。
Zend VMによる防御策：シード値（Hash Seed）の導入
この脆弱性に対し、現代のPHP（PHP 7, 8系）では、プロセス起動時（あるいはリクエストライフサイクル初期）にランダムなシード値（`HT_HASH_SEED`）を生成し、ハッシュ計算にミックスするアプローチをとっている。
// 疑似的なシード適用ハッシュ計算
zend_ulong hash = zend_hash_seed ^ 5381;
for (size_t i = 0; i < len; i++) {
hash = ((hash << 5) + hash) + str[i];
}
これにより、攻撃者は事前にローカル環境で衝突するキーのペアを計算したとしても、標的サーバーのランダムシードが不明であるため、外部から予測してハッシュ衝突を意図的に引き起こすことが極めて困難になっている。
---
4. OPcacheとプロセスのメモリ共有空間におけるHashTable
この堅牢な `HashTable` は、OPcacheのプリローディング（Preloading）やSHM（共有メモリ）上でも重要な役割を果たしている。
OPcacheが有効な環境では、スクリプトのパース結果やコンパイル済みOpcodeだけでなく、定数やクラスのシンボルテーブル（これも内部的には `zend_string` をキーとした `HashTable`）が共有メモリに配置される。
[ Shared Memory (SHM) ]
├── OPcache Shared Memory Segment
│ ├── Opcode Arrays (Zend OPcache)
│ └── Interned Strings Buffer (同一文字列のメモリ重複排除)
│ └── Immutable Hash Tables (不変のクラス・関数シンボルテーブル)
└── 各FPM Worker Process (Private Memory)
├── Request-scoped Hash Tables (ローカル変数、$_POST配列など)
└── Execution Stack / Zend VM Context
特筆すべきは Interned Strings（インターン化文字列） の存在だ。PHPソースコードやリクエスト内で頻出する文字列（キー名や関数名）は、一度メモリ上にハッシュ化されて共有バッファに固定化される。これにより、配列のキー比較が `strcmp`（文字列比較）ではなく、ポインタの比較（あるいはハッシュ値の直接比較） で完結するため、Zend VMの実行効率は極限まで高められている。
—
5. 【実証】PHPコードから低レイヤの挙動をハックする
では、この `HashTable` の挙動や、衝突耐性の限界をエンジニア自身の目で確認するためのコードを提示しよう。以下のスクリプトは、大量のキー挿入時におけるPHPのメモリ割り当てとスケーリング挙動を観測するものである。
/
declare(strict_types=1);
if (php_sapi_name() !== ‘cli’) {
exit(“Run via CLI only.\n”);
}
// 測定開始前のメモリ使用量
$initialMemory = memory_get_usage(true);
$startTime = microtime(true);
$hashTable = [];
$iterations = 100_000;
// 連番の文字列キーを挿入（ハッシュテーブルの動的拡張とRehashを発生させる）
for ($i = 0; $i < $iterations; $i++) {
// プレフィックスを付けることでインターン化を避け、動的なキー生成を行う
$key = 'key_prefix_' . md5((string)$i);
$hashTable[$key] = $i;
}
$endMemory = memory_get_usage(true);
$endTime = microtime(true);
echo "--- HashTable Metrics ---\n";
echo "挿入要素数: " . number_format($iterations) . "\n";
echo "消費メモリ (実質): " . number_format($endMemory - $initialMemory) . " bytes\n";
echo "1要素あたりの平均メモリコスト: " . round(($endMemory - $initialMemory) / $iterations, 2) . " bytes\n";
echo "処理時間: " . number_format($endTime - $startTime, 4) . " 秒\n";
// Zend内部のバケットアロケーションの仕組み上、
// 配列のサイズが2のN乗を超えるタイミングで再ハッシュ（Rehash）が発生する。
このコードが示す低レイヤの真実
通常の連想配列に大量の要素を突っ込むと、Zend Engineは内部の `nTableSize` を動的に倍増（Power-of-two allocation）させ、既存のすべての要素を新しいバケット配列に再配置（Rehash）する。このコストは決してゼロではない。
ホットパス（毎秒何万回も実行されるループ内）で巨大な配列を動的に構築・破棄する設計は、Zend VMに不必要なRehashコストとガベージコレクションの負荷を強いることになるため、あらかじめ `SplFixedArray` を利用するか、配列の事前サイズ見積もりを行うべきである。
—
6. チーフアーキテクトからの提言：セキュアかつ高速なシステム設計のために
PHPの `HashTable` とハッシュ関数の挙動を理解することは、単なるトリビアではない。
1. 外部入力をそのまま配列のキーにしない: ユーザーからの入力を連想配列のキーとして動的に大量生成する場合、論理的なメモリ枯渇や予期せぬパフォーマンス低下を招くリスク（DoS）を常に念頭に置くこと。
2. PHPのバージョンアップの重要性: 古いPHPバージョンでは、ハッシュシードのランダム化が不十分であったり、既知の脆弱性が放置されている場合がある。常に最新のセキュリティパッチが適用されたPHPエンジンを使用せよ。
3. データ構造の適材適所: 高頻度なルックアップや厳密な型・順序が求められるコンテキストでは、通常のPHP配列の特性を理解した上で、SPLデータ構造や外部キャッシュ（Redis等）へのオフロードを arquitetura（設計）レベルで選択すること。
Zend VMの内部構造を掌中に収めた者だけが、真にスケーラブルで堅牢なPHPアプリケーションのアーキテクチャを構築できる。コードの向こう側にあるC言語のメモリ領域とCPUの挙動を常に想像し続けよ。