Skip to content

Conversation

@chinggg
Copy link
Contributor

@chinggg chinggg commented Aug 4, 2022

This draft PR can test package processing by creating package (vector of tx with ordered parents-childs relationship) instead of single tx in tx_pool_standard fuzz target.

maflcko#78 has provided a draft for structural change, I only need to modify the anonymous function to create package. The basic idea is similar to

// construct transaction
const CTransactionRef tx = [&] {
CMutableTransaction tx_mut;
const auto num_in = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, outpoints.size());
const auto num_out = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, outpoints.size());
// pick unique outpoints from outpoints as input
for (uint32_t i = 0; i < num_in; i++) {
auto& prevout = PickValue(fuzzed_data_provider, outpoints);
tx_mut.vin.emplace_back(prevout);
// pop the picked outpoint if duplicate input is not allowed
if (!duplicate_input) {
std::swap(prevout, outpoints.back());
outpoints.pop_back();
}
}
// output amount will not affect txorphanage
for (uint32_t i = 0; i < num_out; i++) {
tx_mut.vout.emplace_back(CAmount{0}, CScript{});
}
// restore previously poped outpoints
for (auto& in : tx_mut.vin) {
outpoints.push_back(in.prevout);
}
const auto new_tx = MakeTransactionRef(tx_mut);
// add newly constructed transaction to outpoints
for (uint32_t i = 0; i < num_out; i++) {
outpoints.emplace_back(new_tx->GetHash(), i);
}
return new_tx;
}();
, where we create tx from initial outpoints, then keep adding outs of newly constructed tx to outpoints in the loop. Since we want a package here, all new txs will be stored in a vector. The package should be valid since we don't have any orphan tx with dangling input, though we can consume a bool from fuzz_data_provider to invalidate the package order by swapping some txs.

Copy link
Member

@glozow glozow left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Concept ACK based on description, thanks for working on this!

Copy link
Contributor Author

@chinggg chinggg Aug 4, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Now the fuzz target has some shallow bugs. For example, GetAmount fail to get coin value. I guess that's because I simply add newly constructed tx out to outpoints, so CCoinsViewMemPool::GetCoin cannot find the outpoint in mempool.

