Dave Malcolm <dmalc...@redhat.com> added the comment:
On Fri, 2012-01-20 at 22:55 +0000, Dave Malcolm wrote:
> Dave Malcolm <dmalc...@redhat.com> added the comment:
>
> On Fri, 2012-01-06 at 12:52 +0000, Marc-Andre Lemburg wrote:
> > Marc-Andre Lemburg <m...@egenix.com> added the comment:
> >
> > Demo patch implementing the collision limit idea for Python 2.7.
> >
> > ----------
> > Added file: http://bugs.python.org/file24151/hash-attack.patch
> >
>
> Marc: is this the latest version of your patch?
>
> Whether or not we go with collision counting and/or adding a random salt
> to hashes and/or something else, I've had a go at updating your patch
>
> Although debate on python-dev seems to have turned against the
> collision-counting idea, based on flaws reported by Frank Sievertsen
> http://mail.python.org/pipermail/python-dev/2012-January/115726.html
> it seemed to me to be worth at least adding some test cases to flesh out
> the approach. Note that the test cases deliberately avoid containing
> "hostile" data.
I had a brainstorm, and I don't yet know if the following makes sense,
but here's a crude patch with another approach, which might get around
the issues Frank raises.
Rather than count the number of equal-hash collisions within each call
to lookdict, instead keep a per-dict count of the total number of
iterations through the probe sequence (regardless of the hashing),
amortized across all calls to lookdict, and if it looks like we're going
O(n^2) rather than O(n), raise an exception. Actually, that's not quite
it, but see below...
We potentially have 24 words of per-dictionary storage hiding in the
ma_smalltable area within PyDictObject, which we can use when ma_mask >=
PyDict_MINSIZE (when mp->ma_table != mp->ma_smalltable), without
changing sizeof(PyDictObject) and thus breaking ABI. I hope there isn't
any code out there that uses this space. (Anyone know of any?)
This very crude patch uses that area to add per-dict tracking of the
total number of iterations spent probing for a free PyDictEntry whilst
constructing the dictionary. It rules that if we've gone more than (32
* ma_used) iterations whilst constructing the dictionary (counted across
all ma_lookup calls), then we're degenerating into O(n^2) behavior, and
this triggers an exception. Any other usage of ma_lookup resets the
count (e.g. when reading values back). I picked the scaling factor of
32 from out of the air; I hope there's a smarter threshold.
I'm assuming that an attack scenario tends to involve a dictionary that
goes through a construction phase (which the attacker is aiming to
change from O(N) to O(N^2)), and then a usage phase, whereas there are
other patterns of dictionary usage in which insertion and lookup are
intermingled for which this approach wouldn't raise an exception.
This leads to exceptions like this:
AlgorithmicComplexityError: dict construction used 4951 probes for 99
entries at key 99 with hash 42
(i.e. the act of constructing a dict with 99 entries required traversing
4951 PyDictEntry slots, suggesting someone is sending deliberately
awkward data).
Seems to successfully handle both the original DoS and the second
scenario in Frank's email. I don't have a reproducer for the first of
Frank's scenarios, but in theory it ought to handle it. (I hope!)
Have seen two failures within python test suite from this, which I hope
can be fixed by tuning the thresholds and the reset events (they seem to
happen when a large dict is emptied).
May have a performance impact, but I didn't make any attempt to optimize
it (beyond picking a power of two for the scaling factor).
(There may be random bits of the old patch thrown in; sorry)
Thoughts? (apart from "ugh! it's ugly!" yes I know - it's late here)
Dave
----------
Added file:
http://bugs.python.org/file24288/amortized-probe-counting-dmalcolm-2012-01-20-002.patch
_______________________________________
Python tracker <rep...@bugs.python.org>
<http://bugs.python.org/issue13703>
_______________________________________
diff -r 3be60a4c8c63 Include/pyerrors.h
--- a/Include/pyerrors.h Fri Jan 20 11:01:06 2012 -0500
+++ b/Include/pyerrors.h Fri Jan 20 22:11:43 2012 -0500
@@ -207,6 +207,8 @@
PyAPI_DATA(PyObject *) PyExc_BytesWarning;
PyAPI_DATA(PyObject *) PyExc_ResourceWarning;
+PyAPI_DATA(PyObject *) PyExc_AlgorithmicComplexityError;
+
/* Convenience functions */
diff -r 3be60a4c8c63 Lib/test/test_dict.py
--- a/Lib/test/test_dict.py Fri Jan 20 11:01:06 2012 -0500
+++ b/Lib/test/test_dict.py Fri Jan 20 22:11:43 2012 -0500
@@ -3,6 +3,8 @@
import collections, random, string
import gc, weakref
+import sys
+import time
class DictTest(unittest.TestCase):
@@ -757,6 +759,196 @@
self._tracked(MyDict())
+# Support classes for HashCollisionTests:
+class ChosenHash:
+ """
+ Use this to create arbitrary collections of keys that are non-equal
+ but have equal hashes, without needing to include hostile data
+ within the test suite.
+ """
+ def __init__(self, variability, hash):
+ self.variability = variability
+ self.hash = hash
+
+ def __eq__(self, other):
+ # The variability field is used to handle non-equalness:
+ return self.variability == other.variability
+
+ def __hash__(self):
+ return self.hash
+
+ def __repr__(self):
+ return 'ChosenHash(%r, %r)' % (self.variability,
+ self.hash)
+
+class Timer:
+ """
+ Simple way to measure time elapsed during a test case
+ """
+ def __init__(self):
+ self.starttime = time.time()
+
+ def get_elapsed_time(self):
+ """Get elapsed time in seconds as a float"""
+ curtime = time.time()
+ return curtime - self.starttime
+
+ def elapsed_time_as_str(self):
+ """Get elapsed time as a string (with units)"""
+ return '%0.3f seconds' % self.get_elapsed_time()
+
+class TookTooLong(RuntimeError):
+ def __init__(self, timelimit, elapsed, itercount=None):
+ self.timelimit = timelimit
+ self.elapsed = elapsed
+ self.itercount = itercount
+
+ def __str__(self):
+ result = 'took >= %s seconds' % self.timelimit
+ if self.itercount is not None:
+ result += (' (%0.3f seconds elapsed after %i iterations)'
+ % (self.elapsed, self.itercount))
+ else:
+ result += ' (%0.3f seconds elapsed)' % self.elapsed
+ return result
+
+# Some of the tests involve constructing large dictionaries. How big
+# should they be?
+ITEM_COUNT = 1000000
+
+# Arbitrary threshold (in seconds) for a "reasonable amount of time"
+# that it should take to work with ITEM_COUNT items:
+TIME_LIMIT = 5
+
+class _FasterThanContext(object):
+ """
+ A context manager for implementing assertFasterThan
+ """
+ def __init__(self, test_case, **kwargs):
+ self.test_case = test_case
+ if 'seconds' in kwargs:
+ self.timelimit = kwargs['seconds']
+ else:
+ raise ValueError()
+
+ def __enter__(self):
+ self.timer = Timer()
+ return self
+
+ def __exit__(self, exc_type, exc_value, tb):
+ if exc_type is not None:
+ # let unexpected exceptions pass through
+ return
+
+ if 1:
+ print('timer within %s took %s'
+ % (self.test_case, self.timer.elapsed_time_as_str()))
+
+ def handle(self, callable_obj, args, kwargs):
+ """
+ If callable_obj is None, assertRaises/Warns is being used as a
+ context manager, so check for a 'msg' kwarg and return self.
+ If callable_obj is not None, call it passing args and kwargs.
+ """
+ if callable_obj is None:
+ self.msg = kwargs.pop('msg', None)
+ return self
+ with self:
+ callable_obj(*args, **kwargs)
+
+ def check_for_timeout(self, itercount):
+ """
+ Allow directly checking for timeouts from within a loop, supplying
+ an iteration count. If the timer has elapsed, this will raise a
+ TookTooLong exception, indicating how many iterations were completed
+ when the time limit was reached. Otherwise, it does nothing.
+ """
+ elapsed_time = self.timer.get_elapsed_time()
+ if elapsed_time > self.timelimit:
+ raise TookTooLong(self.timelimit,
+ elapsed_time,
+ itercount)
+
+@support.cpython_only
+class HashCollisionTests(unittest.TestCase):
+ """
+ Issue 13703: tests about the behavior of dicts in the face of hostile data
+ """
+
+ def assertFasterThan(self, callableObj=None, *args, **kwargs):
+ context = _FasterThanContext(self, *args, **kwargs)
+ return context.handle(callableObj, args, kwargs)
+
+ def test_timings_with_benign_data(self):
+ # Verify that inserting many keys into a dict only takes a few seconds
+ d = dict()
+ with self.assertFasterThan(seconds=TIME_LIMIT) as cm:
+ for i in range(ITEM_COUNT):
+ d[i] = 0
+
+ # Verify that we can also retrieve the values quickly:
+ with self.assertFasterThan(seconds=TIME_LIMIT) as cm:
+ d[i]
+
+ # Verify that we can quickly insert the same item many times
+ # (overwriting each time):
+ d = dict()
+ with self.assertFasterThan(seconds=TIME_LIMIT) as cm:
+ for i in range(ITEM_COUNT):
+ d[0] = 0
+
+ def test_not_reaching_limit(self):
+ # Ensure that we can insert equal-hashed keys up to (but not reaching)
+ # the collision climit:
+ with self.assertFasterThan(seconds=TIME_LIMIT) as cm:
+ d = dict()
+ for i in range(50):
+ key = ChosenHash(i, 42)
+ d[key] = 0
+
+ def test_reaching_collision_limit(self):
+ """
+ Ensure that too many non-equal keys with the same hash lead to a
+ TooManyCollisions exception
+ """
+ with self.assertFasterThan(seconds=TIME_LIMIT) as cm:
+ with self.assertRaisesRegex(AlgorithmicComplexityError,
+ ('dict construction used 2049 probes'
+ ' for 64 entries'
+ ' at key ChosenHash\(64, 42\)'
+ ' with hash 42')):
+ d = dict()
+ for i in range(1000):
+ key = ChosenHash(i, 42)
+ d[key] = 0
+
+ # Frank Sievertsen found scenarios in which the collision-counting
+ # scheme could be attacked:
+ # http://mail.python.org/pipermail/python-dev/2012-January/115726.html
+
+ def test_scenario_b_from_Frank_Sievertsen(self):
+ d = dict()
+
+ with self.assertFasterThan(seconds=TIME_LIMIT) as cm:
+ with self.assertRaisesRegex(AlgorithmicComplexityError,
+ ('dict construction used 2049 probes'
+ ' for 64 entries'
+ ' at key ChosenHash\(64, 42\)'
+ ' with hash 42')):
+ # Insert hash collisions up to (but not reaching) the proposed
+ # limit:
+ for i in range(1000):
+ key = ChosenHash(i, 42)
+ d[key] = 0
+ cm.check_for_timeout(i)
+
+ # Now try to add many equal values that collide
+ # with the hash, and see how long it takes
+ for i in range(ITEM_COUNT):
+ key = ChosenHash(0, 42)
+ d[key] = 0
+ cm.check_for_timeout(i)
+
from test import mapping_tests
class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
@@ -771,6 +963,7 @@
def test_main():
support.run_unittest(
DictTest,
+ HashCollisionTests,
GeneralMappingTests,
SubclassMappingTests,
)
diff -r 3be60a4c8c63 Objects/dictobject.c
--- a/Objects/dictobject.c Fri Jan 20 11:01:06 2012 -0500
+++ b/Objects/dictobject.c Fri Jan 20 22:11:43 2012 -0500
@@ -10,6 +10,29 @@
#include "Python.h"
#include "stringlib/eq.h"
+#define Py_MAX_AVERAGE_PROBES_PER_INSERT 32
+/* power-of-two to make multiplication fast */
+
+/* For large dictionaries, reuse the space allocated for ma_smalltable */
+typedef struct _Py_LargeDictFields {
+ size_t iter_count;
+} _Py_LargeDictFields;
+
+#define PyDict_LARGEDICTFIELDS(mp) \
+ ((_Py_LargeDictFields*)&(mp)->ma_smalltable)
+/* FIXME: add assert(mp->ma_table != mp->ma_smalltable) */
+
+static int is_inserting = 0;
+
+static void reset_iter_count(PyDictObject *mp)
+{
+ if (mp->ma_mask >= PyDict_MINSIZE) {
+ assert(mp->ma_table != mp->ma_smalltable);
+ PyDict_LARGEDICTFIELDS(mp)->iter_count = 0;
+ }
+}
+
+
/* Set a key error with the specified argument, wrapping it in a
* tuple automatically so that tuple keys are not unpacked as the
@@ -25,6 +48,22 @@
Py_DECREF(tup);
}
+/* Set a AlgorithmicComplexityError error */
+static void
+set_algorithmic_complexity_error(PyDictObject *mp, PyObject *key, Py_hash_t
hash)
+{
+ PyErr_Format(PyExc_AlgorithmicComplexityError,
+ ("dict construction used %i probes for %i entries"
+ " at key %R with hash %zd"),
+ PyDict_LARGEDICTFIELDS(mp)->iter_count, mp->ma_used,
+ key, hash);
+ /* Backporting notes: (FIXME)
+ %R is a Python 3-ism
+ %zd is for Py_ssize_t, which in Python 3 is the same as Py_hash_t
+ */
+}
+
+
/* Define this out if you don't want conversion statistics on exit. */
#undef SHOW_CONVERSION_COUNTS
@@ -358,6 +397,11 @@
freeslot = NULL;
}
+ /* This is a non-insertion probe: reset the cost-of-insertion count: */
+ if (!is_inserting) {
+ reset_iter_count(mp);
+ }
+
/* In the loop, me_key == dummy is by far (factor of 100s) the
least likely outcome, so test for that last. */
for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
@@ -389,6 +433,15 @@
}
else if (ep->me_key == dummy && freeslot == NULL)
freeslot = ep;
+
+ if (is_inserting && mask >= PyDict_MINSIZE) {
+ assert(mp->ma_table != mp->ma_smalltable);
+ if (++PyDict_LARGEDICTFIELDS(mp)->iter_count
+ > (mp->ma_used * Py_MAX_AVERAGE_PROBES_PER_INSERT) ) {
+ set_algorithmic_complexity_error(mp, key, hash);
+ return NULL;
+ }
+ }
}
assert(0); /* NOT REACHED */
return 0;
@@ -437,6 +490,11 @@
freeslot = NULL;
}
+ /* This is a non-insertion probe: reset the cost-of-insertion count: */
+ if (!is_inserting) {
+ reset_iter_count(mp);
+ }
+
/* In the loop, me_key == dummy is by far (factor of 100s) the
least likely outcome, so test for that last. */
for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
@@ -451,6 +509,14 @@
return ep;
if (ep->me_key == dummy && freeslot == NULL)
freeslot = ep;
+ if (is_inserting && mask >= PyDict_MINSIZE) {
+ assert(mp->ma_table != mp->ma_smalltable);
+ if (++PyDict_LARGEDICTFIELDS(mp)->iter_count
+ > (mp->ma_used * Py_MAX_AVERAGE_PROBES_PER_INSERT) ) {
+ set_algorithmic_complexity_error(mp, key, hash);
+ return NULL;
+ }
+ }
}
assert(0); /* NOT REACHED */
return 0;
@@ -532,7 +598,9 @@
typedef PyDictEntry *(*lookupfunc)(PyDictObject *, PyObject *, Py_hash_t);
assert(mp->ma_lookup != NULL);
+ is_inserting = 1;
ep = mp->ma_lookup(mp, key, hash);
+ is_inserting = 0;
if (ep == NULL) {
Py_DECREF(key);
Py_DECREF(value);
@@ -675,8 +743,15 @@
/* else key == value == NULL: nothing to do */
}
- if (is_oldtable_malloced)
+ if (is_oldtable_malloced) {
PyMem_DEL(oldtable);
+ } else {
+ if (mp->ma_table != mp->ma_smalltable) {
+ /* clean ma_smalltable for use as _Py_LargeDictFields: */
+ memset(mp->ma_smalltable, 0, sizeof(mp->ma_smalltable));
+ }
+ }
+
return 0;
}
diff -r 3be60a4c8c63 Objects/exceptions.c
--- a/Objects/exceptions.c Fri Jan 20 11:01:06 2012 -0500
+++ b/Objects/exceptions.c Fri Jan 20 22:11:43 2012 -0500
@@ -2205,6 +2205,12 @@
SimpleExtendsException(PyExc_Warning, ResourceWarning,
"Base class for warnings about resource usage.");
+/*
+ * AlgorithmicComplexityError extends BaseException
+ */
+SimpleExtendsException(PyExc_BaseException, AlgorithmicComplexityError,
+ "Base class for warnings about computationally-infeasible data.");
+
/* Pre-computed RuntimeError instance for when recursion depth is reached.
@@ -2318,6 +2324,7 @@
PRE_INIT(UnicodeWarning)
PRE_INIT(BytesWarning)
PRE_INIT(ResourceWarning)
+ PRE_INIT(AlgorithmicComplexityError)
/* OSError subclasses */
PRE_INIT(ConnectionError);
@@ -2399,6 +2406,7 @@
POST_INIT(UnicodeWarning)
POST_INIT(BytesWarning)
POST_INIT(ResourceWarning)
+ POST_INIT(AlgorithmicComplexityError)
if (!errnomap) {
errnomap = PyDict_New();
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
