打了一下Codeforces Round 891 (Div. 3)，赛后看到F题的赛时通过解答被叉（hack）了一大把，非常好奇为啥，所以笔者在hack phase结束之后看了一下这些hack数据的hack点是什么，发现大多数都是叉unordered_map的。这又让我想起刚开始打cf的时候在某场Div. 4中使用了unordered_map结果在hack phase被叉的惨痛经历，然后我突然就想以牙还牙，以后也要叉别人的unordered_map，于是就有了这篇文章。

unordered_map 和 map 的工作原理

在Codeforces比赛中，我们通常会选择map而不是unordered_map，尽管map上的插入和查找操作的时间复杂度是$O(log\ N)$的，而unordered_map的插入和查找操作却是均摊$O(1)$的。为什么我们要做这种令人费解的时间复杂度牺牲？原因就在于哈希表的内部工作原理使得它可能被轻易地攻击。

map

根据Cpp Reference的说明：

1
2
3
4
std::map is a sorted associative container that contains key-value pairs with unique keys. 
Keys are sorted by using the comparison function Compare. Search, removal, 
and insertion operations have logarithmic complexity. 
Maps are usually implemented as Red–black trees.

map内的键是有序的，并且使用模板中给出的Compare函数排序。而且map通常会使用红黑树实现，因此可以保持$O(log\ N)$的时间复杂度，比较稳定。

unordered_map

unordered_map是哈希表，它通过给定的哈希函数，将键的hash值（整数）计算出来，并且这个hash值是均匀地分布在$[0,+\infty)$区间内的。这样元素的hash值能较少地发生冲突。但是我们的空间不是无穷大的，而且hash值难免会有冲突，因此我们通常会开辟一块有一定大小的空间，其中的每一个位置都作为一个bucket（桶），所有键的hash值都对桶的个数取模，然后把键值对作为一个节点放进对应的桶里面。因此，一个桶里面可能会有几个不同的键。插入或查找元素时，都会根据键计算桶的位置，然后尝试找到这个桶里面确实与当前键相同的一个节点。在数据十分随机，hash函数优秀的情况下，我们几乎不会遇到冲突（一个桶里面的节点很少），操作的均摊复杂度为$O(1)$

对unordered_map的攻击分析

unordered_map的均摊复杂度是在数据足够随机的情况下得出的，而在Codeforces比赛的hack phase中攻击者往往不会进行随机的数据生成，而是根据提交者的代码有意制造hack testcase，从而达到攻击的目的。而不幸的是，你使用的unordered_map很有可能就是一个hacker的突破口。它可能会使得你的程序在hack phase中verdict变成tl(time limit)。

攻击原理

unordered_map中的bucket list并不总是初始长度，而是随着它内部存储的键值对数量逐渐扩大。在rehash阶段，哈希表的桶数量可能会发生改变，然后把原有的元素放到新的这组桶里面去，如果我们能够构造一组数据，使得unordered_map在某次resize后，很多（甚至全部）元素都挤到同一个桶里面去，那么unordered_map的操作复杂度就会大幅度上升，甚至达到单次操作$O(N)$的水平，这样你原本认为是$O(N)$的程序就变成了$O(N^2)$水平！在$2e5$的数据下，这下不得不拿下tl的verdict了。
因此，攻击者在知晓你的hash函数和哈希表实现的情况下，可以刻意制造许多hash冲突，让哈希表内部的某个或某几个bucket爆满，达到攻击的目的。

对GCC中unordered_map实现的分析

打开unordered_map.h，查看class unordered_map的内容，可以发现它内部使用一个名为_M_h的_Hashtable类型变量完成大部分操作，注意到还有一句typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;，我们继续追踪__umap_hashtable的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
template<typename _Key,
    typename _Tp,
    typename _Hash = hash<_Key>,
    typename _Pred = std::equal_to<_Key>,
    typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
    typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>>
