Skip to content

DoS: Arithmetic Operation Causes 100% CPU Usage and Unbounded Virtual Memory Growth #135186

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
sha0coder opened this issue Jun 5, 2025 · 13 comments
Assignees
Labels
interpreter-core (Objects, Python, Grammar, and Parser dirs) type-bug An unexpected behavior, bug, or error

Comments

@sha0coder
Copy link

sha0coder commented Jun 5, 2025

Bug report

Bug description:

There is a bug in the PyLongObject implementation during x_mul operations with certain values, triggering a Denial of Service (DoS) by causing 100% CPU usage and unbounded virtual memory growth.

 static PyLongObject *  x_mul(PyLongObject *a, PyLongObject *b)

First I triggered allocation errors in python3.10, and I also verified it with git version.

# dmesg

[1094342.309776] __vm_enough_memory: pid: 1137590, comm: python3, bytes: 156909473792 not enough memory for the allocation
[1094342.309781] __vm_enough_memory: pid: 1137590, comm: python3, bytes: 156909486080 not enough memory for the allocation
[1094342.309784] __vm_enough_memory: pid: 1137590, comm: python3, bytes: 156909961216 not enough memory for the allocation

Reproducing the issue is simple, here I triggered it in latest git verision main branch:

~/s/cpython ❯❯❯ ./python                                                                                                                                            
Python 3.15.0a0 (heads/main:9258f3da917, Jun  5 2025, 16:55:39) [GCC 11.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.

>>> a = 241; b = 137; a = b << a; a = b**a;

With other operations I got a more convenient exceptions like:

OverflowError: too many digits in integer

But with this operation, the CPU starts consuming 100% and virtual memory keeps increasing.

/home/sha0/soft/cpython/Objects/longobject.c:3875

   3875             while (pa < paend) {
   3876                 carry += *pz + *pa++ * f;
   3877                 *pz++ = (digit)(carry & PyLong_MASK);
   3878                 carry >>= PyLong_SHIFT;
   3879                 assert(carry <= (PyLong_MASK << 1));
   3880             }
pwndbg> x/x pa
0x555555e089a0:	0x18f00998
pwndbg> x/x paend
0x555555e089c0:	0x00000001

paend pointer is expected that points after pa pointer.
And this causes a brk() syscall loop:

brk(0x5d96a1b3c000)                     = 0x5d96a1b3c000
brk(0x5d96a1b61000)                     = 0x5d96a1b61000
brk(0x5d96a1b85000)                     = 0x5d96a1b85000
brk(0x5d96a1ba9000)                     = 0x5d96a1ba9000
brk(0x5d96a1bca000)                     = 0x5d96a1bca000
brk(0x5d96a199f000)                     = 0x5d96a199f000
brk(0x5d96a19e0000)                     = 0x5d96a19e0000
brk(0x5d96a1a61000)                     = 0x5d96a1a61000
brk(0x5d96a1aa2000)                     = 0x5d96a1aa2000
brk(0x5d96a1ac7000)                     = 0x5d96a1ac7000
brk(0x5d96a1af3000)                     = 0x5d96a1af3000
brk(0x5d96a1b18000)                     = 0x5d96a1b18000
brk(0x5d96a189b000)                     = 0x5d96a189b000
brk(0x5d96a191d000)                     = 0x5d96a191d000
brk(0x5d96a195e000)                     = 0x5d96a195e000
brk(0x5d96a1982000)                     = 0x5d96a1982000
brk(0x5d96a19a3000)                     = 0x5d96a19a3000
brk(0x5d96a19cf000)                     = 0x5d96a19cf000
brk(0x5d96a19f0000)                     = 0x5d96a19f0000
brk(0x5d96a1a14000)                     = 0x5d96a1a14000
brk(0x5d96a1a35000)                     = 0x5d96a1a35000
brk(0x5d96a1a61000)                     = 0x5d96a1a61000
brk(0x5d96a1613000)                     = 0x5d96a1613000
brk(0x5d96a1695000)                     = 0x5d96a1695000
brk(0x5d96a1716000)                     = 0x5d96a1716000
...

CPython versions tested on:

CPython main branch

Operating systems tested on:

Linux

@sha0coder sha0coder added the type-bug An unexpected behavior, bug, or error label Jun 5, 2025
@sha0coder
Copy link
Author

The problem is not that loop itself, is comparing the pointer not the values.

@skirpichev skirpichev self-assigned this Jun 5, 2025
@skirpichev skirpichev added the pending The issue will be closed if no feedback is provided label Jun 5, 2025
@ZeroIntensity ZeroIntensity added interpreter-core (Objects, Python, Grammar, and Parser dirs) 3.13 bugs and security fixes 3.14 bugs and security fixes 3.15 new features, bugs and security fixes pending The issue will be closed if no feedback is provided and removed pending The issue will be closed if no feedback is provided labels Jun 5, 2025
@skirpichev
Copy link
Contributor

skirpichev commented Jun 5, 2025

I doubt it's a bug.

You tried something like 137 ** 484116095749277306305823515203559673336730587743919594525320099154177818624.

What you expect, computing enormous power with arbitrary precision arithmetic?

@ZeroIntensity, could you argue your decisions?

@sha0coder
Copy link
Author

math.h pow() wouldnt do this ;) but being objects is logic, but maybe an exception

