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
19import random
20from functools import reduce
21
22UINT8 = 0xff
23UINT16 = 0xffff
24UINT32 = 0xffffffff
25UINT64 = 0xffffffffffffffff
26# Most significant bit orders
27UINT32_M = 31
28UINT64_M = 63
29# Fuzz vectors
30UINT8_V = [0, 0x10, UINT8//4, UINT8//2 - 1, UINT8//2, UINT8//2 + 1, UINT8 - 1,
31           UINT8]
32UINT16_V = [0, 0x100, 0x1000, UINT16//4, UINT16//2 - 1, UINT16//2, UINT16//2 + 1,
33            UINT16 - 1, UINT16]
34UINT32_V = [0, 0x100, 0x1000, 0x10000, 0x100000, UINT32//4, UINT32//2 - 1,
35            UINT32//2, UINT32//2 + 1, UINT32 - 1, UINT32]
36UINT64_V = UINT32_V + [0x1000000, 0x10000000, 0x100000000, UINT64//4,
37                       UINT64//2 - 1, UINT64//2, UINT64//2 + 1, UINT64 - 1,
38                       UINT64]
39BYTES_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
46def 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
59def 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
79def 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
87def 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
97def 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
105def 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
113def 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
121def 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
152def 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
161def 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
170def backing_file_offset(current):
171    """Fuzz backing file offset header field."""
172    constraints = UINT64_V
173    return selector(current, constraints)
174
175
176def backing_file_size(current):
177    """Fuzz backing file size header field."""
178    constraints = UINT32_V
179    return selector(current, constraints)
180
181
182def 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
191def size(current):
192    """Fuzz image size header field."""
193    constraints = UINT64_V
194    return selector(current, constraints)
195
196
197def 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
206def l1_size(current):
207    """Fuzz L1 table size header field."""
208    constraints = UINT32_V
209    return selector(current, constraints)
210
211
212def l1_table_offset(current):
213    """Fuzz L1 table offset header field."""
214    constraints = UINT64_V
215    return selector(current, constraints)
216
217
218def refcount_table_offset(current):
219    """Fuzz refcount table offset header field."""
220    constraints = UINT64_V
221    return selector(current, constraints)
222
223
224def refcount_table_clusters(current):
225    """Fuzz refcount table clusters header field."""
226    constraints = UINT32_V
227    return selector(current, constraints)
228
229
230def nb_snapshots(current):
231    """Fuzz number of snapshots header field."""
232    constraints = UINT32_V
233    return selector(current, constraints)
234
235
236def snapshots_offset(current):
237    """Fuzz snapshots offset header field."""
238    constraints = UINT64_V
239    return selector(current, constraints)
240
241
242def 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
251def 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
259def 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
267def refcount_order(current):
268    """Fuzz number of refcount order header field."""
269    constraints = UINT32_V
270    return selector(current, constraints)
271
272
273def 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
283def 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
291def ext_magic(current):
292    """Fuzz magic field of a header extension."""
293    constraints = UINT32_V
294    return selector(current, constraints)
295
296
297def ext_length(current):
298    """Fuzz length field of a header extension."""
299    constraints = UINT32_V
300    return selector(current, constraints)
301
302
303def 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
312def 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
318def 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
324def 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
333def 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
344def 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
359def refcount_table_entry(current):
360    """Fuzz an entry of the refcount table."""
361    constraints = UINT64_V
362    return selector(current, constraints)
363
364
365def refcount_block_entry(current):
366    """Fuzz an entry of a refcount block."""
367    constraints = UINT16_V
368    return selector(current, constraints)
369