fuzz: txorphan tests fixups

sr-gi commented at 6:46 pm on April 26, 2024: member

Adds the following fixups in txorphan fuzz tests:

Don’t bond the output count of the created orphans to the number of available coins
Allow duplicate inputs but don’t store duplicate outpoints

Most significantly, this gets rid of the duplicate_input flag altogether, making the test easier to reason about. Notice how, under normal conditions, duplicate inputs would be caught by MemPoolAccept::PreChecks, however, no validations checks are run on the test before adding data to the orphanage (neither were they before this patch)

Rationale

The way the test is currently written, duplicate inputs are allowed based on a random flag (duplicate_input). If the flag is unset, upon selecting an outpoint as input for a new transaction, the input is popped to prevent re-selection and later re-added to the collection (once all inputs have been picked). However, the re-addition to the collection is performed independently of whether the flag was set or not. This means that, if the flag is set, the selected inputs are duplicated which in turn makes these inputs more likely to be re-picked in the following iteration of the loop.

Additionally, both the input and output count of the transaction are bonded to the number of available outpoints. This makes sense for the former, but the latter shouldn’t be.

DrahtBot commented at 6:46 pm on April 26, 2024: contributor

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	glozow, instagibbs, maflcko

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 Apr 26, 2024

in src/test/fuzz/txorphan.cpp:75 in 4414b363f0 outdated

