piggypiggy / fp256

An efficient library for 256 bit integer arithmetic
Apache License 2.0
43 stars 12 forks source link

address sanitizer #1

Open tankf33der opened 3 years ago

tankf33der commented 3 years ago
$ CFLAGS="-fsanitize=address,undefined" cmake ..
$ make -j 8
$ make test
Running tests...
Test project /home/mpech/fp256/build
      Start  1: MUL_TEST
 1/10 Test  #1: MUL_TEST .........................   Passed    3.50 sec
      Start  2: DIV_TEST
 2/10 Test  #2: DIV_TEST .........................   Passed    3.41 sec
      Start  3: GCD_TEST
 3/10 Test  #3: GCD_TEST .........................   Passed    5.74 sec
      Start  4: MODINV_TEST
 4/10 Test  #4: MODINV_TEST ......................***Failed    0.11 sec
      Start  5: MODMUL_TEST
 5/10 Test  #5: MODMUL_TEST ......................   Passed    0.02 sec
      Start  6: MODSQR_TEST
 6/10 Test  #6: MODSQR_TEST ......................   Passed    0.02 sec
      Start  7: MODADD_TEST
 7/10 Test  #7: MODADD_TEST ......................   Passed    0.02 sec
      Start  8: MODSUB_TEST
 8/10 Test  #8: MODSUB_TEST ......................   Passed    0.02 sec
      Start  9: MONTMUL_TEST
 9/10 Test  #9: MONTMUL_TEST .....................   Passed   10.92 sec
      Start 10: MONTSQR_TEST
10/10 Test #10: MONTSQR_TEST .....................   Passed    7.55 sec

90% tests passed, 1 tests failed out of 10

Total Test time (real) =  31.32 sec

The following tests FAILED:
      4 - MODINV_TEST (Failed)
Errors while running CTest
make: *** [Makefile:149: test] Error 8
$ ./test/modinv_test 
------------ fp256_mod_inv ------------ 
=================================================================
==72280==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffc137c84e0 at pc 0x7ffb67d931ca bp 0x7ffc137c81b0 sp 0x7ffc137c7958
WRITE of size 40 at 0x7ffc137c84e0 thread T0
    #0 0x7ffb67d931c9 in __interceptor_memcpy /build/gcc/src/gcc/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:806
    #1 0x7ffb67d2b81f in ll_div (/home/mpech/fp256/bin/Release/shared/libfp256.so.0+0x2081f)
    #2 0x7ffb67d2d61b in ll_lehmer_exgcd (/home/mpech/fp256/bin/Release/shared/libfp256.so.0+0x2261b)
    #3 0x7ffb67d33944 in fp256_mod_inv (/home/mpech/fp256/bin/Release/shared/libfp256.so.0+0x28944)
    #4 0x561e6d689ebd in fp256_modinv_test_vector (/home/mpech/fp256/build/test/modinv_test+0xbebd)
    #5 0x561e6d68cb76 in run_test (/home/mpech/fp256/build/test/modinv_test+0xeb76)
    #6 0x561e6d689932 in main (/home/mpech/fp256/build/test/modinv_test+0xb932)
    #7 0x7ffb671da151 in __libc_start_main (/usr/lib/libc.so.6+0x28151)
    #8 0x561e6d689aad in _start (/home/mpech/fp256/build/test/modinv_test+0xbaad)

Address 0x7ffc137c84e0 is located in stack of thread T0 at offset 96 in frame
    #0 0x7ffb67d337bf in fp256_mod_inv (/home/mpech/fp256/bin/Release/shared/libfp256.so.0+0x287bf)

  This frame has 2 object(s):
    [32, 40) 'sl' (line 148)
    [64, 96) 'sd' (line 149) <== Memory access at offset 96 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: stack-buffer-overflow /build/gcc/src/gcc/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:806 in __interceptor_memcpy
Shadow bytes around the buggy address:
  0x1000026f1040: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000026f1050: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000026f1060: 00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1 00 f2
  0x1000026f1070: f2 f2 00 00 00 00 f3 f3 f3 f3 00 00 00 00 00 00
  0x1000026f1080: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x1000026f1090: f1 f1 f1 f1 00 f2 f2 f2 00 00 00 00[f3]f3 f3 f3
  0x1000026f10a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000026f10b0: 00 00 00 00 00 00 00 00 f1 f1 f1 f1 00 00 00 00
  0x1000026f10c0: 00 f2 f2 f2 f2 f2 00 00 00 00 00 f2 f2 f2 f2 f2
  0x1000026f10d0: 00 00 00 00 00 f2 f2 f2 f2 f2 00 00 00 00 00 f3
  0x1000026f10e0: f3 f3 f3 f3 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
==72280==ABORTING
piggypiggy commented 3 years ago

commit messgae is broken:(. In ll_lehmer_exgcd, it computes sd = (bd v0 + gcd) / ad, when bd v0 + gcd has 4 more limbs than ad, ll_div requires sd to have 5 limbs to store quotient. So give sd 5 limbs space can fix it.