+++ /dev/null
-from test.test_support import verbose, TESTFN\r
-import random\r
-import os\r
-\r
-# From SF bug #422121: Insecurities in dict comparison.\r
-\r
-# Safety of code doing comparisons has been an historical Python weak spot.\r
-# The problem is that comparison of structures written in C *naturally*\r
-# wants to hold on to things like the size of the container, or "the\r
-# biggest" containee so far, across a traversal of the container; but\r
-# code to do containee comparisons can call back into Python and mutate\r
-# the container in arbitrary ways while the C loop is in midstream. If the\r
-# C code isn't extremely paranoid about digging things out of memory on\r
-# each trip, and artificially boosting refcounts for the duration, anything\r
-# from infinite loops to OS crashes can result (yes, I use Windows <wink>).\r
-#\r
-# The other problem is that code designed to provoke a weakness is usually\r
-# white-box code, and so catches only the particular vulnerabilities the\r
-# author knew to protect against. For example, Python's list.sort() code\r
-# went thru many iterations as one "new" vulnerability after another was\r
-# discovered.\r
-#\r
-# So the dict comparison test here uses a black-box approach instead,\r
-# generating dicts of various sizes at random, and performing random\r
-# mutations on them at random times. This proved very effective,\r
-# triggering at least six distinct failure modes the first 20 times I\r
-# ran it. Indeed, at the start, the driver never got beyond 6 iterations\r
-# before the test died.\r
-\r
-# The dicts are global to make it easy to mutate tham from within functions.\r
-dict1 = {}\r
-dict2 = {}\r
-\r
-# The current set of keys in dict1 and dict2. These are materialized as\r
-# lists to make it easy to pick a dict key at random.\r
-dict1keys = []\r
-dict2keys = []\r
-\r
-# Global flag telling maybe_mutate() whether to *consider* mutating.\r
-mutate = 0\r
-\r
-# If global mutate is true, consider mutating a dict. May or may not\r
-# mutate a dict even if mutate is true. If it does decide to mutate a\r
-# dict, it picks one of {dict1, dict2} at random, and deletes a random\r
-# entry from it; or, more rarely, adds a random element.\r
-\r
-def maybe_mutate():\r
- global mutate\r
- if not mutate:\r
- return\r
- if random.random() < 0.5:\r
- return\r
-\r
- if random.random() < 0.5:\r
- target, keys = dict1, dict1keys\r
- else:\r
- target, keys = dict2, dict2keys\r
-\r
- if random.random() < 0.2:\r
- # Insert a new key.\r
- mutate = 0 # disable mutation until key inserted\r
- while 1:\r
- newkey = Horrid(random.randrange(100))\r
- if newkey not in target:\r
- break\r
- target[newkey] = Horrid(random.randrange(100))\r
- keys.append(newkey)\r
- mutate = 1\r
-\r
- elif keys:\r
- # Delete a key at random.\r
- mutate = 0 # disable mutation until key deleted\r
- i = random.randrange(len(keys))\r
- key = keys[i]\r
- del target[key]\r
- del keys[i]\r
- mutate = 1\r
-\r
-# A horrid class that triggers random mutations of dict1 and dict2 when\r
-# instances are compared.\r
-\r
-class Horrid:\r
- def __init__(self, i):\r
- # Comparison outcomes are determined by the value of i.\r
- self.i = i\r
-\r
- # An artificial hashcode is selected at random so that we don't\r
- # have any systematic relationship between comparison outcomes\r
- # (based on self.i and other.i) and relative position within the\r
- # hash vector (based on hashcode).\r
- self.hashcode = random.randrange(1000000000)\r
-\r
- def __hash__(self):\r
- return 42\r
- return self.hashcode\r
-\r
- def __cmp__(self, other):\r
- maybe_mutate() # The point of the test.\r
- return cmp(self.i, other.i)\r
-\r
- def __eq__(self, other):\r
- maybe_mutate() # The point of the test.\r
- return self.i == other.i\r
-\r
- def __repr__(self):\r
- return "Horrid(%d)" % self.i\r
-\r
-# Fill dict d with numentries (Horrid(i), Horrid(j)) key-value pairs,\r
-# where i and j are selected at random from the candidates list.\r
-# Return d.keys() after filling.\r
-\r
-def fill_dict(d, candidates, numentries):\r
- d.clear()\r
- for i in xrange(numentries):\r
- d[Horrid(random.choice(candidates))] = \\r
- Horrid(random.choice(candidates))\r
- return d.keys()\r
-\r
-# Test one pair of randomly generated dicts, each with n entries.\r
-# Note that dict comparison is trivial if they don't have the same number\r
-# of entires (then the "shorter" dict is instantly considered to be the\r
-# smaller one, without even looking at the entries).\r
-\r
-def test_one(n):\r
- global mutate, dict1, dict2, dict1keys, dict2keys\r
-\r
- # Fill the dicts without mutating them.\r
- mutate = 0\r
- dict1keys = fill_dict(dict1, range(n), n)\r
- dict2keys = fill_dict(dict2, range(n), n)\r
-\r
- # Enable mutation, then compare the dicts so long as they have the\r
- # same size.\r
- mutate = 1\r
- if verbose:\r
- print "trying w/ lengths", len(dict1), len(dict2),\r
- while dict1 and len(dict1) == len(dict2):\r
- if verbose:\r
- print ".",\r
- if random.random() < 0.5:\r
- c = cmp(dict1, dict2)\r
- else:\r
- c = dict1 == dict2\r
- if verbose:\r
- print\r
-\r
-# Run test_one n times. At the start (before the bugs were fixed), 20\r
-# consecutive runs of this test each blew up on or before the sixth time\r
-# test_one was run. So n doesn't have to be large to get an interesting\r
-# test.\r
-# OTOH, calling with large n is also interesting, to ensure that the fixed\r
-# code doesn't hold on to refcounts *too* long (in which case memory would\r
-# leak).\r
-\r
-def test(n):\r
- for i in xrange(n):\r
- test_one(random.randrange(1, 100))\r
-\r
-# See last comment block for clues about good values for n.\r
-test(100)\r
-\r
-##########################################################################\r
-# Another segfault bug, distilled by Michael Hudson from a c.l.py post.\r
-\r
-class Child:\r
- def __init__(self, parent):\r
- self.__dict__['parent'] = parent\r
- def __getattr__(self, attr):\r
- self.parent.a = 1\r
- self.parent.b = 1\r
- self.parent.c = 1\r
- self.parent.d = 1\r
- self.parent.e = 1\r
- self.parent.f = 1\r
- self.parent.g = 1\r
- self.parent.h = 1\r
- self.parent.i = 1\r
- return getattr(self.parent, attr)\r
-\r
-class Parent:\r
- def __init__(self):\r
- self.a = Child(self)\r
-\r
-# Hard to say what this will print! May vary from time to time. But\r
-# we're specifically trying to test the tp_print slot here, and this is\r
-# the clearest way to do it. We print the result to a temp file so that\r
-# the expected-output file doesn't need to change.\r
-\r
-f = open(TESTFN, "w")\r
-print >> f, Parent().__dict__\r
-f.close()\r
-os.unlink(TESTFN)\r
-\r
-##########################################################################\r
-# And another core-dumper from Michael Hudson.\r
-\r
-dict = {}\r
-\r
-# Force dict to malloc its table.\r
-for i in range(1, 10):\r
- dict[i] = i\r
-\r
-f = open(TESTFN, "w")\r
-\r
-class Machiavelli:\r
- def __repr__(self):\r
- dict.clear()\r
-\r
- # Michael sez: "doesn't crash without this. don't know why."\r
- # Tim sez: "luck of the draw; crashes with or without for me."\r
- print >> f\r
-\r
- return repr("machiavelli")\r
-\r
- def __hash__(self):\r
- return 0\r
-\r
-dict[Machiavelli()] = Machiavelli()\r
-\r
-print >> f, str(dict)\r
-f.close()\r
-os.unlink(TESTFN)\r
-del f, dict\r
-\r
-\r
-##########################################################################\r
-# And another core-dumper from Michael Hudson.\r
-\r
-dict = {}\r
-\r
-# let's force dict to malloc its table\r
-for i in range(1, 10):\r
- dict[i] = i\r
-\r
-class Machiavelli2:\r
- def __eq__(self, other):\r
- dict.clear()\r
- return 1\r
-\r
- def __hash__(self):\r
- return 0\r
-\r
-dict[Machiavelli2()] = Machiavelli2()\r
-\r
-try:\r
- dict[Machiavelli2()]\r
-except KeyError:\r
- pass\r
-\r
-del dict\r
-\r
-##########################################################################\r
-# And another core-dumper from Michael Hudson.\r
-\r
-dict = {}\r
-\r
-# let's force dict to malloc its table\r
-for i in range(1, 10):\r
- dict[i] = i\r
-\r
-class Machiavelli3:\r
- def __init__(self, id):\r
- self.id = id\r
-\r
- def __eq__(self, other):\r
- if self.id == other.id:\r
- dict.clear()\r
- return 1\r
- else:\r
- return 0\r
-\r
- def __repr__(self):\r
- return "%s(%s)"%(self.__class__.__name__, self.id)\r
-\r
- def __hash__(self):\r
- return 0\r
-\r
-dict[Machiavelli3(1)] = Machiavelli3(0)\r
-dict[Machiavelli3(2)] = Machiavelli3(0)\r
-\r
-f = open(TESTFN, "w")\r
-try:\r
- try:\r
- print >> f, dict[Machiavelli3(2)]\r
- except KeyError:\r
- pass\r
-finally:\r
- f.close()\r
- os.unlink(TESTFN)\r
-\r
-del dict\r
-del dict1, dict2, dict1keys, dict2keys\r