Running Python 3.7.2, it is possible to segfault the process when sorting some arrays.

Executed commands are

    $ python3
    Python 3.7.2 (default, Feb 12 2019, 08:15:36) 
    [Clang 10.0.0 (clang-1000.11.45.5)] on darwin
    Type "help", "copyright", "credits" or "license" for more information.
    >>> [(1.0, 1.0), (False, "A"), 6].sort()
    Segmentation fault: 11

I did not have the opportunity to test on systems other than macOS, but anecdotally this is reproducible on both Windows and Linux.

Can confirm on 3.7.1 on Linux. The same is happening for sorted. I wonder if the optimisation done in 1e34da49ef2 is responsible

Can confirm for 3.7.2 on my macOS 10.14 system. Although this is the case in 3.7 on my current build of the master branch I get the following AssertionError instead:

Assertion failed: (v->ob_type == w->ob_type), function unsafe_tuple_compare, file Objects/listobject.c, line 2164

It seems like the AssertionError gets thrown in unsafe_tuple_compare().
Link: https://github.com/python/cpython/blob/dc078947a5033a048d804e244e847b5844734439/Objects/listobject.c#L2164

Adding ned and Łukasz since this seems to happen on release builds.

Confirmed on Linux:

$ python3.6
Python 3.6.8 (default, Mar  5 2019, 22:01:36) 
[GCC 8.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> [(1.0, 1.0), (False, "A"), 6].sort()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'int' and 'tuple'
>>> 
$ python3.7
Python 3.7.2 (default, Mar  5 2019, 22:05:50) 
[GCC 8.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> [(1.0, 1.0), (False, "A"), 6].sort()
Segmentation fault

On mac I confirm that 1e34da49ef2 segfaults and 6c6ddf97c4 gives the expected result:

➜  cpython git:(6c6ddf97c4) ✗ ./python.exe tests.py
Traceback (most recent call last):
  File "tests.py", line 1, in <module>
    [(1.0, 1.0), (False, "A"), 6].sort()
TypeError: '<' not supported between instances of 'int' and 'tuple'

The code segfaults at https://github.com/python/cpython/blob/master/Objects/listobject.c#L2164 coming from https://github.com/python/cpython/blob/master/Objects/listobject.c#L1324.

@remi.lapeyre please make sure you are not unsubscribing others by mistake while adding comment.

Hi @xtreak, sorry for that.

I think the issue may come from https://github.com/python/cpython/blob/master/Objects/listobject.c#L2273-L2357 where ms.key_compare is set, the conditions on the first ifs looks weird to me and I suspect ms.key_compare is set to unsafe_tuple_compare when not all elements are tuples.


The following patch fixed the issue and made the whole test suite pass:

diff --git Objects/listobject.c Objects/listobject.c
index b6524e8bd7..5237542092 100644
--- Objects/listobject.c
+++ Objects/listobject.c
@@ -1,4 +1,4 @@
-/* List object implementation */
+    /* List object implementation */
 
 #include "Python.h"
 #include "pycore_object.h"
@@ -2338,21 +2338,21 @@ list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse)
             else {
                 ms.key_compare = safe_object_compare;
             }
+            if (keys_are_in_tuples) {
+                /* Make sure we're not dealing with tuples of tuples
+                * (remember: here, key_type refers list [key[0] for key in keys]) */
+                if (key_type == &PyTuple_Type)
+                    ms.tuple_elem_compare = safe_object_compare;
+                else
+                    ms.tuple_elem_compare = ms.key_compare;
+
+                ms.key_compare = unsafe_tuple_compare;
+            }
         }
         else {
             ms.key_compare = safe_object_compare;
         }
 
-        if (keys_are_in_tuples) {
-            /* Make sure we're not dealing with tuples of tuples
-             * (remember: here, key_type refers list [key[0] for key in keys]) */
-            if (key_type == &PyTuple_Type)
-                ms.tuple_elem_compare = safe_object_compare;
-            else
-                ms.tuple_elem_compare = ms.key_compare;
-
-            ms.key_compare = unsafe_tuple_compare;
-        }
     }
     /* End of pre-sort check: ms is now set properly! */
 


I will have another look at it tomorrow and try to open a pull request.

> The following patch fixed the issue and made the whole test suite pass:

Rémi, are you saying there are failing tests currently in the master related to this bug? It seems there are actually very few tests that test for TypeError and all those introduced in 1e34da49ef2 fail to test this code path.

> Rémi, are you saying there are failing tests currently in the master related to this bug?

No, you are right there is no tests for this code path and there is no tests on master related to this bug as far as I can tell.

I think the issue comes from https://github.com/python/cpython/blob/master/Objects/listobject.c#L2307-L2310, there is an early exit from the loop when keys don't have all the same type, but it is wrong to still think they are all tuples since:
  - they don't all have the same type
  - we did not check all elements in the list anyway 

The code at https://github.com/python/cpython/blob/master/Objects/listobject.c#L2307-L2310 should be guarded by the `if (keys_are_all_same_type)`. I opened a PR to add the tests from Lyn Levenick and the proposed fix.

Thanks for the analysis and the suggested PR which is now awaiting review.  While segfaults are nasty, I don't see how this problem would be likely exploitable as a DoS without direct access to the interpreter.  So I'm downgrading it to "deferred blocker" for now to unblock 3.7.3rc1.

New changeset dd5417afcf8924bcdd7077351941ad21727ef644 by Raymond Hettinger (Rémi Lapeyre) in branch 'master':
bpo-36218: Fix handling of heterogeneous values in list.sort (GH-12209)
https://github.com/python/cpython/commit/dd5417afcf8924bcdd7077351941ad21727ef644

New changeset 9dbb09fc27b99d2c08b8f56db71018eb828cc7cd by Raymond Hettinger (Miss Islington (bot)) in branch '3.7':
bpo-36218: Fix handling of heterogeneous values in list.sort (GH-12209) GH-12532)
https://github.com/python/cpython/commit/9dbb09fc27b99d2c08b8f56db71018eb828cc7cd