classification
Title: Use-after-free in _asyncio_Future_remove_done_callback() of _asynciomodule.c
Type: crash Stage: resolved
Components: Versions: Python 3.7, Python 3.6
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Ned Williamson, inada.naoki, ned.deily, vstinner, yselivanov
Priority: Keywords: patch

Created on 2016-12-13 19:26 by Ned Williamson, last changed 2017-03-31 16:36 by dstufft. This issue is now closed.

Files
File name Uploaded Description Edit
Issue28963.patch yselivanov, 2016-12-13 23:31 review
Pull Requests
URL Status Linked Edit
PR 408 merged yselivanov, 2017-03-02 23:38
PR 703 larry, 2017-03-17 21:00
PR 552 closed dstufft, 2017-03-31 16:36
Messages (13)
msg283134 - (view) Author: Ned Williamson (Ned Williamson) Date: 2016-12-13 19:26
There are two cases of use-after-free in the new Modules/_asynciomodule.c in the release candidate for Python 3.6, but I'm filing these together because it's the same underlying issue.

In both cases in this file where the unsafe `PyList_GET_ITEM` is called, `_asyncio_Future_remove_done_callback` and `future_schedule_callbacks`, there is a function called on the fetched item that allows the user to mutate the callbacks list (`PyObject_RichCompareBool` and `_PyObject_CallMethodId`), which then leads to OOB access on subsequent iterations.

For example, this script can trigger the vulnerability for `remove_done_callback`:
```
import asyncio

fut = asyncio.Future()
fut.add_done_callback(str)

for _ in range(63):
    fut.add_done_callback(id)

class evil:
    def __eq__(self, other):
        fut.remove_done_callback(id)
        return False

fut.remove_done_callback(evil())
```

On an ASAN build we can see that there is indeed a UAF occurring:
```
=================================================================
==19239==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60300000e7f0 at pc 0x000106fe6704 bp 0x7fff5cda09c0 sp 0x7fff5cda09b8
READ of size 8 at 0x60300000e7f0 thread T0
    #0 0x106fe6703 in _asyncio_Future_remove_done_callback _asynciomodule.c:526
    #1 0x102f5af35 in _PyCFunction_FastCallDict methodobject.c:192
    #2 0x1030e9044 in call_function ceval.c:4788
    #3 0x1030da2f0 in _PyEval_EvalFrameDefault ceval.c:3275
    #4 0x1030eb09b in _PyEval_EvalCodeWithName ceval.c:718
    #5 0x1030ced53 in PyEval_EvalCode ceval.c:4140
    #6 0x10317da47 in PyRun_FileExFlags pythonrun.c:980
    #7 0x10317c110 in PyRun_SimpleFileExFlags pythonrun.c:396
    #8 0x1031c76b8 in Py_Main main.c:320
    #9 0x102e5ed40 in main python.c:69
    #10 0x7fffc9bd8254 in start (libdyld.dylib+0x5254)

0x60300000e7f0 is located 0 bytes to the right of 32-byte region [0x60300000e7d0,0x60300000e7f0)
allocated by thread T0 here:
    #0 0x1039d5f87 in wrap_realloc (libclang_rt.asan_osx_dynamic.dylib+0x4af87)
    #1 0x102efb089 in list_ass_slice listobject.c:63
    #2 0x106fe6605 in _asyncio_Future_remove_done_callback _asynciomodule.c:541
    #3 0x102f5af35 in _PyCFunction_FastCallDict methodobject.c:192
    #4 0x1030e9044 in call_function ceval.c:4788
    #5 0x1030da2f0 in _PyEval_EvalFrameDefault ceval.c:3275
    #6 0x1030ed94a in _PyFunction_FastCallDict ceval.c:718
    #7 0x102e81308 in _PyObject_FastCallDict abstract.c:2295
    #8 0x102e816b1 in _PyObject_Call_Prepend abstract.c:2358
    #9 0x102e81286 in _PyObject_FastCallDict abstract.c:2316
    #10 0x102fa125a in slot_tp_richcompare typeobject.c:6287
    #11 0x102f61f66 in PyObject_RichCompare object.c:671
    #12 0x102f62421 in PyObject_RichCompareBool object.c:741
    #13 0x106fe6544 in _asyncio_Future_remove_done_callback _asynciomodule.c:528
    #14 0x102f5af35 in _PyCFunction_FastCallDict methodobject.c:192
    #15 0x1030e9044 in call_function ceval.c:4788
    #16 0x1030da2f0 in _PyEval_EvalFrameDefault ceval.c:3275
    #17 0x1030eb09b in _PyEval_EvalCodeWithName ceval.c:718
    #18 0x1030ced53 in PyEval_EvalCode ceval.c:4140
    #19 0x10317da47 in PyRun_FileExFlags pythonrun.c:980
    #20 0x10317c110 in PyRun_SimpleFileExFlags pythonrun.c:396
    #21 0x1031c76b8 in Py_Main main.c:320
    #22 0x102e5ed40 in main python.c:69
    #23 0x7fffc9bd8254 in start (libdyld.dylib+0x5254)

SUMMARY: AddressSanitizer: heap-buffer-overflow _asynciomodule.c:526 in _asyncio_Future_remove_done_callback
Shadow bytes around the buggy address:
  0x1c0600001ca0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600001cb0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600001cc0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600001cd0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600001ce0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x1c0600001cf0: fa fa fa fa fa fa fa fa fa fa 00 00 00 00[fa]fa
  0x1c0600001d00: 00 00 00 fa fa fa 00 00 00 fa fa fa 00 00 00 02
  0x1c0600001d10: fa fa fd fd fd fd fa fa fd fd fd fd fa fa fd fd
  0x1c0600001d20: fd fd fa fa fd fd fd fd fa fa fd fd fd fd fa fa
  0x1c0600001d30: fd fd fd fd fa fa fd fd fd fd fa fa fd fd fd fd
  0x1c0600001d40: fa fa fd fd fd fd fa fa 00 00 00 00 fa fa 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==19239==ABORTING
[1]    19239 abort      ASAN_OPTIONS=halt_on_error=0 ./python.exe test.py
```
msg283143 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2016-12-13 22:57
Oh, this is a release blocker. I'll take a look later today.
msg283145 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2016-12-13 23:31
I think the bug is only in _asyncio_Future_remove_done_callback, since future_schedule_callbacks makes a slice first, which cannot be mutated.

