Benjamin Peterson | ee8712c | 2008-05-20 21:35:26 +0000 | [diff] [blame] | 1 | from test.support import verbose, TESTFN |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 2 | import random |
Tim Peters | 23cf6be | 2001-06-02 08:02:56 +0000 | [diff] [blame] | 3 | import os |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 4 | |
| 5 | # From SF bug #422121: Insecurities in dict comparison. |
| 6 | |
Tim Peters | 8c3e91e | 2001-05-10 19:40:30 +0000 | [diff] [blame] | 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* |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 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 | |
Guido van Rossum | dc5f6b2 | 2006-08-24 21:29:26 +0000 | [diff] [blame] | 30 | # The dicts are global to make it easy to mutate tham from within functions. |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 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 | |
Neal Norwitz | 2fcf206 | 2005-11-24 23:28:37 +0000 | [diff] [blame] | 39 | # Global flag telling maybe_mutate() whether to *consider* mutating. |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 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 |
Tim Peters | 4c02fec | 2001-05-10 20:18:30 +0000 | [diff] [blame] | 45 | # entry from it; or, more rarely, adds a random element. |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 46 | |
| 47 | def maybe_mutate(): |
Tim Peters | 4c02fec | 2001-05-10 20:18:30 +0000 | [diff] [blame] | 48 | global mutate |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 49 | if not mutate: |
| 50 | return |
| 51 | if random.random() < 0.5: |
| 52 | return |
Tim Peters | 4c02fec | 2001-05-10 20:18:30 +0000 | [diff] [blame] | 53 | |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 54 | if random.random() < 0.5: |
| 55 | target, keys = dict1, dict1keys |
| 56 | else: |
| 57 | target, keys = dict2, dict2keys |
Tim Peters | 4c02fec | 2001-05-10 20:18:30 +0000 | [diff] [blame] | 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. |
Armin Rigo | 57179fe | 2005-05-15 13:29:26 +0000 | [diff] [blame] | 72 | mutate = 0 # disable mutation until key deleted |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 73 | i = random.randrange(len(keys)) |
| 74 | key = keys[i] |
| 75 | del target[key] |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 76 | del keys[i] |
Armin Rigo | 57179fe | 2005-05-15 13:29:26 +0000 | [diff] [blame] | 77 | mutate = 1 |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 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 |
Tim Peters | 8c3e91e | 2001-05-10 19:40:30 +0000 | [diff] [blame] | 88 | # have any systematic relationship between comparison outcomes |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 89 | # (based on self.i and other.i) and relative position within the |
Tim Peters | 8c3e91e | 2001-05-10 19:40:30 +0000 | [diff] [blame] | 90 | # hash vector (based on hashcode). |
Guido van Rossum | dc5f6b2 | 2006-08-24 21:29:26 +0000 | [diff] [blame] | 91 | # XXX This is no longer effective. |
| 92 | ##self.hashcode = random.randrange(1000000000) |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 93 | |
| 94 | def __hash__(self): |
Guido van Rossum | dc5f6b2 | 2006-08-24 21:29:26 +0000 | [diff] [blame] | 95 | return 42 |
Thomas Wouters | 89f507f | 2006-12-13 04:49:30 +0000 | [diff] [blame] | 96 | return self.hashcode |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 97 | |
Guido van Rossum | 47b9ff6 | 2006-08-24 00:41:19 +0000 | [diff] [blame] | 98 | def __eq__(self, other): |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 99 | maybe_mutate() # The point of the test. |
Guido van Rossum | 47b9ff6 | 2006-08-24 00:41:19 +0000 | [diff] [blame] | 100 | return self.i == other.i |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 101 | |
Guido van Rossum | dc5f6b2 | 2006-08-24 21:29:26 +0000 | [diff] [blame] | 102 | def __ne__(self, other): |
| 103 | raise RuntimeError("I didn't expect some kind of Spanish inquisition!") |
| 104 | |
| 105 | __lt__ = __le__ = __gt__ = __ge__ = __ne__ |
| 106 | |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 107 | def __repr__(self): |
| 108 | return "Horrid(%d)" % self.i |
| 109 | |
| 110 | # Fill dict d with numentries (Horrid(i), Horrid(j)) key-value pairs, |
| 111 | # where i and j are selected at random from the candidates list. |
| 112 | # Return d.keys() after filling. |
| 113 | |
| 114 | def fill_dict(d, candidates, numentries): |
| 115 | d.clear() |
Guido van Rossum | 805365e | 2007-05-07 22:24:25 +0000 | [diff] [blame] | 116 | for i in range(numentries): |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 117 | d[Horrid(random.choice(candidates))] = \ |
| 118 | Horrid(random.choice(candidates)) |
Brett Cannon | ecca313 | 2007-02-21 21:59:58 +0000 | [diff] [blame] | 119 | return list(d.keys()) |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 120 | |
| 121 | # Test one pair of randomly generated dicts, each with n entries. |
| 122 | # Note that dict comparison is trivial if they don't have the same number |
| 123 | # of entires (then the "shorter" dict is instantly considered to be the |
| 124 | # smaller one, without even looking at the entries). |
| 125 | |
| 126 | def test_one(n): |
| 127 | global mutate, dict1, dict2, dict1keys, dict2keys |
| 128 | |
| 129 | # Fill the dicts without mutating them. |
| 130 | mutate = 0 |
| 131 | dict1keys = fill_dict(dict1, range(n), n) |
| 132 | dict2keys = fill_dict(dict2, range(n), n) |
| 133 | |
| 134 | # Enable mutation, then compare the dicts so long as they have the |
| 135 | # same size. |
| 136 | mutate = 1 |
| 137 | if verbose: |
Guido van Rossum | be19ed7 | 2007-02-09 05:37:30 +0000 | [diff] [blame] | 138 | print("trying w/ lengths", len(dict1), len(dict2), end=' ') |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 139 | while dict1 and len(dict1) == len(dict2): |
| 140 | if verbose: |
Guido van Rossum | be19ed7 | 2007-02-09 05:37:30 +0000 | [diff] [blame] | 141 | print(".", end=' ') |
Guido van Rossum | 47b9ff6 | 2006-08-24 00:41:19 +0000 | [diff] [blame] | 142 | c = dict1 == dict2 |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 143 | if verbose: |
Guido van Rossum | be19ed7 | 2007-02-09 05:37:30 +0000 | [diff] [blame] | 144 | print() |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 145 | |
| 146 | # Run test_one n times. At the start (before the bugs were fixed), 20 |
| 147 | # consecutive runs of this test each blew up on or before the sixth time |
| 148 | # test_one was run. So n doesn't have to be large to get an interesting |
| 149 | # test. |
| 150 | # OTOH, calling with large n is also interesting, to ensure that the fixed |
| 151 | # code doesn't hold on to refcounts *too* long (in which case memory would |
| 152 | # leak). |
| 153 | |
| 154 | def test(n): |
Guido van Rossum | 805365e | 2007-05-07 22:24:25 +0000 | [diff] [blame] | 155 | for i in range(n): |
Tim Peters | 95bf939 | 2001-05-10 08:32:44 +0000 | [diff] [blame] | 156 | test_one(random.randrange(1, 100)) |
| 157 | |
| 158 | # See last comment block for clues about good values for n. |
| 159 | test(100) |
Tim Peters | 23cf6be | 2001-06-02 08:02:56 +0000 | [diff] [blame] | 160 | |
| 161 | ########################################################################## |
Tim Peters | fa517b2 | 2001-06-02 08:18:58 +0000 | [diff] [blame] | 162 | # Another segfault bug, distilled by Michael Hudson from a c.l.py post. |
Tim Peters | 23cf6be | 2001-06-02 08:02:56 +0000 | [diff] [blame] | 163 | |
| 164 | class Child: |
| 165 | def __init__(self, parent): |
| 166 | self.__dict__['parent'] = parent |
| 167 | def __getattr__(self, attr): |
| 168 | self.parent.a = 1 |
| 169 | self.parent.b = 1 |
| 170 | self.parent.c = 1 |
| 171 | self.parent.d = 1 |
| 172 | self.parent.e = 1 |
| 173 | self.parent.f = 1 |
| 174 | self.parent.g = 1 |
| 175 | self.parent.h = 1 |
| 176 | self.parent.i = 1 |
| 177 | return getattr(self.parent, attr) |
| 178 | |
| 179 | class Parent: |
| 180 | def __init__(self): |
| 181 | self.a = Child(self) |
| 182 | |
| 183 | # Hard to say what this will print! May vary from time to time. But |
| 184 | # we're specifically trying to test the tp_print slot here, and this is |
| 185 | # the clearest way to do it. We print the result to a temp file so that |
| 186 | # the expected-output file doesn't need to change. |
| 187 | |
| 188 | f = open(TESTFN, "w") |
Guido van Rossum | be19ed7 | 2007-02-09 05:37:30 +0000 | [diff] [blame] | 189 | print(Parent().__dict__, file=f) |
Tim Peters | 23cf6be | 2001-06-02 08:02:56 +0000 | [diff] [blame] | 190 | f.close() |
| 191 | os.unlink(TESTFN) |
| 192 | |
| 193 | ########################################################################## |
| 194 | # And another core-dumper from Michael Hudson. |
| 195 | |
| 196 | dict = {} |
| 197 | |
| 198 | # Force dict to malloc its table. |
| 199 | for i in range(1, 10): |
| 200 | dict[i] = i |
| 201 | |
| 202 | f = open(TESTFN, "w") |
| 203 | |
| 204 | class Machiavelli: |
| 205 | def __repr__(self): |
| 206 | dict.clear() |
| 207 | |
| 208 | # Michael sez: "doesn't crash without this. don't know why." |
| 209 | # Tim sez: "luck of the draw; crashes with or without for me." |
Guido van Rossum | be19ed7 | 2007-02-09 05:37:30 +0000 | [diff] [blame] | 210 | print(file=f) |
Tim Peters | 23cf6be | 2001-06-02 08:02:56 +0000 | [diff] [blame] | 211 | |
Brett Cannon | 0b70cca | 2006-08-25 02:59:59 +0000 | [diff] [blame] | 212 | return repr("machiavelli") |
Tim Peters | 23cf6be | 2001-06-02 08:02:56 +0000 | [diff] [blame] | 213 | |
| 214 | def __hash__(self): |
| 215 | return 0 |
| 216 | |
| 217 | dict[Machiavelli()] = Machiavelli() |
| 218 | |
Guido van Rossum | be19ed7 | 2007-02-09 05:37:30 +0000 | [diff] [blame] | 219 | print(str(dict), file=f) |
Tim Peters | 23cf6be | 2001-06-02 08:02:56 +0000 | [diff] [blame] | 220 | f.close() |
| 221 | os.unlink(TESTFN) |
| 222 | del f, dict |
Tim Peters | 453163d | 2001-06-03 04:54:32 +0000 | [diff] [blame] | 223 | |
| 224 | |
| 225 | ########################################################################## |
| 226 | # And another core-dumper from Michael Hudson. |
| 227 | |
| 228 | dict = {} |
| 229 | |
| 230 | # let's force dict to malloc its table |
| 231 | for i in range(1, 10): |
| 232 | dict[i] = i |
| 233 | |
| 234 | class Machiavelli2: |
| 235 | def __eq__(self, other): |
| 236 | dict.clear() |
| 237 | return 1 |
| 238 | |
| 239 | def __hash__(self): |
| 240 | return 0 |
| 241 | |
| 242 | dict[Machiavelli2()] = Machiavelli2() |
| 243 | |
| 244 | try: |
| 245 | dict[Machiavelli2()] |
| 246 | except KeyError: |
| 247 | pass |
| 248 | |
| 249 | del dict |
| 250 | |
| 251 | ########################################################################## |
| 252 | # And another core-dumper from Michael Hudson. |
| 253 | |
| 254 | dict = {} |
| 255 | |
| 256 | # let's force dict to malloc its table |
| 257 | for i in range(1, 10): |
| 258 | dict[i] = i |
| 259 | |
| 260 | class Machiavelli3: |
| 261 | def __init__(self, id): |
| 262 | self.id = id |
| 263 | |
| 264 | def __eq__(self, other): |
| 265 | if self.id == other.id: |
| 266 | dict.clear() |
| 267 | return 1 |
| 268 | else: |
| 269 | return 0 |
| 270 | |
| 271 | def __repr__(self): |
| 272 | return "%s(%s)"%(self.__class__.__name__, self.id) |
| 273 | |
| 274 | def __hash__(self): |
| 275 | return 0 |
| 276 | |
| 277 | dict[Machiavelli3(1)] = Machiavelli3(0) |
| 278 | dict[Machiavelli3(2)] = Machiavelli3(0) |
| 279 | |
| 280 | f = open(TESTFN, "w") |
| 281 | try: |
| 282 | try: |
Guido van Rossum | be19ed7 | 2007-02-09 05:37:30 +0000 | [diff] [blame] | 283 | print(dict[Machiavelli3(2)], file=f) |
Tim Peters | 453163d | 2001-06-03 04:54:32 +0000 | [diff] [blame] | 284 | except KeyError: |
| 285 | pass |
| 286 | finally: |
| 287 | f.close() |
| 288 | os.unlink(TESTFN) |
| 289 | |
| 290 | del dict |
Neal Norwitz | 2fcf206 | 2005-11-24 23:28:37 +0000 | [diff] [blame] | 291 | del dict1, dict2, dict1keys, dict2keys |