Fix signed integer overflow in prioritisetransaction RPC #23418

maflcko · 2021-11-02T19:41:18Z

Signed integer overflow is UB in theory, but not in practice. Still,
it would be nice to avoid this UB to allow Bitcoin Core to be
compiled with sanitizers such as -ftrapv or ubsan.

It is impossible to predict when and if an overflow occurs, since
the overflow caused by a prioritisetransaction RPC might only be
later hit when descendant txs are added to the mempool.
Since it is impossible to predict reliably, leave it up to the user
to use the RPC endpoint responsibly, considering their mempool
limits and usage patterns.

Fixes: #20626
Fixes: #20383
Fixes: #19278
Fixes: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=34146 / https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=47132

Steps to reproduce

Build the code without the changes in this pull.

Make sure to pass the sanitizer flag:

./autogen.sh && ./configure --with-sanitizers=signed-integer-overflow && make clean && make -j $(nproc)

Reproduce on RPC

./src/bitcoind -chain=regtest -noprinttoconsole &
./src/bitcoin-cli -chain=regtest prioritisetransaction 00000000deadbeef00000000deadbeef00000000deadbeef00000000deadbeef 0 9123456789123456789
./src/bitcoin-cli -chain=regtest prioritisetransaction 00000000deadbeef00000000deadbeef00000000deadbeef00000000deadbeef 0 9123456789123456789
|> txmempool.cpp:920:15: runtime error: signed integer overflow: 9123456789123456789 + 9123456789123456789 cannot be represented in type 'long int'

./src/bitcoin-cli -chain=regtest stop

By fuzzing

wget https://github.com/bitcoin/bitcoin/files/8921302/clusterfuzz-testcase-minimized-validation_load_mempool-5599531390074880.bin.txt
FUZZ=validation_load_mempool ./src/test/fuzz/fuzz ./clusterfuzz-testcase-minimized-validation_load_mempool-5599531390074880.bin.txt 
|> txmempool.cpp:920:15: runtime error: signed integer overflow: 7214801925397553184 + 2314885530818453536 cannot be represented in type 'long int'
|> validation_load_mempool: succeeded against 1 files in 0s.

DrahtBot · 2021-11-03T00:06:25Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#17786 (refactor: Nuke policy/fees->mempool circular dependencies by hebasto)

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.

PastaPastaPasta

See https://godbolt.org/z/aWTKcM6db, I have a couple of suggestions:

