<!--############################ Do not remove the line above ############################--> <!--Note that this issue is configured (see the quick actions at the bottom) to be created as confidential. Note that a vulnerability does not need to actually be resolved before it is reported and that these reports can be revised as needed (reopen the issue to request changes). If you do not know how to fill certain fields, mark that in the comment and we will help you.--> <!--Required. Specify the project's name (e.g., "Eclipse Dash") and Eclipse Foundation ID, e.g., "technology.dash".--> ### Summary `langium` (npm) exports `IndentationAwareLexer`/`IndentationAwareTokenBuilder` as a building block for indentation-sensitive, Python-like DSLs. When tokenizing a document, the lexer recomputes the current line number by re-scanning the entire preceding document text from scratch (`text.substring(0, offset).split(...)`) on every DEDENT token it emits. A document whose indentation depth changes on nearly every line forces this recomputation on nearly every line, so the whole `tokenize()` call runs in O(n²) in document length. An unauthenticated attacker who can get such a document tokenized, through a hosted grammar/DSL playground, a backend validation endpoint, or a remote LSP server for an indentation-based language, can freeze the entire Node.js process, not just their own request, for many seconds with a payload well under 1MB. Node is single-threaded, so this blocks every other concurrent session on the same process for the duration of the hang. This affects consumers who opt into `IndentationAwareLexer`/`IndentationAwareTokenBuilder`. It does not affect the default `DefaultLexer`/`DefaultTokenBuilder` that most Langium-based languages use. ### Details * **Affected package:** `langium` (npm) * **Affected version:** `4.4.0`, npm-latest at time of report * **Patched version:** none * **CWE:** CWE-407 (Uncontrolled Resource Consumption / Algorithmic Complexity) * **Attacker prerequisites:** none. The attacker only needs to submit a document, through whatever mechanism the embedding application already exposes, to a consumer wired up with `IndentationAwareLexer`. * **Configuration prerequisite:** the embedding application must use `IndentationAwareLexer`/`IndentationAwareTokenBuilder` for an indentation-sensitive grammar. Both classes are exported from the `langium` package root and documented for this use, though they are opt-in rather than the library's default lexer. #### Root cause packages/langium/src/parser/<wbr>indentation-aware.ts:247-248: protected getLineNumber(text: string, offset: number): number { return text.substring(0, offset).split(/\\r\\n|\\r|\\n/).<wbr>length; } This is called from `createIndentationTokenInstance` (:231), which runs from `dedentMatcher`'s dedent-emission loop and from `flushRemainingDedents`: once per DEDENT token produced during tokenization (`indentMatcher` itself doesn't call it). `dedentMatcher` also runs a second full-prefix scan per dedent: const newlinesBeforeDedent = text.substring(0, offset).match(/\[\\r\\n\]+$/)?.\[0\]<wbr>.length ?? 1; (`indentation-aware.ts:314`) Each call allocates and rescans an O(offset) substring of the document processed so far. There's no cached or incremental line-offset index, and no length or complexity guard anywhere in the tokenization path. A document that changes indentation depth on every line forces a DEDENT, and hence a `getLineNumber` call, on a large fraction of lines, so the cumulative cost across the document is O(n²). #### Attack vector 1. Attacker crafts a plain-text document in the target's indentation-sensitive DSL where indentation depth decreases on a large fraction of lines, for example alternating +1/-1 spaces of indentation every line. No special characters or malformed syntax are required; the document can otherwise be syntactically valid. 2. Attacker submits it to any endpoint that tokenizes with `IndentationAwareLexer`: a playground parse/validate action, a backend document-processing endpoint, a remote LSP `textDocument/didOpen`. 3. `lexer.tokenize()` runs synchronously and blocks the Node.js event loop for the full duration of the quadratic computation. 4. For the duration of the hang, the process can't service any other request, timer, or callback, not just the attacker's own connection. #### Impact Full-process denial of service. Measured: a 708KB crafted document, well under typical upload or paste size limits, blocks the event loop for 69.8 seconds; smaller documents scale down but stay disproportionate (357KB, 10.5s). There's no confidentiality or integrity impact; this is a pure availability bug. On a shared or multi-tenant service, one attacker request denies service to every other concurrent user for the duration of the hang. ### Proof of concept A self-contained, loopback-only PoC (`poc_indent_dos.mjs`) stands up a minimal local HTTP service on `127.0.0.1` (ephemeral port) that tokenizes a submitted document body using the real, unmodified `IndentationAwareLexer`/`IndentationAwareTokenBuilder` from the installed `langium@4.4.0` package, mirroring how a hosted DSL service would process a submission. It runs an in-process heartbeat timer (`setInterval`, 10ms) throughout the attack request. If the event loop is frozen, the heartbeat can't tick, which gives a deterministic, direct measurement that nothing else on the process can run. Racing two real HTTP requests against each other proved unreliable, because of independent-socket I/O scheduling, so that approach isn't used as evidence here. Run: cd targets/langium && npm install && node poc_indent_dos.mjs Reproduced 3/3 independently, deterministic, exit 0 every run: Run 1: wall=6930.4ms, heartbeat ticks 1/\~693 expected, starvation 99.9% Run 2: wall=6396.8ms, heartbeat ticks 2/\~639 expected, starvation 99.7% Run 3: wall=7385.6ms, heartbeat ticks 1/\~738 expected, starvation 99.9% A post-attack control request, issued immediately after each run, returns in single-digit milliseconds, confirming the hang is isolated to the `tokenize()` call itself: the process is fully responsive again the instant it returns. Independent scaling measurements against the same package (full data and re-runnable harnesses in `findings.md` and `harness/`): | Document | Size | `tokenize()` time | |----------|------|-------------------| | 32,000 lines | 357 KB | 10.5 s | | 48,000 lines | 528 KB | 37.2 s | | 64,000 lines | 708 KB | 69.8 s | A same-size control document with flat, non-churning indentation of 341 KB tokenizes in 41.3 ms, a 254x difference that isolates the quadratic cost to indent/dedent frequency, which is fully attacker-controlled via the document's own whitespace. This rules out "large documents are simply slow" as an alternative explanation. ### Severity Severity depends on how the embedding application exposes the vulnerable lexer, so both realistic scenarios are given rather than one blanket score: * **Network-facing consumer** (hosted playground, backend document-processing service, remote LSP, no per-request authentication assumed): `CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H` = 7.5 HIGH * **Local editor** (e.g. a VS Code extension opening an attacker-authored file locally): `CVSS:3.1/AV:L/AC:L/PR:N/UI:R/S:U/C:N/I:N/A:H` = 5.5 MEDIUM ### Suggested fix Replace the per-call `text.substring(0, offset).split(...)` line-number recomputation with either an incrementally maintained line counter, updated as the lexer advances through the document (O(1) amortized per token), or a one-time O(n) newline-offset index built at the start of `tokenize()`, with `getLineNumber` doing a binary search over it (O(log n) per lookup). Either removes the quadratic behavior while preserving the reported line numbers.