#31869 closed defect (fixed)

Fix segfault when multiplying x * ((3*i + 4)*x - 5)

Reported by: Emmanuel Charpentier Owned by:
Priority: critical Milestone: sage-9.4
Component: symbolics Keywords: pynac, segfault
Cc: Emmanuel Charpentier, Andrew, Peter Mueller, Nils Bruin, Samuel Lelièvre Merged in:
Authors: Dave Morris Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 48f7a07 (Commits, GitHub, GitLab) Commit: 48f7a070bd168a3a039b6592f035c62a387b02bb
Dependencies: Stopgaps:

Status badges

Description (last modified by Samuel Lelièvre)

The following crashes Sage:

sage: x = SR.var('x')
sage: h = (3*I + 4)*x - 5
sage: x * h  # hangs then crashes

Small variations work fine:

sage: h = (3*I + 4)*x - 4
sage: x * h
x*((3*I + 4)*x - 4)
sage: h = (3*I + 5)*x - 5
sage: x * h
x*((3*I + 5)*x - 5)

Priority set to critical as such a simple operation should not crash Sage.


From a report on sage-support which involved substitutions.

The original report can be rephrased as follows. Define f:

sage: y, z = SR.var('y, z')
sage: f = -(15*z/(17*y + 11) + 1)*(5*z/(4*y + 1) - 1)*(15*z/(3*y - 4) + 1)

We want to substitute y = I into f. Tweaking f first works:

sage: f.expand()(y=I)
-(3735/1394*I + 405/1394)*z^3 - (606/697*I - 942/697)*z^2 - (8681/6970*I + 15973/6970)*z + 1
sage: f.partial_fraction(y)(y=I)
-(3735/1394*I + 405/1394)*z^3 - (606/697*I - 942/697)*z^2 - (8681/6970*I + 15973/6970)*z + 1
sage: f.simplify_full()(y=I)
-(3735/1394*I + 405/1394)*z^3 - (606/697*I - 942/697)*z^2 - (8681/6970*I + 15973/6970)*z + 1

but doing it directly crashes:

sage: f(y=I)  # hangs then crashes
------------------------------------------------------------------------
(no backtrace available)
------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred.
This probably occurred because a *compiled* module has a bug
in it and is not properly wrapped with sig_on(), sig_off().
Python will now terminate.
------------------------------------------------------------------------
.../src/bin/sage-python: line 2: ... Segmentation fault: 11  sage -python "$@"

A simpler example that boils down to the minimal reproducer:

sage: a, x = SR.var('a, x')
sage: g = x * ((3*a + 4)*x - 5)
sage: g
((3*a + 4)*x - 5)*x
sage: g(a=I)  # hangs then crashes
------------------------------------------------------------------------
(no backtrace available)
------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred.
This probably occurred because a *compiled* module has a bug
in it and is not properly wrapped with sig_on(), sig_off().
Python will now terminate.
------------------------------------------------------------------------
.../src/bin/sage-python: line 2: ... Segmentation fault: 11  sage -python "$@"

Change History (14)

comment:1 Changed 19 months ago by Emmanuel Charpentier

For one, this isn't a Maxima problem :

sage: maxima_calculus.interact()

  --> Switching to Maxima_lib <--

maxima_lib: subst([y=%i], -(15*z/(17*y + 11) + 1)*(5*z/(4*y + 1) - 1)*(15*z/(3*y - 4) + 1)) ;
((15*z)/(3*%i-4)+1)*((5*z)/(4*%i+1)-1)*((-(15*z)/(17*%i+11))-1)
maxima_lib: 
  --> Exiting back to Sage <--

But :

maxima_calculus.subst([y==i],f).sage()

sends Sage in an infinite loop again...

the problem might lie in the Maxima-->Sage translation layer :

sage: foo = f._maxima_lib_()
sage: bar = maxima_calculus.subst((y==I)._maxima_lib_(), foo)
sage: bar
-((15*_SAGE_VAR_z)/(3*%i-4)+1)*((5*_SAGE_VAR_z)/(4*%i+1)-1)*((15*_SAGE_VAR_z)/(17*%i+11)+1)

works fine ; but asking for bar.sage() sends Sage in an infinite loop...

comment:2 in reply to:  1 ; Changed 19 months ago by Nils Bruin

Replying to charpent:

Putting the example in self-contained form here:

sage: var('z y')
sage: f = -(15*z/(17*y + 11) + 1)*(5*z/(4*y + 1) - 1)*(15*z/(3*y - 4) + 1)
sage: foo = f._maxima_lib_()
sage: bar = maxima_calculus.subst((y==I)._maxima_lib_(), foo)
sage: bar
-((15*_SAGE_VAR_z)/(3*%i-4)+1)*((5*_SAGE_VAR_z)/(4*%i+1)-1)*((15*_SAGE_VAR_z)/(17*%i+11)+1)

but asking the following throws sage in an apparently infinite loop.

sage: bar.sage()

Oddly enough, interrupting the process and looking at the traceback often shows sage is constructing $\sqrt(17)$.

Last edited 19 months ago by Nils Bruin (previous) (diff)

comment:3 in reply to:  2 Changed 19 months ago by Andrew

Replying to nbruin:

traceback often shows sage is constructing $\sqrt(17)$.

