trailofbits / trailofbits/polyfile
Regex tests run on a backtracking engine, so a safe libmagic definition can hang PolyFile
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 390
- Forks
- 31
- Avg merge
- 7h 52m
- Merged PRs (30d)
- 72
Description
Summary
PolyFile evaluates every regex test with Python's re, a backtracking engine. libmagic uses a
POSIX engine, which runs in time linear in the input. So a definition that is perfectly safe for
file can take minutes in PolyFile on a few kilobytes of untrusted input.
Three instances have been fixed one at a time, two of them by patching a definition PolyFile
inherits from upstream:
| Issue | Where | Fix |
|---|---|---|
| #3411 | polyfile/magic_defs/c-lang |
local patch to a vendored definition |
| #3473 | polyfile/magic_defs/gentoo |
local patch to a vendored definition |
| #3527 | polyfile/http/matcher.py |
PolyFile's own definition |
The pattern is now clear enough to name: the definitions are not wrong, the engine is. #3473
says so directly — libmagic is unaffected because it does not backtrack. Upstream therefore has no
reason to change these patterns, and PolyFile carries each patch indefinitely.
Why one more patch is not the answer
Scanning the bundled definitions for the same shape — two or more quantified POSIX character
classes in a single regex test — finds 26 candidates across five files:
14 c-lang 5 ruby 4 varied.script 2 perl 1 gentoo
Two of those five have already bitten us. ruby, perl and varied.script are unexamined. The
population grows with every upstream definition sync, and each new pathological pattern is a
denial-of-service surface that reaches users before anyone measures it.
Each local patch also has a standing cost. polyfile/magic_defs/ is a hand-maintained copy of
file/magic/Magdir/, so a patch must be re-applied by hand on every sync. #3479 added
tests/test_magic_defs_drift.py to make a reverted patch fail CI, which makes the debt visible
but not cheaper.
Where the engine is chosen
Two call sites compile a definition's pattern, both in polyfile/magic.py:
MagicRegex.__init__—self.compiled = re.compile(self.pattern, flags), forregextestsStringMatch.pattern—self._pattern = re.compile(self.pattern_string(), flags=...), for the
stringandsearchfamilies
MagicRegex already normalizes POSIX classes into Python syntax through posix_to_python_re, so
the translation layer that an engine swap would extend is in place.
Directions worth weighing
-
A linear-time engine. RE2 (
google-re2) gives the same guarantee libmagic gets from POSIX,
and the libmagic DSL does not use backreferences or lookaround, so the subset of syntax the
definitions need should map cleanly. Two things to establish first: whether the shipped
definitions really avoid constructs RE2 rejects, and what a new native dependency costs for
packaging, since PolyFile ships a pure-Python wheel today. PolyFile's own patterns do now use
lookbehind (polyfile/http/matcher.py, from #3527) and would need rewriting. -
An evaluation budget. Cap the work a single test may spend and treat exhaustion as a
non-match, so a pathological pattern degrades instead of hanging. Weaker than a real guarantee
and it makes matching results depend on timing, but it needs no new dependency and it bounds
every pattern including ones nobody has scanned for. -
A static check over the definitions. A test that rejects a definition whose quantifiers can
split the same input many ways. Cheap, catches regressions at sync time, and complements either
of the above — but it cannot fix a pattern that is genuinely needed.
Whichever direction wins, the payoff is that the two vendored patches become removable rather
than maintained: with a linear-time engine, c-lang and gentoo can go back to matching upstream
byte for byte, and LOCAL_PATCHES in tests/test_magic_defs_drift.py empties out.
Scope
Deliberately outside milestone v0.6.0. This changes a dependency and the matching hot path, so it
wants its own release and its own performance baseline rather than riding along with a bug-fix
milestone.
Found while reviewing the fixes for #3527 and #3473.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in polyfile/magic.py at MagicRegex.init and StringMatch.pattern, then review posix_to_python_re and the definitions under polyfile/magic_defs/. Run the existing magic-definition and drift tests, and establish a performance baseline for the listed patterns. Done means a chosen mitigation is validated, pathological matching is bounded or linear-time, and the vendored c-lang and gentoo patches can be removed with LOCAL_PATCHES updated.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- backend, performance, security
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100