refactor: Check for overflow when calculating sum of tx outputs #18383

elichai · 2020-03-19T13:58:37Z

This was reported by practicalswift here #18046
The exact order of the if, is important, we first do !MoneyRange(tx_out.nValue) to make sure the amount is non-negative. and then std::numeric_limits<CAmount>::max() - tx_out.nValue < nValueOut checks that the addition cannot overflow (if we won't check that the amount is positive this check can also overflow! (by doing something like max - -max))
and only then we make sure that the some is also valid !MoneyRange(nValueOut + tx_out.nValue)
if any of these conditions fail we throw.

the overflowing logic:

a + b > max // we want to fail if a+b is more than the maximum -> will overflow
b > max - a
max - a < b

Closes: #18046

laanwj · 2020-03-19T14:08:17Z

What is the concrete effect of this? Does this affect validation?

Can you please add a test that fails without this change?

elichai · 2020-03-19T14:12:15Z

What is the concrete effect of this? Does this affect validation?

Good question. technically this code is part of validation, it's called from tx_verify.cpp
I do not know if validation can ever execute this with an overflowing value, if so it's a real problem which is why I assume it probably can't. (i'll try writing a test now)
so if it can't happen and assuming this change is correct then this shouldn't affect validation itself

EDIT: Ok, testing it is a bit more complex, because this is only called on ConnectBlock or in mempool, so might take me some time, no rush.

maflcko · 2020-03-19T14:38:04Z

This is not possible to trigger from a network node or RPC, because CheckTransaction is called before CheckInputs is called. (This call order is also a requirement for other reasons)

maflcko · 2020-03-19T14:38:54Z

This was fixed in CVE-2010-5139

maflcko · 2020-03-19T14:41:37Z

I am pretty sure the compiler will optimize out the unused result anyway (and thus the overflow), but if you strongly feel like this needs to be fixed, then you could reorder the code, so that the overflow in the unused result never happens:

First check the output value with MoneyRange
Calculate the result
Check the result with MoneyRange

vasild · 2020-03-19T14:44:22Z

How could it overflow, given that CAmount is int64_t. Expressed in satoshi - about 4000 times more than the total supply of bitcoin?

maflcko · 2020-03-19T14:49:22Z

@vasild CAmount can be std::numeric_limits<CAmount>::max() or any other value in range for a serialized transaction. The deserialization code does not check for consensus rules.

practicalswift · 2020-03-19T15:46:01Z

Concept ACK: CTransaction::GetValueOut() should handle crazy amounts by throwing the expected exception. I think that was the intention behind the current code, so this is simply a bug AFAICT. (Luckily only reachable by the fuzzers at the moment (AFAICT).)

However, I think your fix can be simplified :)

Note that a + b cannot overflow if MoneyRange(a) == true and MoneyRange(b) == true. Where a and b are of type CAmount.

In other words, simply do if (!MoneyRange(a) || !MoneyRange(b)) { throw std::runtime_error(…); } and you should be safe to proceed with a += b? :)

Note that the MoneyRange(a + b) must obviously be checked too to make sure it is within the money bounds :)

Perhaps something along the lines of:

    if (!MoneyRange(a) || !MoneyRange(b) || !MoneyRange(a + b)) {
        throw std::runtime_error(…);
    }
    a += b;

practicalswift · 2020-03-19T16:05:01Z

@elichai

This is the fix I've used in my local fuzzing tree to avoid hitting this signed integer overflow over and over :)

diff --git a/src/primitives/transaction.cpp b/src/primitives/transaction.cpp
index 28c145f71..a1567e805 100644
--- a/src/primitives/transaction.cpp
+++ b/src/primitives/transaction.cpp
@@ -84,9 +84,10 @@ CAmount CTransaction::GetValueOut() const
 {
     CAmount nValueOut = 0;
     for (const auto& tx_out : vout) {
-        nValueOut += tx_out.nValue;
-        if (!MoneyRange(tx_out.nValue) || !MoneyRange(nValueOut))
+        if (!MoneyRange(nValueOut) || !MoneyRange(tx_out.nValue) || !MoneyRange(nValueOut + tx_out.nValue)) {
             throw std::runtime_error(std::string(__func__) + ": value out of range");
+        }
+        nValueOut += tx_out.nValue;
     }
     return nValueOut;
 }

Would love to see it upstreamed -- that would simplify my fuzzing setup :)

I agree with @laanwj that a test case which fails under UBSan prior to this PR should be included :)

practicalswift · 2020-03-19T16:20:25Z

@MarcoFalke

I am pretty sure the compiler will optimize out the unused result anyway (and thus the overflow)

What unused result are you referring to? :)

sipa · 2020-03-19T16:25:02Z

@practicalswift nValueOut is computed but never inspected in case tx_out.nValue is out of range.

