3 年前の年末を騒がせた hashdos というセキュリティ問題を覚えているでしょうか。
これは特定のプログラミング言語を対象にしたものではなく、連想配列の実装に問題があった場合、リクエストパラメータ等から意図的にキーが偏った変数が生成され、ベストケースでは O(1) となる探索の計算量を O(N) とし、それによって DoS 攻撃を行う、というものでした。

特定の言語を対象にしたものではない、とは書きましたが、中にはこれを回避している言語もありました。
Ruby や Perl ではあるバージョン以降はハッシュ生成をランダム化することで、こういった問題を意図的に起こせないようになっていました。

一方、PHP はそういった作りにはなっておらず、リクエストパラメータの最大量を制限するなど、対処療法的な対策しか行うことができませんでした。

この頃の PHP の stable は 5.3 系だったと記憶していますが、その後のバージョンにおいてどうなっているかを検証しました。

hashdos については以下の資料が参考になるでしょう。

hashtable_dump

hashtable_dump というのは、当時私が HashDoS で問題とされた、連想配列のキーの偏りを可視化するために作った PHP 拡張です。
PHP 拡張といっても、実際のプログラム内で使ったり、他のライブラリ等と組み合わせあり、といったことは一切考えてないものです。
PHP における array は C レベルでは HashTable という構造体として実装されており、その中のキーの偏りを以下のように出力します。

<?php
hashtable_dump(array(1, 2, 3));
/*
nTableSize:       8
nTableMask:       7
nNumOfElements:   3
nNextFreeElement: 3
pListHead:        0
pListTail:        2
**arBuckets:
  0 => [0, NULL]
  1 => [1, NULL]
  2 => [2, NULL]
  3 => [NULL]
  4 => [NULL]
  5 => [NULL]
  6 => [NULL]
  7 => [NULL]
*/

**arBuckets というのが、HashTable においてキーと値のペアを保持する Bucket 構造体へのポインタの配列です。
この配列は 0 ~ 7 の 8 つスロットを持っています。

ここで [0, NULL] や [NULL] として表現しているのは、Bucket のキーだけで、値は含まれません。
ここではスロット 0 にキー 0、スロット 1 にキー 1、スロット 2 にキー 2、という感じに等しく配分されています。
[NULL] となっているスロットには一つも値 (Bucket) が格納されていないことを示します。

PHP の Bucket 構造体 (5.x まで)

Bucket はキーと値のペアであるだけでなく、スロット内における前後の Bucket へのポインタを持った、双方向リストとしての側面もあります。
キーから計算されるハッシュ値が重複した場合は、同一スロット内でぞれぞれの Bucket が連結されます。
探索時にはキーから計算されるハッシュ値を元にスロットを決定し、そのスロット内の Bucket の中でキーが一致するものが見つかるまで探索します。

hashdos を試す

上記のように、通常は無造作に配列を生成しても、Bucket は各スロットに概ねおしなべて振り分けられます。
ですが、この振り分け方は予想ができるので、意図的に偏らせることができてしまう、というのがこの hashdos です。

PHP においては、以下のような関数を使えば、任意の要素数で、キーの偏った array を生成できます。

function hashdos($n) {
    $tableSize = 8;
    while ($tableSize < $n) {
        $tableSize *= 2;
    }
    $arr = array();
    for ($i = 0; $i < $n; $i++) {
        $arr[$tableSize * $i] = NULL;
    }
    return $arr;
}

これ使って生成した array を hashtable_dump() してみましょう。
なお、これは PHP 5.3 を使用しています。

$arr = hashdos(8);
var_dump($arr);
/*
array(8) {
  [0]=>
  NULL
  [8]=>
  NULL
  [16]=>
  NULL
  [24]=>
  NULL
  [32]=>
  NULL
  [40]=>
  NULL
  [48]=>
  NULL
  [56]=>
  NULL
}
*/

hashtable_dump($arr);
/*
nTableSize:       8
nTableMask:       7
nNumOfElements:   8
nNextFreeElement: 57
pListHead:        0
pListTail:        56
**arBuckets:
  0 => [56, 48, 40, 32, 24, 16, 8, 0, NULL]
  1 => [NULL]
  2 => [NULL]
  3 => [NULL]
  4 => [NULL]
  5 => [NULL]
  6 => [NULL]
  7 => [NULL]
*/

全てのキーが単一のスロットに偏りました。

いろいろなバージョンで試してみる

元々 hashtable_dump を作った時点では PHP 5.3 で試していましたが、その後のバージョンではどうなっているでしょうか。

今回はこれらを確認するのに Docker を使いました。
PHP 拡張のビルドには phpize コマンド等を使う必要がありますが、これは実行する PHP と Zend API のバージョンを揃える必要があり、何気に面倒です。
Docker を使えば、それぞれのバージョンの環境をなるべく速く (少なくとも Docker Image が手元にキャッシュできてれば) 調達できるので、こういう場合に便利です。

Docker がインストールできていれば、以下のように試せます。
なお、Mac で boot2docker により Docker をインストールした環境を想定しています。

$ git clone git@github.com:yuya-takeyama/hashtable_dump.git
$ cd hashtable_dump
$ sh run_in_docker.sh 5.3
# hashtable_dump のビルドが始まり、完了後に test.php を実行する

このようにすることで、Docker Hub Registry 公式の PHP リポジトリから、指定したバージョンの Docker Image を取得し、docker run によりリポジトリ内の test.php を実行します。

docker run により PHP の各バージョンでテストを実行する方法については以下の記事で詳しく書いています。

Docker で特定のバージョンの PHP でのテストをおもむろに実行する

ここでは test.php を以下のように書き換えて実行します。

<?php
dl('hashtable_dump.so');

$cases = array(
    hashdos(8),
);

foreach ($cases as $case) {
    var_dump($case);
    echo PHP_EOL;

    hashtable_dump($case);
    echo "----------", PHP_EOL, PHP_EOL;
}

function hashdos($n) {
    $tableSize = 8;
    while ($tableSize < $n) {
        $tableSize *= 2;
    }
    $arr = array();
    for ($i = 0; $i < $n; $i++) {
        $arr[$tableSize * $i] = NULL;
    }
    return $arr;
}

以下は各バージョンの実行結果です。

5.3

さっきもやった通り偏ってます。

nTableSize:       8
nTableMask:       7
nNumOfElements:   8
nNextFreeElement: 57
pListHead:        0
pListTail:        56
**arBuckets:
  0 => [56, 48, 40, 32, 24, 16, 8, 0, NULL]
  1 => [NULL]
  2 => [NULL]
  3 => [NULL]
  4 => [NULL]
  5 => [NULL]
  6 => [NULL]
  7 => [NULL]

5.4

特に変わらないですね...

nTableSize:       8
nTableMask:       7
nNumOfElements:   8
nNextFreeElement: 57
pListHead:        0
pListTail:        56
**arBuckets:
  0 => [56, 48, 40, 32, 24, 16, 8, 0, NULL]
  1 => [NULL]
  2 => [NULL]
  3 => [NULL]
  4 => [NULL]
  5 => [NULL]
  6 => [NULL]
  7 => [NULL]

5.5

これも変わらず...

nTableSize:       8
nTableMask:       7
nNumOfElements:   8
nNextFreeElement: 57
pListHead:        0
pListTail:        56
**arBuckets:
  0 => [56, 48, 40, 32, 24, 16, 8, 0, NULL]
  1 => [NULL]
  2 => [NULL]
  3 => [NULL]
  4 => [NULL]
  5 => [NULL]
  6 => [NULL]
  7 => [NULL]

5.6

最新の stable。これも変わりなし...

nTableSize:       8
nTableMask:       7
nNumOfElements:   8
nNextFreeElement: 57
pListHead:        0
pListTail:        56
**arBuckets:
  0 => [56, 48, 40, 32, 24, 16, 8, 0, NULL]
  1 => [NULL]
  2 => [NULL]
  3 => [NULL]
  4 => [NULL]
  5 => [NULL]
  6 => [NULL]
  7 => [NULL]

まとめ

最近の PHP においても hashdos の対策は何らされていないことがわかりました。
設定による対処療法が必要なようです。

なお、PHP7 については HashTable の構造が大きく変わっているため、現状の hashable_dump では検証することができません。
PHP7 でどうなっているか、についても正月休み中に検証できればとは思いますが、今日はここまで。

最近の PHP の hashdos を検証する

hashtable_dump

PHP の Bucket 構造体 (5.x まで)

hashdos を試す

いろいろなバージョンで試してみる

5.3

5.4

5.5

5.6

まとめ