Add support for msan instead of valgrind (for memcheck and ctime test)

sipa commented at 11:54 pm on December 6, 2022: contributor

This introduces an abstraction layer src/checkmem.h, which defines macros for interacting with memory checking tools. Depending on the environment, they’re mapped to MemorySanitizer builtins, Valgrind integration macros, or nothing at all.

This means that msan builds immediately benefit from existing undefined memory checks in the tests. It also means those builds result in a ctime_tests (new name for valgrind_ctime_test) binary that can usefully test constant-timeness (not inside Valgrind, and with the downside that it’s not running against a production library build, but it’s faster and available on more platforms).

Such an msan-ctime test is added to the Linux x86_64 msan CI job, as an example. More CI cases could be added (e.g. for MacOs or ARM Linux) later.

sipa force-pushed on Dec 6, 2022

sipa force-pushed on Dec 7, 2022

sipa cross-referenced this on Dec 7, 2022 from issue Add section on configuration flags to README by ZenulAbidin

sipa force-pushed on Dec 20, 2022

sipa commented at 3:49 am on December 20, 2022: contributor

Rebased after #1178 merge.

sipa force-pushed on Dec 20, 2022

in src/secp256k1.c:125 in f9e36d4c1f outdated

119@@ -116,7 +120,9 @@ secp256k1_context* secp256k1_context_preallocated_create(void* prealloc, unsigne
120     /* Flags have been checked by secp256k1_context_preallocated_size. */
121     VERIFY_CHECK((flags & SECP256K1_FLAGS_TYPE_MASK) == SECP256K1_FLAGS_TYPE_CONTEXT);
122     secp256k1_ecmult_gen_context_build(&ret->ecmult_gen_ctx);
123+#if SECP256K1_CHECKMEM_ENABLED
124     ret->declassify = !!(flags & SECP256K1_FLAGS_BIT_CONTEXT_DECLASSIFY);
125+#endif

real-or-random commented at 3:26 pm on December 20, 2022:

Should this raise the illegal callback if SECP256K1_FLAGS_BIT_CONTEXT_DECLASSIFY && !SECP256K1_CHECKMEM_ENABLED?

sipa commented at 5:27 pm on December 20, 2022:

Added (as a runtime check, rather than a compile-time one) in a separate commit, in secp256k1_context_preallocated_size.

in .cirrus.yml:331 in 6e99c5abfc outdated

327@@ -328,10 +328,11 @@ task:
328     ECDH: yes
329     RECOVERY: yes
330     SCHNORRSIG: yes
331-    CTIMETEST: no
332+    CTIMETEST: yes

real-or-random commented at 3:27 pm on December 20, 2022:

nit: maybe rename this variable to plural, too

sipa commented at 5:28 pm on December 20, 2022:

Done.

in src/secp256k1.c:74 in 6e99c5abfc outdated

71-    { secp256k1_default_error_callback_fn, 0 },
72-    0
73+    { secp256k1_default_error_callback_fn, 0 }
74+#if SECP256K1_CHECKMEM_ENABLED
75+    , 0
76+#endif

real-or-random commented at 3:33 pm on December 20, 2022:

(mostly educational) nit. Trailing commas are allowed in initializer lists, even back in C89:

0    { secp256k1_default_error_callback_fn, 0 },
1#if SECP256K1_CHECKMEM_ENABLED
2    0,
3#endif

sipa commented at 5:27 pm on December 20, 2022:

TIL, thanks.

real-or-random commented at 3:49 pm on December 20, 2022: contributor

I’m not entirely sure about dropping the declassify member from the struct. I don’t see anything immediately wrong about dropping it, but I think the reason why we currently always have it is to make sure the compiled code with valgrind support is as close as possible to the code without valgrind support. This makes testing easier because it (attempts to) avoid yet another config option (plus we save a few preprocessing directives).

sipa force-pushed on Dec 20, 2022

sipa commented at 5:28 pm on December 20, 2022: contributor

@real-or-random I’ve removed the declassify compile-time dependence; it does make sense to minimize the differences with and without.

in src/checkmem.h:66 in 2ce78dea5d outdated

61+#    include <valgrind/memcheck.h>
62+#    define SECP256K1_CHECKMEM_ENABLED 1
63+#    define SECP256K1_CHECKMEM_UNDEFINE(p, len) VALGRIND_MAKE_MEM_UNDEFINED((p), (len))
64+#    define SECP256K1_CHECKMEM_DEFINE(p, len) VALGRIND_MAKE_MEM_DEFINED((p), (len))
65+#    define SECP256K1_CHECKMEM_CHECK(p, len) VALGRIND_CHECK_MEM_IS_DEFINED((p), (len))
66+#    define SECP256K1_CHECKMEM_RUNNING() (RUNNING_ON_VALGRIND)

real-or-random commented at 8:21 pm on December 20, 2022:

When playing around with this on valgrind and reading the memcheck docs, I figured out this trick, which you may or may not take.

0     /* VALGRIND_MAKE_MEM_DEFINED returns 0 iff not running on memcheck.
1      * This is more precise than the RUNNING_ON_VALGRIND macro, which
2      * checks for valgrind in general instead of memcheck specifically. */
3#    define SECP256K1_CHECKMEM_RUNNING() (VALGRIND_MAKE_MEM_DEFINED(NULL, 0) != 0)

sipa commented at 8:26 pm on December 20, 2022:

Done!

I looked over the valgrind/*.h files briefly to find something like this, but missed this possibility.

real-or-random commented at 8:21 pm on December 20, 2022: contributor

Changes look good. I still want to test this locally on msan. I’ll probably do this tomorrow and ACK it then.

sipa force-pushed on Dec 20, 2022

real-or-random approved

real-or-random commented at 6:24 pm on December 21, 2022: contributor

ACK 2788ae70c2bb444365881ce4727e5325b132b0f3 I also tested that the ctimetest fails on valgrind and msan when I introduce variable-time code

Next step (after this PR) would then to run this on macos.

Fwiw, if anyone wonders: Unfortunately, this doesn’t work on mingw, which doesn’t support sanitizers.

sipa commented at 6:29 pm on December 21, 2022: contributor

@real-or-random There appears to be some work on a clang/mingw crossover (https://github.com/mstorsjo/llvm-mingw), but I’m not sure it’s mature enough to try (or whether it support msan; only ubsan and asan are listed).

real-or-random commented at 8:32 pm on December 21, 2022: contributor

@real-or-random There appears to be some work on a clang/mingw crossover (mstorsjo/llvm-mingw), but I’m not sure it’s mature enough to try (or whether it support msan; only ubsan and asan are listed).

It’s probably not worth the effort. I’d expect that the differences between different LLVM OS targets are rather small, or at least in areas such as binary formats, linkage, symbols, etc. and not in actual code generation. This is even more true in our case because we don’t really interact with the OS.

in src/checkmem.h:47 in 2788ae70c2 outdated

42+/* If compiling under msan, map the SECP256K1_CHECKMEM_* functionality to msan.
43+ * Choose this preferentially, even when VALGRIND is defined, as msan-compiled
44+ * binaries can't be run under valgrind anyway. */
45+#if defined(__has_feature)
46+#  if __has_feature(memory_sanitizer)
47+#    include <stddef.h>

real-or-random commented at 2:23 pm on January 3, 2023:

nit: Do we need this here? I think no. But we need it below where we use NULL.

sipa commented at 3:16 pm on January 3, 2023:

Fixed.

sipa force-pushed on Jan 3, 2023

real-or-random approved

real-or-random commented at 3:25 pm on January 3, 2023: contributor

ACK 6ef1afa3ff1437d47ce21aace4409a51ebf81aa5 I also tested that the ctimetest fails on valgrind and msan when I introduce variable-time code

in Makefile.am:125 in 6ef1afa3ff outdated

115@@ -119,18 +116,19 @@ if USE_TESTS
116 noinst_PROGRAMS += tests
117 tests_SOURCES = src/tests.c
118 tests_CPPFLAGS = $(SECP_INCLUDES) $(SECP_TEST_INCLUDES) $(SECP_CONFIG_DEFINES)
119-if VALGRIND_ENABLED

hebasto commented at 4:12 pm on January 3, 2023:

fc2ff99cfdc7005598826d0485aabe3abb349525 removes the last usage of the VALGRIND_ENABLED. The following line can be removed now as well https://github.com/bitcoin-core/secp256k1/blob/31ed5386e8450845c2cdbf1af9dd257937c46e48/configure.ac#L228

sipa commented at 9:35 pm on January 3, 2023:

Fixed.

hebasto commented at 4:58 pm on January 3, 2023: member

Testing 6ef1afa3ff1437d47ce21aace4409a51ebf81aa5 on Ubuntu 22.04:

 0$ ./autogen.sh
 1$ ./configure --enable-ctime-tests CFLAGS="-fsanitize=memory -O1" CC=clang
 2...
 3Build Options:
 4  with external callbacks = no
 5  with benchmarks         = yes
 6  with tests              = yes
 7  with ctime tests        = yes
 8  with coverage           = no
 9  with examples           = no
10  module ecdh             = yes
11  module recovery         = no
12  module extrakeys        = yes
13  module schnorrsig       = yes
14
15  asm                     = x86_64
16  ecmult window size      = 15
17  ecmult gen prec. bits   = 4
18
19  valgrind                = no
20  CC                      = clang
21  CPPFLAGS                =  
22  SECP_CFLAGS             = -O2  -std=c89 -pedantic -Wno-long-long -Wnested-externs -Wshadow -Wstrict-prototypes -Wundef -Wno-overlength-strings -Wall -Wno-unused-function -Wextra -Wcast-align -Wconditional-uninitialized -fvisibility=hidden 
23  CFLAGS                  = -fsanitize=memory -O1
24  LDFLAGS 
25$ make clean
26$ make
27$ ./libtool --mode=execute ./ctime_tests 
28==346524==WARNING: MemorySanitizer: use-of-uninitialized-value
29    [#0](/bitcoin-core-secp256k1/0/) 0x7f87d91c34e2 in secp256k1_scalar_mul secp256k1.c
30    [#1](/bitcoin-core-secp256k1/1/) 0x7f87d9193de5 in secp256k1_ecdsa_sign (/home/hebasto/git/secp256k1/.libs/libsecp256k1.so.1+0xbde5) (BuildId: 8a99d7711aeabba7b1dc311e74fedcef767eb76b)
31    [#2](/bitcoin-core-secp256k1/2/) 0x5618435418c7 in run_tests (/home/hebasto/git/secp256k1/.libs/ctime_tests+0xa48c7) (BuildId: 013cc8d2ba72c4e385d011449343a9ea11a16616)
32    [#3](/bitcoin-core-secp256k1/3/) 0x56184354145b in main (/home/hebasto/git/secp256k1/.libs/ctime_tests+0xa445b) (BuildId: 013cc8d2ba72c4e385d011449343a9ea11a16616)
33    [#4](/bitcoin-core-secp256k1/4/) 0x7f87d8e66d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
34    [#5](/bitcoin-core-secp256k1/5/) 0x7f87d8e66e3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f) (BuildId: 69389d485a9793dbe873f0ea2c93e02efaa9aa3d)
35    [#6](/bitcoin-core-secp256k1/6/) 0x5618434bb3a4 in _start (/home/hebasto/git/secp256k1/.libs/ctime_tests+0x1e3a4) (BuildId: 013cc8d2ba72c4e385d011449343a9ea11a16616)
36
37SUMMARY: MemorySanitizer: use-of-uninitialized-value secp256k1.c in secp256k1_scalar_mul
38Exiting

Is it expected?

real-or-random commented at 7:37 pm on January 3, 2023: contributor

@hebasto Yes, msan is not clever enough to work with our asm. Try disabling asm.

sipa force-pushed on Jan 3, 2023

real-or-random approved

real-or-random commented at 2:15 pm on January 4, 2023: contributor

ACK 39c35e727719536878521fdb0e41e1df8e466d80 I also tested that the ctimetest fails on valgrind and msan when I introduce variable-time code

real-or-random cross-referenced this on Jan 5, 2023 from issue Native jacobi symbol algorithm by sipa

sipa force-pushed on Jan 9, 2023

sipa commented at 4:19 pm on January 9, 2023: contributor

Rebased after #1188 merge.

real-or-random approved

real-or-random commented at 4:25 pm on January 10, 2023: contributor

ACK 472baae02b5ade196fdc1d229d3d52783bbc3b6f

the fourth time :)

real-or-random commented at 2:00 pm on January 11, 2023: contributor

the fourth time :)

needs rebase, so sorry…

Move valgrind CPPFLAGS into SECP_CONFIG_DEFINES 4f1a54e41d

Abstract interactions with valgrind behind new checkmem.h 0db05a770e

Add compile-time error to valgrind_ctime_test 8dc64079eb

Add support for msan integration to checkmem.h 8e11f89a68

Update error messages to suggest msan as well 6eed6c18de

Rename valgrind_ctime_test -> ctime_tests 5048be17e9

Make ctime tests building configurable 18974061a3

Run ctime test in Linux MSan CI job 5e2e6fcfc0

Add runtime checking for DECLASSIFY flag 74b026f05d

Rename CTIMETEST -> CTIMETESTS 0f088ec112

sipa force-pushed on Jan 11, 2023

sipa commented at 9:09 pm on January 11, 2023: contributor

Rebased after merge of #1187.

real-or-random approved

real-or-random commented at 1:05 pm on January 12, 2023: contributor

ACK 0f088ec11263261497661215c110a4c395acc0ac

real-or-random requested review from hebasto on Jan 12, 2023

hebasto approved

hebasto commented at 9:25 am on January 14, 2023: member

ACK 0f088ec11263261497661215c110a4c395acc0ac, I have reviewed the code and it looks OK. Able to build ctime_tests using MSan.

real-or-random merged this on Jan 16, 2023

real-or-random closed this on Jan 16, 2023

hebasto cross-referenced this on Jan 17, 2023 from issue build: Add CMake-based build system by hebasto

hebasto referenced this in commit c9af5208f6 on Jan 19, 2023

hebasto referenced this in commit 2cd4e3c0a9 on Jan 19, 2023

hebasto cross-referenced this on Jan 19, 2023 from issue Drop no longer used variables from the build system by hebasto

sipa referenced this in commit ad7433b140 on Jan 19, 2023

dhruv referenced this in commit 4d33046ce3 on Feb 1, 2023

dhruv referenced this in commit 55e7f2cf2b on Feb 2, 2023

stratospher referenced this in commit 647f63669e on Feb 6, 2023

dhruv referenced this in commit a4351c0df6 on Feb 20, 2023

stratospher referenced this in commit 23f825fc8b on Feb 21, 2023

hebasto commented at 5:20 pm on February 22, 2023: member

From https://www.amongbytes.com/post/20210709-testing-constant-time/ it follows that MSan, due to its speed-optimized design, is less accurate than Valgrind.

Should it be mentioned in this repo’s docs somehow?

real-or-random commented at 8:46 am on February 23, 2023: contributor

Valgrind is also better for other reasons: Because it works on the normal binary without instrumentation, it also covers ASM, and checked code is exactly what people will run in production.

We currently don’t have any docs for constant-time tests. Creating them will be the first step. And yes, then it probably makes sense to mention limitations.

hebasto referenced this in commit 7c0cc5d976 on Mar 7, 2023

dhruv referenced this in commit a5df79db12 on Mar 7, 2023

dhruv referenced this in commit 77b510d84c on Mar 7, 2023

sipa referenced this in commit 763079a3f1 on Mar 8, 2023

div72 referenced this in commit 945b094575 on Mar 14, 2023

dderjoel referenced this in commit f66b1c0a5d on May 23, 2023

vmta referenced this in commit e1120c94a1 on Jun 4, 2023

real-or-random cross-referenced this on Jun 11, 2023 from issue Constant-time tests on macOS by sipa

vmta referenced this in commit 8f03457eed on Jul 1, 2023

jonasnick cross-referenced this on Jul 20, 2023 from issue Upstream PRs 1160, 1193, 1169, 1190, 1192, 1194, 1196, 1195, 1170, 1172, 1200, 1199, 1203, 1201, 1206, 1078, 1209, 979, 1212, 1218, 1217, 1221, 1222 by jonasnick

Add support for msan instead of valgrind (for memcheck and ctime test) #1169