René's URL Explorer Experiment

Title: gh-95778: Add pre-check for int-to-str conversion by mdickinson · Pull Request #96537 · python/cpython · GitHub

Open Graph Title: gh-95778: Add pre-check for int-to-str conversion by mdickinson · Pull Request #96537 · python/cpython

X Title: gh-95778: Add pre-check for int-to-str conversion by mdickinson · Pull Request #96537 · python/cpython

Description: On current main, converting 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. This PR gives a proof-of-concept quick fix: essentially we catch most values that exceed the threshold up front. Those that slip through will still be on the small side, and will get caught by the existing check. For the record, here's the justification for the current check. The C code check is: max_str_digits / (3 * PyLong_SHIFT) <= (size_a - 11) / 10 In math-speak, writing $M$ for max_str_digits, $L$ for PyLong_SHIFT and $s$ for size_a, that check is: $$\left\lfloor\frac{M}{3L}\right\rfloor \le \left\lfloor\frac{s - 11}{10}\right\rfloor$$ From this it follows that $$\frac{M}{3L} < \frac{s-1}{10}$$ hence that $$\frac{L(s-1)}{M} > \frac{10}{3} > \log_2(10).$$ So $$2^{L(s-1)} > 10^M.$$ But our input integer $a$ satisfies $|a| \ge 2^{L(s-1)}$, so $|a|$ is larger than $10^M$. This shows that we don't accidentally capture anything below the intended limit in the check. I don't think this is ready to merge as-is - there are some details to figure out, and I'll add line-by-line comments for those. Issue: gh-95778

Open Graph Description: On current main, converting 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. ...

X Description: On current main, converting 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. ...

Opengraph URL: https://github.com/python/cpython/pull/96537

X: @github

direct link

Domain: github.com

Links:

Viewport: width=device-width