Document intentional and unintentional unsigned integer overflows (wraparounds) using annotations

practicalswift commented at 9:27 am on September 15, 2018: contributor

~~Add -fsanitize=integer Travis job~~
Document unsigned integer overflows (wraparounds) using annotation ALLOW_WRAPAROUND (intentional) or WARNING_UNINTENTIONAL_WRAPAROUND (unintentional).

practicalswift renamed this:
~~Annotate unsigned integer overflows. Add Travis job with -fsanitize=integer.~~
Annotate unsigned integer overflows. Add -fsanitize=integer Travis job.
on Sep 15, 2018

fanquake added the label Refactoring on Sep 15, 2018

fanquake added the label Tests on Sep 15, 2018

ken2812221 commented at 9:46 am on September 15, 2018: contributor

Concept ACK.

in .travis.yml:122 in c65df56f68 outdated

123+        HOST=x86_64-unknown-linux-gnu
124+        PACKAGES="clang python3-zmq qtbase5-dev qttools5-dev-tools libssl1.0-dev libevent-dev bsdmainutils libboost-system-dev libboost-filesystem-dev libboost-chrono-dev libboost-test-dev libboost-thread-dev libdb5.3++-dev libminiupnpc-dev libzmq3-dev libprotobuf-dev protobuf-compiler libqrencode-dev"
125+        NO_DEPENDS=1
126+        RUN_BENCH=false
127+        UBSAN_OPTIONS="suppressions=../contrib/sanitizers-ubsan-integer.suppressions"
128+        RUN_FUNCTIONAL_TESTS=false # Disabled for now, can be combined with the other x86_64 linux NO_DEPENDS job when functional tests pass the sanitizers

ken2812221 commented at 9:48 am on September 15, 2018:

Can’t we pass the functional tests with integer sanitizer even we suppress those cases?

practicalswift commented at 2:44 pm on September 15, 2018:

I got it working locally but not on Travis which is a bit weird. I’m still investigating – the intention is to run also the functional tests under the sanitizer :-)

DrahtBot commented at 12:44 pm on September 15, 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:

#14651 (Refactor: Fix compiler warning in prevector.h by ldm5180)
#14605 (Return of the Banman by dongcarl)
#14194 (Annotate unused parameters with [[maybe_unused]] by practicalswift)
#13949 (Introduce MempoolObserver interface to break “policy/fees -> txmempool -> policy/fees” circular dependency by Empact)
#13937 (Track best-possible-headers (TheBlueMatt) by Sjors)
#13864 (validation: Document where we are intentionally ignoring bool return values from validation related functions by practicalswift)
#13815 (util: Add [[nodiscard]] to all {Decode,Parse}… functions returning bool by practicalswift)
#13804 (WIP: Transaction Pool Layer by MarcoFalke)
#13062 (Make script interpreter independent from storage type CScript by sipa)
#11535 (Avoid unintentional unsigned integer wraparounds by practicalswift)
#10729 (Wrap EvalScript in a ScriptExecution class by luke-jr)
#10443 (Add fee_est tool for debugging fee estimation code by ryanofsky)

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 force-pushed on Sep 15, 2018

practicalswift renamed this:
~~Annotate unsigned integer overflows. Add -fsanitize=integer Travis job.~~
Annotate unsigned integer overflows (wraparounds). Add -fsanitize=integer Travis job.
on Sep 15, 2018

arvidn commented at 2:42 am on September 16, 2018: none

there are a few #include<> directives that changed order, was that deliberate? I take it the idea is to make new code that relies on unsigned wrap-around semantics to be annotated, and current annotations to be removed as code is fixed. Is that right? would it make sense to use a different name for the macro? something like: ALLOW_WRAPAROUND.

nit: technically unsigned integers don’t overflow, all operators on unsigned have modulo-2 arithmetic, so all results will always fit in the resulting variable.

practicalswift force-pushed on Sep 16, 2018

practicalswift renamed this:
~~Annotate unsigned integer overflows (wraparounds). Add -fsanitize=integer Travis job.~~
Add -fsanitize=integer Travis job. Annotate unsigned integer overflows (wraparounds).
on Sep 16, 2018

