Quadratic-time ReDoS in Unix-timestamp (X) format token parsing
- Dominant language
- Python
- Stars
- 9.1k
- Forks
- 784
- PR merge metrics
- No merged PRs in 30d
Description
`arrow.get(string, "X")` (the Unix-timestamp format token) has quadratic-time backtracking on non-matching digit-heavy input, allowing a single request to block a worker thread for seconds to minutes.
**Affected:** `DateTimeParser` / format token `X` (`arrow/parser.py`)
**Tested against:** arrow 1.4.0 (current, tag `1.4.0`, commit `6c4e0db`)
### Root cause
`arrow/parser.py:169`:
```python
_TIMESTAMP_RE: ClassVar[Pattern[str]] = re.compile(r"^\-?\d+\.?\d+$")
```
This is the regex behind the `"X"` format token, used e.g. by `arrow.get(user_string, "X")`. It has two adjacent unbounded `\d+` groups separated by an optional `.`, both anchored to `$`. For an input like `"9"*N + "x"` (N digits followed by one non-digit), the first `\d+` greedily consumes all N digits, the optional `\.?` never matches, and the second `\d+` must then backtrack through every possible split point between the two groups before the whole match can fail — O(N) splits × O(N) backtracking work each = O(N²) total, before `ParserMatchError` is raised.
### Reproduction
```python
import time
import arrow
for n in [1000, 5000, 10000, 20000, 40000]:
payload = "9" * n + "x"
t0 = time.perf_counter()
try:
arrow.get(payload, "X")
except Exception:
pass
dt = time.perf_counter() - t0
print(f"n={n:6d} time={dt:8.3f}s")
```
Measured:
| input length (digits) | time |
|---:|---:|
| 1,000 | 0.012 s |
| 5,000 | 0.23 s |
| 10,000 | 0.96 s |
| 20,000 | 3.72 s |
| 40,000 | 15.4 s |
Time roughly quadruples each time the length doubles — clean O(n²) scaling, confirmed down to the isolated regex (`_TIMESTAMP_RE.match("9"*n + "x")`) as well as through the full `arrow.get()` call path. At n=60,000 (a 60 KB string) the call takes ~31s.
### Impact
Any application that calls `arrow.get(attacker_string, "X")` (or includes `"X"` in a format list, e.g. `arrow.get(s, ["X", "YYYY-MM-DD"])`) on unsanitized, length-unbounded input is affected — a realistic pattern for services parsing Unix-epoch timestamps from webhooks, query parameters, or JSON fields. No auth or user interaction is needed; a single request with a body in the tens-to-hundreds-of-KB range is enough to pin a worker thread for seconds to minutes, and is trivially deliverable over HTTP.
### Suggested fix
Rewrite `_TIMESTAMP_RE` to remove the ambiguity between the two `\d+` groups, e.g. `r"^\-?\d+(?:\.\d+)?$"` (making the fractional part a single non-backtracking optional group instead of two independently-greedy unbounded groups), or add an input-length cap before attempting the match.
I have not modified anything in the checkout — this is read-only analysis plus a standalone timing script. Happy to open a PR with the regex fix if useful.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start in arrow/parser.py at _TIMESTAMP_RE, the regex used by the X format token. Run the supplied digit-heavy reproduction and isolated regex timing before and after the change. Done means non-matching inputs no longer show quadratic scaling while valid Unix-timestamp values still parse.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- security
- Issue type
- Bug
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 82/100