Fix signed integer overflow in prioritisetransaction RPC

MarcoFalke commented at 7:41 pm on November 2, 2021: member

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:

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

Reproduce on RPC

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

By fuzzing

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

DrahtBot added the label Build system on Nov 2, 2021

DrahtBot added the label Mempool on Nov 2, 2021

DrahtBot added the label RPC/REST/ZMQ on Nov 2, 2021

DrahtBot added the label Utils/log/libs on Nov 2, 2021

DrahtBot commented at 0:06 am on November 3, 2021: member

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.

MarcoFalke removed the label Build system on Nov 3, 2021

MarcoFalke removed the label Utils/log/libs on Nov 3, 2021

MarcoFalke marked this as ready for review on Nov 3, 2021

DrahtBot added the label Needs rebase on Nov 3, 2021

PastaPastaPasta commented at 8:22 pm on November 3, 2021: contributor

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 )

in src/txmempool.cpp:69 in e8522d082e outdated

22@@ -22,6 +23,22 @@
23 #include <cmath>
24 #include <optional>
25 
26+template <typename T>
27+static void MaybeAdd(T& mut, const T& apply)

vasild commented at 11:07 am on November 4, 2021:

In this interface the function may or may not add the second argument to the first and it does not signal to the caller which one of the two it did. I find this puzzling. Surely the caller needs to take a different action depending on whether the two numbers can be summed or not? If the caller does not care and takes the same action either way, and the code is still correct, then why bother and not just skip calling MaybeAdd() altogether? (if not adding is also ok)

Or, if this is used in some kind of blurred logic where everything is ok, is it not better for the sum to produce numeric_limits<T>::max() in case of an overflow? E.g. if summing char 100 + 30 to produce 127 instead of 100?

To me it would be more logical to check for an overflow and take the appropriate action if one would occur, even if that is to abort() the program. We have types that are wide enough to ensure that overflow “never” occurs, or if it occurs then abort()ing is justified. Something like:

0template <typename T>
1T SumOrDie(T x, T y)
2{
3    assert(!AddOverflows(x, y));
4    assert(!AddUnderflows(x, y));
5    return x + y;
6}

MarcoFalke commented at 10:15 am on February 22, 2022:

We can’t abort here. Otherwise it might be possible for remote peers to shut down your node. Even if it wasn’t P2P exploitable and only RPC exploitable, an RPC call should never crash the process either (unless it triggers a bug in the consensus engine). See documentation of CheckNonFatal.

The caller does care about the result of the calculation. However, values so large that they overflow 64-bits are not supported by Bitcoin Core. Thus, we can pick any behaviour we want to deal with it.

MarcoFalke commented at 10:17 am on February 22, 2022:

Resolving discussion for now, but feel free to reply or reopen.

in src/txmempool.cpp:79 in e8522d082e outdated

32+        // the overflow caused by a prioritisetransaction RPC might only be
33+        // later hit when descendant txs are added to the mempool.
34+        // Since it is impossible to predict reliably, leave it up to the user
35+        // to use the RPC endpoint responsibly, considering their mempool
36+        // limits and usage patterns.
37+        return;

luke-jr commented at 5:41 pm on November 8, 2021:

This ignores the fee delta when it would otherwise overflow, which seems like incorrect behaviour. Shouldn’t we just set mut to the max value?

MarcoFalke commented at 10:11 am on February 22, 2022:

thanks, done

luke-jr changes_requested

MarcoFalke force-pushed on Jan 5, 2022

DrahtBot removed the label Needs rebase on Jan 5, 2022

PastaPastaPasta commented at 9:27 am on February 7, 2022: contributor

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?

MarcoFalke marked this as a draft on Feb 7, 2022

MarcoFalke commented at 1:27 pm on February 7, 2022: member

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

MarcoFalke referenced this in commit e44423c9d3 on Feb 21, 2022

MarcoFalke marked this as ready for review on Feb 22, 2022

MarcoFalke force-pushed on Feb 22, 2022

in src/txmempool.cpp:499 in fabaeaff2c outdated

