fuzz: add low-level target for txorphanage #25447

nit: year

nondeterminism does not work nicely with whitebox and greybox fuzzing. It makes it impossible for fuzz engines to track coverage precisely. Ideally the full program execution is fully predetermined by the fuzz input exclusively.

Please remove this and use fuzzed_data_provider instead.

nit: I think they are default initialized, so can remove them?

any reason to use COINBASE_MATURITY here? Shouldn't this be a constant derived from TxOrphanage internals? For example a bit larger than the maximum set size?

Already changed to DEFAULT_MAX_ORPHAN_TRANSACTIONS

It might be better to pick either:

• an existing prevout of a previously created transaction
• a random hash

Otherwise you are only ever testing one generation of txs.

Thanks for your advice. You mean we'd better consider parent relationships when constructing transactions even they are not completely valid? I have changed the code to keep transactions (actually CTransactionRef) in a set, from which prevout will be picked for later inputs. However, now it has two differences compared to tx_pool_standard target.

• tx_pool_standard keep a set of outpoints, while I keep transactions
• tx_pool_standard fill the outpoints initially by MineBlock results, while I construct initial transactions using random hashes.

I am not sure which strategy is better.

I think a set of outpoints is better. In your current approach you create first_tx -> (second tx) -> (third tx) ... This is a plain chain. Ideally there are some more complicated graphs.

I think a basic testing setup (args and logging) is sufficient. No need for a chain here in this simple test.

I also want to keep the setup minimal. The chain used here is to construct the first tx by calling chainman->GetParams().GenesisBlock().vtx[0], maybe I should just construct it manually instead of getting it from the genesis block.

Yeah, I think it might be preferable to just construct it manually. However, if you switch to an outpoints approach, you'll probably need to create a few outpoints manually instead.

Please keep the MakeNoLogFileContext in init. It is not strictly needed, but I think it is nice to have to have a logger and argsmanager initialized for testing.

The reason is that they are currently globals, so they may be used at any time during runtime or in future code changes without the fuzz test noticing. And if they are used, we want them to be initialized for testing and not accidentally corrupt the main datadir (or cause OOMs) or other bugs.

I think you can just create a few outpoints by calling the COutPoint constructor and passing a txid of 0 or 1 or so. This should be so cheap that it doesn't have to be done in the global setup, but can be done local in the fuzz target itself.

nit: I think this is no longer needed?

Is this needed right now?

DEFAULT_MAX_ORPHAN_TRANSACTIONS is defined in net_processing.h

            // pick unique outpoints from outpoints as input

nit

                tx_mut.vout.emplace_back(CAmount{}, CScript{});

nit: No need for any script

why?

The loop are used to fill the tx's vout, you mean it is not necessary since we don't have any code that verifies content of vout? Should we replace it with tx.vout.resize(num_out) or just keep vout empty?

Oh, I meant why it is needed or what the goal is to restore previously removed outpoints

The comment actually refers to the loop below.

// restore previously removed outpoints
            for (auto& in : tx_mut.vin) {
                outpoints.insert(in.prevout);
            }

Since we want outpoints used by vin to be unique, whenever an outpoint is used, it is erased from the set temporarily. After vin is constructed, we insert them back to the sets. The logic and the comment here is the same as tx_pool_standard target https://github.com/bitcoin/bitcoin/blob/master/src/test/fuzz/tx_pool.cpp#L221-L224

This is because the tx_pool_standard target does the accounting later on, depending on whether the tx was accepted or not https://github.com/bitcoin/bitcoin/blob/cc22bd7f708fc3f5e793bf0138cd340f71c0feb9/src/test/fuzz/tx_pool.cpp#L296

However, your fuzz target does not have a concept of "rejected" transactions right now. Does it?

If you want to "restore" the outpoints, it might be better to not delete them in the first place.

Thanks for your explanation. There is no "rejected" transaction right now. The outpoint is "deleted" from the set whenever it is picked as an input of the tx to ensure it will not be selected again. Once the construction of the tx is finished, all "deleted" transactions, which are exactly the inputs of the constructed tx, are "recovered". All the process happens within the construction of tx.

So it seems has nothing to do with the later accounting which is considered in tx_pool_standard.

        LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10 * DEFAULT_MAX_ORPHAN_TRANSACTIONS)

