On Wednesday, 9 February 2022 at 21:05:47 UTC, Siarhei Siamashka
wrote:
Is the current implementation of associative arrays in D
language resistant to Denial of Service hash collision attacks?
Answering to myself. No, it isn't. Here's a simple example:
```D
import std, core.time;
const ulong n = 100000;
// Count the number of unique elements using associative array
ulong count_unique_values_assoc(const ulong[] a)
{
bool[ulong] set;
foreach (x ; a)
set[x] = true;
return set.length;
}
// Count the number of unique elements using redBlackTree
ulong count_unique_values_rbtree(const ulong[] a)
{
auto set = redBlackTree!("a<b", false, ulong)();
foreach (x ; a)
set.insert(x);
return set.length;
}
// Generate array, which triggers hash collisions in the
// current D language associative array implementation
ulong[] generate_bad_array(ulong n)
{
return iota(n).map!(x => (x << 46)).array;
}
// Benchmark associative array vs. rbtree
void run_benchmark(ulong[] a)
{
auto t1 = MonoTime.currTime;
auto result_assoc = a.count_unique_values_assoc;
auto t2 = MonoTime.currTime;
auto result_rbtree = a.count_unique_values_rbtree;
auto t3 = MonoTime.currTime;
assert(result_assoc == result_rbtree);
writefln("n=%d, unique_elements=%d, assoc time: %d ms, rbtree
time: %d ms",
a.length, result_assoc,
(t2 - t1).total!"msecs",
(t3 - t2).total!"msecs");
}
void main()
{
assert([1UL, 1UL, 2UL].count_unique_values_assoc == 2);
assert([1UL, 1UL, 2UL].count_unique_values_rbtree == 2);
writefln("== consecutive numbers ==");
n.iota.array.run_benchmark;
writefln("\n== random numbers between 0 and 99 ==");
n.iota.map!(_ => uniform(0UL, 100UL)).array.run_benchmark;
writefln("\n== adversarially constructed array ==");
n.generate_bad_array.run_benchmark;
}
```
Benchmark results using a 64-bit LDC compiler:
```
== consecutive numbers ==
n=100000, unique_elements=100000, assoc time: 11 ms, rbtree time:
20 ms
== random numbers between 0 and 99 ==
n=100000, unique_elements=100, assoc time: 2 ms, rbtree time: 4 ms
== adversarially constructed array ==
n=100000, unique_elements=100000, assoc time: 22626 ms, rbtree
time: 15 ms
```
