Avoid unintentional unsigned integer wraparounds

practicalswift commented at 5:23 pm on October 20, 2017: contributor

Avoid unintentional unsigned integer wraparounds.

fanquake added the label Tests on Oct 20, 2017

in src/test/prevector_tests.cpp:209 in c8dfc4f15f outdated

205@@ -206,7 +206,7 @@ BOOST_AUTO_TEST_CASE(PrevectorTestInt)
206                 test.erase(InsecureRandRange(test.size()));
207             }
208             if (InsecureRandBits(3) == 2) {
209-                int new_size = std::max<int>(0, std::min<int>(30, test.size() + (InsecureRandRange(5)) - 2));
210+                int new_size = std::max<int>(0, std::min<int>(30, static_cast<int>(test.size()) + static_cast<int>(InsecureRandRange(5)) - 2));

laanwj commented at 9:19 am on October 21, 2017:

Does this still need the <int> qualifier on std::max/min if you cast all the arguments to int?

practicalswift force-pushed on Oct 21, 2017

practicalswift commented at 11:03 pm on October 21, 2017: contributor

@laanwj Good point. Fixed! :-)

practicalswift commented at 11:07 am on October 22, 2017: contributor

Added commits from #11547 (“Avoid unintended unsigned integer wraparounds in FormatScript(…) and SplitHostPort(…)”) as requested :-)

practicalswift renamed this:
~~test: Avoid unintentional unsigned integer wraparounds~~
Avoid unintentional unsigned integer wraparounds
on Oct 22, 2017

practicalswift force-pushed on Oct 23, 2017

practicalswift force-pushed on Oct 24, 2017

practicalswift commented at 6:30 am on October 24, 2017: contributor

Added a few more wrap-arounds and squashed. Now at 16 fixed wrap-arounds.

sipa commented at 6:32 am on October 24, 2017: member

We tend to use C-style casts for primitive types… just for brevity.

practicalswift force-pushed on Oct 24, 2017

practicalswift commented at 6:37 am on October 24, 2017: contributor

@sipa I’ll change! Other than that, do the changes look reasonable? :-)

in src/policy/fees.cpp:292 in 0a01b3809b outdated

290@@ -291,7 +291,7 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
291         totalNum += txCtAvg[bucket];
292         failNum += failAvg[periodTarget - 1][bucket];
293         for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++)
294-            extraNum += unconfTxs[(nBlockHeight - confct)%bins][bucket];
295+            extraNum += unconfTxs[(nBlockHeight >= confct ? nBlockHeight - confct : 0) % bins][bucket];

practicalswift commented at 6:58 am on October 24, 2017:

This change needs extra review. Is this the correct way to handle this wrap-around?

promag commented at 6:51 pm on March 5, 2018:

Does it matters if nBlockHeight < GetMaxConfirms()? Maybe we should just skip EstimateMedianVal entirely if so. cc @morcos

morcos commented at 7:26 pm on March 5, 2018:

Actually I think the existing code is broken, we should fix it by replacing the for loop with: for (unsigned int confct = confTarget; confct < GetMaxConfirms() && confct <= nBlockHeight; confct++)

promag commented at 7:31 pm on March 5, 2018:

That makes sense.

practicalswift commented at 8:31 pm on March 5, 2018:

Thanks @promag and @morcos. Now updated. Please re-review :-)

practicalswift force-pushed on Oct 25, 2017

practicalswift commented at 9:07 am on October 25, 2017: contributor

@sipa Now using C-style casts for primitive types :-)

practicalswift force-pushed on Oct 25, 2017

practicalswift commented at 7:35 pm on October 25, 2017: contributor

Added another wraparound fix (this time in AcceptBlock(…)) and squashed.

Anyone willing to review? :-)

practicalswift force-pushed on Nov 9, 2017

practicalswift commented at 3:51 pm on November 9, 2017: contributor

Rebased! :-)

MarcoFalke added the label Refactoring on Nov 9, 2017

MarcoFalke removed the label Tests on Nov 9, 2017

practicalswift commented at 6:30 pm on December 5, 2017: contributor

Anyone willing to review - ACK or NACK? :-)

practicalswift commented at 10:49 am on January 28, 2018: contributor

Ping? :-)

practicalswift commented at 9:48 pm on February 22, 2018: contributor

Do we not care about integer wrap-arounds? If so let me know and I’ll close :-)

MarcoFalke commented at 10:27 pm on February 22, 2018: member

ACK test changes, they seem straightforward. The other need a cautious review, since they change behavior.

(You can split the test changes into a separate pull request, if you want)

laanwj referenced this in commit 7f99964321 on Mar 5, 2018

in src/test/scheduler_tests.cpp:60 in 6ec8af9354 outdated

