Valgrind errors with struct assignment on ARM and PPC64LE

[gmaxwell]

For some time there has been a clang issue where clang emits a memcpy of a struct to itself and valgrind flags it as undefined behaviour. Clang developers gave the response that when the compiler does it, nothing is undefined behaviour. This is response is mostly true, but memcpy is a libc defined function and can change its behaviour out from under the compiler (and has in the past, it used to work okay with overlapping memory) -- in fact, memcpy can be replaced by dynamic linker at runtime (at the direction of the caller).

In any case wisdom of clang's behaviour aside, valgrind can't tell if it was the code or the compiler (which is also part of why valgrind is useful for finding compiler induced non-constant time behaviour).

For this library it is a practical problem both because valgrind errors are rightfully frightening to developers who would call the library but also because some people want to make running valgrind part of "make check" which would potentially elevate these useless errors to build failures (and teach users to ignore these sorts of reports).

It's also the case that where these issues are triggered is unstable and highly environment specific.

E.g. PPC64LE Fedora 32 Clang 10.0.0-2 -Os fails but other optimization levels do not.

Checkout this matrix of configurations on ARM8:

CC=gcc CFLAGS='-Os -g' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --with-scalar=64bit --with-field=64bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=gcc CFLAGS='-Os -g' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --with-scalar=64bit --with-field=64bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=gcc CFLAGS='-O3 -g' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --with-scalar=64bit --with-field=64bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=clang CFLAGS='-O2 -g' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --with-scalar=64bit --with-field=64bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=clang CFLAGS='-Os -g' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --with-scalar=64bit --with-field=64bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 1 errors from 1 contexts 
CC=clang CFLAGS='-O3 -g' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --with-scalar=64bit --with-field=64bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=gcc CFLAGS='-O2 -g' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --with-scalar=32bit --with-field=32bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=gcc CFLAGS='-Os -g' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --with-scalar=32bit --with-field=32bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=gcc CFLAGS='-O3 -g' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --with-scalar=32bit --with-field=32bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=clang CFLAGS='-O2 -g' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --with-scalar=32bit --with-field=32bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=clang CFLAGS='-Os -g' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --with-scalar=32bit --with-field=32bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=clang CFLAGS='-O3 -g' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --with-scalar=32bit --with-field=32bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=gcc CFLAGS='-O2 -g' ./configure --with-bignum=no --enable-experimental --enable-endomorphism --enable-module-ecdh --enable-module-recovery --with-scalar=64bit --with-field=64bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=gcc CFLAGS='-Os -g' ./configure --with-bignum=no --enable-experimental --enable-endomorphism --enable-module-ecdh --enable-module-recovery --with-scalar=64bit --with-field=64bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 2 errors from 2 contexts 
CC=gcc CFLAGS='-O3 -g' ./configure --with-bignum=no --enable-experimental --enable-endomorphism --enable-module-ecdh --enable-module-recovery --with-scalar=64bit --with-field=64bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=clang CFLAGS='-O2 -g' ./configure --with-bignum=no --enable-experimental --enable-endomorphism --enable-module-ecdh --enable-module-recovery --with-scalar=64bit --with-field=64bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=clang CFLAGS='-Os -g' ./configure --with-bignum=no --enable-experimental --enable-endomorphism --enable-module-ecdh --enable-module-recovery --with-scalar=64bit --with-field=64bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 2 errors from 2 contexts 
CC=clang CFLAGS='-O3 -g' ./configure --with-bignum=no --enable-experimental --enable-endomorphism --enable-module-ecdh --enable-module-recovery --with-scalar=64bit --with-field=64bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=gcc CFLAGS='-O2 -g' ./configure --with-bignum=no --enable-experimental --enable-endomorphism --enable-module-ecdh --enable-module-recovery --with-scalar=32bit --with-field=32bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=gcc CFLAGS='-Os -g' ./configure --with-bignum=no --enable-experimental --enable-endomorphism --enable-module-ecdh --enable-module-recovery --with-scalar=32bit --with-field=32bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 2 errors from 2 contexts 
CC=gcc CFLAGS='-O3 -g' ./configure --with-bignum=no --enable-experimental --enable-endomorphism --enable-module-ecdh --enable-module-recovery --with-scalar=32bit --with-field=32bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=clang CFLAGS='-O2 -g' ./configure --with-bignum=no --enable-experimental --enable-endomorphism --enable-module-ecdh --enable-module-recovery --with-scalar=32bit --with-field=32bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=clang CFLAGS='-Os -g' ./configure --with-bignum=no --enable-experimental --enable-endomorphism --enable-module-ecdh --enable-module-recovery --with-scalar=32bit --with-field=32bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 
CC=clang CFLAGS='-O3 -g' ./configure --with-bignum=no --enable-experimental --enable-endomorphism --enable-module-ecdh --enable-module-recovery --with-scalar=32bit --with-field=32bit --disable-openssl-tests && make clean && make -j4 valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
ERROR SUMMARY: 0 errors from 0 contexts 

