Merge from 3.1: Issue #13703: add a way to randomize the hash values of basic types (str, bytes, datetime)

in order to make algorithmic complexity attacks on (e.g.) web apps much more complicated.

The environment variable PYTHONHASHSEED and the new command line flag -R control this
behavior.

1 files changed, 126 insertions, 17 deletions

diff --git a/Objects/obmalloc.c b/Objects/obmalloc.c
index af12f41ed3..3916262120 100644
--- a/Objects/obmalloc.c
+++ b/Objects/obmalloc.c
@@ -2,6 +2,21 @@
 
 #ifdef WITH_PYMALLOC
 
+#ifdef WITH_VALGRIND
+#include <valgrind/valgrind.h>
+
+/* If we're using GCC, use __builtin_expect() to reduce overhead of
+   the valgrind checks */
+#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__)
+#  define UNLIKELY(value) __builtin_expect((value), 0)
+#else
+#  define UNLIKELY(value) (value)
+#endif
+
+/* -1 indicates that we haven't checked that we're running on valgrind yet. */
+static int running_on_valgrind = -1;
+#endif
+
 /* An object allocator for Python.
 
    Here is an introduction to the layers of the Python memory architecture,
@@ -736,6 +751,13 @@ PyObject_Malloc(size_t nbytes)
     poolp next;
     uint size;
 
+#ifdef WITH_VALGRIND
+    if (UNLIKELY(running_on_valgrind == -1))
+        running_on_valgrind = RUNNING_ON_VALGRIND;
+    if (UNLIKELY(running_on_valgrind))
+        goto redirect;
+#endif
+
     /*
      * Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes.
      * Most python internals blindly use a signed Py_ssize_t to track
@@ -938,6 +960,11 @@ PyObject_Free(void *p)
     if (p == NULL)      /* free(NULL) has no effect */
         return;
 
+#ifdef WITH_VALGRIND
+    if (UNLIKELY(running_on_valgrind > 0))
+        goto redirect;
+#endif
+
     pool = POOL_ADDR(p);
     if (Py_ADDRESS_IN_RANGE(p, pool)) {
         /* We allocated this address. */
@@ -1132,6 +1159,9 @@ PyObject_Free(void *p)
         return;
     }
 
+#ifdef WITH_VALGRIND
+redirect:
+#endif
     /* We didn't allocate this address. */
     free(p);
 }
@@ -1164,6 +1194,12 @@ PyObject_Realloc(void *p, size_t nbytes)
     if (nbytes > PY_SSIZE_T_MAX)
         return NULL;
 
+#ifdef WITH_VALGRIND
+    /* Treat running_on_valgrind == -1 the same as 0 */
+    if (UNLIKELY(running_on_valgrind > 0))
+        goto redirect;
+#endif
+
     pool = POOL_ADDR(p);
     if (Py_ADDRESS_IN_RANGE(p, pool)) {
         /* We're in charge of this block */
@@ -1191,6 +1227,9 @@ PyObject_Realloc(void *p, size_t nbytes)
         }
         return bp;
     }
+#ifdef WITH_VALGRIND
+ redirect:
+#endif
     /* We're not managing this block.  If nbytes <=
      * SMALL_REQUEST_THRESHOLD, it's tempting to try to take over this
      * block.  However, if we do, we need to copy the valid data from
@@ -1255,6 +1294,10 @@ PyObject_Free(void *p)
 #define DEADBYTE       0xDB    /* dead (newly freed) memory */
 #define FORBIDDENBYTE  0xFB    /* untouchable bytes at each end of a block */
 
+/* We tag each block with an API ID in order to tag API violations */
+#define _PYMALLOC_MEM_ID 'm'   /* the PyMem_Malloc() API */
+#define _PYMALLOC_OBJ_ID 'o'   /* The PyObject_Malloc() API */
+
 static size_t serialno = 0;     /* incremented on each debug {m,re}alloc */
 
 /* serialno is always incremented via calling this routine.  The point is
@@ -1345,9 +1388,50 @@ p[2*S+n+S: 2*S+n+2*S]
     instant at which this block was passed out.
 */
 
