CVE-2018-20406: Integer Overflow or Wraparound (CWE-190)
value: Modules/_pickle.c in Python before 3.7.1 has an integer overflow via a large LONG_BINPUT value that is mishandled during a "resize to twice the size" attempt. This issue might cause memory exhaustion, but is only relevant if the pickle format is used for serializing tens or hundreds of gigabytes of data. This issue is fixed in: v3.4.10, v3.4.10rc1; v3.5.10, v3.5.10rc1, v3.5.7, v3.5.7rc1, v3.5.8, v3.5.8rc1, v3.5.8rc2, v3.5.9; v3.6.10, v3.6.10rc1, v3.6.11, v3.6.11rc1, v3.6.12, v3.6.7, v3.6.7rc1, v3.6.7rc2, v3.6.8, v3.6.8rc1, v3.6.9, v3.6.9rc1; v3.7.1, v3.7.1rc1, v3.7.1rc2, v3.7.2, v3.7.2rc1, v3.7.3, v3.7.3rc1, v3.7.4, v3.7.4rc1, v3.7.4rc2, v3.7.5, v3.7.5rc1, v3.7.6, v3.7.6rc1, v3.7.7, v3.7.7rc1, v3.7.8, v3.7.8rc1, v3.7.9.
CWE description: The product performs a calculation that can
         produce an integer overflow or wraparound when the logic
         assumes that the resulting value will always be larger than
         the original value. This occurs when an integer value is
         incremented to a value that is too large to store in the
         associated representation. When this occurs, the value may
         become a very small or negative number.
CVSS v3 base score: 7.5
Published: 2018-12-23T23:29Z
Repository: https://github.com/python/cpython
Language: C
Files changed: Modules/_pickle.c
Commit date: 2018-09-20 18:36:40 -0700
Commit message: closes bpo-34656: Avoid relying on signed overflow in _pickle memos. (GH-9261)


