fuzz: Fix mini_miner_selection running out of coin #27806

murchandamus commented at 6:43 PM on June 2, 2023: contributor

Fixes a bug in the mini_miner_selection fuzz test found by fuzzing: It was possible for the mini_miner_selection fuzz test to generated transactions that created fewer new outputs than the two inputs they each spent. If the fuzz seed did so consistently, eventually it would cause a pop_front() on an empty available_coins which resulted in undefined behavior.

Fixed per belt-suspender approach:

assert that available_coins is not empty before generating tx
generate at least two coins per new tx
allow building tx with a single input if only one coin is available

DrahtBot commented at 6:43 PM on June 2, 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	MarcoFalke, dergoegge
Stale ACK	glozow

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

DrahtBot added the label Tests on Jun 2, 2023

achow101 requested review from glozow on Jun 2, 2023

in src/test/fuzz/mini_miner.cpp:122 in bbb9277399 outdated

 117 | @@ -118,9 +118,10 @@ FUZZ_TARGET_INIT(mini_miner_selection, initialize_miner)
 118 |      LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 100)
 119 |      {
 120 |          CMutableTransaction mtx = CMutableTransaction();
 121 | -        const size_t num_inputs = 2;
 122 | -        const size_t num_outputs = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(2, 5);
 123 | +        const size_t num_inputs = std::min(size_t{2}, available_coins.size());

achow101 commented at 10:06 PM on June 2, 2023:

In bbb927739955b1588d94c5fd8ed73ddf5afde46c "fuzz: Fix mini_miner_selection running out of coin"

Is it possible that available_coins is empty and so num_inputs = 0? It may be useful to have an additional assert before the inputs are filled below.

brunoerg commented at 2:30 PM on June 3, 2023:

Wouldn't be an alternative to replace LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 100) for LIMITED_WHILE(!available_coins.empty(), 100)?

murchandamus commented at 6:03 PM on June 5, 2023:

@achow101: I believe that it could not dip below 1 available input, since there were always two created and (n-1) added to the available_coins. Now, it should be impossible for the count to dip below the initial count because it consumes a maximum of two inputs and also adds at least two coins to available_coins every iteration.

Happy to add an assert, though

murchandamus commented at 6:09 PM on June 5, 2023:

@brunoerg: I think that would work as well, although it would probably lead to smaller clusters in some of the fuzzing

glozow commented at 4:50 PM on June 7, 2023:

Happy to add an assert, though

Maybe add this? assert(!available_coins.empty()); above this line

sipa commented at 6:07 PM on June 5, 2023: member

7obqz4

dergoegge approved

dergoegge commented at 10:43 AM on June 7, 2023: member

Code review ACK bbb927739955b1588d94c5fd8ed73ddf5afde46c

murchandamus force-pushed on Jun 9, 2023

murchandamus commented at 7:22 PM on June 9, 2023: contributor

Added the additional assert suggested above in #27806 (review)

DrahtBot added the label CI failed on Jun 9, 2023

glozow commented at 8:51 AM on June 12, 2023: member

ACK de5d8626184f6189d07137ca935da8703b8a78a3

DrahtBot requested review from dergoegge on Jun 12, 2023

dergoegge approved

dergoegge commented at 8:56 AM on June 12, 2023: member

Code review ACK de5d8626184f6189d07137ca935da8703b8a78a3

maflcko commented at 8:58 AM on June 12, 2023: member

I presume this is a fix for https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=59385, which was closed unexpectedly and incorrectly by OSS-Fuzz. Also, the issue should ideally reproduce outside of msan.

To fix both, I've just enabled -D_LIBCPP_ENABLE_ASSERTIONS=1 on OSS-Fuzz, so I'd recommend to wait 2-3 days before merging this to give OSS-Fuzz a final chance to re-detect this issue.

glozow commented at 9:00 AM on June 12, 2023: member

To fix both, I've just enabled -D_LIBCPP_ENABLE_ASSERTIONS=1 on OSS-Fuzz, so I'd recommend to wait 2-3 days before merging this to give OSS-Fuzz a final chance to re-detect this issue.

Noted, thanks!

in src/test/fuzz/mini_miner.cpp:123 in de5d862618 outdated

 117 | @@ -118,9 +118,11 @@ FUZZ_TARGET_INIT(mini_miner_selection, initialize_miner)
 118 |      LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 100)
 119 |      {
 120 |          CMutableTransaction mtx = CMutableTransaction();
 121 | -        const size_t num_inputs = 2;
 122 | -        const size_t num_outputs = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(2, 5);
 123 | +        assert(!available_coins.empty());
 124 | +        const size_t num_inputs = std::min(size_t{2}, available_coins.size());
 125 | +        const size_t num_outputs = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(3, 5);

maflcko commented at 9:01 AM on June 12, 2023:

Any reason this is set to 3, or previously to 2, when it could be 1 to allow for transactions with one output?

I don't think we should reduce test coverage with the rationale "belt-and-suspenders".

murchandamus commented at 6:13 PM on June 12, 2023:

The point of this fuzz test is to test the calculation of bump fees. If all outputs of transactions are spent, there are no bump fees to be calculated. We create at least two outputs to chain one other transaction off of the first (which we add to available_coins, and to have another output left hanging to calculate bump fees on later. We could also permit a single output, if we just make it conclude transaction creation if it runs out of available_coins. I guess that would still achieve our test’s goals on the higher side of outputs.

With the std::min(2, available_coins.size()) the (2, 5) should also not crash, though. I’ll test that and return it to that if my understanding is substantiated.

murchandamus commented at 6:37 PM on June 12, 2023:

I’ve reset it to (2, 5) after fuzzing ~100k execs and the problematic seed. I’m not sure (1, 5) would be an improvement in this particular fuzz seed, but happy to change it if people are convinced otherwise.

fuzz: Fix mini_miner_selection running out of coin

Fixes a bug in the mini_miner_selection fuzz test found by fuzzing:
It was possible for the mini_miner_selection fuzz test to generated
transactions that created fewer new spendable outputs than the two
inputs they each spend. If the fuzz seed did so consistently, eventually
it would cause a `pop_front()` on an empty available_coins.

Fixed by:
- asserting that available_coins is not empty before generating tx
- allowing to build tx with a single coin if only one is available

76c5ea703e

in src/test/fuzz/mini_miner.cpp:126 in de5d862618 outdated

 123 | +        assert(!available_coins.empty());
 124 | +        const size_t num_inputs = std::min(size_t{2}, available_coins.size());
 125 | +        const size_t num_outputs = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(3, 5);
 126 |          for (size_t n{0}; n < num_inputs; ++n) {
 127 | +            assert(available_coins.size() > 0);
 128 |              auto prevout = available_coins.front();

maflcko commented at 3:11 PM on June 12, 2023:

Style nit (only if you retouch), feel free to ignore: Can be written shorter via the included check in at:

            auto prevout = available_coins.at(0);

murchandamus commented at 6:30 PM on June 12, 2023:

Thanks, done.

murchandamus force-pushed on Jun 12, 2023

maflcko commented at 9:21 AM on June 13, 2023: member

lgtm ACK 76c5ea703e77d580b6962e60398f4988cbd9b58b

DrahtBot requested review from dergoegge on Jun 13, 2023

DrahtBot requested review from glozow on Jun 13, 2023

dergoegge approved

dergoegge commented at 3:17 PM on June 13, 2023: member

reACK 76c5ea703e77d580b6962e60398f4988cbd9b58b

fanquake merged this on Jun 13, 2023

fanquake closed this on Jun 13, 2023

murchandamus deleted the branch on Jun 13, 2023

sidhujag referenced this in commit d23114c76d on Jun 15, 2023

bitcoin locked this on Jun 12, 2024