Skip to content

Commit a2cfae4

Browse files
kripkenkripken
committed
add a fuzzer for the relooper through the C API
1 parent ffb9e4b commit a2cfae4

3 files changed

Lines changed: 804 additions & 0 deletions

File tree

‎scripts/fuzz_relooper.py‎

Lines changed: 282 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,282 @@
1+
#! /usr/bin/env python
2+
3+
# Copyright 2016 WebAssembly Community Group participants
4+
#
5+
# Licensed under the Apache License, Version 2.0 (the "License");
6+
# you may not use this file except in compliance with the License.
7+
# You may obtain a copy of the License at
8+
#
9+
# http://www.apache.org/licenses/LICENSE-2.0
10+
#
11+
# Unless required by applicable law or agreed to in writing, software
12+
# distributed under the License is distributed on an "AS IS" BASIS,
13+
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14+
# See the License for the specific language governing permissions and
15+
# limitations under the License.
16+
17+
'''
18+
This fuzzes the relooper using the C API.
19+
'''
20+
21+
import difflib
22+
import os
23+
import random
24+
import subprocess
25+
26+
if os.environ.get('LD_LIBRARY_PATH'):
27+
os.environ['LD_LIBRARY_PATH'] += os.pathsep + 'lib'
28+
else:
29+
os.environ['LD_LIBRARY_PATH'] = 'lib'
30+
31+
while True:
32+
# Random decisions
33+
num = random.randint(2, 100) # TODO: 250+
34+
density = random.random() * random.random()
35+
decisions = [random.randint(1, num * 20) for x in range(num * 3)]
36+
branches = [0] * num
37+
defaults = [0] * num
38+
for i in range(num):
39+
b = set([])
40+
bs = random.randint(1, max(1,
41+
round(density * random.random() * (num - 1))))
42+
for j in range(bs):
43+
b.add(random.randint(1, num - 1))
44+
b = list(b)
45+
defaults[i] = random.choice(b)
46+
b.remove(defaults[i])
47+
branches[i] = b
48+
optimize = random.random() < 0.5
49+
print num, density, optimize
50+
51+
for temp in ['fuzz.wasm', 'fuzz.wast', 'fast.txt', 'fuzz.slow.js',
52+
'fuzz.cpp']:
53+
try:
54+
os.unlink(temp)
55+
except:
56+
pass
57+
58+
# parts
59+
entry = '''
60+
var label = 0;
61+
var state;
62+
var decisions = %s;
63+
var index = 0;
64+
function check() {
65+
if (index == decisions.length) throw 'HALT';
66+
console.log('(i32.const ' + (-decisions[index]) + ')');
67+
return decisions[index++];
68+
}
69+
''' % str(decisions)
70+
71+
slow = entry + '\n'
72+
slow += 'label = 0;\n'
73+
74+
slow += '''
75+
while(1) switch(label) {
76+
'''
77+
78+
fast = '''
79+
80+
#include <assert.h>
81+
#include <stdio.h>
82+
83+
#include "binaryen-c.h"
84+
85+
// globals: address 4 is index
86+
// decisions are at address 8+
87+
88+
int main() {
89+
BinaryenModuleRef module = BinaryenModuleCreate();
90+
91+
// check()
92+
93+
// if the end, halt
94+
BinaryenExpressionRef halter = BinaryenIf(module,
95+
BinaryenBinary(module,
96+
BinaryenEq(),
97+
BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(),
98+
BinaryenConst(module, BinaryenLiteralInt32(4))),
99+
BinaryenConst(module, BinaryenLiteralInt32(4 * %d)) // jumps of 4 bytes
100+
),
101+
BinaryenUnreachable(module),
102+
NULL
103+
);
104+
// increment index
105+
BinaryenExpressionRef incer = BinaryenStore(module,
106+
4, 0, 0,
107+
BinaryenConst(module, BinaryenLiteralInt32(4)),
108+
BinaryenBinary(module,
109+
BinaryenAdd(),
110+
BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(),
111+
BinaryenConst(module, BinaryenLiteralInt32(4))),
112+
BinaryenConst(module, BinaryenLiteralInt32(4))
113+
)
114+
);
115+
116+
// optionally, print the return value
117+
BinaryenExpressionRef args[] = {
118+
BinaryenBinary(module,
119+
BinaryenSub(),
120+
BinaryenConst(module, BinaryenLiteralInt32(0)),
121+
BinaryenLoad(module,
122+
4, 0, 4, 0, BinaryenInt32(),
123+
BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(),
124+
BinaryenConst(module, BinaryenLiteralInt32(4)))
125+
)
126+
)
127+
};
128+
BinaryenExpressionRef debugger;
129+
if (1) debugger = BinaryenCallImport(module, "print", args, 1,
130+
BinaryenNone());
131+
else debugger = BinaryenNop(module);
132+
133+
// return the decision. need to subtract 4 that we just added,
134+
// and add 8 since that's where we start, so overall offset 4
135+
BinaryenExpressionRef returner = BinaryenLoad(module,
136+
4, 0, 4, 0, BinaryenInt32(),
137+
BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(),
138+
BinaryenConst(module, BinaryenLiteralInt32(4)))
139+
);
140+
BinaryenExpressionRef checkBodyList[] = { halter, incer, debugger,
141+
returner };
142+
BinaryenExpressionRef checkBody = BinaryenBlock(module,
143+
NULL, checkBodyList, sizeof(checkBodyList) / sizeof(BinaryenExpressionRef)
144+
);
145+
BinaryenFunctionTypeRef i = BinaryenAddFunctionType(module, "i",
146+
BinaryenInt32(),
147+
NULL, 0);
148+
BinaryenAddFunction(module, "check", i, NULL, 0, checkBody);
149+
150+
// contents of main() begin here
151+
152+
RelooperRef relooper = RelooperCreate();
153+
154+
''' % len(decisions)
155+
156+
for i in range(0, num):
157+
slow += ' case %d: console.log("(i32.const %d)"); state = check(); \n' % (
158+
i, i)
159+
b = branches[i]
160+
for j in range(len(b)):
161+
slow += ' if (state %% %d == %d) { label = %d; break }\n' % (
162+
len(b) + 1, j, b[j]) # TODO: split range 1-n into these options
163+
slow += ' label = %d; break\n' % defaults[i]
164+
165+
for i in range(num):
166+
fast += '''
167+
RelooperBlockRef b%d;
168+
{
169+
BinaryenExpressionRef args[] = {
170+
BinaryenConst(module, BinaryenLiteralInt32(%d))
171+
};
172+
BinaryenExpressionRef list[] = {
173+
BinaryenCallImport(module, "print", args, 1, BinaryenNone()),
174+
BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0,
175+
BinaryenInt32()))
176+
};
177+
b%d = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2));
178+
}
179+
''' % (i, i, i)
180+
181+
for i in range(num):
182+
b = branches[i]
183+
for j in range(len(b)):
184+
fast += '''
185+
RelooperAddBranch(b%d, b%d, BinaryenBinary(module,
186+
BinaryenEq(),
187+
BinaryenBinary(module,
188+
BinaryenRemU(),
189+
BinaryenGetLocal(module, 0, BinaryenInt32()),
190+
BinaryenConst(module, BinaryenLiteralInt32(%d))
191+
),
192+
BinaryenConst(module, BinaryenLiteralInt32(%d))
193+
), NULL);
194+
''' % (i, b[j], len(b) + 1, j)
195+
fast += '''
196+
RelooperAddBranch(b%d, b%d, NULL, NULL);
197+
''' % (i, defaults[i])
198+
199+
fast += '''
200+
BinaryenExpressionRef body = RelooperRenderAndDispose(relooper, b0, 1,
201+
module);
202+
203+
int decisions[] = { %s };
204+
int numDecisions = sizeof(decisions)/sizeof(int);
205+
206+
// write out all the decisions, then the body of the function
207+
BinaryenExpressionRef full[numDecisions + 1];
208+
209+
for (int i = 0; i < numDecisions; i++) {
210+
full[i] = BinaryenStore(module,
211+
4, 0, 0,
212+
BinaryenConst(module, BinaryenLiteralInt32(8 + 4 * i)),
213+
BinaryenConst(module, BinaryenLiteralInt32(decisions[i]))
214+
);
215+
}
216+
full[numDecisions] = body;
217+
BinaryenExpressionRef all = BinaryenBlock(module, NULL, full,
218+
numDecisions + 1);
219+
220+
BinaryenFunctionTypeRef v = BinaryenAddFunctionType(module, "v",
221+
BinaryenNone(),
222+
NULL, 0);
223+
// locals: state, free-for-label
224+
BinaryenType localTypes[] = { BinaryenInt32(), BinaryenInt32() };
225+
BinaryenFunctionRef theMain = BinaryenAddFunction(module, "main", v,
226+
localTypes, 2, all);
227+
BinaryenSetStart(module, theMain);
228+
229+
// import
230+
231+
BinaryenType iparams[] = { BinaryenInt32() };
232+
BinaryenFunctionTypeRef vi = BinaryenAddFunctionType(module, "vi",
233+
BinaryenNone(),
234+
iparams, 1);
235+
BinaryenAddImport(module, "print", "spectest", "print", vi);
236+
237+
// memory
238+
BinaryenSetMemory(module, 1, 1, "mem", NULL, NULL, NULL, 0);
239+
240+
// optionally, optimize
241+
if (%d) BinaryenModuleOptimize(module);
242+
243+
assert(BinaryenModuleValidate(module));
244+
245+
// write it out
246+
247+
BinaryenModulePrint(module);
248+
249+
BinaryenModuleDispose(module);
250+
251+
return 0;
252+
}
253+
''' % (', '.join(map(str, decisions)), optimize)
254+
255+
slow += '}'
256+
257+
open('fuzz.slow.js', 'w').write(slow)
258+
open('fuzz.cpp', 'w').write(fast)
259+
260+
print '.'
261+
cmd = ['g++', 'fuzz.cpp', '-Isrc', '-g', '-lbinaryen-c', '-lasmjs',
262+
'-lsupport', '-Llib/.', '-pthread', '-o', 'fuzz', '-g']
263+
subprocess.check_call(cmd)
264+
print '^'
265+
subprocess.check_call(['./fuzz'], stdout=open('fuzz.wast', 'w'))
266+
print '*'
267+
subprocess.call(['bin/binaryen-shell', 'fuzz.wast'],
268+
stdout=open('fast.txt', 'w'), stderr=subprocess.PIPE)
269+
fast_out = open('fast.txt').read()
270+
print '-'
271+
slow_out = subprocess.Popen(['nodejs', 'fuzz.slow.js'],
272+
stdout=subprocess.PIPE,
273+
stderr=subprocess.PIPE).communicate()[0]
274+
print '_'
275+
276+
if slow_out != fast_out:
277+
print ''.join([a.rstrip() + '\n' for a in difflib.unified_diff(
278+
slow_out.split('\n'),
279+
fast_out.split('\n'),
280+
fromfile='slow',
281+
tofile='fast')])
282+
assert False

0 commit comments

Comments
 (0)