)]}'
{
  "commit": "eace09e63ed7978dbdfeb1ae537fac505e6b5b0e",
  "tree": "28c33c23faec72038fd65cd37d476e6b8ee3de2b",
  "parents": [
    "4dea99f18eeef15a6d69236146793c801d12c329"
  ],
  "author": {
    "name": "Gregory P. Smith",
    "email": "greg@krypto.org",
    "time": "Sun Sep 04 09:54:56 2022 -0700"
  },
  "committer": {
    "name": "GitHub",
    "email": "noreply@github.com",
    "time": "Sun Sep 04 09:54:56 2022 -0700"
  },
  "message": "[3.10] gh-95778: Correctly pre-check for int-to-str conversion (GH-96537) (#96563)\n\nConverting a large enough `int` to a decimal string raises `ValueError` as expected. However, the raise comes _after_ the quadratic-time base-conversion algorithm has run to completion. For effective DOS prevention, we need some kind of check before entering the quadratic-time loop. Oops! \u003d)\r\n\r\nThe quick fix: essentially we catch _most_ values that exceed the threshold up front. Those that slip through will still be on the small side (read: sufficiently fast), and will get caught by the existing check so that the limit remains exact.\r\n\r\nThe justification for the current check. The C code check is:\r\n```c\r\nmax_str_digits / (3 * PyLong_SHIFT) \u003c\u003d (size_a - 11) / 10\r\n```\r\n\r\nIn GitHub markdown math-speak, writing $M$ for `max_str_digits`, $L$ for `PyLong_SHIFT` and $s$ for `size_a`, that check is:\r\n$$\\left\\lfloor\\frac{M}{3L}\\right\\rfloor \\le \\left\\lfloor\\frac{s - 11}{10}\\right\\rfloor$$\r\n\r\nFrom this it follows that\r\n$$\\frac{M}{3L} \u003c \\frac{s-1}{10}$$\r\nhence that\r\n$$\\frac{L(s-1)}{M} \u003e \\frac{10}{3} \u003e \\log_2(10).$$\r\nSo\r\n$$2^{L(s-1)} \u003e 10^M.$$\r\nBut our input integer $a$ satisfies $|a| \\ge 2^{L(s-1)}$, so $|a|$ is larger than $10^M$. This shows that we don\u0027t accidentally capture anything _below_ the intended limit in the check.\r\n\r\n\u003c!-- gh-issue-number: gh-95778 --\u003e\r\n* Issue: gh-95778\r\n\u003c!-- /gh-issue-number --\u003e\r\n\r\nCo-authored-by: Gregory P. Smith [Google LLC] \u003cgreg@krypto.org\u003e\r\n(cherry picked from commit b126196838bbaf5f4d35120e0e6bcde435b0b480)\r\n\r\nCo-authored-by: Mark Dickinson \u003cdickinsm@gmail.com\u003e",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "ee9a5923739095ea8b45d3a39d83af595c06edda",
      "old_mode": 33188,
      "old_path": "Include/internal/pycore_long.h",
      "new_id": "90069f8ed75ddd1d2632271573a3e185249ce0b2",
      "new_mode": 33188,
      "new_path": "Include/internal/pycore_long.h"
    },
    {
      "type": "modify",
      "old_id": "2f678ed90973b06781d77e8449f95dbdf38b1ea0",
      "old_mode": 33188,
      "old_path": "Lib/test/test_int.py",
      "new_id": "a578ca841f05a5d1ca1d410471126343783a57d7",
      "new_mode": 33188,
      "new_path": "Lib/test/test_int.py"
    },
    {
      "type": "modify",
      "old_id": "ea3b85d632e0837bf202f8babe6217626a1b9dd4",
      "old_mode": 33188,
      "old_path": "Misc/NEWS.d/next/Security/2022-08-07-16-53-38.gh-issue-95778.ch010gps.rst",
      "new_id": "8eb8a34884dcedd80033560990fe83d41c493f35",
      "new_mode": 33188,
      "new_path": "Misc/NEWS.d/next/Security/2022-08-07-16-53-38.gh-issue-95778.ch010gps.rst"
    },
    {
      "type": "modify",
      "old_id": "780ea819bd8de96fd1808c38ffec352261a8018f",
      "old_mode": 33188,
      "old_path": "Objects/longobject.c",
      "new_id": "aea5edc99064ec340ba01c1ea0ff2d605b0f5828",
      "new_mode": 33188,
      "new_path": "Objects/longobject.c"
    }
  ]
}