[mirror_edk2.git] / AppPkg / Applications / Python / Python-2.7.2 / Lib / test / test_mutants.py

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