fuzz: split `coinselection` harness

brunoerg commented at 6:09 pm on February 14, 2025: contributor

This PR splits the coinselection fuzz harness into 3 targets (coinselection_bnb, coinselection_knapsack, coinselection_srd). The goal is to be able to fuzz each algorithm separately (to avoid performance issues) and also all of them together.

DrahtBot commented at 6:09 pm on February 14, 2025: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/31870.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	janb84, marcofleon, zaidmstrr, maflcko
Concept ACK	yancyribbens

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:

#31806 (fuzz: coinselection: cover SetBumpFeeDiscount by brunoerg)

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.

DrahtBot added the label Tests on Feb 14, 2025

brunoerg marked this as ready for review on Feb 14, 2025

in src/wallet/test/fuzz/coinselection.cpp:223 in c6ab148559 outdated

220-{
221+enum class CoinSelectionAlgorithm {
222+    BNB,
223+    SRD,
224+    KNAPSACK,
225+    ALL

maflcko commented at 9:22 am on February 17, 2025:

nit: missing trailing comma.

Also, what is the point of combining them, when they are handled completely separate anyway?

brunoerg commented at 1:22 pm on February 17, 2025:

I just removed the ALL option. I don’t see anything that needs all of them combined.

in src/wallet/test/fuzz/coinselection.cpp:227 in c6ab148559 outdated

224+    KNAPSACK,
225+    ALL
226+};
227+
228+template<CoinSelectionAlgorithm Algorithm>
229+void FuzzCoinSelectionAlgorithm(const uint8_t* buffer, size_t size) {

maflcko commented at 9:22 am on February 17, 2025:

nit: please use std::span for new code

brunoerg commented at 1:20 pm on February 17, 2025:

Done

in src/wallet/test/fuzz/coinselection.cpp:289 in c6ab148559 outdated

302-    auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context, max_selection_weight);
303-    if (result_knapsack) {
304-        assert(result_knapsack->GetSelectedValue() >= target);
305-        assert(result_knapsack->GetWeight() <= max_selection_weight);
306-        result_knapsack->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
307-        (void)result_knapsack->GetShuffledInputVector();

maflcko commented at 9:28 am on February 17, 2025:

why remove this call?

brunoerg commented at 11:32 am on February 17, 2025:

There is no need to remove it, will put back. Probably missed it during the rework. Thanks.

brunoerg commented at 1:20 pm on February 17, 2025:

Done

brunoerg force-pushed on Feb 17, 2025

brunoerg commented at 1:23 pm on February 17, 2025: contributor

Force-pushed addressing #31870 (review), #31870 (review) and #31870 (review). Thanks, @maflcko.

in src/wallet/test/fuzz/coinselection.cpp:355 in aa27eeaaf3 outdated

350+FUZZ_TARGET(coinselection_srd) {
351+    FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::SRD>(std::span<const uint8_t>(buffer.data(), buffer.size()));
352+}
353+
354+FUZZ_TARGET(coinselection_knapsack) {
355+    FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::KNAPSACK>(std::span<const uint8_t>(buffer.data(), buffer.size()));

maflcko commented at 1:27 pm on February 17, 2025:

0    FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::KNAPSACK>(buffer);

nit: it is already a span,no?

brunoerg commented at 1:31 pm on February 17, 2025:

yes, done.

brunoerg force-pushed on Feb 17, 2025

DrahtBot added the label CI failed on Feb 17, 2025

DrahtBot removed the label CI failed on Feb 17, 2025

zaidmstrr commented at 8:32 pm on February 17, 2025: none

Hey, I’m reviewing this PR, as the description says that we can test each target separately, (coinselection_bnb, coinselection_knapsack, coinselection_srd) which is fine, but for the combined test I can’t find any fuzz target there like coinselection.

brunoerg commented at 8:37 pm on February 17, 2025: contributor

Hey, I’m reviewing this PR, as the description says that we can test each target separately, (coinselection_bnb, coinselection_knapsack, coinselection_srd) which is fine, but for the combined test I can’t find any fuzz target there like coinselection.

I just updated the description. I removed the coinselection target, so there are 3 ones.

zaidmstrr commented at 8:33 am on February 18, 2025: none

Tested ACK 9b293d0 The idea of fuzzing each algorithm independently seems good. I manually reviewed the new code changes with the previous ones to check for any missing statements. I also tested the code by manually inserting assert statements in between to check whether the desired behaviour was occurring or not.

marcofleon commented at 1:27 pm on February 21, 2025: contributor

Code review ACK 9b293d031c941dc6af0c4274e43388c57c702047

Knapsack is quite a bit slower than the other two, so separating them out is probably a good idea.

Coverage for the three targets: coinselection_bnb coinselection_srd coinselection_knapsack

in src/wallet/test/fuzz/coinselection.cpp:312 in 9b293d031c outdated

344+            (void)result_knapsack->GetShuffledInputVector();
345+            (void)result_knapsack->GetInputSet();
346+            // If the total balance is sufficient for the target and we are not using
347+            // effective values, Knapsack should always find a solution (unless the selection exceeded the max tx weight).
348+            if (total_balance >= target && subtract_fee_outputs && !HasErrorMsg(result_knapsack)) {
349+                assert(result_knapsack);

maflcko commented at 2:05 pm on February 21, 2025:

why are you removing this check?

brunoerg commented at 2:54 pm on February 21, 2025:

Removing?

marcofleon commented at 2:59 pm on February 21, 2025:

Good catch. Took me a bit to see, but yeah this check should be outside of the inner if statement.

maflcko commented at 2:59 pm on February 21, 2025:

Previously the assert was exposed, now it is guarded by the same condition, making it dead code that the compiler will remove.

In other words: { if (a) assert(a); } is equivalent to { }.

brunoerg commented at 3:22 pm on February 21, 2025:

Ah, good catch! Gonna fix it, thanks.

brunoerg commented at 4:27 pm on February 21, 2025:

Done.

fuzz: split `coinselection` harness ba82240553

brunoerg force-pushed on Feb 21, 2025

brunoerg commented at 4:27 pm on February 21, 2025: contributor

Force-pushed addressing #31870 (review)

janb84 commented at 7:47 pm on February 25, 2025: contributor

Tested ACK ba82240

The change to fuzz each algorithm independently seems an okay idea. The implementation/separation in the code also makes it easier to read, review, and reason about.

Built and ran fuzzers, minimum of 15 minutes each.
Reviewed code changes line-by-line
Tried to compile CodeCoverage of new Fuzz targets but I failed at that (not a code issue)

I also wrote a review note on the PR to document my learning journey

DrahtBot requested review from marcofleon on Feb 25, 2025

DrahtBot requested review from zaidmstrr on Feb 25, 2025

marcofleon commented at 6:27 pm on March 13, 2025: contributor

reACK ba82240553ddd534287845e10bc76b46b45329fe

Only thing that changed since last review is the fix to #31870 (review). The order of the two checks has been switched but afaict it shouldn’t matter.

yancyribbens commented at 5:05 pm on March 14, 2025: contributor

Concept ACK. I’m curious if there should be any doc updates accompanying this change.

zaidmstrr commented at 6:39 pm on March 14, 2025: none

reACK ba82240 As the previous issue raised by maflcko is resolved.

brunoerg commented at 6:44 pm on March 14, 2025: contributor

I’m curious if there should be any doc updates accompanying this change.

No, it’s a test-only change.

brunoerg requested review from maflcko on Mar 18, 2025

fanquake commented at 8:54 am on March 21, 2025: member

cc @dergoegge

maflcko commented at 9:05 am on March 21, 2025: member

review ACK ba82240553ddd534287845e10bc76b46b45329fe 👐

Signature:

0untrusted comment: signature from minisign secret key on empty file; verify via: minisign -Vm "${path_to_any_empty_file}" -P RWTRmVTMeKV5noAMqVlsMugDDCyyTSbA3Re5AkUrhvLVln0tSaFWglOw -x "${path_to_this_whole_four_line_signature_blob}"
1RUTRmVTMeKV5npGrKx1nqXCw5zeVHdtdYURB/KlyA/LMFgpNCs+SkW9a8N95d+U4AP1RJMi+krxU1A3Yux4bpwZNLvVBKy0wLgM=
2trusted comment: review ACK ba82240553ddd534287845e10bc76b46b45329fe 👐
3AaLQ7VClMZd8vRGNIiLsK54KJFAUcqCKCnsGUSXGGyDuhdZGVtjAVzTOih3F0roC5Z2Bh/o/YP/kBeS9oRttCQ==

fanquake merged this on Mar 21, 2025

fanquake closed this on Mar 21, 2025

murchandamus commented at 6:58 pm on March 21, 2025: contributor

Oh I had missed this, and noticed it via the new fuzz target corpora. Great idea!

brunoerg deleted the branch on Mar 21, 2025

fuzz: split coinselection harness #31870

Code Coverage & Benchmarks

Reviews

Conflicts

fuzz: split `coinselection` harness #31870