Skip to content

Conversation

brunoerg
Copy link
Contributor

Instead of "randomly" fuzzing min_viable_change and change_output_size, and since they're correlated, this PR changes the approach to fuzz them according to the logic in CreateTransactionInternal.

@DrahtBot
Copy link
Contributor

DrahtBot commented Aug 30, 2023

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 furszy, murchandamus, achow101

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

Conflicts

No conflicts as of last run.

@DrahtBot DrahtBot added the Tests label Aug 30, 2023
Comment on lines 108 to 105
coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
coin_params.m_cost_of_change = coin_params.m_change_fee + coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size);
const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)};
coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
Copy link
Contributor

Choose a reason for hiding this comment

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

I was pondering whether the input size being rolled randomly and the dust being only based on the output type could lead to min_viable_change being smaller than cost_of_change - change_fee, but this seems right to me now. 🤔

Approach ACK, will throw into my fuzzer for a while.

Comment on lines 77 to 82
static CTxOut GetChangePrototypeTxout(FuzzedDataProvider& fuzzed_data_provider)
{
const CTxDestination tx_destination{ConsumeTxDestination(fuzzed_data_provider)};
CScript script_change{GetScriptForDestination(tx_destination)};
return CTxOut(0, script_change);
}
Copy link
Contributor

Choose a reason for hiding this comment

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

This will narrow down the range of output sizes being fuzzed.

An alternative would perhaps be to randomly roll change output size and change input size, while calculating all the other derived values from those, but my gut says that there shouldn’t be all that much exciting happening anyway. Will revisit this question when I’ve fuzzed a bit.

Copy link
Contributor Author

Choose a reason for hiding this comment

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

Did you revisit it?

Copy link
Member

Choose a reason for hiding this comment

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

This will narrow down the range of output sizes being fuzzed.

Agree.
You don't need to create valid known destinations, we only care about the change output size. All yours:

diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
--- a/src/wallet/test/fuzz/coinselection.cpp	(revision ccb25a1ddc1f79f432a6718604f01ed97dced15f)
+++ b/src/wallet/test/fuzz/coinselection.cpp	(date 1702581796902)
@@ -11,6 +11,7 @@
 #include <test/util/setup_common.h>
 #include <wallet/coinselection.h>
 
+#include <algorithm>
 #include <vector>
 
 namespace wallet {
@@ -74,13 +75,6 @@
     return result;
 }
 
-static CTxOut GetChangePrototypeTxout(FuzzedDataProvider& fuzzed_data_provider)
-{
-    const CTxDestination tx_destination{ConsumeTxDestination(fuzzed_data_provider)};
-    CScript script_change{GetScriptForDestination(tx_destination)};
-    return CTxOut(0, script_change);
-}
-
 // Returns true if the result contains an error and the message is not empty
 static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
 
@@ -101,14 +95,16 @@
     coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
     coin_params.m_long_term_feerate = long_term_fee_rate;
     coin_params.m_effective_feerate = effective_fee_rate;
-    auto change_prototype_txout{GetChangePrototypeTxout(fuzzed_data_provider)};
-    coin_params.change_output_size = GetSerializeSize(change_prototype_txout);
+    coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
     coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
     coin_params.m_discard_feerate = discard_fee_rate;
     coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
     const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
     coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
-    const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)};
+    // We only care about the change output size
+    CScript change_out_script;
+    std::fill_n(change_out_script.begin(), coin_params.change_output_size, OP_TRUE);
+    const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
     coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
 
     int next_locktime{0};

@maflcko
Copy link
Member

maflcko commented Aug 31, 2023

Added milestone, because this is a fuzz blocker

@murchandamus
Copy link
Contributor

murchandamus commented Sep 1, 2023

I found a crash:

