Branch data Line data Source code
1 : : // Copyright (c) 2023-present The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #ifndef BITCOIN_TEST_FUZZ_UTIL_DESCRIPTOR_H
6 : : #define BITCOIN_TEST_FUZZ_UTIL_DESCRIPTOR_H
7 : :
8 : : #include <array>
9 : : #include <cinttypes>
10 : : #include <cstddef>
11 : : #include <limits>
12 : : #include <optional>
13 : : #include <span>
14 : : #include <string>
15 : : #include <string_view>
16 : :
17 : : /**
18 : : * Converts a mocked descriptor string to a valid one. Every key in a mocked descriptor is
19 : : * represented by 2 hex characters preceded by the '%' character. We parse the two hex characters
20 : : * as an index in a list of pre-generated keys. This list contains keys of the various types
21 : : * accepted in descriptor key expressions.
22 : : */
23 : : class MockedDescriptorConverter {
24 : : private:
25 : : //! Types are raw (un)compressed pubkeys, raw xonly pubkeys, raw privkeys (WIF), xpubs, xprvs.
26 : : static constexpr uint8_t KEY_TYPES_COUNT{6};
27 : : //! How many keys we'll generate in total.
28 : : static constexpr size_t TOTAL_KEYS_GENERATED{std::numeric_limits<uint8_t>::max() + 1};
29 : : //! 256 keys of various types.
30 : : std::array<std::string, TOTAL_KEYS_GENERATED> keys_str;
31 : :
32 : : public:
33 : : // We derive the type of key to generate from the 1-byte id parsed from hex.
34 [ + + ]: 512 : bool IdIsCompPubKey(uint8_t idx) const { return idx % KEY_TYPES_COUNT == 0; }
35 : : bool IdIsUnCompPubKey(uint8_t idx) const { return idx % KEY_TYPES_COUNT == 1; }
36 : : bool IdIsXOnlyPubKey(uint8_t idx) const { return idx % KEY_TYPES_COUNT == 2; }
37 : : bool IdIsConstPrivKey(uint8_t idx) const { return idx % KEY_TYPES_COUNT == 3; }
38 : : bool IdIsXprv(uint8_t idx) const { return idx % KEY_TYPES_COUNT == 5; }
39 : :
40 : : //! When initializing the target, populate the list of keys.
41 : : void Init();
42 : :
43 : : //! Parse an id in the keys vectors from a 2-characters hex string.
44 : : std::optional<uint8_t> IdxFromHex(std::string_view hex_characters) const;
45 : :
46 : : //! Get an actual descriptor string from a descriptor string whose keys were mocked.
47 : : std::optional<std::string> GetDescriptor(std::string_view mocked_desc) const;
48 : : };
49 : :
50 : : //! Default maximum number of derivation indexes in a single derivation path when limiting its depth.
51 : : inline constexpr int MAX_DEPTH{2};
52 : :
53 : : /**
54 : : * Whether the buffer, if it represents a valid descriptor, contains a derivation path deeper than
55 : : * a given maximum depth. Note this may also be hit for deriv paths in origins.
56 : : */
57 : : bool HasDeepDerivPath(std::span<const uint8_t> buff, int max_depth = MAX_DEPTH);
58 : :
59 : : //! Default maximum number of sub-fragments.
60 : : inline constexpr int MAX_SUBS{1'000};
61 : : //! Maximum number of nested sub-fragments we'll allow in a descriptor.
62 : : inline constexpr size_t MAX_NESTED_SUBS{10'000};
63 : :
64 : : /**
65 : : * Whether the buffer, if it represents a valid descriptor, contains a fragment with more
66 : : * sub-fragments than the given maximum.
67 : : */
68 : : bool HasTooManySubFrag(std::span<const uint8_t> buff, int max_subs = MAX_SUBS,
69 : : size_t max_nested_subs = MAX_NESTED_SUBS);
70 : :
71 : : //! Default maximum number of wrappers per fragment.
72 : : inline constexpr int MAX_WRAPPERS{100};
73 : :
74 : : /**
75 : : * Whether the buffer, if it represents a valid descriptor, contains a fragment with more
76 : : * wrappers than the given maximum.
77 : : */
78 : : bool HasTooManyWrappers(std::span<const uint8_t> buff, int max_wrappers = MAX_WRAPPERS);
79 : :
80 : : /// Default maximum leaf size. This should be large enough to cover an extended
81 : : /// key, including paths "/", inside and outside of "[]".
82 : : inline constexpr uint32_t MAX_LEAF_SIZE{200};
83 : :
84 : : /// Whether the expanded buffer (after calling GetDescriptor() in
85 : : /// MockedDescriptorConverter) has a leaf size too large.
86 : : bool HasTooLargeLeafSize(std::span<const uint8_t> buff, uint32_t max_leaf_size = MAX_LEAF_SIZE);
87 : :
88 : : /// Deriving "expensive" descriptors will consume useful fuzz compute. The
89 : : /// compute is better spent on a smaller subset of descriptors, which still
90 : : /// covers all real end-user settings.
91 : : ///
92 : : /// Use this function after MockedDescriptorConverter::GetDescriptor()
93 : 19279 : inline bool IsTooExpensive(std::span<const uint8_t> buffer)
94 : : {
95 : : // Key derivation is expensive. Deriving deep derivation paths takes a lot of compute and we'd
96 : : // rather spend time elsewhere in this target, like on the actual descriptor syntax. So rule
97 : : // out strings which could correspond to a descriptor containing a too large derivation path.
98 [ + + ]: 19279 : if (HasDeepDerivPath(buffer)) return true;
99 : :
100 : : // Some fragments can take a virtually unlimited number of sub-fragments (thresh, multi_a) but
101 : : // may perform quadratic operations on them. Limit the number of sub-fragments per fragment.
102 [ + + ]: 19273 : if (HasTooManySubFrag(buffer)) return true;
103 : :
104 : : // The script building logic performs quadratic copies in the number of nested wrappers. Limit
105 : : // the number of nested wrappers per fragment.
106 [ + + ]: 19263 : if (HasTooManyWrappers(buffer)) return true;
107 : :
108 : : // If any suspected leaf is too large, it will likely not represent a valid
109 : : // use-case. Also, possible base58 parsing in the leaf is quadratic. So
110 : : // limit the leaf size.
111 [ + + ]: 19251 : if (HasTooLargeLeafSize(buffer)) return true;
112 : :
113 : : return false;
114 : : }
115 : : #endif // BITCOIN_TEST_FUZZ_UTIL_DESCRIPTOR_H
|
