Repository navigation
Commit 07e9720
committed
fix(commit): bound co_authors trailer parsing
`Commit.co_authors` matched `^Co-authored-by: (.*) <(.*?)>$` against the
whole commit message. On a single trailer line that repeats `` <`` without
ever closing a `>`, the greedy `(.*)` backtracks over every `` <`` position
and, for each, the lazy `(.*?)` rescans to the end of the line looking for a
`>` that never arrives. That is O(n^2) in the length of the line.
The commit message is fully attacker-controlled: it comes straight from the
object bytes decoded in `_deserialize`, so a repository can ship a commit
whose message is a few hundred KB of `Co-authored-by: a <a <a <...`. Any
caller that reads `commit.co_authors` (a public property) then stalls. A
60 KB line already costs several seconds of CPU; a few hundred KB reaches
minutes.
Parse each `Co-authored-by:` line with string operations instead of a
backtracking regex: a trailer is `Co-authored-by: <name> <email>` with the
email in the final angle brackets, so the name ends at the last `` <`` and
the line ends at `>`. This reproduces the previous results exactly
(verified against the old pattern over ~1.8M fuzzed inputs, including the
existing `test_commit_co_authors` cases) while running in linear time: the
same crafted input drops from seconds to microseconds.
Add a CPU-time regression test that fails on the old code and passes here,
and confirm a well-formed trailer on a later line is still parsed.1 parent 3c638d2 commit 07e9720
2 files changed
Lines changed: 33 additions & 8 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -10,7 +10,6 @@ | |||
| 10 | 10 | from io import BytesIO | |
| 11 | 11 | import logging | |
| 12 | 12 | import os | |
| 13 | - import re | ||
| 14 | 13 | from subprocess import Popen, PIPE | |
| 15 | 14 | from time import altzone, daylight, localtime, time, timezone | |
| 16 | 15 | import warnings | |
@@ -964,12 +963,21 @@ def co_authors(self) -> List[Actor]: | |||
| 964 | 963 | co_authors = [] | |
| 965 | 964 | ||
| 966 | 965 | if self.message: | |
| 967 | - results = re.findall( | ||
| 968 | - r"^Co-authored-by: (.*) <(.*?)>$", | ||
| 969 | - str(self.message), | ||
| 970 | - re.MULTILINE, | ||
| 971 | - ) | ||
| 972 | - for author in results: | ||
| 973 | - co_authors.append(Actor(*author)) | ||
| 966 | + # Scan line by line instead of matching `(.*) <(.*?)>` across the whole | ||
| 967 | + # message. On a single trailer line that repeats " <" without ever closing | ||
| 968 | + # a ">", greedy backtracking over each " <" made the regex run in O(n^2) | ||
| 969 | + # time, so a large (fully attacker-controlled) commit message could stall | ||
| 970 | + # any caller of this property. A trailer is "Co-authored-by: <name> <email>" | ||
| 971 | + # with the email in the final angle brackets, so the name ends at the last | ||
| 972 | + # " <" and the line ends at ">". | ||
| 973 | + prefix = "Co-authored-by: " | ||
| 974 | + for line in str(self.message).split("\n"): | ||
| 975 | + if not line.startswith(prefix) or not line.endswith(">"): | ||
| 976 | + continue | ||
| 977 | + identity = line[len(prefix) :] | ||
| 978 | + separator = identity.rfind(" <") | ||
| 979 | + if separator == -1: | ||
| 980 | + continue | ||
| 981 | + co_authors.append(Actor(identity[:separator], identity[separator + 2 : -1])) | ||
| 974 | 982 | ||
| 975 | 983 | return co_authors | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -590,6 +590,23 @@ def test_commit_co_authors(self): | |||
| 590 | 590 | Actor("test_user_3", "test_user_3@github.com"), | |
| 591 | 591 | ] | |
| 592 | 592 | ||
| 593 | + def test_commit_co_authors_bounds_malformed_trailer(self): | ||
| 594 | + """A malformed trailer line must not make co_authors run in quadratic time.""" | ||
| 595 | + commit = copy.copy(self.rorepo.commit("4251bd5")) | ||
| 596 | + # An unterminated trailer repeating " <" without a closing ">". The old | ||
| 597 | + # `(.*) <(.*?)>` regex backtracked over every " <" (O(n^2)); the crafted line | ||
| 598 | + # is fully attacker-controlled through the commit message. | ||
| 599 | + commit.message = ( | ||
| 600 | + "Subject\n\nCo-authored-by: " + ("a <" * 20_000) + "\nCo-authored-by: Real Name <real@example.com>" | ||
| 601 | + ) | ||
| 602 | + start = time.process_time() | ||
| 603 | + result = commit.co_authors | ||
| 604 | + elapsed = time.process_time() - start | ||
| 605 | + # Leave ample CPU time for slow runners, but catch quadratic backtracking. | ||
| 606 | + self.assertLess(elapsed, 1.0) | ||
| 607 | + # The malformed line yields nothing; the well-formed trailer still parses. | ||
| 608 | + assert result == [Actor("Real Name", "real@example.com")] | ||
| 609 | + | ||
| 593 | 610 | @with_rw_directory | |
| 594 | 611 | def test_create_from_tree_with_trailers_dict(self, rw_dir): | |
| 595 | 612 | """Test that create_from_tree supports adding trailers via a dict.""" | |
0 commit comments