Fix unsigned integer wrap-around in GetBlockProofEquivalentTime by practicalswift · Pull Request #11551 · bitcoin/bitcoin

practicalswift · 2017-10-23T21:33:08Z

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

Description:

int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, …)
contains the following code:

int sign = 1;
if (to.nChainWork > from.nChainWork) {
…
} else {
    …
    sign = -1;
}
…
return sign * r.GetLow64();

r.GetLow64() is of type uint64_t.

Note that the types of the two operands in sign * r.GetLow64() differ in signedness.

Since uint64_t is wider than int the signed operand (sign) is converted to the unsigned type.

In the case of sign == -1 (to.nChainWork <= from.nChainWork) we wrap around and end up with 18446744073709551615 * r.GetLow64() (std::numeric_limits<uint64_t>::max() * r.GetLow64()) instead of the intended -1 * r.GetLow64().

Note however that another conversion takes place when the result is converted into the return type
(int64_t), so the resulting value should be the expected one (equivalent to -1 * r.GetLow64()).

In the case that this behaviour (wrap-around + relying on return type to fix) is intentional a comment should probably be added to indicate so :-)

GetBlockProofEquivalentTime(…) was introduced in f7303f9. Friendly ping @sipa - intentional or not? :-)

meshcollider · 2017-10-24T00:34:43Z

Again, isn't this part of #11535 too? Both are just avoiding unintentional unsigned integer wraparounds?

practicalswift · 2017-10-24T05:30:18Z

@meshcollider I thought this one was a bit more interesting than the others and deserved its own PR, but sure I can just add all unintentional unsigned integer wraparounds to #11535. I have a few more to report :-)

promag

Nit, shorter commit message Fix unsigned integer wrap-around in GetBlockProofEquivalentTime.

src/chain.cpp

practicalswift · 2017-10-24T09:16:12Z

@promag Nit addressed :-)

promag · 2017-10-24T09:19:47Z

ACK de9517d.

practicalswift · 2017-10-24T09:21:33Z

@promag Thanks a lot for reviewing! Would you mind taking a look at the wrap-arounds covered in #11535 too? :-)

practicalswift · 2017-10-24T14:26:48Z

@sipa What do you think about this change? Do you have time to review? :-)

practicalswift · 2018-02-22T21:48:31Z

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

maflcko · 2018-02-22T23:17:38Z

@practicalswift Can you add a test case that fails before this change and passes after this change. This prevents from re-introducing the issue in the future.

practicalswift · 2018-02-23T08:29:16Z

@MarcoFalke Thanks to the implicit conversion back to the return type int64_t the wrap-around is contained to GetBlockProofEquivalentTime(…) so I don't think it is possible to construct a test for this.

Judging from the reviews of this PR it seems like the current code's reliance on wrap-around + implicit conversion is quite surprising which in itself is a reason to be explicit here. Explicit is better than implicit!

maflcko · 2018-02-23T14:00:16Z

Ah, sorry. My bad, I didn't read OP.

Then it should be possible to add a test case that (temporarily) wraps around, but passes before and after this change?

practicalswift · 2018-03-14T19:14:35Z

@MarcoFalke I'm not sure how that test would be constructed since GetBlockProofEquivalentTime(…) returns the correct value thanks to the conversion that takes place after the unsigned integer wrap-around has taken place. Perhaps I'm missing something? :-)

sipa · 2018-03-15T01:26:37Z

utACK de9517d59bc9943ec62ca26ed5f7111c9bc73b6c

practicalswift · 2018-04-16T14:32:29Z

@laanwj Willing to review? :-)

DrahtBot · 2018-07-20T20:30:28Z

The last travis run for this pull request was 269 days ago and is thus outdated. To trigger a fresh travis build, this pull request should be closed and re-opened.

DrahtBot · 2018-11-09T03:45:40Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#11535 (Avoid unintentional unsigned integer wraparounds 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 · 2018-11-15T22:21:12Z

I'm doing some PR cleaning and this PR has gotten a bit old :-)

This PR has received ACK/utACK:s from @MarcoFalke and the original author of the code @sipa (code introduced in f7303f9).

Does this PR still stand a chance of getting merged? Let me know otherwise and I'll close :-)

ken2812221

utACK d9ab663095a3c2b1e6c2bce70ad897e092b0f068

meshcollider · 2018-11-20T07:20:52Z

utACK d9ab663

promag · 2018-11-20T10:58:36Z

re-utACK d9ab663

…lentTime(...) when to.nChainWork <= from.nChainWork

practicalswift · 2018-11-23T15:57:35Z

Rebased!

ken2812221 · 2018-11-23T17:20:02Z

utACK 58e0342

meshcollider · 2018-11-30T21:12:39Z

re-utACK 58e0342

gmaxwell · 2018-11-30T21:21:29Z

This code looks wrong to me. GetLow64() appears to return a full range uint64 "return pn[0] | (uint64_t)pn[1] << 32;". Simply casting it to int if its out of range would introduce UB where there isn't any potential for UB now.

practicalswift · 2018-12-01T23:43:18Z

@gmaxwell That's already taken care of by if (r.bits() > 63) { … } on L147, right? :-)

