1# Copyright 2016 The Chromium Authors 2# Use of this source code is governed by a BSD-style license that can be 3# found in the LICENSE file. 4 5import base64 6import functools 7import itertools 8import os 9import random 10import re 11import string 12import sys 13import textwrap 14 15from . import utils 16 17 18def FuzzyInt(n): 19 """Returns an integer derived from the input by one of several mutations.""" 20 int_sizes = [8, 16, 32, 64, 128] 21 mutations = [ 22 lambda n: utils.UniformExpoInteger(0, sys.maxsize.bit_length() + 1), 23 lambda n: -utils.UniformExpoInteger(0, sys.maxsize.bit_length()), 24 lambda n: 2 ** random.choice(int_sizes) - 1, 25 lambda n: 2 ** random.choice(int_sizes), 26 lambda n: 0, 27 lambda n: -n, 28 lambda n: n + 1, 29 lambda n: n - 1, 30 lambda n: n + random.randint(-1024, 1024), 31 ] 32 return random.choice(mutations)(n) 33 34 35def FuzzyString(s): 36 """Returns a string derived from the input by one of several mutations.""" 37 # First try some mutations that try to recognize certain types of strings 38 assert isinstance(s, str) 39 chained_mutations = [ 40 FuzzIntsInString, 41 FuzzBase64InString, 42 FuzzListInString, 43 ] 44 original = s 45 for mutation in chained_mutations: 46 s = mutation(s) 47 # Stop if we've modified the string and our coin comes up heads 48 if s != original and random.getrandbits(1): 49 return s 50 51 # If we're still here, apply a more generic mutation 52 mutations = [ 53 lambda _: "".join(random.choice(string.printable) for _ in 54 range(utils.UniformExpoInteger(0, 14))), 55 # We let through the surrogate. The decode exception is handled at caller. 56 lambda _: "".join(chr(random.randint(0, sys.maxunicode)) for _ in 57 range(utils.UniformExpoInteger(0, 14))).encode('utf-8', 'surrogatepass'), 58 lambda _: os.urandom(utils.UniformExpoInteger(0, 14)), 59 lambda s: s * utils.UniformExpoInteger(1, 5), 60 lambda s: s + "A" * utils.UniformExpoInteger(0, 14), 61 lambda s: "A" * utils.UniformExpoInteger(0, 14) + s, 62 lambda s: s[:-random.randint(1, max(1, len(s) - 1))], 63 lambda s: textwrap.fill(s, random.randint(1, max(1, len(s) - 1))), 64 lambda _: "", 65 ] 66 return random.choice(mutations)(s) 67 68 69def FuzzIntsInString(s): 70 """Returns a string where some integers have been fuzzed with FuzzyInt.""" 71 def ReplaceInt(m): 72 val = m.group() 73 if random.getrandbits(1): # Flip a coin to decide whether to fuzz 74 return val 75 if not random.getrandbits(4): # Delete the integer 1/16th of the time 76 return "" 77 decimal = val.isdigit() # Assume decimal digits means a decimal number 78 n = FuzzyInt(int(val) if decimal else int(val, 16)) 79 return str(n) if decimal else "%x" % n 80 return re.sub(r"\b[a-fA-F]*\d[0-9a-fA-F]*\b", ReplaceInt, s) 81 82 83def FuzzBase64InString(s): 84 """Returns a string where Base64 components are fuzzed with FuzzyBuffer.""" 85 def ReplaceBase64(m): 86 fb = FuzzyBuffer(base64.b64decode(m.group())) 87 fb.RandomMutation() 88 return base64.b64encode(fb) 89 # This only matches obvious Base64 words with trailing equals signs 90 return re.sub(r"(?<![A-Za-z0-9+/])" 91 r"(?:[A-Za-z0-9+/]{4})*(?:[A-Za-z0-9+/]{2}==|[A-Za-z0-9+/]{3}=)" 92 r"(?![A-Za-z0-9+/])", ReplaceBase64, s) 93 94 95def FuzzListInString(s, separators=r", |,|; |;|\r\n|\s"): 96 """Tries to interpret the string as a list, and fuzzes it if successful.""" 97 seps = re.findall(separators, s) 98 if not seps: 99 return s 100 sep = random.choice(seps) # Ones that appear often are more likely 101 items = FuzzyList(s.split(sep)) 102 items.RandomMutation() 103 return sep.join(items) 104 105# Pylint doesn't recognize that in this case 'self' is some mutable sequence, 106# so the unsupoorted-assignment-operation and unsupported-delete-operation 107# warnings have been disabled here. 108# pylint: disable=unsupported-assignment-operation,unsupported-delete-operation 109class FuzzySequence(object): #pylint: disable=useless-object-inheritance 110 """A helpful mixin for writing fuzzy mutable sequence types. 111 112 If a method parameter is left at its default value of None, an appropriate 113 random value will be chosen. 114 """ 115 116 def Overwrite(self, value, location=None, amount=None): 117 """Overwrite amount elements starting at location with value. 118 119 Value can be a function of no arguments, in which case it will be called 120 every time a new value is needed. 121 """ 122 if location is None: 123 location = random.randint(0, max(0, len(self) - 1)) 124 if amount is None: 125 amount = utils.RandomLowInteger(min(1, len(self)), len(self) - location) 126 if hasattr(value, "__call__"): 127 new_elements = (value() for i in range(amount)) 128 else: 129 new_elements = itertools.repeat(value, amount) 130 self[location:location+amount] = new_elements 131 132 def Insert(self, value, location=None, amount=None, max_exponent=14): 133 """Insert amount elements starting at location. 134 135 Value can be a function of no arguments, in which case it will be called 136 every time a new value is needed. 137 """ 138 if location is None: 139 location = random.randint(0, max(0, len(self) - 1)) 140 if amount is None: 141 amount = utils.UniformExpoInteger(0, max_exponent) 142 if hasattr(value, "__call__"): 143 new_elements = (value() for i in range(amount)) 144 else: 145 new_elements = itertools.repeat(value, amount) 146 self[location:location] = new_elements 147 148 def Delete(self, location=None, amount=None): 149 """Delete amount elements starting at location.""" 150 if location is None: 151 location = random.randint(0, max(0, len(self) - 1)) 152 if amount is None: 153 amount = utils.RandomLowInteger(min(1, len(self)), len(self) - location) 154 del self[location:location+amount] 155# pylint: enable=unsupported-assignment-operation,unsupported-delete-operation 156 157 158class FuzzyList(list, FuzzySequence): 159 """A list with additional methods for fuzzing.""" 160 161 def RandomMutation(self, count=None, new_element=""): 162 """Apply count random mutations chosen from a list.""" 163 random_items = lambda: random.choice(self) if self else new_element 164 mutations = [ 165 lambda: random.shuffle(self), 166 self.reverse, 167 functools.partial(self.Overwrite, new_element), 168 functools.partial(self.Overwrite, random_items), 169 functools.partial(self.Insert, new_element, max_exponent=10), 170 functools.partial(self.Insert, random_items, max_exponent=10), 171 self.Delete, 172 ] 173 if count is None: 174 count = utils.RandomLowInteger(1, 5, beta=3.0) 175 for _ in range(count): 176 random.choice(mutations)() 177 178 179class FuzzyBuffer(bytearray, FuzzySequence): 180 """A bytearray with additional methods for mutating the sequence of bytes.""" 181 182 def __repr__(self): 183 return "%s(%r)" % (self.__class__.__name__, str(self)) 184 185 def FlipBits(self, num_bits=None): 186 """Flip num_bits bits in the buffer at random.""" 187 if num_bits is None: 188 num_bits = utils.RandomLowInteger(min(1, len(self)), len(self) * 8) 189 for bit in random.sample(range(len(self) * 8), num_bits): 190 self[bit / 8] ^= 1 << (bit % 8) 191 192 def RandomMutation(self, count=None): 193 """Apply count random mutations chosen from a weighted list.""" 194 random_bytes = lambda: random.randint(0x00, 0xFF) 195 mutations = [ 196 (self.FlipBits, 1), 197 (functools.partial(self.Overwrite, random_bytes), 1/3.0), 198 (functools.partial(self.Overwrite, 0xFF), 1/3.0), 199 (functools.partial(self.Overwrite, 0x00), 1/3.0), 200 (functools.partial(self.Insert, random_bytes), 1/3.0), 201 (functools.partial(self.Insert, 0xFF), 1/3.0), 202 (functools.partial(self.Insert, 0x00), 1/3.0), 203 (self.Delete, 1), 204 ] 205 if count is None: 206 count = utils.RandomLowInteger(1, 5, beta=3.0) 207 for _ in range(count): 208 utils.WeightedChoice(mutations)() 209