refactor: Avoid integer overflow in ApplyStats when activating snapshot #23411

pull MarcoFalke wants to merge 4 commits into bitcoin:master from MarcoFalke:2111-fuzzIntAmt changing 13 files +86 −23
  1. MarcoFalke commented at 2:56 PM on November 1, 2021: member

    A snapshot contains the utxo set, including the out value. To activate the snapshot, the hash needs to be calculated. As a side-effect, the total amount in the snapshot is calculated (as the sum of all out values), but never used. Instead of running into an integer overflow in an unused result, don't calculate the result in the first place.

    Other code paths (using the active utxo set) can not run into an integer overflow, since the active utxo set is valid.

    Fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=39716

  2. MarcoFalke force-pushed on Nov 1, 2021
  3. MarcoFalke commented at 2:58 PM on November 1, 2021: member

    Reproducer: clusterfuzz-testcase-minimized-utxo_snapshot-6702059005542400.bin.txt

  4. MarcoFalke added the label Refactoring on Nov 1, 2021
  5. MarcoFalke force-pushed on Nov 1, 2021
  6. sipa commented at 3:30 PM on November 1, 2021: member

    How does activating a snapshot trigger an integer overflow in this code in the first place? That seems far more concerning, and this PR just patches it up.

  7. MarcoFalke commented at 3:55 PM on November 1, 2021: member

    @sipa Added three more sentences to OP to explain this refactor.

  8. jamesob commented at 3:58 PM on November 1, 2021: member

    Hm, I'm kind of confused - is the concern here that a user could be fed a bad snapshot that causes an overflow? Because if that's the case, the hash of the UTXO set won't match the one hardcoded in chainparams' m_assumeutxo_data.

    If it's not a bad snapshot you're worried about, then as far as I can tell the same wraparound issue would exist with a normal gettxoutsetinfo call at the height of the snapshot.

  9. MarcoFalke commented at 3:59 PM on November 1, 2021: member

    Correct.

    If we don't care about integer overflows when activating invalid snapshots, then this pull can be closed.

  10. sipa commented at 7:29 PM on November 1, 2021: member

    Would it make sense to instead compute the total amount as an std::optional, which starts at {0}, and is incremented with the read values, but when an out-of-range value is read, or the sum goes out-of-range, is replaced with std::nullopt (and then stays at std::nullopt)? That would categorically remove this concern, and pushes the responsibility for checking sanity to the caller (where it apparently differs).

  11. DrahtBot commented at 9:06 PM on November 1, 2021: member

    <!--e57a25ab6845829454e8d69fc972939a-->

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

    <!--174a7506f384e20aa4161008e828411d-->

    Conflicts

    No conflicts as of last run.

  12. MarcoFalke force-pushed on Nov 2, 2021
  13. MarcoFalke commented at 12:29 PM on November 2, 2021: member

    Switched to std::optional approach

  14. shaavan commented at 1:45 PM on November 2, 2021: contributor

    Concept ACK

    This PR allows preventing integer overflow of coin_stats.total_amount while activating the snapshot.

    The following points explain the PR in greater detail:

    1. The function AdditionOverflow has been moved from src/test/fuzz/util.h to a new file src/util/overflow.h. The dependencies of other files are updated accordingly.
    2. Unit tests are added for this function, which tests on various edge cases in the case of both signed and unsigned elements.
    3. The AdditionOverflow function is used in the coinstats::ApplyStats function to prevent the risk of an overflow of CAmount. In case if there might be an integer overflow, the total_amount var is set to nullopt.

    Though I have not rigorously tested this PR yet, I think the code is logically coherent.

    I have just one doubt I would like to point out.

    In src/test/util_tests.cpp file: From the line BOOST_CHECK(TestAddMatrix<signed>()); I inferred that this function was made to be used with signed integers. If I am correct, then there is one logical error:

    assert(TestAdd(mini, mini));

    This might not always be true.

    For example:

    • mini = 2; mini + mini = 4 > 2 (in range) TestAdd result == true
    • mini = -2; mini + mini = -4 < -2 (out of range) TestAdd result == false

      <p>

  15. MarcoFalke force-pushed on Nov 2, 2021
  16. MarcoFalke commented at 1:57 PM on November 2, 2021: member

    This might not always be true.

    MINI is a compile time constant (just force pushed to rename it from mini). It allows for the test checking for underflow to be less verbose. Checking for underflow is only needed when adding signed integers. Adding two unsigned integers can only overflow.

  17. MarcoFalke force-pushed on Nov 2, 2021
  18. luke-jr commented at 5:18 PM on November 2, 2021: member

    Seems like the number is useful for human verification. We should probably log it or tell advanced users somewhere.

    Maybe instead, abort activation of snapshots that exceed MAX_MONEY?

  19. MarcoFalke commented at 6:03 PM on November 2, 2021: member

    Maybe instead, abort activation of snapshots that exceed MAX_MONEY?

    The amounts are already covered by the hash, which is obviously trusted and verified. Thus, it will abort activation.

    Starting to check random consensus rules on the snapshot is going to be an open ended issue (why not check that there are no unspendable scriptPubKeys in the snapshot, ...) that doesn't give any benefit.

  20. shaavan approved
  21. shaavan commented at 2:45 PM on November 3, 2021: contributor

    Checking for underflow is only needed when adding signed integers. Adding two unsigned integers can only overflow.

    Makes sense to me now. Since TestAddMatrix() is being used only for signed integer. The minimum possible value ( = MINI) must be < 0. In that case the assertion condition assert(TestAdd(MINI, MINI)); will never fail.

    crACK fa13888199cdae682aa58b68c08d9856dbd20477

  22. in src/node/coinstats.cpp:86 in fa13888199 outdated 
      82 | @@ -82,7 +83,11 @@ static void ApplyStats(CCoinsStats& stats, const uint256& hash, const std::map<u
  83 |      stats.nTransactions++;
  84 |      for (auto it = outputs.begin(); it != outputs.end(); ++it) {
  85 |          stats.nTransactionOutputs++;
  86 | -        stats.nTotalAmount += it->second.out.nValue;
  87 | +        if (stats.total_amount.has_value() && !AdditionOverflow(*stats.total_amount, it->second.out.nValue)) {
    laanwj commented at 12:37 PM on November 10, 2021:

    It seems cleaner to factor this out. What about an AddOverflowDetect in util/overflow.h that implements the "add numbers and collapse to nullopt on overflow" logic?

    MarcoFalke commented at 5:52 PM on November 10, 2021:

    Thx, done

  23. MarcoFalke force-pushed on Nov 10, 2021
  24. shaavan approved
  25. shaavan commented at 11:56 AM on November 12, 2021: contributor

    reACK fa4a86e466ed4983235307d31fbe1ef8b28829d6

    Changes since my last review:

    • Added a new function CheckedAdd (in overflow.h), which returns nullopt if there is an addition overflow (or underflow) and otherwise returns the sum.
    • TestAdd function (in util_tests.cpp) has been removed, and its usage is replaced with CheckedAdd.
    • Finally, CheckedAdd is used to simplify added code in the coinstats.cpp file.
  26. DrahtBot added the label Needs rebase on Nov 25, 2021
  27. MarcoFalke force-pushed on Nov 26, 2021
  28. DrahtBot removed the label Needs rebase on Nov 26, 2021
  29. shaavan approved
  30. shaavan commented at 11:50 AM on November 26, 2021: contributor

    reACK fa72733b12eac2fa038afb75c9463570b48ea34b

    Changes since my last review:

    • Rebased the branch on the current master.
  31. laanwj added this to the "Blockers" column in a project
  32. in src/rpc/blockchain.cpp:1222 in fa72733b12 outdated 
    1216 | @@ -1217,9 +1217,10 @@ static RPCHelpMan gettxoutsetinfo()
1217 |              ret.pushKV("hash_serialized_2", stats.hashSerialized.GetHex());
1218 |          }
1219 |          if (hash_type == CoinStatsHashType::MUHASH) {
1220 | -              ret.pushKV("muhash", stats.hashSerialized.GetHex());
1221 | +            ret.pushKV("muhash", stats.hashSerialized.GetHex());
1222 |          }
1223 | -        ret.pushKV("total_amount", ValueFromAmount(stats.nTotalAmount));
1224 | +        CHECK_NONFATAL(stats.total_amount);
    vasild commented at 8:34 AM on December 17, 2021:

    nit: this looks like we are checking that the amount is not 0. Maybe better to be more explicit:

            CHECK_NONFATAL(stats.total_amount.has_value());
    vasild commented at 8:39 AM on December 17, 2021:

    This would throw and not display any results. Is that the desirable outcome? What about just skipping the ret.pushKV("total_amount", ...) if there is no value? Or push something like "N/A", "NaN" or "overflow"? I mean the rest of the stats are still useful, right?

    MarcoFalke commented at 9:09 AM on December 17, 2021:

    I think we should throw on internal bugs, which are impossible to hit. Otherwise it will be harder to find and fix them. Also, they'll crash the client regardless either with KeyError or with a parse error, since a string isn't int.

    MarcoFalke commented at 9:48 AM on December 17, 2021:

    thx, fixed

  33. in src/test/util_tests.cpp:1476 in fa72733b12 outdated 
    1471 | +static bool TestAddMatrixOverflow()
1472 | +{
1473 | +    constexpr T MAXI{std::numeric_limits<T>::max()};
1474 | +    assert(!CheckedAdd(T{1}, MAXI));
1475 | +    assert(!CheckedAdd(MAXI, MAXI));
1476 | +    assert(0 == CheckedAdd(T{0}, T{0}).value());
    vasild commented at 8:46 AM on December 17, 2021:

    These can be BOOST_CHECK() and BOOST_CHECK_EQUAL(), the TestAddMatrixOverflow() and TestAddMatrix() functions be void and can be called without BOOST_CHECK() from the test case.

    This would have the usual benefit of using BOOST_CHECK() vs assert().

    MarcoFalke commented at 9:49 AM on December 17, 2021:

    nice, fixed.

  34. vasild commented at 8:55 AM on December 17, 2021: member

    Concept ACK fa72733b12eac2fa038afb75c9463570b48ea34b

  35. style: Remove unused whitespace faff051560
  36. Add dev doc to CCoinsStats::m_hash_type and make it const fa526d8fb6
  37. Move AdditionOverflow to util, Add CheckedAdd with unit tests fac01888d1
  38. refactor: Avoid integer overflow in ApplyStats when activating snapshot fa996c58e8
  39. MarcoFalke force-pushed on Dec 17, 2021
  40. MarcoFalke commented at 9:50 AM on December 17, 2021: member

    Addressed test nits in force push. Should be trivial to re-ACK with:

    git range-diff bitcoin-core/master --word-diff-regex=. fa72733b12 fa996c58e8
  41. shaavan approved
  42. shaavan commented at 10:24 AM on December 17, 2021: contributor

    reACK fa996c58e8a31ebe610d186cef408b6dd3b385a8

    Changes since my last review:

    • Addressed suggestion under this comment.
    • stats.total_amount -> stats.total_amount.has_value()
    • Replaced assert with BOOST_CHECK in src/test/util_tests.cpp file.

    I agree with the rationale behind the changes discussed under the above comment.

  43. vasild approved
  44. vasild commented at 10:31 AM on December 17, 2021: member

    ACK fa996c58e8a31ebe610d186cef408b6dd3b385a8

  45. MarcoFalke merged this on Jan 5, 2022
  46. MarcoFalke closed this on Jan 5, 2022
  47. MarcoFalke deleted the branch on Jan 5, 2022
  48. MarcoFalke removed this from the "Blockers" column in a project
  49. sidhujag referenced this in commit f22ac8ff54 on Jan 6, 2022
  50. DrahtBot locked this on Jan 5, 2023
Contributors
MarcoFalkesipajamesobDrahtBotshaavanluke-jrlaanwjvasild
Labels
Refactoring
github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-04-17 06:14 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me