55@@ -56,8 +56,8 @@ BOOST_AUTO_TEST_CASE(manythreads)
56     int counter[10] = { 0 };
57     FastRandomContext rng(42);
58     auto zeroToNine = [](FastRandomContext& rc) -> int { return rc.randrange(10); }; // [0, 9]
59-    auto randomMsec = [](FastRandomContext& rc) -> int { return -11 + rc.randrange(1012); }; // [-11, 1000]
60-    auto randomDelta = [](FastRandomContext& rc) -> int { return -1000 + rc.randrange(2001); }; // [-1000, 1000]
61+    auto randomMsec = [](FastRandomContext& rc) -> int { return -11 + (int)rc.randrange(1012); }; // [-11, 1000]
62+    auto randomDelta = [](FastRandomContext& rc) -> int { return -1000 + (int)rc.randrange(2001); }; // [-1000, 1000]

MarcoFalke commented at 5:59 pm on March 5, 2018:

This change is already in master

in src/txmempool.cpp:219 in 6ec8af9354 outdated

220@@ -221,7 +221,7 @@ void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors
221         UpdateChild(piter, it, add);
222     }
223     const int64_t updateCount = (add ? 1 : -1);
224-    const int64_t updateSize = updateCount * it->GetTxSize();
225+    const int64_t updateSize = updateCount * (int64_t)it->GetTxSize();

promag commented at 6:08 pm on March 5, 2018:

Why is this necessary?

practicalswift commented at 9:52 pm on March 12, 2018:

Consider the case where add == false and it->GetTxSize() == 2.

Then an unsigned integer overflow occurs when calculating updateCount * it->GetTxSize() (but not for updateCount * (int64_t)it->GetTxSize()).

(And yes, the resulting int64_t updateSize will be -2 in both cases :-))

promag commented at 2:40 pm on April 16, 2018:

:+1:

in src/core_write.cpp:61 in 6ec8af9354 outdated

57@@ -58,7 +58,7 @@ std::string FormatScript(const CScript& script)
58         ret += strprintf("0x%x ", HexStr(it2, script.end()));
59         break;
60     }
61-    return ret.substr(0, ret.size() - 1);
62+    return ret.size() > 0 ? ret.substr(0, ret.size() - 1) : ret;

promag commented at 6:19 pm on March 5, 2018:

IMO there is no need in copying the whole string. Suggestion:

0if (!ret.empty()) ret.pop_back();
1return ret;

practicalswift force-pushed on Mar 5, 2018

morcos commented at 8:57 pm on March 5, 2018: member

Re: policy/fees.cpp changes utACK (didn’t review anything else)

Thanks!

in src/validation.cpp:1591 in f53592c0be outdated

1587@@ -1588,7 +1588,8 @@ DisconnectResult CChainState::DisconnectBlock(const CBlock& block, const CBlockI
1588                 error("DisconnectBlock(): transaction and undo data inconsistent");
1589                 return DISCONNECT_FAILED;
1590             }
1591-            for (unsigned int j = tx.vin.size(); j-- > 0;) {
1592+            for (unsigned int j = tx.vin.size(); j > 0;) {

promag commented at 9:23 pm on March 5, 2018:

It doesn’t matter if it wraps, j is only used inside the loop and it only wraps when j = 0 which is when the loop ends.

Anyway, how about changing to:

0for (int j = tx.vin.size() - 1; j >= 0; --j) {

which IMO is more clear.

Edit: j could still be unsigned since tx.vin.size() is always > 0 (this code runs for non coinbase transactions), but I guess the analyser is not happy with that.

practicalswift commented at 10:09 pm on March 12, 2018:

All unsigned integer overflows matter :-)

practicalswift commented at 10:02 pm on March 12, 2018: contributor

@promag Thanks for reviewing. Switched to suggested for formulation. Please re-review.

practicalswift force-pushed on Mar 12, 2018

in src/chain.h:478 in 8d2dcdb16d outdated

474@@ -475,7 +475,7 @@ class CChain {
475 
476     /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */
477     int Height() const {
478-        return vChain.size() - 1;
479+        return (int)vChain.size() - 1;

promag commented at 11:24 pm on March 12, 2018:

Why is this cast necessary?

practicalswift commented at 8:44 pm on March 13, 2018:

An unsigned integer overflow occurs in the case where vChain.size() == 0.

(And yes, the value return by Height() will be the expected -1, but an overflow occurred before returning :-))

promag commented at 2:40 pm on April 16, 2018:

:+1:

practicalswift commented at 2:29 pm on April 16, 2018: contributor

Anyone willing to review?

Getting the project to run cleanly under -fsanitize=integer would be very nice :-)

in src/policy/fees.cpp:291 in 8d2dcdb16d outdated

287@@ -288,7 +288,7 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
288         nConf += confAvg[periodTarget - 1][bucket];
289         totalNum += txCtAvg[bucket];
290         failNum += failAvg[periodTarget - 1][bucket];
291-        for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++)
292+        for (unsigned int confct = confTarget; confct < GetMaxConfirms() && confct <= nBlockHeight; confct++)

promag commented at 2:39 pm on April 16, 2018:

Nit, ++ confct.

in src/validation.cpp:1591 in 8d2dcdb16d outdated

1587@@ -1588,7 +1588,7 @@ DisconnectResult CChainState::DisconnectBlock(const CBlock& block, const CBlockI
1588                 error("DisconnectBlock(): transaction and undo data inconsistent");
1589                 return DISCONNECT_FAILED;
1590             }
1591-            for (unsigned int j = tx.vin.size(); j-- > 0;) {
1592+            for (int j = tx.vin.size() - 1; j >= 0; --j) {

promag commented at 2:42 pm on April 16, 2018:

Should cast here too (int j = (int)tx.vin.size() - 1)?

practicalswift force-pushed on Apr 16, 2018

practicalswift commented at 3:52 pm on April 16, 2018: contributor

@promag Thanks for reviewing! Feedback addressed! @sipa @promag Please re-review :-)

DrahtBot closed this on Jul 22, 2018

DrahtBot commented at 12:55 pm on July 22, 2018: member

DrahtBot reopened this on Jul 22, 2018

in src/policy/fees.cpp:291 in 1d651b3750 outdated

287@@ -288,7 +288,7 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
288         nConf += confAvg[periodTarget - 1][bucket];
289         totalNum += txCtAvg[bucket];
290         failNum += failAvg[periodTarget - 1][bucket];
291-        for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++)
292+        for (unsigned int confct = confTarget; confct < GetMaxConfirms() && confct <= nBlockHeight; ++confct)

arvidn commented at 2:23 pm on September 6, 2018:

it seems questionable that confct is unsigned to begin with. presumably this loop doesn’t rely on the counter having modulo-2 arithmetic.

practicalswift commented at 8:59 am on September 14, 2018:

@arvidn Thanks for reviewing! Do you suggest changing it from unsigned int to int or leaving it as is? :-) Note that GetMaxConfirms() returns an unsigned int.

