fuzz.py (11104B)
1 # Fuzzing functions for qcow2 fields 2 # 3 # Copyright (C) 2014 Maria Kustova <maria.k@catit.be> 4 # 5 # This program is free software: you can redistribute it and/or modify 6 # it under the terms of the GNU General Public License as published by 7 # the Free Software Foundation, either version 2 of the License, or 8 # (at your option) any later version. 9 # 10 # This program is distributed in the hope that it will be useful, 11 # but WITHOUT ANY WARRANTY; without even the implied warranty of 12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 # GNU General Public License for more details. 14 # 15 # You should have received a copy of the GNU General Public License 16 # along with this program. If not, see <http://www.gnu.org/licenses/>. 17 # 18 19 import random 20 from functools import reduce 21 22 UINT8 = 0xff 23 UINT16 = 0xffff 24 UINT32 = 0xffffffff 25 UINT64 = 0xffffffffffffffff 26 # Most significant bit orders 27 UINT32_M = 31 28 UINT64_M = 63 29 # Fuzz vectors 30 UINT8_V = [0, 0x10, UINT8//4, UINT8//2 - 1, UINT8//2, UINT8//2 + 1, UINT8 - 1, 31 UINT8] 32 UINT16_V = [0, 0x100, 0x1000, UINT16//4, UINT16//2 - 1, UINT16//2, UINT16//2 + 1, 33 UINT16 - 1, UINT16] 34 UINT32_V = [0, 0x100, 0x1000, 0x10000, 0x100000, UINT32//4, UINT32//2 - 1, 35 UINT32//2, UINT32//2 + 1, UINT32 - 1, UINT32] 36 UINT64_V = UINT32_V + [0x1000000, 0x10000000, 0x100000000, UINT64//4, 37 UINT64//2 - 1, UINT64//2, UINT64//2 + 1, UINT64 - 1, 38 UINT64] 39 BYTES_V = [b'%s%p%x%d', b'.1024d', b'%.2049d', b'%p%p%p%p', b'%x%x%x%x', 40 b'%d%d%d%d', b'%s%s%s%s', b'%99999999999s', b'%08x', b'%%20d', b'%%20n', 41 b'%%20x', b'%%20s', b'%s%s%s%s%s%s%s%s%s%s', b'%p%p%p%p%p%p%p%p%p%p', 42 b'%#0123456x%08x%x%s%p%d%n%o%u%c%h%l%q%j%z%Z%t%i%e%g%f%a%C%S%08x%%', 43 b'%s x 129', b'%x x 257'] 44 45 46 def random_from_intervals(intervals): 47 """Select a random integer number from the list of specified intervals. 48 49 Each interval is a tuple of lower and upper limits of the interval. The 50 limits are included. Intervals in a list should not overlap. 51 """ 52 total = reduce(lambda x, y: x + y[1] - y[0] + 1, intervals, 0) 53 r = random.randint(0, total - 1) + intervals[0][0] 54 for x in zip(intervals, intervals[1:]): 55 r = r + (r > x[0][1]) * (x[1][0] - x[0][1] - 1) 56 return r 57 58 59 def random_bits(bit_ranges): 60 """Generate random binary mask with ones in the specified bit ranges. 61 62 Each bit_ranges is a list of tuples of lower and upper limits of bit 63 positions will be fuzzed. The limits are included. Random amount of bits 64 in range limits will be set to ones. The mask is returned in decimal 65 integer format. 66 """ 67 bit_numbers = [] 68 # Select random amount of random positions in bit_ranges 69 for rng in bit_ranges: 70 bit_numbers += random.sample(range(rng[0], rng[1] + 1), 71 random.randint(0, rng[1] - rng[0] + 1)) 72 val = 0 73 # Set bits on selected positions to ones 74 for bit in bit_numbers: 75 val |= 1 << bit 76 return val 77 78 79 def truncate_bytes(sequences, length): 80 """Return sequences truncated to specified length.""" 81 if type(sequences) == list: 82 return [s[:length] for s in sequences] 83 else: 84 return sequences[:length] 85 86 87 def validator(current, pick, choices): 88 """Return a value not equal to the current selected by the pick 89 function from choices. 90 """ 91 while True: 92 val = pick(choices) 93 if not val == current: 94 return val 95 96 97 def int_validator(current, intervals): 98 """Return a random value from intervals not equal to the current. 99 100 This function is useful for selection from valid values except current one. 101 """ 102 return validator(current, random_from_intervals, intervals) 103 104 105 def bit_validator(current, bit_ranges): 106 """Return a random bit mask not equal to the current. 107 108 This function is useful for selection from valid values except current one. 109 """ 110 return validator(current, random_bits, bit_ranges) 111 112 113 def bytes_validator(current, sequences): 114 """Return a random bytes value from the list not equal to the current. 115 116 This function is useful for selection from valid values except current one. 117 """ 118 return validator(current, random.choice, sequences) 119 120 121 def selector(current, constraints, validate=int_validator): 122 """Select one value from all defined by constraints. 123 124 Each constraint produces one random value satisfying to it. The function 125 randomly selects one value satisfying at least one constraint (depending on 126 constraints overlaps). 127 """ 128 def iter_validate(c): 129 """Apply validate() only to constraints represented as lists. 130 131 This auxiliary function replaces short circuit conditions not supported 132 in Python 2.4 133 """ 134 if type(c) == list: 135 return validate(current, c) 136 else: 137 return c 138 139 fuzz_values = [iter_validate(c) for c in constraints] 140 # Remove current for cases it's implicitly specified in constraints 141 # Duplicate validator functionality to prevent decreasing of probability 142 # to get one of allowable values 143 # TODO: remove validators after implementation of intelligent selection 144 # of fields will be fuzzed 145 try: 146 fuzz_values.remove(current) 147 except ValueError: 148 pass 149 return random.choice(fuzz_values) 150 151 152 def magic(current): 153 """Fuzz magic header field. 154 155 The function just returns the current magic value and provides uniformity 156 of calls for all fuzzing functions. 157 """ 158 return current 159 160 161 def version(current): 162 """Fuzz version header field.""" 163 constraints = UINT32_V + [ 164 [(2, 3)], # correct values 165 [(0, 1), (4, UINT32)] 166 ] 167 return selector(current, constraints) 168 169 170 def backing_file_offset(current): 171 """Fuzz backing file offset header field.""" 172 constraints = UINT64_V 173 return selector(current, constraints) 174 175 176 def backing_file_size(current): 177 """Fuzz backing file size header field.""" 178 constraints = UINT32_V 179 return selector(current, constraints) 180 181 182 def cluster_bits(current): 183 """Fuzz cluster bits header field.""" 184 constraints = UINT32_V + [ 185 [(9, 20)], # correct values 186 [(0, 9), (20, UINT32)] 187 ] 188 return selector(current, constraints) 189 190 191 def size(current): 192 """Fuzz image size header field.""" 193 constraints = UINT64_V 194 return selector(current, constraints) 195 196 197 def crypt_method(current): 198 """Fuzz crypt method header field.""" 199 constraints = UINT32_V + [ 200 1, 201 [(2, UINT32)] 202 ] 203 return selector(current, constraints) 204 205 206 def l1_size(current): 207 """Fuzz L1 table size header field.""" 208 constraints = UINT32_V 209 return selector(current, constraints) 210 211 212 def l1_table_offset(current): 213 """Fuzz L1 table offset header field.""" 214 constraints = UINT64_V 215 return selector(current, constraints) 216 217 218 def refcount_table_offset(current): 219 """Fuzz refcount table offset header field.""" 220 constraints = UINT64_V 221 return selector(current, constraints) 222 223 224 def refcount_table_clusters(current): 225 """Fuzz refcount table clusters header field.""" 226 constraints = UINT32_V 227 return selector(current, constraints) 228 229 230 def nb_snapshots(current): 231 """Fuzz number of snapshots header field.""" 232 constraints = UINT32_V 233 return selector(current, constraints) 234 235 236 def snapshots_offset(current): 237 """Fuzz snapshots offset header field.""" 238 constraints = UINT64_V 239 return selector(current, constraints) 240 241 242 def incompatible_features(current): 243 """Fuzz incompatible features header field.""" 244 constraints = [ 245 [(0, 1)], # allowable values 246 [(0, UINT64_M)] 247 ] 248 return selector(current, constraints, bit_validator) 249 250 251 def compatible_features(current): 252 """Fuzz compatible features header field.""" 253 constraints = [ 254 [(0, UINT64_M)] 255 ] 256 return selector(current, constraints, bit_validator) 257 258 259 def autoclear_features(current): 260 """Fuzz autoclear features header field.""" 261 constraints = [ 262 [(0, UINT64_M)] 263 ] 264 return selector(current, constraints, bit_validator) 265 266 267 def refcount_order(current): 268 """Fuzz number of refcount order header field.""" 269 constraints = UINT32_V 270 return selector(current, constraints) 271 272 273 def header_length(current): 274 """Fuzz number of refcount order header field.""" 275 constraints = UINT32_V + [ 276 72, 277 104, 278 [(0, UINT32)] 279 ] 280 return selector(current, constraints) 281 282 283 def bf_name(current): 284 """Fuzz the backing file name.""" 285 constraints = [ 286 truncate_bytes(BYTES_V, len(current)) 287 ] 288 return selector(current, constraints, bytes_validator) 289 290 291 def ext_magic(current): 292 """Fuzz magic field of a header extension.""" 293 constraints = UINT32_V 294 return selector(current, constraints) 295 296 297 def ext_length(current): 298 """Fuzz length field of a header extension.""" 299 constraints = UINT32_V 300 return selector(current, constraints) 301 302 303 def bf_format(current): 304 """Fuzz backing file format in the corresponding header extension.""" 305 constraints = [ 306 truncate_bytes(BYTES_V, len(current)), 307 truncate_bytes(BYTES_V, (len(current) + 7) & ~7) # Fuzz padding 308 ] 309 return selector(current, constraints, bytes_validator) 310 311 312 def feature_type(current): 313 """Fuzz feature type field of a feature name table header extension.""" 314 constraints = UINT8_V 315 return selector(current, constraints) 316 317 318 def feature_bit_number(current): 319 """Fuzz bit number field of a feature name table header extension.""" 320 constraints = UINT8_V 321 return selector(current, constraints) 322 323 324 def feature_name(current): 325 """Fuzz feature name field of a feature name table header extension.""" 326 constraints = [ 327 truncate_bytes(BYTES_V, len(current)), 328 truncate_bytes(BYTES_V, 46) # Fuzz padding (field length = 46) 329 ] 330 return selector(current, constraints, bytes_validator) 331 332 333 def l1_entry(current): 334 """Fuzz an entry of the L1 table.""" 335 constraints = UINT64_V 336 # Reserved bits are ignored 337 # Added a possibility when only flags are fuzzed 338 offset = 0x7fffffffffffffff & \ 339 random.choice([selector(current, constraints), current]) 340 is_cow = random.randint(0, 1) 341 return offset + (is_cow << UINT64_M) 342 343 344 def l2_entry(current): 345 """Fuzz an entry of an L2 table.""" 346 constraints = UINT64_V 347 # Reserved bits are ignored 348 # Add a possibility when only flags are fuzzed 349 offset = 0x3ffffffffffffffe & \ 350 random.choice([selector(current, constraints), current]) 351 is_compressed = random.randint(0, 1) 352 is_cow = random.randint(0, 1) 353 is_zero = random.randint(0, 1) 354 value = offset + (is_cow << UINT64_M) + \ 355 (is_compressed << UINT64_M - 1) + is_zero 356 return value 357 358 359 def refcount_table_entry(current): 360 """Fuzz an entry of the refcount table.""" 361 constraints = UINT64_V 362 return selector(current, constraints) 363 364 365 def refcount_block_entry(current): 366 """Fuzz an entry of a refcount block.""" 367 constraints = UINT16_V 368 return selector(current, constraints)