using __ummap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
                    _Alloc, __detail::_Select1st,
                    _Pred, _Hash,
                    __detail::_Mod_range_hashing,
                    __detail::_Default_ranged_hash,
                    __detail::_Prime_rehash_policy, _Tr>;

__detail这个namespace下有一些关于哈希表的细节实现，我们注意到，__detail::_Mod_range_hashing和__detail::_Prime_rehash_policy很重要，很有可能是关于内部如何计算bucket index和控制rehash的。追踪到hashtable_policy.h

__detail::_Mod_range_hashing

1
2
3
4
5
6
7
8
9
10
11
12
13
/// Default range hashing function: use division to fold a large number
/// into the range [0, N).
struct _Mod_range_hashing
{
typedef std::size_t first_argument_type;
typedef std::size_t second_argument_type;
typedef std::size_t result_type;

result_type
operator()(first_argument_type __num,
        second_argument_type __den) const noexcept
{ return __num % __den; }
};

这是默认的hash函数，把定义unordered_map时提供的用户hash函数的较大的结果折叠到$[0, N)$的范围，也就是桶索引的区间。

__detail::_Prime_rehash_policy

1
2
3
/// Default value for rehash policy.  Bucket size is (usually) the
/// smallest prime that keeps the load factor small enough.
struct _Prime_rehash_policy

它控制Rehash策略，桶个数通常时使得负载因子足够小的最小的质数。负载因子其实就是当前键值对的数量除以桶的个数，这个struct在初始化时就提供了一个最大负载因子的参数，且默认为1.0f。负载因子足够小，也就是保证当前负载因子小于设定的最大负载因子。同时，这个文件中也包含了_M_bkt_for_elements函数的实现，就是键值对个数除以最大负载因子。还有一个很重要的参数：

1
static const std::size_t _S_growth_factor = 2;

大小增长因子，resize之后的大小至少是之前的两倍。
这个结构体中有两个函数_M_need_rehash和_M_next_bkt其实现位于hashtable_c++0x.cc。_M_next_bkt中返回的总是质数，并且有一个质数表__prime_list，其具体内容位于hashtable_aux.h。

回到_Hashtable和std::hash

在_Hashtable中查找几个函数被调用的位置，结合以上几个函数的具体实现，在最大负载因子为默认的1.0时，该unordered_map的实现总是将桶大小设为某个质数，并且是__prime_list中的某个质数。而std::hash中预先为几种整数类型实现的哈希函数就是返回identity，加上前面__detail::_Mod_range_hashing的取模运算放入bucket中。我们可以测试__prime_list中的质数，不断使用常数$C$加上该质数$P$倍数的键$C+i*P$插入到unordered_map中。如果unordered_map能够在某次rehash中将桶大小设为这个质数，我们的攻击就会成功（当然，这个质数应该较大，否则它很快就会被另一个质数代替了，也不能使高复杂度的操作持续多久）。

攻击开始

筛选的部分质数

我们针对$2e5$的数据，挑选了部分说不定能被攻击成功的质数：

1
2
3
4
5
6
7
8
9
long long nums[] = {
        5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
        11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
        19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
        33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
        57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
        99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
        159871ul, 172933ul, 187091ul, 202409ul
};

利用Custom Invocation测试

Codeforces上有Custom Invocation功能，可以不向任何题目提交但在评测机上执行自己代码的测试，而且运行时限高达15秒，我们写一段模拟哈希冲突攻击的代码，对GCC中的unordered_map进行测试。但是上面的质数太多了，我们不想分多次测试，需要利用上面的_S_growth_factor=2的性质，先找到小的，再推算较大的。因为下一个必然是第一个大于前一个卡点的两倍的质数。
我们利用如下代码跑一些不至于超出15s时限的小型测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>

using il = long long;
using namespace std;

constexpr int N = 2e5;
void insert_numbers(il x) {
    clock_t begin = clock();
    unordered_map<il, int> numbers;

    for (int i = 1; i <= N; i++)
        numbers[i * x] = i;

    il sum = 0;

    for (auto &entry : numbers)
        sum += (entry.first / x) * entry.second;

    printf("x = %lld: %.3lf secs\n", x, (double) (clock() - begin) / CLOCKS_PER_SEC, sum);
}

