memcmp may be miscompiled by GCC

real-or-random commented at 8:51 am on September 23, 2020: contributor

What about the other memcmp’s we have in actual production code? (bip340 tag, tweak add check, scratch impl, sha256 selftest) does this bug affect those too?

Originally posted by @elichai in #822 (comment)

context: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95189

real-or-random commented at 9:02 am on September 23, 2020: contributor

AFAIU (and I’m not 100% sure) this affects comparisons with fixed byte arrays which include zero bytes. The check may then early terminate at the first zero byte.

BIP340 tag: Strictly speaking yes, here we compare with a fixed string including zero bytes. Even though it will be weird if someone passed BIP0340/nonce\0AB or something like this. (and see #757 , maybe that’s not a great API anyway).
Tweak add check: probably not, no constants here.
scratch: here the byte array is scratch so this should be fine.
sha256 selftest: no zero byte in the outpur either.

In the tests we have many many memcmp calls, some even with the all-zero arrays.

elichai commented at 12:21 pm on September 23, 2020: contributor

BIP340 tag: Strictly speaking yes, here we compare with a fixed string including zero bytes. Even though it will be weird if someone passed BIP0340/nonce\0AB or something like this. (and see #757 , maybe that’s not a great API anyway).

I don’t think it’s explicit anywhere that the tag even needs to be a string, someone could use the timestamp of their product launch datetime, or their birthday as the tag, and that will contain zeros. (I have 0 idea if this is realistic or not, I do not know of products that use tagged hashes so don’t know if they used string/int/bytes as tag)

real-or-random commented at 12:44 pm on September 23, 2020: contributor

@elichai Indeed but I believe the bug only occurs with the zeros in the constant. We may want to verify/test this.

roconnor-blockstream commented at 3:42 pm on September 23, 2020: contributor

Is it sufficient to add a -fno-builtin-memcmp flag if it exists, (and maybe disable it if some autotools stuff has run and was unable to find the bug)?

(I have verified that my tests in #822 pass when -fno-builtin-memcmp is used.)

real-or-random commented at 4:22 pm on September 23, 2020: contributor

If “-fno-builtin-memcmp” is sufficient that sounds good. I think it would still be advisable to include an explicit memcmp test if no-builtin-memcmp is the solution

We could even include a self-test but I’m not sure about this.

And I’m still not sure if shipping our function is just better, even though it’s “extremely dumb” as to your adequate summary. Pragmatically, the implementation is trivial and will just work everywhere without any compiler detection magic etc. edit: Moreover, if the fix is in the code and not in the compiler flags, it’s possible to use check the GCC version in the preprocessor, if we want to do this.

roconnor-blockstream commented at 5:52 pm on September 23, 2020: contributor

If we do that will we be able to detect indirect calls to memcmp (I’m thinking via other libc calls)? In that sense -fno-builtin-memcmp is more robust.

roconnor-blockstream commented at 6:00 pm on September 23, 2020: contributor

how does a secp256k1_memcmp help change behaviour in other compilation units?

sipa commented at 6:01 pm on September 23, 2020: contributor

(I’m thinking via other libc calls)

Well we’re not going to be able to re-build libc. If there is an indirect bug due to libc being compiled with gcc and its memcmp calls working incorrectly, that would be a bug in the resulting libc library, and nothing we can do about that (except minimizing how much we rely on libc).

The compiler can in some cases “emit” memcmp calls automatically, though. I don’t know if that’s the case in our codebase, and I don’t know if that’s strictly for situations where a builtin wouldn’t/can’t be used - but if that is somehow subject to the same bug, having a custom memcmp function may not be enough.

sipa commented at 6:04 pm on September 23, 2020: contributor

Parallel Bitcoin Core issue: https://github.com/bitcoin/bitcoin/issues/20005

roconnor-blockstream commented at 6:15 pm on September 23, 2020: contributor

Oh sorry I didn’t mean fixing libc. I mean that the compiler hypothetically inlining some call to libc that in turn calls memcmp, that then gets optimized. I’m not familiar enough with C to have anything in particular in mind, so maybe it just isn’t a thing to worry about. TBH I was really thinking of something analogous to std::lexicographical_compare.

sipa commented at 6:20 pm on September 23, 2020: contributor

The compiler can’t inline calls to libc, as it doesn’t know what is in the called functions.

What is possible is that some functionality is implemented in libc headers, through inline functions or other builtins, that directly call memcmp/__builtin_memcmp. I can’t find any instances of this in my system C headers (except the definition of memcmp itself), though there are a few in STL C++ headers.

roconnor-blockstream commented at 7:05 pm on September 23, 2020: contributor

That is good to hear.

real-or-random referenced this in commit f5f1202b62 on Sep 24, 2020

elichai commented at 12:23 pm on September 25, 2020: contributor

The compiler can’t inline calls to libc, as it doesn’t know what is in the called functions.

I don’t believe this is true, a compiler target also encodes the exact libc variant that is used, and the compiler can use that knowledge to its advantage (see #/776 for example) a few examples of how without headers the compiler can remove calls to libc and replace them with equivalent instructions while assuming those calls don’t have side effects. (and are well known) https://godbolt.org/z/EKe4rx

EDIT: I see now that @sipa probably commented on this sentence by @roconnor-blockstream

I mean that the compiler hypothetically inlining some call to libc that in turn calls memcmp

I still believe this could happen, just like gcc turns this code into a “return 0”:

0#include <stddef.h>
1void *calloc(size_t nmemb, size_t size);
2int zeroed_alloc(int num) {
3    int* p = calloc(num, sizeof(int));
4    int ret = *p;
5    free(p);
6    return ret;
7}

real-or-random commented at 6:22 pm on September 25, 2020: contributor

Given that we have some evidence that this does not happen when the GCC knows that the return value is compared with != 0 or == 0, I tend towards ignoring the issue. This bug looked very bad but in the end the scope is very limited. As long as our code is not affected, this is not much different from hundreds of other compiler bugs (e.g. #585).

Of course #825 is a simple fix but it’s somewhat arbitrary then.

See also https://github.com/bitcoin/bitcoin/issues/20005#issuecomment-699078122, which does not show any potential issues in secp256k1.

sipa commented at 6:30 pm on September 25, 2020: contributor

@elichai Sure, the compiler may know things about how C standard library functions behave (because they’re specified by the standard, or because it knows additional promises the specifically used C standard library used makes). But (in general) it cannot actually look at the compiled library object code and inline it (in theory LTO could change that, but there is no LTO done for glibc IIRC). So just the fact that a particular function inside glibc is written using memcmp isn’t relevant - except to the extent that it may be miscompiled inside glibc itself - and there is nothing we can do about that.

sipa commented at 3:34 am on September 26, 2020: contributor

@real-or-random I don’t know - even with evidence that the current codebase is unaffected, it’s still scary - evidenced by the fact that we hit it randomly in PR #822 (thankfully in test-only code, but it could have been elsewhere).

real-or-random commented at 9:17 am on September 26, 2020: contributor

If people feel we should do #825, then I’m not against this. It certainly won’t hurt.

elichai commented at 9:23 am on September 26, 2020: contributor

@roconnor-blockstream

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

Can you also try this on libsecp with all the features on + tests?

roconnor-blockstream commented at 12:52 pm on September 26, 2020: contributor

We can make secp256k1_memcmp, but is solving the issue for libsecp256k1 meaningful if we don’t solve it for bitcoin?

real-or-random renamed this:
~~memcmp~~
memcmp may be miscompiled by GCC
on Oct 7, 2020

sipa referenced this in commit 6173839c90 on Oct 11, 2020

sipa closed this on Oct 14, 2020

roconnor-blockstream commented at 6:15 pm on October 14, 2020: contributor

Still nothing prevents reintroduction of memcmp other than diligence.

sipa reopened this on Oct 14, 2020

sipa commented at 6:37 pm on October 14, 2020: contributor

Let’s keep this open to discuss how an accidental memcmp can be prevent.

CI could do a simple grep for the word memcmp in the source code?

roconnor-blockstream commented at 6:41 pm on October 14, 2020: contributor

For reference real-or-random posted a clang-query command at #825 (comment).

real-or-random commented at 12:43 pm on October 15, 2020: contributor

If there is some CI test it could check if any function outside of the library is called, except for whitelisted ones (memset, memcpy, malloc, and free, I believe), no? Maybe also make sure that malloc and free are only called via the wrapper functions. That might be useful independently of the memcmp concerns.

Hm, do we really want to restrict ourselves to a small list of standard library functions? I don’t think the standard library is bad per se. Compiler bugs can happen everywhere, not only in calls to the standard library. Moreover, new calls are easily spotted in code review. I think memcmp is simply different because one needs to remember that memcmp is special.

If you want to give it a try: clang-query src/secp256k1.c -c 'match callExpr(allOf(unless(isExpansionInSystemHeader()), callee(functionDecl(isExpansionInSystemHeader()))))' This matches all calls to functions declared in system headers, unless the call itself happens in a system header.

roconnor-blockstream commented at 6:45 pm on October 15, 2020: contributor

If we are going to whitelist standard library functions, and I’m not arguing here that we should or shouldn’t, one possible solution is to write our own header of standard library prototypes from our whitelist and disallow all system include files. That said I don’t know how to enforce that system includes are disallowed.

elichai commented at 7:04 pm on October 15, 2020: contributor

That said I don’t know how to enforce that system includes are disallowed.

-nostdinc :), the main problem is stdint.h, which we want to manage for us all the int types in different targets

real-or-random commented at 7:39 pm on October 15, 2020: contributor

See also #833

real-or-random referenced this in commit 0114113708 on Oct 19, 2020

real-or-random referenced this in commit 4831f2ed4b on Oct 22, 2020

roconnor-blockstream commented at 1:46 pm on August 4, 2022: contributor

As fanquake noted in https://github.com/bitcoin/bitcoin/issues/20005#issuecomment-1205264613, this is fixed in GCC 10.3 and above.

benma commented at 9:45 am on October 11, 2024: contributor

I just lost an afternoon trying to debug a valgrind false positive.

https://github.com/bitcoin-core/secp256k1/pull/1140/files#diff-3fe8f8fa0b765ad49f70d6c32f6a865be48faeb3c8d6dd5f8c274ca546ef5b61R1111 (click ‘Load diff’ on tests_impl.h).

The line

0           CHECK(memcmp(output, input, sizeof(output)) == 0);

resulted in this CI failure:

https://github.com/bitcoin-core/secp256k1/actions/runs/11285462388/job/31388294841

 0==9263== Memcheck, a memory error detector
 1==9263== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.
 2==9263== Using Valgrind-3.24.0.GIT-lbmacos and LibVEX; rerun with -h for copyright info
 3==9263== Command: ./tests
 4==9263== 
 5test count = 2
 6random seed = ae250b1a3ee1ceb09ad0acfab0d10ecd
 7Skipping run_sha256_known_output_tests 1000000 (iteration count too low)
 8Skipping test_ecmult_constants_sha 2048 (iteration count too low)
 9Skipping test_ecmult_constants_2bit (iteration count too low)
10==9263== Conditional jump or move depends on uninitialised value(s)
11==9263==    at 0x7FF81B8D5D07: ???
12==9263==    by 0x10001A8C4: ??? (in ./tests)
13==9263==    by 0x10001CA1D: ??? (in ./tests)
14==9263==    by 0x10003DA27: ??? (in ./tests)
15==9263==    by 0x10026952D: (below main) (in /usr/lib/dyld)
16==9263== 
17==9263== Use of uninitialised value of size 8
18==9263==    at 0x7FF81B8D5D23: ???
19==9263==    by 0x10001A8C4: ??? (in ./tests)
20==9263==    by 0x10001CA1D: ??? (in ./tests)
21==9263==    by 0x10003DA27: ??? (in ./tests)
22==9263==    by 0x10026952D: (below main) (in /usr/lib/dyld)
23==9263== 
24==9263== Use of uninitialised value of size 8
25==9263==    at 0x7FF81B8D5D28: ???
26==9263==    by 0x10001A8C4: ??? (in ./tests)
27==9263==    by 0x10001CA1D: ??? (in ./tests)
28==9263==    by 0x10003DA27: ??? (in ./tests)
29==9263==    by 0x10026952D: (below main) (in /usr/lib/dyld)
30==9263== 
31==9263== Conditional jump or move depends on uninitialised value(s)
32==9263==    at 0x10001A8C7: ??? (in ./tests)
33==9263==    by 0x10001CA1D: ??? (in ./tests)
34==9263==    by 0x10003DA27: ??? (in ./tests)
35==9263==    by 0x10026952D: (below main) (in /usr/lib/dyld)
36==9263== 
37random run = ae7d7478f2fc4fde34e2625d2948ce83
38no problems found
39==9263== 
40==9263== HEAP SUMMARY:
41==9263==     in use at exit: 8,586 bytes in 169 blocks
42==9263==   total heap usage: 28,425 allocs, 28,256 frees, 98,898,807,326 bytes allocated
43==9263== 
44==9263== LEAK SUMMARY:
45==9263==    definitely lost: 4,160 bytes in 130 blocks
46==9263==    indirectly lost: 0 bytes in 0 blocks
47==9263==      possibly lost: 600 bytes in 3 blocks
48==9263==    still reachable: 3,826 bytes in 36 blocks
49==9263==         suppressed: 0 bytes in 0 blocks
50==9263== Rerun with --leak-check=full to see details of leaked memory
51==9263== 
52==9263== Use --track-origins=yes to see where uninitialised values come from
53==9263== For lists of detected and suppressed errors, rerun with: -s
54==9263== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 123 from 19)
55FAIL tests (exit status: 42)

I could not get valgrind to point me to the right line, so bisecting the line took a very long time. I don’t think anything is actually wrong with the code there.

In the end changing memcmp to secp256k1_memcmp_var fixed it.

This happened on macOS x86 for both gcc and clang. The valgrind check on linux worked fine.

Consider adding a CI check that forbids the use uf memcmp(), so no one else has to go through the pain of debugging something like this again :see_no_evil:

edit: @real-or-random

above you mention

Moreover, new calls are easily spotted in code review. I think memcmp is simply different because one needs to remember that memcmp is special.

This turned out to be a wrong assumption - in my case, no one pointed it out to me in review, and it was very hard for me to figure this one out. If the CI check had been added as discussed above, I would not have lost so much time on this.

memcmp may be miscompiled by GCC #823