fuzz: ../../src/wallet/test/fuzz/coinselection.cpp:130: void wallet::coinselection_fuzz_target(FuzzBufferType): Assertion `result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0' failed.

You can run the crash seed using:

$ echo "FP93w8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8N3d1h3d4h3d3cUAjsTsTsTsTOOd3d3d5t3d3d3WHd3iHd3d3d3d///yZkblPEYAAB3d3d3d3cKJ3d3d////wAyd3d3d3c093d3d3d3dwonAAD/kiEA" | base64 -d > crash.input
$ FUZZ=coinselection src/test/fuzz/fuzz crash.input

@brunoerg
Copy link
Contributor Author

brunoerg commented Sep 2, 2023

@murchandamus The crash happens because GetChange is returning exactly the cost_of_change, instead of 0.

In that crash the m_subtract_fee_outputs is True. So m_use_effective in GetChange is False.

See:

CAmount SelectionResult::GetChange(const CAmount min_viable_change, const CAmount change_fee) const
{
    // change = SUM(inputs) - SUM(outputs) - fees
    // 1) With SFFO we don't pay any fees
    // 2) Otherwise we pay all the fees:
    //  - input fees are covered by GetSelectedEffectiveValue()
    //  - non_input_fee is included in m_target
    //  - change_fee
    const CAmount change = m_use_effective
                           ? GetSelectedEffectiveValue() - m_target - change_fee
                           : GetSelectedValue() - m_target;

    if (change < min_viable_change) {
        return 0;
    }

    return change;
}

I tested m_use_effective with True and the change is 0.

@maflcko
Copy link
Member

maflcko commented Oct 5, 2023

Are you still working on this? What is the current status here?

@furszy
Copy link
Member

furszy commented Oct 5, 2023

Are you still working on this? What is the current status here?

#28395 (review)

@brunoerg
Copy link
Contributor Author

brunoerg commented Oct 5, 2023

Are you still working on this? What is the current status here?

This is just an improvement in the logic and it's not an attempt to fix the crash since it's a real bug in BnB.

@maflcko maflcko removed this from the 26.0 milestone Oct 5, 2023
@maflcko
Copy link
Member

maflcko commented Oct 5, 2023

Ok, removed milestone for now.

Looks like this crashes in any case? #28372 (comment)

So maybe mark as draft for now, while this is not yet ready for review.

@brunoerg brunoerg marked this pull request as draft October 16, 2023 18:13
@brunoerg
Copy link
Contributor Author

Draft while waiting for a fix in BnB

@brunoerg
Copy link
Contributor Author

Rebased

@brunoerg
Copy link
Contributor Author

CI error seems unrelated:

2023-12-13T15:26:02.5983445Z 54/286 - rpc_signer.py failed, Duration: 3 s
2023-12-13T15:26:02.5983915Z 
2023-12-13T15:26:02.5984128Z stdout:
2023-12-13T15:26:02.5985467Z 2023-12-13T15:25:59.249000Z TestFramework (INFO): PRNG seed is: 6112864330657271854
2023-12-13T15:26:02.5986266Z 
2023-12-13T15:26:02.5994148Z 2023-12-13T15:25:59.249000Z TestFramework (INFO): Initializing test directory D:\a\_temp\test_runner_₿_🏃_20231213_151925\rpc_signer_229
2023-12-13T15:26:02.5995453Z 
2023-12-13T15:26:02.5996137Z 2023-12-13T15:26:00.333000Z TestFramework (ERROR): Assertion failed
2023-12-13T15:26:02.5996821Z 
2023-12-13T15:26:02.5997101Z Traceback (most recent call last):
2023-12-13T15:26:02.5997578Z 
2023-12-13T15:26:02.5998332Z   File "D:\a\bitcoin\bitcoin\test\functional\test_framework\test_framework.py", line 556, in start_nodes
2023-12-13T15:26:02.5999355Z 
2023-12-13T15:26:02.5999728Z     node.wait_for_rpc_connection()
2023-12-13T15:26:02.6000194Z 
2023-12-13T15:26:02.6001027Z   File "D:\a\bitcoin\bitcoin\test\functional\test_framework\test_node.py", line 249, in wait_for_rpc_connection
2023-12-13T15:26:02.6002062Z 
2023-12-13T15:26:02.6002391Z     raise FailedToStartError(self._node_msg(
2023-12-13T15:26:02.6002931Z 
2023-12-13T15:26:02.6005067Z test_framework.test_node.FailedToStartError: [node 1] bitcoind exited with status 1 during initialization. Error: Error parsing command line arguments: Invalid parameter -signer=py -3 D:\a\bitcoin\bitcoin\test\functional\mocks\signer.py

@murchandamus
Copy link
Contributor

Just kicked off 10×10h of fuzzing, will take a look tomorrow

@murchandamus
Copy link
Contributor

Most of them, but not all crashed on this:

#626233 REDUCE cov: 1289 ft: 13823 corp: 4183/16Mb lim: 66076 exec/s: 206 rss: 88Mb L: 157/65635 MS: 1 EraseBytes-
fuzz: ../../src/wallet/test/fuzz/coinselection.cpp:131: void wallet::coinselection_fuzz_target(FuzzBufferType): Assertion `result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0' failed.

I think we might have misdiagnosed the issue, when we thought it could only happen when SFFO is active

Copy link
Member

@furszy furszy left a comment

Choose a reason for hiding this comment

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

I think we might have misdiagnosed the issue, when we thought it could only happen when SFFO is active

