search

pq-crystals / dilithium

Other
391 stars 144 forks source link

ASAN failures for AVX2 DilithiumXAES code #32

Closed thomwiggers closed 3 years ago

thomwiggers commented 4 years ago

When compiling the AVX2 code with -fsanitize=address,undefined, the ./test/test_dilithiumXaes executables crash with the following message (gcc 10.1.0):

=================================================================
==291152==ERROR: AddressSanitizer: unknown-crash on address 0x7ffefe704448 at pc 0x55c0811dc9fb bp 0x7ffefe704030 sp 0x7ffefe704020
READ of size 32 at 0x7ffefe704448 thread T0
    #0 0x55c0811dc9fa in pqcrystals_dilithium4aes_avx2_rej_uniform_avx (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x4c9fa)
    #1 0x55c0811ce34d in pqcrystals_dilithium4aes_avx2_poly_uniform_preinit (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x3e34d)
    #2 0x55c0811cc0ba in pqcrystals_dilithium4aes_avx2_expand_mat (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x3c0ba)
    #3 0x55c0811c51a8 in pqcrystals_dilithium4aes_avx2_keypair (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x351a8)
    #4 0x55c0811c35ee in main (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x335ee)
    #5 0x7fda72063001 in __libc_start_main (/usr/lib/libc.so.6+0x27001)
    #6 0x55c0811c3f8d in _start (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x33f8d)

Address 0x7ffefe704448 is located in stack of thread T0 at offset 776 in frame
    #0 0x55c0811ce25f in pqcrystals_dilithium4aes_avx2_poly_uniform_preinit (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x3e25f)

  This frame has 1 object(s):
    [32, 800) 'buf' (line 378) <== Memory access at offset 776 partially overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: unknown-crash (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x4c9fa) in pqcrystals_dilithium4aes_avx2_rej_uniform_avx
Shadow bytes around the buggy address:
  0x10005fcd8830: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005fcd8840: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005fcd8850: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005fcd8860: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005fcd8870: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10005fcd8880: 00 00 00 00 00 00 00 00 00[00]00 00 f3 f3 f3 f3
  0x10005fcd8890: f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 00 00 00 00
  0x10005fcd88a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005fcd88b0: 00 00 00 00 f1 f1 f1 f1 00 00 00 f2 f2 f2 00 00
  0x10005fcd88c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005fcd88d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==291152==ABORTING

Interestingly, the PQCgenKAT executables run fine.

gregorseiler commented 4 years ago

This is expected. The code reads 32 bytes from buf but uses only the lower 24 bytes. So it can read up to 8 bytes past the buffer but they are never used and buf lies on the stack so everything should be fine. One could enlarge the buffer by 8 bytes to silence this warning. The same applies to the rej_gamma1m1_avx.

thomwiggers commented 4 years ago

While it may work, it's still undefined behavior to read past the buffer as far as I understand the C standard. Furthermore, it means that any library including this software is precluded from using -fsanitize or Valgrind. I don't think that's acceptable, especially if the cost is a mere 8 bytes (probably more is added by the compiler when aligning).

gregorseiler commented 3 years ago

Fixed now (see PR #33)