make TestAdd, TestAddMatrixOverflow, TestAddMatrix and AdditionOverflow constexpr b/c why not
Consider replacing MaybeAdd with my implementation of MaybeAddRet, which returns a value instead of mutating a mutable reference, which enables MaybeAddRet to be constexpr. (they appear virtually equally efficient, especially when we take into account we'll be using trivial types with this) (I also think this just makes more sense for a function called "MaybeAdd" as opposed to "MaybeAddEquals" or smth else)
Consider adding a static_assert(std::is_trivial<T>::value); to ensure we only are using trivial types

(also, I see that you weren't really asking for a review, but I just saw the PR and started poking around :D )

src/txmempool.cpp

PastaPastaPasta · 2022-02-07T09:27:00Z

See https://godbolt.org/z/aWTKcM6db, I have a couple of suggestions:

make TestAdd, TestAddMatrixOverflow, TestAddMatrix and AdditionOverflow constexpr b/c why not

Consider replacing MaybeAdd with my implementation of MaybeAddRet, which returns a value instead of mutating a mutable reference, which enables MaybeAddRet to be constexpr. (they appear virtually equally efficient, especially when we take into account we'll be using trivial types with this) (I also think this just makes more sense for a function called "MaybeAdd" as opposed to "MaybeAddEquals" or smth else)

Consider adding a static_assert(std::is_trivial<T>::value); to ensure we only are using trivial types

(also, I see that you weren't really asking for a review, but I just saw the PR and started poking around :D )

@MarcoFalke do you have an opinion about these suggestions?

maflcko · 2022-02-07T13:27:11Z

Yeah, MaybeAdd will be removed, in which case the suggestions won't apply.

faa7d8a util: Add SaturatingAdd helper (MarcoFalke) Pull request description: Seems good to have this in the repo, as it might be needed to write cleaner code. For example: * bitcoin/bitcoin#24090 (comment) * bitcoin/bitcoin#23418 (comment) * ... ACKs for top commit: MarcoFalke: Added a test. Should be trivial to re-ACK with `git range-diff bitcoin-core/master fa90189cbf faa7d8a` klementtan: reACK faa7d8a vasild: ACK faa7d8a Tree-SHA512: d0e6efdba7dfcbdd16ab4539a7f5e45a97d17792e42586c3c52caaae3fc70612dc9e364359658de5de5718fb8c2a765a59ceb2230098355394fa067a9732bc2a

glozow

concept ACK faa69b3

Very nice to get rid of a sanitizer suppression, and the fee delta for modified fees should be a CAmount anyway. I have a small suggestion which is not really within scope of this PR, so feel freee to ignore.

src/txmempool.cpp

src/txmempool.h

src/txmempool.cpp

maflcko · 2022-03-29T12:35:46Z

Rebased and replied to all comments. Also changed the name of the update function.

src/txmempool.h

src/txmempool.cpp

vasild

ACK fac053d

Consider #23418 (comment)

vasild

ACK fa471a7

LarryRuane

Rebased onto latest master (7377ed7), was able to reproduce the bug both using RPC and fuzzing, and the bug is fixed using the PR (both ways).

You could make a couple of small fixes in the description: dot before /autogen.sh, and add -chain=regtest to the bitcoin-cli command lines.

In the first commit message, s/tacked/tracked/.

LarryRuane · 2022-06-22T05:05:46Z

src/txmempool.cpp

      lockPoints{lp},
      nSizeWithDescendants{GetTxSize()},
      nModFeesWithDescendants{nFee},
      nSizeWithAncestors{GetTxSize()},
      nModFeesWithAncestors{nFee},
      nSigOpCostWithAncestors{sigOpCost} {}

-void CTxMemPoolEntry::UpdateFeeDelta(CAmount newFeeDelta)
+void CTxMemPoolEntry::UpdateModifiedFee(CAmount fee_diff)


Would a better name be IncrementModifiedFee? The verb "update" isn't wrong, but it could mean simply setting a variable to a value (as in a simple assignment statement). The verb "increment" makes it clear that a variable, or, in this case, 3 variables, are being incremented by the argument. It's true that the previous name used the verb "update", so maybe it would be best to preserve that. But I just thought I'd mention it for consideration.

I agree, but maybe this can be done as a follow up to also rename the Update*State functions, which do the same thing, but are not touched in this pull request.

LarryRuane · 2022-06-22T05:09:56Z

src/txmempool.cpp

@@ -921,7 +925,7 @@ void CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeD
        delta += nFeeDelta;


delta is now unused

delta is a mutable reference, so while the symbol itself isn't used after this line, the line can not be removed.

* feeDelta tracked the delta (to be applied on top of the actual fee) * m_modified_fee tracks the actual fee with the delta included * Instead of passing in the new total delta to the Updater, pass in by how much the total delta should be modified. This is needed for the next commit, but makes sense on its own because the same is done by UpdateDescendantState and UpdateAncestorState.

maflcko · 2022-06-22T07:36:19Z

In the first commit message, s/tacked/tracked/.

Thx, done. Also rebased to make testing easier. Should be trivial to re-ACK with git range-diff.

vasild

ACK fa07f84

dunxen

ACK fa07f84

michaelfolkson · 2022-06-22T18:15:07Z

Concept ACK, Approach ACK.

The saturating approach (as discussed in today's PR review club) makes sense over alternative approaches. Reviewed code changes, didn't test unfortunately.

LarryRuane

ACK fa07f84
I reproduced the bug on master both using RPC and fuzzing, and the bug is fixed using the PR (both ways)/

…tion RPC fa07f84 Fix signed integer overflow in prioritisetransaction RPC (MarcoFalke) fa52cf8 refactor: Replace feeDelta by m_modified_fee (MarcoFalke) Pull request description: Signed integer overflow is UB in theory, but not in practice. Still, it would be nice to avoid this UB to allow Bitcoin Core to be compiled with sanitizers such as `-ftrapv` or ubsan. It is impossible to predict when and if an overflow occurs, since the overflow caused by a prioritisetransaction RPC might only be later hit when descendant txs are added to the mempool. Since it is impossible to predict reliably, leave it up to the user to use the RPC endpoint responsibly, considering their mempool limits and usage patterns. Fixes: bitcoin#20626 Fixes: bitcoin#20383 Fixes: bitcoin#19278 Fixes: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=34146 / https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=47132 ## Steps to reproduce Build the code without the changes in this pull. Make sure to pass the sanitizer flag: ``` ./autogen.sh && ./configure --with-sanitizers=signed-integer-overflow && make clean && make -j $(nproc) ``` ### Reproduce on RPC ``` ./src/bitcoind -chain=regtest -noprinttoconsole & ./src/bitcoin-cli -chain=regtest prioritisetransaction 00000000deadbeef00000000deadbeef00000000deadbeef00000000deadbeef 0 9123456789123456789 ./src/bitcoin-cli -chain=regtest prioritisetransaction 00000000deadbeef00000000deadbeef00000000deadbeef00000000deadbeef 0 9123456789123456789 |> txmempool.cpp:920:15: runtime error: signed integer overflow: 9123456789123456789 + 9123456789123456789 cannot be represented in type 'long int' ./src/bitcoin-cli -chain=regtest stop ``` ### By fuzzing ``` wget https://github.com/bitcoin/bitcoin/files/8921302/clusterfuzz-testcase-minimized-validation_load_mempool-5599531390074880.bin.txt FUZZ=validation_load_mempool ./src/test/fuzz/fuzz ./clusterfuzz-testcase-minimized-validation_load_mempool-5599531390074880.bin.txt |> txmempool.cpp:920:15: runtime error: signed integer overflow: 7214801925397553184 + 2314885530818453536 cannot be represented in type 'long int' |> validation_load_mempool: succeeded against 1 files in 0s. ACKs for top commit: vasild: ACK fa07f84 dunxen: ACK fa07f84 LarryRuane: ACK fa07f84 Tree-SHA512: 4a357950af55a49c9113da0a50c2e743c5b752f0514dd8d16cd92bfde2f77dd0ef56aa98452626df6f7f7a5b51d1227021f6bc94091201a179f0d488ee32a0df

maflcko mentioned this pull request Nov 2, 2021

Avoid signed integer overflow and invalid integer negation when loading malformed mempool.dat files #20383

Closed

DrahtBot added Build system Mempool RPC/REST/ZMQ Utils/log/libs labels Nov 2, 2021

This was referenced Nov 3, 2021

refactor: move update_* structs from txmempool.h to .cpp file #23211

Merged

Add fee rate distribution in -getinfo #22891

Closed

Add feerate histogram to getmempoolinfo #21422

Closed

refactor: Make CWalletTx sync state type-safe #21206

Merged

maflcko removed Build system Utils/log/libs labels Nov 3, 2021

maflcko marked this pull request as ready for review November 3, 2021 08:00

DrahtBot added the Needs rebase label Nov 3, 2021

PastaPastaPasta reviewed Nov 3, 2021

View reviewed changes

vasild reviewed Nov 4, 2021

View reviewed changes

src/txmempool.cpp Outdated Show resolved Hide resolved

luke-jr suggested changes Nov 8, 2021

View reviewed changes

src/txmempool.cpp Outdated Show resolved Hide resolved

maflcko force-pushed the 2111-txPoolPrioOverflow branch from e8522d0 to fa108c3 Compare January 5, 2022 10:54

DrahtBot removed the Needs rebase label Jan 5, 2022

This was referenced Jan 5, 2022

Use int32_t type for most transaction size/weight values #23962

Merged

refactor: Nuke policy/fees->mempool circular dependencies #17786

Merged

maflcko mentioned this pull request Feb 1, 2022

util: Add SaturatingAdd helper #24224

Merged

maflcko marked this pull request as draft February 7, 2022 13:26

maflcko marked this pull request as ready for review February 22, 2022 10:00

maflcko force-pushed the 2111-txPoolPrioOverflow branch from fa108c3 to faa69b3 Compare February 22, 2022 10:04

glozow reviewed Feb 25, 2022

View reviewed changes

src/txmempool.cpp Outdated Show resolved Hide resolved

vasild reviewed Feb 25, 2022

View reviewed changes

src/txmempool.cpp Outdated Show resolved Hide resolved

src/txmempool.cpp Outdated Show resolved Hide resolved

src/txmempool.h Outdated Show resolved Hide resolved

src/txmempool.cpp Outdated Show resolved Hide resolved

maflcko force-pushed the 2111-txPoolPrioOverflow branch from faa69b3 to fa28736 Compare March 25, 2022 10:20

maflcko closed this Mar 25, 2022

maflcko reopened this Mar 25, 2022

maflcko force-pushed the 2111-txPoolPrioOverflow branch from fa28736 to fa46eec Compare March 25, 2022 10:39

DrahtBot removed the Needs rebase label Mar 25, 2022

maflcko force-pushed the 2111-txPoolPrioOverflow branch 4 times, most recently from fa131d5 to fa59aef Compare March 29, 2022 12:32

maflcko force-pushed the 2111-txPoolPrioOverflow branch 2 times, most recently from fa3d182 to fac053d Compare March 31, 2022 08:38

vasild reviewed Mar 31, 2022

View reviewed changes

src/txmempool.h Outdated Show resolved Hide resolved

src/txmempool.cpp Outdated Show resolved Hide resolved

vasild approved these changes Mar 31, 2022

View reviewed changes

maflcko force-pushed the 2111-txPoolPrioOverflow branch from fac053d to fa471a7 Compare March 31, 2022 13:48

vasild approved these changes Mar 31, 2022

View reviewed changes

maflcko added this to the 24.0 milestone Apr 27, 2022

LarryRuane reviewed Jun 22, 2022

View reviewed changes

MarcoFalke added 2 commits June 22, 2022 09:32

Fix signed integer overflow in prioritisetransaction RPC

fa07f84

maflcko force-pushed the 2111-txPoolPrioOverflow branch from fa471a7 to fa07f84 Compare June 22, 2022 07:34

vasild approved these changes Jun 22, 2022

View reviewed changes

dunxen approved these changes Jun 22, 2022

View reviewed changes

LarryRuane reviewed Jun 22, 2022

View reviewed changes

maflcko merged commit dde7205 into bitcoin:master Jun 27, 2022

maflcko deleted the 2111-txPoolPrioOverflow branch June 27, 2022 06:37

bitcoin locked and limited conversation to collaborators Jun 27, 2023

		@@ -921,7 +925,7 @@ void CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeD
		delta += nFeeDelta;

Fix signed integer overflow in prioritisetransaction RPC #23418

Fix signed integer overflow in prioritisetransaction RPC #23418

Uh oh!

Conversation

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

Uh oh!

Steps to reproduce

Reproduce on RPC

By fuzzing

Uh oh!

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

Uh oh!

Conflicts

Uh oh!

PastaPastaPasta left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

PastaPastaPasta commented Feb 7, 2022

Uh oh!

maflcko commented Feb 7, 2022

Uh oh!

glozow left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

maflcko commented Mar 29, 2022

Uh oh!

Uh oh!

Uh oh!

vasild 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!

LarryRuane left a comment

Choose a reason for hiding this comment

Uh oh!

LarryRuane Jun 22, 2022

Choose a reason for hiding this comment

Uh oh!

maflcko Jun 22, 2022

Choose a reason for hiding this comment

Uh oh!

LarryRuane Jun 22, 2022

Choose a reason for hiding this comment

Uh oh!

maflcko Jun 22, 2022

Choose a reason for hiding this comment

Uh oh!

maflcko commented Jun 22, 2022

Uh oh!

vasild left a comment

Choose a reason for hiding this comment

Uh oh!

dunxen left a comment

Choose a reason for hiding this comment

Uh oh!

michaelfolkson commented Jun 22, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

LarryRuane left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

maflcko commented Nov 2, 2021 •

edited

Loading

DrahtBot commented Nov 3, 2021 •

edited

Loading

PastaPastaPasta left a comment •

edited

Loading

michaelfolkson commented Jun 22, 2022 •

edited

Loading

LarryRuane left a comment •

edited

Loading