I'm attaching a patch.  Inada, would you be able to take a look?
msg283146 - (view) Author: Ned Williamson (Ned Williamson) Date: 2016-12-13 23:36
yselivanov, ah I think you're right. I misread that function after I noticed the issue in the first one.
msg283171 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2016-12-14 08:09
> Oh, this is a release blocker. I'll take a look later today.

The bug requires to have an "evil" class which is unlikely in an application. I don't think that it's a release blocker.
msg283172 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2016-12-14 08:12
I see three options:

* avoid PyObject_RichCompareBool() which can run arbitrary Python code: this can be complicated since callbacks can be proxies, functools.partial, lambda, and other funny callable objects
* reimplement the same algorithm than the Python implementation: create a new list.
* do nothing: if you do weird things, it's your fault :-)

My favorite option is to work on a new list.
msg283173 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2016-12-14 08:47
Inada-san, thanks for the review. You're right, we need to fix another edge-case.  I'll upload a new patch tomorrow.

Victor, fourth option we should go with is to commit the attached patch (with Inada-san review comment fixed).

I guess it's up to Ned if he want to cherry-pick the patch to Python 3.6.  I agree that the bug is very unlikely to appear in any real-world code.
msg283179 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2016-12-14 09:21
_asyncio_Future_remove_done_callback() is still wrong with  Issue28963.patch: what if an evil __eq__() methods inserts or remove directly items of the future callbacks list?

By design, it's not safe to iterate on a list if the body of the list calls arbitrary Python code.

(I don't know how exactly, but everything in Python is possible, see the gc module to retrieve private fields of a C objecct.)
msg283202 - (view) Author: Ned Deily (ned.deily) * (Python committer) Date: 2016-12-14 16:03
This doesn't sound like a showstopper issue so I think it can wait for 3.6.1.
msg288191 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2017-02-20 11:07
3.6.0 had been released?
Yury, would you create pull request?
msg288217 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2017-02-20 16:31
I will in a couple of days.
msg288856 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2017-03-03 05:11
New changeset d8b72e4a0673c414120b029065dbe77055f12e82 by Yury Selivanov in branch '3.6':
bpo-28963: Fix out of bound iteration in asyncio.Future.remove_done_callback/C (#408)
https://github.com/python/cpython/commit/d8b72e4a0673c414120b029065dbe77055f12e82
msg290334 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2017-03-24 23:07
New changeset 84af903f3bc6780cb4e73ff05ad2e242d3966417 by Yury Selivanov in branch 'master':
bpo-28963: Fix out of bound iteration in asyncio.Future.remove_done_callback/C (#408)
https://github.com/python/cpython/commit/84af903f3bc6780cb4e73ff05ad2e242d3966417
History
Date User Action Args
2017-03-31 16:36:28dstufftsetpull_requests: + pull_request1016
2017-03-24 23:07:30yselivanovsetmessages: + msg290334
2017-03-17 21:00:33larrysetpull_requests: + pull_request598
2017-03-03 23:12:56yselivanovsetstatus: open -> closed
stage: resolved
resolution: fixed
versions: + Python 3.7
2017-03-03 05:47:39gvanrossumsetnosy: - gvanrossum
2017-03-03 05:11:26yselivanovsetmessages: + msg288856
2017-03-02 23:38:20yselivanovsetpull_requests: + pull_request340
2017-02-20 16:31:16yselivanovsetmessages: + msg288217
2017-02-20 11:07:59inada.naokisetmessages: + msg288191
2016-12-14 16:04:10giampaolo.rodolasetnosy: - giampaolo.rodola
2016-12-14 16:03:44ned.deilysetmessages: + msg283202
2016-12-14 09:21:08vstinnersetmessages: + msg283179
2016-12-14 08:47:14yselivanovsetmessages: + msg283173
2016-12-14 08:14:11vstinnersettitle: Use-after-free in _asynciomodule.c -> Use-after-free in _asyncio_Future_remove_done_callback() of _asynciomodule.c
2016-12-14 08:12:58vstinnersetmessages: + msg283172
2016-12-14 08:09:15vstinnersetpriority: release blocker ->

messages: + msg283171
2016-12-13 23:36:17Ned Williamsonsetmessages: + msg283146
2016-12-13 23:31:55yselivanovsetfiles: + Issue28963.patch
priority: normal -> release blocker

nosy: + ned.deily
messages: + msg283145

keywords: + patch
2016-12-13 22:57:54yselivanovsetmessages: + msg283143
2016-12-13 20:02:30ned.deilysetnosy: + gvanrossum, vstinner, giampaolo.rodola, yselivanov
2016-12-13 19:34:21berker.peksagsetnosy: + inada.naoki
2016-12-13 19:26:41Ned Williamsoncreate