So out of 24 configurations, 4 fail.

Each of the failing cases look like:

==45040== Source and destination overlap in memcpy(0x1ffeffefe0, 0x1ffeffefe0, 84)
==45040==    at 0x484F1D4: __GI_memcpy (in /usr/lib/aarch64-linux-gnu/valgrind/vgpreload_memcheck-arm64-linux.so)
==45040==    by 0x486B5B3: secp256k1_ge_neg (group_impl.h:95)
==45040==    by 0x4870737: secp256k1_ecmult_const.constprop.0 (ecmult_const_impl.h:260)
==45040==    by 0x4872A6B: secp256k1_ecdh (main_impl.h:53)
==45040==    by 0x109137: main (valgrind_ctime_test.c:73)
==45040== 
==45040== Source and destination overlap in memcpy(0x1ffeffefe0, 0x1ffeffefe0, 84)
==45040==    at 0x484F1D4: __GI_memcpy (in /usr/lib/aarch64-linux-gnu/valgrind/vgpreload_memcheck-arm64-linux.so)
==45040==    by 0x486B5B3: secp256k1_ge_neg (group_impl.h:95)
==45040==    by 0x487075F: secp256k1_ecmult_const.constprop.0 (ecmult_const_impl.h:266)
==45040==    by 0x4872A6B: secp256k1_ecdh (main_impl.h:53)
==45040==    by 0x109137: main (valgrind_ctime_test.c:73)

(The clang build with only one error gets only the ecmult_const_impl.h:260 one, because :266 is endo only)

So there are failures with both GCC and Clang Os only. GCC does it for 32 and 64 only with endo. Clang does it only with 64 bit but doesn't care about endo.

GCC previously had a bug a long time ago on this which was closed as resolved: https://gcc.gnu.org/bugzilla//show_bug.cgi?id=19410

Bug in LLVM tracker: https://bugs.llvm.org/show_bug.cgi?id=11763

I think this is a serious impedement to using valgrind except as a development/review tool, because the location of these issues is unpredictable, depends on random build flags, depends on the compiler version, and could come and go due to unrelated changes to the codebase. There are a large number of struct assignments in the code too, so a large number of places where one could crop up.

[real-or-random]

Not beautiful but what about just suppressing theses errors https://www.valgrind.org/docs/manual/mc-manual.html#mc-manual.suppfiles, https://www.valgrind.org/docs/manual/manual-core.html#manual-core.suppress ?

[gmaxwell]

I think that won't work well: they can show up in 100 different places, they'll move around, etc. Obviously we're not going to be maintaining a separate file with every struct assignment in the codebase. :P

I think suppressions might be workable for our CI purposes where we're targeting a small set of compilers and if we move something we can up just fix it on the spot. We also should be concerned about callers: I don't want to know how many security critical programs went years without being tested under valgrind just because they linked openssl and it returned ub tainted randomness.

For something like the ct timer tester I think we could make it just totally suppress the memcpy arguments check-- that's not what we're looking for with that test.

[real-or-random]

I think that won't work well: they can show up in 100 different places, they'll move around, etc. Obviously we're not going to be maintaining a separate file with every struct assignment in the codebase. :P

The syntax is pretty clever, we could for example suppress it in secp256k1_ge_neg.

I think suppressions might be workable for our CI purposes where we're targeting a small set of compilers and if we move something we can up just fix it on the spot. We also should be concerned about callers: I don't want to know how many security critical programs went years without being tested under valgrind just because they linked openssl and it returned ub tainted randomness.

For something like the ct timer tester I think we could make it just totally suppress the memcpy arguments check-- that's not what we're looking for with that test.

I was thinking more into these directions. That the user can't use valgrind reliably is sad but not our fault and don't see what we could do about it except document it. And maybe report a valgrind bug. The only related bug I could find is https://bugs.kde.org/show_bug.cgi?id=148543.

[gmaxwell]

Yeah, we should talk to the valgrind authors. This isn't technically a valgrind bug and GCC has previously fixed the behaviour. But LLVM/Clang indicate that they will not change the behaviour and instead require that they be used with a libc that can self memcpy safely, and this isn't a crazy position.

The memcpy-to-self seems like something that is pretty unlikely to be an actual bug, so perhaps at a minimum valgrind could be convinced to classify that as a different kind of error from general overlap.

[gmaxwell]

Do we know anyone that is involved in the C standard? ... perhaps they could be convinced to at least elevate self-memcpy to implementation defined. :) I normally don't consider the testing of something even started until a compiler bug or two is reported... getting the language changed would be a new bar to meet in the future. :)

[elichai]

