· 9 years ago · Nov 09, 2016, 02:10 AM
1#!/usr/bin/env python
2# Copyright (C) 2010, Scott W. Dunlop <swdunlop at gmail.com>
3#
4# Redistribution and use in source and binary forms, with or without
5# modification, are permitted provided that the following conditions are met:
6#
7# * Redistributions of source code must retain the above copyright
8# notice, this list of conditions and the following disclaimer.
9# * Redistributions in binary form must reproduce the above copyright
10# notice, this list of conditions and the following disclaimer in the
11# documentation and/or other materials provided with the distribution.
12#
13# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
14# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
15# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
16# DISCLAIMED. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY
17# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
18# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
19# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
20# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
21# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
22# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23
24'''
25Generating random strings from regex-like expressions.
26
27Fuzzex generates sequences of random characters derived from a production
28expression with a grammar approximately identical to that used by Regular
29Expressions. For the majority of regular expressions, R, any product
30generated by a Fuzzex for R would be a satisfactory match.
31
32This is intended for data-driven testing (fuzzing) of input validators and
33parsers that use regex or regex-like semantics.
34
35Example, Generates a Random Email Address:
36-- fuzzex.generate( "[a-zA-Z0-9._]+@[a-zA-Z0-9._]+\\\\.[a-z]+" )
37
38Where Fuzzex Breaks From Regex:
39-- Fuzzex does not support "non-greedy" repetition. (e.g. "a*?")
40-- Fuzzex does not currently support "non-capturing" groups.
41-- Fuzzex is derived from the "Extended Regex" dialect most frequently used.
42-- Fuzzex is 8-bit ASCII-oriented; this matches Python's RE, but not some others.
43
44Where Fuzzex Is Not The Right Tool: (Go use Sulley or Peach)
45-- Fuzzing semantic logic; e.g. it might generate data that looks like BASE-64,
46 but it might not decode.
47
48Special Thanks to Ryan O'Horo and Mattias Brutti for pointing out various
49alternate implementations of this idea in Perl and C#.
50'''
51
52import re, sys, random
53
54def op_dat( data ):
55 def op_dat_fn( vm ):
56 vm.write( data )
57 return op_dat_fn
58
59def op_seq( seq ):
60 def op_seq_fn( vm ):
61 for op in seq:
62 op( vm )
63 return True
64 return op_seq_fn
65
66def op_alt( alt ):
67 def op_alt_fn( vm ):
68 vm.choose( alt )( vm )
69 return op_alt_fn
70
71def op_set( ix, op ):
72 def op_set_fn( vm ):
73 with vm.capture( ix ): op( vm )
74 return op_set_fn
75
76def op_ref( ix ):
77 def op_ref_fn( vm ):
78 vm.write( vm.group( ix ) )
79 return op_ref_fn
80
81def op_nul( ):
82 def op_nul_fn( vm ):
83 pass
84 return op_nul_fn
85
86def op_rpt( op, m, n ):
87 if m == n:
88 def op_fix_rpt_fn( vm ):
89 for i in range( 0, m ):
90 op( vm )
91 return op_fix_rpt_fn
92
93 if m > n: n, m = m, n
94 r = n - m
95
96 def op_rpt_fn( vm ):
97 for i in range( 0, m + vm.choose( r ) ):
98 op( vm )
99
100 return op_rpt_fn
101
102def op_opt( op ):
103 def op_opt_fn( vm ):
104 if vm.choose( 2 ): op( vm )
105 return op_opt_fn
106
107def op_rng( s ):
108 s = ''.join( s )
109 def op_rng_fn( vm ):
110 vm.write( vm.choose( s ) )
111 return op_rng_fn
112
113any_op = op_rng( map( chr, range( 0, 255 ) ) )
114
115def mk_seq_op( seq ):
116 "unifies a sequence of 0 to N requirements into a minimal operation"
117 if not seq: return op_nul( )
118 if callable( seq ): return seq
119 if isinstance( seq, str ): return op_dat( seq )
120
121 out = []; buf = ''
122 for op in seq:
123 if isinstance( op, str ):
124 buf += op
125 else:
126 if buf:
127 out.append( op_dat( buf ) )
128 buf = ''
129 if op:
130 out.append( op )
131 if buf:
132 out.append( op_dat( buf ) )
133
134 if len( out ) == 1:
135 return out[0]
136 else:
137 return op_seq( out )
138
139class Error( Exception ):
140 pass
141
142escapes = {
143 'n' : '\n',
144 'r' : '\r',
145 't' : '\t',
146 'v' : '\v',
147 '0' : '\0'
148}
149
150rx_octet = re.compile( '([0-8][0-8][0-8]|[0])' )
151rx_refer = re.compile( '([0-9][0-9]?)')
152rx_range = re.compile( '[^\\\\]')
153rx_repeat = re.compile( '([0-9]+)(,[0-9]+)?\\}' )
154
155class Compiler:
156 def __init__( self, src ):
157 self.src = src
158 self.ofs = 0
159 self.opens = 0
160 self.closes = 0
161 self.limit = 4
162
163 def parse_rpt( self, op ):
164 m = rx_repeat.match( self.src, self.ofs )
165 if not m:
166 raise Error( '"{" followed without matching "}"') #TODO: Python ignores this silently.
167 self.ofs = m.end( )
168 if not m.group(2):
169 n = int( m.group( 1 ) )
170 return op_rpt( op, n, n )
171 n = int( m.group(2)[1:] )
172 m = int( m.group(1) )
173 return op_rpt( op, m, n )
174
175 def parse_rng( self ):
176 end = len( self.src )
177 if self.ofs >= end:
178 raise Error( '"[" at end of expression' )
179
180 if self.src[self.ofs] == '^':
181 self.ofs += 1
182 x = self.parse_rng_items( )
183 s = set( )
184 for i in range( 0, 127 ): #TODO: configurable
185 c = chr( i )
186 if c not in x: s.add( c )
187 else:
188 s = self.parse_rng_items( )
189
190 return op_rng( s )
191
192 def parse_rng_items( self ):
193 end = len( self.src )
194 s = set()
195 while self.ofs < end:
196 ch = self.src[ self.ofs ]
197 if ch == ']':
198 self.ofs += 1
199 return s
200
201 a = self.parse_rng_item( )
202 if self.src[ self.ofs ] == '-':
203 self.ofs += 1
204 b = self.parse_rng_item( )
205 for i in range( ord( a ), ord( b ) + 1 ):
206 ch = chr( i )
207 s.add( ch )
208 else:
209 s.add( a )
210
211 raise Error( 'unmatched "["' )
212
213 def parse_rng_item( self ):
214 end = len( self.src )
215 if self.ofs >= end: raise Error( '"[" at end of expression' )
216 ch = self.src[ self.ofs ]
217 self.ofs += 1
218 if ch == '\\':
219 if self.ofs >= end: raise Error( '"\\" at end of expression' )
220
221 m = rx_octet.match( self.src, self.ofs )
222 if m:
223 self.ofs = m.end( )
224 return chr( int( m.group(1), 8 ) )
225 else:
226 return ch
227
228 def parse_esc( self ):
229 if self.ofs >= len( self.src ):
230 raise Error( '"\\" at end of expression' )
231
232 m = rx_octet.match( self.src, self.ofs )
233 if m:
234 self.ofs = m.end( )
235 return op_data( chr( int( m.group(1), 8 ) ) )
236
237 m = rx_refer.match( self.src, self.ofs )
238 if m:
239 self.ofs = m.end( )
240 ix = int( m.group( 1 ), 8 )
241 if ix > self.closes:
242 raise Error( 'illegal forward reference' ) # not that there are any legal ones.
243 return op_ref( ix )
244
245 ch = self.src[self.ofs]
246 self.ofs += 1
247 return escapes.get( ch, ch )
248
249 def parse_expr( self, inner = False ):
250 "parses a possibly branched expression yielding none or an operation"
251 opt = [] # We start with an empty sequence of requirements.
252 opts = [opt] # And a empty list of branches.
253 end = len( self.src )
254
255 while self.ofs < end:
256 ch = self.src[ self.ofs ]
257 self.ofs += 1
258
259 if ch == '|':
260 opt = []
261 opts.append( opt )
262 elif ch =='(':
263 self.opens += 1
264 opt.append( op_set( self.opens, self.parse_expr( True ) ) )
265 self.closes += 1
266 elif ch == ')':
267 if not inner: raise Error( 'unmatched ")"' )
268 inner = False
269 break
270 elif ch == '\\':
271 opt.append( self.parse_esc( ) )
272 elif ch == '.':
273 opt.append( any_op )
274 elif ch == '*':
275 if not opt: raise Error( 'nothing to repeat' )
276 #TODO: Catch and Report multiple-repeat.
277 opt[-1] = op_rpt( mk_seq_op( opt[-1] ), 0, self.limit )
278 elif ch == '+':
279 if not opt: raise Error( 'nothing to repeat' )
280 #TODO: Catch and Report multiple-repeat.
281 opt[-1] = op_rpt( mk_seq_op( opt[-1] ), 1, self.limit )
282 elif ch == '?':
283 if not opt: raise Error( 'nothing to repeat' )
284 #TODO: Catch and Report multiple-repeat.
285 opt[-1] = op_opt( mk_seq_op( opt[-1] ) )
286 elif ch == '[':
287 opt.append( self.parse_rng( ) )
288 elif ch == '{':
289 if not opt: raise Error( 'nothing to repeat' )
290 #TODO: Catch and Report multiple-repeat.
291 opt[-1] = self.parse_rpt( mk_seq_op( opt[-1] ) )
292 else:
293 opt.append( ch )
294
295 if inner:
296 raise Error( 'unmatched "("' )
297
298 opts = filter( lambda x:x, opts )
299 if not opts:
300 return op_nul( )
301 elif len( opts ) == 1:
302 return mk_seq_op( opt )
303 else:
304 return op_alt( map( mk_seq_op, opts ) )
305
306class Generator:
307 def __init__( self, root ):
308 if not root: raise Exception #TODO
309 self.root = root
310
311 def generate( self, seed = None, vm = None ):
312 if vm is None: vm = Vm( seed )
313 self.root( vm )
314 return str( vm )
315
316class Vm:
317 def __init__( self, seed = None ):
318 self.rng = random.WichmannHill( seed )
319 self.out = []
320 self.groups = {}
321
322 def choose( self, field ):
323 "selects a random value from 0 .. field - 1, or the list"
324 if isinstance( field, int ):
325 return self.rng.randint( 0, field )
326 else:
327 return self.rng.choice( field )
328
329 def write( self, data ):
330 self.out.append( data )
331
332 def group( self, tag ):
333 return self.groups.get( tag, '' )
334
335 def capture( self, tag ):
336 return Capture( self, tag )
337
338 def __str__( self ):
339 return ''.join( self.out )
340
341 def __repr__( self ):
342 return '<fuzzex.vm %r>' % str( self )
343
344class Capture:
345 def __init__( self, vm, ref ):
346 self.vm = vm
347 self.ref = ref
348
349 def __enter__( self ):
350 self.out = self.vm.out
351 self.vm.out = []
352
353 def __exit__( self, errtyp, errval, errtb ):
354 if errtyp or errval: return False
355
356 vm = self.vm
357 data = ''.join( vm.out )
358 vm.out = self.out
359 vm.write( data )
360 vm.groups[self.ref] = data
361
362def generate( fx, seed = None, vm = None ):
363 if isinstance( fx, str ):
364 fx = compile( fx )
365 return fx.generate( seed, vm )
366
367def compile( data ):
368 return Generator( Compiler( data ).parse_expr( ) )
369
370def test( ex, seed = None ):
371 r = re.compile( '^' + ex + '$' )
372 data = generate( ex, seed )
373 k = r.match( data )
374 print >>sys.stderr, 'TESTING: %s, RESULT: %r, %s' % (
375 ex, data, "PASSED" if k else "FAILED"
376 )
377 return k
378
379def test_batch( seed = None ):
380 return ( test( 'a' )
381 and test( 'a|b', seed )
382 and test( 'a|b|c', seed )
383 and test( 'aa', seed )
384 and test( 'aa|b', seed )
385 and test( 'aa|bb', seed )
386 and test( 'aa|bb|c', seed )
387 and test( 'a|bb|c', seed )
388 and test( 'a|bb|cc', seed )
389 and test( '(a|bb|cc)z\\1', seed )
390 and test( 'a?b', seed )
391 and test( 'a*b', seed )
392 and test( 'a+b', seed )
393 and test( '[a]', seed )
394 and test( '[-a-c]', seed )
395 and test( '[^a-zA-Z0-9]', seed )
396 and test( "^(([^:/?#]+):)?(//([^/?#]*))?([^?#]*)([?]([^#]*))?(#(.*))?", seed )
397 and test( "[a-zA-Z0-9._]+@[a-z0-9._]+\\.[a-z]+", seed )
398 and test( "[a-z]{3,8}", seed )
399 and test( ".{3,8}", seed )
400 )
401
402__all__ = [
403 'compile', 'generate', 'Generator'
404]
405
406if __name__ == '__main__':
407 test_batch( )
408
409#TODO: report error for []