test/fuzz/tx_pool.cpp:164 operator(): Assertion `amount_view.GetCoin(outpoint, c)' failed.
==3026798== ERROR: libFuzzer: deadly signal
    #0 0x5609ccdba680 in __sanitizer_print_stack_trace (/home/ubuntu/bitcoin/src/test/fuzz/fuzz+0xfd7680)
    #1 0x5609ccd66988 in fuzzer::PrintStackTrace() (/home/ubuntu/bitcoin/src/test/fuzz/fuzz+0xf83988)
    #2 0x5609ccd4bad3 in fuzzer::Fuzzer::CrashCallback() (/home/ubuntu/bitcoin/src/test/fuzz/fuzz+0xf68ad3)
    #3 0x7f173207341f  (/lib/x86_64-linux-gnu/libpthread.so.0+0x1441f)
    #4 0x7f1731cd900a in __libc_signal_restore_set /build/glibc-SzIz7B/glibc-2.31/signal/../sysdeps/unix/sysv/linux/internal-signals.h:86:3
    #5 0x7f1731cd900a in raise /build/glibc-SzIz7B/glibc-2.31/signal/../sysdeps/unix/sysv/linux/raise.c:48:3
    #6 0x7f1731cb8858 in abort /build/glibc-SzIz7B/glibc-2.31/stdlib/abort.c:79:7
    #7 0x5609cf0fa49d in assertion_fail(char const*, int, char const*, char const*) src/util/check.cpp:13:5
    #8 0x5609cd319c02 in bool&& inline_assertion_check<true, bool>(bool&&, char const*, int, char const*, char const*) src/./util/check.h:67:13
    #9 0x5609cd5cbdda in (anonymous namespace)::tx_pool_standard_fuzz_target(Span<unsigned char const>)::$_4::operator()(COutPoint const&) const src/test/fuzz/tx_pool.cpp:164:9
    #10 0x5609cd5cc62a in (anonymous namespace)::tx_pool_standard_fuzz_target(Span<unsigned char const>)::$_5::operator()() const src/test/fuzz/tx_pool.cpp:198:34

There are at least two different ways to fix the assert:

  • extend the outpoints_* datastructures with the amount and use that directly
  • add a new datastructure to keep track of amounts and modify GetAmount to use that

Copy link
Contributor Author

@chinggg chinggg Aug 5, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This assertion failure is solved in c157a6c, by changing amount_view to be non-const and calling amount_view.PackageAddTransaction(tx); after each tx is constructed.

@fanquake fanquake added the Tests label Aug 4, 2022
Copy link
Contributor Author

@chinggg chinggg Aug 5, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Another bug assert violation happens in insert_tx.

test/fuzz/tx_pool.cpp:308 operator(): Assertion `set.get().emplace(tx.GetHash(), i).second' failed.
==3192931== ERROR: libFuzzer: deadly signal
    #0 0x55c5a9cbf680 in __sanitizer_print_stack_trace (/home/ubuntu/bitcoin/src/test/fuzz/fuzz+0xfd7680)
    #1 0x55c5a9c6b988 in fuzzer::PrintStackTrace() (/home/ubuntu/bitcoin/src/test/fuzz/fuzz+0xf83988)
    #2 0x55c5a9c50ad3 in fuzzer::Fuzzer::CrashCallback() (/home/ubuntu/bitcoin/src/test/fuzz/fuzz+0xf68ad3)
    #3 0x7f666ad8a41f  (/lib/x86_64-linux-gnu/libpthread.so.0+0x1441f)
    #4 0x7f666a9f000a in __libc_signal_restore_set /build/glibc-SzIz7B/glibc-2.31/signal/../sysdeps/unix/sysv/linux/internal-signals.h:86:3
    #5 0x7f666a9f000a in raise /build/glibc-SzIz7B/glibc-2.31/signal/../sysdeps/unix/sysv/linux/raise.c:48:3
    #6 0x7f666a9cf858 in abort /build/glibc-SzIz7B/glibc-2.31/stdlib/abort.c:79:7
    #7 0x55c5abfff51d in assertion_fail(char const*, int, char const*, char const*) src/util/check.cpp:13:5
    #8 0x55c5aa21ec02 in bool&& inline_assertion_check<true, bool>(bool&&, char const*, int, char const*, char const*) src/./util/check.h:67:13
    #9 0x55c5aa4d3759 in auto (anonymous namespace)::tx_pool_standard_fuzz_target(Span<unsigned char const>)::$_1::operator()<CTransaction>(std::vector<std::reference_wrapper<std::set<COutPoint, std::less<COutPoint>, std::allocator<COutPoint> > >, std::allocator<std::reference_wrapper<std::set<COutPoint, std::less<COutPoint>, std::allocator<COutPoint> > > > >, std::vector<std::reference_wrapper<std::set<COutPoint, std::less<COutPoint>, std::allocator<COutPoint> > >, std::allocator<std::reference_wrapper<std::set<COutPoint, std::less<COutPoint>, std::allocator<COutPoint> > > > >, CTransaction const&) const src/test/fuzz/tx_pool.cpp:308:21
    #10 0x55c5aa4cdf0a in (anonymous namespace)::tx_pool_standard_fuzz_target(Span<unsigned char const>) src/test/fuzz/tx_pool.cpp:327:17

https://github.com/bitcoin/bitcoin/blob/master/src/test/fuzz/tx_pool.cpp#L271-L296

I am not sure about what the loops are doing. Maybe outpoint_rbf should not be modified when constructing transactions.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is solved in 6ca7fcf by use a new copy of outpoint_rbf in the loop.

@chinggg chinggg force-pushed the fuzz-pkg branch 2 times, most recently from dfad376 to 6ca7fcf Compare August 6, 2022 01:44
Copy link
Contributor Author

@chinggg chinggg Aug 6, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The assertion result_package.m_tx_results.size() == package.size() failed quickly. I debug the testcase and it seems results.size() < package.size().