Do we know anyone that is involved in the C standard? ... perhaps they could be convinced to at least elevate self-memcpy to implementation defined. :) I normally don't consider the testing of something even started until a compiler bug or two is reported... getting the language changed would be a new bar to meet in the future. :)

I think I might know someone on twitter, I'll post a tweet and start tagging :)

[real-or-random]

Some more references:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=32667

https://web.archive.org/web/20180926060810/http://valgrind.10908.n7.nabble.com/memcpy-x-x-n-is-not-OK-clang-llvm-vs-memcheck-td44514.html

I'm not very motivated to talk to Valgrind after this thread but yeah, it's old, hm.

Do we know anyone that is involved in the C standard? ... perhaps they could be convinced to at least elevate self-memcpy to implementation defined. :)

I don't believe that this is a language issue. I tend to agree with the clang devs here.

[gmaxwell]

Clang devs don't have any control over libc. But if they think must-support-memcpy-self is a reasonable requirement for memcpy, then isn't that a case that it's a reasonable implementation defined behaviour for memcpy? ::shrugs:: That is in fact defacto what they're relying on now-- that they're only used with a memcpy that has an implementation defined behaviour for self copies.

You shouldn't let that thread throw you on valgrind-- the person with the argument for not changing valgrind doesn't appear to listed as a valgrind author, could just be an internet hothead. I'm not sure what change I'd ask from valgrind other than making it so you can separately suppress memcpy-self from overlaps (if that isn't already the case). I wouldn't want it to stop returning errors for actual bugs in source code.

[Especially now that I see that thread pointed out a plausible memcpy construction that would break self assignment.]

[real-or-random]

Clang devs don't have any control over libc. But if they think must-support-memcpy-self is a reasonable requirement for memcpy, then isn't that a case that it's a reasonable implementation defined behaviour for memcpy? ::shrugs::

I think this would miss the point. Clang and libc together form a C implementation, and things like "implementation-defined" apply to C programs calling memcpy and not to internal calls between one part of a C implementation and another part, these are literally implementation details. You're right of course, it's somewhat crazy for clang to rely on it if you control only half of the C implementation, and rely on undocumented behavior provided by the other part. (I don't know enough to judge about the potential real issues on PowerPC.)

You shouldn't let that thread throw you on valgrind-- the person with the argument for not changing valgrind doesn't appear to listed as a valgrind author, could just be an internet hothead. I'm not sure what change I'd ask from valgrind other than making it so you can separately suppress memcpy-self from overlaps (if that isn't already the case). I wouldn't want it to stop returning errors for actual bugs in source code.

Fair. Do you want to give a try? Otherwise I can do it next week or so, I guess I don't have the time right now.

[gmaxwell]

it's somewhat crazy for clang to rely on it if you control only half of the C implementation,

Yeah. That's also my point. They're perfectly right that the "implementation" (complier + libc) can do whatever it wants, I agree. But relying on undocumented libc behaviour is not wise, esp because glibc has changed before -- memcpy on overlapping regions used to work.

Fair. Do you want to give a try? Otherwise I can do it next week or so, I guess I don't have the time right now.

I'm going to seek some friendly input for a few days first, but sure.

[elichai]

I can no longer reproduce this, not with clang or with gcc, I'm not sure if it is because of a code change or new compilers or valgrind changed

$ clang --version
clang version 11.0.0 (https://github.com/llvm/llvm-project.git 176249bd6732a8044d457092ed932768724a6f06)
Target: x86_64-unknown-linux-gnu

$ gcc --version
gcc (GCC) 10.2.0

$ CC=clang CFLAGS='-Os' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --enable-module-schnorrsig --enable-module-extrakeys --disable-openssl-tests && make clean && make valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
==3791018== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

$ CC=gcc CFLAGS='-Os' ./configure --with-bignum=no --enable-experimental --enable-module-ecdh --enable-module-recovery --enable-module-schnorrsig --enable-module-extrakeys --disable-openssl-tests && make clean &&make valgrind_ctime_test && libtool --mode=execute valgrind ./valgrind_ctime_test
==3793460== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

[real-or-random]

@elichai I'm not sure if we ever had this issue on x86_64. The matrix in the initial comment is on ARM8.

[elichai]

@elichai I'm not sure if we ever had this issue on x86_64. The matrix in the initial comment is on ARM8.

Oops I forgot that part. you're right.

[real-or-random]

This seems to happen with clang 7 also on -O2 builds:
https://app.shippable.com/github/real-or-random/secp256k1/runs/9/29/console (I was playing around with Shippable as a CI)
Not sure what the crucial difference here is to Travis, which also runs clang 7. Maybe it's that Shippable uses an older valgrind version,

[real-or-random]

Fair. Do you want to give a try? Otherwise I can do it next week or so, I guess I don't have the time right now.

I'm going to seek some friendly input for a few days first, but sure.

@gmaxwell Did you reach out to them?