This article is a translation of the following,
neal's blog: Blowing up unordered_map, and how to stop getting hacked on it
Neal, thank you for a very interesting article.
この記事はnealの記事の翻訳です。また、DeepLを多分に活用しています。ありがとうございます。
はじめに
初期のC++バージョンからstd::set と std::mapを使うことができます。これらは便利ではありますが、ツリー型のデータ構造体で管理されているため、各操作(挿入、消去、アクセスなど)に時間がかかります。ついにC++11では、ツリーではなくハッシュで管理するstd::unordered_setと std::unordered_mapが使えるようになりました。これらは通常、高速なアクセスを提供しますが、Codeforcesではこれらを使ったsubmitがハッキングされたり、システムテストでTLEする例を見ます。この記事では、これらがどのように攻撃され、逆に、ハッキングされることを気にせずに使うためにはどのように対策ができるのかを説明します。
まず、どのようにして攻撃されるのでしょう？私たちは、ハッシュの操作の計算量は$O(1)$であると仮定しています。これは、入力がランダムであり、ハッシュの衝突がランダムに発生すると仮定できる場合は妥当な仮定です。しかし、ハッキングフェイズなどの敵意を持つ相手が入力を設計している場合はどうでしょうか？我々のハッシュ関数の仕組みを相手が熟知している場合、意図的なハッシュを衝突させるような入力を生成して最悪$O(n^2)$の計算量となることがあるのです。
ハッシュ攻撃の実際
実際にunordered_mapでどのように意図的な衝突を引き起こせるか調べてみましょう。まず、私たちは実装を知る必要があります。GitHub上でgccの実装で見ていきます。
まず、unordered_map.h(Githubリンク)を見ると__detail::_Mod_range_hashingと__detail::_Prime_rehash_policyを利用しているとわかります。つまり、unordered_mapは入力値のハッシュを素数でmodし、その値をハッシュテーブルのインデックスとしてに使っているようです。
_Prime_rehash_policy を追いかけると hashtable_c++0x.cc(Githubリンク)にたどり着きます。ハッシュテーブルはそのサイズが大きくなると、別の場所で定義されている__prime_list配列を参照して次のサイズを決定し変更することがわかります。このリストはhashtable-aux.cc(githubリンク)にあります。
さて、unordered_mapで使うハッシュ関数を理解しなければなりません。std::hashを使用しています。このハッシュ関数を理解すればn^2の衝突を起こすために、リストのような値を挿入すればよいかわかります。先ほど、予め定義されている__prime_listを見ましたが、ある値が使われるにはmapがこれらの値を使うようにリサイズされなければなりません。用いられる値はコンパイラのバージョンに依存します。gcc 6 以前のバージョンでは126271、gcc 7 以降では 107897 で動作します。以下のコードをCodeforcesのCustom Invocationで実行して、どのような出力が得られるか見てみましょう。
(訳注: このテストは手元で実行してももちろんかまいません。ただし、Codeforcesの環境で攻撃を行うならば、Codeforcesの環境を知らなければなりません)
#include <ctime>
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 2e5;
void insert_numbers(long long x) {
clock_t begin = clock();
unordered_map<long long, int> numbers;
for (int i = 1; i <= N; i++)
numbers[i * x] = i;
long long sum = 0;
for (auto &entry : numbers)
sum += (entry.first / x) * entry.second;
printf("x = %lld: %.3lf seconds, sum = %lld\n", x, (double) (clock() - begin) / CLOCKS_PER_SEC, sum);
}
int main() {
insert_numbers(85229ul); // AtCoder C++20, C++23 gcc12.2, MojaCoder killer
insert_numbers(107897);// CodeForces C++11, C++14 killer
insert_numbers(126271);// CodeForces C++17 killer
}
訳注: 参考
C++11
x = 107897: 0.043 seconds, sum = 2666686666700000
x = 126271: 3.004 seconds, sum = 2666686666700000
C++14
x = 107897: 0.042 seconds, sum = 2666686666700000
x = 126271: 2.923 seconds, sum = 2666686666700000
C++17
x = 107897: 3.257 seconds, sum = 2666686666700000
x = 126271: 0.016 seconds, sum = 2666686666700000
MSC++17 (いずれの素数とも違うテーブルのようで両方高速に動作します)
x = 107897: 0.040 seconds, sum = 2666686666700000
x = 126271: 0.040 seconds, sum = 2666686666700000
これらの2つの数値のうちの1つは他のものよりも明らかに長い時間がかかるはずです。他にも(訳注:要素の数に応じて)いくつかの値が使えます。
cc_hash_tableやgp_hash_tableのような他のハッシュテーブル(Chilliの投稿参照)は、衝突を発生させるのがより簡単です。これらのハッシュテーブルは計算に累乗のmodを使っているので、衝突の発生にmod 2^16の数をたくさん挿入するだけで良いです。
ハッシュ衝突攻撃のハッキングから身を守る方法
それではどのようにすればハッシュを攻撃から守れるのでしょうか？unordered_map(だけでなくgp_hash_tableなども)には自作のハッシュ関数に渡すことができます。ここで与える関数は以下のように定義します。
struct custom_hash {
size_t operator()(uint64_t x) const {
return x;
}
};
さて、計算が確定しており処理が予測可能なハッシュ関数は、リバースエンジニアリングして衝突を引き起こすことが容易です。これを防ぐために最初に思い浮かぶアイデアは、高精度クロックの値を利用して(訳注: 時間を利用して)非決定な処理にすることです。
struct custom_hash {
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return x + FIXED_RANDOM;
}
};
しかし、これは十分ではありません。私(neal)の記事my post on making randomized solutions unhackableを見てください。上のコードは、全てに全く同じを関数に加えています。これでは、ある2つの数aとbが$a = b (mod m)$を満たすとき、$a + x = b + x (mod m)$となります。これだけではなく、似たような問題が単純なハッシュ関数では発生します。例えば、適当な奇数するハッシュ計算は乗算すると($2^64$のオーバーフローを発生させる)、$mod p$を満たす可能性がありますが、 gp_hash_tableでは2の累乗を用いているため問題となります。
では、以下のようなハッシュ関数はどうでしょうか？
struct custom_hash {
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
x ^= FIXED_RANDOM;
return x ^ (x >> 16);
}
};
例えばgp_hash_table を使用している場合、この関数はハッキングを受けます。(1 << 16) + 1, (2 << 16) + 2, (3 << 16) + 3, ...をこのハッシュテーブルに挿入すると、すべてのハッシュの出力は$mod 2^{16}$となります。(なぜかわかりますか？)
理想的なハッシュ関数は、入力ビットを変更すると出力ビットを変更する確率が半々になることです。先ほどの x + FIXED_RANDOM は、この要件を全く満していません。入力の値のある上位ビットを変更したとしても、出力でそれより下位のビットが変更する確率は0です。
私は、非常に高速で高品質なsplitmix64(splitmix64.cへのリンク)を使うのが好きです。これを用いると、安全なカスタムハッシュ関数ができあがります。
#include <chrono>
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
これで、次のように unordered_mapや gp_hash_table を定義することができるようになりました。
unordered_map<long long, int, custom_hash> safe_map;
gp_hash_table<long long, int, custom_hash> safe_hash_table;
上記のプログラムでこれらを使用すると、非常に速く実行されます。
x = 107897: 0.035sec、sum = 2666686666700000
x = 126271: 0.031sec、sum = 2666686666700000
(again): This article is a translation of the following,
neal's blog: Blowing up unordered_map, and how to stop getting hacked on it