Lib/test/test_mutants.py

   1 from test.test_support import verbose, TESTFN
   2 import random
   3 import os
   4
   5 # From SF bug #422121:  Insecurities in dict comparison.
   6
   7 # Safety of code doing comparisons has been an historical Python weak spot.
   8 # The problem is that comparison of structures written in C *naturally*
   9 # wants to hold on to things like the size of the container, or "the
  10 # biggest" containee so far, across a traversal of the container; but
  11 # code to do containee comparisons can call back into Python and mutate
  12 # the container in arbitrary ways while the C loop is in midstream.  If the
  13 # C code isn't extremely paranoid about digging things out of memory on
  14 # each trip, and artificially boosting refcounts for the duration, anything
  15 # from infinite loops to OS crashes can result (yes, I use Windows <wink>).
  16 #
  17 # The other problem is that code designed to provoke a weakness is usually
  18 # white-box code, and so catches only the particular vulnerabilities the
  19 # author knew to protect against.  For example, Python's list.sort() code
  20 # went thru many iterations as one "new" vulnerability after another was
  21 # discovered.
  22 #
  23 # So the dict comparison test here uses a black-box approach instead,
  24 # generating dicts of various sizes at random, and performing random
  25 # mutations on them at random times.  This proved very effective,
  26 # triggering at least six distinct failure modes the first 20 times I
  27 # ran it.  Indeed, at the start, the driver never got beyond 6 iterations
  28 # before the test died.
  29
  30 # The dicts are global to make it easy to mutate tham from within functions.
  31 dict1 = {}
  32 dict2 = {}
  33
  34 # The current set of keys in dict1 and dict2.  These are materialized as
  35 # lists to make it easy to pick a dict key at random.
  36 dict1keys = []
  37 dict2keys = []
  38
  39 # Global flag telling maybe_mutate() whether to *consider* mutating.
  40 mutate = 0
  41
  42 # If global mutate is true, consider mutating a dict.  May or may not
  43 # mutate a dict even if mutate is true.  If it does decide to mutate a
  44 # dict, it picks one of {dict1, dict2} at random, and deletes a random
  45 # entry from it; or, more rarely, adds a random element.
  46
  47 def maybe_mutate():
  48     global mutate
  49     if not mutate:
  50         return
  51     if random.random() < 0.5:
  52         return
  53
  54     if random.random() < 0.5:
  55         target, keys = dict1, dict1keys
  56     else:
  57         target, keys = dict2, dict2keys
  58
  59     if random.random() < 0.2:
  60         # Insert a new key.
  61         mutate = 0   # disable mutation until key inserted
  62         while 1:
  63             newkey = Horrid(random.randrange(100))
  64             if newkey not in target:
  65                 break
  66         target[newkey] = Horrid(random.randrange(100))
  67         keys.append(newkey)
  68         mutate = 1
  69
  70     elif keys:
  71         # Delete a key at random.
  72         mutate = 0   # disable mutation until key deleted
  73         i = random.randrange(len(keys))
  74         key = keys[i]
  75         del target[key]
  76         del keys[i]
  77         mutate = 1
  78
  79 # A horrid class that triggers random mutations of dict1 and dict2 when
  80 # instances are compared.
  81
  82 class Horrid:
  83     def __init__(self, i):
  84         # Comparison outcomes are determined by the value of i.
  85         self.i = i
  86
  87         # An artificial hashcode is selected at random so that we don't
  88         # have any systematic relationship between comparison outcomes
  89         # (based on self.i and other.i) and relative position within the
  90         # hash vector (based on hashcode).
  91         self.hashcode = random.randrange(1000000000)
  92
  93     def __hash__(self):
  94         return 42
  95         return self.hashcode
  96
  97     def __cmp__(self, other):
  98         maybe_mutate()   # The point of the test.
  99         return cmp(self.i, other.i)
 100
 101     def __eq__(self, other):
 102         maybe_mutate()   # The point of the test.
 103         return self.i == other.i
 104
 105     def __repr__(self):
 106         return "Horrid(%d)" % self.i
 107
 108 # Fill dict d with numentries (Horrid(i), Horrid(j)) key-value pairs,
 109 # where i and j are selected at random from the candidates list.
 110 # Return d.keys() after filling.
 111
 112 def fill_dict(d, candidates, numentries):
 113     d.clear()
 114     for i in xrange(numentries):
 115         d[Horrid(random.choice(candidates))] = \
 116             Horrid(random.choice(candidates))
 117     return d.keys()
 118
 119 # Test one pair of randomly generated dicts, each with n entries.
 120 # Note that dict comparison is trivial if they don't have the same number
 121 # of entires (then the "shorter" dict is instantly considered to be the
 122 # smaller one, without even looking at the entries).
 123
 124 def test_one(n):
 125     global mutate, dict1, dict2, dict1keys, dict2keys
 126
 127     # Fill the dicts without mutating them.
 128     mutate = 0
 129     dict1keys = fill_dict(dict1, range(n), n)
 130     dict2keys = fill_dict(dict2, range(n), n)
 131
 132     # Enable mutation, then compare the dicts so long as they have the
 133     # same size.
 134     mutate = 1
 135     if verbose:
 136         print "trying w/ lengths", len(dict1), len(dict2),
 137     while dict1 and len(dict1) == len(dict2):
 138         if verbose:
 139             print ".",
 140         if random.random() < 0.5:
 141             c = cmp(dict1, dict2)
 142         else:
 143             c = dict1 == dict2
 144     if verbose:
 145         print
 146
 147 # Run test_one n times.  At the start (before the bugs were fixed), 20
 148 # consecutive runs of this test each blew up on or before the sixth time
 149 # test_one was run.  So n doesn't have to be large to get an interesting
 150 # test.
 151 # OTOH, calling with large n is also interesting, to ensure that the fixed
 152 # code doesn't hold on to refcounts *too* long (in which case memory would
 153 # leak).
 154
 155 def test(n):
 156     for i in xrange(n):
 157         test_one(random.randrange(1, 100))
 158
 159 # See last comment block for clues about good values for n.
 160 test(100)
 161
 162 ##########################################################################
 163 # Another segfault bug, distilled by Michael Hudson from a c.l.py post.
 164
 165 class Child:
 166     def __init__(self, parent):
 167         self.__dict__['parent'] = parent
 168     def __getattr__(self, attr):
 169         self.parent.a = 1
 170         self.parent.b = 1
 171         self.parent.c = 1
 172         self.parent.d = 1
 173         self.parent.e = 1
 174         self.parent.f = 1
 175         self.parent.g = 1
 176         self.parent.h = 1
 177         self.parent.i = 1
 178         return getattr(self.parent, attr)
 179
 180 class Parent:
 181     def __init__(self):
 182         self.a = Child(self)
 183
 184 # Hard to say what this will print!  May vary from time to time.  But
 185 # we're specifically trying to test the tp_print slot here, and this is
 186 # the clearest way to do it.  We print the result to a temp file so that
 187 # the expected-output file doesn't need to change.
 188
 189 f = open(TESTFN, "w")
 190 print >> f, Parent().__dict__
 191 f.close()
 192 os.unlink(TESTFN)
 193
 194 ##########################################################################
 195 # And another core-dumper from Michael Hudson.
 196
 197 dict = {}
 198
 199 # Force dict to malloc its table.
 200 for i in range(1, 10):
 201     dict[i] = i
 202
 203 f = open(TESTFN, "w")
 204
 205 class Machiavelli:
 206     def __repr__(self):
 207         dict.clear()
 208
 209         # Michael sez:  "doesn't crash without this.  don't know why."
 210         # Tim sez:  "luck of the draw; crashes with or without for me."
 211         print >> f
 212
 213         return repr("machiavelli")
 214
 215     def __hash__(self):
 216         return 0
 217
 218 dict[Machiavelli()] = Machiavelli()
 219
 220 print >> f, str(dict)
 221 f.close()
 222 os.unlink(TESTFN)
 223 del f, dict
 224
 225
 226 ##########################################################################
 227 # And another core-dumper from Michael Hudson.
 228
 229 dict = {}
 230
 231 # let's force dict to malloc its table
 232 for i in range(1, 10):
 233     dict[i] = i
 234
 235 class Machiavelli2:
 236     def __eq__(self, other):
 237         dict.clear()
 238         return 1
 239
 240     def __hash__(self):
 241         return 0
 242
 243 dict[Machiavelli2()] = Machiavelli2()
 244
 245 try:
 246     dict[Machiavelli2()]
 247 except KeyError:
 248     pass
 249
 250 del dict
 251
 252 ##########################################################################
 253 # And another core-dumper from Michael Hudson.
 254
 255 dict = {}
 256
 257 # let's force dict to malloc its table
 258 for i in range(1, 10):
 259     dict[i] = i
 260
 261 class Machiavelli3:
 262     def __init__(self, id):
 263         self.id = id
 264
 265     def __eq__(self, other):
 266         if self.id == other.id:
 267             dict.clear()
 268             return 1
 269         else:
 270             return 0
 271
 272     def __repr__(self):
 273         return "%s(%s)"%(self.__class__.__name__, self.id)
 274
 275     def __hash__(self):
 276         return 0
 277
 278 dict[Machiavelli3(1)] = Machiavelli3(0)
 279 dict[Machiavelli3(2)] = Machiavelli3(0)
 280
 281 f = open(TESTFN, "w")
 282 try:
 283     try:
 284         print >> f, dict[Machiavelli3(2)]
 285     except KeyError:
 286         pass
 287 finally:
 288     f.close()
 289     os.unlink(TESTFN)
 290
 291 del dict
 292 del dict1, dict2, dict1keys, dict2keys