+/* debug replacements for the PyMem_* memory API */
+void *
+_PyMem_DebugMalloc(size_t nbytes)
+{
+    return _PyObject_DebugMallocApi(_PYMALLOC_MEM_ID, nbytes);
+}
+void *
+_PyMem_DebugRealloc(void *p, size_t nbytes)
+{
+    return _PyObject_DebugReallocApi(_PYMALLOC_MEM_ID, p, nbytes);
+}
+void
+_PyMem_DebugFree(void *p)
+{
+    _PyObject_DebugFreeApi(_PYMALLOC_MEM_ID, p);
+}
+
+/* debug replacements for the PyObject_* memory API */
 void *
 _PyObject_DebugMalloc(size_t nbytes)
 {
+    return _PyObject_DebugMallocApi(_PYMALLOC_OBJ_ID, nbytes);
+}
+void *
+_PyObject_DebugRealloc(void *p, size_t nbytes)
+{
+    return _PyObject_DebugReallocApi(_PYMALLOC_OBJ_ID, p, nbytes);
+}
+void
+_PyObject_DebugFree(void *p)
+{
+    _PyObject_DebugFreeApi(_PYMALLOC_OBJ_ID, p);
+}
+void
+_PyObject_DebugCheckAddress(const void *p)
+{
+    _PyObject_DebugCheckAddressApi(_PYMALLOC_OBJ_ID, p);
+}
+
+
+/* generic debug memory api, with an "id" to identify the API in use */
+void *
+_PyObject_DebugMallocApi(char id, size_t nbytes)
+{
     uchar *p;           /* base address of malloc'ed block */
     uchar *tail;        /* p + 2*SST + nbytes == pointer to tail pad bytes */
     size_t total;       /* nbytes + 4*SST */
@@ -1362,12 +1446,15 @@ _PyObject_DebugMalloc(size_t nbytes)
     if (p == NULL)
         return NULL;
 
+    /* at p, write size (SST bytes), id (1 byte), pad (SST-1 bytes) */
     write_size_t(p, nbytes);
-    memset(p + SST, FORBIDDENBYTE, SST);
+    p[SST] = (uchar)id;
+    memset(p + SST + 1 , FORBIDDENBYTE, SST-1);
 
     if (nbytes > 0)
         memset(p + 2*SST, CLEANBYTE, nbytes);
 
+    /* at tail, write pad (SST bytes) and serialno (SST bytes) */
     tail = p + 2*SST + nbytes;
     memset(tail, FORBIDDENBYTE, SST);
     write_size_t(tail + SST, serialno);
@@ -1376,27 +1463,28 @@ _PyObject_DebugMalloc(size_t nbytes)
 }
 
 /* The debug free first checks the 2*SST bytes on each end for sanity (in
-   particular, that the FORBIDDENBYTEs are still intact).
+   particular, that the FORBIDDENBYTEs with the api ID are still intact).
    Then fills the original bytes with DEADBYTE.
    Then calls the underlying free.
 */
 void
-_PyObject_DebugFree(void *p)
+_PyObject_DebugFreeApi(char api, void *p)
 {
     uchar *q = (uchar *)p - 2*SST;  /* address returned from malloc */
     size_t nbytes;
 
     if (p == NULL)
         return;
-    _PyObject_DebugCheckAddress(p);
+    _PyObject_DebugCheckAddressApi(api, p);
     nbytes = read_size_t(q);
+    nbytes += 4*SST;
     if (nbytes > 0)
         memset(q, DEADBYTE, nbytes);
     PyObject_Free(q);
 }
 
 void *
