fuzz, coinselection: Assertion 'result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0' failed #28918

$ echo "PACVlVuVlZWVlZUE3pUAANNRAFEA09NRUb9RUVFR/wD/AP//AP8AWwD//wcErq6urv///////wD/4wAAAAD4a9cA////ra2tra2tra2tra2VlZWVMGA5OTk5OZWVlZWVlZWVlZWVlZWVlYUVJwyq6wEAlZWblZWVlZWVlZWVlZWVlZWblZWVlZWVlZWVlZWV//+V/5WV/////z4AAAAALAtfAgAAX/8=" | base64 --decode > coinselection-d97eed2ff63da56af72c8c858c560a7c6f2aef45.crash
$ FUZZ=coinselection ./src/test/fuzz/fuzz coinselection-d97eed2ff63da56af72c8c858c560a7c6f2aef45.crash
INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 1899726424
INFO: Loaded 1 modules   (570172 inline 8-bit counters): 570172 [0x55dfa99a29a0, 0x55dfa9a2dcdc), 
INFO: Loaded 1 PC tables (570172 PCs): 570172 [0x55dfa9a2dce0,0x55dfaa2e10a0), 
/workdir/fuzz_bins/fuzz_libfuzzer: Running 1 inputs 1 time(s) each.
Running: /workdir/crashes/crash-d97eed2ff63da56af72c8c858c560a7c6f2aef45
fuzz_libfuzzer: wallet/test/fuzz/coinselection.cpp:121: void wallet::coinselection_fuzz_target(FuzzBufferType): Assertion `result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0' failed.
==482== ERROR: libFuzzer: deadly signal
    [#0](/bitcoin-bitcoin/0/) 0x55dfa8279c88 in __sanitizer_print_stack_trace (/workdir/fuzz_bins/fuzz_libfuzzer+0x149ec88) (BuildId: 2b223d93a9bf2ebca89c11d8baf07b3113f0c65f)
    [#1](/bitcoin-bitcoin/1/) 0x55dfa825104c in fuzzer::PrintStackTrace() crtstuff.c
    [#2](/bitcoin-bitcoin/2/) 0x55dfa8236e67 in fuzzer::Fuzzer::CrashCallback() crtstuff.c
    [#3](/bitcoin-bitcoin/3/) 0x7fadb47b050f  (/lib/x86_64-linux-gnu/libc.so.6+0x3c50f) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
    [#4](/bitcoin-bitcoin/4/) 0x7fadb47fe0fb  (/lib/x86_64-linux-gnu/libc.so.6+0x8a0fb) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
    [#5](/bitcoin-bitcoin/5/) 0x7fadb47b0471 in raise (/lib/x86_64-linux-gnu/libc.so.6+0x3c471) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
    [#6](/bitcoin-bitcoin/6/) 0x7fadb479a4b1 in abort (/lib/x86_64-linux-gnu/libc.so.6+0x264b1) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
    [#7](/bitcoin-bitcoin/7/) 0x7fadb479a3d4  (/lib/x86_64-linux-gnu/libc.so.6+0x263d4) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
    [#8](/bitcoin-bitcoin/8/) 0x7fadb47a93a1 in __assert_fail (/lib/x86_64-linux-gnu/libc.so.6+0x353a1) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
    [#9](/bitcoin-bitcoin/9/) 0x55dfa8283267 in wallet::coinselection_fuzz_target(Span<unsigned char const>) coinselection.cpp
    [#10](/bitcoin-bitcoin/10/) 0x55dfa864b487 in LLVMFuzzerTestOneInput fuzz.cpp
    [#11](/bitcoin-bitcoin/11/) 0x55dfa8238334 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) crtstuff.c
    [#12](/bitcoin-bitcoin/12/) 0x55dfa8221263 in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) crtstuff.c
    [#13](/bitcoin-bitcoin/13/) 0x55dfa8226e86 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) crtstuff.c
    [#14](/bitcoin-bitcoin/14/) 0x55dfa82519d6 in main crtstuff.c
    [#15](/bitcoin-bitcoin/15/) 0x7fadb479b6c9  (/lib/x86_64-linux-gnu/libc.so.6+0x276c9) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
    [#16](/bitcoin-bitcoin/16/) 0x7fadb479b784 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x27784) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
    [#17](/bitcoin-bitcoin/17/) 0x55dfa821bcd0 in _start (/workdir/fuzz_bins/fuzz_libfuzzer+0x1440cd0) (BuildId: 2b223d93a9bf2ebca89c11d8baf07b3113f0c65f)

NOTE: libFuzzer has rudimentary signal handlers.
      Combine libFuzzer with AddressSanitizer or similar for better crash reports.
SUMMARY: libFuzzer: deadly signal

Relevant discussion: #28372, #28372 (comment), #28395, #28395#pullrequestreview-1651973742

@murchandamus @furszy @brunoerg what's the status on this?

Whatever is done here, at some point something needs to be done on the 26.x branch to avoid a failing CI.

The latest state is #28395#pullrequestreview-1651973742. I could tackle it if @murchandamus is busy with something else.

So, if the problem is SFFO, can we fix fuzz by doing:

diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
index 4caf96b18d..1e040fb5e2 100644
--- a/src/wallet/test/fuzz/coinselection.cpp
+++ b/src/wallet/test/fuzz/coinselection.cpp
@@ -116,12 +116,14 @@ FUZZ_TARGET(coinselection)
     }
 
     // Run coinselection algorithms
-    auto result_bnb = 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->GetSelectedValue() >= target);
-        (void)result_bnb->GetShuffledInputVector();
-        (void)result_bnb->GetInputSet();
+    if (!subtract_fee_outputs) {
+        auto result_bnb = 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->GetSelectedValue() >= target);
+            (void)result_bnb->GetShuffledInputVector();
+            (void)result_bnb->GetInputSet();
+        }
     }

I don't think that hide issues under the carpet is a good path to follow.

I don't think that hide issues under the carpet is a good path to follow.

Correct me if I'm wrong. In #28395#pullrequestreview-1651973742, isn't the solution that we will adopt to disable BnB when SFFO is enabled? I was wondering whether we would end up touching the fuzz doing that.

I don't think that hide issues under the carpet is a good path to follow.

Correct me if I'm wrong. In #28395 (review), isn't the solution that we will adopt to disable BnB when SFFO is enabled? I was wondering whether we would end up touching the fuzz doing that.

Yes. We need to tackle both aspects in the same PR (wallet and fuzz test). Skipping BnB only in the test side would hide the unexpected behavior; no other test would fail because of this. I believe Murch haven't tackled it yet because the coin selection unit tests require further changes. But it is just a guess.

Yeah, a bunch of coin selection tests break when you stop running BnB while SFFO is active, since a lot of tests made use of SFFO as a crutch to avoid needing to consider the fee of inputs compared to the target. Since there are exist some other issues with the coinselector_tests anyway, I decided to clean up the coinselector_tests in combination with implementing the avoidance of changeless solutions when SFFO is being used.

This is my draft PR: https://github.com/bitcoin/bitcoin/pull/28985

Removed from the 26.0 milestone. #28985 looks a bit large to backport, so I guess the fuzz target will be disabled on 26.x and the issue remains?

will be disabled on 26.x and the issue remains?

Yea, #28985 just arrived way to late for 26.0, and it's still draft, tests failing, no review yet etc. I agree that as-is, it looks too big to backport, maybe it can be done in a way where there is 1 or 2 commits that can be cleanly cherry-picked to fix the issue in the release branch.

will be disabled on 26.x and the issue remains?

Yea, #28985 just arrived way to late for 26.0, and it's still draft, tests failing, no review yet etc. I agree that as-is, it looks too big to backport, maybe it can be done in a way where there is 1 or 2 commits that can be cleanly cherry-picked to fix the issue in the release branch.

Could cherry-pick the bugfix (a38f5856edaf843cf25e8dead1c96f93daea77a4), the bugfix test (aa3b971320ee7b0c8effd105681709f18f07eb63, 0bae09423676f6be8428d90aa582468dde54eefc, bac2e06e7760491c572bd762de3a4411f456c3b9) and make an extra commit (one line) skipping BnB at the fuzzing test.

The rest of the stuff Murch is doing there is to add a SFFO assertion inside BnB. Which could be done later.

Sure, go ahead!

This is still broken, please reopen:

$ echo "AQ0N0NfM0B7QEK1AL3m3AJWVlQAAgQAAAAAAlZWVAACBAAAAAACVlZUAAAAAAAAAAAAAAAAAXQAAgQAAAAAAAAAAAAAA" | base64 --decode > coinselection-90005214eeb91a419ca37def8d958bf6bb670edf.crash
$ FUZZ=coinselection ./src/test/fuzz/fuzz coinselection-90005214eeb91a419ca37def8d958bf6bb670edf.crash
fuzz_libfuzzer: wallet/test/fuzz/coinselection.cpp:122: void wallet::coinselection_fuzz_target(FuzzBufferType): Assertion `result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0' failed.