@murchandamus. The code here has not fixed the issue I mentioned #28918 (comment).
Need to provide min_viable_change to the BnB result GetChange() function, not cost_of_change. @brunoerg

@brunoerg
Copy link
Contributor Author

Need to provide min_viable_change to the BnB function, not cost_of_change. @brunoerg

Yes, I'm addressing it.

@furszy
Copy link
Member

furszy commented Dec 14, 2023

Yes, I'm addressing it.

Before pushing the changes, can verify them against the issue #28918 (comment).

@brunoerg
Copy link
Contributor Author

brunoerg commented Dec 14, 2023

Also, I think it would be more appropriate if we don't set change_spend_size randomly. Perhaps we could use CalculateMaximumSignedInputSize and the same approach in CreateTransactionInternal.

@murchandamus
Copy link
Contributor

I think it would be fine to roll input and output sizes randomly as long as they remain greater than zero and all the related values are derived from them. E.g. it would be an issue if cost_of_change or min_viable_change were independent of change_spend_size

@brunoerg
Copy link
Contributor Author

Need to provide min_viable_change to the BnB result GetChange() function, not cost_of_change. @brunoerg

Got same crash with it.

diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
index b35bf34db3..5a3250bdd7 100644
--- a/src/wallet/test/fuzz/coinselection.cpp
+++ b/src/wallet/test/fuzz/coinselection.cpp
@@ -128,7 +128,7 @@ FUZZ_TARGET(coinselection)
     auto result_bnb = coin_params.m_subtract_fee_outputs ? util::Error{Untranslated("BnB disabled when SFFO is enabled")} :
                       SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
     if (result_bnb) {
-        assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
+        assert(result_bnb->GetChange(coin_params.min_viable_change, CAmount{0}) == 0);
         assert(result_bnb->GetSelectedValue() >= target);
         (void)result_bnb->GetShuffledInputVector();
         (void)result_bnb->GetInputSet();
echo "//////////////////8AKH4pAAAsICkpAAAAAAgARSwLCwv//////////wsLCwsL                   
Cwt+MPILCwsLCwsLCwsLCwEAAAsHCwsLTJV4CwsLCwsLCwsBAAALCwsLCwsLCwsL
CwsA+f8nAAsLCwsLAf//JgImJtAB/w==" | base64 --decode > coinselection.crash

@murchandamus
Copy link
Contributor

murchandamus commented Dec 14, 2023

It seems to me that the check in line 131 is simply wrong:

assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);

The function definition is CAmount SelectionResult::GetChange(const CAmount min_viable_change, const CAmount change_fee) const

So, instead of passing coin_params.m_cost_of_change and 0, we should be passing coin_params.min_viable_change and coin_params.m_change_fee. Just fixing one or the other was insufficient, but when I replace both all my fuzz crashes pass.

@@ -128,7 +128,7 @@ FUZZ_TARGET(coinselection)
     auto result_bnb = coin_params.m_subtract_fee_outputs ? util::Error{Untranslated("BnB disabled when SFFO is enabled")} :
                       SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
     if (result_bnb) {
-        assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
+        assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);
         assert(result_bnb->GetSelectedValue() >= target);
         (void)result_bnb->GetShuffledInputVector();
         (void)result_bnb->GetInputSet();

@furszy
Copy link
Member

furszy commented Dec 14, 2023

So, instead of passing coin_params.m_cost_of_change and 0, we should be passing coin_params.min_viable_change and coin_params.m_change_fee. Just fixing one or the other was insufficient, but when I replace both all my fuzz crashes pass.

Yeah, thats good.
It is because cost_of_change, the BnB upper bound, includes change_fee while min_viable_change does not.

Copy link
Member

@furszy furszy left a comment

Choose a reason for hiding this comment

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

Left a comment

Comment on lines 77 to 82
static CTxOut GetChangePrototypeTxout(FuzzedDataProvider& fuzzed_data_provider)
{
const CTxDestination tx_destination{ConsumeTxDestination(fuzzed_data_provider)};
CScript script_change{GetScriptForDestination(tx_destination)};
return CTxOut(0, script_change);
}
Copy link
Member

Choose a reason for hiding this comment

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

This will narrow down the range of output sizes being fuzzed.

Agree.
You don't need to create valid known destinations, we only care about the change output size. All yours:

diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
--- a/src/wallet/test/fuzz/coinselection.cpp	(revision ccb25a1ddc1f79f432a6718604f01ed97dced15f)
+++ b/src/wallet/test/fuzz/coinselection.cpp	(date 1702581796902)
@@ -11,6 +11,7 @@
 #include <test/util/setup_common.h>
 #include <wallet/coinselection.h>
 
