<?xml version='1.0' encoding='UTF-8'?>
<?xml-stylesheet href="/static/style.xsl" type="text/xsl"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="en">
  <id>https://db.gcve.eu/rss/recent/all/10</id>
  <title>Most recent entries from all</title>
  <updated>2026-10-29T20:11:56.194171+00:00</updated>
  <author>
    <name>Vulnerability-Lookup</name>
    <email>info@gcve.eu</email>
  </author>
  <link href="https://db.gcve.eu" rel="alternate"/>
  <generator uri="https://lkiesow.github.io/python-feedgen" version="1.0.0">python-feedgen</generator>
  <subtitle>Contains only the most 10 recent entries.</subtitle>
  <entry>
    <id>https://db.gcve.eu/vuln/ghsa-gg6h-894w-4m9c</id>
    <title>GHSA-gg6h-894w-4m9c — RE2JS: Quadratic-time denial of service in re2js lookbehind matching</title>
    <updated>2026-10-29T20:11:56.195917+00:00</updated>
    <content type="xhtml">
      <div xmlns="http://www.w3.org/1999/xhtml"><p><strong>Affected:</strong> npm: re2js</p>
<p>### Summary</p>
<p>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**.</p>
<p>### Description</p>
<p>#### Root cause</p>
<p>In `build/index.cjs`, `Machine.match`:</p>
<p>```js
let currentPos = this.prog.numLb &gt; 0 ? 0 : pos;   // ~line 1907
...
if (this.ncap === 0 &amp;&amp; this.matched) break;        // ~line 1953
```</p>
<p>Any pattern containing a lookbehind sets `prog.numLb &gt; 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.</p>
<p>A find-loop over *k* matches in an *n*-character string therefore costs
*k* × Θ(*n*); for dense matches *k* ∝ *n*, giving **Θ(n²)** total.</p>
<p>#### Isolating control</p>
<p>Identical find-loop, identical input sizes, same 2-character literal pattern
*shape* — but **without** the…</p></div>
    </content>
    <link href="https://db.gcve.eu/vuln/ghsa-gg6h-894w-4m9c"/>
  </entry>
</feed>
