Title: gh-136063: Fix quadratic complexity in the email header value parser by serhiy-storchaka · Pull Request #152521 · python/cpython · GitHub
Open Graph Title: gh-136063: Fix quadratic complexity in the email header value parser by serhiy-storchaka · Pull Request #152521 · python/cpython
X Title: gh-136063: Fix quadratic complexity in the email header value parser by serhiy-storchaka · Pull Request #152521 · python/cpython
Description: Issue: gh-136063 The email header value parser advanced through the input by repeatedly slicing off the already-parsed prefix (value = value[1:], value = ''.join(remainder)), copying the whole remainder on every step. For headers built from many small tokens (long address lists, encoded-word runs, content-type parameters) this is O(n²) and can be exploited for denial of service. This rewrites the parser to pass an index: every get_*/parse_* now takes (value, pos) and returns the parsed token together with the new position, scanning with value[pos], regex.match(value, pos), and match.end(). No remainder is ever copied. A few things worth calling out for review: Error messages now interpolate at most a 60-character fragment of the unparsed input (_tail()). Several of these HeaderParseErrors are raised and caught as ordinary control flow, so interpolating the full remainder was itself O(n) and reintroduced the quadratic behaviour. No test asserts on the message text. EncodedWord.cte now holds just the encoded word rather than the entire remaining header (the old code assigned the whole remainder to .cte). An obsolete local-part is now re-parsed from the original source text instead of from str(local_part) + remaining (the decoded rendering of the already-parsed tokens). This is both a quadratic spot and incorrect when a token rendered back to text differs from the source — e.g. an RFC 2047 encoded-word decoding to a bare special such as @, which RFC 2047 does not permit in an addr-spec anyway. Such an encoded-word is no longer decoded and the address is reported as invalid. See gh-152519 for the underlying correctness bug. All test_email, test_smtplib and test_logging tests pass. Non-debug benchmarks show the previously quadratic headers now scale linearly (e.g. parse_content_type ~8× faster at 64k, get_address_list ~5.6× faster at 72k).
Open Graph Description: Issue: gh-136063 The email header value parser advanced through the input by repeatedly slicing off the already-parsed prefix (value = value[1:], value = ''.join(remainder)), copying the ...
X Description: Issue: gh-136063 The email header value parser advanced through the input by repeatedly slicing off the already-parsed prefix (value = value[1:], value = ''.join(remainder)), copy...
Opengraph URL: https://github.com/python/cpython/pull/152521
X: @github
Domain: github.com
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /:user_id/:repository/pull/:id/files(.:format) |
| route-controller | pull_requests |
| route-action | files |
| fetch-nonce | v2:04b01010-417d-ea8d-28cb-af5ab73118ad |
| current-catalog-service-hash | ae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b |
| request-id | 8ABC:24645:1C02407:24D5CC7:6B0220A7 |
| html-safe-nonce | faa22360cae654cd82e479713ac8621cbee63b39237a2523b9aa61479da9743a |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI4QUJDOjI0NjQ1OjFDMDI0MDc6MjRENUNDNzo2QjAyMjBBNyIsInZpc2l0b3JfaWQiOiI5MTc3ODcyODEyOTczNjI5NjA3IiwicmVnaW9uX2VkZ2UiOiJpYWQiLCJyZWdpb25fcmVuZGVyIjoiaWFkIn0= |
| visitor-hmac | 2c32b600c6906d58cf6ab91dae2dabe8d885fb235acf95ee643158b39fd61089 |
| hovercard-subject-tag | pull_request:3951590299 |
| github-keyboard-shortcuts | repository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/python/cpython/pull/152521/files |
| twitter:image | https://avatars.githubusercontent.com/u/3659035?s=400&v=4 |
| twitter:card | summary_large_image |
| og:image | https://avatars.githubusercontent.com/u/3659035?s=400&v=4 |
| og:image:alt | Issue: gh-136063 The email header value parser advanced through the input by repeatedly slicing off the already-parsed prefix (value = value[1:], value = ''.join(remainder)), copying the ... |
| og:site_name | GitHub |
| og:type | object |
| hostname | github.com |
| expected-hostname | github.com |
| None | 87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456 |
| turbo-cache-control | no-preview |
| diff-view | unified |
| go-import | github.com/python/cpython git https://github.com/python/cpython.git |
| octolytics-dimension-user_id | 1525981 |
| octolytics-dimension-user_login | python |
| octolytics-dimension-repository_id | 81598961 |
| octolytics-dimension-repository_nwo | python/cpython |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 81598961 |
| octolytics-dimension-repository_network_root_nwo | python/cpython |
| turbo-body-classes | logged-out env-production page-responsive full-width |
| disable-turbo | true |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 423dbb54c5e7bfecc838eb387c1435eb3d0e760d |
| ui-target | canary-2 |
| theme-color | #1e2327 |
| color-scheme | light dark |
Links:
Viewport: width=device-width