+#include <algorithm>
 #include <vector>
 
 namespace wallet {
@@ -74,13 +75,6 @@
     return result;
 }
 
-static CTxOut GetChangePrototypeTxout(FuzzedDataProvider& fuzzed_data_provider)
-{
-    const CTxDestination tx_destination{ConsumeTxDestination(fuzzed_data_provider)};
-    CScript script_change{GetScriptForDestination(tx_destination)};
-    return CTxOut(0, script_change);
-}
-
 // Returns true if the result contains an error and the message is not empty
 static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
 
@@ -101,14 +95,16 @@
     coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
     coin_params.m_long_term_feerate = long_term_fee_rate;
     coin_params.m_effective_feerate = effective_fee_rate;
-    auto change_prototype_txout{GetChangePrototypeTxout(fuzzed_data_provider)};
-    coin_params.change_output_size = GetSerializeSize(change_prototype_txout);
+    coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
     coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
     coin_params.m_discard_feerate = discard_fee_rate;
     coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
     const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
     coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
-    const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)};
+    // We only care about the change output size
+    CScript change_out_script;
+    std::fill_n(change_out_script.begin(), coin_params.change_output_size, OP_TRUE);
+    const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
     coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
 
     int next_locktime{0};

@murchandamus
Copy link
Contributor

@@ -128,7 +128,7 @@ FUZZ_TARGET(coinselection)
     auto result_bnb = coin_params.m_subtract_fee_outputs ? util::Error{Untranslated("BnB disabled when SFFO is enabled")} :
                       SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
     if (result_bnb) {
-        assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
+        assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);
         assert(result_bnb->GetSelectedValue() >= target);
         (void)result_bnb->GetShuffledInputVector();
         (void)result_bnb->GetInputSet();

Fuzzed for 1h with that change and got no new crash.

@brunoerg
Copy link
Contributor Author

So, instead of passing coin_params.m_cost_of_change and 0, we should be passing coin_params.min_viable_change and coin_params.m_change_fee. Just fixing one or the other was insufficient, but when I replace both all my fuzz crashes pass.

Cool, I think the 0 came from the way we call ComputeAndSetWaste internally in SelectCoinsBnB.

@brunoerg
Copy link
Contributor Author

brunoerg commented Dec 14, 2023

Thanks, @furszy and @murchandamus. I will address the suggestions and leave it running for some time before pushing.

Just an observation on @furszy's suggestion - I think it will cause stack-buffer-overflow:

-    const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)};
+    // We only care about the change output size
+    CScript change_out_script;
+    std::fill_n(change_out_script.begin(), coin_params.change_output_size, OP_TRUE);
+    const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
 

@furszy
Copy link
Member

furszy commented Dec 14, 2023

Just an observation on @furszy's suggestion - I think it will cause stack-buffer-overflow:

-    const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)};
+    // We only care about the change output size
+    CScript change_out_script;
+    std::fill_n(change_out_script.begin(), coin_params.change_output_size, OP_TRUE);
+    const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};

I coded it on the fly. You can just push the opcodes manually if std::fill_n() doesn't work or correct it in some way. The rationale is to not construct only known destinations as you are doing here. Coin selection doesn't care about them, it just uses the script size.

Change it to use same approach from
`CreateTransactionInternal`.
@brunoerg brunoerg force-pushed the 2023-08-fuzz-coinselection-min-viable-change branch from ccb25a1 to cd81007 Compare December 15, 2023 09:29
@brunoerg
Copy link
Contributor Author

Force-pushed addressing #28372 (comment) and #28372 (comment). Thanks @murchandamus and @furszy for the review!

Left it running for 10h before pushing and did not crash.

Copy link
Member

@furszy furszy left a comment

Choose a reason for hiding this comment

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

Code ACK cd81007

@murchandamus
Copy link
Contributor

ACK cd81007

Passes all my fuzzing crashes and no new crashes with some light additional fuzzing, code LGTM.

@achow101
Copy link
Member

ACK cd81007

@achow101 achow101 merged commit 7524fcf into bitcoin:master Dec 21, 2023
luke-jr pushed a commit to bitcoinknots/bitcoin that referenced this pull request Mar 15, 2024
Change it to use same approach from
`CreateTransactionInternal`.

Github-Pull: bitcoin#28372
Rebased-From: cd81007
luke-jr pushed a commit to bitcoinknots/bitcoin that referenced this pull request Mar 18, 2024
Change it to use same approach from
`CreateTransactionInternal`.

Github-Pull: bitcoin#28372
Rebased-From: cd81007
@bitcoin bitcoin locked and limited conversation to collaborators Dec 20, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
Projects
None yet
Development

Successfully merging this pull request may close these issues.

6 participants