null pointer deref and segfault in _PyObject_Alloc (obmalloc.c:1258)

[geeknik]

BPO	31166
Nosy	@vstinner, @benjaminp, @methane, @geeknik
Files	31166.txt: valgrind -q ./python 31166.py

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2018-07-27.10:28:55.154>
created_at = <Date 2017-08-10.02:04:37.716>
labels = ['interpreter-core', '3.7', 'type-crash']
title = 'null pointer deref and segfault in _PyObject_Alloc (obmalloc.c:1258)'
updated_at = <Date 2018-07-27.10:28:55.154>
user = 'https://github.com/geeknik'

bugs.python.org fields:

activity = <Date 2018-07-27.10:28:55.154>
actor = 'methane'
assignee = 'none'
closed = True
closed_date = <Date 2018-07-27.10:28:55.154>
closer = 'methane'
components = ['Interpreter Core']
creation = <Date 2017-08-10.02:04:37.716>
creator = 'geeknik'
dependencies = []
files = ['47071']
hgrepos = []
issue_num = 31166
keywords = []
message_count = 10.0
messages = ['300034', '300050', '300051', '300058', '300061', '300062', '300063', '300064', '300065', '322484']
nosy_count = 4.0
nosy_names = ['vstinner', 'benjamin.peterson', 'methane', 'geeknik']
pr_nums = []
priority = 'normal'
resolution = 'wont fix'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue31166'
versions = ['Python 3.7']

[geeknik]

Python 3.7 git commit 3ca9f50 compiled with afl-clang-fast on Ubuntu 16 x64. The following script triggers undefined-behavior followed by a null pointer dereference and a segfault.

import gc
t0ing0=object()
class A(object):
    def f():0
    x=t0ing0
r=gc.get_referrers(t0ing0)
if[0]:dct=r[0]
a=A
for i in range(1):a.f
dct["f"]=lambda:0
(a.f)

Objects/dictobject.c:547:12: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:547:12 in
Objects/dictobject.c:1105:18: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:1105:18 in
Objects/dictobject.c:2739:15: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:2739:15 in
Objects/dictobject.c:789:27: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:789:27 in
Objects/dictobject.c:1104:18: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:1104:18 in
Objects/dictobject.c:994:15: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:994:15 in
Objects/dictobject.c:683:11: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:683:11 in
Objects/dictobject.c:1024:9: runtime error: index 64 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:1024:9 in
Objects/dictobject.c:2882:31: runtime error: index 64 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:2882:31 in
Objects/dictobject.c:2346:15: runtime error: index 128 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:2346:15 in
Objects/dictobject.c:1449:11: runtime error: index 32 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:1449:11 in
Objects/dictobject.c:744:27: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:744:27 in
Objects/dictobject.c:1631:22: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:1631:22 in
Objects/dictobject.c:554:31: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:554:31 in
Objects/dictobject.c:1183:15: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:1183:15 in
Objects/dictobject.c:835:27: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:835:27 in
Objects/dictobject.c:2036:10: runtime error: index 128 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:2036:10 in
Objects/dictobject.c:3504:38: runtime error: index 16 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:3504:38 in
Objects/dictobject.c:3422:38: runtime error: index 64 out of bounds for type 'int8_t [8]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/dictobject.c:3422:38 in
Objects/obmalloc.c:1258:36: runtime error: load of misaligned address 0xffffffffffffffff for type 'block *' (aka 'unsigned char *'), which requires 8 byte alignment
0xffffffffffffffff: note: pointer points here
<memory cannot be printed>
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Objects/obmalloc.c:1258:36 in
ASAN:DEADLYSIGNAL
=================================================================
==768==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc 0x000000506f9f bp 0x7fff0666cbc0 sp 0x7fff0666cb20 T0)
==768==The signal is caused by a READ memory access.
==768==Hint: address points to the zero page.
#0 0x506f9e in _PyObject_Alloc /root/cpython/Objects/obmalloc.c:1258:36
#1 0x9a669b in PyUnicode_New /root/cpython/Objects/unicodeobject.c:1296:24
#2 0x9fea51 in _PyUnicodeWriter_PrepareInternal /root/cpython/Objects/unicodeobject.c:13561:26
#3 0x9b9db4 in PyUnicode_DecodeUTF8Stateful /root/cpython/Objects/unicodeobject.c:4995:9
#4 0x9c0e65 in _PyUnicode_FromId /root/cpython/Objects/unicodeobject.c:2115:22
#5 0x89561e in _PyObject_GetAttrId /root/cpython/Objects/object.c:850:23
#6 0x6b3f4a in _PyObject_CallMethodId /root/cpython/Objects/call.c:1086:16
#7 0x518569 in flush_std_files /root/cpython/Python/pylifecycle.c:889:15
#8 0x517942 in Py_FinalizeEx /root/cpython/Python/pylifecycle.c:959:9
#9 0x5a882b in Py_Main /root/cpython/Modules/main.c:921:9
#10 0x500382 in main /root/cpython/./Programs/python.c:102:11
#11 0x7f94db0bb3f0 in __libc_start_main /build/glibc-mXZSwJ/glibc-2.24/csu/../csu/libc-start.c:291
#12 0x433e49 in _start (/root/cpython/python+0x433e49)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV /root/cpython/Objects/obmalloc.c:1258:36 in _PyObject_Alloc
==768==ABORTING