practicalswift · 2020-03-19T16:43:09Z

@sipa

Ah, in @elichai's suggested fix. I thought @MarcoFalke meant in current master :)

The patch I'm suggesting in the comment above looks robust and correct?

vasild · 2020-03-20T14:05:51Z

The patch I'm suggesting in the comment above looks robust and correct?

Yes, and also more readable than the one in this PR (c5dd8eb625).

maflcko · 2020-03-20T14:11:28Z

I thought @MarcoFalke meant in current master :)

I do mean current master :)

as pointed out by pieter: "nValueOut is computed but never inspected in case tx_out.nValue is out of range." So I think the compiler will likely never produce a binary that computes nValueOut in the first place, or even if it did, it wouldn't matter because it is never read.

practicalswift · 2020-03-20T15:25:50Z

An even simpler patch which also tests the post-condition:

diff --git a/src/primitives/transaction.cpp b/src/primitives/transaction.cpp
index 28c145f71..76acb08b0 100644
--- a/src/primitives/transaction.cpp
+++ b/src/primitives/transaction.cpp
@@ -9,6 +9,8 @@
 #include <tinyformat.h>
 #include <util/strencodings.h>

+#include <cassert>
+
 std::string COutPoint::ToString() const
 {
     return strprintf("COutPoint(%s, %u)", hash.ToString().substr(0,10), n);
@@ -84,10 +86,11 @@ CAmount CTransaction::GetValueOut() const
 {
     CAmount nValueOut = 0;
     for (const auto& tx_out : vout) {
-        nValueOut += tx_out.nValue;
-        if (!MoneyRange(tx_out.nValue) || !MoneyRange(nValueOut))
+        if (!MoneyRange(tx_out.nValue) || !MoneyRange(nValueOut + tx_out.nValue))
             throw std::runtime_error(std::string(__func__) + ": value out of range");
+        nValueOut += tx_out.nValue;
     }
+    assert(MoneyRange(nValueOut));
     return nValueOut;
 }

instagibbs · 2020-03-20T18:12:51Z

I prefer @practicalswift solution above

elichai · 2020-03-21T14:21:16Z

as pointed out by pieter: "nValueOut is computed but never inspected in case tx_out.nValue is out of range." So I think the compiler will likely never compute nValueOut in the first place, or even if it did, it wouldn't matter because it is never read.

I honestly don't know if it's a problem overflowing without reading the value, probably isn't as you said.

An even simpler patch which also tests the post-condition:

It is a somewhat nicer fix :)

promag · 2020-03-23T11:56:47Z

I also prefer #18383 (comment).

elichai · 2020-03-23T12:05:16Z

@practicalswift do you wan to open a new PR with your suggestion? or should I replace my diff here with yours?

practicalswift · 2020-03-23T12:35:17Z

@elichai Feel free to use the patch I suggested. That way we'll keep the review to this PR and I can keep my work-in-progress PR count down :)

practicalswift · 2020-03-23T13:15:36Z

ACK a4c79f8cf6e0407f7e937fb41c73127f630231fa

instagibbs · 2020-03-23T13:22:47Z

utACK a4c79f8

practicalswift · 2020-03-23T15:21:26Z

src/primitives/transaction.cpp

 #include <tinyformat.h>
 #include <util/strencodings.h>

+#include <assert.h>


~~Nit: #include <assert.h> is deprecated in C++. Use the idiomatic form #include <cassert> :)~~

No need to invalidate ACK:s for this :)

maflcko · 2020-03-23T15:41:43Z

As pointed out earlier, this indeed is not an issue, because gcc will produce identical binaries for before this PR and after this PR. The overflow never happens.

ACK f65c9ad, checked that clang with O2 produces identical binaries 💕

Show signature and timestamp

Signature:

Timestamp of file with hash 25065ff511c22aa1d923f7b1fe85f03fe3fe6ee9ddaa063d16dd44d09119c844 -

vasild

ACK f65c9ad modulo s/assert.h/cassert/

practicalswift · 2020-03-23T21:46:40Z

ACK f65c9ad

practicalswift · 2020-03-23T23:06:21Z

@MarcoFalke

As pointed out earlier, this indeed is not an issue, because gcc will produce identical binaries for before this PR and after this PR. The overflow never happens.

I'm not sure I follow your reasoning here TBH.

"gcc will produce identical binaries for before this PR and after this PR" does not necessarily imply anything about the behaviour of other compilers we care about, no?

Test case compiled with clang as shown in #18046:

