Commit 226654a
committed
fix(commit): accumulate gpgsig continuation lines in linear time
`Commit._deserialize` collected a `gpgsig` header by appending each
continuation line to a `bytes` object with `+=`. `bytes` are immutable, so
every line copied the whole signature read so far, and a signature with *n*
continuation lines cost O(n^2) to parse.
Commit headers are fully controlled by whoever wrote the commit, and
`_deserialize` runs on the first access to any commit attribute (`author`,
`message`, `parents`, ...). Reading the commits of an untrusted repository is
therefore enough to hit it. Measured on Python 3.11 with a `gpgsig` header of
`" x\n"` lines:
| object size | before | after |
| ----------- | ------- | ------ |
| 2.4 MB | 9.5 s | 0.08 s |
| 4.8 MB | 116.8 s | |
| 9.6 MB | 547.9 s | 0.32 s |
Collect the lines in a list and join them once. This is linear and produces
byte-identical `gpgsig` values, so the existing `test_gpgsig` round trip is
unchanged.
`test_gpgsig_deserialization_is_linear` deserializes a 1.8 MB signature under
a 1 s CPU-time bound. It fails on the previous code and passes here. The full
suite has no new failures; the 8 tests that fail locally (non-UTF-8 trailer
encoding and NUL submodule names) fail identically without this change.
`ruff`, `mypy` and `basedpyright --warnings` are clean.1 parent 6306c5c commit 226654a
2 files changed
Lines changed: 25 additions & 3 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -885,7 +885,7 @@ def _deserialize(self, stream: BytesIO) -> "Commit": | |||
| 885 | 885 | if buf[0:10] == b"encoding ": | |
| 886 | 886 | self.encoding = buf[buf.find(b" ") + 1 :].decode(self.encoding, "ignore") | |
| 887 | 887 | elif buf[0:7] == b"gpgsig ": | |
| 888 | - sig = buf[buf.find(b" ") + 1 :] + b"\n" | ||
| 888 | + sig_lines = [buf[buf.find(b" ") + 1 :] + b"\n"] | ||
| 889 | 889 | is_next_header = False | |
| 890 | 890 | while True: | |
| 891 | 891 | sigbuf = readline() | |
@@ -895,9 +895,9 @@ def _deserialize(self, stream: BytesIO) -> "Commit": | |||
| 895 | 895 | buf = sigbuf.strip() | |
| 896 | 896 | is_next_header = True | |
| 897 | 897 | break | |
| 898 | - sig += sigbuf[1:] | ||
| 898 | + sig_lines.append(sigbuf[1:]) | ||
| 899 | 899 | # END read all signature | |
| 900 | - self.gpgsig = sig.rstrip(b"\n").decode(self.encoding, "ignore") | ||
| 900 | + self.gpgsig = b"".join(sig_lines).rstrip(b"\n").decode(self.encoding, "ignore") | ||
| 901 | 901 | if is_next_header: | |
| 902 | 902 | continue | |
| 903 | 903 | buf = readline().strip() | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -607,6 +607,28 @@ def test_commit_co_authors_bounds_malformed_trailer(self): | |||
| 607 | 607 | # The malformed line yields nothing; the well-formed trailer still parses. | |
| 608 | 608 | assert result == [Actor("Real Name", "real@example.com")] | |
| 609 | 609 | ||
| 610 | + def test_gpgsig_deserialization_is_linear(self): | ||
| 611 | + """A long gpgsig header must not make deserialization run in quadratic time.""" | ||
| 612 | + num_lines = 600_000 | ||
| 613 | + # Commit headers are fully attacker-controlled. Accumulating the signature with | ||
| 614 | + # bytes concatenation copied it once per continuation line (O(n^2)). | ||
| 615 | + data = ( | ||
| 616 | + b"tree 4b825dc642cb6eb9a060e54bf8d69288fbee4904\n" | ||
| 617 | + b"author A <a@example.com> 1700000000 +0000\n" | ||
| 618 | + b"committer A <a@example.com> 1700000000 +0000\n" | ||
| 619 | + b"gpgsig -----BEGIN PGP SIGNATURE-----\n" + b" x\n" * num_lines + b" -----END PGP SIGNATURE-----\n" | ||
| 620 | + b"\n" | ||
| 621 | + b"message\n" | ||
| 622 | + ) | ||
| 623 | + cmt = copy.copy(self.rorepo.commit()) | ||
| 624 | + start = time.process_time() | ||
| 625 | + cmt._deserialize(BytesIO(data)) | ||
| 626 | + elapsed = time.process_time() - start | ||
| 627 | + # Leave ample CPU time for slow runners, but catch quadratic accumulation. | ||
| 628 | + self.assertLess(elapsed, 1.0) | ||
| 629 | + self.assertEqual(cmt.gpgsig.count("\n"), num_lines + 1) | ||
| 630 | + self.assertEqual(cmt.message, "message\n") | ||
| 631 | + | ||
| 610 | 632 | @with_rw_directory | |
| 611 | 633 | def test_create_from_tree_with_trailers_dict(self, rw_dir): | |
| 612 | 634 | """Test that create_from_tree supports adding trailers via a dict.""" | |
0 commit comments