I see

  • parse_sequence from misc/parser.pyx, it goes to
  • __mul__ from structure/element.pyx line 1513
             if HAVE_SAME_PARENT(cl):
                 return (<Element>left)._mul_(right)
    
  • _mul_ from symbolic/expression.pyx line 3792
             else:
                 x = left._gobj * _right._gobj
    
  • and it jumps in GiNaC::operator* from pynac-0.7.27/ginac/operators.cpp:78
  • GiNaC::exmul from pynac-0.7.27/ginac/operators.cpp:53
  • GiNaC::ex::ex from pynac-0.7.27/ginac/ex.h:314
  • GiNaC::ex::construct_from_basic from pynac-0.7.27/ginac/ex.cpp:923
  • GiNaC::mul::eval from pynac-0.7.27/ginac/mul.cpp:783
  • and here in jumps back to GiNaC::ex::ex from pynac-0.7.27/ginac/ex.h:314 and repeat calls GiNaC::ex::ex -> GiNaC::ex::construct_from_basic -> GiNaC::mul::eval more than 36500 times :(

comment:4 Changed 19 months ago by Peter Mueller

I don't know if that helps to pin down the problem, but even in

var('z')
a = z/(4*I + 1)
b = 15*z/(3*I - 4) + 1
c = a*b

the execution of the last line hangs. Slight modifications of the assignment of b, like b = z/(3*I - 4) + 1 or b = 15*z/(3*I - 4) don't display that problem.

comment:5 in reply to:  4 Changed 19 months ago by Nils Bruin

Replying to gh-ypfmde:

I don't know if that helps to pin down the problem

I think it does: as far as I can see, the code example you give does not involve maxima at all. This indicates it's a straight-up bug in pynac, or at least in the way sage uses it (pynac is basically part of sage: I don't think there is any other package that uses it)

comment:6 Changed 19 months ago by Peter Mueller

I'm new to sage trac (and more of a naive end user of sage), so I don't want to potentially mess up this ticket. But in view of the many tickets, wouldn't a more expressive title (and fix of the typo) be more useful? From A simple substitution can send Sage in an infiite loop I would expect that some substitution generates an unlimited recursion. Maybe something explicit like y = x*(5*x/(3*I-4)+1)/I causes segfault? (And indeed it does!)

comment:7 Changed 18 months ago by Samuel Lelièvre

Cc: Emmanuel Charpentier Andrew Peter Mueller Nils Bruin Samuel Lelièvre added
Description: modified (diff)
Keywords: pynac segfault added
Summary: A simple substitution can send Sage in an infiite loop.Fix segfault when multiplying x * ((3*i + 4)*x - 5)

Here is a simpler reproducer: x * ((3*i + 4)*x - 5).

Kept original expression in ticket description so the discussion still makes sense.

comment:8 Changed 18 months ago by Dave Morris

Authors: Dave Morris

The infinite loop (in pynac) is caused by an incorrect calculation of the integer_content of a polynomial (or other sum) that has complex coefficients. I will soon provide a patch and further explanation.

comment:9 Changed 18 months ago by Dave Morris

Branch: public/31869

comment:10 Changed 18 months ago by Dave Morris

Commit: 48f7a070bd168a3a039b6592f035c62a387b02bb
Status: newneeds_review

This pynac patch should solve the problem.

Diagnosis: Pynac automatically simplifies expressions to a standard form. In the situation here, it passes repeatedly through a loop, until no changes are made in a pass, so it knows that it is finished. One step of the simplification of a polynomial (or other sum) divides by the integer_content. This is supposed to be the largest rational number that can be divided by to give a result that has no denominator.

For a polynomial with rational coefficients, the integer_content can be calculated by taking the gcd of the numerators, and dividing by the lcm of the denominators. Pynac tries to use this same formula for polynomials with complex coefficients, but a "feature" of the gcd function sends the calculation awry. Namely, pynac assumes that gcd(a,0) is always abs(a). (See #31884 for a complaint about this.)

Here is what goes wrong: To calculate the integer_content of the expression (3*i + 4)*x - 5, pynac calculates gcd(gcd(0, 3*i + 4), -5). Since gcd(0, 3*i + 4) is abs(3*i + 4), which is 5, the result is gcd(5, -5), which is 5. (This is incorrect: the integer_content of this polynomial is 1.) So pynac divides by 5, resulting in (3/5 * i + 4/5)*x - 1. In the next pass through the loop, pynac sees the denominator of 5, and (correctly) concludes that the integer_content of this polynomial is 1/5. It therefore divides by 1/5 to get rid of the denominator. This gets us back to the original polynomial, so pynac is in an infinite loop.

Solution: The integer_content of a polynomial with coefficient a + b*i should be calculated as if a and b were the coefficients of two different terms.


New commits:

48f7a07trac 31869 fix pynac integer_content
Last edited 18 months ago by Dave Morris (previous) (diff)

comment:11 Changed 18 months ago by Dave Morris

PS Thanks to everyone who contributed to this discussion. The simplified example, the traceback, and the other comments made it much easier to locate the bug!

comment:12 Changed 18 months ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

LGTM. Please also create a PR upstream and link it in the ticket description.

comment:13 in reply to:  12 Changed 18 months ago by Emmanuel Charpentier

Replying to tscrim:

LGTM. Please also create a PR upstream and link it in the ticket description.

Same results here : passes ptestlong with the sae results as 9.4.betaO).

Thanks a lot !

comment:14 Changed 18 months ago by Volker Braun

Branch: public/3186948f7a070bd168a3a039b6592f035c62a387b02bb
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.