HashDoS を可視化する PHP 拡張 hashtable_dump 書いた2011 年の年末に HashDoS というのが話題になった. Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 要するにハッシュテーブルのキーのハッシュ値を意図的に衝突させ, 非効率な挿入を行わせることで, 効率的にサービスを妨害する, というものだ. ということをドヤ顔で書いてはいるが, 年末の時点ではこの HashDoS の原理については理解しておらず, 「データ構造を偏らせて計算量を増やすんだろう」ぐらいの漠然としたイメージしか無かった. その後, PHP の HashTable 構造体や, 一般的なハッシュテーブルの実装について調べることで, HashDoS の原理がわかってきた. ハッシュテーブルについては, いくつかの解説ページを見ながら, サンプルコードを Ruby に翻訳することで学習した. アルゴリズムとデータ構造編 第１４章 ハッシュ探