Diff: diff --git a/Modules/_pickle.c b/Modules/_pickle.c
index 2de70f5d94..3588e33f09 100644
--- a/Modules/_pickle.c
+++ b/Modules/_pickle.c
@@ -600,13 +600,13 @@ typedef struct {
     PyObject *me_key;
     Py_ssize_t me_value;
 } PyMemoEntry;
 
 typedef struct {
-    Py_ssize_t mt_mask;
-    Py_ssize_t mt_used;
-    Py_ssize_t mt_allocated;
+    size_t mt_mask;
+    size_t mt_used;
+    size_t mt_allocated;
     PyMemoEntry *mt_table;
 } PyMemoTable;
 
 typedef struct PicklerObject {
     PyObject_HEAD
@@ -648,12 +648,12 @@ typedef struct UnpicklerObject {
     Pdata *stack;               /* Pickle data stack, store unpickled objects. */
 
     /* The unpickler memo is just an array of PyObject *s. Using a dict
        is unnecessary, since the keys are contiguous ints. */
     PyObject **memo;
-    Py_ssize_t memo_size;       /* Capacity of the memo array */
-    Py_ssize_t memo_len;        /* Number of objects in the memo */
+    size_t memo_size;       /* Capacity of the memo array */
+    size_t memo_len;        /* Number of objects in the memo */
 
     PyObject *pers_func;        /* persistent_load() method, can be NULL. */
     PyObject *pers_func_self;   /* borrowed reference to self if pers_func
                                    is an unbound method, NULL otherwise */
 
@@ -735,11 +735,10 @@ PyMemoTable_New(void)
 }
 
 static PyMemoTable *
 PyMemoTable_Copy(PyMemoTable *self)
 {
-    Py_ssize_t i;
     PyMemoTable *new = PyMemoTable_New();
     if (new == NULL)
         return NULL;
 
     new->mt_used = self->mt_used;
@@ -752,11 +751,11 @@ PyMemoTable_Copy(PyMemoTable *self)
     if (new->mt_table == NULL) {
         PyMem_FREE(new);
         PyErr_NoMemory();
         return NULL;
     }
-    for (i = 0; i < self->mt_allocated; i++) {
+    for (size_t i = 0; i < self->mt_allocated; i++) {
         Py_XINCREF(self->mt_table[i].me_key);
     }
     memcpy(new->mt_table, self->mt_table,
            sizeof(PyMemoEntry) * self->mt_allocated);
 
@@ -798,11 +797,11 @@ PyMemoTable_Del(PyMemoTable *self)
 static PyMemoEntry *
 _PyMemoTable_Lookup(PyMemoTable *self, PyObject *key)
 {
     size_t i;
     size_t perturb;
-    size_t mask = (size_t)self->mt_mask;
+    size_t mask = self->mt_mask;
     PyMemoEntry *table = self->mt_table;
     PyMemoEntry *entry;
     Py_hash_t hash = (Py_hash_t)key >> 3;
 
     i = hash & mask;
@@ -819,26 +818,28 @@ _PyMemoTable_Lookup(PyMemoTable *self, PyObject *key)
     Py_UNREACHABLE();
 }
 
 /* Returns -1 on failure, 0 on success. */
 static int
-_PyMemoTable_ResizeTable(PyMemoTable *self, Py_ssize_t min_size)
+_PyMemoTable_ResizeTable(PyMemoTable *self, size_t min_size)
 {
     PyMemoEntry *oldtable = NULL;
     PyMemoEntry *oldentry, *newentry;
-    Py_ssize_t new_size = MT_MINSIZE;
-    Py_ssize_t to_process;
+    size_t new_size = MT_MINSIZE;
+    size_t to_process;
 
     assert(min_size > 0);
 
-    /* Find the smallest valid table size >= min_size. */
-    while (new_size < min_size && new_size > 0)
-        new_size <<= 1;
-    if (new_size <= 0) {
+    if (min_size > PY_SSIZE_T_MAX) {
         PyErr_NoMemory();
         return -1;
     }
+
+    /* Find the smallest valid table size >= min_size. */
+    while (new_size < min_size) {
+        new_size <<= 1;
+    }
     /* new_size needs to be a power of two. */
     assert((new_size & (new_size - 1)) == 0);
 
     /* Allocate new table. */
     oldtable = self->mt_table;
@@ -907,14 +908,16 @@ PyMemoTable_Set(PyMemoTable *self, PyObject *key, Py_ssize_t value)
      * the number of expensive resize operations in a growing memo table.
      *
      * Very large memo tables (over 50K items) use doubling instead.
      * This may help applications with severe memory constraints.
      */
-    if (!(self->mt_used * 3 >= (self->mt_mask + 1) * 2))
+    if (SIZE_MAX / 3 >= self->mt_used && self->mt_used * 3 < self->mt_allocated * 2) {
         return 0;
-    return _PyMemoTable_ResizeTable(self,
-        (self->mt_used > 50000 ? 2 : 4) * self->mt_used);
+    }
+    // self->mt_used is always < PY_SSIZE_T_MAX, so this can't overflow.
+    size_t desired_size = (self->mt_used > 50000 ? 2 : 4) * self->mt_used;
+    return _PyMemoTable_ResizeTable(self, desired_size);
 }
 
 #undef MT_MINSIZE
 #undef PERTURB_SHIFT
 
@@ -1374,13 +1377,13 @@ _Unpickler_Readline(UnpicklerObject *self, char **result)
 }
 
 /* Returns -1 (with an exception set) on failure, 0 on success. The memo array
    will be modified in place. */
 static int
-_Unpickler_ResizeMemoList(UnpicklerObject *self, Py_ssize_t new_size)
+_Unpickler_ResizeMemoList(UnpicklerObject *self, size_t new_size)
 {
-    Py_ssize_t i;
+    size_t i;
 
     assert(new_size > self->memo_size);
 
     PyObject **memo_new = self->memo;
     PyMem_RESIZE(memo_new, PyObject *, new_size);
@@ -1395,22 +1398,22 @@ _Unpickler_ResizeMemoList(UnpicklerObject *self, Py_ssize_t new_size)
     return 0;
 }
 
 /* Returns NULL if idx is out of bounds. */
 static PyObject *
-_Unpickler_MemoGet(UnpicklerObject *self, Py_ssize_t idx)
+_Unpickler_MemoGet(UnpicklerObject *self, size_t idx)
 {
-    if (idx < 0 || idx >= self->memo_size)
+    if (idx >= self->memo_size)
         return NULL;
 
     return self->memo[idx];
 }
 
 /* Returns -1 (with an exception set) on failure, 0 on success.
    This takes its own reference to `value`. */
 static int
-_Unpickler_MemoPut(UnpicklerObject *self, Py_ssize_t idx, PyObject *value)
+_Unpickler_MemoPut(UnpicklerObject *self, size_t idx, PyObject *value)
 {
     PyObject *old_item;
 
     if (idx >= self->memo_size) {
         if (_Unpickler_ResizeMemoList(self, idx * 2) < 0)
@@ -4411,18 +4414,17 @@ Copy the memo to a new object.
 
 static PyObject *
 _pickle_PicklerMemoProxy_copy_impl(PicklerMemoProxyObject *self)
 /*[clinic end generated code: output=bb83a919d29225ef input=b73043485ac30b36]*/
 {
-    Py_ssize_t i;
     PyMemoTable *memo;
     PyObject *new_memo = PyDict_New();
     if (new_memo == NULL)
         return NULL;
 
     memo = self->pickler->memo;
-    for (i = 0; i < memo->mt_allocated; ++i) {
+    for (size_t i = 0; i < memo->mt_allocated; ++i) {
         PyMemoEntry entry = memo->mt_table[i];
         if (entry.me_key != NULL) {
             int status;
             PyObject *key, *value;
 
@@ -6841,11 +6843,11 @@ Copy the memo to a new object.
 
 static PyObject *
 _pickle_UnpicklerMemoProxy_copy_impl(UnpicklerMemoProxyObject *self)
 /*[clinic end generated code: output=e12af7e9bc1e4c77 input=97769247ce032c1d]*/
 {
-    Py_ssize_t i;
+    size_t i;
     PyObject *new_memo = PyDict_New();
     if (new_memo == NULL)
         return NULL;
 
     for (i = 0; i < self->unpickler->memo_size; i++) {
@@ -6992,12 +6994,11 @@ Unpickler_get_memo(UnpicklerObject *self)
 
 static int
 Unpickler_set_memo(UnpicklerObject *self, PyObject *obj)
 {
     PyObject **new_memo;
-    Py_ssize_t new_memo_size = 0;
-    Py_ssize_t i;
+    size_t new_memo_size = 0;
 
     if (obj == NULL) {
         PyErr_SetString(PyExc_TypeError,
                         "attribute deletion is not supported");
         return -1;
@@ -7010,11 +7011,11 @@ Unpickler_set_memo(UnpicklerObject *self, PyObject *obj)
         new_memo_size = unpickler->memo_size;
         new_memo = _Unpickler_NewMemo(new_memo_size);
         if (new_memo == NULL)
             return -1;
 
-        for (i = 0; i < new_memo_size; i++) {
+        for (size_t i = 0; i < new_memo_size; i++) {
             Py_XINCREF(unpickler->memo[i]);
             new_memo[i] = unpickler->memo[i];
         }
     }
     else if (PyDict_Check(obj)) {
@@ -7058,12 +7059,11 @@ Unpickler_set_memo(UnpicklerObject *self, PyObject *obj)
 
     return 0;
 
   error:
     if (new_memo_size) {
-        i = new_memo_size;
-        while (--i >= 0) {
+        for (size_t i = new_memo_size - 1; i != SIZE_MAX; i--) {
             Py_XDECREF(new_memo[i]);
         }
         PyMem_FREE(new_memo);
     }
     return -1;

Vulnerable code:     Py_ssize_t mt_mask;
    Py_ssize_t mt_used;
    Py_ssize_t mt_allocated;
    Py_ssize_t memo_size;       /* Capacity of the memo array */
    Py_ssize_t memo_len;        /* Number of objects in the memo */
    Py_ssize_t i;
    for (i = 0; i < self->mt_allocated; i++) {
    size_t mask = (size_t)self->mt_mask;
_PyMemoTable_ResizeTable(PyMemoTable *self, Py_ssize_t min_size)
    Py_ssize_t new_size = MT_MINSIZE;
    Py_ssize_t to_process;
    /* Find the smallest valid table size >= min_size. */
    while (new_size < min_size && new_size > 0)
        new_size <<= 1;
    if (new_size <= 0) {
    if (!(self->mt_used * 3 >= (self->mt_mask + 1) * 2))
    return _PyMemoTable_ResizeTable(self,
        (self->mt_used > 50000 ? 2 : 4) * self->mt_used);
_Unpickler_ResizeMemoList(UnpicklerObject *self, Py_ssize_t new_size)
    Py_ssize_t i;
_Unpickler_MemoGet(UnpicklerObject *self, Py_ssize_t idx)
    if (idx < 0 || idx >= self->memo_size)
_Unpickler_MemoPut(UnpicklerObject *self, Py_ssize_t idx, PyObject *value)
    Py_ssize_t i;
    for (i = 0; i < memo->mt_allocated; ++i) {
    Py_ssize_t i;
    Py_ssize_t new_memo_size = 0;
    Py_ssize_t i;
        for (i = 0; i < new_memo_size; i++) {
        i = new_memo_size;
        while (--i >= 0) {
Fixed code:     size_t mt_mask;
    size_t mt_used;
    size_t mt_allocated;
    size_t memo_size;       /* Capacity of the memo array */
    size_t memo_len;        /* Number of objects in the memo */
    for (size_t i = 0; i < self->mt_allocated; i++) {
    size_t mask = self->mt_mask;
_PyMemoTable_ResizeTable(PyMemoTable *self, size_t min_size)
    size_t new_size = MT_MINSIZE;
    size_t to_process;
    if (min_size > PY_SSIZE_T_MAX) {

    /* Find the smallest valid table size >= min_size. */
    while (new_size < min_size) {
        new_size <<= 1;
    }
    if (SIZE_MAX / 3 >= self->mt_used && self->mt_used * 3 < self->mt_allocated * 2) {
    }
    // self->mt_used is always < PY_SSIZE_T_MAX, so this can't overflow.
    size_t desired_size = (self->mt_used > 50000 ? 2 : 4) * self->mt_used;
    return _PyMemoTable_ResizeTable(self, desired_size);
_Unpickler_ResizeMemoList(UnpicklerObject *self, size_t new_size)
    size_t i;
_Unpickler_MemoGet(UnpicklerObject *self, size_t idx)
    if (idx >= self->memo_size)
_Unpickler_MemoPut(UnpicklerObject *self, size_t idx, PyObject *value)
    for (size_t i = 0; i < memo->mt_allocated; ++i) {
    size_t i;
    size_t new_memo_size = 0;
        for (size_t i = 0; i < new_memo_size; i++) {
        for (size_t i = new_memo_size - 1; i != SIZE_MAX; i--) {