Skip to content

wallet: Guard against undefined behaviour #25982

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
wants to merge 1 commit into from
Closed

wallet: Guard against undefined behaviour #25982

wants to merge 1 commit into from

Conversation

yancyribbens
Copy link
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 fanquake added the Wallet label Sep 2, 2022
@fanquake
Copy link
Member

fanquake commented Sep 2, 2022

CI:

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

@yancyribbens yancyribbens force-pushed the undefined-behavior-gaurd branch from 1bd498a to 69325de Compare September 2, 2022 16:50
@yancyribbens
Copy link
Contributor Author

Thanks, CI should be fixed now.

@fanquake
Copy link
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 0x55b9e6f65521  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x1758521) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #1 0x55b9e6ed7db8  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16cadb8) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #2 0x55b9e6ebd833  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16b0833) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #3 0x7fb4cce7e51f  (/lib/x86_64-linux-gnu/libc.so.6+0x4251f) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    #4 0x7fb4cced2a7b  (/lib/x86_64-linux-gnu/libc.so.6+0x96a7b) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    #5 0x7fb4cce7e475  (/lib/x86_64-linux-gnu/libc.so.6+0x42475) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    #6 0x7fb4cce647f2  (/lib/x86_64-linux-gnu/libc.so.6+0x287f2) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    #7 0x7fb4cce6471a  (/lib/x86_64-linux-gnu/libc.so.6+0x2871a) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    #8 0x7fb4cce75e95  (/lib/x86_64-linux-gnu/libc.so.6+0x39e95) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    #9 0x55b9e7fec5a9  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x27df5a9) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #10 0x55b9e6f99479  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x178c479) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #11 0x55b9e6f9bcc5  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x178ecc5) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #12 0x55b9e6f9bb8d  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x178eb8d) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #13 0x55b9e6f9b968  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x178e968) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #14 0x55b9e73faedd  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x1bededd) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #15 0x55b9e73fab38  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x1bedb38) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #16 0x55b9e6ebedc3  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16b1dc3) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #17 0x55b9e6ec0020  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16b3020) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #18 0x55b9e6ec0672  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16b3672) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #19 0x55b9e6eae9c2  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16a19c2) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #20 0x55b9e6ed86b2  (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz+0x16cb6b2) (BuildId: edd028937b0f2ab14f284ed90efe810d8be85edc)
    #21 0x7fb4cce65d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    #22 0x7fb4cce65e3f  (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
    #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
Copy link
Contributor Author

@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
Copy link
Contributor

DrahtBot commented Sep 23, 2022 •
edited
Loading

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
Copy link
Contributor

mzumsande commented Sep 30, 2022 •
edited
Loading

@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 yancyribbens force-pushed the undefined-behavior-gaurd branch from 69325de to b951972 Compare October 3, 2022 09:41
@yancyribbens
Copy link
Contributor Author

yancyribbens commented Oct 3, 2022 •
edited
Loading

@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 yancyribbens force-pushed the undefined-behavior-gaurd branch from b951972 to 496d5c5 Compare October 3, 2022 15:10
@yancyribbens
Copy link
Contributor Author

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

murchandamus
murchandamus reviewed Oct 3, 2022
View reviewed changes
src/wallet/coinselection.cpp
Comment on lines +67 to +71
assert(selection_target > 0);
assert(selection_target <= MAX_MONEY);

assert(cost_of_change > 0);
assert(cost_of_change <= MAX_MONEY);
Copy link
Contributor

Choose a reason for hiding this comment

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

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.

Copy link
Contributor Author

Choose a reason for hiding this comment

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

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.

Copy link
Contributor

Choose a reason for hiding this comment

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

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?

Copy link
Contributor Author

@yancyribbens yancyribbens Oct 5, 2022 •
edited
Loading

Choose a reason for hiding this comment

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

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.

Copy link
Contributor Author

Choose a reason for hiding this comment

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

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.

Copy link
Contributor

Choose a reason for hiding this comment

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

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.

Copy link
Contributor Author

Choose a reason for hiding this comment

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

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.

Copy link
Contributor Author

Choose a reason for hiding this comment

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

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?

@DrahtBot DrahtBot mentioned this pull request Oct 28, 2022
Merged
@DrahtBot DrahtBot mentioned this pull request Dec 19, 2022
Merged
@fanquake
Copy link
Member

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

@maflcko
Copy link
Member

maflcko commented Feb 15, 2023

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
Copy link
Contributor Author

@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
Copy link
Contributor

DrahtBot commented Mar 7, 2023

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

@achow101
Copy link
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 achow101 closed this Apr 25, 2023
@bitcoin bitcoin locked and limited conversation to collaborators Apr 24, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Reviewers
1 more reviewer

@murchandamus murchandamus murchandamus left review comments

Reviewers whose approvals may not affect merge requirements
Assignees
No one assigned
Labels
Needs rebase Wallet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
7 participants
@yancyribbens @fanquake @DrahtBot @mzumsande @maflcko @achow101 @murchandamus