practicalswift renamed this:
~~Add -fsanitize=integer Travis job. Annotate unsigned integer overflows (wraparounds).~~
Add -fsanitize=integer Travis job. Document unsigned integer overflows (wraparounds) using annotation ALLOW_WRAPAROUND.
on Sep 16, 2018

gmaxwell commented at 7:14 am on September 16, 2018: contributor

Please don’t just blindly permit existing cases that might actually be bugs. If we must do this with bypasses, the annotation macro should be different for cases where the modular arithmetic is intentional (e.g. hash functions) and where we’re just silencing the warning in order to get something merged.

practicalswift commented at 7:18 am on September 16, 2018: contributor

@arvidn ALLOW_WRAPAROUND is a much better name. Updated!

Yes, the include sorting was deliberate.

Yes, the idea is to make it so that new code that relies on unsigned wrap-around semantics is annotated. I’ve now added the following to the developer notes to clarify:

Do not rely on unsigned wrap-around semantics unless there are good reasons for doing so (e.g. hashing). Functions that rely on on unsigned wrap-around semantics should be annotated using ALLOW_WRAPAROUND.

Rationale: Code relying on unsigned wrap-around semantics is legal and well-defined but error-prone.

Looks good?

gmaxwell commented at 7:24 am on September 16, 2018: contributor

I don’t agree that it is error prone. I’m aware of no study which shows as much, and it’s not my experience that intentional use of modular arithmetic results in bugs.

The comment should state that intentional use of it needs to be annotated because unintended wraps are often bugs and we use instrumentation to look for those bugs.

But so long as the patch just papers over behaviour that is probably buggy– or only not buggy by chance–, I think my position is NAK.

practicalswift commented at 7:24 am on September 16, 2018: contributor

@gmaxwell The bulk of the existing ones were handled in #11535 which was submitted almost a year ago :-)

My main goal with this PR is to make sure we’re not introducing new unintentional integer wrap arounds. Until #11535 is merged I’m afraid we need ALLOW_WRAPAROUND to make -fsanitize=integer pass, no?

Please advice on how to proceed :-)

practicalswift commented at 7:27 am on September 16, 2018: contributor

@gmaxwell Yes, intentional use of wraparound semantics (e.g. hashing code) is obviously not problematic. I’ll update the developer note to make that crystal clear.

practicalswift commented at 7:36 am on September 16, 2018: contributor

@gmaxwell

I don’t agree that it is error prone. I’m aware of no study which shows as much

From the paper “Understanding Integer Overflow in C/C++” co-authored by Regehr:

IOC’s instrumentation is designed to be semantically transparent for programs that conform to the C or C++ language standards, except in the case where a user requests additional checking for conforming but error-prone operations, e.g., wraparound with unsigned integer types.

.-)

practicalswift force-pushed on Sep 16, 2018

practicalswift commented at 1:04 pm on September 16, 2018: contributor

@arvidn @gmaxwell Thanks for reviewing. I’ve now updated the developer notes and split the annotations in two as suggested by @gmaxwell: ALLOW_WRAPAROUND for intentional wraparounds and WARNING_UNINTENTIONAL_WRAPAROUND for unintentional wraparounds.

Could you please re-review? :-)