495@@ -496,7 +496,7 @@ void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry, setEntries &setAnces
496     CAmount delta{0};
497     ApplyDelta(entry.GetTx().GetHash(), delta);
498     if (delta) {
499-            mapTx.modify(newit, update_fee_delta(delta));
500+        mapTx.modify(newit, update_modify_fee(delta));

glozow commented at 1:33 pm on February 25, 2022:

Since you’re touching anyway, might as well update this to use a lambda (now that we’re not pre-C++11 anymore), and we can delete the update_modify_fee struct. Similar to e177fcab3831b6d259da5164cabedcc9e78f6957

0        mapTx.modify(newit, [&delta](CTxMemPoolEntry& e) { e.UpdateModifyFee(delta); });

(Same suggestion to L935)

MarcoFalke commented at 12:11 pm on March 29, 2022:

Thx, already fixed in master.

glozow commented at 1:40 pm on February 25, 2022: member

concept ACK faa69b3876ac18d2ec69d6ac28468144d98ebceb

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.

in src/txmempool.cpp:65 in faa69b3876 outdated

64-    void operator() (CTxMemPoolEntry &e) { e.UpdateFeeDelta(feeDelta); }
65+    void operator()(CTxMemPoolEntry& e) { e.UpdateModifyFee(modify_fee); }
66 
67 private:
68-    int64_t feeDelta;
69+    CAmount modify_fee;

vasild commented at 1:57 pm on February 25, 2022:

nit:

0    const CAmount modify_fee;

MarcoFalke commented at 12:11 pm on March 29, 2022:

Thx, already fixed in master.

in src/txmempool.cpp:93 in faa69b3876 outdated

 99@@ -99,11 +100,11 @@ CTxMemPoolEntry::CTxMemPoolEntry(const CTransactionRef& tx, CAmount fee,
100       nModFeesWithAncestors{nFee},
101       nSigOpCostWithAncestors{sigOpCost} {}
102 
103-void CTxMemPoolEntry::UpdateFeeDelta(int64_t newFeeDelta)
104+void CTxMemPoolEntry::UpdateModifyFee(CAmount modify_fee)

vasild commented at 2:03 pm on February 25, 2022:

I find the name UpdateModifyFee() confusing because both Update and Modify are verbs. What about UpdateModifiedFee(CAmount delta)? Or diff instead of delta? The member variable is called “modified_fee”. Or maybe even use Increment instead of Update in the name because we are doing += (surely, incrementing with a negative number is actually decrementing).

(if you decide to change the name, the same change should be done to the name of struct update_modify_fee)

MarcoFalke commented at 12:26 pm on March 29, 2022:

Thx, changed to UpdateModifiedFee(fee_diff) as suggested.

in src/txmempool.h:104 in faa69b3876 outdated

100@@ -101,7 +101,7 @@ class CTxMemPoolEntry
101     const unsigned int entryHeight; //!< Chain height when entering the mempool
102     const bool spendsCoinbase;      //!< keep track of transactions that spend a coinbase
103     const int64_t sigOpCost;        //!< Total sigop cost
104-    int64_t feeDelta{0};            //!< Used for determining the priority of the transaction for mining in a block
105+    CAmount modified_fee{nFee};     //!< Used for determining the priority of the transaction for mining in a block

vasild commented at 2:18 pm on February 25, 2022:

I think it is better to initialize modified_fee where the rest of the members are initialized:

 0CTxMemPoolEntry::CTxMemPoolEntry(const CTransactionRef& tx, CAmount fee,
 1                                 int64_t time, unsigned int entry_height,
 2                                 bool spends_coinbase, int64_t sigops_cost, LockPoints lp)
 3    : tx{tx},
 4      nFee{fee},
 5      nTxWeight(GetTransactionWeight(*tx)),
 6      nUsageSize{RecursiveDynamicUsage(tx)},
 7      nTime{time},
 8      entryHeight{entry_height},
 9      spendsCoinbase{spends_coinbase},
10      sigOpCost{sigops_cost},
11      lockPoints{lp},
12      nSizeWithDescendants{GetTxSize()},
13      nModFeesWithDescendants{nFee},
14      nSizeWithAncestors{GetTxSize()},
15      nModFeesWithAncestors{nFee},
16      nSigOpCostWithAncestors{sigOpCost} {}

MarcoFalke commented at 12:30 pm on March 29, 2022:

Thx, done

in src/txmempool.cpp:500 in faa69b3876 outdated

496@@ -496,7 +497,7 @@ void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry, setEntries &setAnces
497     CAmount delta{0};
498     ApplyDelta(entry.GetTx().GetHash(), delta);
499     if (delta) {
500-            mapTx.modify(newit, update_fee_delta(delta));
501+        mapTx.modify(newit, update_modify_fee(delta));

vasild commented at 2:48 pm on February 25, 2022:

This looks wrong.

Lets say nFee is 100.

Before this PR we would store feeDelta=5 to designate a modified fee of 105. Lets say this code wants to change that to a modified fee of 107. Then this delta argument here would be 7. In this case, inside the old CTxMemPoolEntry::UpdateFeeDelta() the variables nModFeesWithDescendants and nModFeesWithAncestors would be incremented with 2, and 7 would be stored in feeDelta (to designate a modified fee of 107 (nFee=100 plus feeDelta=7).

After this PR we would store modified_fee=105 to designate a modified fee of 105. Then this code gets executed with argument delta=7. The new CTxMemPoolEntry::UpdateModifyFee() would increment the variables nModFeesWithDescendants and nModFeesWithAncestors with 7 (not with 2 as before) and would store 105+7=112 in modified_fee to designate a modified fee of 112 (not 107).

Either this call site, or the method UpdateModifyFee() has to be changed in order to keep the same behavior, or I miss something. I think the other call site of UpdateModifyFee() is correct.

MarcoFalke commented at 12:35 pm on March 29, 2022:

This code path is for newly added txs. Thus, nFee is always equal to modified_fee before this call to update the fee. It is not possible to execute this code for txs that have already been added, whose fee is modified repeatedly.

Luckily we have tests to catch this.

If I am missing something, it might be good if you write a test (or explain steps to reproduce).

vasild commented at 2:26 pm on March 30, 2022:

Ok, so the behavior of the code before and after this PR is the same only in the case where feeDelta is 0 (old code) / nFee is equal to modified_fee (new code). It is quite obscure to me whether this code is executed only for such cases (and will always be in the future). What about adding an assert to ensure that:

0     if (delta) {
1-        mapTx.modify(newit, [&delta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(delta); });
2+        mapTx.modify(newit, [&delta](CTxMemPoolEntry& e) {
3+            assert(e.GetFee() == e.GetModifiedFee());
4+            e.UpdateModifiedFee(delta);
5+        });
6     }

or, to preserve the behavior in all cases, not just when feeDelta=0:

0     if (delta) {
1-        mapTx.modify(newit, [&delta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(delta); });
2+        mapTx.modify(newit, [&delta](CTxMemPoolEntry& e) {
3+            e.UpdateModifiedFee(e.GetModifiedFee() - e.GetFee() + delta);
4+        });
5     }

I would be more comfortable with the second variant as it preserves the behavior in all cases and there is no chance that a newly added assert is too strong and is triggered unintentionally by a legit code.

MarcoFalke commented at 2:44 pm on March 30, 2022:

I don’t like the second variant, because it makes the code more verbose and confusing. Also, it will lead to signed integer overflow (the thing that this pull is trying to solve).

MarcoFalke commented at 8:33 am on March 31, 2022:

I’ve pushed a documention update to make it clearer along with an Assume. I don’t think an assert is the right thing to pick here. It seems incredibly unlikely that someone is going to modify the code while violating the assumption and at the same time have passing tests (hopefully added in the same patch that modifies the code). So I am also happy to remove the Assume again, if deemed useless.

vasild commented at 10:26 am on March 31, 2022:

Ok, IMO it is better with the Assume() compared to without any protection.

This call site is kind of misusing the UpdateModifiedFee() method whose semantic is to alter the existent value with a provided delta, while this call site is actually trying to set the value. It works as long as the value is 0 here, before the call.

What about introducing a new method to set the modified fee and use it here?

0void CTxMemPoolEntry::SetModifiedFee(CAmount modified_fee_)
1{
2    nModFeesWithDescendants = modified_fee_;
3    nModFeesWithAncestors = modified_fee_;
4    modified_fee = modified_fee_;
5}

Or check that what we intended was actually done correctly afterwards:

0     if (delta) {
1         mapTx.modify(newit, [&delta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(delta); });
2+        Assume(entry.GetModifiedFee() == SaturatingAdd(entry.GetFee(), delta));
3     }

MarcoFalke commented at 1:51 pm on March 31, 2022:

I think it is fine to call UpdateModifiedFee to set the initial fee update. Introducing a new method doesn’t allow to get rid of the Assumption that the fee wasn’t previously modified.

Happy to move the Assume/comment after the mapTx.modify call.

MarcoFalke commented at 6:12 am on June 10, 2022:

Closing thread for now. Let me know if I should reopen.

DrahtBot added the label Needs rebase on Mar 24, 2022

MarcoFalke force-pushed on Mar 25, 2022

MarcoFalke closed this on Mar 25, 2022

MarcoFalke reopened this on Mar 25, 2022

MarcoFalke force-pushed on Mar 25, 2022

DrahtBot removed the label Needs rebase on Mar 25, 2022

MarcoFalke force-pushed on Mar 25, 2022

MarcoFalke force-pushed on Mar 29, 2022

MarcoFalke commented at 12:35 pm on March 29, 2022: member

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

MarcoFalke force-pushed on Mar 31, 2022

in src/txmempool.h:104 in fac053d9d8 outdated

100@@ -101,7 +101,7 @@ class CTxMemPoolEntry
101     const unsigned int entryHeight; //!< Chain height when entering the mempool
102     const bool spendsCoinbase;      //!< keep track of transactions that spend a coinbase
103     const int64_t sigOpCost;        //!< Total sigop cost
104-    CAmount feeDelta{0};            //!< Used for determining the priority of the transaction for mining in a block
105+    CAmount modified_fee;           //!< Used for determining the priority of the transaction for mining in a block

vasild commented at 9:38 am on March 31, 2022:

naming:

0    CAmount m_modified_fee;           //!< Used for determining the priority of the transaction for mining in a block

MarcoFalke commented at 1:51 pm on March 31, 2022:

thx, fixed.

vasild approved

vasild commented at 10:28 am on March 31, 2022: member

ACK fac053d9d883ed87707b62f87ab107d41d9cdf50

Consider #23418 (review)

MarcoFalke force-pushed on Mar 31, 2022

vasild approved

vasild commented at 2:10 pm on March 31, 2022: member

ACK fa471a7ae273d3bf8f956e8a862d0b586dd3fe4b

MarcoFalke added this to the milestone 24.0 on Apr 27, 2022

laanwj added this to the "Blockers" column in a project

in src/txmempool.cpp:95 in fa42c09ba2 outdated

90       nSizeWithAncestors{GetTxSize()},
91       nModFeesWithAncestors{nFee},
92       nSigOpCostWithAncestors{sigOpCost} {}
93 
94-void CTxMemPoolEntry::UpdateFeeDelta(CAmount newFeeDelta)
95+void CTxMemPoolEntry::UpdateModifiedFee(CAmount fee_diff)

LarryRuane commented at 5:05 am on June 22, 2022:

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.

MarcoFalke commented at 7:28 am on June 22, 2022:

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.

in src/txmempool.cpp:925 in fa42c09ba2 outdated

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

LarryRuane commented at 5:09 am on June 22, 2022:

delta is now unused

MarcoFalke commented at 7:30 am on June 22, 2022:

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

LarryRuane commented at 5:39 am on June 22, 2022: contributor

Rebased onto latest master (7377ed778c6d832ecd291e65b2789af7bac2ae2b), 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/.

refactor: Replace feeDelta by m_modified_fee

* 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.

fa52cf8e11

Fix signed integer overflow in prioritisetransaction RPC fa07f84e31

MarcoFalke force-pushed on Jun 22, 2022

MarcoFalke commented at 7:36 am on June 22, 2022: member

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 approved

vasild commented at 12:48 pm on June 22, 2022: member

ACK fa07f84e316171d60dd9941fb8db37e0a0de6654

dunxen approved

dunxen commented at 5:09 pm on June 22, 2022: contributor

ACK fa07f84

michaelfolkson commented at 6:15 pm on June 22, 2022: contributor

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 commented at 8:01 pm on June 22, 2022: contributor

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

MarcoFalke merged this on Jun 27, 2022

MarcoFalke closed this on Jun 27, 2022

MarcoFalke deleted the branch on Jun 27, 2022

sidhujag referenced this in commit 758481e22d on Jun 27, 2022

DrahtBot locked this on Jun 27, 2023

Fix signed integer overflow in prioritisetransaction RPC #23418

Steps to reproduce

Reproduce on RPC

By fuzzing

Conflicts