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

1. 
   elichai commented at 1:58 pm on March 19, 2020: contributor

   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:

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

   Closes: #18046

2. 
   laanwj commented at 2:08 pm on March 19, 2020: member

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

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

3. 
   elichai commented at 2:12 pm on March 19, 2020: contributor

   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.

4. MarcoFalke added the label Consensus on Mar 19, 2020
5. 
   MarcoFalke commented at 2:38 pm on March 19, 2020: member

   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)
6. MarcoFalke added the label Refactoring on Mar 19, 2020
7. 
   MarcoFalke commented at 2:38 pm on March 19, 2020: member

   This was fixed in CVE-2010-5139
8. 
   MarcoFalke commented at 2:41 pm on March 19, 2020: member

   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
9. 
   vasild commented at 2:44 pm on March 19, 2020: member

   How could it overflow, given that CAmount is int64_t. Expressed in satoshi - about 4000 times more than the total supply of bitcoin?
10. 
    MarcoFalke commented at 2:49 pm on March 19, 2020: member

    @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.
11. MarcoFalke renamed this:
    Check for overflow when calculating sum of outputs in a transaction
    refactor: Check for overflow when calculating sum of tx outputs
    on Mar 19, 2020
12. 
    practicalswift commented at 3:46 pm on March 19, 2020: contributor

    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:

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

13. 
    practicalswift commented at 4:05 pm on March 19, 2020: contributor

    @elichai

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

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

    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 :)

14. 
    practicalswift commented at 4:20 pm on March 19, 2020: contributor

    @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? :)

15. 
    sipa commented at 4:25 pm on March 19, 2020: member

    @practicalswift nValueOut is computed but never inspected in case tx_out.nValue is out of range.
16. 
    practicalswift commented at 4:43 pm on March 19, 2020: contributor

    @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?

17. MarcoFalke added the label Waiting for author on Mar 19, 2020
18. 
    vasild commented at 2:05 pm on March 20, 2020: member

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

19. 
    MarcoFalke commented at 2:11 pm on March 20, 2020: member

    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.

20. 
    practicalswift commented at 3:25 pm on March 20, 2020: contributor

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

     0diff --git a/src/primitives/transaction.cpp b/src/primitives/transaction.cpp
     1index 28c145f71..76acb08b0 100644
     2--- a/src/primitives/transaction.cpp
     3+++ b/src/primitives/transaction.cpp
     4@@ -9,6 +9,8 @@
     5 #include <tinyformat.h>
     6 #include <util/strencodings.h>
     7
     8+#include <cassert>
     9+
    10 std::string COutPoint::ToString() const
    11 {
    12     return strprintf("COutPoint(%s, %u)", hash.ToString().substr(0,10), n);
    13@@ -84,10 +86,11 @@ CAmount CTransaction::GetValueOut() const
    14 {
    15     CAmount nValueOut = 0;
    16     for (const auto& tx_out : vout) {
    17-        nValueOut += tx_out.nValue;
    18-        if (!MoneyRange(tx_out.nValue) || !MoneyRange(nValueOut))
    19+        if (!MoneyRange(tx_out.nValue) || !MoneyRange(nValueOut + tx_out.nValue))
    20             throw std::runtime_error(std::string(__func__) + ": value out of range");
    21+        nValueOut += tx_out.nValue;
    22     }
    23+    assert(MoneyRange(nValueOut));
    24     return nValueOut;
    25 }
    

21. 
    instagibbs commented at 6:12 pm on March 20, 2020: member

    I prefer @practicalswift solution above
22. 
    elichai commented at 2:21 pm on March 21, 2020: contributor

    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 :)

23. 
    promag commented at 11:56 am on March 23, 2020: member

    I also prefer #18383 (comment).
24. 
    elichai commented at 12:05 pm on March 23, 2020: contributor

    @practicalswift do you wan to open a new PR with your suggestion? or should I replace my diff here with yours?
25. 
    practicalswift commented at 12:35 pm on March 23, 2020: contributor

    @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 :)
26. elichai force-pushed on Mar 23, 2020
27. elichai force-pushed on Mar 23, 2020
28. 
    practicalswift commented at 1:15 pm on March 23, 2020: contributor

    ACK a4c79f8cf6e0407f7e937fb41c73127f630231fa
29. 
    instagibbs commented at 1:22 pm on March 23, 2020: member

    utACK https://github.com/bitcoin/bitcoin/pull/18383/commits/a4c79f8cf6e0407f7e937fb41c73127f630231fa
30. Check for overflow when calculating sum of outputs f65c9ad40f
31. elichai force-pushed on Mar 23, 2020
32. in src/primitives/transaction.cpp:12 in f65c9ad40f

     8@@ -9,6 +9,8 @@
     9 #include <tinyformat.h>
    10 #include <util/strencodings.h>
    11 
    12+#include <assert.h>
    

    ---

    ---

    

    practicalswift commented at 3:21 pm on March 23, 2020:

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

    No need to invalidate ACK:s for this :)

