Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Heap buffer overflow for Suyama tests #13

Closed
tdulcet opened this issue Mar 23, 2024 · 0 comments · Fixed by #14
Closed

Heap buffer overflow for Suyama tests #13

tdulcet opened this issue Mar 23, 2024 · 0 comments · Fixed by #14
Labels
bug Something isn't working

Comments

@tdulcet
Copy link
Member

tdulcet commented Mar 23, 2024

This was first reported by Gary Gostin on the forum.

A heap buffer overflow occurs for some Suyama tests. All of the errors occur in src/mi64.c and seem to be related to realloc. Ernst had a similar issue as well:

Mlucas/src/mi64.c

Lines 5637 to 5646 in 37bf170

/*** May 2022: In preparing for the cofactor-is-prime-power GCD on F25/[known factors], build on Linux
with GCC 9.2.1, hit SIGABRT here with 'realloc(): invalid next size'. Step-thru debug showed
the #limbs-allocated counter lens increasing from 0 to 4 to 9, next jump from 9 to 1048574 triggered
the exception ... looks like realloc does not like too-large jumps in allocated size, switched to malloc.
***
Jun 2022: Again hit error, this time after half-dozen small increments in lens:
"malloc: *** error for object 0x1006002d8: incorrect checksum for freed object - object was probably modified after being freed.
*** set a breakpoint in malloc_error_break to debug"
Setting said breakpoint is useless, can't see function context when hit. Instead try setting min-size = 1024 in lens = ... .
***/

F17:

=================================================================
==38430==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6030000099c0 at pc 0x7fcf07298f3d bp 0x7ffc608adf70 sp 0x7ffc608ad718
WRITE of size 48 at 0x6030000099c0 thread T0
    #0 0x7fcf07298f3c in __interceptor_memset ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:762
    #1 0x55fa973d8254 in memset /usr/include/x86_64-linux-gnu/bits/string_fortified.h:71
    #2 0x55fa973d8254 in mi64_mul_vector_lo_half ../src/mi64.c:3163
    #3 0x55fa973db2d0 in mi64_scalar_modpow_lr ../src/mi64.c:4009
    #4 0x55fa973dbbee in mi64_pprimeF ../src/mi64.c:3933
    #5 0x55fa973ecd2c in extract_known_factors ../src/Mlucas.c:6348
    #6 0x55fa973f625b in ernstMain ../src/Mlucas.c:704
    #7 0x55fa97395f2a in main ../src/Mlucas.c:4383
    #8 0x7fcf062b1082 in __libc_start_main ../csu/libc-start.c:308
    #9 0x55fa97397d2d in _start (/raid/gary/Mlucas_v21_github/Mlucas-main_2024_03_12/obj/Mlucas+0x6d2d)

0x6030000099c0 is located 0 bytes to the right of 32-byte region [0x6030000099a0,0x6030000099c0)
allocated by thread T0 here:
    #0 0x7fcf0733ec3e in __interceptor_realloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:163
    #1 0x55fa973d83db in mi64_mul_vector_lo_half ../src/mi64.c:3160

SUMMARY: AddressSanitizer: heap-buffer-overflow ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:762 in __interceptor_memset
Shadow bytes around the buggy address:
  0x0c067fff92e0: 00 00 00 fa fa fa 00 00 00 fa fa fa 00 00 00 fa
  0x0c067fff92f0: fa fa 00 00 00 fa fa fa 00 00 00 fa fa fa 00 00
  0x0c067fff9300: 00 fa fa fa 00 00 00 fa fa fa 00 00 00 fa fa fa
  0x0c067fff9310: 00 00 00 fa fa fa 00 00 00 fa fa fa 00 00 00 fa
  0x0c067fff9320: fa fa 00 00 00 fa fa fa 00 00 00 fa fa fa 00 00
=>0x0c067fff9330: 00 fa fa fa 00 00 00 00[fa]fa 00 00 00 00 fa fa
  0x0c067fff9340: 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00 00 00
  0x0c067fff9350: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9360: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9370: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9380: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
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
==38430==ABORTING

F18:

INFO: Maximum recommended exponent for FFT length (14 Kdbl) = 301338; p[ = 262144]/pmax_rec = 0.8699334302.
Initial DWT-multipliers chain length = [long] in carry step.
 INFO: restart file f18 found...reading...
Suyama-PRP on cofactors of F18: using FFT length 14K = 14336 8-byte floats.
The test will be done in form of a 3-PRP test.
 this gives an average   18.285714285714285 bits per digit
Doing one mod-F18 squaring of iteration-262143 residue [Res64 = 506A5A0ABC27E6F0] to get Fermat-PRP residue
Using 1 threads in carry step
MaxErr = 0.005859375
Fermat-PRP residue (A)     = 0xBCBFB1C446912EAD, 5160281264,16198816711
Processed 99 bits in binary modpow; MaxErr = 0.009765625
3^(F-1) residue (B)        = 0x689AC15EAF3057EE,15794027617,29076663800
(A - B) Res64 = 0x5424F0659760D6C0, C Res64 = 0xD63F299AFAB00001
=================================================================
==38458==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6310000887f8 at pc 0x7f51ccf8ef3d bp 0x7fff835e76d0 sp 0x7fff835e6e78
WRITE of size 8 at 0x6310000887f8 thread T0
    #0 0x7f51ccf8ef3c in __interceptor_memset ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:762
    #1 0x560c378e540a in mi64_clear ../src/mi64.c:300
    #2 0x560c378e540a in mi64_div_binary ../src/mi64.c:5671
    #3 0x560c378f8d1d in Suyama_CF_PRP ../src/Mlucas.c:3394
    #4 0x560c37900399 in ernstMain ../src/Mlucas.c:2468
    #5 0x560c378a0f2a in main ../src/Mlucas.c:4383
    #6 0x7f51cbfa7082 in __libc_start_main ../csu/libc-start.c:308
    #7 0x560c378a2d2d in _start (/raid/gary/Mlucas_v21_github/Mlucas-main_2024_03_12/obj/Mlucas+0x6d2d)

0x6310000887f8 is located 0 bytes to the right of 65528-byte region [0x631000078800,0x6310000887f8)
allocated by thread T0 here:
    #0 0x7f51cd034c3e in __interceptor_realloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:163
    #1 0x560c378e5b28 in mi64_div_binary ../src/mi64.c:5648
    #2 0x560c378f8d1d in Suyama_CF_PRP ../src/Mlucas.c:3394
    #3 0x560c37900399 in ernstMain ../src/Mlucas.c:2468
    #4 0x560c378a0f2a in main ../src/Mlucas.c:4383

SUMMARY: AddressSanitizer: heap-buffer-overflow ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:762 in __interceptor_memset
Shadow bytes around the buggy address:
  0x0c62800090a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c62800090b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c62800090c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c62800090d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c62800090e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c62800090f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00[fa]
  0x0c6280009100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c6280009110: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c6280009120: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c6280009130: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c6280009140: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
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
==38458==ABORTING

F19:

INFO: Maximum recommended exponent for FFT length (28 Kdbl) = 593840; p[ = 524288]/pmax_rec = 0.8828775428.
Initial DWT-multipliers chain length = [long] in carry step.
 INFO: restart file f19 found...reading...
Suyama-PRP on cofactors of F19: using FFT length 28K = 28672 8-byte floats.
The test will be done in form of a 3-PRP test.
 this gives an average   18.285714285714285 bits per digit
Doing one mod-F19 squaring of iteration-524287 residue [Res64 = 8C9339452E75F19C] to get Fermat-PRP residue
Using 1 threads in carry step
MaxErr = 0.008789062
Fermat-PRP residue (A)     = 0x449FBCA640B4FA27,  405458041,30933529616
Processed 190 bits in binary modpow; MaxErr = 0.011718750
3^(F-1) residue (B)        = 0x4E81A5FE01B9AC83,18465526654,52398778242
=================================================================
==38177==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6030000099c0 at pc 0x7f87ef25bf3d bp 0x7ffd277dee30 sp 0x7ffd277de5d8
WRITE of size 48 at 0x6030000099c0 thread T0
    #0 0x7f87ef25bf3c in __interceptor_memset ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:762
    #1 0x558a42644254 in memset /usr/include/x86_64-linux-gnu/bits/string_fortified.h:71
    #2 0x558a42644254 in mi64_mul_vector_lo_half ../src/mi64.c:3163
    #3 0x558a4264d2ad in mi64_div_mont ../src/mi64.c:5302
    #4 0x558a4264fae5 in mi64_div ../src/mi64.c:5012
    #5 0x558a42659c6c in Suyama_CF_PRP ../src/Mlucas.c:3388
    #6 0x558a42661399 in ernstMain ../src/Mlucas.c:2468
    #7 0x558a42601f2a in main ../src/Mlucas.c:4383
    #8 0x7f87ee274082 in __libc_start_main ../csu/libc-start.c:308
    #9 0x558a42603d2d in _start (/raid/gary/Mlucas_v21_github/Mlucas-main_2024_03_12/obj/Mlucas+0x6d2d)

0x6030000099c0 is located 0 bytes to the right of 32-byte region [0x6030000099a0,0x6030000099c0)
allocated by thread T0 here:
    #0 0x7f87ef301c3e in __interceptor_realloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:163
    #1 0x558a426443db in mi64_mul_vector_lo_half ../src/mi64.c:3160

SUMMARY: AddressSanitizer: heap-buffer-overflow ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:762 in __interceptor_memset
Shadow bytes around the buggy address:
  0x0c067fff92e0: 00 00 00 fa fa fa 00 00 00 fa fa fa 00 00 00 fa
  0x0c067fff92f0: fa fa 00 00 00 fa fa fa 00 00 00 fa fa fa 00 00
  0x0c067fff9300: 00 fa fa fa 00 00 00 fa fa fa 00 00 00 fa fa fa
  0x0c067fff9310: 00 00 00 fa fa fa 00 00 00 fa fa fa 00 00 00 fa
  0x0c067fff9320: fa fa 00 00 00 fa fa fa 00 00 00 fa fa fa 00 00
=>0x0c067fff9330: 00 fa fa fa 00 00 00 00[fa]fa 00 00 00 00 fa fa
  0x0c067fff9340: 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00 00 fa
  0x0c067fff9350: fa fa 00 00 00 00 fa fa 00 00 00 fa fa fa 00 00
  0x0c067fff9360: 00 fa fa fa 00 00 00 fa fa fa fa fa fa fa fa fa
  0x0c067fff9370: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9380: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
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
==38177==ABORTING
@tdulcet tdulcet added bug Something isn't working help wanted Extra attention is needed labels Mar 23, 2024
@xanthe-cat xanthe-cat mentioned this issue Mar 24, 2024
Closed
@tdulcet tdulcet removed the help wanted Extra attention is needed label Mar 24, 2024
tdulcet added a commit that referenced this issue Mar 24, 2024
@tdulcet
Fixed buffer overflow errors in mi64.c. Fixes #13
075c48c 
Patch submitted by Gary Gostin.
@tdulcet tdulcet mentioned this issue Mar 24, 2024
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fixed buffer overflow errors in mi64.c primesearch/Mlucas
1 participant
@tdulcet