Python 3.5.6 removes overlapping regular expression matches
Python 3.5.6 fixes denial-of-service risks in difflib and poplib by changing their regular expressions. The patch makes a useful distinction between limiting input size and limiting the work spent matching it.
A short regular expression can leave its matcher many ways to divide the same input. When those alternatives fail late, matching can consume disproportionate work. Python 3.5.6 repairs this problem in two standard-library modules, difflib and poplib, without asking their callers to adopt a new API.
The August 2 release continues the 3.5 branch's source-only security maintenance. Its included release candidate notes identify the regular-expression changes as fixes for CVE-2018-1060 and CVE-2018-1061, with a patch by Jamie Davis. They also include a minimal buffer-overrun repair for os.symlink on Windows.
I depend on Python's library ecosystem more than I enjoy the language's maintenance arrangements. These fixes concern a reason that dependency deserves scrutiny. Standard-library code can spend excessive time on data even when an application has delegated the parsing to an established module.
Optional syntax can create overlapping matches
The difflib change is visible by comparing the 3.5.5 source with the 3.5.6 source. The IS_LINE_JUNK helper changes its default matching expression.
# Previous expression
r"\s*#?\s*$"
# Python 3.5.6 expression
r"\s*(?:#\s*)?$"
Both expressions concern lines containing whitespace and an optional comment marker. The important structural difference occurs when the marker is absent. In the old pattern, two whitespace repetitions remain adjacent because #? can match nothing. The same whitespace can then be apportioned between the repetitions in many ways while the matcher tries to satisfy the rest of the pattern.
The new pattern groups the marker with the whitespace after it. If that group is absent, the expression has only the leading whitespace repetition. If the group participates, it must include the marker, which separates the two whitespace runs. This gives the matcher a boundary that the optional marker alone did not provide.
That explanation is an analysis of the two tagged expressions, rather than a claim of a measured speedup. The release notes establish the security issue and its correction. The source comparison shows how this particular correction removes overlap in the pattern's structure. No timing result is needed to identify that structural difference.
The general lesson for this helper concerns rejection as well as acceptance. A pattern can describe a simple set of valid strings while doing expensive work on strings outside that set. Reviewing only a few successful examples would examine the accepted language without examining the paths the matcher takes when a final condition fails.
A protocol delimiter also supplies a boundary
The poplib change applies the same concern to a different kind of input. Its timestamp pattern participates in APOP authentication, matching the server's initial greeting before constructing the authentication digest. The 3.5.5 implementation and 3.5.6 implementation use different prefixes before the captured timestamp.
# Previous expression
br"\+OK.*(<[^>]+>)"
# Python 3.5.6 expression
br"\+OK.[^<]*(<.*>)"
The older prefix permits arbitrary characters, including a potential opening delimiter, before the captured part. The revised prefix excludes < from its repetition. This places the boundary at an opening delimiter that the prefix cannot itself consume. The expression consequently gives the prefix and timestamp different responsibilities in parsing the greeting.
The release's apop() implementation matches this pattern against self.welcome. If no timestamp matches, it raises error_proto. If a match exists, it combines the captured bytes with the password bytes before computing the digest. That code establishes why the regular expression is processing data received from the server, rather than a pattern chosen by the application user.
The same module already bounds lines through _MAXLINE, set to 2048, and rejects a longer line in _getline(). That limit constrains how much input one read accepts. It does not establish a simple relationship between input length and matching effort. The existence of a size bound therefore does not make a problematic expression irrelevant.
The update belongs to the interpreter distribution
This release does not introduce a new comparison or mail API. Its corrected expressions are internal details of the standard library distributed with Python. Applications calling the affected operations receive the changed implementation through their runtime update.
The separate Windows symlink fix addresses native memory handling. It has a different mechanism from either expression change, so the release's security scope includes both processing cost and a platform-specific buffer boundary.
My judgement is that the source-only status should be part of any account of this patch. Upstream publishes the corrected source, while the distributor of a packaged interpreter determines how that correction reaches its users. The important observable change is the removal of problematic matching behaviour in the relevant module. A package's relationship to the upstream release must establish that it actually contains those corrections.