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

practicalswift commented at 3:11 pm on November 13, 2020: contributor

Closes #19278.

Avoid signed integer overflow when loading malformed mempool.dat files.

Avoid invalid integer negation when loading malformed mempool.dat files (or when processing prioritisetransaction RPC calls).

Add note about the valid range of inputs for FormatMoney(...).

Add test.

Before this patch:

 0$ xxd -p -r > mempool-signed-integer-overflow.dat << "EOF"
 101000000000000003f2d3f3f21f800000000000000000000000000000000
 26d697464657363656e64616e00000001000000ec000000003d6a6c000000
 3000000000000ec9bf601000000000000000000ec9b0001000000000001ff
 4fffef900000001000000ec0000000000ec9b000001000000000101000100
 500000001000000ec000000003d6a6a000000000000000020ec9b000000fa
 600
 7EOF
 8$ cp mempool-signed-integer-overflow.dat ~/.bitcoin/regtest/mempool.dat
 9$ UBSAN_OPTIONS="print_stacktrace=1:halt_on_error=1:report_error_type=1" src/bitcoind -regtest
10…
11txmempool.cpp:839:15: runtime error: signed integer overflow: -7211388903327006720 + -7211353718954917888 cannot be represented in type 'long'
12…

0$ xxd -p -r > mempool-invalid-negation.dat << "EOF"
10100000000000000002e000000005d2d000d020000000000000000000000
2200000000000000000000080fc0000002d
3EOF
4$ cp mempool-invalid-negation.dat ~/.bitcoin/regtest/mempool.dat
5$ UBSAN_OPTIONS="print_stacktrace=1:halt_on_error=1:report_error_type=1" src/bitcoind -regtest
6…
7util/moneystr.cpp:16:34: runtime error: negation of -9223372036854775808 cannot be represented in type 'CAmount' (aka 'long'); cast to an unsigned type to negate this value to itself
8…

After this patch:

 0$ xxd -p -r > mempool-signed-integer-overflow.dat << "EOF"
 101000000000000003f2d3f3f21f800000000000000000000000000000000
 26d697464657363656e64616e00000001000000ec000000003d6a6c000000
 3000000000000ec9bf601000000000000000000ec9b0001000000000001ff
 4fffef900000001000000ec0000000000ec9b000001000000000101000100
 500000001000000ec000000003d6a6a000000000000000020ec9b000000fa
 600
 7EOF
 8$ cp mempool-signed-integer-overflow.dat ~/.bitcoin/regtest/mempool.dat
 9$ UBSAN_OPTIONS="print_stacktrace=1:halt_on_error=1:report_error_type=1" src/bitcoind -regtest
10…
112020-11-13T12:34:56Z PrioritiseTransaction(...) failed. Invalid fee delta?
12…

0$ xxd -p -r > mempool-invalid-negation.dat << "EOF"
10100000000000000002e000000005d2d000d020000000000000000000000
2200000000000000000000080fc0000002d
3EOF
4$ cp mempool-invalid-negation.dat ~/.bitcoin/regtest/mempool.dat
5$ UBSAN_OPTIONS="print_stacktrace=1:halt_on_error=1:report_error_type=1" src/bitcoind -regtest
6…
72020-11-13T12:34:56Z PrioritiseTransaction(...) failed. Invalid fee delta?
8…

DrahtBot added the label Build system on Nov 13, 2020

DrahtBot added the label Mempool on Nov 13, 2020

DrahtBot added the label Mining on Nov 13, 2020

DrahtBot added the label RPC/REST/ZMQ on Nov 13, 2020

DrahtBot added the label Utils/log/libs on Nov 13, 2020

DrahtBot added the label Validation on Nov 13, 2020

in src/txmempool.cpp:841 in 38c331b124 outdated

