mirror of
https://github.com/diegosouzapw/OmniRoute.git
synced 2026-11-21 15:05:56 +00:00
Compare commits
3 Commits
chore/omni
...
fix/codeql
| Author | SHA1 | Date | |
|---|---|---|---|
|
|
2a48a0a823 | ||
|
|
c13cee2357 | ||
|
|
eca9826d29 |
1
changelog.d/fixes/20825-compression-regex-bounds.md
Normal file
1
changelog.d/fixes/20825-compression-regex-bounds.md
Normal 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)
|
||||
@@ -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:
|
||||
|
||||
219
tests/unit/compression/compression-regex-bounds.test.ts
Normal file
219
tests/unit/compression/compression-regex-bounds.test.ts
Normal 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]"),
|
||||
});
|
||||
});
|
||||
});
|
||||
Reference in New Issue
Block a user