Fix unsigned integer wrap-around in GetBlockProofEquivalentTime #11551

pull practicalswift wants to merge 2 commits into bitcoin:master from practicalswift:proof-equivalent-time changing 2 files +1 −2
  1. practicalswift commented at 9:33 pm on October 23, 2017: contributor

    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:

    0int sign = 1;
1if (to.nChainWork > from.nChainWork) {
2…
3} else {
4    …
5    sign = -1;
6}
7…
8return 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 f7303f97933be33e34d482cf8348d180c8da2a26. Friendly ping @sipa - intentional or not? :-)

  2. practicalswift renamed this:
    Fix invalid return value in GetBlockProofEquivalentTime(...) when to.nChainWork <= from.nChainWork
    Fix unintentional wrap-around in GetBlockProofEquivalentTime(...) when to.nChainWork <= from.nChainWork
    on Oct 23, 2017
  3. practicalswift renamed this:
    Fix unintentional wrap-around in GetBlockProofEquivalentTime(...) when to.nChainWork <= from.nChainWork
    Fix unintentional unsigned integer wrap-around in GetBlockProofEquivalentTime(...) when to.nChainWork <= from.nChainWork
    on Oct 23, 2017
  4. practicalswift force-pushed on Oct 23, 2017
  5. meshcollider commented at 0:34 am on October 24, 2017: contributor
    Again, isn’t this part of #11535 too? Both are just avoiding unintentional unsigned integer wraparounds?
  6. practicalswift commented at 5:30 am on October 24, 2017: contributor
    @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 :-)
  7. in src/chain.cpp:150 in de9517d59b outdated 
    145@@ -146,7 +146,7 @@ int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& fr
146     if (r.bits() > 63) {
147         return sign * std::numeric_limits<int64_t>::max();
148     }
149-    return sign * r.GetLow64();
150+    return sign * static_cast<int64_t>(r.GetLow64());
    promag commented at 8:47 am on October 24, 2017:
    Correct me if I’m wrong, but if GetLow64() result is greater than 9223372036854775807 then the cast result is negative?
    sipa commented at 8:54 am on October 24, 2017:
    It can’t be, due to the if (r.bits() > 63) above.
    promag commented at 9:14 am on October 24, 2017:
    Ah right, and it’s like 2 lines above… Sorry.
  8. promag commented at 8:48 am on October 24, 2017: member
    Nit, shorter commit message Fix unsigned integer wrap-around in GetBlockProofEquivalentTime.
  9. practicalswift renamed this:
    Fix unintentional unsigned integer wrap-around in GetBlockProofEquivalentTime(...) when to.nChainWork <= from.nChainWork
    Fix unsigned integer wrap-around in GetBlockProofEquivalentTime
    on Oct 24, 2017
  10. practicalswift commented at 9:16 am on October 24, 2017: contributor
    @promag Nit addressed :-)
  11. promag commented at 9:19 am on October 24, 2017: member
    ACK de9517d.
  12. practicalswift commented at 9:21 am on October 24, 2017: contributor
    @promag Thanks a lot for reviewing! Would you mind taking a look at the wrap-arounds covered in #11535 too? :-)
  13. practicalswift commented at 2:26 pm on October 24, 2017: contributor
    @sipa What do you think about this change? Do you have time to review? :-)
  14. fanquake added the label Refactoring on Jan 22, 2018
  15. 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 :-)
  16. MarcoFalke commented at 11:17 pm on February 22, 2018: member
    @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.
  17. practicalswift commented at 8:29 am on February 23, 2018: contributor

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

  18. MarcoFalke commented at 2:00 pm on February 23, 2018: member

    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?

  19. practicalswift commented at 7:14 pm on March 14, 2018: contributor
    @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? :-)
  20. sipa commented at 1:26 am on March 15, 2018: member
    utACK de9517d59bc9943ec62ca26ed5f7111c9bc73b6c
  21. practicalswift commented at 2:32 pm on April 16, 2018: contributor
    @laanwj Willing to review? :-)
  22. DrahtBot commented at 8:30 pm on July 20, 2018: member
  23. DrahtBot closed this on Jul 20, 2018
  24. DrahtBot reopened this on Jul 20, 2018
  25. practicalswift force-pushed on Nov 6, 2018
  26. DrahtBot commented at 3:45 am on November 9, 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:

    • #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.

  27. practicalswift commented at 10:21 pm on November 15, 2018: contributor

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

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

  28. ken2812221 approved
  29. ken2812221 commented at 7:54 pm on November 19, 2018: contributor
    utACK d9ab663095a3c2b1e6c2bce70ad897e092b0f068
  31. promag commented at 10:58 am on November 20, 2018: member
    re-utACK d9ab663
  32. DrahtBot added the label Needs rebase on Nov 23, 2018
  33. Fix unintentional unsigned integer wrap-around in GetBlockProofEquivalentTime(...) when to.nChainWork <= from.nChainWork 3ed72c7212
  34. Remove UBSan suppression 58e034266c
  35. practicalswift force-pushed on Nov 23, 2018
  36. practicalswift commented at 3:57 pm on November 23, 2018: contributor
    Rebased!
  37. DrahtBot removed the label Needs rebase on Nov 23, 2018
  38. ken2812221 commented at 5:20 pm on November 23, 2018: contributor
    utACK 58e034266c9beeb83298dd4ac026136fdac21139
  40. gmaxwell commented at 9:21 pm on November 30, 2018: contributor
    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.
  41. practicalswift commented at 11:43 pm on December 1, 2018: contributor

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

  42. gmaxwell commented at 1:00 am on December 2, 2018: contributor
    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.
  43. practicalswift closed this on Dec 2, 2018
  44. practicalswift deleted the branch on Apr 10, 2021
  45. DrahtBot locked this on Aug 18, 2022


practicalswift meshcollider promag sipa MarcoFalke DrahtBot ken2812221 gmaxwell

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: 2024-10-04 22:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me