(Pedantic nit: An out-of-range conversion from unsigned to signed would have resulted in implementation-defined behaviour and not UB, right? Not that implementation-defined behaviour is much better from a distributed consensus perspective :-))

gmaxwell · 2018-12-02T01:00:49Z

I was brain-farting a bit and thinking that (signed)(2^63 - 1)-1 was UB but it's actually the opposite case where -1 times a maximally negative number that I was thinking of (-(signed)(2^63 - 1)-1)-1. ... I'm hesitant to spend more time reviewing these kinds of changes than they take to write. It was also unclear if bits returned 63 or 64 on 1<<63, and I ultimately wrote a test to check. It's easy to introduce bugs with changes like this, and hard to review them to be absolutely sure. Sorry for the distraction there.

practicalswift changed the title ~~Fix invalid return value in GetBlockProofEquivalentTime(...) when to.nChainWork <= from.nChainWork~~ Fix unintentional wrap-around in GetBlockProofEquivalentTime(...) when to.nChainWork <= from.nChainWork Oct 23, 2017

practicalswift changed the title ~~Fix unintentional wrap-around in GetBlockProofEquivalentTime(...) when to.nChainWork <= from.nChainWork~~ Fix unintentional unsigned integer wrap-around in GetBlockProofEquivalentTime(...) when to.nChainWork <= from.nChainWork Oct 23, 2017

practicalswift force-pushed the proof-equivalent-time branch from adf44fc to de9517d Compare October 23, 2017 22:37

promag reviewed Oct 24, 2017

View reviewed changes

src/chain.cpp Outdated Show resolved Hide resolved

practicalswift changed the title ~~Fix unintentional unsigned integer wrap-around in GetBlockProofEquivalentTime(...) when to.nChainWork <= from.nChainWork~~ Fix unsigned integer wrap-around in GetBlockProofEquivalentTime Oct 24, 2017

fanquake added the Refactoring label Jan 22, 2018

DrahtBot closed this Jul 20, 2018

DrahtBot reopened this Jul 20, 2018

practicalswift mentioned this pull request Aug 31, 2018

wallet: Remove unused local variable old_label #14117

Closed

practicalswift mentioned this pull request Sep 24, 2018

mempool: Fix unintended unsigned integer wraparound in CTxMemPool::UpdateAncestorsOf(bool add, …) when add is false #14226

Closed

practicalswift mentioned this pull request Oct 4, 2018

fix assert crash when specified change output spend size is unknown #14380

Merged

practicalswift force-pushed the proof-equivalent-time branch from de9517d to d9ab663 Compare November 6, 2018 23:33

ken2812221 approved these changes Nov 19, 2018

View reviewed changes

DrahtBot added the Needs rebase label Nov 23, 2018

practicalswift added 2 commits November 23, 2018 16:57

Fix unintentional unsigned integer wrap-around in GetBlockProofEquiva…

3ed72c7

…lentTime(...) when to.nChainWork <= from.nChainWork

Remove UBSan suppression

58e0342

practicalswift force-pushed the proof-equivalent-time branch from d9ab663 to 58e0342 Compare November 23, 2018 15:57

DrahtBot removed the Needs rebase label Nov 23, 2018

practicalswift closed this Dec 2, 2018

practicalswift deleted the proof-equivalent-time branch April 10, 2021 19:36

bitcoin locked as resolved and limited conversation to collaborators Aug 18, 2022

Conversation

practicalswift commented Oct 23, 2017 • edited by DrahtBot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

meshcollider commented Oct 24, 2017

Uh oh!

practicalswift commented Oct 24, 2017

Uh oh!

promag left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

practicalswift commented Oct 24, 2017

Uh oh!

promag commented Oct 24, 2017

Uh oh!

practicalswift commented Oct 24, 2017

Uh oh!

practicalswift commented Oct 24, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

practicalswift commented Feb 22, 2018

Uh oh!

maflcko commented Feb 22, 2018

Uh oh!

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

Uh oh!

Uh oh!

maflcko commented Feb 23, 2018

Uh oh!

practicalswift commented Mar 14, 2018

Uh oh!

sipa commented Mar 15, 2018

Uh oh!

practicalswift commented Apr 16, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Jul 20, 2018

Uh oh!

DrahtBot commented Nov 9, 2018

Conflicts

Uh oh!

practicalswift commented Nov 15, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ken2812221 left a comment

Choose a reason for hiding this comment

Uh oh!

meshcollider commented Nov 20, 2018

Uh oh!

promag commented Nov 20, 2018

Uh oh!

practicalswift commented Nov 23, 2018

Uh oh!

ken2812221 commented Nov 23, 2018

Uh oh!

meshcollider commented Nov 30, 2018

Uh oh!

gmaxwell commented Nov 30, 2018

Uh oh!

practicalswift commented Dec 1, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

gmaxwell commented Dec 2, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

9 participants

practicalswift commented Oct 23, 2017 •

edited by DrahtBot

Loading

practicalswift commented Oct 24, 2017 •

edited

Loading

practicalswift commented Feb 23, 2018 •

edited

Loading

practicalswift commented Apr 16, 2018 •

edited

Loading

practicalswift commented Nov 15, 2018 •

edited

Loading

practicalswift commented Dec 1, 2018 •

edited

Loading