A Series of Potential DoS Risk Points in the CPython Standard Library

[kexinoh]

Bug report

Bug description:

Approximately six months ago, our automated scanning program detected several issues and an issue(#134873) was filed. Recently, after improving the scanner and re-running it against CPython, additional locations were found that may be susceptible to algorithmic complexity attacks. Although each finding has been validated as carefully as possible, some false positives may still exist.
Please note that these findings do not necessarily imply an exploitable vulnerability (and are unlikely to represent a straightforward remote attack vector). After discussion with PSRC, these points are being disclosed in this issue in order to leverage community review and contributions to assess impact and, where appropriate, implement hardening or fixes.
Incremental updates will be posted over the coming weeks.

We’ve updated the items related to the email module in #136063.

1. _c3_mro（EXP）
   

   cpython/Lib/functools.py

   Lines 780 to 823 in e66597d

   	def _c3_mro(cls, abcs=None):
   	"""Computes the method resolution order using extended C3 linearization.
   	If no *abcs* are given, the algorithm works exactly like the built-in C3
   	linearization used for method resolution.
   	If given, *abcs* is a list of abstract base classes that should be inserted
   	into the resulting MRO. Unrelated ABCs are ignored and don't end up in the
   	result. The algorithm inserts ABCs where their functionality is introduced,
   	i.e. issubclass(cls, abc) returns True for the class itself but returns
   	False for all its direct base classes. Implicit ABCs for a given class
   	(either registered or inferred from the presence of a special method like
   	__len__) are inserted directly after the last ABC explicitly listed in the
   	MRO of said class. If two implicit ABCs end up next to each other in the
   	resulting MRO, their ordering depends on the order of types in *abcs*.
   	"""
   	for i, base in enumerate(reversed(cls.__bases__)):
   	if hasattr(base, '__abstractmethods__'):
   	boundary = len(cls.__bases__) - i
   	break # Bases up to the last explicit ABC are considered first.
   	else:
   	boundary = 0
   	abcs = list(abcs) if abcs else []
   	explicit_bases = list(cls.__bases__[:boundary])
   	abstract_bases = []
   	other_bases = list(cls.__bases__[boundary:])
   	for base in abcs:
   	if issubclass(cls, base) and not any(
   	issubclass(b, base) for b in cls.__bases__
   	):
   	# If *cls* is the class that introduces behaviour described by
   	# an ABC *base*, insert said ABC to its MRO.
   	abstract_bases.append(base)
   	for base in abstract_bases:
   	abcs.remove(base)
   	explicit_c3_mros = [_c3_mro(base, abcs=abcs) for base in explicit_bases]
   	abstract_c3_mros = [_c3_mro(base, abcs=abcs) for base in abstract_bases]
   	other_c3_mros = [_c3_mro(base, abcs=abcs) for base in other_bases]
   	return _c3_merge(
   	[[cls]] +
   	explicit_c3_mros + abstract_c3_mros + other_c3_mros +
   	[explicit_bases] + [abstract_bases] + [other_bases]
   	)

2.allmethods（Exp）

cpython/Lib/pydoc.py

Line 211 in e66597d

def allmethods(cl):

3.FragmentBuilderNS._getNSattrs (Poly）

cpython/Lib/xml/dom/expatbuilder.py

Line 818 in e66597d

def _getNSattrs(self):

)

4. __dict_replace（EXP）

   cpython/Lib/xml/sax/saxutils.py

   Line 12 in e66597d

   def __dict_replace(s, d):

5.punycode_decode（Poly)

cpython/Lib/encodings/punycode.py

Line 188 in e66597d

def punycode_decode(text, errors):

.

CPython versions tested on:

CPython main branch

Operating systems tested on:

Linux

[kexinoh]

cc @picnixz @serhiy-storchaka

[VanshAgarwal24036]

Before starting work, I’d like to confirm that the following minimal approach aligns with expectations for this issue:

• Treat each listed location independently and first determine whether the reported worst-case complexity is actually reachable with attacker-controlled input, or whether it is effectively bounded by upstream constraints.
• For cases that appear to be false positives or practically unreachable, resolve them via explicit documentation or comments explaining why they are safe.
• For cases where untrusted input can realistically trigger pathological behavior, apply small, localized hardening (e.g. simple size / depth limits or early exits), avoiding larger algorithmic refactors unless strictly necessary.

My plan is to start with a helper function, perhaps one that is narrowly scoped, such as an email or XML function, and document the scope or perhaps provide a minimal guard with a regression test.

Please let me know if this approach is acceptable, or if there are preferred starting points or additional expectations (e.g. proof-of-exploit vs. analysis-only resolution).

[picnixz]

I would prefer that this task is achieved by core developers. For email, this will be part of a larger refactor. For the rest I will have a look at it when I am back home (in a few days).

[kexinoh]

OK — then I’ll move all the email-related issues to the end of the issue at #136063, so it’s easier for you to handle all the email items in a unified way.

For the remaining items, I’m speeding up verification, and then I’ll do another detailed categorization pass.

What do you think?

[picnixz]

Up to you! I won't have time to look at them one by one until the end of the week, but the more detail there are, the easier it will be for us to know what we could do. There might also be some cases that are not worth considering if the attack surface is very small.

cc @sethmlarson

[kexinoh]

In fact, for each DoS point we have a corresponding PoC and some discussion. But I’m not sure whether putting them directly in the issue could introduce potential security risks. Maybe I can email you instead, including the specific DoS root causes and PoC examples.
My email is findmykexin@gmail.com.