Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb126196

Browse files
pythongh-95778: Correctly pre-check for int-to-str conversion (python#96537)
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. Oops! =)The 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.The justification for the current check. The C code check is:```cmax_str_digits / (3 * PyLong_SHIFT) <= (size_a - 11) / 10```In GitHub markdown 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.<!-- gh-issue-number:pythongh-95778 -->* Issue:pythongh-95778<!-- /gh-issue-number -->Co-authored-by: Gregory P. Smith [Google LLC] <greg@krypto.org>
1 parent6adb89f commitb126196

File tree

4 files changed

+107
-7
lines changed

4 files changed

+107
-7
lines changed

‎Include/internal/pycore_long.h‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -18,9 +18,9 @@ extern "C" {
1818
* everyone's existing deployed numpy test suite passes before
1919
* https://github.com/numpy/numpy/issues/22098 is widely available.
2020
*
21-
* $ python -m timeit -s 's =*"1"*4300' 'int(s)'
21+
* $ python -m timeit -s 's = "1"*4300' 'int(s)'
2222
* 2000 loops, best of 5: 125 usec per loop
23-
* $ python -m timeit -s 's =*"1"*4300; v = int(s)' 'str(v)'
23+
* $ python -m timeit -s 's = "1"*4300; v = int(s)' 'str(v)'
2424
* 1000 loops, best of 5: 311 usec per loop
2525
* (zen2 cloud VM)
2626
*

‎Lib/test/test_int.py‎

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
importsys
2+
importtime
23

34
importunittest
45
fromtestimportsupport
@@ -632,6 +633,87 @@ def test_max_str_digits(self):
632633
withself.assertRaises(ValueError):
633634
str(i)
634635

636+
deftest_denial_of_service_prevented_int_to_str(self):
637+
"""Regression test: ensure we fail before performing O(N**2) work."""
638+
maxdigits=sys.get_int_max_str_digits()
639+
assertmaxdigits<50_000,maxdigits# A test prerequisite.
640+
get_time=time.process_time
641+
ifget_time()<=0:# some platforms like WASM lack process_time()
642+
get_time=time.monotonic
643+
644+
huge_int=int(f'0x{"c"*65_000}',base=16)# 78268 decimal digits.
645+
digits=78_268
646+
withsupport.adjust_int_max_str_digits(digits):
647+
start=get_time()
648+
huge_decimal=str(huge_int)
649+
seconds_to_convert=get_time()-start
650+
self.assertEqual(len(huge_decimal),digits)
651+
# Ensuring that we chose a slow enough conversion to measure.
652+
# It takes 0.1 seconds on a Zen based cloud VM in an opt build.
653+
ifseconds_to_convert<0.005:
654+
raiseunittest.SkipTest('"slow" conversion took only '
655+
f'{seconds_to_convert} seconds.')
656+
657+
# We test with the limit almost at the size needed to check performance.
658+
# The performant limit check is slightly fuzzy, give it a some room.
659+
withsupport.adjust_int_max_str_digits(int(.995*digits)):
660+
withself.assertRaises(ValueError)aserr:
661+
start=get_time()
662+
str(huge_int)
663+
seconds_to_fail_huge=get_time()-start
664+
self.assertIn('conversion',str(err.exception))
665+
self.assertLess(seconds_to_fail_huge,seconds_to_convert/8)
666+
667+
# Now we test that a conversion that would take 30x as long also fails
668+
# in a similarly fast fashion.
669+
extra_huge_int=int(f'0x{"c"*500_000}',base=16)# 602060 digits.
670+
withself.assertRaises(ValueError)aserr:
671+
start=get_time()
672+
# If not limited, 8 seconds said Zen based cloud VM.
673+
str(extra_huge_int)
674+
seconds_to_fail_extra_huge=get_time()-start
675+
self.assertIn('conversion',str(err.exception))
676+
self.assertLess(seconds_to_fail_extra_huge,seconds_to_convert/8)
677+
678+
deftest_denial_of_service_prevented_str_to_int(self):
679+
"""Regression test: ensure we fail before performing O(N**2) work."""
680+
maxdigits=sys.get_int_max_str_digits()
681+
assertmaxdigits<100_000,maxdigits# A test prerequisite.
682+
get_time=time.process_time
683+
ifget_time()<=0:# some platforms like WASM lack process_time()
684+
get_time=time.monotonic
685+
686+
digits=133700
687+
huge='8'*digits
688+
withsupport.adjust_int_max_str_digits(digits):
689+
start=get_time()
690+
int(huge)
691+
seconds_to_convert=get_time()-start
692+
# Ensuring that we chose a slow enough conversion to measure.
693+
# It takes 0.1 seconds on a Zen based cloud VM in an opt build.
694+
ifseconds_to_convert<0.005:
695+
raiseunittest.SkipTest('"slow" conversion took only '
696+
f'{seconds_to_convert} seconds.')
697+
698+
withsupport.adjust_int_max_str_digits(digits-1):
699+
withself.assertRaises(ValueError)aserr:
700+
start=get_time()
701+
int(huge)
702+
seconds_to_fail_huge=get_time()-start
703+
self.assertIn('conversion',str(err.exception))
704+
self.assertLess(seconds_to_fail_huge,seconds_to_convert/8)
705+
706+
# Now we test that a conversion that would take 30x as long also fails
707+
# in a similarly fast fashion.
708+
extra_huge='7'*1_200_000
709+
withself.assertRaises(ValueError)aserr:
710+
start=get_time()
711+
# If not limited, 8 seconds in the Zen based cloud VM.
712+
int(extra_huge)
713+
seconds_to_fail_extra_huge=get_time()-start
714+
self.assertIn('conversion',str(err.exception))
715+
self.assertLess(seconds_to_fail_extra_huge,seconds_to_convert/8)
716+
635717
deftest_power_of_two_bases_unlimited(self):
636718
"""The limit does not apply to power of 2 bases."""
637719
maxdigits=sys.get_int_max_str_digits()

‎Misc/NEWS.d/next/Security/2022-08-07-16-53-38.gh-issue-95778.ch010gps.rst‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,4 +11,4 @@ limitation <int_max_str_digits>` documentation. The default limit is 4300
1111
digits in string form.
1212

1313
Patch by Gregory P. Smith [Google] and Christian Heimes [Red Hat] with feedback
14-
from Victor Stinner, Thomas Wouters, Steve Dower,andNed Deily.
14+
from Victor Stinner, Thomas Wouters, Steve Dower, Ned Deily, and Mark Dickinson.

‎Objects/longobject.c‎

Lines changed: 22 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -36,7 +36,8 @@ medium_value(PyLongObject *x)
3636
#defineIS_SMALL_INT(ival) (-_PY_NSMALLNEGINTS <= (ival) && (ival) < _PY_NSMALLPOSINTS)
3737
#defineIS_SMALL_UINT(ival) ((ival) < _PY_NSMALLPOSINTS)
3838

39-
#define_MAX_STR_DIGITS_ERROR_FMT "Exceeds the limit (%d) for integer string conversion: value has %zd digits"
39+
#define_MAX_STR_DIGITS_ERROR_FMT_TO_INT "Exceeds the limit (%d) for integer string conversion: value has %zd digits"
40+
#define_MAX_STR_DIGITS_ERROR_FMT_TO_STR "Exceeds the limit (%d) for integer string conversion"
4041

4142
staticinlinevoid
4243
_Py_DECREF_INT(PyLongObject*op)
@@ -1758,6 +1759,23 @@ long_to_decimal_string_internal(PyObject *aa,
17581759
size_a=Py_ABS(Py_SIZE(a));
17591760
negative=Py_SIZE(a)<0;
17601761

1762+
/* quick and dirty pre-check for overflowing the decimal digit limit,
1763+
based on the inequality 10/3 >= log2(10)
1764+
1765+
explanation in https://github.com/python/cpython/pull/96537
1766+
*/
1767+
if (size_a >=10*_PY_LONG_MAX_STR_DIGITS_THRESHOLD
1768+
/ (3*PyLong_SHIFT)+2) {
1769+
PyInterpreterState*interp=_PyInterpreterState_GET();
1770+
intmax_str_digits=interp->int_max_str_digits;
1771+
if ((max_str_digits>0)&&
1772+
(max_str_digits / (3*PyLong_SHIFT) <= (size_a-11) /10)) {
1773+
PyErr_Format(PyExc_ValueError,_MAX_STR_DIGITS_ERROR_FMT_TO_STR,
1774+
max_str_digits);
1775+
return-1;
1776+
}
1777+
}
1778+
17611779
/* quick and dirty upper bound for the number of digits
17621780
required to express a in base _PyLong_DECIMAL_BASE:
17631781
@@ -1823,8 +1841,8 @@ long_to_decimal_string_internal(PyObject *aa,
18231841
Py_ssize_tstrlen_nosign=strlen-negative;
18241842
if ((max_str_digits>0)&& (strlen_nosign>max_str_digits)) {
18251843
Py_DECREF(scratch);
1826-
PyErr_Format(PyExc_ValueError,_MAX_STR_DIGITS_ERROR_FMT,
1827-
max_str_digits,strlen_nosign);
1844+
PyErr_Format(PyExc_ValueError,_MAX_STR_DIGITS_ERROR_FMT_TO_STR,
1845+
max_str_digits);
18281846
return-1;
18291847
}
18301848
}
@@ -2498,7 +2516,7 @@ digit beyond the first.
24982516
PyInterpreterState*interp=_PyInterpreterState_GET();
24992517
intmax_str_digits=interp->int_max_str_digits;
25002518
if ((max_str_digits>0)&& (digits>max_str_digits)) {
2501-
PyErr_Format(PyExc_ValueError,_MAX_STR_DIGITS_ERROR_FMT,
2519+
PyErr_Format(PyExc_ValueError,_MAX_STR_DIGITS_ERROR_FMT_TO_INT,
25022520
max_str_digits,digits);
25032521
returnNULL;
25042522
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp