fuzz, coinselection: Assertion 'result_bnb->GetChange(coin_params.m_cost_of

dergoegge commented at 12:58 pm on November 20, 2023: member

 0$ echo "PACVlVuVlZWVlZUE3pUAANNRAFEA09NRUb9RUVFR/wD/AP//AP8AWwD//wcErq6urv///////wD/4wAAAAD4a9cA////ra2tra2tra2tra2VlZWVMGA5OTk5OZWVlZWVlZWVlZWVlZWVlYUVJwyq6wEAlZWblZWVlZWVlZWVlZWVlZWblZWVlZWVlZWVlZWV//+V/5WV/////z4AAAAALAtfAgAAX/8=" | base64 --decode > coinselection-d97eed2ff63da56af72c8c858c560a7c6f2aef45.crash
 1$ FUZZ=coinselection ./src/test/fuzz/fuzz coinselection-d97eed2ff63da56af72c8c858c560a7c6f2aef45.crash
 2INFO: Running with entropic power schedule (0xFF, 100).
 3INFO: Seed: 1899726424
 4INFO: Loaded 1 modules   (570172 inline 8-bit counters): 570172 [0x55dfa99a29a0, 0x55dfa9a2dcdc), 
 5INFO: Loaded 1 PC tables (570172 PCs): 570172 [0x55dfa9a2dce0,0x55dfaa2e10a0), 
 6/workdir/fuzz_bins/fuzz_libfuzzer: Running 1 inputs 1 time(s) each.
 7Running: /workdir/crashes/crash-d97eed2ff63da56af72c8c858c560a7c6f2aef45
 8fuzz_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.
 9==482== ERROR: libFuzzer: deadly signal
10    [#0](/bitcoin-bitcoin/0/) 0x55dfa8279c88 in __sanitizer_print_stack_trace (/workdir/fuzz_bins/fuzz_libfuzzer+0x149ec88) (BuildId: 2b223d93a9bf2ebca89c11d8baf07b3113f0c65f)
11    [#1](/bitcoin-bitcoin/1/) 0x55dfa825104c in fuzzer::PrintStackTrace() crtstuff.c
12    [#2](/bitcoin-bitcoin/2/) 0x55dfa8236e67 in fuzzer::Fuzzer::CrashCallback() crtstuff.c
13    [#3](/bitcoin-bitcoin/3/) 0x7fadb47b050f  (/lib/x86_64-linux-gnu/libc.so.6+0x3c50f) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
14    [#4](/bitcoin-bitcoin/4/) 0x7fadb47fe0fb  (/lib/x86_64-linux-gnu/libc.so.6+0x8a0fb) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
15    [#5](/bitcoin-bitcoin/5/) 0x7fadb47b0471 in raise (/lib/x86_64-linux-gnu/libc.so.6+0x3c471) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
16    [#6](/bitcoin-bitcoin/6/) 0x7fadb479a4b1 in abort (/lib/x86_64-linux-gnu/libc.so.6+0x264b1) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
17    [#7](/bitcoin-bitcoin/7/) 0x7fadb479a3d4  (/lib/x86_64-linux-gnu/libc.so.6+0x263d4) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
18    [#8](/bitcoin-bitcoin/8/) 0x7fadb47a93a1 in __assert_fail (/lib/x86_64-linux-gnu/libc.so.6+0x353a1) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
19    [#9](/bitcoin-bitcoin/9/) 0x55dfa8283267 in wallet::coinselection_fuzz_target(Span<unsigned char const>) coinselection.cpp
20    [#10](/bitcoin-bitcoin/10/) 0x55dfa864b487 in LLVMFuzzerTestOneInput fuzz.cpp
21    [#11](/bitcoin-bitcoin/11/) 0x55dfa8238334 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) crtstuff.c
22    [#12](/bitcoin-bitcoin/12/) 0x55dfa8221263 in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) crtstuff.c
23    [#13](/bitcoin-bitcoin/13/) 0x55dfa8226e86 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) crtstuff.c
24    [#14](/bitcoin-bitcoin/14/) 0x55dfa82519d6 in main crtstuff.c
25    [#15](/bitcoin-bitcoin/15/) 0x7fadb479b6c9  (/lib/x86_64-linux-gnu/libc.so.6+0x276c9) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
26    [#16](/bitcoin-bitcoin/16/) 0x7fadb479b784 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x27784) (BuildId: 8a1bf172e710f8ca0c1576912c057b45f90d90d8)
27    [#17](/bitcoin-bitcoin/17/) 0x55dfa821bcd0 in _start (/workdir/fuzz_bins/fuzz_libfuzzer+0x1440cd0) (BuildId: 2b223d93a9bf2ebca89c11d8baf07b3113f0c65f)
28
29NOTE: libFuzzer has rudimentary signal handlers.
30      Combine libFuzzer with AddressSanitizer or similar for better crash reports.
31SUMMARY: libFuzzer: deadly signal

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

dergoegge commented at 12:58 pm on November 20, 2023: member

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

maflcko added this to the milestone 26.0 on Nov 20, 2023

maflcko commented at 1:10 pm on November 20, 2023: member

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

furszy commented at 9:17 pm on November 20, 2023: member

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

brunoerg commented at 9:30 pm on November 20, 2023: contributor

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

 0diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
 1index 4caf96b18d..1e040fb5e2 100644
 2--- a/src/wallet/test/fuzz/coinselection.cpp
 3+++ b/src/wallet/test/fuzz/coinselection.cpp
 4@@ -116,12 +116,14 @@ FUZZ_TARGET(coinselection)
 5     }
 6 
 7     // Run coinselection algorithms
 8-    auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
 9-    if (result_bnb) {
10-        assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
11-        assert(result_bnb->GetSelectedValue() >= target);
12-        (void)result_bnb->GetShuffledInputVector();
13-        (void)result_bnb->GetInputSet();
14+    if (!subtract_fee_outputs) {
15+        auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
16+        if (result_bnb) {
17+            assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
18+            assert(result_bnb->GetSelectedValue() >= target);
19+            (void)result_bnb->GetShuffledInputVector();
20+            (void)result_bnb->GetInputSet();
21+        }
22     }

furszy commented at 9:38 pm on November 20, 2023: member

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

brunoerg commented at 10:28 pm on November 20, 2023: contributor

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.

furszy commented at 11:07 pm on November 20, 2023: member

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.

maflcko added the label Wallet on Nov 21, 2023

maflcko added the label Tests on Nov 21, 2023

murchandamus commented at 7:54 pm on December 1, 2023: contributor

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.

murchandamus commented at 10:42 pm on December 1, 2023: contributor

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

maflcko removed this from the milestone 26.0 on Dec 4, 2023

maflcko commented at 10:53 am on December 4, 2023: member

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?

maflcko added this to the milestone 26.1 on Dec 4, 2023

fanquake commented at 1:01 pm on December 4, 2023: member

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.

furszy commented at 1:16 pm on December 4, 2023: member

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.

murchandamus commented at 2:13 pm on December 4, 2023: contributor

Sure, go ahead!

achow101 referenced this in commit d646ca35d9 on Dec 12, 2023

maflcko closed this on Dec 12, 2023

dergoegge commented at 9:13 am on December 13, 2023: member

This is still broken, please reopen:

0$ echo "AQ0N0NfM0B7QEK1AL3m3AJWVlQAAgQAAAAAAlZWVAACBAAAAAACVlZUAAAAAAAAAAAAAAAAAXQAAgQAAAAAAAAAAAAAA" | base64 --decode > coinselection-90005214eeb91a419ca37def8d958bf6bb670edf.crash
1$ FUZZ=coinselection ./src/test/fuzz/fuzz coinselection-90005214eeb91a419ca37def8d958bf6bb670edf.crash
2fuzz_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.

maflcko reopened this on Dec 13, 2023

maflcko removed this from the milestone 26.1 on Dec 13, 2023

furszy commented at 12:11 pm on December 13, 2023: member

This is still broken, please reopen:

0$ echo "AQ0N0NfM0B7QEK1AL3m3AJWVlQAAgQAAAAAAlZWVAACBAAAAAACVlZUAAAAAAAAAAAAAAAAAXQAAgQAAAAAAAAAAAAAA" | base64 --decode > coinselection-90005214eeb91a419ca37def8d958bf6bb670edf.crash
1$ FUZZ=coinselection ./src/test/fuzz/fuzz coinselection-90005214eeb91a419ca37def8d958bf6bb670edf.crash
2fuzz_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.

furszy commented at 12:45 pm on December 13, 2023: member

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.

murchandamus commented at 7:14 pm on December 22, 2023: contributor

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

dergoegge closed this on Dec 22, 2023

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