summaryrefslogtreecommitdiffstats
path: root/Lib/test/test_mutants.py
blob: a219450b2556e96cbd47606bacb2d2b5e62d77af (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
from test.test_support import verbose, TESTFN
import random
import os

# From SF bug #422121:  Insecurities in dict comparison.

# Safety of code doing comparisons has been an historical Python weak spot.
# The problem is that comparison of structures written in C *naturally*
# wants to hold on to things like the size of the container, or "the
# biggest" containee so far, across a traversal of the container; but
# code to do containee comparisons can call back into Python and mutate
# the container in arbitrary ways while the C loop is in midstream.  If the
# C code isn't extremely paranoid about digging things out of memory on
# each trip, and artificially boosting refcounts for the duration, anything
# from infinite loops to OS crashes can result (yes, I use Windows <wink>).
#
# The other problem is that code designed to provoke a weakness is usually
# white-box code, and so catches only the particular vulnerabilities the
# author knew to protect against.  For example, Python's list.sort() code
# went thru many iterations as one "new" vulnerability after another was
# discovered.
#
# So the dict comparison test here uses a black-box approach instead,
# generating dicts of various sizes at random, and performing random
# mutations on them at random times.  This proved very effective,
# triggering at least six distinct failure modes the first 20 times I
# ran it.  Indeed, at the start, the driver never got beyond 6 iterations
# before the test died.

# The dicts are global to make it easy to mutate tham from within functions.
dict1 = {}
dict2 = {}

# The current set of keys in dict1 and dict2.  These are materialized as
# lists to make it easy to pick a dict key at random.
dict1keys = []
dict2keys = []

# Global flag telling maybe_mutate() whether to *consider* mutating.
mutate = 0

# If global mutate is true, consider mutating a dict.  May or may not
# mutate a dict even if mutate is true.  If it does decide to mutate a
# dict, it picks one of {dict1, dict2} at random, and deletes a random
# entry from it; or, more rarely, adds a random element.

def maybe_mutate():
    global mutate
    if not mutate:
        return
    if random.random() < 0.5:
        return

    if random.random() < 0.5:
        target, keys = dict1, dict1keys
    else:
        target, keys = dict2, dict2keys

    if random.random() < 0.2:
        # Insert a new key.
        mutate = 0   # disable mutation until key inserted
        while 1:
            newkey = Horrid(random.randrange(100))
            if newkey not in target:
                break
        target[newkey] = Horrid(random.randrange(100))
        keys.append(newkey)
        mutate = 1

    elif keys:
        # Delete a key at random.
        mutate = 0   # disable mutation until key deleted
        i = random.randrange(len(keys))
        key = keys[i]
        del target[key]
        del keys[i]
        mutate = 1

# A horrid class that triggers random mutations of dict1 and dict2 when
# instances are compared.

class Horrid:
    def __init__(self, i):
        # Comparison outcomes are determined by the value of i.
        self.i = i

        # An artificial hashcode is selected at random so that we don't
        # have any systematic relationship between comparison outcomes
        # (based on self.i and other.i) and relative position within the
        # hash vector (based on hashcode).
        self.hashcode = random.randrange(1000000000)

    def __hash__(self):
        return 42
        return self.hashcode

    def __cmp__(self, other):
        maybe_mutate()   # The point of the test.
        return cmp(self.i, other.i)

    def __eq__(self, other):
        maybe_mutate()   # The point of the test.
        return self.i == other.i

    def __repr__(self):
        return "Horrid(%d)" % self.i

# Fill dict d with numentries (Horrid(i), Horrid(j)) key-value pairs,
# where i and j are selected at random from the candidates list.
# Return d.keys() after filling.

def fill_dict(d, candidates, numentries):
    d.clear()
    for i in xrange(numentries):
        d[Horrid(random.choice(candidates))] = \
            Horrid(random.choice(candidates))
    return d.keys()

# Test one pair of randomly generated dicts, each with n entries.
# Note that dict comparison is trivial if they don't have the same number
# of entires (then the "shorter" dict is instantly considered to be the
# smaller one, without even looking at the entries).

def test_one(n):
    global mutate, dict1, dict2, dict1keys, dict2keys

    # Fill the dicts without mutating them.
    mutate = 0
    dict1keys = fill_dict(dict1, range(n), n)
    dict2keys = fill_dict(dict2, range(n), n)

    # Enable mutation, then compare the dicts so long as they have the
    # same size.
    mutate = 1
    if verbose:
        print "trying w/ lengths", len(dict1), len(dict2),
    while dict1 and len(dict1) == len(dict2):
        if verbose:
            print ".",
        if random.random() < 0.5:
            c = cmp(dict1, dict2)
        else:
            c = dict1 == dict2
    if verbose:
        print

# Run test_one n times.  At the start (before the bugs were fixed), 20
# consecutive runs of this test each blew up on or before the sixth time
# test_one was run.  So n doesn't have to be large to get an interesting
# test.
# OTOH, calling with large n is also interesting, to ensure that the fixed
# code doesn't hold on to refcounts *too* long (in which case memory would
# leak).

def test(n):
    for i in xrange(n):
        test_one(random.randrange(1, 100))

# See last comment block for clues about good values for n.
test(100)

##########################################################################
# Another segfault bug, distilled by Michael Hudson from a c.l.py post.

class Child:
    def __init__(self, parent):
        self.__dict__['parent'] = parent
    def __getattr__(self, attr):
        self.parent.a = 1
        self.parent.b = 1
        self.parent.c = 1
        self.parent.d = 1
        self.parent.e = 1
        self.parent.f = 1
        self.parent.g = 1
        self.parent.h = 1
        self.parent.i = 1
        return getattr(self.parent, attr)

class Parent:
    def __init__(self):
        self.a = Child(self)

# Hard to say what this will print!  May vary from time to time.  But
# we're specifically trying to test the tp_print slot here, and this is
# the clearest way to do it.  We print the result to a temp file so that
# the expected-output file doesn't need to change.

f = open(TESTFN, "w")
print >> f, Parent().__dict__
f.close()
os.unlink(TESTFN)

##########################################################################
# And another core-dumper from Michael Hudson.

dict = {}

# Force dict to malloc its table.
for i in range(1, 10):
    dict[i] = i

f = open(TESTFN, "w")

class Machiavelli:
    def __repr__(self):
        dict.clear()

        # Michael sez:  "doesn't crash without this.  don't know why."
        # Tim sez:  "luck of the draw; crashes with or without for me."
        print >> f

        return `"machiavelli"`

    def __hash__(self):
        return 0

dict[Machiavelli()] = Machiavelli()

print >> f, str(dict)
f.close()
os.unlink(TESTFN)
del f, dict


##########################################################################
# And another core-dumper from Michael Hudson.

dict = {}

# let's force dict to malloc its table
for i in range(1, 10):
    dict[i] = i

class Machiavelli2:
    def __eq__(self, other):
        dict.clear()
        return 1

    def __hash__(self):
        return 0

dict[Machiavelli2()] = Machiavelli2()

try:
    dict[Machiavelli2()]
except KeyError:
    pass

del dict

##########################################################################
# And another core-dumper from Michael Hudson.

dict = {}

# let's force dict to malloc its table
for i in range(1, 10):
    dict[i] = i

class Machiavelli3:
    def __init__(self, id):
        self.id = id

    def __eq__(self, other):
        if self.id == other.id:
            dict.clear()
            return 1
        else:
            return 0

    def __repr__(self):
        return "%s(%s)"%(self.__class__.__name__, self.id)

    def __hash__(self):
        return 0

dict[Machiavelli3(1)] = Machiavelli3(0)
dict[Machiavelli3(2)] = Machiavelli3(0)

f = open(TESTFN, "w")
try:
    try:
        print >> f, dict[Machiavelli3(2)]
    except KeyError:
        pass
finally:
    f.close()
    os.unlink(TESTFN)

del dict
del dict1, dict2, dict1keys, dict2keys