Branch data Line data Source code
1 : : // Copyright (c) 2021-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 <script/miniscript.h>
6 : :
7 : : #include <core_io.h>
8 : : #include <hash.h>
9 : : #include <key.h>
10 : : #include <script/script.h>
11 : : #include <script/signingprovider.h>
12 : : #include <test/fuzz/FuzzedDataProvider.h>
13 : : #include <test/fuzz/fuzz.h>
14 : : #include <test/fuzz/util.h>
15 : : #include <test/fuzz/util/descriptor.h>
16 : : #include <util/check.h>
17 : : #include <util/strencodings.h>
18 : :
19 : : #include <algorithm>
20 : : #include <map>
21 : : #include <optional>
22 : : #include <vector>
23 : :
24 : : namespace {
25 : :
26 : : using Fragment = miniscript::Fragment;
27 : : using Node = miniscript::Node<CPubKey>;
28 : : using Type = miniscript::Type;
29 : : using MsCtx = miniscript::MiniscriptContext;
30 : : using miniscript::operator""_mst;
31 : :
32 : : //! Some pre-computed data for more efficient string roundtrips and to simulate challenges.
33 : : struct TestData {
34 : : typedef CPubKey Key;
35 : :
36 : : // Precomputed public keys, and a dummy signature for each of them.
37 : : std::vector<Key> dummy_keys;
38 : : std::map<Key, int> dummy_key_idx_map;
39 : : std::map<CKeyID, Key> dummy_keys_map;
40 : : std::map<Key, std::pair<std::vector<unsigned char>, bool>> dummy_sigs;
41 : : std::map<XOnlyPubKey, std::pair<std::vector<unsigned char>, bool>> schnorr_sigs;
42 : :
43 : : // Precomputed hashes of each kind.
44 : : std::vector<std::vector<unsigned char>> sha256;
45 : : std::vector<std::vector<unsigned char>> ripemd160;
46 : : std::vector<std::vector<unsigned char>> hash256;
47 : : std::vector<std::vector<unsigned char>> hash160;
48 : : std::map<std::vector<unsigned char>, std::vector<unsigned char>> sha256_preimages;
49 : : std::map<std::vector<unsigned char>, std::vector<unsigned char>> ripemd160_preimages;
50 : : std::map<std::vector<unsigned char>, std::vector<unsigned char>> hash256_preimages;
51 : : std::map<std::vector<unsigned char>, std::vector<unsigned char>> hash160_preimages;
52 : :
53 : : //! Set the precomputed data.
54 : 3 : void Init() {
55 : 3 : unsigned char keydata[32] = {1};
56 : : // All our signatures sign (and are required to sign) this constant message.
57 : 3 : constexpr uint256 MESSAGE_HASH{"0000000000000000f5cd94e18b6fe77dd7aca9e35c2b0c9cbd86356c80a71065"};
58 : : // We don't pass additional randomness when creating a schnorr signature.
59 : 3 : const auto EMPTY_AUX{uint256::ZERO};
60 : :
61 [ + + ]: 771 : for (size_t i = 0; i < 256; i++) {
62 : 768 : keydata[31] = i;
63 : 768 : CKey privkey;
64 [ + - ]: 768 : privkey.Set(keydata, keydata + 32, true);
65 [ + - ]: 768 : const Key pubkey = privkey.GetPubKey();
66 : :
67 [ + - ]: 768 : dummy_keys.push_back(pubkey);
68 [ + - ]: 768 : dummy_key_idx_map.emplace(pubkey, i);
69 [ + - + - ]: 768 : dummy_keys_map.insert({pubkey.GetID(), pubkey});
70 : 768 : XOnlyPubKey xonly_pubkey{pubkey};
71 [ + - ]: 768 : dummy_key_idx_map.emplace(xonly_pubkey, i);
72 [ + - ]: 768 : uint160 xonly_hash{Hash160(xonly_pubkey)};
73 [ + - ]: 768 : dummy_keys_map.emplace(xonly_hash, pubkey);
74 : :
75 [ + - ]: 768 : std::vector<unsigned char> sig, schnorr_sig(64);
76 [ + - ]: 768 : privkey.Sign(MESSAGE_HASH, sig);
77 [ + - ]: 768 : sig.push_back(1); // SIGHASH_ALL
78 [ + - + - ]: 1536 : dummy_sigs.insert({pubkey, {sig, i & 1}});
79 [ - + + - : 768 : assert(privkey.SignSchnorr(MESSAGE_HASH, schnorr_sig, nullptr, EMPTY_AUX));
- + ]
80 [ + - ]: 768 : schnorr_sig.push_back(1); // Maximally-sized signature has sighash byte
81 [ + - ]: 768 : schnorr_sigs.emplace(XOnlyPubKey{pubkey}, std::make_pair(std::move(schnorr_sig), i & 1));
82 : :
83 : 768 : std::vector<unsigned char> hash;
84 [ + - ]: 768 : hash.resize(32);
85 [ + - + - : 768 : CSHA256().Write(keydata, 32).Finalize(hash.data());
+ - ]
86 [ + - ]: 768 : sha256.push_back(hash);
87 [ + + + - : 768 : if (i & 1) sha256_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
+ - ]
88 [ + - + - : 768 : CHash256().Write(keydata).Finalize(hash);
- + + - ]
89 [ + - ]: 768 : hash256.push_back(hash);
90 [ + + + - : 768 : if (i & 1) hash256_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
+ - ]
91 [ + - ]: 768 : hash.resize(20);
92 [ + - + - : 768 : CRIPEMD160().Write(keydata, 32).Finalize(hash.data());
+ - ]
93 [ - + - + ]: 768 : assert(hash.size() == 20);
94 [ + - ]: 768 : ripemd160.push_back(hash);
95 [ + + + - : 768 : if (i & 1) ripemd160_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
+ - ]
96 [ + - + - : 768 : CHash160().Write(keydata).Finalize(hash);
- + + - ]
97 [ + - ]: 768 : hash160.push_back(hash);
98 [ + + + - : 768 : if (i & 1) hash160_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
+ - ]
99 : 768 : }
100 : 3 : }
101 : :
102 : : //! Get the (Schnorr or ECDSA, depending on context) signature for this pubkey.
103 : 239892 : const std::pair<std::vector<unsigned char>, bool>* GetSig(const MsCtx script_ctx, const Key& key) const {
104 [ + + ]: 239892 : if (!miniscript::IsTapscript(script_ctx)) {
105 : 137835 : const auto it = dummy_sigs.find(key);
106 [ + - ]: 137835 : if (it == dummy_sigs.end()) return nullptr;
107 : 137835 : return &it->second;
108 : : } else {
109 : 102057 : const auto it = schnorr_sigs.find(XOnlyPubKey{key});
110 [ + - ]: 102057 : if (it == schnorr_sigs.end()) return nullptr;
111 : 102057 : return &it->second;
112 : : }
113 : : }
114 : : } TEST_DATA;
115 : :
116 : : /**
117 : : * Context to parse a Miniscript node to and from Script or text representation.
118 : : * Uses an integer (an index in the dummy keys array from the test data) as keys in order
119 : : * to focus on fuzzing the Miniscript nodes' test representation, not the key representation.
120 : : */
121 : : struct ParserContext {
122 : : typedef CPubKey Key;
123 : :
124 : : const MsCtx script_ctx;
125 : :
126 : 9146 : constexpr ParserContext(MsCtx ctx) noexcept : script_ctx(ctx) {}
127 : :
128 : 1046386 : bool KeyCompare(const Key& a, const Key& b) const {
129 : 1046386 : return a < b;
[ + + + +
- - - - -
- - - + +
+ + + + ]
130 : : }
131 : :
132 : 162056 : std::optional<std::string> ToString(const Key& key, bool& has_priv_key) const
133 : : {
134 : 162056 : has_priv_key = false;
135 : 162056 : auto it = TEST_DATA.dummy_key_idx_map.find(key);
136 [ - + ]: 162056 : if (it == TEST_DATA.dummy_key_idx_map.end()) {
137 : 0 : return HexStr(key);
138 : : }
139 : 162056 : has_priv_key = true;
140 : 162056 : uint8_t idx = it->second;
141 : 162056 : return HexStr(std::span{&idx, 1});
142 : : }
143 : :
144 : 162414 : std::vector<unsigned char> ToPKBytes(const Key& key) const {
145 [ + + ]: 162414 : if (!miniscript::IsTapscript(script_ctx)) {
146 : 93773 : return {key.begin(), key.end()};
147 : : }
148 : 68641 : const XOnlyPubKey xonly_pubkey{key};
149 : 68641 : return {xonly_pubkey.begin(), xonly_pubkey.end()};
150 : : }
151 : :
152 : 16781 : std::vector<unsigned char> ToPKHBytes(const Key& key) const {
153 [ + + ]: 16781 : if (!miniscript::IsTapscript(script_ctx)) {
154 : 8908 : const auto h = Hash160(key);
155 : 8908 : return {h.begin(), h.end()};
156 : : }
157 : 7873 : const auto h = Hash160(XOnlyPubKey{key});
158 : 7873 : return {h.begin(), h.end()};
159 : : }
160 : :
161 : 178745 : std::optional<Key> FromString(std::span<const char>& in) const {
162 [ + + ]: 178745 : if (in.size() != 2) return {};
163 [ - + + - ]: 178742 : auto idx = ParseHex(std::string(in.begin(), in.end()));
164 [ - + + + ]: 178742 : if (idx.size() != 1) return {};
165 : 178722 : return TEST_DATA.dummy_keys[idx[0]];
166 : 178742 : }
167 : :
168 : : template<typename I>
169 : 71746 : std::optional<Key> FromPKBytes(I first, I last) const {
170 [ + + ]: 71746 : if (!miniscript::IsTapscript(script_ctx)) {
171 [ + - ]: 41603 : Key key{first, last};
172 [ + - ]: 41603 : if (key.IsValid()) return key;
173 : 0 : return {};
174 : : }
175 [ - + ]: 30143 : if (last - first != 32) return {};
176 : 30143 : XOnlyPubKey xonly_pubkey;
177 : 30143 : std::copy(first, last, xonly_pubkey.begin());
178 : 30143 : return xonly_pubkey.GetEvenCorrespondingCPubKey();
179 : : }
180 : :
181 : : template<typename I>
182 [ - + ]: 8218 : std::optional<Key> FromPKHBytes(I first, I last) const {
183 [ - + ]: 8218 : assert(last - first == 20);
184 : 8218 : CKeyID keyid;
185 : 8218 : std::copy(first, last, keyid.begin());
186 [ - + ]: 8218 : const auto it = TEST_DATA.dummy_keys_map.find(keyid);
187 [ - + ]: 8218 : if (it == TEST_DATA.dummy_keys_map.end()) return {};
188 : 8218 : return it->second;
189 : : }
190 : :
191 : 2215544 : MsCtx MsContext() const {
192 : 2215544 : return script_ctx;
[ + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + + + -
+ - ]
193 : : }
194 : : };
195 : :
196 : : //! Context that implements naive conversion from/to script only, for roundtrip testing.
197 : : struct ScriptParserContext {
198 : : const MsCtx script_ctx;
199 : :
200 : 867 : constexpr ScriptParserContext(MsCtx ctx) noexcept : script_ctx(ctx) {}
201 : :
202 : : //! For Script roundtrip we never need the key from a key hash.
203 [ + - ]: 48244 : struct Key {
204 : : bool is_hash;
205 : : std::vector<unsigned char> data;
206 : : };
207 : :
208 : 18368 : bool KeyCompare(const Key& a, const Key& b) const {
209 : 18368 : return a.data < b.data;
[ + + + +
- - - - -
- - - + +
+ + + + ]
210 : : }
211 : :
212 : 1267 : const std::vector<unsigned char>& ToPKBytes(const Key& key) const
213 : : {
214 [ - + ]: 1267 : assert(!key.is_hash);
215 : 1267 : return key.data;
216 : : }
217 : :
218 : 550 : std::vector<unsigned char> ToPKHBytes(const Key& key) const
219 : : {
220 [ + - ]: 550 : if (key.is_hash) return key.data;
221 : 0 : const auto h = Hash160(key.data);
222 : 0 : return {h.begin(), h.end()};
223 : : }
224 : :
225 : : template<typename I>
226 [ + - ]: 5137 : std::optional<Key> FromPKBytes(I first, I last) const
227 : : {
228 [ + - ]: 5137 : Key key;
229 : 5137 : key.data.assign(first, last);
230 : 5137 : key.is_hash = false;
231 : 5137 : return key;
232 : 5137 : }
233 : :
234 : : template<typename I>
235 [ + - ]: 4729 : std::optional<Key> FromPKHBytes(I first, I last) const
236 : : {
237 [ + - ]: 4729 : Key key;
238 : 4729 : key.data.assign(first, last);
239 : 4729 : key.is_hash = true;
240 : 4729 : return key;
241 : 4729 : }
242 : :
243 : 4415392 : MsCtx MsContext() const {
244 : 4415392 : return script_ctx;
[ + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - +
- ]
245 : : }
246 : : };
247 : :
248 : : //! Context to produce a satisfaction for a Miniscript node using the pre-computed data.
249 : : struct SatisfierContext : ParserContext {
250 : :
251 : 3918 : constexpr SatisfierContext(MsCtx ctx) noexcept : ParserContext(ctx) {}
252 : :
253 : : // Timelock challenges satisfaction. Make the value (deterministically) vary to explore different
254 : : // paths.
255 [ + + ]: 7750 : bool CheckAfter(uint32_t value) const { return value % 2; }
256 [ + + ]: 10448 : bool CheckOlder(uint32_t value) const { return value % 2; }
257 : :
258 : : // Signature challenges fulfilled with a dummy signature, if it was one of our dummy keys.
259 : 159928 : miniscript::Availability Sign(const CPubKey& key, std::vector<unsigned char>& sig) const {
260 : 159928 : bool sig_available{false};
261 [ + - ]: 159928 : if (auto res = TEST_DATA.GetSig(script_ctx, key)) {
262 : 159928 : std::tie(sig, sig_available) = *res;
263 : : }
264 [ + + ]: 159928 : return sig_available ? miniscript::Availability::YES : miniscript::Availability::NO;
265 : : }
266 : :
267 : : //! Lookup generalization for all the hash satisfactions below
268 : 25804 : miniscript::Availability LookupHash(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage,
269 : : const std::map<std::vector<unsigned char>, std::vector<unsigned char>>& map) const
270 : : {
271 : 25804 : const auto it = map.find(hash);
272 [ + + ]: 25804 : if (it == map.end()) return miniscript::Availability::NO;
273 : 16818 : preimage = it->second;
274 : 16818 : return miniscript::Availability::YES;
275 : : }
276 : 5762 : miniscript::Availability SatSHA256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
277 [ + - ]: 5762 : return LookupHash(hash, preimage, TEST_DATA.sha256_preimages);
278 : : }
279 : 6208 : miniscript::Availability SatRIPEMD160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
280 [ + - ]: 6208 : return LookupHash(hash, preimage, TEST_DATA.ripemd160_preimages);
281 : : }
282 : 6888 : miniscript::Availability SatHASH256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
283 [ + - ]: 6888 : return LookupHash(hash, preimage, TEST_DATA.hash256_preimages);
284 : : }
285 : 6946 : miniscript::Availability SatHASH160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
286 [ + - ]: 6946 : return LookupHash(hash, preimage, TEST_DATA.hash160_preimages);
287 : : }
288 : : };
289 : :
290 : : //! Context to check a satisfaction against the pre-computed data.
291 : : const struct CheckerContext: BaseSignatureChecker {
292 : : // Signature checker methods. Checks the right dummy signature is used.
293 : 25803 : bool CheckECDSASignature(const std::vector<unsigned char>& sig, const std::vector<unsigned char>& vchPubKey,
294 : : const CScript& scriptCode, SigVersion sigversion) const override
295 : : {
296 [ - + ]: 25803 : const CPubKey key{vchPubKey};
297 : 25803 : const auto it = TEST_DATA.dummy_sigs.find(key);
298 [ + - ]: 25803 : if (it == TEST_DATA.dummy_sigs.end()) return false;
299 : 25803 : return it->second.first == sig;
300 : : }
301 : 9346 : bool CheckSchnorrSignature(std::span<const unsigned char> sig, std::span<const unsigned char> pubkey, SigVersion,
302 : : ScriptExecutionData&, ScriptError*) const override {
303 : 9346 : XOnlyPubKey pk{pubkey};
304 : 9346 : auto it = TEST_DATA.schnorr_sigs.find(pk);
305 [ + - ]: 9346 : if (it == TEST_DATA.schnorr_sigs.end()) return false;
306 : 9346 : return std::ranges::equal(it->second.first, sig);
307 : : }
308 : 1317 : bool CheckLockTime(const CScriptNum& nLockTime) const override { return nLockTime.GetInt64() & 1; }
309 : 2285 : bool CheckSequence(const CScriptNum& nSequence) const override { return nSequence.GetInt64() & 1; }
310 : : } CHECKER_CTX;
311 : :
312 : : //! Context to check for duplicates when instancing a Node.
313 : : const struct KeyComparator {
314 : 262297 : bool KeyCompare(const CPubKey& a, const CPubKey& b) const {
315 : 262297 : return a < b;
[ + + + +
- - - - -
- - - + +
+ + + + ]
316 : : }
317 : : } KEY_COMP;
318 : :
319 : : // A dummy scriptsig to pass to VerifyScript (we always use Segwit v0).
320 : : const CScript DUMMY_SCRIPTSIG;
321 : :
322 : : /** Information about a yet to be constructed Miniscript node. */
323 : : struct NodeInfo {
324 : : //! The type of this node
325 : : Fragment fragment;
326 : : //! The timelock value for older() and after(), the threshold value for multi() and thresh()
327 : : uint32_t k;
328 : : //! Keys for this node, if it has some
329 : : std::vector<CPubKey> keys;
330 : : //! The hash value for this node, if it has one
331 : : std::vector<unsigned char> hash;
332 : : //! The type requirements for the children of this node.
333 : : std::vector<Type> subtypes;
334 : :
335 : 34832 : NodeInfo(Fragment frag): fragment(frag), k(0) {}
336 : 24485 : NodeInfo(Fragment frag, CPubKey key): fragment(frag), k(0), keys({key}) {}
337 : 6755 : NodeInfo(Fragment frag, uint32_t _k): fragment(frag), k(_k) {}
338 : 14380 : NodeInfo(Fragment frag, std::vector<unsigned char> h): fragment(frag), k(0), hash(std::move(h)) {}
339 : 110290 : NodeInfo(std::vector<Type> subt, Fragment frag): fragment(frag), k(0), subtypes(std::move(subt)) {}
340 : 11090 : NodeInfo(std::vector<Type> subt, Fragment frag, uint32_t _k): fragment(frag), k(_k), subtypes(std::move(subt)) {}
341 : 9741 : NodeInfo(Fragment frag, uint32_t _k, std::vector<CPubKey> _keys): fragment(frag), k(_k), keys(std::move(_keys)) {}
342 : : };
343 : :
344 : : /** Pick an index in a collection from a single byte in the fuzzer's output. */
345 : : template<typename T, typename A>
346 : 106767 : T ConsumeIndex(FuzzedDataProvider& provider, A& col) {
347 : 106767 : const uint8_t i = provider.ConsumeIntegral<uint8_t>();
348 : 106767 : return col[i];
349 : : }
350 : :
351 : 98444 : CPubKey ConsumePubKey(FuzzedDataProvider& provider) {
352 : 98444 : return ConsumeIndex<CPubKey>(provider, TEST_DATA.dummy_keys);
353 : : }
354 : :
355 : 1821 : std::vector<unsigned char> ConsumeSha256(FuzzedDataProvider& provider) {
356 : 1821 : return ConsumeIndex<std::vector<unsigned char>>(provider, TEST_DATA.sha256);
357 : : }
358 : :
359 : 2330 : std::vector<unsigned char> ConsumeHash256(FuzzedDataProvider& provider) {
360 : 2330 : return ConsumeIndex<std::vector<unsigned char>>(provider, TEST_DATA.hash256);
361 : : }
362 : :
363 : 1965 : std::vector<unsigned char> ConsumeRipemd160(FuzzedDataProvider& provider) {
364 : 1965 : return ConsumeIndex<std::vector<unsigned char>>(provider, TEST_DATA.ripemd160);
365 : : }
366 : :
367 : 2207 : std::vector<unsigned char> ConsumeHash160(FuzzedDataProvider& provider) {
368 : 2207 : return ConsumeIndex<std::vector<unsigned char>>(provider, TEST_DATA.hash160);
369 : : }
370 : :
371 : 6780 : std::optional<uint32_t> ConsumeTimeLock(FuzzedDataProvider& provider) {
372 : 6780 : const uint32_t k = provider.ConsumeIntegral<uint32_t>();
373 [ + + ]: 6780 : if (k == 0 || k >= 0x80000000) return {};
374 : 6755 : return k;
375 : : }
376 : :
377 : : /**
378 : : * Consume a Miniscript node from the fuzzer's output.
379 : : *
380 : : * This version is intended to have a fixed, stable, encoding for Miniscript nodes:
381 : : * - The first byte sets the type of the fragment. 0, 1 and all non-leaf fragments but thresh() are a
382 : : * single byte.
383 : : * - For the other leaf fragments, the following bytes depend on their type.
384 : : * - For older() and after(), the next 4 bytes define the timelock value.
385 : : * - For pk_k(), pk_h(), and all hashes, the next byte defines the index of the value in the test data.
386 : : * - For multi(), the next 2 bytes define respectively the threshold and the number of keys. Then as many
387 : : * bytes as the number of keys define the index of each key in the test data.
388 : : * - For multi_a(), same as for multi() but the threshold and the keys count are encoded on two bytes.
389 : : * - For thresh(), the next byte defines the threshold value and the following one the number of subs.
390 : : */
391 : 183181 : std::optional<NodeInfo> ConsumeNodeStable(MsCtx script_ctx, FuzzedDataProvider& provider, Type type_needed) {
392 [ + + + + ]: 183181 : bool allow_B = (type_needed == ""_mst) || (type_needed << "B"_mst);
393 [ + + + + ]: 183181 : bool allow_K = (type_needed == ""_mst) || (type_needed << "K"_mst);
394 [ + + + + ]: 183181 : bool allow_V = (type_needed == ""_mst) || (type_needed << "V"_mst);
395 [ + + + + ]: 183181 : bool allow_W = (type_needed == ""_mst) || (type_needed << "W"_mst);
396 : :
397 : 183181 : switch (provider.ConsumeIntegral<uint8_t>()) {
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
398 : 25622 : case 0:
399 [ + + ]: 25622 : if (!allow_B) return {};
400 : 25560 : return {{Fragment::JUST_0}};
401 : 9279 : case 1:
402 [ + + ]: 9279 : if (!allow_B) return {};
403 : 9272 : return {{Fragment::JUST_1}};
404 : 6721 : case 2:
405 [ + + ]: 6721 : if (!allow_K) return {};
406 : 6713 : return {{Fragment::PK_K, ConsumePubKey(provider)}};
407 : 4939 : case 3:
408 [ + + ]: 4939 : if (!allow_K) return {};
409 : 4935 : return {{Fragment::PK_H, ConsumePubKey(provider)}};
410 : 3797 : case 4: {
411 [ + + ]: 3797 : if (!allow_B) return {};
412 : 3791 : const auto k = ConsumeTimeLock(provider);
413 [ + + ]: 3791 : if (!k) return {};
414 : 3779 : return {{Fragment::OLDER, *k}};
415 : : }
416 : 2992 : case 5: {
417 [ + + ]: 2992 : if (!allow_B) return {};
418 : 2989 : const auto k = ConsumeTimeLock(provider);
419 [ + + ]: 2989 : if (!k) return {};
420 : 2976 : return {{Fragment::AFTER, *k}};
421 : : }
422 : 1826 : case 6:
423 [ + + ]: 1826 : if (!allow_B) return {};
424 : 1821 : return {{Fragment::SHA256, ConsumeSha256(provider)}};
425 : 2335 : case 7:
426 [ + + ]: 2335 : if (!allow_B) return {};
427 : 2330 : return {{Fragment::HASH256, ConsumeHash256(provider)}};
428 : 1970 : case 8:
429 [ + + ]: 1970 : if (!allow_B) return {};
430 : 1965 : return {{Fragment::RIPEMD160, ConsumeRipemd160(provider)}};
431 : 2210 : case 9:
432 [ + + ]: 2210 : if (!allow_B) return {};
433 : 2207 : return {{Fragment::HASH160, ConsumeHash160(provider)}};
434 : 4579 : case 10: {
435 [ + + + + ]: 4579 : if (!allow_B || IsTapscript(script_ctx)) return {};
436 : 3911 : const auto k = provider.ConsumeIntegral<uint8_t>();
437 : 3911 : const auto n_keys = provider.ConsumeIntegral<uint8_t>();
438 [ + + + + ]: 3911 : if (n_keys > 20 || k == 0 || k > n_keys) return {};
439 : 3903 : std::vector<CPubKey> keys{n_keys};
440 [ + + ]: 21290 : for (auto& key: keys) key = ConsumePubKey(provider);
441 : 3903 : return {{Fragment::MULTI, k, std::move(keys)}};
442 : 3903 : }
443 : 7990 : case 11:
444 [ + + + + ]: 7990 : if (!(allow_B || allow_K || allow_V)) return {};
445 : 7987 : return {{{"B"_mst, type_needed, type_needed}, Fragment::ANDOR}};
446 : 21587 : case 12:
447 [ + + + + ]: 21587 : if (!(allow_B || allow_K || allow_V)) return {};
448 : 21584 : return {{{"V"_mst, type_needed}, Fragment::AND_V}};
449 : 4824 : case 13:
450 [ + + ]: 4824 : if (!allow_B) return {};
451 : 4819 : return {{{"B"_mst, "W"_mst}, Fragment::AND_B}};
452 : 3049 : case 15:
453 [ + + ]: 3049 : if (!allow_B) return {};
454 : 3046 : return {{{"B"_mst, "W"_mst}, Fragment::OR_B}};
455 : 2432 : case 16:
456 [ + + ]: 2432 : if (!allow_V) return {};
457 : 2426 : return {{{"B"_mst, "V"_mst}, Fragment::OR_C}};
458 : 5937 : case 17:
459 [ + + ]: 5937 : if (!allow_B) return {};
460 : 5932 : return {{{"B"_mst, "B"_mst}, Fragment::OR_D}};
461 : 12376 : case 18:
462 [ + + + + ]: 12376 : if (!(allow_B || allow_K || allow_V)) return {};
463 : 12371 : return {{{type_needed, type_needed}, Fragment::OR_I}};
464 : 5406 : case 19: {
465 [ + + ]: 5406 : if (!allow_B) return {};
466 : 5400 : auto k = provider.ConsumeIntegral<uint8_t>();
467 : 5400 : auto n_subs = provider.ConsumeIntegral<uint8_t>();
468 [ + + ]: 5400 : if (k == 0 || k > n_subs) return {};
469 : 5376 : std::vector<Type> subtypes;
470 [ + - ]: 5376 : subtypes.reserve(n_subs);
471 [ + - ]: 5376 : subtypes.emplace_back("B"_mst);
472 [ + - + + ]: 20301 : for (size_t i = 1; i < n_subs; ++i) subtypes.emplace_back("W"_mst);
473 : 5376 : return {{std::move(subtypes), Fragment::THRESH, k}};
474 : 5376 : }
475 : 11156 : case 20:
476 [ + + ]: 11156 : if (!allow_W) return {};
477 : 11148 : return {{{"B"_mst}, Fragment::WRAP_A}};
478 : 1366 : case 21:
479 [ + + ]: 1366 : if (!allow_W) return {};
480 : 1361 : return {{{"B"_mst}, Fragment::WRAP_S}};
481 : 9782 : case 22:
482 [ + + ]: 9782 : if (!allow_B) return {};
483 : 9777 : return {{{"K"_mst}, Fragment::WRAP_C}};
484 : 976 : case 23:
485 [ + + ]: 976 : if (!allow_B) return {};
486 : 973 : return {{{"V"_mst}, Fragment::WRAP_D}};
487 : 22215 : case 24:
488 [ + + ]: 22215 : if (!allow_V) return {};
489 : 22208 : return {{{"B"_mst}, Fragment::WRAP_V}};
490 : 1860 : case 25:
491 [ + + ]: 1860 : if (!allow_B) return {};
492 : 1855 : return {{{"B"_mst}, Fragment::WRAP_J}};
493 : 4809 : case 26:
494 [ + + ]: 4809 : if (!allow_B) return {};
495 : 4803 : return {{{"B"_mst}, Fragment::WRAP_N}};
496 : 1136 : case 27: {
497 [ + + + + ]: 1136 : if (!allow_B || !IsTapscript(script_ctx)) return {};
498 : 899 : const auto k = provider.ConsumeIntegral<uint16_t>();
499 : 899 : const auto n_keys = provider.ConsumeIntegral<uint16_t>();
500 [ + + + + ]: 899 : if (n_keys > 999 || k == 0 || k > n_keys) return {};
501 : 890 : std::vector<CPubKey> keys{n_keys};
502 [ + + ]: 17310 : for (auto& key: keys) key = ConsumePubKey(provider);
503 : 890 : return {{Fragment::MULTI_A, k, std::move(keys)}};
504 : 890 : }
505 : 10 : default:
506 : 10 : break;
507 : : }
508 : 10 : return {};
509 : : }
510 : :
511 : : /* This structure contains a table which for each "target" Type a list of recipes
512 : : * to construct it, automatically inferred from the behavior of ComputeType.
513 : : * Note that the Types here are not the final types of the constructed Nodes, but
514 : : * just the subset that are required. For example, a recipe for the "Bo" type
515 : : * might construct a "Bondu" sha256() NodeInfo, but cannot construct a "Bz" older().
516 : : * Each recipe is a Fragment together with a list of required types for its subnodes.
517 : : */
518 : : struct SmartInfo
519 : : {
520 : : using recipe = std::pair<Fragment, std::vector<Type>>;
521 : : std::map<Type, std::vector<recipe>> wsh_table, tap_table;
522 : :
523 : 1 : void Init()
524 : : {
525 : 1 : Init(wsh_table, MsCtx::P2WSH);
526 : 1 : Init(tap_table, MsCtx::TAPSCRIPT);
527 : 1 : }
528 : :
529 : 2 : void Init(std::map<Type, std::vector<recipe>>& table, MsCtx script_ctx)
530 : : {
531 : : /* Construct a set of interesting type requirements to reason with (sections of BKVWzondu). */
532 : 2 : std::vector<Type> types;
533 [ + + ]: 10 : for (int base = 0; base < 4; ++base) { /* select from B,K,V,W */
534 [ + + + + : 8 : Type type_base = base == 0 ? "B"_mst : base == 1 ? "K"_mst : base == 2 ? "V"_mst : "W"_mst;
+ + ]
535 [ + + ]: 32 : for (int zo = 0; zo < 3; ++zo) { /* select from z,o,(none) */
536 [ + + + + ]: 24 : Type type_zo = zo == 0 ? "z"_mst : zo == 1 ? "o"_mst : ""_mst;
537 [ + + ]: 72 : for (int n = 0; n < 2; ++n) { /* select from (none),n */
538 [ + + ]: 48 : if (zo == 0 && n == 1) continue; /* z conflicts with n */
539 [ + + ]: 40 : if (base == 3 && n == 1) continue; /* W conflicts with n */
540 [ + + ]: 36 : Type type_n = n == 0 ? ""_mst : "n"_mst;
541 [ + + ]: 108 : for (int d = 0; d < 2; ++d) { /* select from (none),d */
542 [ + + ]: 72 : if (base == 2 && d == 1) continue; /* V conflicts with d */
543 [ + + ]: 62 : Type type_d = d == 0 ? ""_mst : "d"_mst;
544 [ + + ]: 186 : for (int u = 0; u < 2; ++u) { /* select from (none),u */
545 [ + + ]: 124 : if (base == 2 && u == 1) continue; /* V conflicts with u */
546 [ + + ]: 114 : Type type_u = u == 0 ? ""_mst : "u"_mst;
547 [ + - ]: 114 : Type type = type_base | type_zo | type_n | type_d | type_u;
548 [ + - ]: 114 : types.push_back(type);
549 : : }
550 : : }
551 : : }
552 : : }
553 : : }
554 : :
555 : : /* We define a recipe a to be a super-recipe of recipe b if they use the same
556 : : * fragment, the same number of subexpressions, and each of a's subexpression
557 : : * types is a supertype of the corresponding subexpression type of b.
558 : : * Within the set of recipes for the construction of a given type requirement,
559 : : * no recipe should be a super-recipe of another (as the super-recipe is
560 : : * applicable in every place the sub-recipe is, the sub-recipe is redundant). */
561 : 260828 : auto is_super_of = [](const recipe& a, const recipe& b) {
562 [ + + ]: 260826 : if (a.first != b.first) return false;
563 [ - + - + : 26260 : if (a.second.size() != b.second.size()) return false;
+ + ]
564 [ + + ]: 91420 : for (size_t i = 0; i < a.second.size(); ++i) {
565 [ + + ]: 66654 : if (!(b.second[i] << a.second[i])) return false;
566 : : }
567 : : return true;
568 : : };
569 : :
570 : : /* Sort the type requirements. Subtypes will always sort later (e.g. Bondu will
571 : : * sort after Bo or Bu). As we'll be constructing recipes using these types, in
572 : : * order, in what follows, we'll construct super-recipes before sub-recipes.
573 : : * That means we never need to go back and delete a sub-recipe because a
574 : : * super-recipe got added. */
575 : 2 : std::sort(types.begin(), types.end());
576 : :
577 : : // Iterate over all possible fragments.
578 [ + + ]: 56 : for (int fragidx = 0; fragidx <= int(Fragment::MULTI_A); ++fragidx) {
579 : 54 : int sub_count = 0; //!< The minimum number of child nodes this recipe has.
580 : 54 : int sub_range = 1; //!< The maximum number of child nodes for this recipe is sub_count+sub_range-1.
581 : 54 : size_t data_size = 0;
582 : 54 : size_t n_keys = 0;
583 : 54 : uint32_t k = 0;
584 : 54 : Fragment frag{fragidx};
585 : :
586 : : // Only produce recipes valid in the given context.
587 [ + + ]: 81 : if ((!miniscript::IsTapscript(script_ctx) && frag == Fragment::MULTI_A)
588 [ + + + + : 80 : || (miniscript::IsTapscript(script_ctx) && frag == Fragment::MULTI)) {
+ + ]
589 : 2 : continue;
590 : : }
591 : :
592 : : // Based on the fragment, determine #subs/data/k/keys to pass to ComputeType. */
593 [ + + + + : 52 : switch (frag) {
+ + + + +
+ ]
594 : 4 : case Fragment::PK_K:
595 : 4 : case Fragment::PK_H:
596 : 4 : n_keys = 1;
597 : 4 : break;
598 : 2 : case Fragment::MULTI:
599 : 2 : case Fragment::MULTI_A:
600 : 2 : n_keys = 1;
601 : 2 : k = 1;
602 : 2 : break;
603 : 4 : case Fragment::OLDER:
604 : 4 : case Fragment::AFTER:
605 : 4 : k = 1;
606 : 4 : break;
607 : 4 : case Fragment::SHA256:
608 : 4 : case Fragment::HASH256:
609 : 4 : data_size = 32;
610 : 4 : break;
611 : 4 : case Fragment::RIPEMD160:
612 : 4 : case Fragment::HASH160:
613 : 4 : data_size = 20;
614 : 4 : break;
615 : : case Fragment::JUST_0:
616 : : case Fragment::JUST_1:
617 : : break;
618 : 14 : case Fragment::WRAP_A:
619 : 14 : case Fragment::WRAP_S:
620 : 14 : case Fragment::WRAP_C:
621 : 14 : case Fragment::WRAP_D:
622 : 14 : case Fragment::WRAP_V:
623 : 14 : case Fragment::WRAP_J:
624 : 14 : case Fragment::WRAP_N:
625 : 14 : sub_count = 1;
626 : 14 : break;
627 : 12 : case Fragment::AND_V:
628 : 12 : case Fragment::AND_B:
629 : 12 : case Fragment::OR_B:
630 : 12 : case Fragment::OR_C:
631 : 12 : case Fragment::OR_D:
632 : 12 : case Fragment::OR_I:
633 : 12 : sub_count = 2;
634 : 12 : break;
635 : 2 : case Fragment::ANDOR:
636 : 2 : sub_count = 3;
637 : 2 : break;
638 : 2 : case Fragment::THRESH:
639 : : // Thresh logic is executed for 1 and 2 arguments. Larger numbers use ad-hoc code to extend.
640 : 2 : sub_count = 1;
641 : 2 : sub_range = 2;
642 : 2 : k = 1;
643 : 2 : break;
644 : : }
645 : :
646 : : // Iterate over the number of subnodes (sub_count...sub_count+sub_range-1).
647 : 52 : std::vector<Type> subt;
648 [ + + ]: 106 : for (int subs = sub_count; subs < sub_count + sub_range; ++subs) {
649 : : // Iterate over the possible subnode types (at most 3).
650 [ + + ]: 1878 : for (Type x : types) {
651 [ + + ]: 53830 : for (Type y : types) {
652 [ + + ]: 2886502 : for (Type z : types) {
653 : : // Compute the resulting type of a node with the selected fragment / subnode types.
654 [ + + ]: 2836790 : subt.clear();
655 [ + + + - ]: 2836790 : if (subs > 0) subt.push_back(x);
656 [ + + + - ]: 2836768 : if (subs > 1) subt.push_back(y);
657 [ + + + - ]: 2796208 : if (subs > 2) subt.push_back(z);
658 [ + - ]: 2836790 : Type res = miniscript::internal::ComputeType(frag, x, y, z, subt, k, data_size, subs, n_keys, script_ctx);
659 : : // Continue if the result is not a valid node.
660 [ + + ]: 2836790 : if ((res << "K"_mst) + (res << "V"_mst) + (res << "B"_mst) + (res << "W"_mst) != 1) continue;
661 : :
662 [ + - ]: 11456 : recipe entry{frag, subt};
663 [ + + ]: 260826 : auto super_of_entry = [&](const recipe& rec) { return is_super_of(rec, entry); };
664 : : // Iterate over all supertypes of res (because if e.g. our selected fragment/subnodes result
665 : : // in a Bondu, they can form a recipe that is also applicable for constructing a B, Bou, Bdu, ...).
666 [ + + ]: 664448 : for (Type s : types) {
667 [ + + ]: 652992 : if ((res & "BKVWzondu"_mst) << s) {
668 [ + - ]: 25510 : auto& recipes = table[s];
669 : : // If we don't already have a super-recipe to the new one, add it.
670 [ + + ]: 25510 : if (!std::any_of(recipes.begin(), recipes.end(), super_of_entry)) {
671 [ + - ]: 744 : recipes.push_back(entry);
672 : : }
673 : : }
674 : : }
675 : :
676 [ + + ]: 11456 : if (subs <= 2) break;
677 : 11456 : }
678 [ + + ]: 52918 : if (subs <= 1) break;
679 : : }
680 [ + + ]: 1846 : if (subs <= 0) break;
681 : : }
682 : : }
683 : : }
684 : :
685 : : /* Find which types are useful. The fuzzer logic only cares about constructing
686 : : * B,V,K,W nodes, so any type that isn't needed in any recipe (directly or
687 : : * indirectly) for the construction of those is uninteresting. */
688 [ + - ]: 4 : std::set<Type> useful_types{"B"_mst, "V"_mst, "K"_mst, "W"_mst};
689 : : // Find the transitive closure by adding types until the set of types does not change.
690 : 4 : while (true) {
691 : 4 : size_t set_size = useful_types.size();
692 [ + + ]: 200 : for (const auto& [type, recipes] : table) {
693 [ + + ]: 196 : if (useful_types.contains(type)) {
694 [ + + ]: 1129 : for (const auto& [_, subtypes] : recipes) {
695 [ + - + + ]: 2379 : for (auto subtype : subtypes) useful_types.insert(subtype);
696 : : }
697 : : }
698 : : }
699 [ + + ]: 4 : if (useful_types.size() == set_size) break;
700 : : }
701 : : // Remove all rules that construct uninteresting types.
702 : 100 : std::erase_if(table, [&](const auto& entry) { return !useful_types.contains(entry.first); });
703 : :
704 : : /* Find which types are constructible. A type is constructible if there is a leaf
705 : : * node recipe for constructing it, or a recipe whose subnodes are all constructible.
706 : : * Types can be non-constructible because they have no recipes to begin with,
707 : : * because they can only be constructed using recipes that involve otherwise
708 : : * non-constructible types, or because they require infinite recursion. */
709 : 4 : std::set<Type> constructible_types{};
710 : 812 : auto known_constructible = [&](Type type) { return constructible_types.contains(type); };
711 : : // Find the transitive closure by adding types until the set of types does not change.
712 : 4 : while (true) {
713 : 4 : size_t set_size = constructible_types.size();
714 : : // Iterate over all types we have recipes for.
715 [ + + ]: 132 : for (const auto& [type, recipes] : table) {
716 [ + + ]: 128 : if (!known_constructible(type)) {
717 : : // For not (yet known to be) constructible types, iterate over their recipes.
718 [ + + ]: 80 : for (const auto& [_, subt] : recipes) {
719 : : // If any recipe involves only (already known to be) constructible types,
720 : : // add the recipe's type to the set.
721 [ + + ]: 72 : if (std::all_of(subt.begin(), subt.end(), known_constructible)) {
722 [ + - ]: 60 : constructible_types.insert(type);
723 : : break;
724 : : }
725 : : }
726 : : }
727 : : }
728 [ + + ]: 4 : if (constructible_types.size() == set_size) break;
729 : : }
730 [ + + ]: 66 : for (auto type_it = table.begin(); type_it != table.end();) {
731 : : // Remove all recipes which involve non-constructible types.
732 : 64 : std::erase_if(type_it->second, [&](const recipe& rec) {
733 : 594 : return !std::all_of(rec.second.begin(), rec.second.end(), known_constructible);
734 : : });
735 : : // Delete types entirely which have no recipes left.
736 [ + + ]: 64 : if (type_it->second.empty()) {
737 : 4 : type_it = table.erase(type_it);
738 : : } else {
739 : 60 : ++type_it;
740 : : }
741 : : }
742 : :
743 [ + + ]: 62 : for (auto& [type, recipes] : table) {
744 : : // Sort recipes for determinism, and place those using fewer subnodes first.
745 : : // This avoids runaway expansion (when reaching the end of the fuzz input,
746 : : // all zeroes are read, resulting in the first available recipe being picked).
747 : 60 : std::sort(recipes.begin(), recipes.end(),
748 : 1271 : [](const recipe& a, const recipe& b) {
749 [ - + - + : 1271 : if (a.second.size() < b.second.size()) return true;
+ + ]
750 [ + + ]: 988 : if (a.second.size() > b.second.size()) return false;
751 : 536 : return a < b;
752 : : }
753 : : );
754 : : }
755 : 2 : }
756 : : } SMARTINFO;
757 : :
758 : : /**
759 : : * Consume a Miniscript node from the fuzzer's output.
760 : : *
761 : : * This is similar to ConsumeNodeStable, but uses a precomputed table with permitted
762 : : * fragments/subnode type for each required type. It is intended to more quickly explore
763 : : * interesting miniscripts, at the cost of higher implementation complexity (which could
764 : : * cause it miss things if incorrect), and with less regard for stability of the seeds
765 : : * (as improvements to the tables or changes to the typing rules could invalidate
766 : : * everything).
767 : : */
768 : 156584 : std::optional<NodeInfo> ConsumeNodeSmart(MsCtx script_ctx, FuzzedDataProvider& provider, Type type_needed) {
769 : : /** Table entry for the requested type. */
770 [ + + ]: 156584 : const auto& table{IsTapscript(script_ctx) ? SMARTINFO.tap_table : SMARTINFO.wsh_table};
771 : 156584 : auto recipes_it = table.find(type_needed);
772 [ - + ]: 156584 : assert(recipes_it != table.end());
773 : : /** Pick one recipe from the available ones for that type. */
774 : 156584 : const auto& [frag, subt] = PickValue(provider, recipes_it->second);
[ + + + +
+ + + + +
+ - ]
775 : :
776 : : // Based on the fragment the recipe uses, fill in other data (k, keys, data).
777 : 156584 : switch (frag) {
[ + + + +
+ + + + +
+ - ]
778 : 12837 : case Fragment::PK_K:
779 : 12837 : case Fragment::PK_H:
780 : 12837 : return {{frag, ConsumePubKey(provider)}};
781 : 3927 : case Fragment::MULTI: {
782 : 3927 : const auto n_keys = provider.ConsumeIntegralInRange<uint8_t>(1, 20);
783 : 3927 : const auto k = provider.ConsumeIntegralInRange<uint8_t>(1, n_keys);
784 : 3927 : std::vector<CPubKey> keys{n_keys};
785 [ + + ]: 22837 : for (auto& key: keys) key = ConsumePubKey(provider);
786 : 3927 : return {{frag, k, std::move(keys)}};
787 : 3927 : }
788 : 1021 : case Fragment::MULTI_A: {
789 : 1021 : const auto n_keys = provider.ConsumeIntegralInRange<uint16_t>(1, 999);
790 : 1021 : const auto k = provider.ConsumeIntegralInRange<uint16_t>(1, n_keys);
791 : 1021 : std::vector<CPubKey> keys{n_keys};
792 [ + + ]: 22263 : for (auto& key: keys) key = ConsumePubKey(provider);
793 : 1021 : return {{frag, k, std::move(keys)}};
794 : 1021 : }
795 : 3328 : case Fragment::OLDER:
796 : 3328 : case Fragment::AFTER:
797 : 3328 : return {{frag, provider.ConsumeIntegralInRange<uint32_t>(1, 0x7FFFFFF)}};
798 : 1425 : case Fragment::SHA256:
799 : 1425 : return {{frag, PickValue(provider, TEST_DATA.sha256)}};
800 : 1527 : case Fragment::HASH256:
801 : 1527 : return {{frag, PickValue(provider, TEST_DATA.hash256)}};
802 : 1499 : case Fragment::RIPEMD160:
803 : 1499 : return {{frag, PickValue(provider, TEST_DATA.ripemd160)}};
804 : 1606 : case Fragment::HASH160:
805 : 1606 : return {{frag, PickValue(provider, TEST_DATA.hash160)}};
806 : 123700 : case Fragment::JUST_0:
807 : 123700 : case Fragment::JUST_1:
808 : 123700 : case Fragment::WRAP_A:
809 : 123700 : case Fragment::WRAP_S:
810 : 123700 : case Fragment::WRAP_C:
811 : 123700 : case Fragment::WRAP_D:
812 : 123700 : case Fragment::WRAP_V:
813 : 123700 : case Fragment::WRAP_J:
814 : 123700 : case Fragment::WRAP_N:
815 : 123700 : case Fragment::AND_V:
816 : 123700 : case Fragment::AND_B:
817 : 123700 : case Fragment::OR_B:
818 : 123700 : case Fragment::OR_C:
819 : 123700 : case Fragment::OR_D:
820 : 123700 : case Fragment::OR_I:
821 : 123700 : case Fragment::ANDOR:
822 : 123700 : return {{subt, frag}};
823 : 5714 : case Fragment::THRESH: {
824 : 5714 : uint32_t children;
825 [ - + + + ]: 5714 : if (subt.size() < 2) {
826 : 4793 : children = subt.size();
827 : : } else {
828 : : // If we hit a thresh with 2 subnodes, artificially extend it to any number
829 : : // (2 or larger) by replicating the type of the last subnode.
830 : 921 : children = provider.ConsumeIntegralInRange<uint32_t>(2, MAX_OPS_PER_SCRIPT / 2);
831 : : }
832 : 5714 : auto k = provider.ConsumeIntegralInRange<uint32_t>(1, children);
833 : 5714 : std::vector<Type> subs = subt;
834 [ + - - + : 26492 : while (subs.size() < children) subs.push_back(subs.back());
+ + ]
835 : 5714 : return {{std::move(subs), frag, k}};
836 : 5714 : }
837 : : }
838 : :
839 : 0 : assert(false);
840 : : }
841 : :
842 : : /**
843 : : * Generate a Miniscript node based on the fuzzer's input.
844 : : *
845 : : * - ConsumeNode is a function object taking a Type, and returning an std::optional<NodeInfo>.
846 : : * - root_type is the required type properties of the constructed Node.
847 : : * - strict_valid sets whether ConsumeNode is expected to guarantee a NodeInfo that results in
848 : : * a Node whose Type() matches the type fed to ConsumeNode.
849 : : */
850 : : template <typename F>
851 : 5761 : std::optional<Node> GenNode(MsCtx script_ctx, F ConsumeNode, Type root_type, bool strict_valid = false)
852 : : {
853 : : /** A stack of miniscript Nodes being built up. */
854 : 5761 : std::vector<Node> stack;
855 : : /** The queue of instructions. */
856 [ + - + + : 17283 : std::vector<std::pair<Type, std::optional<NodeInfo>>> todo{{root_type, {}}};
- - ]
857 : : /** Predict the number of (static) script ops. */
858 : 5761 : uint32_t ops{0};
859 : : /** Predict the total script size (every unexplored subnode is counted as one, as every leaf is
860 : : * at least one script byte). */
861 : 5761 : uint32_t scriptsize{1};
862 : :
863 [ + + ]: 664546 : while (!todo.empty()) {
864 : : // The expected type we have to construct.
865 : 660283 : auto type_needed = todo.back().first;
866 [ + + ]: 660283 : if (!todo.back().second) {
867 : : // Fragment/children have not been decided yet. Decide them.
868 [ + + ]: 339765 : auto node_info = ConsumeNode(type_needed);
869 [ + + ]: 339765 : if (!node_info) return {};
870 : : // Update predicted resource limits. Since every leaf Miniscript node is at least one
871 : : // byte long, we move one byte from each child to their parent. A similar technique is
872 : : // used in the miniscript::internal::Parse function to prevent runaway string parsing.
873 [ - + - + : 338601 : scriptsize += miniscript::internal::ComputeScriptLen(node_info->fragment, ""_mst, node_info->subtypes.size(), node_info->k, node_info->subtypes.size(),
+ - ]
874 [ - + ]: 338601 : node_info->keys.size(), script_ctx) - 1;
875 [ + + ]: 338601 : if (scriptsize > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
876 : 338568 : switch (node_info->fragment) {
[ + + + +
+ + + + +
+ + + + +
+ + + + ]
877 : : case Fragment::JUST_0:
878 : : case Fragment::JUST_1:
879 : : break;
880 : : case Fragment::PK_K:
881 : : break;
882 : 8854 : case Fragment::PK_H:
883 : 8854 : ops += 3;
884 : 8854 : break;
885 : 10083 : case Fragment::OLDER:
886 : : case Fragment::AFTER:
887 : 10083 : ops += 1;
888 : 10083 : break;
889 : 14380 : case Fragment::RIPEMD160:
890 : : case Fragment::SHA256:
891 : : case Fragment::HASH160:
892 : : case Fragment::HASH256:
893 : 14380 : ops += 4;
894 : 14380 : break;
895 : 14499 : case Fragment::ANDOR:
896 : 14499 : ops += 3;
897 : 14499 : break;
898 : : case Fragment::AND_V:
899 : : break;
900 : 15184 : case Fragment::AND_B:
901 : : case Fragment::OR_B:
902 : 15184 : ops += 1;
903 : 15184 : break;
904 : 4595 : case Fragment::OR_C:
905 : 4595 : ops += 2;
906 : 4595 : break;
907 : 9257 : case Fragment::OR_D:
908 : 9257 : ops += 3;
909 : 9257 : break;
910 : 20242 : case Fragment::OR_I:
911 : 20242 : ops += 3;
912 : 20242 : break;
913 [ - + ]: 11090 : case Fragment::THRESH:
914 [ - + ]: 11090 : ops += node_info->subtypes.size();
915 : 11090 : break;
916 : 7830 : case Fragment::MULTI:
917 : 7830 : ops += 1;
918 : 7830 : break;
919 [ - + ]: 1887 : case Fragment::MULTI_A:
920 [ - + ]: 1887 : ops += node_info->keys.size() + 1;
921 : 1887 : break;
922 : 26297 : case Fragment::WRAP_A:
923 : 26297 : ops += 2;
924 : 26297 : break;
925 : 3712 : case Fragment::WRAP_S:
926 : 3712 : ops += 1;
927 : 3712 : break;
928 : 16895 : case Fragment::WRAP_C:
929 : 16895 : ops += 1;
930 : 16895 : break;
931 : 1623 : case Fragment::WRAP_D:
932 : 1623 : ops += 3;
933 : 1623 : break;
934 : : case Fragment::WRAP_V:
935 : : // We don't account for OP_VERIFY here; that will be corrected for when the actual
936 : : // node is constructed below.
937 : : break;
938 : 3016 : case Fragment::WRAP_J:
939 : 3016 : ops += 4;
940 : 3016 : break;
941 : 8038 : case Fragment::WRAP_N:
942 : 8038 : ops += 1;
943 : 8038 : break;
944 : : }
945 [ + + ]: 338568 : if (ops > MAX_OPS_PER_SCRIPT) return {};
946 [ + - ]: 338468 : auto subtypes = node_info->subtypes;
947 [ - + ]: 338468 : todo.back().second = std::move(node_info);
948 [ - + + - ]: 338468 : todo.reserve(todo.size() + subtypes.size());
949 : : // As elements on the todo stack are processed back to front, construct
950 : : // them in reverse order (so that the first subnode is generated first).
951 [ - + + + ]: 695708 : for (size_t i = 0; i < subtypes.size(); ++i) {
952 [ + - ]: 357240 : todo.emplace_back(*(subtypes.rbegin() + i), std::nullopt);
953 : : }
954 : 339765 : } else {
955 : : // The back of todo has fragment and number of children decided, and
956 : : // those children have been constructed at the back of stack. Pop
957 : : // that entry off todo, and use it to construct a new Node on
958 : : // stack.
959 [ - + ]: 320518 : NodeInfo& info = *todo.back().second;
960 : : // Gather children from the back of stack.
961 : 320518 : std::vector<Node> sub;
962 [ - + + - ]: 320518 : sub.reserve(info.subtypes.size());
963 [ - + + + ]: 631425 : for (size_t i = 0; i < info.subtypes.size(); ++i) {
964 [ + - ]: 310907 : sub.push_back(std::move(*(stack.end() - info.subtypes.size() + i)));
965 : : }
966 : 320518 : stack.erase(stack.end() - info.subtypes.size(), stack.end());
967 : : // Construct new Node.
968 [ + - ]: 641036 : Node node{[&] {
969 [ + + + + ]: 320518 : if (info.keys.empty()) {
970 [ + - + - ]: 572658 : return Node{miniscript::internal::NoDupCheck{}, script_ctx, info.fragment, std::move(sub), std::move(info.hash), info.k};
971 : : }
972 [ - + - + ]: 34189 : assert(sub.empty());
973 [ - + - + ]: 34189 : assert(info.hash.empty());
974 [ + - + - ]: 68378 : return Node{miniscript::internal::NoDupCheck{}, script_ctx, info.fragment, std::move(info.keys), info.k};
975 : : }()};
976 : : // Verify acceptability.
977 [ + + ]: 320518 : if ((node.GetType() & "KVWB"_mst) == ""_mst) {
978 [ - + ]: 178 : assert(!strict_valid);
979 : 178 : return {};
980 : : }
981 [ + + ]: 320340 : if (!(type_needed == ""_mst)) {
982 [ - + ]: 301327 : assert(node.GetType() << type_needed);
983 : : }
984 [ + + ]: 320340 : if (!node.IsValid()) return {};
985 : : // Update resource predictions.
986 [ + + + + ]: 320337 : if (node.Fragment() == Fragment::WRAP_V && node.Subs()[0].GetType() << "x"_mst) {
987 : 18381 : ops += 1;
988 : 18381 : scriptsize += 1;
989 : : }
990 [ + + + + ]: 320337 : if (!miniscript::IsTapscript(script_ctx) && ops > MAX_OPS_PER_SCRIPT) return {};
991 [ + + + + ]: 517692 : if (scriptsize > miniscript::internal::MaxScriptSize(script_ctx)) {
992 : 2 : return {};
993 : : }
994 : : // Move it to the stack.
995 : 320317 : stack.push_back(std::move(node));
996 : 320317 : todo.pop_back();
997 : 320518 : }
998 : : }
999 [ - + ]: 4263 : assert(stack.size() == 1);
1000 [ - + ]: 4263 : assert(stack[0].GetStaticOps() == ops);
1001 [ - + ]: 4263 : assert(stack[0].ScriptSize() == scriptsize);
1002 [ + - ]: 4263 : stack[0].DuplicateKeyCheck(KEY_COMP);
1003 : 4263 : return std::move(stack[0]);
1004 [ - + ]: 11522 : }
1005 : :
1006 : : //! The spk for this script under the given context. If it's a Taproot output also record the spend data.
1007 : 3918 : CScript ScriptPubKey(MsCtx ctx, const CScript& script, TaprootBuilder& builder)
1008 : : {
1009 [ + + + - : 3918 : if (!miniscript::IsTapscript(ctx)) return CScript() << OP_0 << WitnessV0ScriptHash(script);
+ - ]
1010 : :
1011 : : // For Taproot outputs we always use a tree with a single script and a dummy internal key.
1012 [ + + ]: 3342 : builder.Add(0, script, TAPROOT_LEAF_TAPSCRIPT);
1013 : 1671 : builder.Finalize(XOnlyPubKey::NUMS_H);
1014 [ + - ]: 3342 : return GetScriptForDestination(builder.GetOutput());
1015 : : }
1016 : :
1017 : : //! Fill the witness with the data additional to the script satisfaction.
1018 : 3669 : void SatisfactionToWitness(MsCtx ctx, CScriptWitness& witness, const CScript& script, TaprootBuilder& builder) {
1019 : : // For P2WSH, it's only the witness script.
1020 [ + + ]: 7338 : witness.stack.emplace_back(script.begin(), script.end());
1021 [ + + ]: 3669 : if (!miniscript::IsTapscript(ctx)) return;
1022 : : // For Tapscript we also need the control block.
1023 [ + - ]: 3028 : witness.stack.push_back(*builder.GetSpendData().scripts.begin()->second.begin());
1024 : : }
1025 : :
1026 : : /** Perform various applicable tests on a miniscript Node. */
1027 : 5761 : void TestNode(const MsCtx script_ctx, const std::optional<Node>& node, FuzzedDataProvider& provider)
1028 : : {
1029 [ + + ]: 5761 : if (!node) return;
1030 : :
1031 : : // Check that it roundtrips to text representation
1032 : 4263 : const ParserContext parser_ctx{script_ctx};
1033 : 4263 : std::optional<std::string> str{node->ToString(parser_ctx)};
1034 [ - + ]: 4263 : assert(str);
1035 [ - + ]: 4263 : auto parsed = miniscript::FromString(*str, parser_ctx);
1036 [ - + ]: 4263 : assert(parsed);
1037 [ + - - + ]: 4263 : assert(*parsed == *node);
1038 : :
1039 : : // Check consistency between script size estimation and real size.
1040 [ + - ]: 4263 : auto script = node->ToScript(parser_ctx);
1041 [ + + - + ]: 8148 : assert(node->ScriptSize() == script.size());
1042 : :
1043 : : // Check consistency of "x" property with the script (type K is excluded, because it can end
1044 : : // with a push of a key, which could match these opcodes).
1045 [ + + ]: 4263 : if (!(node->GetType() << "K"_mst)) {
1046 [ + + ]: 4158 : bool ends_in_verify = !(node->GetType() << "x"_mst);
1047 : 19302 : assert(ends_in_verify == (script.back() == OP_CHECKSIG || script.back() == OP_CHECKMULTISIG || script.back() == OP_EQUAL || script.back() == OP_NUMEQUAL));
[ + + + +
+ + + + +
+ - + ]
1048 : : }
1049 : :
1050 : : // The rest of the checks only apply when testing a valid top-level script.
1051 [ + + ]: 4263 : if (!node->IsValidTopLevel()) return;
1052 : :
1053 : : // Check roundtrip to script
1054 [ + - ]: 3918 : auto decoded = miniscript::FromScript(script, parser_ctx);
1055 [ - + ]: 3918 : assert(decoded);
1056 : : // Note we can't use *decoded == *node because the miniscript representation may differ, so we check that:
1057 : : // - The script corresponding to that decoded form matches exactly
1058 : : // - The type matches exactly
1059 [ + - - + ]: 3918 : assert(decoded->ToScript(parser_ctx) == script);
1060 [ - + ]: 3918 : assert(decoded->GetType() == node->GetType());
1061 : :
1062 : : // Optionally pad the script or the witness in order to increase the sensitivity of the tests of
1063 : : // the resources limits logic.
1064 : 3918 : CScriptWitness witness_mal, witness_nonmal;
1065 [ + + ]: 3918 : if (provider.ConsumeBool()) {
1066 : : // Under P2WSH, optionally pad the script with OP_NOPs to max op the ops limit of the constructed script.
1067 : : // This makes the script obviously not actually miniscript-compatible anymore, but the
1068 : : // signatures constructed in this test don't commit to the script anyway, so the same
1069 : : // miniscript satisfier will work. This increases the sensitivity of the test to the ops
1070 : : // counting logic being too low, especially for simple scripts.
1071 : : // Do this optionally because we're not solely interested in cases where the number of ops is
1072 : : // maximal.
1073 : : // Do not pad more than what would cause MAX_STANDARD_P2WSH_SCRIPT_SIZE to be reached, however,
1074 : : // as that also invalidates scripts.
1075 : 647 : const auto node_ops{node->GetOps()};
1076 [ + + + + ]: 991 : if (!IsTapscript(script_ctx) && node_ops && *node_ops < MAX_OPS_PER_SCRIPT
1077 [ + + + + ]: 935 : && node->ScriptSize() < MAX_STANDARD_P2WSH_SCRIPT_SIZE) {
1078 [ + + ]: 286 : int add = std::min<int>(
1079 [ + + ]: 286 : MAX_OPS_PER_SCRIPT - *node_ops,
1080 [ + + ]: 286 : MAX_STANDARD_P2WSH_SCRIPT_SIZE - node->ScriptSize());
1081 [ + + ]: 28306 : for (int i = 0; i < add; ++i) script.push_back(OP_NOP);
1082 : : }
1083 : :
1084 : : // Under Tapscript, optionally pad the stack up to the limit minus the calculated maximum execution stack
1085 : : // size to assert a Miniscript would never add more elements to the stack during execution than anticipated.
1086 : 647 : const auto node_exec_ss{node->GetExecStackSize()};
1087 [ + + + + : 647 : if (miniscript::IsTapscript(script_ctx) && node_exec_ss && *node_exec_ss < MAX_STACK_SIZE) {
+ - ]
1088 [ + - ]: 281 : unsigned add{(unsigned)MAX_STACK_SIZE - *node_exec_ss};
1089 [ + - ]: 281 : witness_mal.stack.resize(add);
1090 [ + - ]: 281 : witness_nonmal.stack.resize(add);
1091 : 281 : script.reserve(add);
1092 [ + + ]: 270174 : for (unsigned i = 0; i < add; ++i) script.push_back(OP_NIP);
1093 : : }
1094 : : }
1095 : :
1096 : 3918 : const SatisfierContext satisfier_ctx{script_ctx};
1097 : :
1098 : : // Get the ScriptPubKey for this script, filling spend data if it's Taproot.
1099 [ + - ]: 3918 : TaprootBuilder builder;
1100 [ + - ]: 3918 : const CScript script_pubkey{ScriptPubKey(script_ctx, script, builder)};
1101 : :
1102 : : // Run malleable satisfaction algorithm.
1103 : 3918 : std::vector<std::vector<unsigned char>> stack_mal;
1104 [ + - ]: 3918 : const bool mal_success = node->Satisfy(satisfier_ctx, stack_mal, false) == miniscript::Availability::YES;
1105 : :
1106 : : // Run non-malleable satisfaction algorithm.
1107 : 3918 : std::vector<std::vector<unsigned char>> stack_nonmal;
1108 [ + - ]: 3918 : const bool nonmal_success = node->Satisfy(satisfier_ctx, stack_nonmal, true) == miniscript::Availability::YES;
1109 : :
1110 [ + + ]: 3918 : if (nonmal_success) {
1111 : : // Non-malleable satisfactions are bounded by the satisfaction size plus:
1112 : : // - For P2WSH spends, the witness script
1113 : : // - For Tapscript spends, both the witness script and the control block
1114 : 1114 : const size_t max_stack_size{*node->GetStackSize() + 1 + miniscript::IsTapscript(script_ctx)};
1115 [ - + - + ]: 1114 : assert(stack_nonmal.size() <= max_stack_size);
1116 : : // If a non-malleable satisfaction exists, the malleable one must also exist, and be identical to it.
1117 [ - + ]: 1114 : assert(mal_success);
1118 [ - + ]: 1114 : assert(stack_nonmal == stack_mal);
1119 : : // Compute witness size (excluding script push, control block, and witness count encoding).
1120 [ - + - + ]: 1114 : const uint64_t wit_size{GetSerializeSize(stack_nonmal) - GetSizeOfCompactSize(stack_nonmal.size())};
1121 [ - + - + ]: 2228 : assert(wit_size <= *node->GetWitnessSize());
1122 : :
1123 : : // Test non-malleable satisfaction.
1124 [ + - ]: 1114 : witness_nonmal.stack.insert(witness_nonmal.stack.end(), std::make_move_iterator(stack_nonmal.begin()), std::make_move_iterator(stack_nonmal.end()));
1125 [ + - ]: 1114 : SatisfactionToWitness(script_ctx, witness_nonmal, script, builder);
1126 : 1114 : ScriptError serror;
1127 [ + - ]: 1114 : bool res = VerifyScript(DUMMY_SCRIPTSIG, script_pubkey, &witness_nonmal, STANDARD_SCRIPT_VERIFY_FLAGS, CHECKER_CTX, &serror);
1128 : : // Non-malleable satisfactions are guaranteed to be valid if ValidSatisfactions().
1129 [ + + - + ]: 1114 : if (node->ValidSatisfactions()) assert(res);
1130 : : // More detailed: non-malleable satisfactions must be valid, or could fail with ops count error (if CheckOpsLimit failed),
1131 : : // or with a stack size error (if CheckStackSize check failed).
1132 [ + + + - : 93 : assert(res ||
- + - - -
- ]
1133 : : (!node->CheckOpsLimit() && serror == ScriptError::SCRIPT_ERR_OP_COUNT) ||
1134 : : (!node->CheckStackSize() && serror == ScriptError::SCRIPT_ERR_STACK_SIZE));
1135 : : }
1136 : :
1137 [ + + + + : 3918 : if (mal_success && (!nonmal_success || witness_mal.stack != witness_nonmal.stack)) {
+ - ]
1138 : : // Test malleable satisfaction only if it's different from the non-malleable one.
1139 [ + - ]: 2555 : witness_mal.stack.insert(witness_mal.stack.end(), std::make_move_iterator(stack_mal.begin()), std::make_move_iterator(stack_mal.end()));
1140 [ + - ]: 2555 : SatisfactionToWitness(script_ctx, witness_mal, script, builder);
1141 : 2555 : ScriptError serror;
1142 [ + - ]: 2555 : bool res = VerifyScript(DUMMY_SCRIPTSIG, script_pubkey, &witness_mal, STANDARD_SCRIPT_VERIFY_FLAGS, CHECKER_CTX, &serror);
1143 : : // Malleable satisfactions are not guaranteed to be valid under any conditions, but they can only
1144 : : // fail due to stack or ops limits.
1145 [ + + + + : 2555 : assert(res || serror == ScriptError::SCRIPT_ERR_OP_COUNT || serror == ScriptError::SCRIPT_ERR_STACK_SIZE);
- + ]
1146 : : }
1147 : :
1148 [ + + ]: 3918 : if (node->IsSane()) {
1149 : : // For sane nodes, the two algorithms behave identically.
1150 [ - + ]: 483 : assert(mal_success == nonmal_success);
1151 : : }
1152 : :
1153 : : // Verify that if a node is policy-satisfiable, the malleable satisfaction
1154 : : // algorithm succeeds. Given that under IsSane() both satisfactions
1155 : : // are identical, this implies that for such nodes, the non-malleable
1156 : : // satisfaction will also match the expected policy.
1157 : 83882 : const auto is_key_satisfiable = [script_ctx](const CPubKey& pubkey) -> bool {
1158 : 79964 : auto sig_ptr{TEST_DATA.GetSig(script_ctx, pubkey)};
1159 [ + - + + ]: 79964 : return sig_ptr != nullptr && sig_ptr->second;
1160 : 3918 : };
1161 [ + - ]: 3918 : bool satisfiable = node->IsSatisfiable([&](const Node& node) -> bool {
1162 [ + + + + : 53176 : switch (node.Fragment()) {
+ + + - ]
1163 : 21991 : case Fragment::PK_K:
1164 : 21991 : case Fragment::PK_H:
1165 : 21991 : return is_key_satisfiable(node.Keys()[0]);
1166 : 9184 : case Fragment::MULTI:
1167 : 9184 : case Fragment::MULTI_A: {
1168 : 9184 : size_t sats = std::ranges::count_if(node.Keys(), [&](const auto& key) {
1169 : 57973 : return size_t(is_key_satisfiable(key));
1170 : 9184 : });
1171 : 9184 : return sats >= node.K();
1172 : : }
1173 : 9099 : case Fragment::OLDER:
1174 : 9099 : case Fragment::AFTER:
1175 : 9099 : return node.K() & 1;
1176 : 2881 : case Fragment::SHA256:
1177 : 2881 : return TEST_DATA.sha256_preimages.contains(node.Data());
1178 : 3444 : case Fragment::HASH256:
1179 : 3444 : return TEST_DATA.hash256_preimages.contains(node.Data());
1180 : 3104 : case Fragment::RIPEMD160:
1181 : 3104 : return TEST_DATA.ripemd160_preimages.contains(node.Data());
1182 : 3473 : case Fragment::HASH160:
1183 : 3473 : return TEST_DATA.hash160_preimages.contains(node.Data());
1184 : 0 : default:
1185 : 0 : assert(false);
1186 : : }
1187 : : return false;
1188 : : });
1189 [ - + ]: 3918 : assert(mal_success == satisfiable);
1190 : 4263 : }
1191 : :
1192 : : } // namespace
1193 : :
1194 : 3 : void FuzzInit()
1195 : : {
1196 [ + - + - : 3 : static ECC_Context ecc_context{};
+ - ]
1197 : 3 : TEST_DATA.Init();
1198 : 3 : }
1199 : :
1200 : 1 : void FuzzInitSmart()
1201 : : {
1202 : 1 : FuzzInit();
1203 : 1 : SMARTINFO.Init();
1204 : 1 : }
1205 : :
1206 : : /** Fuzz target that runs TestNode on nodes generated using ConsumeNodeStable. */
1207 [ + - ]: 2402 : FUZZ_TARGET(miniscript_stable, .init = FuzzInit)
1208 : : {
1209 : : // Run it under both P2WSH and Tapscript contexts.
1210 [ + + ]: 5778 : for (const auto script_ctx: {MsCtx::P2WSH, MsCtx::TAPSCRIPT}) {
1211 : 3852 : FuzzedDataProvider provider(buffer.data(), buffer.size());
1212 [ + - ]: 190885 : TestNode(script_ctx, GenNode(script_ctx, [&](Type needed_type) {
1213 [ + - ]: 183181 : return ConsumeNodeStable(script_ctx, provider, needed_type);
1214 : : }, ""_mst), provider);
1215 : : }
1216 : 1926 : }
1217 : :
1218 : : /** Fuzz target that runs TestNode on nodes generated using ConsumeNodeSmart. */
1219 [ + - ]: 2385 : FUZZ_TARGET(miniscript_smart, .init = FuzzInitSmart)
1220 : : {
1221 : : /** The set of types we aim to construct nodes for. Together they cover all. */
1222 : 1909 : static constexpr std::array<Type, 4> BASE_TYPES{"B"_mst, "V"_mst, "K"_mst, "W"_mst};
1223 : :
1224 : 1909 : FuzzedDataProvider provider(buffer.data(), buffer.size());
1225 : 1909 : const auto script_ctx{(MsCtx)provider.ConsumeBool()};
1226 [ + - ]: 158493 : TestNode(script_ctx, GenNode(script_ctx, [&](Type needed_type) {
1227 [ + - ]: 156584 : return ConsumeNodeSmart(script_ctx, provider, needed_type);
1228 : 1909 : }, PickValue(provider, BASE_TYPES), true), provider);
1229 : 1909 : }
1230 : :
1231 : : /* Fuzz tests that test parsing from a string, and roundtripping via string. */
1232 [ + - ]: 1450 : FUZZ_TARGET(miniscript_string, .init = FuzzInit)
1233 : : {
1234 [ + + + + ]: 1948 : constexpr auto is_too_expensive{[](std::span<const uint8_t> buf) { return HasTooManySubFrag(buf) || HasTooManyWrappers(buf); }};
1235 : :
1236 [ + - ]: 974 : if (buffer.empty()) return;
1237 : 974 : FuzzedDataProvider provider(buffer.data(), buffer.size());
1238 : 974 : auto str = provider.ConsumeBytesAsString(provider.remaining_bytes() - 1);
1239 [ + - + + ]: 974 : if (is_too_expensive(MakeUCharSpan(str))) return;
1240 : 965 : const ParserContext parser_ctx{(MsCtx)provider.ConsumeBool()};
1241 [ - + ]: 965 : auto parsed = miniscript::FromString(str, parser_ctx);
1242 [ + + ]: 965 : if (!parsed) return;
1243 : :
1244 [ + - ]: 535 : const auto str2 = parsed->ToString(parser_ctx);
1245 [ - + ]: 535 : assert(str2);
1246 [ - + ]: 535 : auto parsed2 = miniscript::FromString(*str2, parser_ctx);
1247 [ - + ]: 535 : assert(parsed2);
1248 [ + - - + ]: 535 : assert(*parsed == *parsed2);
1249 : 1404 : }
1250 : :
1251 : : /* Fuzz tests that test parsing from a script, and roundtripping via script. */
1252 [ + - ]: 1356 : FUZZ_TARGET(miniscript_script)
1253 : : {
1254 : 880 : FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
1255 : 880 : const std::optional<CScript> script = ConsumeDeserializable<CScript>(fuzzed_data_provider);
1256 [ + + ]: 880 : if (!script) return;
1257 : :
1258 : 867 : const ScriptParserContext script_parser_ctx{(MsCtx)fuzzed_data_provider.ConsumeBool()};
1259 [ + - ]: 867 : const auto ms = miniscript::FromScript(*script, script_parser_ctx);
1260 [ + + ]: 867 : if (!ms) return;
1261 : :
1262 [ + - - + ]: 606 : assert(ms->ToScript(script_parser_ctx) == *script);
1263 : 1444 : }
|