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