GHSA-5478-66C3-RHXR: Algorithmic Complexity Denial of Service in @chenglou/pretext

The @chenglou/pretext npm package provides text layout and measurement capabilities for web and Node.js environments. The library operates by parsing input strings and breaking them down into manageable segments using JavaScript's native Intl.Segmenter API. These segments are subsequently merged and measured to calculate accurate text layouts.

A high-severity vulnerability (GHSA-5478-66C3-RHXR) exists within the segmentation merging phase of the library. The vulnerability is classified as an Algorithmic Complexity issue, which leads to Uncontrolled Resource Consumption (Denial of Service). The processing time required by the library scales quadratically relative to the length of the input string when specific character patterns are supplied.

Because JavaScript runtimes (both Node.js and browser environments) are single-threaded, this quadratic processing time directly blocks the main event loop. While the loop is blocked, the application becomes completely unresponsive to other events, network requests, or user interactions. A remote attacker can exploit this condition without authentication by supplying a sufficiently long string of repeated punctuation characters.

The root cause of the vulnerability lies in the text analysis phase, specifically within the buildMergedSegmentation() and isRepeatedSingleCharRun() functions located in src/analysis.ts. When Intl.Segmenter processes text with word granularity, it emits discrete segments. For continuous runs of punctuation characters, the segmenter generates a separate segment for every individual character.

To optimize layout calculations, the buildMergedSegmentation() function attempts to combine these individual punctuation segments back into a single continuous block. Before merging a new character into the accumulated sequence, the library invokes isRepeatedSingleCharRun() to verify that the incoming character matches the characters already present in the segment.

This verification function iterates through the entirety of the accumulated segment for each new character processed. On the $k$-th merge attempt, the accumulated segment contains $k$ characters, requiring $k$ comparison operations. When processing a string of $N$ identical punctuation characters, the total number of operations equals the sum of the arithmetic series $1 + 2 + 3 + ... + N$. This mathematical progression results in an execution time of $O(N^2)$.

The flaw is evident in the implementation of the isRepeatedSingleCharRun() function in version 0.0.4 and earlier. The function receives the accumulated string segment and the new single character ch.

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

The for (const part of segment) loop is the source of the performance degradation. Because segment grows by one character with every successful merge, the loop executes an increasing number of times. When processing 80,000 characters, the loop will ultimately perform over 3.2 billion iterations.

The fix involves replacing this $O(N)$ full-scan verification with a more efficient check. Since the function's purpose is only to verify that the accumulated segment consists entirely of the single character ch, checking every character is redundant if the segment is built incrementally. Verifying that the first character matches, or maintaining state during the merge phase, reduces the check to $O(1)$ complexity. This optimization changes the overall algorithm from $O(N^2)$ back to $O(N)$.

Exploitation requires the attacker to submit a payload of contiguous punctuation characters to an endpoint or interface that passes data to the @chenglou/pretext engine. The layout engine is often triggered automatically when text is rendered or measured for UI components.

The attack payload consists of a high volume of repeated non-alphanumeric characters. Characters known to trigger the vulnerable code path include parentheses, brackets, and common symbols. The following Proof of Concept (PoC) demonstrates the attack using the parenthesis character.

import { prepare } from '@chenglou/pretext'
 
// Payload consisting of 80,000 repeating characters
const payload = '('.repeat(80_000)
 
console.time('pretext-dos');
// Triggers the O(N^2) code path, blocking the thread
prepare(payload, '16px Arial'); 
console.timeEnd('pretext-dos');

When this payload is passed to the prepare() function, the JavaScript engine begins the computationally expensive merge process. A payload of 80,000 characters typically forces the main thread to hang for approximately 20 seconds on standard hardware. By sending concurrent requests with this payload, an attacker easily exhausts all available Node.js worker threads or severely degrades client-side performance.

The vulnerability carries a CVSS v4.0 score of 8.7 (High), reflecting a severe impact on availability with minimal attack complexity. The CVSS vector 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 indicates that the attack is executable over the network without authentication or specialized conditions.

On server-side deployments utilizing @chenglou/pretext for server-side rendering (SSR) or document generation, the impact is critical. Node.js operates on a single-threaded event loop. When the loop is blocked for 20 seconds processing a single malicious request, the server cannot accept new connections or process existing requests. This results in an immediate and total Denial of Service for all users.

In client-side implementations, the vulnerability causes the victim's browser tab to freeze. While this isolates the damage to the individual user, it severely damages application usability and trust. If the payload is persistent (e.g., stored in a database and rendered to multiple users), it creates a persistent DoS condition for anyone viewing the affected content.

The primary remediation strategy is to upgrade the @chenglou/pretext dependency to version 0.0.5 or later. The patch eliminates the algorithmic inefficiency, ensuring that execution time scales linearly rather than quadratically with input length. Developers should audit their dependency trees (npm ls @chenglou/pretext) to identify transitive dependencies that may include vulnerable versions.

If an immediate upgrade is impossible, organizations should implement strict input validation on any user-supplied text before it reaches the prepare() function. Limiting the maximum character length of the input significantly reduces the risk. Given the $O(N^2)$ scaling factor, a conservative limit of 10,000 characters restricts the maximum processing time to a negligible fraction of a second.

Additionally, implementing a Web Application Firewall (WAF) rule to drop requests containing long sequences of repeating punctuation characters can act as a stopgap measure. However, this approach is fragile and may produce false positives in applications that handle technical documentation or code snippets.