33. MarcoFalke removed the label Waiting for author on Mar 23, 2020
34. 
    MarcoFalke commented at 3:41 pm on March 23, 2020: member

    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 f65c9ad40f2f5cdc581bdaf72e7dc68e9d7f7a80, checked that clang with O2 produces identical binaries 💕

    Signature:

     0-----BEGIN PGP SIGNED MESSAGE-----
     1Hash: SHA512
     2
     3ACK f65c9ad40f2f5cdc581bdaf72e7dc68e9d7f7a80, checked that gcc with O2 produces identical binaries 💕
     4-----BEGIN PGP SIGNATURE-----
     5
     6iQGzBAEBCgAdFiEE+rVPoUahrI9sLGYTzit1aX5ppUgFAlwqrYAACgkQzit1aX5p
     7pUj+xQv/d/bubEHp/tcMadyZVysqF3siEHt78ZoTKQRhFP5lw4uXb6ovzfzBja/a
     8kvrU8JXI9uhrb5crSgHSG7usI7c1hNh0dIN0xttD114U3irQJYdNkXT6OdJvwXMx
     9J+FB/95iD3SRz/WnDW1HI8s7D3eDRsPi66g+i/qVtiACuZnH0v8upNplGExv+IHF
    10ZDQrdNeTvwSXogBGmzNmNAXKI8YRXW2rqM+anQCPQPCLiSckitQoo7R8MffLkQWn
    115czTy4+DOaz7iydxwDvEavu0MQ/VboC3pv8QzdD+Hna6in2kHAZ0b95DC73Xo123
    12Gp/LlwaYdkIWLgl15HUOGp0WZ0M8btc1yFFt69XhdS82gV0/AT+MWgDVLsZiCVnc
    13hcjvFFmxlv1Kx7HtOYWdkIwXSX9etJkbVcbi0nWn+8lIjhqI4K6FPeZmUkO8VxgZ
    143ixw0PthqJD8R43kCLBy/W7JqFwRLYjE952d4Zwbu5Ub5ZAXzHS+pEiexn1rFRA/
    15EjBVwzaq
    16=5AXK
    17-----END PGP SIGNATURE-----
    

    Timestamp of file with hash 25065ff511c22aa1d923f7b1fe85f03fe3fe6ee9ddaa063d16dd44d09119c844 -

35. vasild approved
36. 
    vasild commented at 7:50 pm on March 23, 2020: member

    ACK f65c9ad40f2f5cdc581bdaf72e7dc68e9d7f7a80 modulo s/assert.h/cassert/
37. 
    practicalswift commented at 9:46 pm on March 23, 2020: contributor

    ACK f65c9ad40f2f5cdc581bdaf72e7dc68e9d7f7a80
38. 
    practicalswift commented at 11:06 pm on March 23, 2020: contributor

    @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:

    0$ xxd -p -r <<< "fb67656c70000000000200ff0000ff0000000000000000ffffff7f0000000000" > crash-transaction
    1$ src/test/fuzz/transaction crash-transaction
    2primitives/transaction.cpp:87:19: runtime error: signed integer overflow: 1095216725760 + 9223372032559808512 cannot be represented in type 'long'
    3    [#0](/bitcoin-bitcoin/0/) 0x5574b725f6c1 in CTransaction::GetValueOut() const src/primitives/transaction.cpp:87:19
    4    [#1](/bitcoin-bitcoin/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? :)

39. 
    practicalswift commented at 5:07 am on April 1, 2020: contributor

    @MarcoFalke Friendly ping: can you clarify? :)
40. 
    practicalswift commented at 5:22 am on April 1, 2020: contributor

    @instagibbs You reviewed a previous version of this PR – would you mind re-reviewing the current version? :)
41. 
    elichai commented at 7:33 am on April 1, 2020: contributor

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

    0        mov     rcx, QWORD PTR [rax]
    1        add     r8, rcx
    2        cmp     rcx, rsi
    3        ja      .L3
    4        cmp     r8, rsi
    5        ja      .L3
    6        add     rax, 8
    7        cmp     rdx, rax
    8        jne     .L6
    

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

    0        mov     rcx, QWORD PTR [rax]
    1        cmp     rcx, rsi
    2        ja      .L3
    3        add     r8, rcx
    4        cmp     r8, rsi
    5        jg      .L3
    6        add     rax, 8
    7        cmp     rdx, rax
    8        jne     .L6
    

42. 
    MarcoFalke commented at 3:53 pm on April 1, 2020: member

    I used clang, not gcc. Anyway, I didn’t say it is wrong to fix this ;)
43. 
    instagibbs commented at 4:10 pm on April 1, 2020: member

    utACK https://github.com/bitcoin/bitcoin/pull/18383/commits/f65c9ad40f2f5cdc581bdaf72e7dc68e9d7f7a80
44. MarcoFalke referenced this in commit d3dc77c162 on Apr 2, 2020
45. MarcoFalke merged this on Apr 2, 2020
46. MarcoFalke closed this on Apr 2, 2020

    ---

47. sidhujag referenced this in commit 4c1e075bc9 on Apr 3, 2020
48. elichai deleted the branch on Apr 4, 2020
49. Fabcien referenced this in commit 1efecfe658 on Oct 27, 2020
50. Fabcien referenced this in commit 4a38b361f6 on Mar 31, 2021
51. PastaPastaPasta referenced this in commit 9845af0c9f on Jun 27, 2021
52. PastaPastaPasta referenced this in commit c04052eb40 on Jun 28, 2021
53. PastaPastaPasta referenced this in commit 889992b3d5 on Jun 29, 2021
54. PastaPastaPasta referenced this in commit 652cea449d on Jul 1, 2021
55. PastaPastaPasta referenced this in commit c192334f41 on Jul 1, 2021
56. PastaPastaPasta referenced this in commit c542cd3a98 on Jul 14, 2021
57. DrahtBot locked this on Feb 15, 2022

Contributors
elichai laanwj MarcoFalke vasild practicalswift sipa instagibbs promag

Labels
Refactoring Consensus