refactor: Avoid integer overflow in ApplyStats when activating snapshot #23411

maflcko · 2021-11-01T14:56:24Z

A snapshot contains the utxo set, including the out value. To activate the snapshot, the hash needs to be calculated. As a side-effect, the total amount in the snapshot is calculated (as the sum of all out values), but never used. Instead of running into an integer overflow in an unused result, don't calculate the result in the first place.

Other code paths (using the active utxo set) can not run into an integer overflow, since the active utxo set is valid.

Fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=39716

maflcko · 2021-11-01T14:58:11Z

Reproducer:
clusterfuzz-testcase-minimized-utxo_snapshot-6702059005542400.bin.txt

sipa · 2021-11-01T15:30:15Z

How does activating a snapshot trigger an integer overflow in this code in the first place? That seems far more concerning, and this PR just patches it up.

maflcko · 2021-11-01T15:55:28Z

@sipa Added three more sentences to OP to explain this refactor.

jamesob · 2021-11-01T15:58:09Z

Hm, I'm kind of confused - is the concern here that a user could be fed a bad snapshot that causes an overflow? Because if that's the case, the hash of the UTXO set won't match the one hardcoded in chainparams' m_assumeutxo_data.

If it's not a bad snapshot you're worried about, then as far as I can tell the same wraparound issue would exist with a normal gettxoutsetinfo call at the height of the snapshot.

maflcko · 2021-11-01T15:59:33Z

Correct.

If we don't care about integer overflows when activating invalid snapshots, then this pull can be closed.

sipa · 2021-11-01T19:29:31Z

Would it make sense to instead compute the total amount as an std::optional, which starts at {0}, and is incremented with the read values, but when an out-of-range value is read, or the sum goes out-of-range, is replaced with std::nullopt (and then stays at std::nullopt)? That would categorically remove this concern, and pushes the responsibility for checking sanity to the caller (where it apparently differs).

DrahtBot · 2021-11-01T21:06:33Z

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

Conflicts

No conflicts as of last run.

maflcko · 2021-11-02T12:29:53Z

Switched to std::optional approach

shaavan

Concept ACK

This PR allows preventing integer overflow of coin_stats.total_amount while activating the snapshot.

The following points explain the PR in greater detail:

The function AdditionOverflow has been moved from src/test/fuzz/util.h to a new file src/util/overflow.h. The dependencies of other files are updated accordingly.
Unit tests are added for this function, which tests on various edge cases in the case of both signed and unsigned elements.
The AdditionOverflow function is used in the coinstats::ApplyStats function to prevent the risk of an overflow of CAmount. In case if there might be an integer overflow, the total_amount var is set to nullopt.

Though I have not rigorously tested this PR yet, I think the code is logically coherent.

I have just one doubt I would like to point out.

In src/test/util_tests.cpp file:
From the line BOOST_CHECK(TestAddMatrix<signed>()); I inferred that this function was made to be used with signed integers. If I am correct, then there is one logical error:

assert(TestAdd(mini, mini));

This might not always be true.

For example:

mini = 2; mini + mini = 4 > 2 (in range) TestAdd result == true
mini = -2; mini + mini = -4 < -2 (out of range) TestAdd result == false

maflcko · 2021-11-02T13:57:35Z

This might not always be true.

MINI is a compile time constant (just force pushed to rename it from mini). It allows for the test checking for underflow to be less verbose. Checking for underflow is only needed when adding signed integers. Adding two unsigned integers can only overflow.

luke-jr · 2021-11-02T17:18:28Z

Seems like the number is useful for human verification. We should probably log it or tell advanced users somewhere.

Maybe instead, abort activation of snapshots that exceed MAX_MONEY?

maflcko · 2021-11-02T18:03:11Z

Maybe instead, abort activation of snapshots that exceed MAX_MONEY?

The amounts are already covered by the hash, which is obviously trusted and verified. Thus, it will abort activation.

Starting to check random consensus rules on the snapshot is going to be an open ended issue (why not check that there are no unspendable scriptPubKeys in the snapshot, ...) that doesn't give any benefit.

shaavan

Checking for underflow is only needed when adding signed integers. Adding two unsigned integers can only overflow.

Makes sense to me now. Since TestAddMatrix() is being used only for signed integer. The minimum possible value ( = MINI) must be < 0. In that case the assertion condition assert(TestAdd(MINI, MINI)); will never fail.

crACK fa13888

src/node/coinstats.cpp

shaavan

reACK fa4a86e

Changes since my last review:

Added a new function CheckedAdd (in overflow.h), which returns nullopt if there is an addition overflow (or underflow) and otherwise returns the sum.
TestAdd function (in util_tests.cpp) has been removed, and its usage is replaced with CheckedAdd.
Finally, CheckedAdd is used to simplify added code in the coinstats.cpp file.

shaavan

reACK fa72733

Changes since my last review:

Rebased the branch on the current master.

vasild

Concept ACK fa72733

src/rpc/blockchain.cpp

src/test/util_tests.cpp

maflcko · 2021-12-17T09:50:04Z

Addressed test nits in force push. Should be trivial to re-ACK with:

git range-diff bitcoin-core/master --word-diff-regex=. fa72733b12 fa996c58e8

shaavan

reACK fa996c5

Changes since my last review:

Addressed suggestion under this comment.
stats.total_amount -> stats.total_amount.has_value()
Replaced assert with BOOST_CHECK in src/test/util_tests.cpp file.

I agree with the rationale behind the changes discussed under the above comment.

vasild

ACK fa996c5