$ xxd -p -r <<< "fb67656c70000000000200ff0000ff0000000000000000ffffff7f0000000000" > crash-transaction
$ src/test/fuzz/transaction crash-transaction
primitives/transaction.cpp:87:19: runtime error: signed integer overflow: 1095216725760 + 9223372032559808512 cannot be represented in type 'long'
    #0 0x5574b725f6c1 in CTransaction::GetValueOut() const src/primitives/transaction.cpp:87:19
    #1 0x5574b611e5bb in test_one_input(std::vector<unsigned char, std::allocator<unsigned char> > const&) src/test/fuzz/transaction.cpp:71:18

Overflow never happens? :)

practicalswift · 2020-04-01T05:07:28Z

@MarcoFalke Friendly ping: can you clarify? :)

practicalswift · 2020-04-01T05:22:14Z

@instagibbs You reviewed a previous version of this PR -- would you mind re-reviewing the current version? :)

elichai · 2020-04-01T07:33:17Z

FWIW.
You can see that before: https://godbolt.org/z/wHZVFr
The logic was first add then compare:

        mov     rcx, QWORD PTR [rax]
        add     r8, rcx
        cmp     rcx, rsi
        ja      .L3
        cmp     r8, rsi
        ja      .L3
        add     rax, 8
        cmp     rdx, rax
        jne     .L6

But now: https://godbolt.org/z/oT7RJb it's first compare then add

        mov     rcx, QWORD PTR [rax]
        cmp     rcx, rsi
        ja      .L3
        add     r8, rcx
        cmp     r8, rsi
        jg      .L3
        add     rax, 8
        cmp     rdx, rax
        jne     .L6

maflcko · 2020-04-01T15:53:50Z

I used clang, not gcc. Anyway, I didn't say it is wrong to fix this ;)

instagibbs · 2020-04-01T16:10:09Z

utACK f65c9ad

…m of tx outputs f65c9ad Check for overflow when calculating sum of outputs (Elichai Turkel) Pull request description: This was reported by practicalswift here bitcoin#18046 The exact order of the if, is important, we first do `!MoneyRange(tx_out.nValue)` to make sure the amount is non-negative. and then `std::numeric_limits<CAmount>::max() - tx_out.nValue < nValueOut` checks that the addition cannot overflow (if we won't check that the amount is positive this check can also overflow! (by doing something like `max - -max`)) and only then we make sure that the some is also valid `!MoneyRange(nValueOut + tx_out.nValue)` if any of these conditions fail we throw. the overflowing logic: ``` a + b > max // we want to fail if a+b is more than the maximum -> will overflow b > max - a max - a < b ``` Closes: bitcoin#18046 ACKs for top commit: MarcoFalke: ACK f65c9ad, checked that clang with O2 produces identical binaries 💕 practicalswift: ACK f65c9ad instagibbs: utACK bitcoin@f65c9ad vasild: ACK f65c9ad modulo `s/assert.h/cassert/` Tree-SHA512: 512d6cf4762f24c41cf9a38da486b17b19c634fa3f4efbdebfe6608779e96fc3014d5d2d29adb8001e113152c0217bbd5b3900ac4edc7b8abe77f82f36209e33