void solve() {
    long long nums[] = {
            5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul, 11113ul, 12011ul,
            12983ul, 14033ul, 15173ul, 16411ul, 17749ul, 19183ul, 20753ul, 22447ul,
    };
    for (auto &x : nums) {
        insert_numbers(x);
    }
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), std::ios::sync_with_stdio(false);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

由于测试数据较多，我们只选取在某个编译器版本出现了异常的测试结果如下：

编译器 6427 7517 10273 12983 15173 20753
GNU G++14 6.4.0 0.015s 0.092s 0.016s 0.015s 0.268s 0.015s
GNU G++17 7.3.0 0.046s 0.015s 0.015s 0.173s 0.015s 0.016s
GNU G++17 9.2.0 (64bit, msys2) 0.020s 0.183s 0.032s 0.016s 0.633s 0.015s
GNU G++20 11.2.0 (64bit, winlibs) 0.015s 0.015s 0.313s 0.031s 0.031s 1.205s

根据_S_growth_factor，从__prime_list取得的较大的可攻击素数以及攻击结果如下：

编译器 素数 运行状态
GNU G++14 6.4.0 126271 3.217s
GNU G++17 7.3.0 107897 3.387s
GNU G++17 9.2.0 (64bit, msys2) 126271 tl
GNU G++20 11.2.0 (64bit, winlibs) 172933 tl

其中运行状态为tl的表示运行时间超过15s，Codeforces已停止继续执行该代码。

对非64bit的情况分析

两个标明是64bit的编译器都得到了tl的运行结果，为什么另外两个编译器产生的代码却没有时间超限？
使用Custom Invocation运行cout << sizeof(std::size_t);，发现未标明64bit的编译器均为32bit。而我们hash函数返回的正是std::size_t。因此在hash时，我们的部分数值因为超出了32bit整数可表示的范围，内置hash函数产生的结果并不是我们选择的质数的倍数，导致这些数值被分进了其他的bucket中，我们增加部分判断：

1
2
3
uint32_t performHash(il p) {
    return static_cast<uint32_t>(p);
}

修改insertNumbers的代码，对溢出的值做一点小操作：

1
2
3
4
5
6
7
8
9
10
bool x86 = sizeof(std::size_t) == 4;
int k = 0;
for (int i = 1; i <= N; i++) {
    il value = i * x + k;
    if (x86 && performHash(value) % x != k) {
        il rest = performHash(value) % x;
        value += (k - rest);
    }
    numbers[value] = i;
}

结果在两个32bit编译器上也发生了tl运行结果。

攻击小结

利用GCC中的unordered_map特性，我们可以较容易地针对编译器版本选择素数进行攻击。
上面的运行时间其实95%以上都是插入键值对的时间，因为使用迭代器遍历哈希表中的键值对的复杂度总是$O(n)$的，而实际攻击中构造的特定查询会更加耗时，在多数题目时限小于6s的情况下我们可以通过这种手段攻击成功。此外还需要注意待攻击的代码中是否修改了max_load_factor配置，这可能导致我们选择用于攻击的素数发生变化。如果是32bit编译器，还要注意hash时可能发生的溢出，修正我们生成的数据。

另一种攻击法

unordered_map提供了bucket_count方法，我们可以在hack generator中根据这个数值不断构造输入数据，只要我们generator选择的编译器和待攻击的代码的编译器相同，就可以达到攻击效果。例如这份Hack Generator

使我们的哈希表变安全

此处的详细信息请参考neal在Codeforces上的博文。使用基于评测时间的随机数和splitmix64算法作为我们的自定义哈希函数，避免被攻击：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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);
    }
};

然后，将custom_hash添加到我们的unordered_map：

1
unordered_map<long long, int, custom_hash> safe_map;

就可以防御住较多的攻击。

参考资料：