[benjaminp]

Yeah, bad things happen when the underlying class dict, which isn't normally exposed to Python, is mutated.

[methane]

I think it's false positive of ASAN.

We have dynamically sized block.

cpython/Objects/dict-common.h

Lines 49 to 69 in 3b0f620

	/* Actual hash table of dk_size entries. It holds indices in dk_entries,
	or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
	Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
	The size in bytes of an indice depends on dk_size:
	- 1 byte if dk_size <= 0xff (char*)
	- 2 bytes if dk_size <= 0xffff (int16_t*)
	- 4 bytes if dk_size <= 0xffffffff (int32_t*)
	- 8 bytes otherwise (int64_t*)
	Dynamically sized, 8 is minimum. */
	union {
	int8_t as_1[8];
	int16_t as_2[4];
	int32_t as_4[2];
	#if SIZEOF_VOID_P > 4
	int64_t as_8[1];
	#endif
	} dk_indices;

dictobject.c:547 calls memcpy to fill the block and head pointer
is defined as int8_t [8].
ASAN doesn't know this is overallocated memory block.

[geeknik]

So if I leave UBSan and ASan out of the equation and compile with gcc and run this script:

Program received signal SIGSEGV, Segmentation fault.
update_refs (containers=<optimized out>) at Modules/gcmodule.c:353
353 _PyGCHead_SET_REFS(gc, Py_REFCNT(FROM_GC(gc)));
(gdb) bt
#0 update_refs (containers=<optimized out>) at Modules/gcmodule.c:353
#1 collect (generation=generation@entry=2,
n_collected=n_collected@entry=0x7fffffffe2f8,
n_uncollectable=n_uncollectable@entry=0x7fffffffe300,
nofail=nofail@entry=0) at Modules/gcmodule.c:962
#2 0x00005555555d5365 in collect_with_callback (generation=2)
at Modules/gcmodule.c:1135
#3 PyGC_Collect () at Modules/gcmodule.c:1622
#4 _PyGC_CollectIfEnabled () at Modules/gcmodule.c:1635
#5 0x00005555555b8e28 in Py_FinalizeEx () at Python/pylifecycle.c:978
#6 0x00005555555b9225 in Py_FinalizeEx () at Python/pylifecycle.c:1119
#7 0x00005555555d2ed2 in Py_Main (argc=<optimized out>, argv=<optimized out>)
at Modules/main.c:921
#8 0x00005555555aa1cb in main (argc=2, argv=<optimized out>)
at ./Programs/python.c:102
(gdb) list
348 update_refs(PyGC_Head *containers)
349 {
350 PyGC_Head *gc = containers->gc.gc_next;
351 for (; gc != containers; gc = gc->gc.gc_next) {
352 assert(_PyGCHead_REFS(gc) == GC_REACHABLE);
353 _PyGCHead_SET_REFS(gc, Py_REFCNT(FROM_GC(gc)));
354 /* Python's cyclic gc should never see an incoming refcount
355 * of 0: if something decref'ed to 0, it should have been
356 * deallocated immediately at that time.
357 * Possible cause (if the assert triggers): a tp_dealloc

Valgrind shows a null deref as well after some invalid reads and conditional jumps. I've attached the log, it's a bit verbose.

[methane]

As Benjamin commented, this is caused by mutating internal dict.

PyType_Lookup() use "method cache", based on "tp_version_tag" in the type object.
When you modify internal dict directly, namespace is changed without
invalidating tp_version_tag.
So cached pointer is used, and it's already deallocated.

I don't know we should fix it or not.
I don't have any idea fix this without any performance penalty.

[vstinner]

I don't know we should fix it or not. I don't have any idea fix this without any performance penalty.

The PEP-509 (dict version) might help if we want to fix this bug.

[methane]

But we should check dicts of all parents.
It will has significant penalty, especially for classes having long mro (inheriting metaclass from typing module cause long mro).

[vstinner]

"But we should check dicts of all parents. It will has significant penalty, especially for classes having long mro (inheriting metaclass from typing module cause long mro)."

Oh right. That would defeat the whole purpose of the cache.

Maybe we should not fix the bug. You are not supposed to access the hidden dictionary :-)

[vstinner]

Another solution is to replace class dict with a special type which invalidates the type cache on dict[key]=value.

[methane]

We ignores several crashes caused by exposing internal object
through gc or weakref module.
This case is not special enough to care.