Home | History | Annotate | Download | only in utils 
      1 #! /usr/bin/env python
      2 
      3 # To use:
      4 #  1) Update the 'decls' list below with your fuzzing configuration.
      5 #  2) Run with the clang binary as the command-line argument.
      6 
      7 import random
      8 import subprocess
      9 import sys
     10 import os
     11 
     12 clang = sys.argv[1]
     13 none_opts = 0.3
     14 
     15 class Decl:
     16   def __init__(self, text, depends=[], provides=[], conflicts=[]):
     17     self.text = text
     18     self.depends = depends
     19     self.provides = provides
     20     self.conflicts = conflicts
     21 
     22   def valid(self, model):
     23     for i in self.depends:
     24       if i not in model.decls:
     25         return False
     26     for i in self.conflicts:
     27       if i in model.decls:
     28         return False
     29     return True
     30 
     31   def apply(self, model, name):
     32     for i in self.provides:
     33       model.decls[i] = True
     34     model.source += self.text % {'name': name}
     35 
     36 decls = [
     37   Decl('struct X { int n; };\n', provides=['X'], conflicts=['X']),
     38   Decl('static_assert(X{.n=1}.n == 1, "");\n', depends=['X']),
     39   Decl('X %(name)s;\n', depends=['X']),
     40 ]
     41 
     42 class FS:
     43   def __init__(self):
     44     self.fs = {}
     45     self.prevfs = {}
     46 
     47   def write(self, path, contents):
     48     self.fs[path] = contents
     49 
     50   def done(self):
     51     for f, s in self.fs.items():
     52       if self.prevfs.get(f) != s:
     53         f = file(f, 'w')
     54         f.write(s)
     55         f.close()
     56 
     57     for f in self.prevfs:
     58       if f not in self.fs:
     59         os.remove(f)
     60 
     61     self.prevfs, self.fs = self.fs, {}
     62 
     63 fs = FS()
     64 
     65 class CodeModel:
     66   def __init__(self):
     67     self.source = ''
     68     self.modules = {}
     69     self.decls = {}
     70     self.i = 0
     71 
     72   def make_name(self):
     73     self.i += 1
     74     return 'n' + str(self.i)
     75 
     76   def fails(self):
     77     fs.write('module.modulemap',
     78           ''.join('module %s { header "%s.h" export * }\n' % (m, m)
     79                   for m in self.modules.keys()))
     80 
     81     for m, (s, _) in self.modules.items():
     82       fs.write('%s.h' % m, s)
     83 
     84     fs.write('main.cc', self.source)
     85     fs.done()
     86 
     87     return subprocess.call([clang, '-std=c++11', '-c', '-fmodules', 'main.cc', '-o', '/dev/null']) != 0
     88 
     89 def generate():
     90   model = CodeModel()
     91   m = []
     92 
     93   try:
     94     for d in mutations(model):
     95       d(model)
     96       m.append(d)
     97     if not model.fails():
     98       return
     99   except KeyboardInterrupt:
    100     print
    101     return True
    102 
    103   sys.stdout.write('\nReducing:\n')
    104   sys.stdout.flush()
    105 
    106   try:
    107     while True:
    108       assert m, 'got a failure with no steps; broken clang binary?'
    109       i = random.choice(range(len(m)))
    110       x = m[0:i] + m[i+1:]
    111       m2 = CodeModel()
    112       for d in x:
    113         d(m2)
    114       if m2.fails():
    115         m = x
    116         model = m2
    117       else:
    118         sys.stdout.write('.')
    119         sys.stdout.flush()
    120   except KeyboardInterrupt:
    121     # FIXME: Clean out output directory first.
    122     model.fails()
    123     return model
    124 
    125 def choose(options):
    126   while True:
    127     i = int(random.uniform(0, len(options) + none_opts))
    128     if i >= len(options):
    129       break
    130     yield options[i]
    131 
    132 def mutations(model):
    133   options = [create_module, add_top_level_decl]
    134   for opt in choose(options):
    135     yield opt(model, options)
    136 
    137 def create_module(model, options):
    138   n = model.make_name()
    139   def go(model):
    140     model.modules[n] = (model.source, model.decls)
    141     (model.source, model.decls) = ('', {})
    142   options += [lambda model, options: add_import(model, options, n)]
    143   return go
    144 
    145 def add_top_level_decl(model, options):
    146   n = model.make_name()
    147   d = random.choice([decl for decl in decls if decl.valid(model)])
    148   def go(model):
    149     if not d.valid(model):
    150       return
    151     d.apply(model, n)
    152   return go
    153 
    154 def add_import(model, options, module_name):
    155   def go(model):
    156     if module_name in model.modules:
    157       model.source += '#include "%s.h"\n' % module_name
    158       model.decls.update(model.modules[module_name][1])
    159   return go
    160 
    161 sys.stdout.write('Finding bug: ')
    162 while True:
    163   if generate():
    164     break
    165   sys.stdout.write('.')
    166   sys.stdout.flush()
    167