tests/image-fuzzer/qcow2/fuzz.py

   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 STRING_V = ['%s%p%x%d', '.1024d', '%.2049d', '%p%p%p%p', '%x%x%x%x',
  40             '%d%d%d%d', '%s%s%s%s', '%99999999999s', '%08x', '%%20d', '%%20n',
  41             '%%20x', '%%20s', '%s%s%s%s%s%s%s%s%s%s', '%p%p%p%p%p%p%p%p%p%p',
  42             '%#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             '%s x 129', '%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_string(strings, length):
  80     """Return strings truncated to specified length."""
  81     if type(strings) == list:
  82         return [s[:length] for s in strings]
  83     else:
  84         return strings[: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 string_validator(current, strings):
 114     """Return a random string 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, strings)
 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_string(STRING_V, len(current))
 287     ]
 288     return selector(current, constraints, string_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_string(STRING_V, len(current)),
 307         truncate_string(STRING_V, (len(current) + 7) & ~7)  # Fuzz padding
 308     ]
 309     return selector(current, constraints, string_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_string(STRING_V, len(current)),
 328         truncate_string(STRING_V, 46)  # Fuzz padding (field length = 46)
 329     ]
 330     return selector(current, constraints, string_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)