fuzz: bound some miniscript operations to avoid fuzz timeouts #30197

darosior · 2024-05-30T11:07:55Z

Some of the logic in the miniscript module is quadratic. It only becomes an issue for very large uninteresting descriptors (like a thresh with 130k sub-fragments or a fragment with more than 60k nested j: wrappers).

This PR fixes the two types of fuzz timeouts reported by Marco in #28812 by trying to pinpoint the problematic descriptors through a simple analysis of the string, without limiting the size of the string itself. This is the same approach as was adopted for limiting the depth of derivation paths.

DrahtBot · 2024-05-30T11:07:58Z

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	dergoegge, stickies-v, marcofleon

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

DrahtBot · 2024-05-30T15:14:12Z

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the
documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

_{Debug: https://github.com/bitcoin/bitcoin/runs/25599793054}

maflcko · 2024-05-31T11:46:32Z

src/test/fuzz/util/descriptor.cpp

+{
+    auto count{0};
+    // We iterate in reverse order to start counting when we encounter a colon.
+    for (const auto& ch: buff | std::views::reverse) {


This isn't available yet. You'll have to use a reverse iterator manually for now.

src/test/fuzz/util/descriptor.cpp

dergoegge · 2024-06-13T08:39:25Z

#30229 was merged if you want to rebase

darosior · 2024-06-27T14:42:28Z

Rebased on master to take advantage of #30229.

dergoegge

utACK 178a1da

stickies-v

Concept ACK

src/test/fuzz/util/descriptor.cpp

src/test/fuzz/util/descriptor.h

src/test/fuzz/util/descriptor.cpp

marcofleon

Lightly tested ACK 178a1da. I tested on the three inputs brought up in #28812 and they all executed in 1ms. I can run the target for a while and see if any other timeouts come up. But looks good to me.

src/test/fuzz/util/descriptor.cpp

stickies-v

Light ACK 178a1da

Code LGTM and approach seems reasonable, but there may be fuzzing and miniscript nuances I'm not considering.

src/test/fuzz/util/descriptor.cpp

src/test/fuzz/util/descriptor.h

darosior · 2024-07-11T18:54:50Z

Thank you both for the review. I addressed your comments and heavily documented the code. I think it can be helpful as it indeed relies on being familiar with the descriptor/miniscript syntax. If only to make the assumptions in the counting logic explicit, or for when we'll all have forgotten about the details of this syntax.

I also modified two small things:

I introduced a limit to the number of nested sub-fragments a fragment may have. Since we are pushing an element on top of a stack for every occurrence of a (, the fuzzer might just spit a -max_len (about 1M in my experience) string of (((((((... and we'd create a stack of 1 million integers. It'd waste resources and anyways 10k subs is more than enough for anything interesting.
I corrected HasTooManySubs to not start counting at 1 since technically : isn't a wrapper. Instead i use an optional to detect whether we are counting or not. This also made the code slightly clearer and allowed to better document it.

stickies-v

Changes look good, thanks for adding more documentation. Nits can be ignored but I think HasTooManySubFrag needs some fixes wrt return statement and type narrowing before ACK.

src/test/fuzz/util/descriptor.cpp

This target may call into logic quadratic over the number of sub-fragments. Limit the number of sub-fragments to keep the runtime reasonable. Thanks to Marco Falke for reporting the fuzz timeouts with a minimized input.

The script building logic performs a quadratic number of copies in the number of nested wrappers in the miniscript. Limit the number of nested wrappers to avoid fuzz timeouts. Thanks to Marco Falke for reporting the fuzz timeouts and providing a minimal input to reproduce.

dergoegge

utACK bc34bc2

stickies-v

Light ACK bc34bc2

Code LGTM and approach seems reasonable, but there may be fuzzing and miniscript nuances I'm not considering.

marcofleon

Code review ACK bc34bc2. The added comments are useful, thanks for those. Tested on the three inputs in #28812 that caused the timeouts.

maflcko · 2024-07-17T14:00:54Z

Should the check be applied to miniscript_string, for example the miniscript_string/ae395bdc087e233d7f8e1844d4814b2c00cc9d21 input, as well?

darosior · 2024-07-18T14:25:29Z

Yes, makes sense.

DrahtBot added Tests CI failed labels May 30, 2024

fanquake requested review from maflcko and dergoegge May 31, 2024 09:36

maflcko reviewed May 31, 2024

View reviewed changes

maflcko reviewed Jun 5, 2024

View reviewed changes

src/test/fuzz/util/descriptor.cpp Outdated Show resolved Hide resolved

darosior force-pushed the 2405_desc_fuzz_timeouts branch 2 times, most recently from 7ff2652 to 980fc9f Compare June 6, 2024 10:44

stickies-v mentioned this pull request Jun 6, 2024

C++20 std::views::reverse #28687

Merged

DrahtBot removed the CI failed label Jun 6, 2024

darosior force-pushed the 2405_desc_fuzz_timeouts branch from 980fc9f to 178a1da Compare June 27, 2024 14:37

dergoegge approved these changes Jul 8, 2024

View reviewed changes

stickies-v reviewed Jul 8, 2024

View reviewed changes

src/test/fuzz/util/descriptor.cpp Outdated Show resolved Hide resolved

src/test/fuzz/util/descriptor.cpp Outdated Show resolved Hide resolved

src/test/fuzz/util/descriptor.h Outdated Show resolved Hide resolved

src/test/fuzz/util/descriptor.cpp Outdated Show resolved Hide resolved

darosior mentioned this pull request Jul 11, 2024

descriptors: Be able to specify change and receiving in a single descriptor string #22838

Merged

marcofleon reviewed Jul 11, 2024

View reviewed changes

src/test/fuzz/util/descriptor.cpp Outdated Show resolved Hide resolved

DrahtBot requested a review from stickies-v July 11, 2024 15:16

stickies-v approved these changes Jul 11, 2024

View reviewed changes

src/test/fuzz/util/descriptor.cpp Outdated Show resolved Hide resolved

src/test/fuzz/util/descriptor.cpp Outdated Show resolved Hide resolved

src/test/fuzz/util/descriptor.h Outdated Show resolved Hide resolved

darosior force-pushed the 2405_desc_fuzz_timeouts branch from 178a1da to 63f62b5 Compare July 11, 2024 18:54

stickies-v reviewed Jul 12, 2024

View reviewed changes

src/test/fuzz/util/descriptor.cpp Outdated Show resolved Hide resolved

src/test/fuzz/util/descriptor.cpp Outdated Show resolved Hide resolved

src/test/fuzz/util/descriptor.cpp Outdated Show resolved Hide resolved

src/test/fuzz/util/descriptor.cpp Outdated Show resolved Hide resolved

darosior added 2 commits July 14, 2024 17:46

darosior force-pushed the 2405_desc_fuzz_timeouts branch from 63f62b5 to bc34bc2 Compare July 14, 2024 15:49

dergoegge approved these changes Jul 15, 2024

View reviewed changes

DrahtBot requested review from marcofleon and stickies-v July 15, 2024 09:58

stickies-v approved these changes Jul 15, 2024

View reviewed changes

marcofleon reviewed Jul 15, 2024

View reviewed changes

fanquake merged commit 262260c into bitcoin:master Jul 15, 2024

maflcko mentioned this pull request Jul 18, 2024

fuzz: Limit parse_univalue input length #30473

Merged

darosior deleted the 2405_desc_fuzz_timeouts branch July 18, 2024 14:25

maflcko mentioned this pull request Jul 22, 2024

fuzz: Apply HasTooManySubFrag (et al) to miniscript_string (et al) #30498

Open

bitcoin locked and limited conversation to collaborators Jul 18, 2025

fuzz: bound some miniscript operations to avoid fuzz timeouts #30197

fuzz: bound some miniscript operations to avoid fuzz timeouts #30197

Uh oh!

Conversation

darosior commented May 30, 2024

Uh oh!

DrahtBot commented May 30, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Coverage

Reviews

Uh oh!

DrahtBot commented May 30, 2024

Uh oh!

maflcko May 31, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

dergoegge commented Jun 13, 2024

Uh oh!

darosior commented Jun 27, 2024

Uh oh!

dergoegge left a comment

Choose a reason for hiding this comment

Uh oh!

stickies-v left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

marcofleon left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

stickies-v left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

darosior commented Jul 11, 2024

Uh oh!

stickies-v left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

dergoegge left a comment

Choose a reason for hiding this comment

Uh oh!

stickies-v left a comment

Choose a reason for hiding this comment

Uh oh!

marcofleon left a comment

Choose a reason for hiding this comment

Uh oh!

maflcko commented Jul 17, 2024

Uh oh!

darosior commented Jul 18, 2024

Uh oh!

Uh oh!

DrahtBot commented May 30, 2024 •

edited

Loading

stickies-v left a comment •

edited

Loading