arrow-py / arrow-py/arrow

Quadratic-time ReDoS in Unix-timestamp (X) format token parsing

Open Beginner friendly
#1,353 0 comments 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.