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

[pmp2sdp with duplicate poles] ERROR: AddressSanitizer: stack-buffer-overflow in operator_plus_set_Derivative_Term.cxx #194

Closed
vasdommes opened this issue Feb 8, 2024 · 3 comments
Closed

[pmp2sdp with duplicate poles] ERROR: AddressSanitizer: stack-buffer-overflow in operator_plus_set_Derivative_Term.cxx #194

vasdommes opened this issue Feb 8, 2024 · 3 comments
Assignees
@vasdommes
Labels
bug
Milestone
2.7.0

Comments

@vasdommes
Copy link
Collaborator

Description

There might be an error in operator_plus_set_Derivative_Term.cxx, causing segfault mentioned in #192

This code is used in pmp2sdp to compute bilinear basis.

Note that all integration tests still pass (if we set ASAN_OPTIONS=detect_leaks=0 to avoid false positive memory leak errors in MPI).

Repro

  1. Compile sdpb with and compiler+linker flag -fsanitize=address. Also turn on optimization level -O1, -O2 or -O3 (our wscript sets -O3 by default).
  2. Run pmp2sdp for the attached pmp-stack-buffer-overflow.json:
pmp2sdp --input=pmp-stack-buffer-overflow.json --output=sdp --precision=768

This file has a prefactor with many poles (including duplicates), which may cause an error when computing bilinear bases.

Error

==583639==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fffa09e7e00 at pc 0x5621c1809304 bp 0x7fffa09e6d30 sp 0x7fffa09e6d20
READ of size 8 at 0x7fffa09e7e00 thread T0
    #0 0x5621c1809303 in std::pair<std::_Rb_tree_iterator<Derivative_Term>, bool> std::_Rb_tree<Derivative_Term, Derivative_Term, std::_Identity<Derivative_Term>, std::less<Derivative_Term>, std::allocator<Derivative_Term> >::_M_insert_unique<Derivative_Term const&>(Derivative_Term const&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x2092303)
    #1 0x5621c180c8ca in operator+=(std::set<Derivative_Term, std::less<Derivative_Term>, std::allocator<Derivative_Term> >&, std::set<Derivative_Term, std::less<Derivative_Term>, std::allocator<Derivative_Term> > const&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x20958ca)
    #2 0x5621c17e5e59 in dExp(long const&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x206ee59)
    #3 0x5621c17a2ecc in rest(long const&, boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expre
ssion_template_option)1> const&, std::vector<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::exp
ression_template_option)1>, std::allocator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expre
ssion_template_option)1> > > const&, std::pair<__gnu_cxx::__normal_iterator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)
1>, (boost::multiprecision::expression_template_option)1> const*, std::vector<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_typ
e)1>, (boost::multiprecision::expression_template_option)1>, std::allocator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)
1>, (boost::multiprecision::expression_template_option)1> > > >, __gnu_cxx::__normal_iterator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpf
r_allocation_type)1>, (boost::multiprecision::expression_template_option)1> const*, std::vector<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::m
pfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1>, std::allocator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1> > > > > const&, long const&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x202becc)
    #4 0x5621c1734b2b in bilinear_form(Damped_Rational const&, std::vector<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1
>, (boost::multiprecision::expression_template_option)1>, std::allocator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>,
 (boost::multiprecision::expression_template_option)1> > > const&, std::vector<std::pair<__gnu_cxx::__normal_iterator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (bo
ost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1> const*, std::vector<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (
boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1>, std::allocator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (bo
ost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1> > > >, __gnu_cxx::__normal_iterator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_flo
at_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1> const*, std::vector<boost::multiprecision::number<boost::multiprecision::backends::mpfr_f
loat_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1>, std::allocator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_flo
at_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1> > > > >, std::allocator<std::pair<__gnu_cxx::__normal_iterator<boost::multiprecision::num
ber<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1> const*, std::vector<boost::multiprecision::n
umber<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1>, std::allocator<boost::multiprecision::num
ber<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1> > > >, __gnu_cxx::__normal_iterator<boost::m
ultiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1> const*, std::vector<boost:
:multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1>, std::allocator<boost::m
ultiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1> > > > > > > const&, std::v
ector<long, std::allocator<long> > const&, std::vector<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprec
ision::expression_template_option)1>, std::allocator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecis
ion::expression_template_option)1> > > const&, std::vector<std::vector<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (
boost::multiprecision::expression_template_option)1>, std::allocator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (bo
ost::multiprecision::expression_template_option)1> > >, std::allocator<std::vector<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocatio
n_type)1>, (boost::multiprecision::expression_template_option)1>, std::allocator<boost::multiprecision::number<boost::multiprecision::backends::mpfr_float_backend<0u, (boost::multiprecision::mpfr_allocation_type)1>, (boost::multiprecision::expression_template_option)1> > > > > const&, long const&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x1fbdb2b)
    #5 0x5621c157f256 in bilinear_basis(Damped_Rational const&, unsigned long const&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x1e08256)
    #6 0x5621c14e94a6 in Polynomial_Vector_Matrix::Polynomial_Vector_Matrix(El::Matrix<Polynomial_Vector> const&, std::optional<Damped_Rational> const&, std::optional<std::vector<El::BigFloat, std::allocator<El::BigFloat> > > const&, std::optional<std::vector<El::BigFloat, std::allocator<El::BigFloat> > > const&, std::optional<Polynomial_Vector> const&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x1d724a6)  
    #7 0x5621c118d6b3 in Json_Positive_Matrix_With_Prefactor_Parser::get_result() (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x1a166b3)
    #8 0x5621c1121720 in non-virtual thunk to Abstract_Json_Array_Parser_With_Skip<Vector_Parse_Result_With_Skip<Polynomial_Vector_Matrix>, Json_Positive_Matrix_With_Prefactor_Parser>::json_end_object(unsigned int) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x19aa720)
    #9 0x5621c117f354 in non-virtual thunk to Abstract_Json_Object_Parser<PMP_File_Parse_Result>::json_end_object(unsigned int) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x1a08354)
    #10 0x5621c119ceda in void rapidjson::GenericReader<rapidjson::UTF8<char>, rapidjson::UTF8<char>, rapidjson::CrtAllocator>::ParseObject<0u, rapidjson::BasicIStreamWrapper<std::istream>, Json_PMP_Parser>(rapidjson::BasicIStreamWrapper<std::istream>&, Json_PMP_Parser&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x1a25eda)
    #11 0x5621c11a1c1d in void rapidjson::GenericReader<rapidjson::UTF8<char>, rapidjson::UTF8<char>, rapidjson::CrtAllocator>::ParseArray<0u, rapidjson::BasicIStreamWrapper<std::istream>, Json_PMP_Parser>(rapidjson::BasicIStreamWrapper<std::istream>&, Json_PMP_Parser&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x1a2ac1d)
    #12 0x5621c119cae6 in void rapidjson::GenericReader<rapidjson::UTF8<char>, rapidjson::UTF8<char>, rapidjson::CrtAllocator>::ParseObject<0u, rapidjson::BasicIStreamWrapper<std::istream>, Json_PMP_Parser>(rapidjson::BasicIStreamWrapper<std::istream>&, Json_PMP_Parser&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x1a25ae6)
    #13 0x5621c10cbe1a in read_json(std::filesystem::__cxx11::path const&, bool, bool, std::function<bool (unsigned long)> const&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x1954e1a)
    #14 0x5621c107fc18 in PMP_File_Parse_Result::read(std::filesystem::__cxx11::path const&, bool, bool, std::function<bool (unsigned long)> const&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x1908c18)  
    #15 0x5621c0fdb0de in read_polynomial_matrix_program(Environment const&, std::vector<std::filesystem::__cxx11::path, std::allocator<std::filesystem::__cxx11::path> > const&, Timers&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x18640de)
    #16 0x5621c0feac18 in read_polynomial_matrix_program(Environment const&, std::filesystem::__cxx11::path const&, Timers&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x1873c18)
    #17 0x5621c0ea045f in main (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x172945f)
    #18 0x7fba12c1ad8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #19 0x7fba12c1ae3f in __libc_start_main_impl ../csu/libc-start.c:392
    #20 0x5621c0eccc24 in _start (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x1755c24)

Address 0x7fffa09e7e00 is located in stack of thread T0 at offset 624 in frame
    #0 0x5621c17e51ff in dExp(long const&) (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x206e1ff)

  This frame has 15 object(s):
    [48, 49) '__tmp'
    [64, 68) '<unknown>'
    [80, 88) '__for_begin' (line 17)
    [112, 120) '__for_end' (line 17)
    [144, 152) '<unknown>'
    [176, 184) '<unknown>'
    [208, 216) '__tmp'
    [240, 248) '__tmp'
    [272, 280) '__tmp'
    [304, 312) '__tmp'
    [336, 352) '<unknown>'
    [368, 384) '<unknown>'
    [400, 448) '<unknown>'
    [480, 528) 'new_terms' (line 16)
    [560, 608) '<unknown>' <== Memory access at offset 624 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 (/home/vasdommes/bootstrap/sdpb/build/pmp2sdp+0x2092303) in std::pair<std::_Rb_tree_iterator<Derivative_Term>, bool> std::_Rb_tree<Derivative_Term, Derivative_Term, std::_Identity<Derivative_Term>, std::less<Derivative_Term>, std::allocator<Derivative_Term> >::_M_insert_unique<Derivative_Term const&>(Derivative_Term const&)
Shadow bytes around the buggy address:
  0x100074134f70: 00 00 f1 f1 f1 f1 f1 f1 f8 f2 f8 f2 00 f2 f2 f2
  0x100074134f80: 00 f2 f2 f2 f8 f2 f2 f2 f8 f2 f2 f2 f8 f2 f2 f2
  0x100074134f90: f8 f2 f2 f2 f8 f2 f2 f2 f8 f2 f2 f2 f8 f8 f2 f2
  0x100074134fa0: f8 f8 f2 f2 f8 f8 f8 f8 f8 f8 f2 f2 f2 f2 00 00
  0x100074134fb0: 00 00 00 00 f2 f2 f2 f2 00 00 00 00 00 00 f3 f3
=>0x100074134fc0:[f3]f3 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100074134fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100074134fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100074134ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100074135000: 00 00 00 00 f1 f1 f1 f1 f1 f1 01 f2 01 f2 01 f2
  0x100074135010: 01 f2 01 f2 01 f2 01 f2 01 f2 01 f2 01 f2 01 f2
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
==583639==ABORTING
@vasdommes vasdommes added the bug label Feb 8, 2024
@vasdommes vasdommes added this to the 2.7.0 milestone Feb 8, 2024
@vasdommes vasdommes self-assigned this Feb 8, 2024
@vasdommes vasdommes mentioned this issue Feb 8, 2024
Closed
@vasdommes
Copy link
Collaborator Author

vasdommes commented Feb 8, 2024 •
edited
Loading

Minimal example contains only five duplicate poles.
pmp-stack-buffer-overflow-minimal.json

"DampedRational": {
"base": "0.17",
"constant": "1",
"poles": [
	"-1",
	"-1",
	"-1",
	"-1",
	"-1"
]
},

@vasdommes vasdommes changed the title pmp2sdp ERROR: AddressSanitizer: stack-buffer-overflow in operator_plus_set_Derivative_Term.cxx [pmp2sdp with duplicate poles] ERROR: AddressSanitizer: stack-buffer-overflow in operator_plus_set_Derivative_Term.cxx Feb 8, 2024
@vasdommes
Copy link
Collaborator Author

After adding some debug output:

bilinear_form() pole->str()='-1' l='5' 
start dExp() k='0'
start dExp() k='1'
start operator+= a.size()='0' b.size()='1'
start dExp() k='2'
start operator+= a.size()='0' b.size()='1'
start operator+= a.size()='0' b.size()='2'
start dExp() k='3'
start operator+= a.size()='0' b.size()='1'
start operator+= a.size()='0' b.size()='2'
start operator+= a.size()='0' b.size()='2'
start operator+= a.size()='2' b.size()='2'
start dExp() k='4'
start operator+= a.size()='0' b.size()='1'
start operator+= a.size()='0' b.size()='2'
start operator+= a.size()='0' b.size()='2'
start operator+= a.size()='2' b.size()='2'
start operator+= a.size()='0' b.size()='3'
start operator+= a.size()='3' b.size()='2'
=================================================================
==605719==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fff361b33f0 at pc 0x55d80cf4b3eb bp 0x7fff361b2a50 sp 0x7fff361b2a40

@vasdommes
Copy link
Collaborator Author

The solution is simple:
We should write

  while(iter_a != a.end() && iter_b != b.end())

instead of

sdpb/src/pmp/convert/bilinear_basis/bilinear_form/operator_plus_set_Derivative_Term.cxx

Line 10 in 82ec4cb

while(iter_a != a.end())

@vasdommes vasdommes mentioned this issue Feb 8, 2024
Merged
vasdommes added a commit that referenced this issue Feb 8, 2024
@vasdommes
Merge pull request #195 from davidsd/fix-address-sanitizer-error
a950a3a 
Fix #194 [pmp2sdp with duplicate poles] ERROR: AddressSanitizer: stack-buffer-overflow in operator_plus_set_Derivative_Term.cxx
bharathr98 pushed a commit to bharathr98/sdpb that referenced this issue Mar 1, 2024
@vasdommes @bharathr98
Fix davidsd#194 [pmp2sdp with duplicate poles] ERROR: AddressSanitize…
e1f9732 
…r: stack-buffer-overflow in operator_plus_set_Derivative_Term.cxx
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@vasdommes vasdommes

Labels
bug
Projects
None yet
Milestone
2.7.0
Development

No branches or pull requests
1 participant
@vasdommes