classification
Title: .sort() segfaults consistently on crafted input
Type: crash Stage: resolved
Components: Interpreter Core Versions: Python 3.8, Python 3.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Lyn Levenick, SilentGhost, elliot.gorokhovsky, lukasz.langa, lys.nikolaou, ned.deily, remi.lapeyre, rhettinger, xtreak, zach.ware
Priority: deferred blocker Keywords: patch

Created on 2019-03-06 21:54 by Lyn Levenick, last changed 2019-03-25 07:49 by rhettinger. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 12209 merged remi.lapeyre, 2019-03-07 09:42
PR 12532 merged miss-islington, 2019-03-25 07:25
Messages (14)
msg337341 - (view) Author: Lyn Levenick (Lyn Levenick) Date: 2019-03-06 21:54
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.
msg337342 - (view) Author: SilentGhost (SilentGhost) * (Python triager) Date: 2019-03-06 22:07
Can confirm on 3.7.1 on Linux. The same is happening for sorted. I wonder if the optimisation done in 1e34da49ef2 is responsible
msg337343 - (view) Author: Lysandros Nikolaou (lys.nikolaou) * Date: 2019-03-06 22:16
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
msg337344 - (view) Author: Karthikeyan Singaravelan (xtreak) * (Python triager) Date: 2019-03-06 22:23
Adding ned and Łukasz since this seems to happen on release builds.
msg337345 - (view) Author: Zachary Ware (zach.ware) * (Python committer) Date: 2019-03-06 22:30
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
msg337346 - (view) Author: Rémi Lapeyre (remi.lapeyre) * Date: 2019-03-06 22:30
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'
msg337347 - (view) Author: Rémi Lapeyre (remi.lapeyre) * Date: 2019-03-06 22:41
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.
msg337348 - (view) Author: Karthikeyan Singaravelan (xtreak) * (Python triager) Date: 2019-03-06 22:56
@remi.lapeyre please make sure you are not unsubscribing others by mistake while adding comment.
msg337349 - (view) Author: Rémi Lapeyre (remi.lapeyre) * Date: 2019-03-06 23:09
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.
msg337373 - (view) Author: SilentGhost (SilentGhost) * (Python triager) Date: 2019-03-07 08:39
> 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.
msg337378 - (view) Author: Rémi Lapeyre (remi.lapeyre) * Date: 2019-03-07 09:43
> 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.
msg337744 - (view) Author: Ned Deily (ned.deily) * (Python committer) Date: 2019-03-12 14:29
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.
msg338785 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-03-25 07:25
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
msg338786 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-03-25 07:48
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
History
Date User Action Args
2019-03-25 07:49:35rhettingersetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2019-03-25 07:48:03rhettingersetmessages: + msg338786
2019-03-25 07:25:51miss-islingtonsetpull_requests: + pull_request12482
2019-03-25 07:25:39rhettingersetmessages: + msg338785
2019-03-12 14:29:02ned.deilysetpriority: release blocker -> deferred blocker

messages: + msg337744
2019-03-07 09:43:34remi.lapeyresetmessages: + msg337378
2019-03-07 09:42:51remi.lapeyresetkeywords: + patch
stage: needs patch -> patch review
pull_requests: + pull_request12201
2019-03-07 08:39:27SilentGhostsetmessages: + msg337373
2019-03-06 23:09:43remi.lapeyresetmessages: + msg337349
2019-03-06 22:56:11xtreaksetnosy: + zach.ware, elliot.gorokhovsky
messages: + msg337348
2019-03-06 22:41:58remi.lapeyresetnosy: - zach.ware, elliot.gorokhovsky
messages: + msg337347
2019-03-06 22:38:12xtreaksetnosy: + zach.ware, elliot.gorokhovsky
2019-03-06 22:30:52remi.lapeyresetnosy: + remi.lapeyre, - zach.ware, elliot.gorokhovsky
messages: + msg337346
2019-03-06 22:30:33zach.waresetnosy: + elliot.gorokhovsky
2019-03-06 22:30:06zach.waresetpriority: normal -> release blocker
nosy: + zach.ware, - elliot.gorokhovsky
messages: + msg337345
2019-03-06 22:28:47SilentGhostsetnosy: + elliot.gorokhovsky
2019-03-06 22:23:03xtreaksetnosy: + ned.deily, xtreak, lukasz.langa
messages: + msg337344
2019-03-06 22:18:03SilentGhostsetversions: + Python 3.8
2019-03-06 22:16:26lys.nikolaousetnosy: + lys.nikolaou
messages: + msg337343
2019-03-06 22:07:27SilentGhostsetnosy: + rhettinger, SilentGhost
messages: + msg337342

components: + Interpreter Core
stage: needs patch
2019-03-06 21:54:32Lyn Levenickcreate