Summary: Address a possible undefined behavior when summing outputs for a transaction, when the first outputs are valid but a following output causes an overflow. > The exact order of the if, is important, we first do `!MoneyRange(tx_out.nValue)` to make sure the amount is non-negative. and then `std::numeric_limits<CAmount>::max() - tx_out.nValue < nValueOut` checks that the addition cannot overflow (if we won't check that the amount is positive this check can also overflow! (by doing something like `max - -max`)) > and only then we make sure that the sum is also valid `!MoneyRange(nValueOut + tx_out.nValue`) > if any of these conditions fail we throw. This is a backport of Core [[bitcoin/bitcoin#18383 | PR18383]] Test Plan: ``` mkdir build_ubsan cd build_ubsan cmake -GNinja .. \ -DCMAKE_BUILD_TYPE=Debug \ -DENABLE_SANITIZERS=undefined ninja check ``` Reviewers: #bitcoin_abc, deadalnix Reviewed By: #bitcoin_abc, deadalnix Subscribers: deadalnix Differential Revision: https://reviews.bitcoinabc.org/D8899

…m of tx outputs f65c9ad Check for overflow when calculating sum of outputs (Elichai Turkel) Pull request description: This was reported by practicalswift here bitcoin#18046 The exact order of the if, is important, we first do `!MoneyRange(tx_out.nValue)` to make sure the amount is non-negative. and then `std::numeric_limits<CAmount>::max() - tx_out.nValue < nValueOut` checks that the addition cannot overflow (if we won't check that the amount is positive this check can also overflow! (by doing something like `max - -max`)) and only then we make sure that the some is also valid `!MoneyRange(nValueOut + tx_out.nValue)` if any of these conditions fail we throw. the overflowing logic: ``` a + b > max // we want to fail if a+b is more than the maximum -> will overflow b > max - a max - a < b ``` Closes: bitcoin#18046 ACKs for top commit: MarcoFalke: ACK f65c9ad, checked that clang with O2 produces identical binaries 💕 practicalswift: ACK f65c9ad instagibbs: utACK bitcoin@f65c9ad vasild: ACK f65c9ad modulo `s/assert.h/cassert/` Tree-SHA512: 512d6cf4762f24c41cf9a38da486b17b19c634fa3f4efbdebfe6608779e96fc3014d5d2d29adb8001e113152c0217bbd5b3900ac4edc7b8abe77f82f36209e33

maflcko added the Consensus label Mar 19, 2020

maflcko added the Refactoring label Mar 19, 2020

maflcko changed the title ~~Check for overflow when calculating sum of outputs in a transaction~~ refactor: Check for overflow when calculating sum of tx outputs Mar 19, 2020

maflcko added the Waiting for author label Mar 19, 2020

elichai force-pushed the 2020-03-value-overflow branch 2 times, most recently from 9a04da1 to a4c79f8 Compare March 23, 2020 12:58

Check for overflow when calculating sum of outputs

f65c9ad

elichai force-pushed the 2020-03-value-overflow branch from a4c79f8 to f65c9ad Compare March 23, 2020 14:36

practicalswift reviewed Mar 23, 2020

View reviewed changes

maflcko removed the Waiting for author label Mar 23, 2020

vasild approved these changes Mar 23, 2020

View reviewed changes

pierreN mentioned this pull request Mar 23, 2020

script: prevent UB when computing abs value for num opcode serialize #18413

Merged

practicalswift mentioned this pull request Mar 24, 2020

Some fuzzing crashes when running under ASan and/or UBSan #18046

Closed

maflcko pushed a commit to bitcoin-core/qa-assets that referenced this pull request Apr 2, 2020

Add transaction seed from bitcoin/bitcoin#18383 (comment)

d3dc77c

maflcko merged commit dce6f3b into bitcoin:master Apr 2, 2020

elichai deleted the 2020-03-value-overflow branch April 4, 2020 11:33

MarkLTZ mentioned this pull request Apr 4, 2020

Bitcoin PR tracking litecoinz-core/litecoinz#14

Closed

Fabcien pushed a commit to Fabcien/qa-assets that referenced this pull request Oct 27, 2020

Add transaction seed from bitcoin/bitcoin#18383 (comment)

1efecfe

bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022

refactor: Check for overflow when calculating sum of tx outputs #18383

refactor: Check for overflow when calculating sum of tx outputs #18383

Uh oh!

Conversation

elichai commented Mar 19, 2020 • edited by fanquake Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

laanwj commented Mar 19, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

elichai commented Mar 19, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

maflcko commented Mar 19, 2020

Uh oh!

maflcko commented Mar 19, 2020

Uh oh!

maflcko commented Mar 19, 2020

Uh oh!

vasild commented Mar 19, 2020

Uh oh!

maflcko commented Mar 19, 2020

Uh oh!

practicalswift commented Mar 19, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

practicalswift commented Mar 19, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

practicalswift commented Mar 19, 2020

Uh oh!

sipa commented Mar 19, 2020

Uh oh!

practicalswift commented Mar 19, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vasild commented Mar 20, 2020

Uh oh!

maflcko commented Mar 20, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

practicalswift commented Mar 20, 2020

Uh oh!

instagibbs commented Mar 20, 2020

Uh oh!

elichai commented Mar 21, 2020

Uh oh!

promag commented Mar 23, 2020

Uh oh!

elichai commented Mar 23, 2020

Uh oh!

practicalswift commented Mar 23, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

practicalswift commented Mar 23, 2020

Uh oh!

instagibbs commented Mar 23, 2020

Uh oh!

practicalswift Mar 23, 2020 • 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!

maflcko commented Mar 23, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vasild left a comment

Choose a reason for hiding this comment

Uh oh!

practicalswift commented Mar 23, 2020

Uh oh!

practicalswift commented Mar 23, 2020

Uh oh!

practicalswift commented Apr 1, 2020

Uh oh!

practicalswift commented Apr 1, 2020

Uh oh!

elichai commented Apr 1, 2020

Uh oh!

maflcko commented Apr 1, 2020

Uh oh!

elichai commented Mar 19, 2020 •

edited by fanquake

Loading

laanwj commented Mar 19, 2020 •

edited

Loading

elichai commented Mar 19, 2020 •

edited

Loading

practicalswift commented Mar 19, 2020 •

edited

Loading

practicalswift commented Mar 19, 2020 •

edited

Loading

practicalswift commented Mar 19, 2020 •

edited

Loading

maflcko commented Mar 20, 2020 •

edited

Loading

practicalswift commented Mar 23, 2020 •

edited

Loading

practicalswift Mar 23, 2020 •

edited

Loading

maflcko commented Mar 23, 2020 •

edited

Loading