Repository navigation
Commit 2235723
committed
fix(config): bound option-line parsing
`GitConfigParser.OPTCRE` matched an option line with
`(?P<option>[^:=#;]*)` immediately followed by `\s*(?P<vi>[:=])`. The
option name class and that `\s*` both match spaces, so a line that never
reaches a `:` or `=` separator (a key followed by a long run of
whitespace) makes the regex engine retry every space position, taking
`O(n^2)` time in the length of the run.
Config files are parsed straight from repository content. `.gitmodules`
in particular is read whenever submodules of an inspected or cloned
repository are enumerated, so the line is fully attacker-controlled. A
crafted key line costs about `0.25s` of CPU at 8,000 spaces and roughly
`160s` at 200,000, stalling any caller that reads the config.
The trailing `\s*` is redundant: `[^:=#;]*` already consumes any spaces
up to the indicator, and the captured name is right-stripped after
parsing. Dropping it leaves a single quantifier over the whitespace run,
so matching is linear. The collapsed pattern accepts exactly the same
lines and yields the same groups as the previous one, checked over
200,000 fuzzed inputs with zero differences.
Add `test_option_line_with_long_whitespace_run_is_not_quadratic`, a
CPU-time regression that fails on the previous pattern and passes here,
and that confirms a valid key before the malformed line still parses.1 parent f8776ee commit 2235723
2 files changed
Lines changed: 25 additions & 1 deletion
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -334,7 +334,11 @@ class GitConfigParser(cp.RawConfigParser, metaclass=MetaParserBuilder): | |||
| 334 | 334 | ||
| 335 | 335 | OPTVALUEONLY = re.compile(optvalueonly_source) | |
| 336 | 336 | ||
| 337 | - OPTCRE = re.compile(optvalueonly_source + r"\s*(?P<vi>[:=])\s*" + r"(?P<value>.*)$") | ||
| 337 | + # The option name class [^:=#;]* already consumes any spaces up to the ":" or "=", | ||
| 338 | + # so a second \s* before the indicator would overlap it and backtrack quadratically | ||
| 339 | + # on a line that never reaches an indicator (for example a key followed by a long | ||
| 340 | + # whitespace run). Drop the redundant \s*; the name is right-stripped after parsing. | ||
| 341 | + OPTCRE = re.compile(optvalueonly_source + r"(?P<vi>[:=])\s*" + r"(?P<value>.*)$") | ||
| 338 | 342 | ||
| 339 | 343 | del optvalueonly_source | |
| 340 | 344 | ||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -9,6 +9,7 @@ | |||
| 9 | 9 | import os.path as osp | |
| 10 | 10 | import subprocess | |
| 11 | 11 | import sys | |
| 12 | + import time | ||
| 12 | 13 | from unittest import mock | |
| 13 | 14 | ||
| 14 | 15 | import pytest | |
@@ -262,6 +263,25 @@ def test_inline_comments_are_stripped_like_git(self): | |||
| 262 | 263 | with self.subTest(content=content): | |
| 263 | 264 | self.assertEqual(config.get_value("a", "k"), expected) | |
| 264 | 265 | ||
| 266 | + def test_option_line_with_long_whitespace_run_is_not_quadratic(self): | ||
| 267 | + """A key followed by a long whitespace run and no indicator must not make | ||
| 268 | + the option regex backtrack quadratically. | ||
| 269 | + | ||
| 270 | + `.gitmodules` and other config files are fully controlled by any repository | ||
| 271 | + that is inspected, so a crafted line must stay cheap to parse. Keys that come | ||
| 272 | + before the malformed line are still read. | ||
| 273 | + """ | ||
| 274 | + malformed = b'[submodule "x"]\n\tpath = x\n\tbranch' + b" " * 200_000 + b"\n" | ||
| 275 | + config_file = io.BytesIO(malformed) | ||
| 276 | + config_file.name = ".gitmodules" | ||
| 277 | + config = GitConfigParser(config_file) | ||
| 278 | + start = time.process_time() | ||
| 279 | + config.read() | ||
| 280 | + elapsed = time.process_time() - start | ||
| 281 | + # Leave ample CPU time for slow runners, but catch quadratic backtracking. | ||
| 282 | + self.assertLess(elapsed, 1.0) | ||
| 283 | + self.assertEqual(config.get_value('submodule "x"', "path"), "x") | ||
| 284 | + | ||
| 265 | 285 | @with_rw_directory | |
| 266 | 286 | def test_inline_comments_preserve_balanced_quotes_and_following_settings(self, rw_dir): | |
| 267 | 287 | config_path = osp.join(rw_dir, "config") | |
0 commit comments