nit: I think this can be larger, unless it takes a long time?

There are two LIMITED_WHILE loops in the file, the outer loop determines how many transactions can be constructed, and the inner loop (the one you suggested) determines how many times can TxOrphange methods be triggered. I am not sure about the exact value to be set. I think it can be bigger, though the probability of actually reaching the limit may be very low.

could assert that the return value is equal to the one of HaveTx here?

could assert that the return value of HaveTx is true here?

could assert that the return value of HaveTx is false here?

Could assert that the new size is less than the passed value?

I think this might be better as std::vector, to get a more stable, predictable sorting

vector is better if we only want to add outpoints to the end, but it will be slow if we want to randomly delete elements.

Ah, I see. I think you can also use the std::swap(*pop, vec.back()) and then vec.pop_back() to achieve deletion in O(1), which should be faster than deletion in std::set?

is this needed?

I think BasicTestingSetup should be enough

Is this needed?

I think you'll need to use SetMockTime throughout the test to expire txs

Also there is a non-deterministic FastRandomContext in this function, but I guess it won't be possible to fix that without touching non-fuzz code.

I am thinking that it might be interesting to fuzz duplicate inputs?

Maybe a bool (determined at the beginning of the fuzz input) can indicate whether this run may have duplicate inputs in txs or not?

I find most targets set mocktime at the beginning so I put it here. How can we achieve better coverage by controlling mocktime/expiry?

This will just set it once and keep it constant. To change it you'd have to set it in the loop below

FUZZ_TARGET_INIT(txorphanage, initialize_orphanage)

Maybe rename the file and target to txorphanage?

Sure. orphanage is not so explicit. But the source file has the same name txorphanage.cpp, is txorphan better?

nit: I ran iwyu on this to add missing includes. Feel free to pick:

diff --git a/ci/test/06_script_b.sh b/ci/test/06_script_b.sh
index bdb68e0f6..32f0ea5e4 100755
--- a/ci/test/06_script_b.sh
+++ b/ci/test/06_script_b.sh
@@ -46,6 +46,7 @@ if [ "${RUN_TIDY}" = "true" ]; then
           " src/policy/settings.cpp"\
           " src/rpc/fees.cpp"\
           " src/rpc/signmessage.cpp"\
+          " src/test/fuzz/txorphan.cpp"\
           " -p . ${MAKEJOBS} -- -Xiwyu --cxx17ns -Xiwyu --mapping_file=${BASE_BUILD_DIR}/bitcoin-$HOST/contrib/devtools/iwyu/bitcoin.core.imp"
 fi
 
diff --git a/src/test/fuzz/txorphan.cpp b/src/test/fuzz/txorphan.cpp
index 8a39ea685..d318baa6a 100644
--- a/src/test/fuzz/txorphan.cpp
+++ b/src/test/fuzz/txorphan.cpp
@@ -2,12 +2,27 @@
 // Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
+#include <consensus/amount.h>
+#include <net.h>
 #include <net_processing.h>
+#include <primitives/transaction.h>
+#include <script/script.h>
+#include <sync.h>
 #include <test/fuzz/FuzzedDataProvider.h>
 #include <test/fuzz/fuzz.h>
 #include <test/fuzz/util.h>
 #include <test/util/setup_common.h>
 #include <txorphanage.h>
+#include <uint256.h>
+#include <util/check.h>
+#include <util/time.h>
+
+#include <algorithm>
+#include <cstdint>
+#include <memory>
+#include <set>
+#include <utility>
+#include <vector>
 
 void initialize_orphanage()
 {

For reference the output was:

test/fuzz/txorphan.cpp should add these lines:
#include <stdint.h>                        // for uint32_t, uint8_t
#include <algorithm>                       // for max
#include <memory>                          // for __shared_ptr_access, opera...
#include <set>                             // for set
#include <utility>                         // for swap, pair
#include <vector>                          // for vector
#include "consensus/amount.h"              // for CAmount
#include "net.h"                           // for NodeId
#include "primitives/transaction.h"        // for COutPoint, CTxIn, CTxOut
#include "script/script.h"                 // for CScript
#include "sync.h"                          // for LOCK, WITH_LOCK
#include "uint256.h"                       // for uint256
#include "util/check.h"                    // for inline_assertion_check
#include "util/time.h"                     // for SetMockTime