memcmp with constants that contain zero bytes are broken in GCC

[sipa]

It appears that there is a bug in certain GCC releases (in the version 9 and 10 series) where an optimization step breaks correctness of memcmp when at least one of the arguments is a compile-time constant array that contains at least one zero byte.

GCC bug is here: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95189. It was stumbled upon by @roconnor-blockstream in bitcoin-core/secp256k1#822. It is being tracked for libsecp256k1 in bitcoin-core/secp256k1#823.

I have verified that in some instances it also affects C++, and may even affect std::lexicographical_compare.

This may be relevant in some of our code (in particular, the CNetAddr IP range checking does comparisons with constants that contain zeroes, but perhaps more).

Solutions:

• Build with -fno-builtin-memcmp, but we should measure performance impact.
• Very carefully inspect the codebase for potential cases, and use a custom memcmp for those.

TODO:

• Verify if compiler-generated memcmp calls may be affected as well

[sipa]

Another observation by @roconnor-blockstream: it seems memcmp(...) <= 0 is not affected, while memcmp(...) < 0.

[roconnor-blockstream]

Technically my claim was, from my very limited understanding, the bug can only change non-zero results from memcpy to zero results. Still, even in this case if the result of memcmp(x,y) is changed from a 1 to a 0, the value of memcmp(...) <= 0 will change from false to true.

[elichai]

Here is the example of the bug appearing when using the > operator on 2 arrays: https://godbolt.org/z/j5en9d
Here it appears with std::lexicographical_compare: https://godbolt.org/z/a6scYK

-fno-builtin-memcmp Doesn't do anything for either of these (as they didn't call memcmp)

[sipa]

@elichai Great find. That's... unfortunate.

It appears that code paths that use memcmp for (in)equality checks (e.g. memcmp(...) == 0) are unaffected. I suspect this means that automatically generated operator== on simple classes/structs aren't affected either. @real-or-random also found evidence for this in the bug's code.

However, @elichai's finding means that -fno-builtin-memcmp is not enough, as there are C++ headers that directly invoke __builtin_memcmp. Some possibilities (we're not restricted to just one of them, though):

• Outlaw compiling with affected compilers entirely (by introducing a sanity check, and a unit test)
• Figure out exactly which GCC -f... optimization flag controls the presence of the bug, and disabled that (always, or selectively on known-bad compilers)
• Find the subset of affected C++ headers, and remove them from the codebase (replace them with my_memcmp where needed or so).

[elichai]

Another worth mentioning is that arith_uint256 managed to dodge this: https://github.com/bitcoin/bitcoin/blob/master/src/arith_uint256.h#L217-L222

while manually going over all the -O2 flags in my GCC 10.2 I found that disabling these 5 flags make the bug disappear:
-fno-tree-dce -fno-tree-dominator-opts -fno-tree-fre -fno-tree-pre -fno-code-hoisting

quickly reading the description of these they don't sound like something we'd like to disable that quickly :(

[real-or-random]

This is a patch against the broken GCC versions that emits a warning when the bug could be triggered:
https://gist.github.com/real-or-random/1548239059158370416dfdc6a866329a

When I compile the project with this patch, I don't get any warning. That's good news. But unfortunately, this is not perfeclty sound. It catches all known examples but it fails to catch the std::lexicographical_compare example in this thread.... Maybe the reason is buried somewhere in this function but I don't know. https://gcc.gnu.org/onlinedocs/gcc-10.2.0/libstdc++/api/a00596_source.html#l01592

[roconnor-blockstream]

With

               location_t loc = EXPR_HAS_LOCATION(exp) ? EXPR_LOCATION (exp) : UNKNOWN_LOCATION;
               expanded_location s = expand_location (loc);
               fnotice(stderr, "%s:%d: Potentially miscompiled memcmp\n", s.file, s.line);

I get a not so usefully located message, but a message none the less:

/nix/store/034wplfrxzhmljmajhmyya2ahg4z0nbl-gcc-9.3.0/include/c++/9.3.0/bits/stl_algobase.h:940: Potentially miscompiled memcmp

[roconnor-blockstream]

Okay, I think I've cracked the puzzle:

               location_t loc = EXPR_HAS_LOCATION(exp) ? EXPR_LOCATION (exp) : UNKNOWN_LOCATION;
               loc = expansion_point_location_if_in_system_header(loc);
               emit_diagnostic(DK_DEBUG, loc, 0, "Potentially miscompiled memcmp");

In file included from /nix/store/23rhjr5qzbvf4kr0nwb5q3lkbxxl62jq-gcc-9.3.0/include/c++/9.3.0/algorithm:61,
                 from test4.cpp:1:
/nix/store/23rhjr5qzbvf4kr0nwb5q3lkbxxl62jq-gcc-9.3.0/include/c++/9.3.0/bits/stl_algobase.h: In function ‘int square(std::array<unsigned char, 3>)’:
/nix/store/23rhjr5qzbvf4kr0nwb5q3lkbxxl62jq-gcc-9.3.0/include/c++/9.3.0/bits/stl_algobase.h:940:41: debug: Potentially miscompiled memcmp
  940 |      if (int __result = __builtin_memcmp(__first1, __first2, __len))
      |   

expansion_point_location_if_in_system_header probably doesn't play a role, but maybe it doesn't hurt either.

[roconnor-blockstream]

I rebuilt bitcoin-0.20.1 (including libsecp256k1) using emit_diagnostic, and I also did not get any miscompiled memcmp messages.

[theuni]

I was curious to see how much work it would be to work around this, so I hacked up (and vendored) my libstdc++ headers in order to add detection for the guilty functions, and started a branch of workarounds.

The guilty v9 headers (which call __builtin_memcmp themselves) are:

• bits/char_traits.h
• bits/stl_algobase.h

v10 adds:

• array (I haven't looked into this one yet)

The workarounds mostly involve creating comparators for containers to avoid the default lexicographical_compare and getting rid of some std::equal usage. Those are pretty straightforward. But then I discovered that many of the boost string parsing functions end up being guilty.

For example:
boost::split(vDeploymentParams, strDeployment, boost::is_any_of(":")); ends up internally calling std::__equal<true>::equal().

And while this might be a good excuse to get rid of some of boost usage, I'm afraid that the boost libs themselves are going to be a problem. And I don't think we want to be patching boost to fix this.

Even worse than boost, glibc and libstdc++ themselves are likely affected as well (for different reasons).

I can push up my partial work if anyone is interested, but it's not looking like this is a good way forward.

[theuni]

I suspect this means that automatically generated operator== on simple classes/structs aren't affected either.

That seems to be the case from what I've seen so far, but we do end up in __builtin_memcmp when using a map/set of an array/vector of bytes, as those will use std::lexicographical_compare by default for comparison. There are lots of these in psbt.h, for example.

Thankfully there's an easy way to specify our own comparator:

struct VecByteComp {
    bool operator()(const std::vector<unsigned char>& lhs, const std::vector<unsigned char>& rhs) const {
        //TODO: fill in
        return true;
    }
};

...

-        std::set<std::vector<unsigned char>> key_lookup;
+        std::set<std::vector<unsigned char>, VecByteComp> key_lookup;

But as I mentioned above, working around those doesn't get us very far :(