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