These are the intentional wraparounds:

 0$ git grep ALLOW_WRAPAROUND -- "*.cpp" "*.h" ":(exclude)src/attributes.h"
 1src/bloom.cpp:ALLOW_WRAPAROUND static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, const std::vector<unsigned char>& vDataToHash) {
 2src/crypto/chacha20.cpp:ALLOW_WRAPAROUND void ChaCha20::Output(unsigned char* c, size_t bytes)
 3src/crypto/ripemd160.cpp:ALLOW_WRAPAROUND void inline Round(uint32_t& a, uint32_t b, uint32_t& c, uint32_t d, uint32_t e, uint32_t f, uint32_t x, uint32_t k, int r)
 4src/crypto/ripemd160.cpp:ALLOW_WRAPAROUND void Transform(uint32_t* s, const unsigned char* chunk)
 5src/crypto/sha1.cpp:ALLOW_WRAPAROUND void inline Round(uint32_t a, uint32_t& b, uint32_t c, uint32_t d, uint32_t& e, uint32_t f, uint32_t k, uint32_t w)
 6src/crypto/sha1.cpp:ALLOW_WRAPAROUND void Transform(uint32_t* s, const unsigned char* chunk)
 7src/crypto/sha256.cpp:ALLOW_WRAPAROUND void inline Round(uint32_t a, uint32_t b, uint32_t c, uint32_t& d, uint32_t e, uint32_t f, uint32_t g, uint32_t& h, uint32_t k)
 8src/crypto/sha256.cpp:ALLOW_WRAPAROUND void Transform(uint32_t* s, const unsigned char* chunk, size_t blocks)
 9src/crypto/sha512.cpp:ALLOW_WRAPAROUND void inline Round(uint64_t a, uint64_t b, uint64_t c, uint64_t& d, uint64_t e, uint64_t f, uint64_t g, uint64_t& h, uint64_t k, uint64_t w)
10src/crypto/sha512.cpp:ALLOW_WRAPAROUND void Transform(uint64_t* s, const unsigned char* chunk)
11src/hash.cpp:ALLOW_WRAPAROUND unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector<unsigned char>& vDataToHash)
12src/hash.cpp:ALLOW_WRAPAROUND CSipHasher& CSipHasher::Write(uint64_t data)
13src/hash.cpp:ALLOW_WRAPAROUND CSipHasher& CSipHasher::Write(const unsigned char* data, size_t size)
14src/hash.cpp:ALLOW_WRAPAROUND uint64_t CSipHasher::Finalize() const
15src/hash.cpp:ALLOW_WRAPAROUND uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val)
16src/hash.cpp:ALLOW_WRAPAROUND uint64_t SipHashUint256Extra(uint64_t k0, uint64_t k1, const uint256& val, uint32_t extra)

These are the unintentional wraparounds:

 0$ git grep WARNING_UNINTENTIONAL_WRAPAROUND -- "*.cpp" "*.h" ":(exclude)src/attributes.h"
 1src/arith_uint256.h:    WARNING_UNINTENTIONAL_WRAPAROUND base_uint& operator++()
 2src/bench/bench.h:    WARNING_UNINTENTIONAL_WRAPAROUND inline bool KeepRunning()
 3src/chain.cpp:WARNING_UNINTENTIONAL_WRAPAROUND int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
 4src/chain.h:    WARNING_UNINTENTIONAL_WRAPAROUND int Height() const {
 5src/core_write.cpp:WARNING_UNINTENTIONAL_WRAPAROUND std::string FormatScript(const CScript& script)
 6src/policy/fees.cpp:WARNING_UNINTENTIONAL_WRAPAROUND double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
 7src/prevector.h:    WARNING_UNINTENTIONAL_WRAPAROUND reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
 8src/prevector.h:    WARNING_UNINTENTIONAL_WRAPAROUND const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
 9src/script/interpreter.cpp:WARNING_UNINTENTIONAL_WRAPAROUND bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror)
10src/txmempool.cpp:WARNING_UNINTENTIONAL_WRAPAROUND void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors)
11src/txmempool.cpp:WARNING_UNINTENTIONAL_WRAPAROUND void CTxMemPoolEntry::UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount)
12src/txmempool.cpp:WARNING_UNINTENTIONAL_WRAPAROUND void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps)
13src/utilstrencodings.cpp:WARNING_UNINTENTIONAL_WRAPAROUND void SplitHostPort(std::string in, int &portOut, std::string &hostOut) {
14src/validation.cpp:WARNING_UNINTENTIONAL_WRAPAROUND DisconnectResult CChainState::DisconnectBlock(const CBlock& block, const CBlockIndex* pindex, CCoinsViewCache& view)
15src/validation.cpp:WARNING_UNINTENTIONAL_WRAPAROUND bool CChainState::AcceptBlock(const std::shared_ptr<const CBlock>& pblock, CValidationState& state, const CChainParams& chainparams, CBlockIndex** ppindex, bool fRequested, const CDiskBlockPos* dbp, bool* fNewBlock)
16src/validation.cpp:WARNING_UNINTENTIONAL_WRAPAROUND bool LoadMempool(void)

Looks correct? :-)

