Worst case quadratic complexity in HTMLParser #135462

Activity

1. serhiy-storchaka

   self-assigned this

   on Jun 13, 2025
2. serhiy-storchaka

   added 2 commits that reference this issue on Jun 13, 2025

   pythongh-135462: Fix quadratic complexity in processing special input…

   ...

   77d5125

   pythongh-135462: Fix quadratic complexity in processing special input…

   ...

   c87cb49
3. picnixz

   added

   type-securityA security issueA security issue

   stdlibStandard Library Python modules in the Lib/ directoryStandard Library Python modules in the Lib/ directory

   3.11only security fixesonly security fixes

   3.10 (EOL)end of lifeend of life

   3.9 (EOL)end of lifeend of life

   3.12only security fixesonly security fixes

   3.13only security fixesonly security fixes

   3.14bugs and security fixesbugs and security fixes

   3.15bugs and security fixesbugs and security fixes

   on Jun 13, 2025
4. serhiy-storchaka

   added a commit that references this issue on Jun 13, 2025

   gh-135462: Fix quadratic complexity in processing special input in HT…

   ...

   6eb6c5d
5. miss-islington

   added 2 commits that reference this issue on Jun 13, 2025

   pythongh-135462: Fix quadratic complexity in processing special input…

   ...

   ebd88a8

   pythongh-135462: Fix quadratic complexity in processing special input…

   ...

   9043eda
6. 14 remaining items

   Load more

7. serhiy-storchaka commented on Jul 4, 2025

   

   serhiy-storchaka

   on Jul 4, 2025

   MemberAuthor

   More actions

   Some more information.

   The issue was reported by Jake Howard on behalf of the Django Security team.

   The problem is that when the parser found the beginning of an element (tag, commet, etc), it looked for its end (this has linear complexity), and when it didn't find it, it emitted the beginning as data and started with the next "<". And it could find a new beginning in the middle of an incomplete element, so it continued over and over again, making the total complexity quadratic. There are many ways to trigger this.

   The HTML5 standard specifies the behavior for unexpectedly terminated elements, it does not require backtracking, so the total complexity is linear. #135464 implements this.
8. serhiy-storchaka

   closed this as completedon Jul 4, 2025
9. github-project-automation

   moved this from Todo to Done in html.parser issueson Jul 4, 2025
10. Pranjal095

    added a commit that references this issue on Jul 12, 2025

    pythongh-135462: Fix quadratic complexity in processing special input…

    ...

    5a01b11
11. gentoo-bot

    added a commit that references this issue on Jul 30, 2025

    [3.9] pythongh-135462: Fix quadratic complexity in processing special…

    ...

    44a1053
12. taegyunkim

    added a commit that references this issue on Aug 4, 2025

    pythongh-135462: Fix quadratic complexity in processing special input…

    ...

    72a4079
13. Agent-Hellboy

    added a commit that references this issue on Aug 19, 2025

    pythongh-135462: Fix quadratic complexity in processing special input…

    ...

    4bce1bc
14. netbsd-srcmastr

    added a commit that references this issue on Mar 16, 2026

    CVE-2025-6069 python/cpython#135462

    16c6830
15. jperkin

    added a commit that references this issue on May 14, 2026

    CVE-2025-6069 python/cpython#135462

    a976249
16. mcepl

    added 2 commits that reference this issue on Sep 18, 2026

    [CVE-2025-6069] fix quadratic complexity in processing special input …

    ...

    fd191b9

    [CVE-2025-6069] fix quadratic complexity in processing special input …

    ...

    1aeb539
17. mcepl

    added 2 commits that reference this issue on Oct 1, 2026

    [CVE-2025-6069] fix quadratic complexity in processing special input …

    ...

    ea28e73

    [CVE-2025-6069] fix quadratic complexity in processing special input …

    ...

    f25aa3e
18. github-merge-queue

    added a commit that references this issue on Oct 7, 2026

    fix: pin Python 3.12.15 repo-wide for CVE-2025-6069 (HTMLParser quadr…

    ...

    e05c2c4
19. tsutsui

    added a commit that references this issue on Oct 17, 2026

    CVE-2025-6069 python/cpython#135462

    cafe09b