arvidn commented at 0:07 am on September 15, 2018:

yes, in general I would recommend using signed integers for anything that is expected to have normal arithmetic (as opposed to modulo-2 arithmetic). i.e. GetMaxConfirms() should probably return a signed integer. But I don’t think it’s practical to “unravel” all such dependencies in one commit.

arvidn commented at 0:08 am on September 15, 2018:

yes, in general I would recommend using signed integers for anything that is expected to have normal arithmetic (as opposed to modulo-2 arithmetic). i.e. GetMaxConfirms() should probably return a signed integer. But I don’t think it’s practical to “unravel” all such dependencies in one commit.

practicalswift force-pushed on Sep 6, 2018

practicalswift commented at 2:35 pm on September 6, 2018: contributor

@arvidn Updated to address your feedback. Please re-review!

BTW, I love your talk about C++ integers! Great to have you as a reviewer of this PR :-)

practicalswift force-pushed on Sep 13, 2018

practicalswift force-pushed on Sep 14, 2018

practicalswift commented at 8:47 am on September 14, 2018: contributor

Updated! Please re-review.

in src/script/interpreter.cpp:54 in 47a4cd73a4 outdated

50@@ -51,8 +51,8 @@ bool CastToBool(const valtype& vch)
51  * Script is a stack machine (like Forth) that evaluates a predicate
52  * returning a bool indicating valid or not.  There are no loops.
53  */
54-#define stacktop(i)  (stack.at(stack.size()+(i)))
55-#define altstacktop(i)  (altstack.at(altstack.size()+(i)))
56+#define stacktop(i)  (stack.at((size_t)((ssize_t)stack.size() + (ssize_t)i)))

practicalswift commented at 7:51 am on September 21, 2018:

02018-09-19 12:07:43 clang-tidy(pr=11535): src/script/interpreter.cpp:54:74: warning: macro argument should be enclosed in parentheses [misc-macro-parentheses]

in src/script/interpreter.cpp:55 in 47a4cd73a4 outdated

50@@ -51,8 +51,8 @@ bool CastToBool(const valtype& vch)
51  * Script is a stack machine (like Forth) that evaluates a predicate
52  * returning a bool indicating valid or not.  There are no loops.
53  */
54-#define stacktop(i)  (stack.at(stack.size()+(i)))
55-#define altstacktop(i)  (altstack.at(altstack.size()+(i)))
56+#define stacktop(i)  (stack.at((size_t)((ssize_t)stack.size() + (ssize_t)i)))
57+#define altstacktop(i)  (altstack.at((size_t)((ssize_t)altstack.size() + (ssize_t)i)))