test/fuzz/tx_pool.cpp:286 tx_pool_standard_fuzz_target: Assertion `result_package.m_tx_results.size() == package.size()' failed.
==3398073== ERROR: libFuzzer: deadly signal
    #0 0x55e1fcaec680 in __sanitizer_print_stack_trace (/home/ubuntu/bitcoin/src/test/fuzz/fuzz+0xfd8680)
    #1 0x55e1fca98988 in fuzzer::PrintStackTrace() (/home/ubuntu/bitcoin/src/test/fuzz/fuzz+0xf84988)
    #2 0x55e1fca7dad3 in fuzzer::Fuzzer::CrashCallback() (/home/ubuntu/bitcoin/src/test/fuzz/fuzz+0xf69ad3)
    #3 0x7ff789c3741f  (/lib/x86_64-linux-gnu/libpthread.so.0+0x1441f)
    #4 0x7ff78989d00a in __libc_signal_restore_set /build/glibc-SzIz7B/glibc-2.31/signal/../sysdeps/unix/sysv/linux/internal-signals.h:86:3
    #5 0x7ff78989d00a in raise /build/glibc-SzIz7B/glibc-2.31/signal/../sysdeps/unix/sysv/linux/raise.c:48:3
    #6 0x7ff78987c858 in abort /build/glibc-SzIz7B/glibc-2.31/stdlib/abort.c:79:7
    #7 0x55e1fee2dc3d in assertion_fail(char const*, int, char const*, char const*) src/util/check.cpp:13:5
    #8 0x55e1fd04bc02 in bool&& inline_assertion_check<true, bool>(bool&&, char const*, int, char const*, char const*) src/./util/check.h:67:13
    #9 0x55e1fd2f9f0b in (anonymous namespace)::tx_pool_standard_fuzz_target(Span<unsigned char const>) src/test/fuzz/tx_pool.cpp:286:17

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ok, that is probably my fault. I wrote the fuzz code without reading the validation code. I should read more about the interface and the meaning of valid/invalid in the context of packages. Apparently we can't deduce any meaningful information useful for fuzzing from the result. So for now I'd suggest to remove the failing Asserts.

Moreover, the "tracking" code seems not prepared for packages. I think it can be fixed by tracking the history of added/removed transactions chronologically. (That is, switching the two std::set into one std::vector)

See this diff:

diff --git a/src/test/fuzz/tx_pool.cpp b/src/test/fuzz/tx_pool.cpp
index c38e3420f6..b01b4f978a 100644
--- a/src/test/fuzz/tx_pool.cpp
+++ b/src/test/fuzz/tx_pool.cpp
@@ -70,6 +70,24 @@ struct TransactionsDelta final : public CValidationInterface {
     }
 };
 
+struct TransactionsHistory final : public CValidationInterface {
+    std::vector<std::tuple<bool, CTransactionRef>>& m_history;
+
+    explicit TransactionsHistory(std::vector<std::tuple<bool, CTransactionRef>>& h)
+        : m_history{h} {}
+
+    void TransactionAddedToMempool(const CTransactionRef& tx, uint64_t /* mempool_sequence */) override
+    {
+        m_history.emplace_back(true, tx);
+    }
+
+    void TransactionRemovedFromMempool(const CTransactionRef& tx, MemPoolRemovalReason reason, uint64_t /* mempool_sequence */) override
+    {
+        if (reason != MemPoolRemovalReason::SIZELIMIT)
+            m_history.emplace_back(false, tx);
+    }
+};
+
 void SetMempoolConstraints(ArgsManager& args, FuzzedDataProvider& fuzzed_data_provider)
 {
     args.ForceSetArg("-limitancestorcount",
@@ -247,9 +265,8 @@ FUZZ_TARGET_INIT(tx_pool_standard, initialize_tx_pool)
         }
 
         // Remember all removed and added transactions
-        std::set<CTransactionRef> removed;
-        std::set<CTransactionRef> added;
-        auto txr = std::make_shared<TransactionsDelta>(removed, added);
+        std::vector<std::tuple<bool, CTransactionRef>> history;
+        auto txr = std::make_shared<TransactionsHistory>(history);
         RegisterSharedValidationInterface(txr);
         const bool bypass_limits = fuzzed_data_provider.ConsumeBool();
 
@@ -283,7 +300,6 @@ FUZZ_TARGET_INIT(tx_pool_standard, initialize_tx_pool)
                 }
             }
             if (accepted) {
-                Assert(result_package.m_tx_results.size() == package.size());
                 for (const auto& tx_res : result_package.m_tx_results) {
                     Assert(tx_res.second.m_result_type == MempoolAcceptResult::ResultType::VALID);
                 }
@@ -291,15 +307,6 @@ FUZZ_TARGET_INIT(tx_pool_standard, initialize_tx_pool)
         }
         SyncWithValidationInterfaceQueue();
         UnregisterSharedValidationInterface(txr);
-        Assert(accepted != added.empty());
-        if (accepted) {
-            Assert(Package(added.begin(), added.end()) == package);
-        } else {
-            // Do not consider rejected transactions removed
-            for (const auto& tx : package) {
-                removed.erase(tx);
-            }
-        }
 
         // Helper to insert spent and created outpoints of a tx into collections
         using Sets = std::vector<std::reference_wrapper<std::set<COutPoint>>>;
@@ -317,16 +324,17 @@ FUZZ_TARGET_INIT(tx_pool_standard, initialize_tx_pool)
         };
         // Add created outpoints, remove spent outpoints
         {
+            for (const auto& [added,tx]:history){
             // Outpoints that no longer exist at all
             std::set<COutPoint> consumed_erased;
             // Outpoints that no longer count toward the total supply
             std::set<COutPoint> consumed_supply;
-            for (const auto& removed_tx : removed) {
-                insert_tx(/*created_by_tx=*/{consumed_erased}, /*consumed_by_tx=*/{outpoints_supply}, /*tx=*/*removed_tx);
-            }
-            for (const auto& added_tx : added) {
-                insert_tx(/*created_by_tx=*/{outpoints_supply, outpoints_rbf}, /*consumed_by_tx=*/{consumed_supply}, /*tx=*/*added_tx);
+            if (added) {
+                insert_tx(/*created_by_tx=*/{outpoints_supply, outpoints_rbf}, /*consumed_by_tx=*/{consumed_supply}, /*tx=*/*tx);
+            } else {
+                insert_tx(/*created_by_tx=*/{consumed_erased}, /*consumed_by_tx=*/{outpoints_supply}, /*tx=*/*tx);
             }
+
             for (const auto& p : consumed_erased) {
                 Assert(outpoints_supply.erase(p) == 1);
                 Assert(outpoints_rbf.erase(p) == 1);
@@ -334,6 +342,7 @@ FUZZ_TARGET_INIT(tx_pool_standard, initialize_tx_pool)
             for (const auto& p : consumed_supply) {
                 Assert(outpoints_supply.erase(p) == 1);
             }
+            }
         }
     }
     Finish(fuzzed_data_provider, tx_pool, chainstate);

However, now I am running into an assert in validation, which might be an actual bug 🥲

Copy link
Contributor Author

@chinggg chinggg Aug 12, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Sorry for the late response, your diff is applied in 08e5172, with some formatting changes by clangd. I will try to find the reason of crash in validation.cpp:414: bool CheckInputsFromMempoolAndCache(const CTransaction &, TxValidationState &, const CCoinsViewCache &, const CTxMemPool &, unsigned int, PrecomputedTransactionData &, CCoinsViewCache &): Assertion !coinFromUTXOSet.IsSpent()' failed. It happens after 3 continues on breakpoint tx_pool.cpp:291

#10 0x5634390f86ad in CheckInputsFromMempoolAndCache(CTransaction const&, TxValidationState&, CCoinsViewCache const&, CTxMemPool const&, unsigned int, PrecomputedTransactionData&, CCoinsViewCache&) src/./src/validation.cpp:414:13
#11 0x5634390f4729 in (anonymous namespace)::MemPoolAccept::ConsensusScriptChecks((anonymous namespace)::MemPoolAccept::ATMPArgs const&, (anonymous namespace)::MemPoolAccept::Workspace&) src/./src/validation.cpp:1040:10
#12 0x563439100255 in (anonymous namespace)::MemPoolAccept::SubmitPackage((anonymous namespace)::MemPoolAccept::ATMPArgs const&, std::vector<(anonymous namespace)::MemPoolAccept::Workspace, std::allocator<(anonymous namespace)::MemPoolAccept::Workspace> >&, PackageValidationState&, std::map<uint256 const, MempoolAcceptResult const, std::less<uint256 const>, std::allocator<std::pair<uint256 const, MempoolAcceptResult const> > >&) src/./src/validation.cpp:1112:14
#13 0x5634390fc3ee in (anonymous namespace)::MemPoolAccept::AcceptMultipleTransactions(std::vector<std::shared_ptr<CTransaction const>, std::allocator<std::shared_ptr<CTransaction const> > > const&, (anonymous namespace)::MemPoolAccept::ATMPArgs&) src/./src/validation.cpp:1273:10
#14 0x5634390fe435 in (anonymous namespace)::MemPoolAccept::AcceptPackage(std::vector<std::shared_ptr<CTransaction const>, std::allocator<std::shared_ptr<CTransaction const> > > const&, (anonymous namespace)::MemPoolAccept::ATMPArgs&) src/./src/validation.cpp:1404:30
#15 0x5634390a201c in ProcessNewPackage(CChainState&, CTxMemPool&, std::vector<std::shared_ptr<CTransaction const>, std::allocator<std::shared_ptr<CTransaction const> > > const&, bool)::$_2::operator()() const src/./src/validation.cpp:1458:59
#16 0x5634390a187f in ProcessNewPackage(CChainState&, CTxMemPool&, std::vector<std::shared_ptr<CTransaction const>, std::allocator<std::shared_ptr<CTransaction const> > > const&, bool) src/./src/validation.cpp:1451:25
#17 0x5634385288a5 in (anonymous namespace)::tx_pool_standard_fuzz_target(Span<unsigned char const>)::$_7::operator()() const src/./src/test/fuzz/tx_pool.cpp:291:39

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The crash happens when one of the tx finally get passed into CheckInputsFromMempoolAndCache, it assume that the tx is either a UTXO from mempool or UTXO set. The assert fails because coinFromUTXOSet is actually coinEmpty.

@DrahtBot
Copy link
Contributor

DrahtBot commented Sep 23, 2022

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
Concept ACK glozow

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

  • #26758 (clang-tidy: Add performance-no-automatic-move check by hebasto)
  • #26642 (clang-tidy: Add more performance-* checks and related fixes by hebasto)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

@fanquake
Copy link
Member

fanquake commented Dec 5, 2022

@chinggg are you planning on following up with the build failures here?

/usr/bin/ccache clang++ -ftrivial-auto-var-init=pattern -std=c++17 -DHAVE_CONFIG_H -I. -I../src/config  -DABORT_ON_FAILED_ASSUME -fmacro-prefix-map=/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu=. -U_FORTIFY_SOURCE -D_FORTIFY_SOURCE=2 -DHAVE_BUILD_INFO -I. -I./minisketch/include -I./secp256k1/include -I./univalue/include  -I./leveldb/include  -fdebug-prefix-map=/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu=. -Wstack-protector -fstack-protector-all -fcf-protection=full -fstack-clash-protection -Wall -Wextra -Wgnu -Wformat -Wformat-security -Wvla -Wshadow-field -Wthread-safety -Wrange-loop-analysis -Wredundant-decls -Wunused-member-function -Wdate-time -Wconditional-uninitialized -Woverloaded-virtual -Wsuggest-override -Wunreachable-code-loop-increment -Wimplicit-fallthrough -Wdocumentation -Wno-unused-parameter -Wno-self-assign -Werror  -fsanitize=fuzzer,address,undefined,integer   -fPIE -g -O2 -c -o test/fuzz/fuzz-tx_pool.o `test -f 'test/fuzz/tx_pool.cpp' || echo './'`test/fuzz/tx_pool.cpp
test/fuzz/tx_pool.cpp:59:14: error: unused member function 'TransactionsDelta' [-Werror,-Wunused-member-function]
    explicit TransactionsDelta(std::set<CTransactionRef>& r, std::set<CTransactionRef>& a)
             ^
1 error generated.
make[2]: *** [Makefile:16988: test/fuzz/fuzz-tx_pool.o] Error 1

@maflcko
Copy link
Member

maflcko commented Dec 5, 2022

I think the build failures can be fixed, but then there will be fuzz failures and I never got around to fully debug this, as the package stuff is still being worked on as we speak

@chinggg
Copy link
Contributor Author

chinggg commented Dec 6, 2022

@fanquake Sorry for the late reply. I just built this code with ./configure --enable-debug --enable-fuzz --with-gui=no and my compiler (clang++ 15) recognized this unused member function 'TransactionsDelta' as a warning instead of an error.
For the completion of this PR, we might wait for the progress of the new package relay feature. The original BIP PR bitcoin/bips#1324 has been closed and it seems "the updated proposal is going to be significantly different"

@fanquake
Copy link
Member

fanquake commented Dec 6, 2022

Ok. Should we close this for now then, and reopen when we actually know what we have to fuzz?

@DrahtBot
Copy link
Contributor

🐙 This pull request conflicts with the target branch and needs rebase.

@DrahtBot
Copy link
Contributor

There hasn't been much activity lately and the patch still needs rebase. What is the status here?

  • Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
  • Is it no longer relevant? ➡️ Please close.
  • Did the author lose interest or time to work on this? ➡️ Please close it and mark it 'Up for grabs' with the label, so that it can be picked up in the future.

1 similar comment
@DrahtBot
Copy link
Contributor

There hasn't been much activity lately and the patch still needs rebase. What is the status here?

  • Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
  • Is it no longer relevant? ➡️ Please close.
  • Did the author lose interest or time to work on this? ➡️ Please close it and mark it 'Up for grabs' with the label, so that it can be picked up in the future.

@maflcko
Copy link
Member

maflcko commented Jul 10, 2023

Closing for now. Maybe this can be picked up as part of one of the package relay PRs.

@maflcko maflcko closed this Jul 10, 2023
@chinggg
Copy link
Contributor Author

chinggg commented Jul 13, 2023

I am not sure if the package relay features have been implemented. Feel free to reach out to me if there is need to continue the development of this fuzz target.

@bitcoin bitcoin locked and limited conversation to collaborators Sep 13, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants