Opened 12 years ago

Closed 12 years ago

#9345 closed defect (fixed)

Unhandled SIGFPE in rational_reconstruction if the modulus is zero

Reported by: Luis Felipe Tabera Alonso Owned by: Alex Ghitza
Priority: major Milestone: sage-4.6.1
Component: algebra Keywords:
Cc: Jeroen Demeyer Merged in: sage-4.6.1.alpha2
Authors: Luis Felipe Tabera Alonso Reviewers: Minh Van Nguyen, Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Jeroen Demeyer)

Sage crashes if try to perform a rational_reconstruction with zero modulus and compiled fast algorithm

sage: rational_reconstruction(1,0)


------------------------------------------------------------
Unhandled SIGFPE: An unhandled floating point exception occured in Sage.
This probably occured because a *compiled* component
of Sage has a bug in it (typically accessing invalid memory)
or is not properly wrapped with _sig_on, _sig_off.
You might want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate (sorry).
------------------------------------------------------------

Apply: trac_9345.3.patch

Attachments (7)

trac_9345.patch (760 bytes) - added by Luis Felipe Tabera Alonso 12 years ago.
trac_9345.2.patch (924 bytes) - added by Minh Van Nguyen 12 years ago.
trac_9345-reviewer.patch (1.4 KB) - added by Minh Van Nguyen 12 years ago.
trac_9345.3.patch (6.0 KB) - added by Luis Felipe Tabera Alonso 12 years ago.
previous patches merged
trac-9345-sigs.patch (2.2 KB) - added by Luis Felipe Tabera Alonso 12 years ago.
trac-9345-sigs-jd.patch (1.4 KB) - added by Jeroen Demeyer 12 years ago.
Better alternative to trac-9345-sigs.patch
trac-9345-sigs-jd-2.patch (1.8 KB) - added by Luis Felipe Tabera Alonso 12 years ago.

Download all attachments as: .zip

Change History (20)

Changed 12 years ago by Luis Felipe Tabera Alonso

Attachment: trac_9345.patch added

comment:1 Changed 12 years ago by Luis Felipe Tabera Alonso

Status: newneeds_review

Changed 12 years ago by Minh Van Nguyen

Attachment: trac_9345.2.patch added

Changed 12 years ago by Minh Van Nguyen

Attachment: trac_9345-reviewer.patch added

comment:2 Changed 12 years ago by Minh Van Nguyen

Description: modified (diff)
Reviewers: Minh Van Nguyen
Summary: Unhandled SIGFPE is rational_reconstruction if the modulus is zeroUnhandled SIGFPE in rational_reconstruction if the modulus is zero

I'm mostly OK with lftabera's patch. Here are some changes that needs to be made:

  • Reference the ticket number in the relevant regression test.
  • Use the Python 3.x compliant way of raising exceptions.
  • Add a more general regression test.
  • Credit lftabera in his patch. (We don't accept anonymous patches.) Put a sensible commit message in lftabera's patch. So one now uses trac_9345.2.patch instead of trac_9345.patch.

See the ticket description for instructions on how to apply the relevant patches. Only my proposed changes need review by anyone but me. If they are OK, then the whole ticket receives a positive review.

comment:3 Changed 12 years ago by Luis Felipe Tabera Alonso

Status: needs_reviewneeds_work

Not quite solved, the problem is not in this method, but in the compiled rational reconstruction

sage: ZZ(1).rational_reconstruction(0)


------------------------------------------------------------
Unhandled SIGFPE: An unhandled floating point exception occured in Sage.
This probably occured because a *compiled* component
of Sage has a bug in it (typically accessing invalid memory)
or is not properly wrapped with _sig_on, _sig_off.
You might want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate (sorry).
------------------------------------------------------------

I will update the patch to the correct function

comment:4 Changed 12 years ago by Luis Felipe Tabera Alonso

The following files have a call to rational_reconstruction, computed using

sage: search_src('rational_reconstruction',interact=False)

and code to make Sage crash

  • rings/integer.pyx
 sage: ZZ(1).rational_reconstruction(0)

Calls rational.pyrex_rational_reconstruction

  • rings/rational.pyx
 sage: sage.rings.rational.pyrex_rational_reconstruction(1,0)
  • rings/arith.py
 sage: rational_reconstruction(1,0)

Calls ZZ.rational_reconstruction

  • rings/finite_rings/element_ext_pari.py

Unable to crash, it is an element of a finite field. Anyway, it calls arith.rational_reconstruction

  • rings/finite_rings/integer_mod.pyx

Unable to crash, an element mod 0 is an Integer. Anyway, it calls ZZ.rational_reconstruction

  • rings/padics/padic_generic_element.pyx

Unable to crash, modulus of a p-adic element is not zero. anyway, it calls arith.rational_reconstruction

  • matrix/matrix_rational_dense.pyx
  1. _lift_crt_rr
  2. _lift_crt_rr_with_lcm

Obsolete functions for crt? They seem not to be used anywhere. By the code, it seems tha mm should be a list of moduli matrices (call of _lift_crt). On the other hand, the product should be an integer
m= mm.prod(); mpq_rational_reconstruction(Q_row[j], Z_row[j], m.value) So I cannot test whether there is a problem for these functions. I am not able to get crashes or any sensible output from these functions.

  • matrix/matrix_integer_sparse.pyx
 sage: M = random_matrix(ZZ, 3, 3, 'sparse')
 sage: M.rational_reconstruction()

Calls misc.matrix_integer_sparse_rational_reconstruction

  • matrix/misc.pyx
 sage: M = random_matrix(ZZ, 3, 3, 'sparse')
 sage: sage.matrix.misc.matrix_integer_sparse_rational_reconstruction(M,0)
 sage: M = random_matrix(ZZ, 3, 3)
 sage: sage.matrix.misc.matrix_integer_dense_rational_reconstruction(M,0)
  • matrix/matrix_cyclo_dense.pyx

Unable to crash. Used in a modular algorithm, calls misc.matrix_integer_dense_rational_reconstruction

  • matrix/matrix_integer_dense.pyx
 sage: M = random_matrix(ZZ,3)
 sage: M.rational_reconstruction(0)

Calls misc.matrix_integer_dense_rational_reconstruction

Changed 12 years ago by Luis Felipe Tabera Alonso

Attachment: trac_9345.3.patch added

previous patches merged

comment:5 Changed 12 years ago by Luis Felipe Tabera Alonso

Description: modified (diff)
Status: needs_workneeds_review

New patch with all the modifications. Respecting the code, the patch only changes rings/rational.pyx and matrix/misc.pyx where the offending code is.

However, I have added doctests to check all the crashes in the previous post. This might be overkilling though.

comment:6 Changed 12 years ago by Jeroen Demeyer

Cc: Jeroen Demeyer added
Status: needs_reviewneeds_work

I think one should find out which code really causes the crash, because _sig_on/_sig_off should be used there. See http://sagemath.org/doc/developer/coding_in_other.html#the-pari-c-library-interface (the docs are about PARI but apply more generally to all C and Cython code).

Changed 12 years ago by Luis Felipe Tabera Alonso

Attachment: trac-9345-sigs.patch added

comment:7 Changed 12 years ago by Luis Felipe Tabera Alonso

Status: needs_workneeds_review

Well, there was a similar problem in #9357 and I got this answer to the question of _sig_onm, _sig_off

http://groups.google.com/group/sage-devel/browse_thread/thread/e8317365bfe9e6e8/2a4148024500dfd2

Note that if the exception is controlled by _sig, it will raise a RuntimeError? instead of ZeroDivisionError?. Moreover, with the patch I provided, all ocurrences of being zero are catched and never reaches the C functions.

Anyway, I have written a second patch that add the _sig_on, _sig_off to the problematic functions, so if they have to be added, apply the following patches (in order):

trac_9345.3.patch trac-9345-sigs.patch

comment:8 in reply to:  7 Changed 12 years ago by Jeroen Demeyer

Milestone: sage-4.5.3sage-4.6

Replying to lftabera:

Note that if the exception is controlled by _sig, it will raise a RuntimeError? instead of ZeroDivisionError?. Moreover, with the patch I provided, all ocurrences of being zero are catched and never reaches the C functions.

I agree that your patch fixes the problem of division by zero, that wasn't my point. My point was that, in addition you should add _sig_on and _sig_off to make the code more robust (for example, against crtl+C).

Anyway, I have written a second patch that add the _sig_on, _sig_off to the problematic functions, so if they have to be added, apply the following patches (in order):

trac_9345.3.patch trac-9345-sigs.patch

Well, the _sig_on and _sig_off are in the wrong places (_sig_on should be before any mpz or mpq function is called and _sig_off after). I can have a look at this if you want.

Changed 12 years ago by Jeroen Demeyer

Attachment: trac-9345-sigs-jd.patch added

Better alternative to trac-9345-sigs.patch

comment:9 in reply to:  5 Changed 12 years ago by Jeroen Demeyer

Reviewers: Minh Van NguyenMinh Van Nguyen, Jeroen Demeyer

Replying to lftabera:

However, I have added doctests to check all the crashes in the previous post. This might be overkilling though.

I agree that it is overkill, but I'm fine with it. I'm giving positive_review for trac_9345.3.patch. Somebody else should review my trac-9345-sigs-jd.patch.

Changed 12 years ago by Luis Felipe Tabera Alonso

Attachment: trac-9345-sigs-jd-2.patch added

comment:10 Changed 12 years ago by Luis Felipe Tabera Alonso

Description: modified (diff)

I have corrected jdemeyer patch to also include the sparse matrix case. The patch to review is trac-9345-sigs-jd-2.patch

comment:11 in reply to:  10 Changed 12 years ago by Jeroen Demeyer

Replying to lftabera:

I have corrected jdemeyer patch to also include the sparse matrix case. The patch to review is trac-9345-sigs-jd-2.patch

Looks good to me, but I suppose somebody else should formally review it.

comment:12 Changed 12 years ago by Jeroen Demeyer

Description: modified (diff)
Status: needs_reviewpositive_review

I will move the signals part to #10061, therefore positive review for trac_9345.3.patch

comment:13 Changed 12 years ago by Jeroen Demeyer

Merged in: sage-4.6.1.alpha2
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.