Make miniscript_{stable,smart} fuzzers avoid too large scripts

sipa commented at 9:34 pm on February 25, 2023: member

This adds a number of improvements to the miniscript fuzzers that all amount to rejecting invalid or overly big miniscripts early on:

Base type propagation in the miniscript_stable fuzzers prevents constructing a large portion of miniscripts that would be illegal, with just a little bit of type logic in the fuzzer. The fuzzer input format is unchanged.
Ops and script size tracking in GenNode means that too-large scripts (either due to script size limit or ops limit) will be detected on the fly during fuzz input processing, before actually constructing the scripts.

Closes #27147.

DrahtBot commented at 9:34 pm on February 25, 2023: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	darosior, dergoegge

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

sipa requested review from darosior on Feb 25, 2023

sipa renamed this:
~~Improve miniscript_{stable,smart} fuzzer ability to avoid too large scripts~~
Make miniscript_{stable,smart} fuzzers avoid too large scripts
on Feb 25, 2023

fanquake requested review from instagibbs on Feb 27, 2023

fanquake requested review from dergoegge on Feb 27, 2023

in src/test/fuzz/miniscript.cpp:784 in b09b7a1f94 outdated

780@@ -778,6 +781,8 @@ NodeRef GenNode(F ConsumeNode, Type root_type, bool strict_valid = false) {
781             auto node_info = ConsumeNode(type_needed);
782             if (!node_info) return {};
783             // Update predicted resource limits.
784+            scriptsize += miniscript::internal::ComputeScriptLen(node_info->fragment, ""_mst, 0, node_info->k, node_info->subtypes.size(), node_info->keys.size()) + node_info->subtypes.size() - 1;

darosior commented at 9:35 am on February 28, 2023:

You can directly pass the number of sub fragments to ComputeScriptLen instead of passing 0 and then adding it.

 0diff --git a/src/test/fuzz/miniscript.cpp b/src/test/fuzz/miniscript.cpp
 1index 90d752b898..490fac18ce 100644
 2--- a/src/test/fuzz/miniscript.cpp
 3+++ b/src/test/fuzz/miniscript.cpp
 4@@ -781,7 +781,7 @@ NodeRef GenNode(F ConsumeNode, Type root_type, bool strict_valid = false) {
 5             auto node_info = ConsumeNode(type_needed);
 6             if (!node_info) return {};
 7             // Update predicted resource limits.
 8-            scriptsize += miniscript::internal::ComputeScriptLen(node_info->fragment, ""_mst, 0, node_info->k, node_info->subtypes.size(), node_info->keys.size()) + node_info->subtypes.size() - 1;
 9+            scriptsize += miniscript::internal::ComputeScriptLen(node_info->fragment, ""_mst, node_info->subtypes.size(), node_info->k, node_info->subtypes.size(), node_info->keys.size()) - 1;
10             if (scriptsize > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
11             switch (node_info->fragment) {
12             case Fragment::JUST_0:

sipa commented at 2:28 pm on February 28, 2023:

Done.

in src/test/fuzz/miniscript.cpp:774 in b09b7a1f94 outdated

768@@ -769,6 +769,9 @@ NodeRef GenNode(F ConsumeNode, Type root_type, bool strict_valid = false) {
769     std::vector<std::pair<Type, std::optional<NodeInfo>>> todo{{root_type, {}}};
770     /** Predict the number of (static) script ops. */
771     uint32_t ops{0};
772+    /** Predict the total script size (every unexplored subnode is counted as one, as every leaf is
773+     *  at least one script byte). */
774+    uint32_t scriptsize{1};

darosior commented at 9:47 am on February 28, 2023:

Maybe worth pointing to the explanatory comment in Parse()? I think the “borrowing” logic could be a little unclear to a reader with less context.

sipa commented at 2:28 pm on February 28, 2023:

I’ve expanded the comment slightly, mentioning the FromScript logic.

darosior approved

darosior commented at 9:50 am on February 28, 2023: member

ACK b09b7a1f94885feed5d44a3858543536e3659287

Elegant fix and improvement. Just two non-blocking comments.

fanquake added this to the milestone 25.0 on Feb 28, 2023

Do base type propagation in miniscript_stable fuzzer

Keep track of which base type (B, K, V, or W) is desired in the miniscript_stable
ConsumeStableNode function. This allows aborting early if the constructed node
won't have the right type.

Note that this does not change the fuzzer format; the meaning of inputs in
ConsumeStableNode is unmodified. The only change is that often the fuzzer will
abort early.

The direct motivation is preventing recursing v: wrappers, which are the only
fragment type that does not otherwise increase the overall minimum possible script
size. In a later commit this will be exploited to prevent overly-large scripts from
being constructed.

5abb0f5ac3

Simplify miniscript fuzzer NodeInfo struct

Since we now keep track of all expected child node types (even if rudimentary)
in both miniscript_stable and miniscript_smart fuzzers, there is no need anymore
for the former shortcut NodeInfo constructors without sub types.

e1f30414c6

Enforce type consistency in miniscript_stable fuzz test

Add a self-check to the fuzzer that the constructed types match the expected
types in the miniscript_stable fuzzer too.

213fffa513

Make miniscript fuzzers avoid ops limit

Keep track of the total number of ops the constructed script will have
during miniscript_stable and miniscript_smart fuzzers' GenNode, so it
can abort early if the 201 ops limit would be exceeded.

Also add a self-check that the final constructed node has the predicted
ops size limit, so we know the fuzzer's logic for keeping track of this
is correct.

bcec5ab4ff

sipa force-pushed on Feb 28, 2023

Make miniscript fuzzers avoid script size limit

Use the same technique as is using in the FromString miniscript parser to
predict the final script size of the miniscript being generated in the
miniscript_stable and miniscript_smart fuzzers (by counting every unexplored
sub node as 1 script byte, which is possible because every leaf node always
adds at least 1 byte). This allows bailing out early if the script being
generated would exceed the maximum allowed size (before actually constructing
the miniscript, as that may happen only significantly later potentially).

Also add a self-check to make sure this predicted script size matches that
of generated scripts.

56e37e71a2

in src/test/fuzz/miniscript.cpp:785 in bcc054d046 outdated

779@@ -777,7 +780,11 @@ NodeRef GenNode(F ConsumeNode, Type root_type, bool strict_valid = false) {
780             // Fragment/children have not been decided yet. Decide them.
781             auto node_info = ConsumeNode(type_needed);
782             if (!node_info) return {};
783-            // Update predicted resource limits.
784+            // Update predicted resource limits. Since every leaf Miniscript node is at least one
785+            // byte long, we move one byte from each child to their parent. A similar technique is
786+            // used in the miniscript FromScript parser.

darosior commented at 2:35 pm on February 28, 2023:

Sorry to nit just for a code comment.. But it’s in Parse() (called by FromString()) that we have this logic, not FromScript (where we can just check the script size isn’t larger than 3600).

sipa commented at 2:43 pm on February 28, 2023:

Fixed.

sipa force-pushed on Feb 28, 2023

darosior commented at 2:47 pm on February 28, 2023: member

re-ACK 56e37e71a2

dergoegge commented at 4:09 pm on February 28, 2023: member

tACK 56e37e71a2538a240cc360678aeb752d17bd8f45

Reproduced the initial timeout from #27147 and verified that this patch fixes the issue.

dergoegge approved

fanquake merged this on Feb 28, 2023

fanquake closed this on Feb 28, 2023

sidhujag referenced this in commit 6a0ba6180a on Mar 1, 2023

fanquake commented at 7:56 pm on March 1, 2023: member

Verified as fixed: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=56332#c3.

bitcoin locked this on Feb 29, 2024

Make miniscript_{stable,smart} fuzzers avoid too large scripts #27165

Reviews