@skirpichev
Copy link
Contributor

math.h pow() wouldnt do this ;)

math.h is not for arbitrary precision integer arithmetic.

@ZeroIntensity
Copy link
Member

@ZeroIntensity, could you argue your decisions?

I didn't mean to remove pending, GitHub did it automatically when I applied other labels. I agree with you that using massive exponents will take... very long, to say the least.

math.h pow() wouldnt do this ;) but being objects is logic, but maybe an exception

What exception do you expect?

@sha0coder
Copy link
Author

sha0coder commented Jun 5, 2025

    a << a
    ~~^^~~
OverflowError: too many digits in integer

but with pow there is no error control and is keep allocating all the time

@ZeroIntensity
Copy link
Member

OverflowError comes up when you try to convert a very large Python int to a C integer. It doesn't come up with Python-to-Python calls.

@sha0coder
Copy link
Author

sha0coder commented Jun 5, 2025

>>> a
484116095749277306305823515203559673336730587743919594525320099154177818624
>>> b
137
>>> a**b
Traceback (most recent call last):
  File "<python-input-7>", line 1, in <module>
    a**b
    ~^^~
ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit
>>>

in this way there is a ValueError, here there is a limit, in the other case not

@ZeroIntensity
Copy link
Member

Because it's a much smaller operation. pow(a, b) is not the same complexity as pow(b, a). Multiplying 484116095749277306305823515203559673336730587743919594525320099154177818624 only 137 times is a lot faster than the other way around.

@sha0coder
Copy link
Author

sha0coder commented Jun 5, 2025

sure, well a**b has limits of digits but b**a not, well I just notify, you know better if it worth to check it.

regards.

@skirpichev
Copy link
Contributor

OverflowError: too many digits in integer

But your problem is not the shift - it's power: b**a (I corrected my message above).

ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

This message coming from limits in binary->decimal conversion of the output, not from computing of the power.

in this way there is a ValueError, here there is a limit, in the other case not

It's because limiting "other cases" will ruin sane computations of people.

It's easy to estimate size of your power:

>>> a = 241; b = 137; a = b << a
>>> a*math.log2(b)  # bit length
3.4362715795059602e+75

Wikipedia knows something like the quettabyte - it's 10**30 bytes...

sure, well ab has limits of digits but ba not

No. Neither power has "digits limit", except from coming from hardware limitations (available memory, etc).

You can read about integer conversion string limitations here:
https://docs.python.org/3/library/stdtypes.html#int-max-str-digits

(BTW, I suspect this odd limit will produce new issues like that.)

@sha0coder
Copy link
Author

The ValueError needs first to compute the result to trigger the exception, and in this case is not computable.

Languages like nodejs or ruby answers Infitity directly, but is other philosopy.

But well, It makes sense not implementing power limits and don't limiting other more powerful hardwares, I close the ticket.

thanks.

@skirpichev
Copy link
Contributor

Languages like nodejs or ruby answers Infitity directly

Are you sure? Are you using big integers on whose languages or trying to compute floating-point powers?

but is other philosopy

Or reading of the documentation;-)

@skirpichev skirpichev removed pending The issue will be closed if no feedback is provided 3.13 bugs and security fixes 3.14 bugs and security fixes 3.15 new features, bugs and security fixes labels Jun 5, 2025
@skirpichev skirpichev closed this as not planned Won't fix, can't repro, duplicate, stale Jun 5, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
interpreter-core (Objects, Python, Grammar, and Parser dirs) type-bug An unexpected behavior, bug, or error
Projects
None yet
Development

No branches or pull requests

3 participants