…hen activating snapshot fa996c5 refactor: Avoid integer overflow in ApplyStats when activating snapshot (MarcoFalke) fac0188 Move AdditionOverflow to util, Add CheckedAdd with unit tests (MarcoFalke) fa526d8 Add dev doc to CCoinsStats::m_hash_type and make it const (MarcoFalke) faff051 style: Remove unused whitespace (MarcoFalke) Pull request description: A snapshot contains the utxo set, including the out value. To activate the snapshot, the hash needs to be calculated. As a side-effect, the total amount in the snapshot is calculated (as the sum of all out values), but never used. Instead of running into an integer overflow in an unused result, don't calculate the result in the first place. Other code paths (using the active utxo set) can not run into an integer overflow, since the active utxo set is valid. Fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=39716 ACKs for top commit: shaavan: reACK fa996c5 vasild: ACK fa996c5 Tree-SHA512: 4f207f634841f6f634fd02ae1e5907e343fd767524fd0e8149aa99fa9a1834fe50167d14874834d45236e9c325d567925f28129bacb7d80be29cf22277a16a14

maflcko force-pushed the 2111-fuzzIntAmt branch from 31ce7b3 to fac215e Compare November 1, 2021 14:56

maflcko added the Refactoring label Nov 1, 2021

maflcko force-pushed the 2111-fuzzIntAmt branch from fac215e to fa5bdc9 Compare November 1, 2021 15:20

DrahtBot mentioned this pull request Nov 1, 2021

rpc: various fixups for dumptxoutset #23155

Merged

maflcko force-pushed the 2111-fuzzIntAmt branch from fa5bdc9 to fa12d4f Compare November 2, 2021 09:28

shaavan reviewed Nov 2, 2021

View reviewed changes

maflcko force-pushed the 2111-fuzzIntAmt branch from fa29302 to faff961 Compare November 2, 2021 13:54

maflcko force-pushed the 2111-fuzzIntAmt branch from faff961 to fa13888 Compare November 2, 2021 14:06

DrahtBot mentioned this pull request Nov 2, 2021

refactor: Make CWalletTx sync state type-safe #21206

Merged

maflcko mentioned this pull request Nov 2, 2021

Fix signed integer overflow in prioritisetransaction RPC #23418

Merged

shaavan approved these changes Nov 3, 2021

View reviewed changes

laanwj reviewed Nov 10, 2021

View reviewed changes

src/node/coinstats.cpp Outdated Show resolved Hide resolved

maflcko force-pushed the 2111-fuzzIntAmt branch from fa13888 to fa4a86e Compare November 10, 2021 17:50

shaavan approved these changes Nov 12, 2021

View reviewed changes

DrahtBot added the Needs rebase label Nov 25, 2021

maflcko force-pushed the 2111-fuzzIntAmt branch from fa4a86e to fa72733 Compare November 26, 2021 09:43

DrahtBot removed the Needs rebase label Nov 26, 2021

shaavan approved these changes Nov 26, 2021

View reviewed changes

vasild reviewed Dec 17, 2021

View reviewed changes

src/rpc/blockchain.cpp Outdated Show resolved Hide resolved

src/rpc/blockchain.cpp Outdated Show resolved Hide resolved

src/test/util_tests.cpp Outdated Show resolved Hide resolved

MarcoFalke added 4 commits December 17, 2021 10:39

style: Remove unused whitespace

faff051

Add dev doc to CCoinsStats::m_hash_type and make it const

fa526d8

Move AdditionOverflow to util, Add CheckedAdd with unit tests

fac0188

refactor: Avoid integer overflow in ApplyStats when activating snapshot

fa996c5

maflcko force-pushed the 2111-fuzzIntAmt branch from fa72733 to fa996c5 Compare December 17, 2021 09:48

shaavan approved these changes Dec 17, 2021

View reviewed changes

vasild approved these changes Dec 17, 2021

View reviewed changes

maflcko merged commit e31cdb0 into bitcoin:master Jan 5, 2022

maflcko deleted the 2111-fuzzIntAmt branch January 5, 2022 09:38

bitcoin locked and limited conversation to collaborators Jan 5, 2023

refactor: Avoid integer overflow in ApplyStats when activating snapshot #23411

refactor: Avoid integer overflow in ApplyStats when activating snapshot #23411

Uh oh!

Conversation

maflcko commented Nov 1, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

maflcko commented Nov 1, 2021

Uh oh!

sipa commented Nov 1, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

maflcko commented Nov 1, 2021

Uh oh!

jamesob commented Nov 1, 2021

Uh oh!

maflcko commented Nov 1, 2021

Uh oh!

sipa commented Nov 1, 2021

Uh oh!

DrahtBot commented Nov 1, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

maflcko commented Nov 2, 2021

Uh oh!

shaavan left a comment

Choose a reason for hiding this comment

Uh oh!

maflcko commented Nov 2, 2021

Uh oh!

luke-jr commented Nov 2, 2021

Uh oh!

maflcko commented Nov 2, 2021

Uh oh!

shaavan left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

shaavan left a comment

Choose a reason for hiding this comment

Uh oh!

shaavan left a comment

Choose a reason for hiding this comment

Uh oh!

vasild left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

maflcko commented Dec 17, 2021

Uh oh!

shaavan left a comment

Choose a reason for hiding this comment

Uh oh!

vasild left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

maflcko commented Nov 1, 2021 •

edited

Loading

sipa commented Nov 1, 2021 •

edited

Loading

DrahtBot commented Nov 1, 2021 •

edited

Loading