trailofbits / trailofbits/polyfile

Regex tests run on a backtracking engine, so a safe libmagic definition can hang PolyFile

Open
#3,547 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement
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), for regex tests
  • StringMatch.patternself._pattern = re.compile(self.pattern_string(), flags=...), for the
    string and search families

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

  1. 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.

  2. 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.

  3. 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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.