Vulnerability: 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.
Vulnerability ID: CVE-2018-20406
CWE: CWE-190
Severity score: 2.9
Project: https://github.com/python/cpython
Published: 2018-12-23
File: Modules/_pickle.c
Commit message: closes bpo-34656: Avoid relying on signed overflow in _pickle memos. (GH-9261)
Commit author: Benjamin Peterson

Vulnerable version (before fix):
 typedef struct { } PyMemoEntry;  typedef struct {     Py_ssize_t mt_mask;     Py_ssize_t mt_used;     Py_ssize_t mt_allocated;     PyMemoEntry *mt_table; } PyMemoTable;  typedef struct UnpicklerObject {     /* 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 */      PyObject *pers_func;        /* persistent_load() method, can be NULL. */     PyObject *pers_func_self;   /* borrowed reference to self if pers_func PyMemoTable_New(void) static PyMemoTable * PyMemoTable_Copy(PyMemoTable *self) {     Py_ssize_t i;     PyMemoTable *new = PyMemoTable_New();     if (new == NULL)         return NULL; PyMemoTable_Copy(PyMemoTable *self)         PyErr_NoMemory();         return NULL;     }     for (i = 0; i < self->mt_allocated; i++) {         Py_XINCREF(self->mt_table[i].me_key);     }     memcpy(new->mt_table, self->mt_table, _PyMemoTable_Lookup(PyMemoTable *self, PyObject *key) {     size_t i;     size_t perturb;     size_t mask = (size_t)self->mt_mask;     PyMemoEntry *table = self->mt_table;     PyMemoEntry *entry;     Py_hash_t hash = (Py_hash_t)key >> 3; _PyMemoTable_Lookup(PyMemoTable *self, PyObject *key)  /* Returns -1 on failure, 0 on success. */ static int _PyMemoTable_ResizeTable(PyMemoTable *self, Py_ssize_t min_size) {     PyMemoEntry *oldtable = NULL;     PyMemoEntry *oldentry, *newentry;     Py_ssize_t new_size = MT_MINSIZE;     Py_ssize_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) {         PyErr_NoMemory();         return -1;     }     /* new_size needs to be a power of two. */     assert((new_size & (new_size - 1)) == 0);  PyMemoTable_Set(PyMemoTable *self, PyObject *key, Py_ssize_t value)      * 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))         return 0;     return _PyMemoTable_ResizeTable(self,         (self->mt_used > 50000 ? 2 : 4) * self->mt_used); }  #undef MT_MINSIZE _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) {     Py_ssize_t i;      assert(new_size > self->memo_size);  _Unpickler_ResizeMemoList(UnpicklerObject *self, Py_ssize_t new_size)  /* Returns NULL if idx is out of bounds. */ static PyObject * _Unpickler_MemoGet(UnpicklerObject *self, Py_ssize_t idx) {     if (idx < 0 || idx >= self->memo_size)         return NULL;      return self->memo[idx]; _Unpickler_MemoGet(UnpicklerObject *self, Py_ssize_t 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) {     PyObject *old_item;  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) {         PyMemoEntry entry = memo->mt_table[i];         if (entry.me_key != NULL) {             int status; static PyObject * _pickle_UnpicklerMemoProxy_copy_impl(UnpicklerMemoProxyObject *self) /*[clinic end generated code: output=e12af7e9bc1e4c77 input=97769247ce032c1d]*/ {     Py_ssize_t i;     PyObject *new_memo = PyDict_New();     if (new_memo == NULL)         return NULL; static int Unpickler_set_memo(UnpicklerObject *self, PyObject *obj) {     PyObject **new_memo;     Py_ssize_t new_memo_size = 0;     Py_ssize_t i;      if (obj == NULL) {         PyErr_SetString(PyExc_TypeError, Unpickler_set_memo(UnpicklerObject *self, PyObject *obj)         if (new_memo == NULL)             return -1;          for (i = 0; i < new_memo_size; i++) {             Py_XINCREF(unpickler->memo[i]);             new_memo[i] = unpickler->memo[i];         } Unpickler_set_memo(UnpicklerObject *self, PyObject *obj)    error:     if (new_memo_size) {         i = new_memo_size;         while (--i >= 0) {             Py_XDECREF(new_memo[i]);         }         PyMem_FREE(new_memo);

