Compare commits

...

3 Commits

Author SHA1 Message Date
diegosouzapw
2a48a0a823 Merge remote-tracking branch 'origin/release/v3.8.55' into fix/codeql-redos-compression
# Conflicts:
#	open-sse/services/compression/engines/headroom/gcf/scalar.ts
#	open-sse/services/compression/engines/rtk/rawOutput.ts
2026-11-21 00:25:29 -03:00
diegosouzapw
c13cee2357 chore(changelog): prefix the fragment with PR #20825 2026-11-20 18:33:25 -03:00
diegosouzapw
eca9826d29 fix(security): bound regex work in compression engines (CodeQL #1301, #1302, #1349)
- headroom GCF needsQuote: inline-array regex excludes '[' from the bracket body (same .test verdict, linear on '[' runs).
- RTK raw-output: cut the tool_use command to 256 chars before the slug replaces.
- CCR grep: reject patterns with more than one unbounded quantifier and run the scan under a 1000 ms vm timeout.
2026-11-20 18:31:14 -03:00
3 changed files with 320 additions and 21 deletions

View File

@@ -0,0 +1 @@
- **fix(security):** Compression engines bound their regex work on hostile input: the headroom GCF inline-array check and the RTK raw-output command slug run in linear time, and CCR `grep` rejects patterns with more than one unbounded quantifier and stops a scan that exceeds a 1 s time budget (CodeQL #1301, #1302, #1349)

View File

@@ -3,9 +3,12 @@
*
* `full`/absent → whole text (backward-compat). All modes are fail-safe:
* incoherent params or an unsafe regex yield { error }, never throw. The grep
* mode validates the pattern with `safe-regex` (no catastrophic backtracking)
* before compiling, and bounds matches/pattern length.
* mode validates the pattern with `safe-regex` (no nested quantifiers), allows at
* most one unbounded quantifier, bounds matches/pattern length, and runs the scan
* under a wall-clock budget (CodeQL #1349): a caller-supplied pattern can still be
* super-linear (`.*x` is quadratic per line), so the budget is the hard bound.
*/
import vm from "node:vm";
import safeRegex from "safe-regex";
export type CcrMode = "full" | "head" | "tail" | "lines" | "grep" | "stats";
@@ -24,6 +27,8 @@ export type CcrQueryResult = { content: string } | { error: string };
export const MAX_RANGE_LINES = 10_000;
export const MAX_GREP_MATCHES = 1_000;
export const MAX_PATTERN_LEN = 512;
/** Wall-clock budget for one grep scan over a block (ms). */
export const GREP_TIME_BUDGET_MS = 1_000;
const err = (m: string): CcrQueryResult => ({ error: m });
const ok = (c: string): CcrQueryResult => ({ content: c });
@@ -53,30 +58,104 @@ function sliceLines(lines: string[], start?: number, end?: number): CcrQueryResu
return ok(lines.slice(start - 1, Math.min(end, lines.length)).join("\n"));
}
function grepLines(lines: string[], pattern?: string, unique?: boolean): CcrQueryResult {
/**
* Number of unbounded quantifiers (`*`, `+`, `{n,}`) outside character classes and
* escapes. Two or more in sequence make the backtracking polynomial in the line length
* (`.*.*.*.*x` is O(n^4)), which `safe-regex`'s star-height check does not catch.
*/
export function countUnboundedQuantifiers(pattern: string): number {
let count = 0;
let i = 0;
while (i < pattern.length) {
const c = pattern[i];
if (c === "\\") {
i += 2;
} else if (c === "[") {
i = classEnd(pattern, i);
} else {
if (c === "*" || c === "+" || (c === "{" && isOpenRange(pattern, i))) count++;
i++;
}
}
return count;
}
/** Index just past the character class that opens at `start` (escapes honoured). */
function classEnd(pattern: string, start: number): number {
let i = start + 1;
while (i < pattern.length && pattern[i] !== "]") i += pattern[i] === "\\" ? 2 : 1;
return i + 1;
}
/** True when an open range quantifier `{n,}` starts at `start`. */
function isOpenRange(pattern: string, start: number): boolean {
let j = start + 1;
while (j < pattern.length && pattern[j] >= "0" && pattern[j] <= "9") j++;
return j > start + 1 && pattern[j] === "," && pattern[j + 1] === "}";
}
// The scan runs in a dedicated context only so `timeout` can stop a runaway regex.
// No host object enters it: inputs are primitives, the result leaves as a JSON string.
const GREP_SCRIPT = new vm.Script(`(() => {
"use strict";
let re;
try { re = new RegExp(grepPattern); } catch { return JSON.stringify({ invalid: true }); }
const matched = [];
let truncated = false;
for (const line of grepText.split("\\n")) {
if (re.test(line)) {
matched.push(line);
if (matched.length >= grepMaxMatches) { truncated = true; break; }
}
}
return JSON.stringify({ matched, truncated });
})()`);
let grepContext: vm.Context | null = null;
function runGrepScan(
text: string,
pattern: string
): { matched: string[]; truncated: boolean } | "invalid" | "timeout" {
grepContext ??= vm.createContext(Object.create(null), {
codeGeneration: { strings: false, wasm: false },
});
grepContext.grepPattern = pattern;
grepContext.grepText = text;
grepContext.grepMaxMatches = MAX_GREP_MATCHES;
let raw: unknown;
try {
raw = GREP_SCRIPT.runInContext(grepContext, { timeout: GREP_TIME_BUDGET_MS });
} catch (e) {
if ((e as { code?: string })?.code === "ERR_SCRIPT_EXECUTION_TIMEOUT") return "timeout";
throw e;
} finally {
grepContext.grepText = "";
grepContext.grepPattern = "";
}
const parsed = JSON.parse(String(raw)) as {
invalid?: boolean;
matched?: string[];
truncated?: boolean;
};
if (parsed.invalid === true) return "invalid";
return { matched: parsed.matched ?? [], truncated: parsed.truncated === true };
}
function grepLines(text: string, pattern?: string, unique?: boolean): CcrQueryResult {
if (!pattern) return err("grep requires a 'pattern'");
if (pattern.length > MAX_PATTERN_LEN) return err(`pattern exceeds ${MAX_PATTERN_LEN} chars`);
if (!safeRegex(pattern)) return err("pattern rejected: potentially catastrophic backtracking");
let re: RegExp;
try {
re = new RegExp(pattern);
} catch {
return err("invalid regex pattern");
if (countUnboundedQuantifiers(pattern) > 1) {
return err("pattern rejected: at most one unbounded quantifier (*, +, {n,}) is allowed");
}
const matched: string[] = [];
let truncated = false;
for (const line of lines) {
if (re.test(line)) {
matched.push(line);
if (matched.length >= MAX_GREP_MATCHES) {
truncated = true;
break;
}
}
const scan = runGrepScan(text, pattern);
if (scan === "invalid") return err("invalid regex pattern");
if (scan === "timeout") {
return err(`grep exceeded its ${GREP_TIME_BUDGET_MS} ms time budget; use a narrower pattern`);
}
const out = unique ? [...new Set(matched)] : matched;
const out = unique ? [...new Set(scan.matched)] : scan.matched;
const body = out.join("\n");
return ok(truncated ? `${body}\n…[truncated at ${MAX_GREP_MATCHES} matches]` : body);
return ok(scan.truncated ? `${body}\n…[truncated at ${MAX_GREP_MATCHES} matches]` : body);
}
function blockStats(text: string, lines: string[]): CcrQueryResult {
@@ -101,7 +180,7 @@ export function queryBlock(text: string, q: CcrQuery): CcrQueryResult {
case "lines":
return sliceLines(lines, q.start, q.end);
case "grep":
return grepLines(lines, q.pattern, q.unique);
return grepLines(text, q.pattern, q.unique);
case "stats":
return blockStats(text, lines);
default:

View File

@@ -0,0 +1,219 @@
/**
* Regex work in the compression engines stays bounded on hostile input
* (CodeQL #1301, #1302, #1349).
*
* - #1301 headroom/gcf needsQuote(): the inline-array check ran in O(n^2) on runs of `[`.
* - #1302 rtk maybePersistRtkRawOutput(): the command slug trim ran in O(n^2) on runs of `_`
* from a client-supplied tool_use command of unbounded length.
* - #1349 ccr grep: a caller-supplied pattern such as `.*.*.*.*x` passed the star-height
* gate and blocked the event loop for minutes on a single long line.
*
* Each block pairs a timing assertion (the pathological input finishes fast or is refused)
* with a behaviour assertion (ordinary input gives the same result as before).
*/
import { describe, it } from "node:test";
import assert from "node:assert/strict";
import fs from "node:fs";
import os from "node:os";
import path from "node:path";
import { needsQuote } from "../../../open-sse/services/compression/engines/headroom/gcf/scalar.ts";
import { maybePersistRtkRawOutput } from "../../../open-sse/services/compression/engines/rtk/rawOutput.ts";
import { queryBlock } from "../../../open-sse/services/compression/engines/ccr/ccrQuery.ts";
/** Ceiling for the fixed paths. They run in a few ms when idle; before the fix the same
* inputs took 10 s (#1301), 21 s (#1302) and minutes (#1349). The headroom absorbs a loaded
* CI runner (one fixed case reached 806 ms at load average 44) without hiding a regression. */
const FAST_MS = 1_000;
/** Upper bound for a grep stopped by its 1 s time budget (budget plus scheduling slack). */
const BUDGET_CEILING_MS = 5_000;
function timed<T>(fn: () => T): { value: T; ms: number } {
const t0 = performance.now();
const value = fn();
return { value, ms: performance.now() - t0 };
}
/** Reference semantics of the SPEC 2.4 inline-array rule: some `[` whose first following
* `]` is followed by optional whitespace and a `:`. Written as a plain linear scan. */
function hasInlineArrayHeader(s: string): boolean {
for (let i = 0; i < s.length; i++) {
if (s[i] !== "[") continue;
const close = s.indexOf("]", i + 1);
if (close === -1) return false;
let k = close + 1;
while (k < s.length && /\s/.test(s[k])) k++;
if (s[k] === ":") return true;
}
return false;
}
/** Deterministic PRNG (mulberry32) so the equivalence sample is reproducible. */
function prng(seed: number): () => number {
let a = seed >>> 0;
return () => {
a = (a + 0x6d2b79f5) >>> 0;
let t = a;
t = Math.imul(t ^ (t >>> 15), t | 1);
t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
describe("#1301 headroom/gcf needsQuote inline-array check", () => {
it("finishes fast on 50k '[' characters", () => {
for (const s of [
"[".repeat(50_000),
"a" + "[".repeat(50_000) + "]",
"[".repeat(50_000) + "]x",
]) {
const { value, ms } = timed(() => needsQuote(s));
assert.equal(value, false);
assert.ok(ms < FAST_MS, `needsQuote took ${ms.toFixed(1)}ms on ${s.length} chars`);
}
});
it("keeps the same verdict on ordinary values", () => {
assert.equal(needsQuote("ERR[404]: Not Found"), true);
assert.equal(needsQuote("[Speaker 1]: Hello"), true);
assert.equal(needsQuote("a[[b]: c"), true);
assert.equal(needsQuote("x[a[b] :y"), true);
assert.equal(needsQuote("arr[0] index"), false);
assert.equal(needsQuote("a]: [b"), false);
assert.equal(needsQuote("a[b] c: d"), false);
});
it("matches the reference rule on a random sample", () => {
const rand = prng(1301);
const alphabet = "[]: ab";
for (let n = 0; n < 20_000; n++) {
const len = Math.floor(rand() * 12);
let body = "";
for (let i = 0; i < len; i++) body += alphabet[Math.floor(rand() * alphabet.length)];
// Leading/trailing 'a' keeps the other needsQuote rules (edge space, numeric, '#'…)
// out of the way, so the verdict depends only on the inline-array rule.
const s = `a${body}a`;
assert.equal(needsQuote(s), hasInlineArrayHeader(s), JSON.stringify(s));
}
});
});
describe("#1302 rtk raw-output command slug", () => {
function persist(command: string) {
const base = process.env.DATA_DIR || os.tmpdir();
const dataDir = fs.mkdtempSync(path.join(base, "rtk-slug-"));
const previous = process.env.DATA_DIR;
process.env.DATA_DIR = dataDir;
try {
return timed(() =>
maybePersistRtkRawOutput("error: build failed\nline 2", { retention: "always", command })
);
} finally {
if (previous === undefined) delete process.env.DATA_DIR;
else process.env.DATA_DIR = previous;
fs.rmSync(dataDir, { recursive: true, force: true });
}
}
function slugOf(pointerPath: string): string {
const match = /^\d+-(.*)-[0-9a-f]{24}\.log$/.exec(path.basename(pointerPath));
assert.ok(match, pointerPath);
return match[1];
}
it("finishes fast on a 50k-underscore command", () => {
for (const command of ["_".repeat(50_000) + "x", "x" + "_".repeat(50_000) + "x"]) {
const { value, ms } = persist(command);
assert.ok(value, "pointer expected");
assert.ok(ms < FAST_MS, `slug took ${ms.toFixed(1)}ms on ${command.length} chars`);
}
});
it("keeps the same slug for ordinary commands", () => {
const cases: Array<[string, string]> = [
["git status --short", "git_status_--short"],
[" npm test -- --watch=false ", "npm_test_--_--watch_false"],
["__init__", "init"],
["cargo build --release && ./target/release/app", "cargo_build_--release_target_release_app"],
["a".repeat(100), "a".repeat(48)],
];
for (const [command, expected] of cases) {
const { value } = persist(command);
assert.ok(value);
assert.equal(slugOf(value.path), expected, command);
}
const { value } = persist("");
assert.ok(value);
assert.equal(slugOf(value.path), "tool-output");
});
});
describe("#1349 ccr grep pattern", () => {
it("refuses a multi-quantifier pattern on a 500+ char line quickly", () => {
const text = "a".repeat(600);
const { value, ms } = timed(() => queryBlock(text, { mode: "grep", pattern: ".*.*.*.*x" }));
assert.ok("error" in value, JSON.stringify(value));
assert.ok(ms < FAST_MS, `grep took ${ms.toFixed(1)}ms`);
});
it("stops a single-quantifier pattern that exceeds the time budget", () => {
// 2 MiB of 4096-char lines: `.*x` is quadratic per line (minutes before the fix).
const text = Array.from({ length: 512 }, () => "a".repeat(4095)).join("\n");
const { value, ms } = timed(() => queryBlock(text, { mode: "grep", pattern: ".*x" }));
assert.ok("error" in value, JSON.stringify(value).slice(0, 200));
assert.match((value as { error: string }).error, /time budget/);
assert.ok(ms < BUDGET_CEILING_MS, `grep took ${ms.toFixed(1)}ms`);
});
it("counts only unbounded quantifiers outside classes and escapes", () => {
const tooMany = ["a.*b.*c", "\\d+\\.\\d+", "x{2,}y+", "a.*?b.+?c"];
for (const pattern of tooMany) {
const r = queryBlock("abc", { mode: "grep", pattern });
assert.ok("error" in r, pattern);
assert.match((r as { error: string }).error, /unbounded quantifier/, pattern);
}
const text = ["l1 ERROR upstream timeout", "l2 *+ literal", "l3 {2,} braces", "l4 ok"].join(
"\n"
);
assert.deepEqual(queryBlock(text, { mode: "grep", pattern: "ERROR.*timeout" }), {
content: "l1 ERROR upstream timeout",
});
assert.deepEqual(queryBlock(text, { mode: "grep", pattern: "[*+]+ literal" }), {
content: "l2 *+ literal",
});
assert.deepEqual(queryBlock(text, { mode: "grep", pattern: "\\*\\+ lit.*" }), {
content: "l2 *+ literal",
});
assert.deepEqual(queryBlock(text, { mode: "grep", pattern: "\\{2,\\} b.*s" }), {
content: "l3 {2,} braces",
});
assert.deepEqual(queryBlock(text, { mode: "grep", pattern: "l[0-9]{1,2} (ok|ERROR)" }), {
content: "l1 ERROR upstream timeout\nl4 ok",
});
});
it("keeps grep results unchanged on an ordinary log block", () => {
const lines = Array.from(
{ length: 5_000 },
(_, i) => `2026-11-20T10:00:${String(i % 60).padStart(2, "0")}Z INFO req=${i} status=200`
);
lines[1234] = "2026-11-20T10:00:34Z ERROR req=1234 upstream timeout";
lines[4321] = "2026-11-20T10:00:01Z WARN req=4321 slow upstream";
const text = lines.join("\n");
const expected = (re: RegExp) => lines.filter((l) => re.test(l)).join("\n");
for (const pattern of ["ERROR", "(WARN|ERROR) req=", "req=12\\d\\d ", "^\\S+ WARN"]) {
assert.deepEqual(
queryBlock(text, { mode: "grep", pattern }),
{ content: expected(new RegExp(pattern)) },
pattern
);
}
assert.deepEqual(queryBlock(text, { mode: "grep", pattern: "INFO", unique: true }), {
content: lines
.filter((l) => l.includes("INFO"))
.slice(0, 1000)
.join("\n")
.concat("\n…[truncated at 1000 matches]"),
});
});
});