practicalswift renamed this:
~~Add -fsanitize=integer Travis job. Document unsigned integer overflows (wraparounds) using annotation ALLOW_WRAPAROUND.~~
Add -fsanitize=integer Travis job. Document unsigned integer overflows (wraparounds) using annotation ALLOW_WRAPAROUND (intentional) or WARNING_UNINTENTIONAL_WRAPAROUND (unintentional).
on Sep 16, 2018

practicalswift renamed this:
~~Add -fsanitize=integer Travis job. Document unsigned integer overflows (wraparounds) using annotation ALLOW_WRAPAROUND (intentional) or WARNING_UNINTENTIONAL_WRAPAROUND (unintentional).~~
Add -fsanitize=integer Travis job. Document intentional and unintentional unsigned integer overflows (wraparounds) using annotations.
on Sep 16, 2018

practicalswift force-pushed on Sep 17, 2018

practicalswift commented at 12:29 pm on September 17, 2018: contributor

@ken2812221 Now running also the functional tests and the quick bench test. Please re-review :-)

practicalswift force-pushed on Sep 17, 2018

in doc/developer-notes.md:450 in 9ce5e11584 outdated

438@@ -439,6 +439,14 @@ General C++
439 
440   - *Rationale*: This avoids memory and resource leaks, and ensures exception safety
441 
442+- Do not rely on unsigned wrap-around semantics unless there are good reasons for doing so (e.g. hash functions).
443+  Functions that intentionally rely on unsigned wrap-around semantics should be annotated using `ALLOW_WRAPAROUND`.
444+  Functions that unintentionally trigger unsigned wrap-arounds should be annotated using
445+  `WARNING_UNINTENTIONAL_WRAPAROUND` while awaiting being fixed.

arvidn commented at 2:37 pm on September 17, 2018:

would it be unrealistic to fix all these before landing this patch, so this annotation is not needed?

practicalswift commented at 2:49 pm on September 17, 2018:

@arvidn My main goal with this PR is to make it less likely that we introduce new unintentional wraparounds going forward, so I’ll choose the quickest route to get this checked by Travis.

The progress in #11535 which fixes these cases has been quite slow during the last year, so perhaps it would make sense to first get this PR merged and then take on fixing WARNING_UNINTENTIONAL_WRAPAROUND? That way we get the much needed Travis checking sooner rather than later :-)

DrahtBot added the label Needs rebase on Sep 20, 2018

practicalswift force-pushed on Sep 21, 2018

practicalswift renamed this:
~~Add -fsanitize=integer Travis job. Document intentional and unintentional unsigned integer overflows (wraparounds) using annotations.~~
Document intentional and unintentional unsigned integer overflows (wraparounds) using annotations
on Sep 21, 2018

practicalswift force-pushed on Sep 21, 2018

DrahtBot removed the label Needs rebase on Sep 21, 2018

practicalswift commented at 1:06 pm on September 21, 2018: contributor

I’ve now changed this PR to only add annotations.

The Travis checking is added in #14252 independently of the annotations.

Also rebased.

DrahtBot added the label Needs rebase on Sep 21, 2018

practicalswift force-pushed on Sep 22, 2018

DrahtBot removed the label Needs rebase on Sep 22, 2018

practicalswift force-pushed on Sep 30, 2018

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

practicalswift force-pushed on Nov 5, 2018

DrahtBot added the label Needs rebase on Nov 6, 2018

practicalswift force-pushed on Nov 6, 2018

DrahtBot removed the label Needs rebase on Nov 6, 2018

MarcoFalke deleted a comment on Nov 6, 2018

DrahtBot added the label Needs rebase on Nov 12, 2018

Document unsigned integer wraparounds with ALLOW_WRAPAROUND (intentional) or WARNING_UNINTENTIONAL_WRAPAROUND (unintentional) c1c726efb8

Add developer note about ALLOW_WRAPAROUND 0373038ced

practicalswift force-pushed on Nov 12, 2018

DrahtBot removed the label Needs rebase on Nov 12, 2018

practicalswift closed this on Nov 12, 2018

practicalswift deleted the branch on Apr 10, 2021

DrahtBot locked this on Aug 18, 2022

Document intentional and unintentional unsigned integer overflows (wraparounds) using annotations #14224

Conflicts