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 #include <test/fuzz/util/descriptor.h>
6 7 #include <key.h>
8 #include <key_io.h>
9 #include <pubkey.h>
10 #include <span.h>
11 #include <util/strencodings.h>
12 13 #include <ranges>
14 #include <stack>
15 #include <vector>
16 17 void MockedDescriptorConverter::Init()
18 {
19 // The data to use as a private key or a seed for an xprv.
20 std::array<std::byte, 32> key_data{std::byte{1}};
21 // Generate keys of all kinds and store them in the keys array.
22 for (size_t i{0}; i < TOTAL_KEYS_GENERATED; i++) {
23 key_data[31] = std::byte(i);
24 25 // If this is a "raw" key, generate a normal privkey. Otherwise generate
26 // an extended one.
27 if (IdIsCompPubKey(i) || IdIsUnCompPubKey(i) || IdIsXOnlyPubKey(i) || IdIsConstPrivKey(i)) {
28 CKey privkey;
29 privkey.Set(key_data.begin(), key_data.end(), !IdIsUnCompPubKey(i));
30 if (IdIsCompPubKey(i) || IdIsUnCompPubKey(i)) {
31 CPubKey pubkey{privkey.GetPubKey()};
32 keys_str[i] = HexStr(pubkey);
33 } else if (IdIsXOnlyPubKey(i)) {
34 const XOnlyPubKey pubkey{privkey.GetPubKey()};
35 keys_str[i] = HexStr(pubkey);
36 } else {
37 keys_str[i] = EncodeSecret(privkey);
38 }
39 } else {
40 CExtKey ext_privkey;
41 ext_privkey.SetSeed(key_data);
42 if (IdIsXprv(i)) {
43 keys_str[i] = EncodeExtKey(ext_privkey);
44 } else {
45 const CExtPubKey ext_pubkey{ext_privkey.Neuter()};
46 keys_str[i] = EncodeExtPubKey(ext_pubkey);
47 }
48 }
49 }
50 }
51 52 std::optional<uint8_t> MockedDescriptorConverter::IdxFromHex(std::string_view hex_characters) const {
53 if (hex_characters.size() != 2) return {};
54 auto idx = ParseHex(hex_characters);
55 if (idx.size() != 1) return {};
56 return idx[0];
57 }
58 59 std::optional<std::string> MockedDescriptorConverter::GetDescriptor(std::string_view mocked_desc) const {
60 // The smallest fragment would be "pk(%00)"
61 if (mocked_desc.size() < 7) return {};
62 63 // The actual descriptor string to be returned.
64 std::string desc;
65 desc.reserve(mocked_desc.size());
66 67 // Replace all occurrences of '%' followed by two hex characters with the corresponding key.
68 for (size_t i = 0; i < mocked_desc.size();) {
69 if (mocked_desc[i] == '%') {
70 if (i + 3 >= mocked_desc.size()) return {};
71 if (const auto idx = IdxFromHex(mocked_desc.substr(i + 1, 2))) {
72 desc += keys_str[*idx];
73 i += 3;
74 } else {
75 return {};
76 }
77 } else {
78 desc += mocked_desc[i++];
79 }
80 }
81 82 return desc;
83 }
84 85 bool HasDeepDerivPath(std::span<const uint8_t> buff, const int max_depth)
86 {
87 auto depth{0};
88 for (const auto& ch: buff) {
89 if (ch == ',') {
90 // A comma is always present between two key expressions, so we use that as a delimiter.
91 depth = 0;
92 } else if (ch == '/') {
93 if (++depth > max_depth) return true;
94 }
95 }
96 return false;
97 }
98 99 bool HasTooManySubFrag(std::span<const uint8_t> buff, const int max_subs, const size_t max_nested_subs)
100 {
101 // We use a stack because there may be many nested sub-frags.
102 std::stack<int> counts;
103 for (const auto& ch: buff) {
104 // The fuzzer may generate an input with a ton of parentheses. Rule out pathological cases.
105 if (counts.size() > max_nested_subs) return true;
106 107 if (ch == '(') {
108 // A new fragment was opened, create a new sub-count for it and start as one since any fragment with
109 // parentheses has at least one sub.
110 counts.push(1);
111 } else if (ch == ',' && !counts.empty()) {
112 // When encountering a comma, account for an additional sub in the last opened fragment. If it exceeds the
113 // limit, bail.
114 if (++counts.top() > max_subs) return true;
115 } else if (ch == ')' && !counts.empty()) {
116 // Fragment closed! Drop its sub count and resume to counting the number of subs for its parent.
117 counts.pop();
118 }
119 }
120 return false;
121 }
122 123 bool HasTooManyWrappers(std::span<const uint8_t> buff, const int max_wrappers)
124 {
125 // The number of nested wrappers. Nested wrappers are always characters which follow each other so we don't have to
126 // use a stack as we do above when counting the number of sub-fragments.
127 std::optional<int> count;
128 129 // We want to detect nested wrappers. A wrapper is a character prepended to a fragment, separated by a colon. There
130 // may be more than one wrapper, in which case the colon is not repeated. For instance `jjjjj:pk()`. To count
131 // wrappers we iterate in reverse and use the colon to detect the end of a wrapper expression and count how many
132 // characters there are since the beginning of the expression. We stop counting when we encounter a character
133 // indicating the beginning of a new expression.
134 for (const auto ch: buff | std::views::reverse) {
135 // A colon, start counting.
136 if (ch == ':') {
137 // The colon itself is not a wrapper so we start at 0.
138 count = 0;
139 } else if (count) {
140 // If we are counting wrappers, stop when we crossed the beginning of the wrapper expression. Otherwise keep
141 // counting and bail if we reached the limit.
142 // A wrapper may only ever occur as the first sub of a descriptor/miniscript expression ('('), as the
143 // first Taproot leaf in a pair ('{') or as the nth sub in each case (',').
144 if (ch == ',' || ch == '(' || ch == '{') {
145 count.reset();
146 } else if (++*count > max_wrappers) {
147 return true;
148 }
149 }
150 }
151 152 return false;
153 }
154 155 bool HasTooLargeLeafSize(std::span<const uint8_t> buff, const uint32_t max_leaf_size)
156 {
157 uint32_t leaf_len{0};
158 for (auto c : buff) {
159 if (c == '(' || c == ')' || c == ',' || c == '{' || c == '}') {
160 // Possibly start a fresh leaf, or a fresh function name (with
161 // wrappers), or terminate a prior leaf.
162 leaf_len = 0;
163 } else {
164 // Just treat everything else as a leaf. This will also reject long
165 // function names, but this should be fine if the max_leaf_size is
166 // set large enough.
167 if (++leaf_len > max_leaf_size) {
168 return true;
169 }
170 }
171 }
172 return false;
173 }
174