[ python-Bugs-1202533 ] a bunch of infinite C recursions

Thu Sep 1 22:39:26 CEST 2005

Bugs item #1202533, was opened at 2005-05-15 19:43
Message generated for change (Comment added) made by tjreedy
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1202533&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Python Interpreter Core
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: Armin Rigo (arigo)
Assigned to: Nobody/Anonymous (nobody)
Summary: a bunch of infinite C recursions

Initial Comment:
There is a general way to cause unchecked infinite recursion at the C level, and I have no clue at the moment how it could be reasonably fixed.  The idea is to define special __xxx__ methods in such a way that no Python code is actually called before they invoke more special methods (e.g. themselves).

>>> class A: pass
>>> A.__mul__=new.instancemethod(operator.mul,None,A)
>>> A()*2
Segmentation fault

----------------------------------------------------------------------

>Comment By: Terry J. Reedy (tjreedy)
Date: 2005-09-01 16:39

Message:
Logged In: YES 
user_id=593130

Bug submission [ 1267884 ] crash recursive __getattr__
appears to be another example of this problem, so I closed it as 
a duplicate.  If that turns out to be wrong, it should be reopened.

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2005-05-29 08:23

Message:
Logged In: YES 
user_id=4771

Adding a Py_EnterRecursiveCall() in PyObject_Call() seems to fix all the examples so far, with the exception of the "__get__=getattr" one, where we get a strange result instead of a RuntimeError (I suspect careless exception eating is taking place).

The main loop in ceval.c doesn't call PyObject_Call() very often: it usually dispatches directly itself for performance, which is exactly what we want here, as recursion from ceval.c is already protected by a Py_EnterRecursiveCall().  So this change has a minor impact on performance.  Pystone for example issues only three PyObject_Call() per loop, to call classes.  This has an almost-unmeasurable impact ( < 0.4%).

Of course I'll think a bit more and search for examples that don't go through PyObject_Call()  :-)

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2005-05-23 09:52

Message:
Logged In: YES 
user_id=4771

When I thought about the same problem for PyPy, I imagined
that it would be easy to use the call graph computed by
the type inferencer ("annotator").  We would find an
algorithm that figures out the minimal number of places
that need a Py_EnterRecursiveCall so that every cycle goes
through at least one of them.  For CPython it might be
possible to go down the same path if someone can find a C
code analyzer smart enough to provide the required
information -- a call graph including indirect calls through
function pointers.  Not sure it's sane, though.

----------------------------------------------------------------------

Comment By: Michael Hudson (mwh)
Date: 2005-05-23 09:16

Message:
Logged In: YES 
user_id=6656

I agree with Armin that this could easily be a never ending story.  Perhaps 
it would suffice to sprinkle Py_EnterRecursiveCall around as we find holes.

It might have to, because I can't really think of a better way of doing this.  
The only other approach I know is that of SBCL (a Common Lisp 
implementation): it mprotects a page at the end of the stack and installs a 
SIGSEGV handler (and uses sigaltstack) that knows how to abort the 
current lisp operation.  Somehow, I don't think we want to go down this 
line.

Anybody have any other ideas?

----------------------------------------------------------------------

Comment By: Martin v. Löwis (loewis)
Date: 2005-05-23 09:06

Message:
Logged In: YES 
user_id=21627

It has been a long-time policy that you should not be able
to crash the Python interpreter even with malicious code. I
think this is a good policy, because it provides people
always with a back-trace, which is much easier to analyse
than a core dump.

----------------------------------------------------------------------

Comment By: Josiah Carlson (josiahcarlson)
Date: 2005-05-23 03:41

Message:
Logged In: YES 
user_id=341410

I personally think that the CPython runtime should make a
best-effort to not crash when running code that makes sense.
 But when CPython is running on input that is nonsensical
(in each of the examples that Armin provides, no return
value could make sense), I think that as long as the
behavior is stated clearly, it is sufficient.

Certainly it would be nice if CPython did not crash in such
cases, but I don't know if the performance penalty and code
maintenance outweigh the cases where users write bad code. 
Perhaps a compile-time option, enabled by default based on
whether or not we want a safer or faster CPython.  Of course
maintenance is still a chore, and it is one additional set
of calls that C extension writers may need to be aware of
(if their code can be recursively called, and they want to
participate in the infinite recursion detection).

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2005-05-20 17:46

Message:
Logged In: YES 
user_id=4771

Yes, but I'm concerned that we would need to add it really really many places, and probably forget some even then.  E.g. I just thought about:

    lst = [apply]
    lst.append(lst)
    apply(*lst)

It seems a bit hopeless, honestly...

----------------------------------------------------------------------

Comment By: Martin v. Löwis (loewis)
Date: 2005-05-20 17:22

Message:
Logged In: YES 
user_id=21627

Wouldn't adding Py_EnterRecursiveCall into many places solve
the problem?

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2005-05-19 11:05

Message:
Logged In: YES 
user_id=4771

This is not about the new module.  The same example can be written as:

  import types
  class A: pass
  A.__mul__ = types.MethodType(operator.mul, None, A)

If this still looks essentially like an indirect way of using the new module, here is another example:

  class A(str): __get__ = getattr
  a = A('a')
  A.a = a
  a.a

Or, as I just found out, new-style classes are again vulnerable to the older example based __call__, which was fixed for old-style classes:

  class A(object): pass
  A.__call__ = A()
  A()()

I'm not denying that these examples look convoluted :-)
My point here is that we can basically build a lot of examples based only on core (if not necessarily widely understood) language features.  It appears to go against the basic hope that CPython cannot be crashed as long as you don't use features explicitely marked as dangerous.

----------------------------------------------------------------------

Comment By: Terry J. Reedy (tjreedy)
Date: 2005-05-18 22:02

Message:
Logged In: YES 
user_id=593130

On Windows, this caused the interactive window to just 
disappear.so I suspect something similar occurred.

New is a known dangerous, use at your own risk, implementation 
specific module whose use, like byte code hacking, is outside 
the language proper.  Both bypass normal object creation syntax 
and its checks and both can create invalid objects.  A hold-your-
hand inplementation would not give such access to internals.

Lib Ref 3.28 says "This module provides a low-level interface to 
the interpreter, so care must be exercised when using this 
module. It is possible to supply non-sensical arguments which 
crash the interpreter when the object is used."  Should more or 
different be said?  

If not, I suspect this should be closed as 'won't fix', as in 'won't 
remove the inherently dangerous new module'.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1202533&group_id=5470