<html>
<head>
<base href="https://bugs.llvm.org/">
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW - unordered_map and unordered_set operator== double key comparison causes exponential behavior"
href="https://bugs.llvm.org/show_bug.cgi?id=42761">42761</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>unordered_map and unordered_set operator== double key comparison causes exponential behavior
</td>
</tr>
<tr>
<th>Product</th>
<td>libc++
</td>
</tr>
<tr>
<th>Version</th>
<td>9.0
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>All
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>enhancement
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>All Bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedclangbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>terrelln@fb.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org, mclow.lists@gmail.com
</td>
</tr></table>
<p>
<div>
<pre>When unordered_map or unordered_set has a nested unordered_{map,set} as a key,
operator== becomes exponential in the depth of the nesting. This is because
unordered_{map,set}::operator== does two key comparisons, one in find() using
key_eq() and one when comparing the key-value pairs using the key’s operator==.
These two comparisons can theoretically be different but are almost always the
same in practice. unordered_{map,set} should only do one key comparison in
operator== to avoid this. It is also generally more efficient even in the
non-nesting cases.
Nathan Bronson helped create a minimal repro below that demonstrates this
exponential behavior.
#include <unordered_set>
#include <cassert>
#include <memory>
struct Nested;
struct NestedHash {
std::size_t operator()(Nested const& n) const;
};
struct Nested {
std::unique_ptr<std::unordered_set<Nested, NestedHash>> set;
explicit Nested(int depth)
: set(std::make_unique<std::unordered_set<Nested, NestedHash>>()) {
if (depth > 0) {
set->emplace(depth - 1);
}
}
};
std::size_t NestedHash::operator()(Nested const& n) const {
std::size_t rv = 1;
for (auto& k : *n.set) {
rv += operator()(k);
}
return rv;
}
bool operator==(Nested const& lhs, Nested const& rhs) {
return *lhs.set == *rhs.set;
}
bool operator!=(Nested const& lhs, Nested const& rhs) {
return !(lhs == rhs);
}
void testNestedSetEquality() {
auto n1 = Nested(100);
auto n2 = Nested(100);
auto n3 = Nested(99);
assert(n1 == n1);
assert(n1 == n2);
assert(n1 != n3);
}
This is a contrived example, but this shows up in practice in
folly::dynamic::operator== [1] as a worst case exponential algorithm. No one
will create objects like this intentionally, but they can be produced with
folly::parseJson() [2] when non-string keys are allowed. If an attacker
controlled the input to parseJson() they could easily DDOS the machine with a
payload like "{{{{{0:0}:0}:0}:0}:0}" but nested 100 layers deep instead of 5.
unordered_map and unordered_set should only do one key comparison per item in
operator==. This is possible [3] because it is undefined behavior to call the
containers operator== if the key’s operator== isn’t a refinement of key_eq().
Fixing this bug in unordered_map and unordered_set avoids the exponential
behavior with nested keys, and it is generally more efficient even in the
non-nesting cases. An implementation of set and map equality with only one key
comparison is included below, thanks to Nathan Bronson.
template <typename S>
bool eqSet(S const& lhs, S const& rhs) {
if (lhs.size() != rhs.size()) {
return false;
}
for (auto& v : lhs) {
auto slot = rhs.bucket(v);
auto b = rhs.begin(slot);
auto e = rhs.end(slot);
while (b != e && !(*b == v)) {
++b;
}
if (b == e) {
return false;
}
}
return true;
}
template <typename M>
bool eqMap(M const& lhs, M const& rhs) {
if (lhs.size() != rhs.size()) {
return false;
}
for (auto& v : lhs) {
auto slot = rhs.bucket(v.first);
auto b = rhs.begin(slot);
auto e = rhs.end(slot);
while (b != e && !(b->first == v.first)) {
++b;
}
if (b == e || !(b->second == v.second)) {
return false;
}
}
return true;
}
[1] <a href="https://github.com/facebook/folly/blob/master/folly/dynamic.cpp#L113">https://github.com/facebook/folly/blob/master/folly/dynamic.cpp#L113</a>
[2] <a href="https://github.com/facebook/folly/blob/master/folly/json.h#L194">https://github.com/facebook/folly/blob/master/folly/json.h#L194</a>
[3]
<a href="https://github.com/facebook/folly/commit/11855c21b21fb46fe1004de8c0412dd94eb5c45f">https://github.com/facebook/folly/commit/11855c21b21fb46fe1004de8c0412dd94eb5c45f</a></pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>