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

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

Concept ACK.

<!--e57a25ab6845829454e8d69fc972939a-->

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

<!--174a7506f384e20aa4161008e828411d-->

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.

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.

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.

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

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.

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

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

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

.-)

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

$ git grep ALLOW_WRAPAROUND -- "*.cpp" "*.h" ":(exclude)src/attributes.h"
src/bloom.cpp:ALLOW_WRAPAROUND static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, const std::vector<unsigned char>& vDataToHash) {
src/crypto/chacha20.cpp:ALLOW_WRAPAROUND void ChaCha20::Output(unsigned char* c, size_t bytes)
src/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)
src/crypto/ripemd160.cpp:ALLOW_WRAPAROUND void Transform(uint32_t* s, const unsigned char* chunk)
src/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)
src/crypto/sha1.cpp:ALLOW_WRAPAROUND void Transform(uint32_t* s, const unsigned char* chunk)
src/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)
src/crypto/sha256.cpp:ALLOW_WRAPAROUND void Transform(uint32_t* s, const unsigned char* chunk, size_t blocks)
src/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)
src/crypto/sha512.cpp:ALLOW_WRAPAROUND void Transform(uint64_t* s, const unsigned char* chunk)
src/hash.cpp:ALLOW_WRAPAROUND unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector<unsigned char>& vDataToHash)
src/hash.cpp:ALLOW_WRAPAROUND CSipHasher& CSipHasher::Write(uint64_t data)
src/hash.cpp:ALLOW_WRAPAROUND CSipHasher& CSipHasher::Write(const unsigned char* data, size_t size)
src/hash.cpp:ALLOW_WRAPAROUND uint64_t CSipHasher::Finalize() const
src/hash.cpp:ALLOW_WRAPAROUND uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val)
src/hash.cpp:ALLOW_WRAPAROUND uint64_t SipHashUint256Extra(uint64_t k0, uint64_t k1, const uint256& val, uint32_t extra)

These are the unintentional wraparounds:

$ git grep WARNING_UNINTENTIONAL_WRAPAROUND -- "*.cpp" "*.h" ":(exclude)src/attributes.h"
src/arith_uint256.h:    WARNING_UNINTENTIONAL_WRAPAROUND base_uint& operator++()
src/bench/bench.h:    WARNING_UNINTENTIONAL_WRAPAROUND inline bool KeepRunning()
src/chain.cpp:WARNING_UNINTENTIONAL_WRAPAROUND int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
src/chain.h:    WARNING_UNINTENTIONAL_WRAPAROUND int Height() const {
src/core_write.cpp:WARNING_UNINTENTIONAL_WRAPAROUND std::string FormatScript(const CScript& script)
src/policy/fees.cpp:WARNING_UNINTENTIONAL_WRAPAROUND double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
src/prevector.h:    WARNING_UNINTENTIONAL_WRAPAROUND reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
src/prevector.h:    WARNING_UNINTENTIONAL_WRAPAROUND const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
src/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)
src/txmempool.cpp:WARNING_UNINTENTIONAL_WRAPAROUND void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors)
src/txmempool.cpp:WARNING_UNINTENTIONAL_WRAPAROUND void CTxMemPoolEntry::UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount)
src/txmempool.cpp:WARNING_UNINTENTIONAL_WRAPAROUND void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps)
src/utilstrencodings.cpp:WARNING_UNINTENTIONAL_WRAPAROUND void SplitHostPort(std::string in, int &portOut, std::string &hostOut) {
src/validation.cpp:WARNING_UNINTENTIONAL_WRAPAROUND DisconnectResult CChainState::DisconnectBlock(const CBlock& block, const CBlockIndex* pindex, CCoinsViewCache& view)
src/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)
src/validation.cpp:WARNING_UNINTENTIONAL_WRAPAROUND bool LoadMempool(void)

Looks correct? :-)

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

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

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

Also rebased.