Commit | Line | Data |
---|---|---|
920dae64 AT |
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() wether 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 | i = random.randrange(len(keys)) | |
73 | key = keys[i] | |
74 | del target[key] | |
75 | # CAUTION: don't use keys.remove(key) here. Or do <wink>. The | |
76 | # point is that .remove() would trigger more comparisons, and so | |
77 | # also more calls to this routine. We're mutating often enough | |
78 | # without that. | |
79 | del keys[i] | |
80 | ||
81 | # A horrid class that triggers random mutations of dict1 and dict2 when | |
82 | # instances are compared. | |
83 | ||
84 | class Horrid: | |
85 | def __init__(self, i): | |
86 | # Comparison outcomes are determined by the value of i. | |
87 | self.i = i | |
88 | ||
89 | # An artificial hashcode is selected at random so that we don't | |
90 | # have any systematic relationship between comparison outcomes | |
91 | # (based on self.i and other.i) and relative position within the | |
92 | # hash vector (based on hashcode). | |
93 | self.hashcode = random.randrange(1000000000) | |
94 | ||
95 | def __hash__(self): | |
96 | return self.hashcode | |
97 | ||
98 | def __cmp__(self, other): | |
99 | maybe_mutate() # The point of the test. | |
100 | return cmp(self.i, other.i) | |
101 | ||
102 | def __repr__(self): | |
103 | return "Horrid(%d)" % self.i | |
104 | ||
105 | # Fill dict d with numentries (Horrid(i), Horrid(j)) key-value pairs, | |
106 | # where i and j are selected at random from the candidates list. | |
107 | # Return d.keys() after filling. | |
108 | ||
109 | def fill_dict(d, candidates, numentries): | |
110 | d.clear() | |
111 | for i in xrange(numentries): | |
112 | d[Horrid(random.choice(candidates))] = \ | |
113 | Horrid(random.choice(candidates)) | |
114 | return d.keys() | |
115 | ||
116 | # Test one pair of randomly generated dicts, each with n entries. | |
117 | # Note that dict comparison is trivial if they don't have the same number | |
118 | # of entires (then the "shorter" dict is instantly considered to be the | |
119 | # smaller one, without even looking at the entries). | |
120 | ||
121 | def test_one(n): | |
122 | global mutate, dict1, dict2, dict1keys, dict2keys | |
123 | ||
124 | # Fill the dicts without mutating them. | |
125 | mutate = 0 | |
126 | dict1keys = fill_dict(dict1, range(n), n) | |
127 | dict2keys = fill_dict(dict2, range(n), n) | |
128 | ||
129 | # Enable mutation, then compare the dicts so long as they have the | |
130 | # same size. | |
131 | mutate = 1 | |
132 | if verbose: | |
133 | print "trying w/ lengths", len(dict1), len(dict2), | |
134 | while dict1 and len(dict1) == len(dict2): | |
135 | if verbose: | |
136 | print ".", | |
137 | c = cmp(dict1, dict2) | |
138 | if verbose: | |
139 | ||
140 | ||
141 | # Run test_one n times. At the start (before the bugs were fixed), 20 | |
142 | # consecutive runs of this test each blew up on or before the sixth time | |
143 | # test_one was run. So n doesn't have to be large to get an interesting | |
144 | # test. | |
145 | # OTOH, calling with large n is also interesting, to ensure that the fixed | |
146 | # code doesn't hold on to refcounts *too* long (in which case memory would | |
147 | # leak). | |
148 | ||
149 | def test(n): | |
150 | for i in xrange(n): | |
151 | test_one(random.randrange(1, 100)) | |
152 | ||
153 | # See last comment block for clues about good values for n. | |
154 | test(100) | |
155 | ||
156 | ########################################################################## | |
157 | # Another segfault bug, distilled by Michael Hudson from a c.l.py post. | |
158 | ||
159 | class Child: | |
160 | def __init__(self, parent): | |
161 | self.__dict__['parent'] = parent | |
162 | def __getattr__(self, attr): | |
163 | self.parent.a = 1 | |
164 | self.parent.b = 1 | |
165 | self.parent.c = 1 | |
166 | self.parent.d = 1 | |
167 | self.parent.e = 1 | |
168 | self.parent.f = 1 | |
169 | self.parent.g = 1 | |
170 | self.parent.h = 1 | |
171 | self.parent.i = 1 | |
172 | return getattr(self.parent, attr) | |
173 | ||
174 | class Parent: | |
175 | def __init__(self): | |
176 | self.a = Child(self) | |
177 | ||
178 | # Hard to say what this will print! May vary from time to time. But | |
179 | # we're specifically trying to test the tp_print slot here, and this is | |
180 | # the clearest way to do it. We print the result to a temp file so that | |
181 | # the expected-output file doesn't need to change. | |
182 | ||
183 | f = open(TESTFN, "w") | |
184 | print >> f, Parent().__dict__ | |
185 | f.close() | |
186 | os.unlink(TESTFN) | |
187 | ||
188 | ########################################################################## | |
189 | # And another core-dumper from Michael Hudson. | |
190 | ||
191 | dict = {} | |
192 | ||
193 | # Force dict to malloc its table. | |
194 | for i in range(1, 10): | |
195 | dict[i] = i | |
196 | ||
197 | f = open(TESTFN, "w") | |
198 | ||
199 | class Machiavelli: | |
200 | def __repr__(self): | |
201 | dict.clear() | |
202 | ||
203 | # Michael sez: "doesn't crash without this. don't know why." | |
204 | # Tim sez: "luck of the draw; crashes with or without for me." | |
205 | print >> f | |
206 | ||
207 | return `"machiavelli"` | |
208 | ||
209 | def __hash__(self): | |
210 | return 0 | |
211 | ||
212 | dict[Machiavelli()] = Machiavelli() | |
213 | ||
214 | print >> f, str(dict) | |
215 | f.close() | |
216 | os.unlink(TESTFN) | |
217 | del f, dict | |
218 | ||
219 | ||
220 | ########################################################################## | |
221 | # And another core-dumper from Michael Hudson. | |
222 | ||
223 | dict = {} | |
224 | ||
225 | # let's force dict to malloc its table | |
226 | for i in range(1, 10): | |
227 | dict[i] = i | |
228 | ||
229 | class Machiavelli2: | |
230 | def __eq__(self, other): | |
231 | dict.clear() | |
232 | return 1 | |
233 | ||
234 | def __hash__(self): | |
235 | return 0 | |
236 | ||
237 | dict[Machiavelli2()] = Machiavelli2() | |
238 | ||
239 | try: | |
240 | dict[Machiavelli2()] | |
241 | except KeyError: | |
242 | pass | |
243 | ||
244 | del dict | |
245 | ||
246 | ########################################################################## | |
247 | # And another core-dumper from Michael Hudson. | |
248 | ||
249 | dict = {} | |
250 | ||
251 | # let's force dict to malloc its table | |
252 | for i in range(1, 10): | |
253 | dict[i] = i | |
254 | ||
255 | class Machiavelli3: | |
256 | def __init__(self, id): | |
257 | self.id = id | |
258 | ||
259 | def __eq__(self, other): | |
260 | if self.id == other.id: | |
261 | dict.clear() | |
262 | return 1 | |
263 | else: | |
264 | return 0 | |
265 | ||
266 | def __repr__(self): | |
267 | return "%s(%s)"%(self.__class__.__name__, self.id) | |
268 | ||
269 | def __hash__(self): | |
270 | return 0 | |
271 | ||
272 | dict[Machiavelli3(1)] = Machiavelli3(0) | |
273 | dict[Machiavelli3(2)] = Machiavelli3(0) | |
274 | ||
275 | f = open(TESTFN, "w") | |
276 | try: | |
277 | try: | |
278 | print >> f, dict[Machiavelli3(2)] | |
279 | except KeyError: | |
280 | pass | |
281 | finally: | |
282 | f.close() | |
283 | os.unlink(TESTFN) | |
284 | ||
285 | del dict |