-_PyObject_DebugRealloc(void *p, size_t nbytes)
+_PyObject_DebugReallocApi(char api, void *p, size_t nbytes)
 {
     uchar *q = (uchar *)p;
     uchar *tail;
@@ -1405,9 +1493,9 @@ _PyObject_DebugRealloc(void *p, size_t nbytes)
     int i;
 
     if (p == NULL)
-        return _PyObject_DebugMalloc(nbytes);
+        return _PyObject_DebugMallocApi(api, nbytes);
 
-    _PyObject_DebugCheckAddress(p);
+    _PyObject_DebugCheckAddressApi(api, p);
     bumpserialno();
     original_nbytes = read_size_t(q - 2*SST);
     total = nbytes + 4*SST;
@@ -1417,16 +1505,20 @@ _PyObject_DebugRealloc(void *p, size_t nbytes)
 
     if (nbytes < original_nbytes) {
         /* shrinking:  mark old extra memory dead */
-        memset(q + nbytes, DEADBYTE, original_nbytes - nbytes);
+        memset(q + nbytes, DEADBYTE, original_nbytes - nbytes + 2*SST);
     }
 
-    /* Resize and add decorations. */
+    /* Resize and add decorations. We may get a new pointer here, in which
+     * case we didn't get the chance to mark the old memory with DEADBYTE,
+     * but we live with that.
+     */
     q = (uchar *)PyObject_Realloc(q - 2*SST, total);
     if (q == NULL)
         return NULL;
 
     write_size_t(q, nbytes);
-    for (i = 0; i < SST; ++i)
+    assert(q[SST] == (uchar)api);
+    for (i = 1; i < SST; ++i)
         assert(q[SST + i] == FORBIDDENBYTE);
     q += 2*SST;
     tail = q + nbytes;
@@ -1445,26 +1537,38 @@ _PyObject_DebugRealloc(void *p, size_t nbytes)
 /* Check the forbidden bytes on both ends of the memory allocated for p.
  * If anything is wrong, print info to stderr via _PyObject_DebugDumpAddress,
  * and call Py_FatalError to kill the program.
+ * The API id, is also checked.
  */
  void
-_PyObject_DebugCheckAddress(const void *p)
+_PyObject_DebugCheckAddressApi(char api, const void *p)
 {
     const uchar *q = (const uchar *)p;
+    char msgbuf[64];
     char *msg;
     size_t nbytes;
     const uchar *tail;
     int i;
+    char id;
 
     if (p == NULL) {
         msg = "didn't expect a NULL pointer";
         goto error;
     }
 
+    /* Check the API id */
+    id = (char)q[-SST];
+    if (id != api) {
+        msg = msgbuf;
+        snprintf(msg, sizeof(msgbuf), "bad ID: Allocated using API '%c', verified using API '%c'", id, api);
+        msgbuf[sizeof(msgbuf)-1] = 0;
+        goto error;
+    }
+
     /* Check the stuff at the start of p first:  if there's underwrite
      * corruption, the number-of-bytes field may be nuts, and checking
      * the tail could lead to a segfault then.
      */
-    for (i = SST; i >= 1; --i) {
+    for (i = SST-1; i >= 1; --i) {
         if (*(q-i) != FORBIDDENBYTE) {
             msg = "bad leading pad byte";
             goto error;
@@ -1496,19 +1600,24 @@ _PyObject_DebugDumpAddress(const void *p)
     size_t nbytes, serial;
     int i;
     int ok;
+    char id;
 
-    fprintf(stderr, "Debug memory block at address p=%p:\n", p);
-    if (p == NULL)
+    fprintf(stderr, "Debug memory block at address p=%p:", p);
+    if (p == NULL) {
+        fprintf(stderr, "\n");
         return;
+    }
+    id = (char)q[-SST];
+    fprintf(stderr, " API '%c'\n", id);
 
     nbytes = read_size_t(q - 2*SST);
     fprintf(stderr, "    %" PY_FORMAT_SIZE_T "u bytes originally "
                     "requested\n", nbytes);
 
     /* In case this is nuts, check the leading pad bytes first. */
-    fprintf(stderr, "    The %d pad bytes at p-%d are ", SST, SST);
+    fprintf(stderr, "    The %d pad bytes at p-%d are ", SST-1, SST-1);
     ok = 1;
-    for (i = 1; i <= SST; ++i) {
+    for (i = 1; i <= SST-1; ++i) {
         if (*(q-i) != FORBIDDENBYTE) {
             ok = 0;
             break;
@@ -1519,7 +1628,7 @@ _PyObject_DebugDumpAddress(const void *p)
     else {
         fprintf(stderr, "not all FORBIDDENBYTE (0x%02x):\n",
             FORBIDDENBYTE);
-        for (i = SST; i >= 1; --i) {
+        for (i = SST-1; i >= 1; --i) {
             const uchar byte = *(q-i);
             fprintf(stderr, "        at p-%d: 0x%02x", i, byte);
             if (byte != FORBIDDENBYTE)