71@@ -67,8 +72,9 @@ FUZZ_TARGET(txorphan, .init = initialize_orphanage)
72                 tx_mut.vout.emplace_back(CAmount{0}, CScript{});
73             }
74             // restore previously popped outpoints
75-            for (auto& in : tx_mut.vin) {
76-                outpoints.push_back(in.prevout);
77+            while (!selected_outpoints.empty()) {

instagibbs commented at 7:49 pm on April 26, 2024:

to make the link locally explicit?

0            while (!selected_outpoints.empty()) {
1                assert(!duplicate_input);

sr-gi commented at 7:55 pm on April 26, 2024:

Good point. Covered in 6998f02

sr-gi force-pushed on Apr 26, 2024

instagibbs approved

instagibbs commented at 4:23 pm on April 29, 2024: member

ACK 6998f02c97c0b2c3579fac160192402c8b09613d

in src/test/fuzz/txorphan.cpp:78 in 6998f02c97 outdated

71@@ -67,8 +72,10 @@ FUZZ_TARGET(txorphan, .init = initialize_orphanage)
72                 tx_mut.vout.emplace_back(CAmount{0}, CScript{});
73             }
74             // restore previously popped outpoints
75-            for (auto& in : tx_mut.vin) {
76-                outpoints.push_back(in.prevout);
77+            while (!selected_outpoints.empty()) {
78+                assert(!duplicate_input);
79+                outpoints.push_back(selected_outpoints.back());
80+                selected_outpoints.pop_back();

glozow commented at 2:23 pm on April 30, 2024:

Should this be happening when duplicate_inputs is true (we’d be intentionally re-adding copies of the inputs we used)? Maybe I’m interpreting duplicate_inputs incorrectly but I thought that just means “we’re ok with duplicates” not “we will add a copy of an outpoint every time we use it”

sr-gi commented at 2:45 pm on April 30, 2024:

The way I’ve understood duplicate_inputs is: “We are OK with using the same input more than once in a transaction”. The way the test was built, re-using inputs across transactions was always an option, so I took that for granted.

sr-gi commented at 3:13 pm on May 1, 2024:

I updated the approach to get rid of duplicate_inputs altogether. Let me know if this make more sense to you now

in src/test/fuzz/txorphan.cpp:61 in 6998f02c97 outdated

59             // pick unique outpoints from outpoints as input
60             for (uint32_t i = 0; i < num_in; i++) {
61                 auto& prevout = PickValue(fuzzed_data_provider, outpoints);
62-                tx_mut.vin.emplace_back(prevout);
63+                // make every txid unique so multiple iteration don't potentially create the same outpoint
64+                tx_mut.vin.emplace_back(prevout, CScript{}, nSequence--);

glozow commented at 2:26 pm on April 30, 2024:

Approach-wise, sorry to bikeshed, but did you consider just making outpoints a set instead of a vector?

sr-gi commented at 2:44 pm on April 30, 2024:

Yeah, that may reduce the boilerplate and, given this is a test, performance shouldn’t matter much

sr-gi commented at 4:51 pm on April 30, 2024:

Covered in 0ab279e

sr-gi force-pushed on Apr 30, 2024

DrahtBot added the label CI failed on Apr 30, 2024

DrahtBot commented at 5:21 pm on April 30, 2024: contributor

🚧 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/24436241229

DrahtBot removed the label CI failed on Apr 30, 2024

fuzz: txorphan tests fixups

Adds the following fixups in txorphan fuzz tests:

- Don't bond the output count of the created orphans based on the number of available coins
- Allow duplicate inputs, when applicable, but don't store duplicate outpoints

Rationale
---------

The way the test is currently written, duplicate inputs are allowed based on a random flag (`duplicate_input`).
If the flag is unset, upon selecting an outpoint as input for a new transaction, the input is popped to prevent re-selection,
and later re-added to the collection (once all inputs have been picked). However, the re-addition to the collection is performed independently of whether the flag was set or not.
This means that, if the flag is set, the selected inputs are duplicated which in turn makes these inputs more likely to be re-picked in the following iteration of the loop.

Additionally, both the input and output count of the transaction and bonded to the number of available outpoints. This makes sense for the former, but the latter shouldn't be.

58594c7040

sr-gi force-pushed on May 1, 2024

sr-gi commented at 3:10 pm on May 1, 2024: member

Updated the approach to get rid of duplicate_input altogether, simplifying the test and reducing the boilerplate when dealing with duplicate outpoints

glozow commented at 6:07 pm on May 1, 2024: member

ACK 58594c7

DrahtBot requested review from instagibbs on May 1, 2024

in src/test/fuzz/txorphan.cpp:60 in 58594c7040

63-                // pop the picked outpoint if duplicate input is not allowed
64-                if (!duplicate_input) {
65-                    std::swap(prevout, outpoints.back());
66-                    outpoints.pop_back();
67-                }
68+                // try making transactions unique by setting a random nSequence, but allow duplicate transactions if they happen

instagibbs commented at 6:23 pm on May 1, 2024:

feel free to ignore

micro-nit/guess: for stability I think a single boolean might be better

sr-gi commented at 8:26 pm on May 1, 2024:

The reason why I choose to do it this way is because I don’t think we generally want to be generating the same transaction often, but it won’t be an issue if the case is hit once in a while (really infrequently really).

I don’t have strong opinions on what the odds for that should be, so I’m happy to change it if someone does, otherwise I’ll leave it as is

instagibbs approved

instagibbs commented at 7:09 pm on May 1, 2024: member

ACK 58594c7040241f2312b0b8735a8baf0412674613

ran fuzz for a while, no issues

sr-gi commented at 2:30 pm on May 8, 2024: member

@maflcko would you mind taking a look at this (given you reviewed the original PR for this fuzz test)?

maflcko commented at 2:57 pm on May 13, 2024: member

Additionally, both the input and output count of the transaction are bonded to the number of available outpoints. This makes sense for the former, but the latter shouldn’t be.

IIRC this was done to start with a few outputs in the beginning, and increase the number of outputs as the size of the fuzz input increases. The hope is that the runtime is linear with the size of the fuzz input, and that minimizing a potential crash results in a transaction with less outputs. If you allow 256 in the first iteration, the minimizer may spit out a transaction with that many outputs.

However, I haven’t benchmarked this. Should be fine either way.

utACK 58594c7040241f2312b0b8735a8baf0412674613

glozow merged this on May 13, 2024

glozow closed this on May 13, 2024

fuzz: txorphan tests fixups #29974

Rationale

Code Coverage

Reviews