wallet: Guard against undefined behaviour #25982

yancyribbens commented at 10:46 AM on September 2, 2022: contributor

This PR adds a few safe guards against undefined or nonsense values. A selection_target of negative or 0 value is undefined and same with cost_of_change. It's safer to prevent undefined values from being evaluated later on in the function body which may result in unexpected behavior. An exception is raised similar to here when values are undefined.

fanquake added the label Wallet on Sep 2, 2022

fanquake commented at 10:57 AM on September 2, 2022: member

CI:

Assertion failed: (cost_of_change > 0), function SelectCoinsBnB, file coinselection.cpp, line 68.

yancyribbens force-pushed on Sep 2, 2022

yancyribbens commented at 4:54 PM on September 2, 2022: contributor

Thanks, CI should be fixed now.

fanquake commented at 2:03 PM on September 22, 2022: member

Thanks, CI should be fixed now.

The fuzzer is failing https://github.com/bitcoin/bitcoin/pull/25982/checks?check_run_id=8160631729:

INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 1696319385
INFO: Loaded 1 modules   (350003 inline 8-bit counters): 350003 [0x55b9e9d5a780, 0x55b9e9dafeb3), 
INFO: Loaded 1 PC tables (350003 PCs): 350003 [0x55b9e9dafeb8,0x55b9ea3071e8), 
INFO:        0 files found in /tmp/cirrus-ci-build/ci/scratch/qa-assets/fuzz_seed_corpus/coinselection
INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 4096 bytes
fuzz: wallet/coinselection.cpp:68: std::optional<SelectionResult> wallet::SelectCoinsBnB(std::vector<OutputGroup> &, const CAmount &, const CAmount &): Assertion `cost_of_change > 0' failed.
==19052== ERROR: libFuzzer: deadly signal
    [#0](/bitcoin-bitcoin/0/) 0x55b9e6f65521  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x1758521) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#1](/bitcoin-bitcoin/1/) 0x55b9e6ed7db8  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16cadb8) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#2](/bitcoin-bitcoin/2/) 0x55b9e6ebd833  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16b0833) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#3](/bitcoin-bitcoin/3/) 0x7fb4cce7e51f  (/lib/x86_64-linux-gnu/libc.so.6+0x4251f) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    [#4](/bitcoin-bitcoin/4/) 0x7fb4cced2a7b  (/lib/x86_64-linux-gnu/libc.so.6+0x96a7b) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    [#5](/bitcoin-bitcoin/5/) 0x7fb4cce7e475  (/lib/x86_64-linux-gnu/libc.so.6+0x42475) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    [#6](/bitcoin-bitcoin/6/) 0x7fb4cce647f2  (/lib/x86_64-linux-gnu/libc.so.6+0x287f2) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    [#7](/bitcoin-bitcoin/7/) 0x7fb4cce6471a  (/lib/x86_64-linux-gnu/libc.so.6+0x2871a) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    [#8](/bitcoin-bitcoin/8/) 0x7fb4cce75e95  (/lib/x86_64-linux-gnu/libc.so.6+0x39e95) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    [#9](/bitcoin-bitcoin/9/) 0x55b9e7fec5a9  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x27df5a9) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#10](/bitcoin-bitcoin/10/) 0x55b9e6f99479  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x178c479) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#11](/bitcoin-bitcoin/11/) 0x55b9e6f9bcc5  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x178ecc5) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#12](/bitcoin-bitcoin/12/) 0x55b9e6f9bb8d  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x178eb8d) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#13](/bitcoin-bitcoin/13/) 0x55b9e6f9b968  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x178e968) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#14](/bitcoin-bitcoin/14/) 0x55b9e73faedd  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x1bededd) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#15](/bitcoin-bitcoin/15/) 0x55b9e73fab38  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x1bedb38) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#16](/bitcoin-bitcoin/16/) 0x55b9e6ebedc3  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16b1dc3) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#17](/bitcoin-bitcoin/17/) 0x55b9e6ec0020  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16b3020) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#18](/bitcoin-bitcoin/18/) 0x55b9e6ec0672  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16b3672) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#19](/bitcoin-bitcoin/19/) 0x55b9e6eae9c2  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16a19c2) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#20](/bitcoin-bitcoin/20/) 0x55b9e6ed86b2  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16cb6b2) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    [#21](/bitcoin-bitcoin/21/) 0x7fb4cce65d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    [#22](/bitcoin-bitcoin/22/) 0x7fb4cce65e3f  (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    [#23](/bitcoin-bitcoin/23/) 0x55b9e6ea3404  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x1696404) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
NOTE: libFuzzer has rudimentary signal handlers.
      Combine libFuzzer with AddressSanitizer or similar for better crash reports.
SUMMARY: libFuzzer: deadly signal
MS: 0 ; base unit: 0000000000000000000000000000000000000000
artifact_prefix='./'; Test unit written to ./crash-da39a3ee5e6b4b0d3255bfef95601890afd80709
Base64: 
Target "/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz -runs=1 /tmp/cirrus-ci-build/ci/scratch/qa-assets/fuzz_seed_corpus/coinselection" failed with exit code 77

@achow @Xekyo any opinion on this?

yancyribbens commented at 2:13 PM on September 22, 2022: contributor

@fanquake thanks. I've had some trouble getting the fuzzer to run locally on my machine (FreeBSD) so it's difficult for me to debug this. Waiting to hear feedback if others think it's worth while.

DrahtBot commented at 4:21 AM on September 23, 2022: contributor

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

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#26720 (wallet: coin selection, don't return results that exceed the max allowed weight by furszy)
#25806 (wallet: group outputs only once, decouple it from Coin Selection by furszy)

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.

mzumsande commented at 8:10 PM on September 30, 2022: contributor

@fanquake thanks. I've had some trouble getting the fuzzer to run locally on my machine (FreeBSD) so it's difficult for me to debug this. Waiting to hear feedback if others think it's worth while.

To fix the fuzzer, you could change const CAmount cost_of_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)}; (code) to const CAmount cost_of_change{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)}; The first one draws a random number between 0 and MAX_MONEY (which will crash with the added assert), the second one between 1 and MAX_MONEY.

yancyribbens force-pushed on Oct 3, 2022

yancyribbens commented at 9:47 AM on October 3, 2022: contributor

@mzumsande thanks, this should fix the test. Although, ideally the fuzz data would also include values larger than 0 but less than 1 [0, MAX_MONEY). I didn't know if it was worth spending a lot of time on this PR since I haven't had any type of ack though.

yancyribbens force-pushed on Oct 3, 2022

yancyribbens commented at 3:10 PM on October 3, 2022: contributor

May as well add assertions for the upper bound as well.

wallet: Guard against undefined behaviour 496d5c5874

in src/wallet/coinselection.cpp:71 in 496d5c5874

  63 | @@ -64,6 +64,12 @@ static const size_t TOTAL_TRIES = 100000;
  64 |  
  65 |  std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change)
  66 |  {
  67 | +    assert(selection_target > 0);
  68 | +    assert(selection_target <= MAX_MONEY);
  69 | +
  70 | +    assert(cost_of_change > 0);
  71 | +    assert(cost_of_change <= MAX_MONEY);

murchandamus commented at 5:12 PM on October 3, 2022:

Weak concept ACK. I think it's a good practice to explicitly communicate assumptions, but it also feels a bit far-fetched that we'd manage to screw up our internal call stack that the asserts would actually get triggered except in unit tests.

Both selection_target and cost_of_change necessarily are always greater than 0. Yet, both these values are set by our own internal functions and initialized to non-zero values. Also, they appear in every coin selection algorithm, not just BnB. So, perhaps if we wanted to assert that they are in the proper range, the assert should be placed at the SelectCoins level rather than in SelectCoinsBnB?

@mzumsande thanks, this should fix the test. Although, ideally the fuzz data would also include values larger than 0 but less than 1 [0, MAX_MONEY). I didn't know if it was worth spending a lot of time on this PR since I haven't had any type of ack though.

from src/consensus/.amount.h:

/** Amount in satoshis (Can be negative) */
typedef int64_t CAmount;

CAmount is an integer satoshi count. The smallest CAmount greater than 0 is 1.

yancyribbens commented at 2:25 AM on October 4, 2022:

typedef int64_t CAmount;

Thanks, good point, it's an int type.

perhaps if we wanted to assert that they are in the proper range, the assert should be placed at the SelectCoins level rather than in SelectCoinsBnB?

I think moving this type of check higher up the call stack could makes sense. However there is already some precedence for this type of assertion at this level so it didn't seem out of place. The good thing about the assertions here is that the code is a bit more modular and stands on it's own.

Also, I noticed after I created this PR, that there is another assertion for cost_of_change here, although it seems less useful to place the assertion after the coinselection process has happened. I mentioned this in a different PR, but this entire method call is redundant I believe since we just endup comparing the results again here.

murchandamus commented at 7:17 PM on October 4, 2022:

You could add the same asserts to the other coin selection algorithms, they all depend on these two values. Would you mind elaborating what gave you the idea to add the asserts?

yancyribbens commented at 9:20 AM on October 5, 2022:

I am looking into some optimizations, however I want to be sure I know what the bounds are to prevent possible overflows or exceptions. There are cases already that if invalid values are passed in there's the possibility to overflow, for example if selection_target is INT_MAX, then the addition of here would overflow the size of INT_MAX. selection_target and cost_of_change are both signed int int64_t and exceeding INT_MAX is undefined behavior. Likewise if selection_target is INT_MIN and cost_of_change is negative would again result in undefined behavior.

yancyribbens commented at 9:45 AM on October 5, 2022:

You could add the same asserts to the other coin selection algorithms

Sure, the other selection algorithms I see are: KnapsackSolver, SelectCoinsSRD, ApproximateBestSubset. We can add these as part of this PR or a new one. I'm not sure which is preferable.

murchandamus commented at 5:54 PM on October 5, 2022:

Since it would be the same two values getting checked in all of the algorithms for the same reason, it would be better to add them all in a single commit.

yancyribbens commented at 10:02 AM on October 6, 2022:

What do you think about restructuring this file so that each selection algorithm has it's own file, class and test suit? Feels like this file is a bit of a messy as is. Obviously talking about a different PR to do so.

yancyribbens commented at 10:39 AM on October 6, 2022:

I looked into adding the same bounds check for the other three selection algorithms however it doesn't seem like the params they use are consistent. They all use an equivalent of selection_target however call it a different name nTargetValue for example. cost_of_change doesn't seem to be passed as an argument but instead KnapsackSolver uses change_target. These two params change_target and cost_of_change appear to be different. ApproximateBestSubset uses nTotalLower which would be a different type of boundary check. Since each algorithm appears to have unique params, maybe it makes more sense to address each separately.

Since it would be the same two values getting checked in all of the algorithms for the same reason, it would be better to add them all in a single commit.

It doesn't appear to me that the same two values are checked. What do you think about addressing each selection algorithm separately to reduce the scope of this PR?

Also, does it make sense to use 0 as a default value here for cost_of_change?

fanquake commented at 11:08 AM on February 15, 2023: member

@achow101 would be good to get your conceptual thoughts here.

maflcko commented at 11:25 AM on February 15, 2023: member

In any case: test_bitcoin: wallet/coinselection.cpp:71: std::optional<wallet::SelectionResult> wallet::SelectCoinsBnB(std::__debug::vector<wallet::OutputGroup>&, const CAmount&, const CAmount&): Assertion cost_of_change > 0' failed.`

yancyribbens commented at 6:50 PM on February 17, 2023: contributor

@MarcoFalke it looks like the following test_case here was added after I made the PR (that test doesn't exist in my PR branch).

The cost_of_change should always be greater than zero so something is wrong with the test case. However, there doesn't seem to be much enthusiasm for this PR so its probably not worth it for me to spend time fixing it unless I get feedback that says this PR is worthwhile.

DrahtBot added the label Needs rebase on Mar 7, 2023

DrahtBot commented at 1:03 AM on March 7, 2023: contributor

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

achow101 commented at 4:25 PM on April 25, 2023: member

Closing this as it has not had any activity in a while. If you are interested in continuing work on this, please leave a comment so that it can be reopened.

achow101 closed this on Apr 25, 2023

bitcoin locked this on Apr 24, 2024