Fixed version (after fix):
 typedef struct { } PyMemoEntry;  typedef struct {     size_t mt_mask;     size_t mt_used;     size_t mt_allocated;     PyMemoEntry *mt_table; } PyMemoTable;  typedef struct UnpicklerObject {     /* The unpickler memo is just an array of PyObject *s. Using a dict        is unnecessary, since the keys are contiguous ints. */     PyObject **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 PyMemoTable_New(void) static PyMemoTable * PyMemoTable_Copy(PyMemoTable *self) {     PyMemoTable *new = PyMemoTable_New();     if (new == NULL)         return NULL; PyMemoTable_Copy(PyMemoTable *self)         PyErr_NoMemory();         return NULL;     }     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, _PyMemoTable_Lookup(PyMemoTable *self, PyObject *key) {     size_t i;     size_t perturb;     size_t mask = self->mt_mask;     PyMemoEntry *table = self->mt_table;     PyMemoEntry *entry;     Py_hash_t hash = (Py_hash_t)key >> 3; _PyMemoTable_Lookup(PyMemoTable *self, PyObject *key)  /* Returns -1 on failure, 0 on success. */ static int _PyMemoTable_ResizeTable(PyMemoTable *self, size_t min_size) {     PyMemoEntry *oldtable = NULL;     PyMemoEntry *oldentry, *newentry;     size_t new_size = MT_MINSIZE;     size_t to_process;      assert(min_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);  PyMemoTable_Set(PyMemoTable *self, PyObject *key, Py_ssize_t value)      * Very large memo tables (over 50K items) use doubling instead.      * This may help applications with severe memory constraints.      */     if (SIZE_MAX / 3 >= self->mt_used && self->mt_used * 3 < self->mt_allocated * 2) {         return 0;     }     // 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 _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, size_t new_size) {     size_t i;      assert(new_size > self->memo_size);  _Unpickler_ResizeMemoList(UnpicklerObject *self, Py_ssize_t new_size)  /* Returns NULL if idx is out of bounds. */ static PyObject * _Unpickler_MemoGet(UnpicklerObject *self, size_t idx) {     if (idx >= self->memo_size)         return NULL;      return self->memo[idx]; _Unpickler_MemoGet(UnpicklerObject *self, Py_ssize_t 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, size_t idx, PyObject *value) {     PyObject *old_item;  static PyObject * _pickle_PicklerMemoProxy_copy_impl(PicklerMemoProxyObject *self) /*[clinic end generated code: output=bb83a919d29225ef input=b73043485ac30b36]*/ {     PyMemoTable *memo;     PyObject *new_memo = PyDict_New();     if (new_memo == NULL)         return NULL;      memo = self->pickler->memo;     for (size_t i = 0; i < memo->mt_allocated; ++i) {         PyMemoEntry entry = memo->mt_table[i];         if (entry.me_key != NULL) {             int status; static PyObject * _pickle_UnpicklerMemoProxy_copy_impl(UnpicklerMemoProxyObject *self) /*[clinic end generated code: output=e12af7e9bc1e4c77 input=97769247ce032c1d]*/ {     size_t i;     PyObject *new_memo = PyDict_New();     if (new_memo == NULL)         return NULL; static int Unpickler_set_memo(UnpicklerObject *self, PyObject *obj) {     PyObject **new_memo;     size_t new_memo_size = 0;      if (obj == NULL) {         PyErr_SetString(PyExc_TypeError, Unpickler_set_memo(UnpicklerObject *self, PyObject *obj)         if (new_memo == NULL)             return -1;          for (size_t i = 0; i < new_memo_size; i++) {             Py_XINCREF(unpickler->memo[i]);             new_memo[i] = unpickler->memo[i];         } Unpickler_set_memo(UnpicklerObject *self, PyObject *obj)    error:     if (new_memo_size) {         for (size_t i = new_memo_size - 1; i != SIZE_MAX; i--) {             Py_XDECREF(new_memo[i]);         }         PyMem_FREE(new_memo);

Patch:
patch: @@ -602,9 +602,9 @@ typedef struct {
 } 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;
 
@@ -650,8 +650,8 @@ typedef struct UnpicklerObject {
     /* 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
@@ -737,7 +737,6 @@ PyMemoTable_New(void)
 static PyMemoTable *
 PyMemoTable_Copy(PyMemoTable *self)
 {
-    Py_ssize_t i;
     PyMemoTable *new = PyMemoTable_New();
     if (new == NULL)
         return NULL;
@@ -754,7 +753,7 @@ PyMemoTable_Copy(PyMemoTable *self)
         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,
@@ -800,7 +799,7 @@ _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;
@@ -821,22 +820,24 @@ _PyMemoTable_Lookup(PyMemoTable *self, PyObject *key)
 
 /* 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);
 
@@ -909,10 +910,12 @@ PyMemoTable_Set(PyMemoTable *self, PyObject *key, Py_ssize_t value)
      * 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
@@ -1376,9 +1379,9 @@ _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);
 
@@ -1397,9 +1400,9 @@ _Unpickler_ResizeMemoList(UnpicklerObject *self, Py_ssize_t new_size)
 
 /* 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];
@@ -1408,7 +1411,7 @@ _Unpickler_MemoGet(UnpicklerObject *self, Py_ssize_t 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;
 
@@ -4413,14 +4416,13 @@ 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;
@@ -6843,7 +6845,7 @@ 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;
@@ -6994,8 +6996,7 @@ 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,
@@ -7012,7 +7013,7 @@ Unpickler_set_memo(UnpicklerObject *self, PyObject *obj)
         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];
         }
@@ -7060,8 +7061,7 @@ Unpickler_set_memo(UnpicklerObject *self, PyObject *obj)
 
   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);
path: Modules/_pickle.c