practicalswift commented at 7:51 am on September 21, 2018:

02018-09-19 12:07:43 clang-tidy(pr=11535): src/script/interpreter.cpp:55:83: warning: macro argument should be enclosed in parentheses [misc-macro-parentheses]

DrahtBot commented at 1:31 pm on September 21, 2018: 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:

#14224 (Document intentional and unintentional unsigned integer overflows (wraparounds) using annotations by practicalswift)
#13804 (WIP: Transaction Pool Layer by MarcoFalke)
#11551 (Fix unsigned integer wrap-around in GetBlockProofEquivalentTime 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.

practicalswift commented at 3:57 pm on September 28, 2018: contributor

To increase the likelihood of this PR getting merged – should I limit it to a subset that is low-risk/non-controversial? Please help me find that subset :-)

It would be really nice to get rid of these unintended unsigned integer wraparounds.

flack commented at 8:30 pm on September 28, 2018: contributor

Please help me find that subset :-) @practicalswift see #11535 (comment)

practicalswift commented at 12:22 pm on October 7, 2018: contributor

@flack That subset has already been fixed – see #12516 :-)

DrahtBot added the label Needs rebase on Nov 5, 2018

practicalswift force-pushed on Nov 5, 2018

DrahtBot removed the label Needs rebase on Nov 5, 2018

arvidn commented at 2:16 pm on November 5, 2018: none

I don’t have any authority here, I can only offer advice how I would approach this.

What do I mean by “this”? I think the code should transition to using signed integers pervasively, everywhere by default, except the places where it needs unsigned integers (such as bit fiddling and modulo-2 arithmetic, a lot of crypto code falls into this category).

I think getting there has to be incremental, and during the transition there will probably be a net increase of signed/unsigned casts. But in the end the whole codebase could be built with -Wsign-conversion -Werror, which would be a great place to be in, and with fewer casts. @practicalswift I believe you’ve found the issues you’ve addressed here with -fsanitize=unsigned, right? I think that’s a good tool to find the most egregious misuses of unsigned integers, they should probably be the first ones to go. However, perhaps addressing all of these individual spots in a single commit isn’t the right slicing or increment towards the goal of reducing misuses of unsigned integers. Perhaps instead, pick one, and fix that one properly, including all the ripple-effects it may have.

for example, take this part of the patch.

Maybe it would make more sense to explore what would happen if GetTxSize() would return an int64_t (which seems like a cleaner solution than casting its result like this).

MarcoFalke commented at 2:25 pm on November 5, 2018: member

If we decide to return sizes and lengths as int64_t, that should probably be documented in the developer notes (coding style) with rationale for doing so. Otherwise it seems like the code could go back and forth over this constantly.

practicalswift commented at 3:57 pm on November 5, 2018: contributor

@arvidn Good point regarding splitting this PR into smaller parts. I’ll do that. @arvidn @MarcoFalke Are there any parts of this PR that you can ACK or NACK? I’m trying to identify the appropriate parts to split it in :-)

Avoid unintentional unsigned integer wraparounds be8eec1706

practicalswift force-pushed on Nov 6, 2018

practicalswift force-pushed on Nov 7, 2018

Fix unintentional unsigned integer wrap-around in GetBlockProofEquivalentTime(...) when to.nChainWork <= from.nChainWork a92926a7fa

Remove UBSan suppression 42aba473a5

in src/validation.cpp:4711 in ac8ff2357d outdated

4706@@ -4707,7 +4707,8 @@ bool LoadMempool()
4707         }
4708         uint64_t num;
4709         file >> num;
4710-        while (num--) {
4711+        while (num) {
4712+            --num;

ken2812221 commented at 6:31 pm on November 7, 2018:

How do this avoid overflow?

sipa commented at 6:36 pm on November 7, 2018:

It won’t decrement when num is 0. The old code would stop the loop, but still decrement.

practicalswift force-pushed on Nov 11, 2018

practicalswift closed this on Nov 12, 2018

PastaPastaPasta referenced this in commit e7a3fc7f7b on Jun 9, 2020

PastaPastaPasta referenced this in commit e4d719c5d7 on Jun 9, 2020

PastaPastaPasta referenced this in commit dc202ba89c on Jun 10, 2020

PastaPastaPasta referenced this in commit afde6d1cdc on Jun 11, 2020

PastaPastaPasta referenced this in commit 7afd746191 on Jun 11, 2020

PastaPastaPasta referenced this in commit 04d780d03d on Jun 11, 2020

PastaPastaPasta referenced this in commit f96ba063b8 on Jun 12, 2020

practicalswift deleted the branch on Apr 10, 2021

gades referenced this in commit 11ff3f86ef on May 31, 2022

DrahtBot locked this on Aug 18, 2022

Avoid unintentional unsigned integer wraparounds #11535

Conflicts