secp256k1: Valgrind errors with struct assignment on ARM and PPC64LE

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.