This is still broken, please reopen:

$ echo "AQ0N0NfM0B7QEK1AL3m3AJWVlQAAgQAAAAAAlZWVAACBAAAAAACVlZUAAAAAAAAAAAAAAAAAXQAAgQAAAAAAAAAAAAAA" | base64 --decode > coinselection-90005214eeb91a419ca37def8d958bf6bb670edf.crash
$ FUZZ=coinselection ./src/test/fuzz/fuzz coinselection-90005214eeb91a419ca37def8d958bf6bb670edf.crash
fuzz_libfuzzer: wallet/test/fuzz/coinselection.cpp:122: void wallet::coinselection_fuzz_target(FuzzBufferType): Assertion `result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0' failed.

Cool. Thats another issue. SFFO disabled.

First glance, the solution is to calculate the minimum viable change in the same way we do inside the wallet (not setting it randomly as we currently do) and provide it to GetChange() instead of providing cost_of_change. There is more information about this inside the long convo Murch and I had on #28395#pullrequestreview-1620951490.

The issue arises when cost_of_change <= selected_value - target. Because we provide the cost of creating change as the minimum viable change for GetChange() inside the test.

IIRC, #28372 is already doing the correction. So.. cc @brunoerg to revive the PR and finish it.

I think that this should be fixed with the merge of #28372