16d5e9372SMaria Kustova# Fuzzing functions for qcow2 fields 26d5e9372SMaria Kustova# 36d5e9372SMaria Kustova# Copyright (C) 2014 Maria Kustova <maria.k@catit.be> 46d5e9372SMaria Kustova# 56d5e9372SMaria Kustova# This program is free software: you can redistribute it and/or modify 66d5e9372SMaria Kustova# it under the terms of the GNU General Public License as published by 76d5e9372SMaria Kustova# the Free Software Foundation, either version 2 of the License, or 86d5e9372SMaria Kustova# (at your option) any later version. 96d5e9372SMaria Kustova# 106d5e9372SMaria Kustova# This program is distributed in the hope that it will be useful, 116d5e9372SMaria Kustova# but WITHOUT ANY WARRANTY; without even the implied warranty of 126d5e9372SMaria Kustova# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 136d5e9372SMaria Kustova# GNU General Public License for more details. 146d5e9372SMaria Kustova# 156d5e9372SMaria Kustova# You should have received a copy of the GNU General Public License 166d5e9372SMaria Kustova# along with this program. If not, see <http://www.gnu.org/licenses/>. 176d5e9372SMaria Kustova# 186d5e9372SMaria Kustova 196d5e9372SMaria Kustovaimport random 208d2860cbSEduardo Habkostfrom functools import reduce 216d5e9372SMaria Kustova 226d5e9372SMaria KustovaUINT8 = 0xff 232e5be6b7SMaria KustovaUINT16 = 0xffff 246d5e9372SMaria KustovaUINT32 = 0xffffffff 256d5e9372SMaria KustovaUINT64 = 0xffffffffffffffff 266d5e9372SMaria Kustova# Most significant bit orders 276d5e9372SMaria KustovaUINT32_M = 31 286d5e9372SMaria KustovaUINT64_M = 63 296d5e9372SMaria Kustova# Fuzz vectors 30d974451cSEduardo HabkostUINT8_V = [0, 0x10, UINT8//4, UINT8//2 - 1, UINT8//2, UINT8//2 + 1, UINT8 - 1, 316d5e9372SMaria Kustova UINT8] 32d974451cSEduardo HabkostUINT16_V = [0, 0x100, 0x1000, UINT16//4, UINT16//2 - 1, UINT16//2, UINT16//2 + 1, 332e5be6b7SMaria Kustova UINT16 - 1, UINT16] 34d974451cSEduardo HabkostUINT32_V = [0, 0x100, 0x1000, 0x10000, 0x100000, UINT32//4, UINT32//2 - 1, 35d974451cSEduardo Habkost UINT32//2, UINT32//2 + 1, UINT32 - 1, UINT32] 36d974451cSEduardo HabkostUINT64_V = UINT32_V + [0x1000000, 0x10000000, 0x100000000, UINT64//4, 37d974451cSEduardo Habkost UINT64//2 - 1, UINT64//2, UINT64//2 + 1, UINT64 - 1, 386d5e9372SMaria Kustova UINT64] 39*71858451SEduardo HabkostBYTES_V = [b'%s%p%x%d', b'.1024d', b'%.2049d', b'%p%p%p%p', b'%x%x%x%x', 40*71858451SEduardo Habkost b'%d%d%d%d', b'%s%s%s%s', b'%99999999999s', b'%08x', b'%%20d', b'%%20n', 41*71858451SEduardo Habkost 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*71858451SEduardo Habkost 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*71858451SEduardo Habkost b'%s x 129', b'%x x 257'] 446d5e9372SMaria Kustova 456d5e9372SMaria Kustova 466d5e9372SMaria Kustovadef random_from_intervals(intervals): 476d5e9372SMaria Kustova """Select a random integer number from the list of specified intervals. 486d5e9372SMaria Kustova 496d5e9372SMaria Kustova Each interval is a tuple of lower and upper limits of the interval. The 506d5e9372SMaria Kustova limits are included. Intervals in a list should not overlap. 516d5e9372SMaria Kustova """ 526d5e9372SMaria Kustova total = reduce(lambda x, y: x + y[1] - y[0] + 1, intervals, 0) 536d5e9372SMaria Kustova r = random.randint(0, total - 1) + intervals[0][0] 546d5e9372SMaria Kustova for x in zip(intervals, intervals[1:]): 556d5e9372SMaria Kustova r = r + (r > x[0][1]) * (x[1][0] - x[0][1] - 1) 566d5e9372SMaria Kustova return r 576d5e9372SMaria Kustova 586d5e9372SMaria Kustova 596d5e9372SMaria Kustovadef random_bits(bit_ranges): 606d5e9372SMaria Kustova """Generate random binary mask with ones in the specified bit ranges. 616d5e9372SMaria Kustova 626d5e9372SMaria Kustova Each bit_ranges is a list of tuples of lower and upper limits of bit 636d5e9372SMaria Kustova positions will be fuzzed. The limits are included. Random amount of bits 646d5e9372SMaria Kustova in range limits will be set to ones. The mask is returned in decimal 656d5e9372SMaria Kustova integer format. 666d5e9372SMaria Kustova """ 676d5e9372SMaria Kustova bit_numbers = [] 686d5e9372SMaria Kustova # Select random amount of random positions in bit_ranges 696d5e9372SMaria Kustova for rng in bit_ranges: 706d5e9372SMaria Kustova bit_numbers += random.sample(range(rng[0], rng[1] + 1), 716d5e9372SMaria Kustova random.randint(0, rng[1] - rng[0] + 1)) 726d5e9372SMaria Kustova val = 0 736d5e9372SMaria Kustova # Set bits on selected positions to ones 746d5e9372SMaria Kustova for bit in bit_numbers: 756d5e9372SMaria Kustova val |= 1 << bit 766d5e9372SMaria Kustova return val 776d5e9372SMaria Kustova 786d5e9372SMaria Kustova 79*71858451SEduardo Habkostdef truncate_bytes(sequences, length): 80*71858451SEduardo Habkost """Return sequences truncated to specified length.""" 81*71858451SEduardo Habkost if type(sequences) == list: 82*71858451SEduardo Habkost return [s[:length] for s in sequences] 836d5e9372SMaria Kustova else: 84*71858451SEduardo Habkost return sequences[:length] 856d5e9372SMaria Kustova 866d5e9372SMaria Kustova 876d5e9372SMaria Kustovadef validator(current, pick, choices): 886d5e9372SMaria Kustova """Return a value not equal to the current selected by the pick 896d5e9372SMaria Kustova function from choices. 906d5e9372SMaria Kustova """ 916d5e9372SMaria Kustova while True: 926d5e9372SMaria Kustova val = pick(choices) 936d5e9372SMaria Kustova if not val == current: 946d5e9372SMaria Kustova return val 956d5e9372SMaria Kustova 966d5e9372SMaria Kustova 976d5e9372SMaria Kustovadef int_validator(current, intervals): 986d5e9372SMaria Kustova """Return a random value from intervals not equal to the current. 996d5e9372SMaria Kustova 1006d5e9372SMaria Kustova This function is useful for selection from valid values except current one. 1016d5e9372SMaria Kustova """ 1026d5e9372SMaria Kustova return validator(current, random_from_intervals, intervals) 1036d5e9372SMaria Kustova 1046d5e9372SMaria Kustova 1056d5e9372SMaria Kustovadef bit_validator(current, bit_ranges): 1066d5e9372SMaria Kustova """Return a random bit mask not equal to the current. 1076d5e9372SMaria Kustova 1086d5e9372SMaria Kustova This function is useful for selection from valid values except current one. 1096d5e9372SMaria Kustova """ 1106d5e9372SMaria Kustova return validator(current, random_bits, bit_ranges) 1116d5e9372SMaria Kustova 1126d5e9372SMaria Kustova 113*71858451SEduardo Habkostdef bytes_validator(current, sequences): 114*71858451SEduardo Habkost """Return a random bytes value from the list not equal to the current. 1156d5e9372SMaria Kustova 1166d5e9372SMaria Kustova This function is useful for selection from valid values except current one. 1176d5e9372SMaria Kustova """ 118*71858451SEduardo Habkost return validator(current, random.choice, sequences) 1196d5e9372SMaria Kustova 1206d5e9372SMaria Kustova 1216d5e9372SMaria Kustovadef selector(current, constraints, validate=int_validator): 1226d5e9372SMaria Kustova """Select one value from all defined by constraints. 1236d5e9372SMaria Kustova 1246d5e9372SMaria Kustova Each constraint produces one random value satisfying to it. The function 1256d5e9372SMaria Kustova randomly selects one value satisfying at least one constraint (depending on 1266d5e9372SMaria Kustova constraints overlaps). 1276d5e9372SMaria Kustova """ 1286d5e9372SMaria Kustova def iter_validate(c): 1296d5e9372SMaria Kustova """Apply validate() only to constraints represented as lists. 1306d5e9372SMaria Kustova 1316d5e9372SMaria Kustova This auxiliary function replaces short circuit conditions not supported 1326d5e9372SMaria Kustova in Python 2.4 1336d5e9372SMaria Kustova """ 1346d5e9372SMaria Kustova if type(c) == list: 1356d5e9372SMaria Kustova return validate(current, c) 1366d5e9372SMaria Kustova else: 1376d5e9372SMaria Kustova return c 1386d5e9372SMaria Kustova 1396d5e9372SMaria Kustova fuzz_values = [iter_validate(c) for c in constraints] 1406d5e9372SMaria Kustova # Remove current for cases it's implicitly specified in constraints 1416d5e9372SMaria Kustova # Duplicate validator functionality to prevent decreasing of probability 1426d5e9372SMaria Kustova # to get one of allowable values 1436d5e9372SMaria Kustova # TODO: remove validators after implementation of intelligent selection 1446d5e9372SMaria Kustova # of fields will be fuzzed 1456d5e9372SMaria Kustova try: 1466d5e9372SMaria Kustova fuzz_values.remove(current) 1476d5e9372SMaria Kustova except ValueError: 1486d5e9372SMaria Kustova pass 1496d5e9372SMaria Kustova return random.choice(fuzz_values) 1506d5e9372SMaria Kustova 1516d5e9372SMaria Kustova 1526d5e9372SMaria Kustovadef magic(current): 1536d5e9372SMaria Kustova """Fuzz magic header field. 1546d5e9372SMaria Kustova 1556d5e9372SMaria Kustova The function just returns the current magic value and provides uniformity 1566d5e9372SMaria Kustova of calls for all fuzzing functions. 1576d5e9372SMaria Kustova """ 1586d5e9372SMaria Kustova return current 1596d5e9372SMaria Kustova 1606d5e9372SMaria Kustova 1616d5e9372SMaria Kustovadef version(current): 1626d5e9372SMaria Kustova """Fuzz version header field.""" 1636d5e9372SMaria Kustova constraints = UINT32_V + [ 1646d5e9372SMaria Kustova [(2, 3)], # correct values 1656d5e9372SMaria Kustova [(0, 1), (4, UINT32)] 1666d5e9372SMaria Kustova ] 1676d5e9372SMaria Kustova return selector(current, constraints) 1686d5e9372SMaria Kustova 1696d5e9372SMaria Kustova 1706d5e9372SMaria Kustovadef backing_file_offset(current): 1716d5e9372SMaria Kustova """Fuzz backing file offset header field.""" 1726d5e9372SMaria Kustova constraints = UINT64_V 1736d5e9372SMaria Kustova return selector(current, constraints) 1746d5e9372SMaria Kustova 1756d5e9372SMaria Kustova 1766d5e9372SMaria Kustovadef backing_file_size(current): 1776d5e9372SMaria Kustova """Fuzz backing file size header field.""" 1786d5e9372SMaria Kustova constraints = UINT32_V 1796d5e9372SMaria Kustova return selector(current, constraints) 1806d5e9372SMaria Kustova 1816d5e9372SMaria Kustova 1826d5e9372SMaria Kustovadef cluster_bits(current): 1836d5e9372SMaria Kustova """Fuzz cluster bits header field.""" 1846d5e9372SMaria Kustova constraints = UINT32_V + [ 1856d5e9372SMaria Kustova [(9, 20)], # correct values 1866d5e9372SMaria Kustova [(0, 9), (20, UINT32)] 1876d5e9372SMaria Kustova ] 1886d5e9372SMaria Kustova return selector(current, constraints) 1896d5e9372SMaria Kustova 1906d5e9372SMaria Kustova 1916d5e9372SMaria Kustovadef size(current): 1926d5e9372SMaria Kustova """Fuzz image size header field.""" 1936d5e9372SMaria Kustova constraints = UINT64_V 1946d5e9372SMaria Kustova return selector(current, constraints) 1956d5e9372SMaria Kustova 1966d5e9372SMaria Kustova 1976d5e9372SMaria Kustovadef crypt_method(current): 1986d5e9372SMaria Kustova """Fuzz crypt method header field.""" 1996d5e9372SMaria Kustova constraints = UINT32_V + [ 2006d5e9372SMaria Kustova 1, 2016d5e9372SMaria Kustova [(2, UINT32)] 2026d5e9372SMaria Kustova ] 2036d5e9372SMaria Kustova return selector(current, constraints) 2046d5e9372SMaria Kustova 2056d5e9372SMaria Kustova 2066d5e9372SMaria Kustovadef l1_size(current): 2076d5e9372SMaria Kustova """Fuzz L1 table size header field.""" 2086d5e9372SMaria Kustova constraints = UINT32_V 2096d5e9372SMaria Kustova return selector(current, constraints) 2106d5e9372SMaria Kustova 2116d5e9372SMaria Kustova 2126d5e9372SMaria Kustovadef l1_table_offset(current): 2136d5e9372SMaria Kustova """Fuzz L1 table offset header field.""" 2146d5e9372SMaria Kustova constraints = UINT64_V 2156d5e9372SMaria Kustova return selector(current, constraints) 2166d5e9372SMaria Kustova 2176d5e9372SMaria Kustova 2186d5e9372SMaria Kustovadef refcount_table_offset(current): 2196d5e9372SMaria Kustova """Fuzz refcount table offset header field.""" 2206d5e9372SMaria Kustova constraints = UINT64_V 2216d5e9372SMaria Kustova return selector(current, constraints) 2226d5e9372SMaria Kustova 2236d5e9372SMaria Kustova 2246d5e9372SMaria Kustovadef refcount_table_clusters(current): 2256d5e9372SMaria Kustova """Fuzz refcount table clusters header field.""" 2266d5e9372SMaria Kustova constraints = UINT32_V 2276d5e9372SMaria Kustova return selector(current, constraints) 2286d5e9372SMaria Kustova 2296d5e9372SMaria Kustova 2306d5e9372SMaria Kustovadef nb_snapshots(current): 2316d5e9372SMaria Kustova """Fuzz number of snapshots header field.""" 2326d5e9372SMaria Kustova constraints = UINT32_V 2336d5e9372SMaria Kustova return selector(current, constraints) 2346d5e9372SMaria Kustova 2356d5e9372SMaria Kustova 2366d5e9372SMaria Kustovadef snapshots_offset(current): 2376d5e9372SMaria Kustova """Fuzz snapshots offset header field.""" 2386d5e9372SMaria Kustova constraints = UINT64_V 2396d5e9372SMaria Kustova return selector(current, constraints) 2406d5e9372SMaria Kustova 2416d5e9372SMaria Kustova 2426d5e9372SMaria Kustovadef incompatible_features(current): 2436d5e9372SMaria Kustova """Fuzz incompatible features header field.""" 2446d5e9372SMaria Kustova constraints = [ 2456d5e9372SMaria Kustova [(0, 1)], # allowable values 2466d5e9372SMaria Kustova [(0, UINT64_M)] 2476d5e9372SMaria Kustova ] 2486d5e9372SMaria Kustova return selector(current, constraints, bit_validator) 2496d5e9372SMaria Kustova 2506d5e9372SMaria Kustova 2516d5e9372SMaria Kustovadef compatible_features(current): 2526d5e9372SMaria Kustova """Fuzz compatible features header field.""" 2536d5e9372SMaria Kustova constraints = [ 2546d5e9372SMaria Kustova [(0, UINT64_M)] 2556d5e9372SMaria Kustova ] 2566d5e9372SMaria Kustova return selector(current, constraints, bit_validator) 2576d5e9372SMaria Kustova 2586d5e9372SMaria Kustova 2596d5e9372SMaria Kustovadef autoclear_features(current): 2606d5e9372SMaria Kustova """Fuzz autoclear features header field.""" 2616d5e9372SMaria Kustova constraints = [ 2626d5e9372SMaria Kustova [(0, UINT64_M)] 2636d5e9372SMaria Kustova ] 2646d5e9372SMaria Kustova return selector(current, constraints, bit_validator) 2656d5e9372SMaria Kustova 2666d5e9372SMaria Kustova 2676d5e9372SMaria Kustovadef refcount_order(current): 2686d5e9372SMaria Kustova """Fuzz number of refcount order header field.""" 2696d5e9372SMaria Kustova constraints = UINT32_V 2706d5e9372SMaria Kustova return selector(current, constraints) 2716d5e9372SMaria Kustova 2726d5e9372SMaria Kustova 2736d5e9372SMaria Kustovadef header_length(current): 2746d5e9372SMaria Kustova """Fuzz number of refcount order header field.""" 2756d5e9372SMaria Kustova constraints = UINT32_V + [ 2766d5e9372SMaria Kustova 72, 2776d5e9372SMaria Kustova 104, 2786d5e9372SMaria Kustova [(0, UINT32)] 2796d5e9372SMaria Kustova ] 2806d5e9372SMaria Kustova return selector(current, constraints) 2816d5e9372SMaria Kustova 2826d5e9372SMaria Kustova 2836d5e9372SMaria Kustovadef bf_name(current): 2846d5e9372SMaria Kustova """Fuzz the backing file name.""" 2856d5e9372SMaria Kustova constraints = [ 286*71858451SEduardo Habkost truncate_bytes(BYTES_V, len(current)) 2876d5e9372SMaria Kustova ] 288*71858451SEduardo Habkost return selector(current, constraints, bytes_validator) 2896d5e9372SMaria Kustova 2906d5e9372SMaria Kustova 2916d5e9372SMaria Kustovadef ext_magic(current): 2926d5e9372SMaria Kustova """Fuzz magic field of a header extension.""" 2936d5e9372SMaria Kustova constraints = UINT32_V 2946d5e9372SMaria Kustova return selector(current, constraints) 2956d5e9372SMaria Kustova 2966d5e9372SMaria Kustova 2976d5e9372SMaria Kustovadef ext_length(current): 2986d5e9372SMaria Kustova """Fuzz length field of a header extension.""" 2996d5e9372SMaria Kustova constraints = UINT32_V 3006d5e9372SMaria Kustova return selector(current, constraints) 3016d5e9372SMaria Kustova 3026d5e9372SMaria Kustova 3036d5e9372SMaria Kustovadef bf_format(current): 3046d5e9372SMaria Kustova """Fuzz backing file format in the corresponding header extension.""" 3056d5e9372SMaria Kustova constraints = [ 306*71858451SEduardo Habkost truncate_bytes(BYTES_V, len(current)), 307*71858451SEduardo Habkost truncate_bytes(BYTES_V, (len(current) + 7) & ~7) # Fuzz padding 3086d5e9372SMaria Kustova ] 309*71858451SEduardo Habkost return selector(current, constraints, bytes_validator) 3106d5e9372SMaria Kustova 3116d5e9372SMaria Kustova 3126d5e9372SMaria Kustovadef feature_type(current): 3136d5e9372SMaria Kustova """Fuzz feature type field of a feature name table header extension.""" 3146d5e9372SMaria Kustova constraints = UINT8_V 3156d5e9372SMaria Kustova return selector(current, constraints) 3166d5e9372SMaria Kustova 3176d5e9372SMaria Kustova 3186d5e9372SMaria Kustovadef feature_bit_number(current): 3196d5e9372SMaria Kustova """Fuzz bit number field of a feature name table header extension.""" 3206d5e9372SMaria Kustova constraints = UINT8_V 3216d5e9372SMaria Kustova return selector(current, constraints) 3226d5e9372SMaria Kustova 3236d5e9372SMaria Kustova 3246d5e9372SMaria Kustovadef feature_name(current): 3256d5e9372SMaria Kustova """Fuzz feature name field of a feature name table header extension.""" 3266d5e9372SMaria Kustova constraints = [ 327*71858451SEduardo Habkost truncate_bytes(BYTES_V, len(current)), 328*71858451SEduardo Habkost truncate_bytes(BYTES_V, 46) # Fuzz padding (field length = 46) 3296d5e9372SMaria Kustova ] 330*71858451SEduardo Habkost return selector(current, constraints, bytes_validator) 331eeadd924SMaria Kustova 332eeadd924SMaria Kustova 333eeadd924SMaria Kustovadef l1_entry(current): 334eeadd924SMaria Kustova """Fuzz an entry of the L1 table.""" 335eeadd924SMaria Kustova constraints = UINT64_V 336eeadd924SMaria Kustova # Reserved bits are ignored 337eeadd924SMaria Kustova # Added a possibility when only flags are fuzzed 338407ba084SMaria Kustova offset = 0x7fffffffffffffff & \ 339407ba084SMaria Kustova random.choice([selector(current, constraints), current]) 340eeadd924SMaria Kustova is_cow = random.randint(0, 1) 341eeadd924SMaria Kustova return offset + (is_cow << UINT64_M) 342eeadd924SMaria Kustova 343eeadd924SMaria Kustova 344eeadd924SMaria Kustovadef l2_entry(current): 345eeadd924SMaria Kustova """Fuzz an entry of an L2 table.""" 346eeadd924SMaria Kustova constraints = UINT64_V 347eeadd924SMaria Kustova # Reserved bits are ignored 348eeadd924SMaria Kustova # Add a possibility when only flags are fuzzed 349407ba084SMaria Kustova offset = 0x3ffffffffffffffe & \ 350407ba084SMaria Kustova random.choice([selector(current, constraints), current]) 351eeadd924SMaria Kustova is_compressed = random.randint(0, 1) 352eeadd924SMaria Kustova is_cow = random.randint(0, 1) 353eeadd924SMaria Kustova is_zero = random.randint(0, 1) 354eeadd924SMaria Kustova value = offset + (is_cow << UINT64_M) + \ 355eeadd924SMaria Kustova (is_compressed << UINT64_M - 1) + is_zero 356eeadd924SMaria Kustova return value 3572e5be6b7SMaria Kustova 3582e5be6b7SMaria Kustova 3592e5be6b7SMaria Kustovadef refcount_table_entry(current): 3602e5be6b7SMaria Kustova """Fuzz an entry of the refcount table.""" 3612e5be6b7SMaria Kustova constraints = UINT64_V 3622e5be6b7SMaria Kustova return selector(current, constraints) 3632e5be6b7SMaria Kustova 3642e5be6b7SMaria Kustova 3652e5be6b7SMaria Kustovadef refcount_block_entry(current): 3662e5be6b7SMaria Kustova """Fuzz an entry of a refcount block.""" 3672e5be6b7SMaria Kustova constraints = UINT16_V 3682e5be6b7SMaria Kustova return selector(current, constraints) 369