831@@ -831,11 +832,17 @@ TxMempoolInfo CTxMemPool::info(const GenTxid& gtxid) const
832 
833 TxMempoolInfo CTxMemPool::info(const uint256& txid) const { return info(GenTxid{false, txid}); }
834 
835-void CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta)
836+bool CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta)
837 {
838+    if (nFeeDelta == std::numeric_limits<CAmount>::min()) {
839+        return false;
840+    }

luke-jr commented at 6:42 pm on November 13, 2020:

Why?

practicalswift commented at 9:50 pm on November 13, 2020:

Otherwise the following invalid integer negation will take place:

0util/moneystr.cpp:16:34: runtime error: negation of -9223372036854775808 cannot be represented in type 'CAmount' (aka 'long'); cast to an unsigned type to negate this value to itself
1    [#0](/bitcoin-bitcoin/0/) 0x55b386a14eac in FormatMoney[abi:cxx11](long const&) src/util/moneystr.cpp:16:34
2    [#1](/bitcoin-bitcoin/1/) 0x55b3861962f3 in CTxMemPool::PrioritiseTransaction(uint256 const&, long const&) src/txmempool.cpp:861:77

FormatMoney(CAmount n) is not defined for n == std::numeric_limits<CAmount>::min().

The negation of std::numeric_limits<CAmount>::min() (-9223372036854775808) cannot be represented in the type CAmount (int64_t).

To reproduce:

 0$ git checkout master
 1$ make -C src/ bitcoind
 2$ xxd -p -r > mempool-invalid-negation.dat << "EOF"
 30100000000000000002e000000005d2d000d020000000000000000000000
 4200000000000000000000080fc0000002d
 5EOF
 6$ cp mempool-invalid-negation.dat ~/.bitcoin/regtest/mempool.dat
 7$ UBSAN_OPTIONS="print_stacktrace=1:halt_on_error=1:report_error_type=1" src/bitcoind -regtest
 8…
 9util/moneystr.cpp:16:34: runtime error: negation of -9223372036854775808 cannot be represented in type 'CAmount' (aka 'long'); cast to an unsigned type to negate this value to itself
10…

practicalswift commented at 4:09 pm on November 19, 2020:

If the fix to FormayMoney in #20406 is applied we don’t have to have the restriction. I think that would be even better :)

DrahtBot commented at 8:11 pm on November 13, 2020: 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:

#21007 (bitcoind: Add -daemonwait option to wait for initialization by laanwj)
#20406 (util: Avoid invalid integer negation in FormatMoney and ValueFromAmount by practicalswift)

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.

in src/test/fuzz/util.h:29 in 6ab2080bd8 outdated

24@@ -25,6 +25,7 @@
25 #include <test/util/setup_common.h>
26 #include <txmempool.h>
27 #include <uint256.h>
28+#include <util/overflow.h>

luke-jr commented at 9:45 pm on November 13, 2020:

This needs to be in the parent commit

practicalswift commented at 10:14 pm on November 13, 2020:

Good point. Now fixed.

in src/rpc/mining.cpp:476 in 38c331b124 outdated

471@@ -472,7 +472,9 @@ static RPCHelpMan prioritisetransaction()
472         throw JSONRPCError(RPC_INVALID_PARAMETER, "Priority is no longer supported, dummy argument to prioritisetransaction must be 0.");
473     }
474 
475-    EnsureMemPool(request.context).PrioritiseTransaction(hash, nAmount);
476+    if (!EnsureMemPool(request.context).PrioritiseTransaction(hash, nAmount)) {
477+        throw JSONRPCError(RPC_MISC_ERROR, "PrioritiseTransaction failed.");

luke-jr commented at 9:48 pm on November 13, 2020:

Maybe a bit more verbosity here would be good.

practicalswift commented at 10:24 pm on November 13, 2020:

Now using a slightly more verbose error message which hints that an invalid fee_delta argument is the most likely cause. Let me know if you have any other suggestion on wording.

in src/validation.cpp:5031 in 38c331b124 outdated

5080@@ -5081,7 +5081,9 @@ bool LoadMempool(CTxMemPool& pool)
5081 
5082             CAmount amountdelta = nFeeDelta;
5083             if (amountdelta) {
5084-                pool.PrioritiseTransaction(tx->GetHash(), amountdelta);
5085+                if (!pool.PrioritiseTransaction(tx->GetHash(), amountdelta)) {
5086+                    LogPrintf("PrioritiseTransaction(...) failed. Invalid fee delta?\n");

luke-jr commented at 9:50 pm on November 13, 2020:

This should be literally impossible to hit based on invalid data…?

AFAICT, the only possibility is if the user manages to call prioritisetransaction RPC before it’s loaded the transaction in question

practicalswift commented at 10:12 pm on November 13, 2020:

It is possible, but don’t take my word for it. Take my PoC for it! :)

Proof of concept:

 0$ git checkout master
 1$ make -C src/ bitcoind
 2$ xxd -p -r > mempool-signed-integer-overflow.dat << "EOF"
 301000000000000003f2d3f3f21f800000000000000000000000000000000
 46d697464657363656e64616e00000001000000ec000000003d6a6c000000
 5000000000000ec9bf601000000000000000000ec9b0001000000000001ff
 6fffef900000001000000ec0000000000ec9b000001000000000101000100
 700000001000000ec000000003d6a6a000000000000000020ec9b000000fa
 800
 9EOF
10$ cp mempool-signed-integer-overflow.dat ~/.bitcoin/regtest/mempool.dat
11$ UBSAN_OPTIONS="print_stacktrace=1:halt_on_error=1:report_error_type=1" src/bitcoind -regtest
12…
13txmempool.cpp:839:15: runtime error: signed integer overflow: -7211388903327006720 + -7211353718954917888 cannot be represented in type 'long'
14    [#0](/bitcoin-bitcoin/0/) 0x556807f763ec in CTxMemPool::PrioritiseTransaction(uint256 const&, long const&) src/txmempool.cpp:839:15
15    [#1](/bitcoin-bitcoin/1/) 0x556807ff3c61 in LoadMempool(CTxMemPool&) src/validation.cpp:5084:22
16…

practicalswift force-pushed on Nov 13, 2020

in src/validation.cpp:5064 in bde46e38fd outdated

5113@@ -5112,7 +5114,9 @@ bool LoadMempool(CTxMemPool& pool)
5114         file >> mapDeltas;
5115 
5116         for (const auto& i : mapDeltas) {
5117-            pool.PrioritiseTransaction(i.first, i.second);
5118+            if (!pool.PrioritiseTransaction(i.first, i.second)) {
5119+                LogPrintf("PrioritiseTransaction(...) failed. Invalid fee delta?\n");

Crypt-iQ commented at 2:46 pm on November 14, 2020:

@practicalswift do you have a PoC for this one too? Just curious what the input looks like.

practicalswift commented at 11:43 am on November 15, 2020:

@Crypt-iQ Absolutely, your wish is my command: here you go! :)

Proof of concept:

 0$ git checkout master
 1$ make -C src/ bitcoind
 2$ xxd -p -r > mempool-poc-for-second-case-on-line-5115.dat << EOF
 30100000000000000010000000000000000000000000000003f0020202020
 4202020202020202020ff20ff016e2682a8e0af181ae4ffa4ce2fc42b1e3d
 58ce88019b194a45cd7c476b88ef1e220202020202020802020ff2020
 6EOF
 7$ cp mempool-poc-for-second-case-on-line-5115.dat ~/.bitcoin/regtest/mempool.dat
 8$ UBSAN_OPTIONS="print_stacktrace=1:halt_on_error=1:report_error_type=1" src/bitcoind -regtest
 9…
10txmempool.cpp:839:15: runtime error: signed integer overflow: -62769881340174304 + -9214329515250016224 cannot be represented in type 'long'
11    [#0](/bitcoin-bitcoin/0/) 0x5652ab2203ec in CTxMemPool::PrioritiseTransaction(uint256 const&, long const&) src/txmempool.cpp:839:15
12    [#1](/bitcoin-bitcoin/1/) 0x5652ab29e1ad in LoadMempool(CTxMemPool&) src/validation.cpp:5115:18
13…

:)

promag commented at 11:11 pm on November 15, 2020:

Add as a test?

practicalswift commented at 7:12 am on November 16, 2020:

@promag A fuzz test is added in #19259 (“tests: Add fuzzing harness for LoadMempool(…) and DumpMempool(…)”). Review welcome! :)

Crypt-iQ commented at 2:51 pm on November 14, 2020: contributor

crACK 2c61f90f047097fe372beb8bc8b4d779c66cd505

Will run my seeds against this patch.

promag commented at 11:12 pm on November 15, 2020: member

Concept ACK, change looks good to me.

practicalswift commented at 7:13 am on November 16, 2020: contributor

@promag A fuzz test is added in #19259 (“tests: Add fuzzing harness for LoadMempool(…) and DumpMempool(…)”). Review welcome! :)

DrahtBot added the label Needs rebase on Nov 30, 2020

practicalswift force-pushed on Nov 30, 2020

DrahtBot removed the label Needs rebase on Nov 30, 2020

in src/txmempool.cpp:845 in 1977f9d946 outdated

839+        return false;
840+    }
841     {
842         LOCK(cs);
843         CAmount &delta = mapDeltas[hash];
844+        if (AdditionOverflow(delta, nFeeDelta)) {

MarcoFalke commented at 9:22 am on January 14, 2021:

This check isn’t complete. You’d have to check all ancestors and descandants as well. Also, I don’t understand why this can’t be FeeDeltaRange https://github.com/bitcoin/bitcoin/pull/20089/files#r557249710

MarcoFalke commented at 7:52 pm on November 2, 2021:

Implemented an alternative that also checks all ancestors and descendants here: #23418

in src/rpc/mining.cpp:471 in 1977f9d946 outdated

466@@ -467,7 +467,9 @@ static RPCHelpMan prioritisetransaction()
467         throw JSONRPCError(RPC_INVALID_PARAMETER, "Priority is no longer supported, dummy argument to prioritisetransaction must be 0.");
468     }
469 
470-    EnsureMemPool(request.context).PrioritiseTransaction(hash, nAmount);
471+    if (!EnsureMemPool(request.context).PrioritiseTransaction(hash, nAmount)) {
472+        throw JSONRPCError(RPC_MISC_ERROR, "PrioritiseTransaction(...) failed. Invalid fee_delta argument?");

MarcoFalke commented at 9:25 am on January 14, 2021:

might be good to update the docs and release notes. Something like

 0diff --git a/src/amount.h b/src/amount.h
 1index 47968e80b1..9c770a8fe3 100644
 2--- a/src/amount.h
 3+++ b/src/amount.h
 4@@ -24,5 +24,6 @@ static const CAmount COIN = 100000000;
 5  * */
 6 static const CAmount MAX_MONEY = 21000000 * COIN;
 7 inline bool MoneyRange(const CAmount& nValue) { return (nValue >= 0 && nValue <= MAX_MONEY); }
 8+inline bool FeeDeltaRange(const CAmount& fee_delta) { return -MAX_MONEY <= fee_delta && fee_delta <= MAX_MONEY; }
 9 
10 #endif //  BITCOIN_AMOUNT_H
11diff --git a/src/rpc/mining.cpp b/src/rpc/mining.cpp
12index 0e96beb6db..181570807c 100644
13--- a/src/rpc/mining.cpp
14+++ b/src/rpc/mining.cpp
15@@ -444,14 +444,14 @@ static RPCHelpMan prioritisetransaction()
16                 {
17                     {"txid", RPCArg::Type::STR_HEX, RPCArg::Optional::NO, "The transaction id."},
18                     {"dummy", RPCArg::Type::NUM, RPCArg::Optional::OMITTED_NAMED_ARG, "API-Compatibility for previous API. Must be zero or null.\n"
19-            "                  DEPRECATED. For forward compatibility use named arguments and omit this parameter."},
20-                    {"fee_delta", RPCArg::Type::NUM, RPCArg::Optional::NO, "The fee value (in satoshis) to add (or subtract, if negative).\n"
21-            "                  Note, that this value is not a fee rate. It is a value to modify absolute fee of the TX.\n"
22-            "                  The fee is not actually paid, only the algorithm for selecting transactions into a block\n"
23-            "                  considers the transaction as it would have paid a higher (or lower) fee."},
24+                              "DEPRECATED. For forward compatibility use named arguments and omit this parameter."},
25+                    {"fee_delta", RPCArg::Type::NUM, RPCArg::Optional::NO, "The fee value (in satoshis) to add (or subtract, if negative). Must be in the range +-" + ToString(MAX_MONEY) + " sat.\n"
26+                              "Note, that this value is not a fee rate. It is a value to modify absolute fee of the TX.\n"
27+                              "The fee is not actually paid, only the algorithm for selecting transactions into a block\n"
28+                              "considers the transaction as it would have paid a higher (or lower) fee."},
29                 },
30                 RPCResult{
31-                    RPCResult::Type::BOOL, "", "Returns true"},
32+                    RPCResult::Type::BOOL, "", "Returns true or throws on error"},
33                 RPCExamples{
34                     HelpExampleCli("prioritisetransaction", "\"txid\" 0.0 10000")
35             + HelpExampleRpc("prioritisetransaction", "\"txid\", 0.0, 10000")
36@@ -460,14 +460,17 @@ static RPCHelpMan prioritisetransaction()
37 {
38     LOCK(cs_main);
39 
40-    uint256 hash(ParseHashV(request.params[0], "txid"));
41-    CAmount nAmount = request.params[2].get_int64();
42+    const uint256 hash(ParseHashV(request.params[0], "txid"));
43+    const CAmount nAmount = request.params[2].get_int64();
44 
45     if (!(request.params[1].isNull() || request.params[1].get_real() == 0)) {
46         throw JSONRPCError(RPC_INVALID_PARAMETER, "Priority is no longer supported, dummy argument to prioritisetransaction must be 0.");
47     }
48 
49-    EnsureMemPool(request.context).PrioritiseTransaction(hash, nAmount);
50+    CTxMemPool& mempool = EnsureMemPool(request.context);
51+    if (!mempool.PrioritiseTransaction(hash, nAmount)) {
52+        throw JSONRPCError(RPC_INVALID_PARAMETER, "Invalid fee_delta passed");
53+    }
54     return true;
55 },
56     };

MarcoFalke commented at 9:26 am on January 14, 2021: member

If you want to eliminate this issue completely, the diff would be quite invasive. So I am not sure if we want this. Maybe a note “pls don’t fuzz your rpc interface in production” is good enough?

practicalswift force-pushed on Jan 14, 2021

practicalswift commented at 2:06 pm on January 15, 2021: contributor

Maybe a note “pls don’t fuzz your rpc interface in production” is good enough?

I think we should try to make all our interfaces robust against crazy inputs. That includes our RPC interface :)

Where “robustness” includes being able to handle crazy inputs without triggering ASAN, MSAN, TSAN or UBSAN warnings.

In other words I think we should strive for handling crazy user input (UI robustness), crazy programmatic input (RPC robustness) and crazy network input (P2P robustness) without triggering sanitizer warnings.

Note that even if we didn’t care at all about robustness against crazy inputs in our RPC interface it is still makes perfect sense to fuzz the RPC interface since it is the broadest possible general “entry point” in to our application. By fuzzing the RPC interface we can reach large parts of our code base and uncover also non-RPC specific bugs.

MarcoFalke commented at 2:16 pm on January 15, 2021: member

Sure, when it is possible to add a simple check if the input is invalid, but here it requires changing the whole mempool package tracking code

felipsoarez commented at 11:39 pm on January 15, 2021: none

Concept ACK

DrahtBot added the label Needs rebase on Feb 8, 2021

util: Move AdditionOverflow(...) to new file src/util/overflow.h bbd79180d5

mempool: Avoid signed integer overflow in CTxMemPool::PrioritiseTransaction(...) c4258488c9

util: Add note about the valid range of inputs for FormatMoney(...) 7df8dbf9ba

tests: Test invalid fee delta check 1db76e1d86

mempool: Avoid signed integer overflow in CTxMemPool::PrioritiseTransaction(...) 7244d852d2

practicalswift force-pushed on Feb 11, 2021

DrahtBot removed the label Needs rebase on Feb 11, 2021

in src/amount.h:27 in 7244d852d2

23@@ -24,5 +24,6 @@ static const CAmount COIN = 100000000;
24  * */
25 static const CAmount MAX_MONEY = 21000000 * COIN;
26 inline bool MoneyRange(const CAmount& nValue) { return (nValue >= 0 && nValue <= MAX_MONEY); }
27+inline bool FeeDeltaRange(const CAmount& fee_delta) { return -MAX_MONEY <= fee_delta && fee_delta <= MAX_MONEY; }

luke-jr commented at 4:56 pm on February 28, 2021:

Fee deltas have no such range limit.

practicalswift commented at 6:15 pm on February 28, 2021:

Context: #20089 (review) + #20383 (review)

practicalswift closed this on Feb 28, 2021

practicalswift deleted the branch on Apr 10, 2021

MarcoFalke referenced this in commit dde7205c57 on Jun 27, 2022

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

DrahtBot locked this on Nov 2, 2022

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

Conflicts